\documentclass[11pt]{article} \usepackage{times} \usepackage{fancyheadings} \pagestyle{fancy} \usepackage{pifont} % for fancy bullets \newcommand{\mywidth}{6.0in} \newcommand{\st}{\rule[-.8mm]{0mm}{2mm}} \newcommand{\longst}{\rule[-3mm]{0mm}{2mm}} \newcommand{\outerbaselinesep}{13pt} \newcommand{\mh}{\vspace{-0.1in}\hspace{-0.2in}} \newcommand{\myvspace}{-0.2in} \newcommand{\mysvspace}{-0.1in} \topmargin 0.0in \oddsidemargin 0.25in \evensidemargin 0.25in \textwidth \mywidth \textheight 9.0in \parindent 0mm %10mm \parskip 3mm \newcommand{\headerfont}{\fontfamily{phv}\fontseries{b}\fontshape{n}% \fontsize{10}{12pt}\selectfont} \newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}% \fontsize{11}{13pt}\selectfont} \newcommand{\largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{13}{15pt}\selectfont} \newcommand{\Largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{19}{21pt}\selectfont} \newcommand{\largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}% \fontsize{13}{15pt}\selectfont} \newcommand{\sfb}{\fontfamily{phv}\fontseries{b}\fontshape{n}% \fontsize{11}{13pt}\selectfont} \newcommand{\sfbi}{\fontfamily{phv}\fontseries{b}\fontshape{it}% \fontsize{11}{13pt}\selectfont} %%%%%%%%% Headings %%%%%%%%%%%%%%%%%%%%%%% \setlength{\headwidth}{\textwidth} % This shouldn't be needed. ?? %\setlength{\headrulewidth}{0pt} % to eliminate rule under header \newcommand{\currhead}{CS 1723, Course Information and Tentative Syllabus, \today} \lhead{\footnotesize \currhead} \rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}} \lfoot{} \chead{} \cfoot{} \rfoot{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \begin{center} {\largebold CS 1723, Data Structures---Fall Semester, 1998 \\ {\largeboldital Course Information and Tentative Syllabus} } \end{center} \baselineskip=\outerbaselinesep %\vspace{\mysvspace} %\mh{\sfb Course:} CS 1723, Data Structures. \vspace{\myvspace} \mh{\sfb Time, Place, Dates:} \vspace{\mysvspace} CS 1723, Section 001 MWF 1-1:50 pm, 3.04.06 BB. \\ (Students must also take: \hspace*{1mm}CS 1721-001: W 12--12:50 pm, 3.04.06 BB \\ \hspace*{1mm}First class meets Monday, August 24, 1998. \\ \hspace*{1mm}Final exam: Wednesday, December 9, 1:30-4:15 pm.) \mh{\sfb Instructor:} \vspace{\mysvspace} Dr. Neal R. Wagner, Office: 3.02.16 SB, Telephone: (210)458-5550. \\ E-mail: wagner@cs.utsa.edu, wagner@runner.jpl.utsa.edu \mh{\sfb Prerequisites:} \vspace{\mysvspace} The official prerequisites are: CS 1713 and MAT 1214. In practice you need programming experience in C, including especially the use of functions with parameters. The topics of C pointers, and recursion are not on the CS 1713 syllabus, and will be covered ``from scratch'' in this course. C {\tt struct}s will also be covered from scratch, but quickly. There will be a review of other parts of C. You also need to know the rudiments of Unix from a user perspective. \mh{\sfb Class Newsgroups and On-line Access:} \vspace{\mysvspace} This course will use e-mail on runner for announcements by the instructor and for answers to student questions. You should send questions to me by e-mail. I will send you an individual answer, but in most cases I will also send the question andan answer to all students, with the name and identifying information stripped off. I plan to carry out much of the work for this course over the network. All materials, including assignments, sample programs, and even this document, will be available on runner in the directory: \vspace{\myvspace} %\vspace{\mysvspace} \begin{verbatim} runner% cd ~wagner/pub/CS1723 \end{verbatim} \vspace{\mysvspace} \mh{\sfb Textbooks:} \vspace{\myvspace} \begin{list}{dummy}{\parsep=0.5mm \itemsep=0mm} \item [\ding{42}] {\bf Required:} {\em The C Programming Language}, Kerhighan and Ritchie, Prentice-Hall, Second Edition, 1988. (This is the standard `bible'' on the C language, written by one of C's originators. The text also covers data structures material. The C code in this book, including its formatting, can be used as a model for the code for the course. Though an excellent book, this text is sophisticated and can be difficult to understand.) \item [\ding{42}] {\bf Possibly helpful:} {\em Data Structures in C}, Drozdek and Simon, PWS, 1995. (This is a useful reference for the course, but I will not be following it. Instead, much of the course material will be presented using handouts.) \item [\ding{42}] {\bf Possibly helpful:} {\em Introduction to Algorithms}, Cormen, Leiserson, and Rivest, MIT Press, 1990. (Another useful reference for the course that I will use on occasion. This book is also used for the Algorithms course, CS 3343.) \end{list} \vspace{\mysvspace} \mh{\sfb Course Objectives:} \vspace{\myvspace} \begin{list}{dummy}{\parsep=0.5mm \itemsep=0mm} \item [\ding{224}] Introduction to data structures such as arrays, structs, lists, stacks, queues, trees, and their variations, including linked-list versions. \item [\ding{224}] Introduction to recursion and its uses. \item [\ding{224}] Discussion of hashing techniques. \item [\ding{224}] Elementary searching and sorting methods. \item [\ding{224}] Details of the C programming language. This includes especially C pointers, structs, and strings. \item [\ding{224}] Familiarity with the Unix environment. \item [\ding{224}] Introduction to object-oriented programming concepts, such as abstract data types, information hiding, objects (with associated data and functions). \item [\ding{224}] Discussion of storage management, including C stack-based storage, C {\tt static} storage, and storage created with {\tt malloc} and accessed through pointers. Also simulation of pointer storage using arrays (allocation, use and deallocation). \item [\ding{224}] Introduction to algorithm design and analysis techniques. \item [\ding{224}] Introduction to various applications of data structures. \end{list} \vspace{\mysvspace} \mh{\sfb Course Requirements (with {\sfbi tentative} percentages of grade):} \vspace{\myvspace} \begin{list}{dummy}{\parsep=0.5mm \itemsep=0mm} \item [\ding{228}] Programming (7--9 assignments at roughly 5\% each, about 45\% of grade): There will be up to 9 programming assignments, each handed out one or two weeks before the due date. Some will be harder than others, so the credit for these assignments may vary. These must be well-documented and well-structured, as illustrated in your textbooks. Usually you will turn in a single listing giving the source program and any required output. {\bf Note:} The programming assignments are a basic course requirement, like engineering lab work, and not like homework in a calculus class. You {\em must} complete most of the programs in order to pass the course. % \vspace{\mysvspace} \item [\ding{228}] Two In-class Exams (2 at 15\% each = 30\% of grade). \item [\ding{228}] Final Exam (25\% of grade): The final will be nearly twice the length of the other exams. It will be comprehensive, but with emphasis on material covered after the second hour exam. \end{list} \vspace{\mysvspace} \mh{\sfb Laboratories:} \\ The laboratory meets Monday and Wednesday at 9 am. All students should show up for each Monday lab. There will be presentations, required work, quizzes, questions answered, etc. Students who do not complete all the work or have further questions should come to the Wednesday lab session for additional help. The laboratory classes are there to review material about the C language and to go over questions and problems related to the programs. The laboratory instructors will keep track of attendance and participation. You will get a separate grade in the lab, not necessarily the same grade as in the lecture. %\vspace{\mysvspace} \mh{\sfb Late Assignments:} \\ For full credit, programming assignments must be completed and turned in at the start of class on the Friday shown in the Syllabus. If this deadline is missed, then assignments may be turned in at the start of class on the next Monday and will receive a 25\% penalty. Assignments should only be turned in at the start of class on Friday or the following Monday, and not between classes. Answers will often be provided during class on the Monday after the assignment is due, so they cannot be accepted after the start of class on Monday. \mh{\sfb Scholastic Dishonesty:} \vspace{\mysvspace} \noindent From the UTSA Catalog: {\em The integrity of a university degree depends on the integrity of the work done for that degree by each student. The University expects a student to maintain a high standard of individual honor in his/her scholastic work. \noindent ``Scholastic dishonesty'' includes, but is not limited to, cheating on a test or other class work, plagiarism (the appropriation of another's work and the unacknowledged incorporation of that work in one's own written work offered for credit), and collusion (the unauthorized collaboration with another person in preparing course work offered for credit).} \noindent In practice, for this course, you may discuss assignments in general terms, but you are not allowed to share any details of actual algorithms or of program code. You may help someone else debug their program as long as you do not start substituting in your own code when there are problems. Turning in a copy of someone else's program, even a copy with extensive changes made to it, is a very serious offense in this course. \mh{\sfb Missed Classes:} \vspace{\mysvspace} \noindent You are urged to get to know other class members so that you can find out what happened in class if you have to miss. \newpage \begin{center} {\largebold CS 1723, Tentative Course Syllabus, Fall 1998 } \end{center} \renewcommand{\arraystretch}{1.1} \noindent \begin{tabular} {|r|l|l|l|p{3.3in}|} \hline & {\bf Dates} & {\bf D \& S}& {\bf K\&R} & {\bf Topics Covered} \\ \hline \hline 1 & Aug 24, 26, 28 & 1 & 1-4& Intro, course organization. C review, esp. operators and precedence, functions and parameters. {\bf [Classes start Aug 24]} \\ \hline 2 & Aug 31, 2, 4 & 6 & 5 & Stacks and queues, using arrays. static and auto storage\\ & & & & {\bf [Program 1 (3/2 problem): Due Sep 4.]} \\ \hline 3 & Sep 9, 11 & 5, 7& 6 & Dynamic memory allocation, linked lists, recursion. \\ & & & &{\bf [Sep 7 is Labor Day.]}\\ & & & & {\bf [Program 2 (RPN evaluation): Due Sep 11.]} \\ \hline 4 & Sep 14, 16, 18 & same & 6 & Same as week 3. \\ & & & & {\bf [Program 3 (Queues): Due Sep 18.]} \\ \hline 5 & Sep 21, 23, 25 & & 5 & Strings in C, pointers, pointer arithmetic.\\ & & & & {\bf [Program 4 (Strings): Due Sep 25.]} \\ \hline 6 & Sep 28, Oct 30, 2& - & 7 & Files in C. \\ & & & & {\bf [FIRST EXAM : Oct 30.]} \\ \hline 7 & Oct 5, 7, 9 & 7, 8& 6 & Binary trees, recursion. \\ & & & & {\bf [Program 5 (Translation to RPN): Due Oct 9.]} \\ \hline 8 & Oct 12, 14, 16 & 7, 8& 6 & More binary trees, recursion. \\ & & & & {\bf [Program 6 (All words in a string): Oct 16.]} \\ \hline 9 & Oct 19, 21, 23 & 11 & 5,6& Searching and sorting. \\ & & & & {\bf [Last day to drop: Oct 23.]} \\ \hline 10 & Oct 26, 28, 30 & 11 & 5,6 & More searching and sorting. \\ & & & & {\bf [Program 7 (Concordance): Due Oct 30.]} \\ \hline 11 & Nov 2, 4, 6 & - & 5 & 2-dim arrays and pointers. \\ & & & & {\bf [SECOND EXAM : Nov 4.]} \\ \hline 12 & Nov 9, 11, 13 & - & 5 & structs and pointers. \\ & & & & {\bf [Program 8 (Recursive bdry recog.): Nov 13.]} \\ \hline 13 & Nov 16, 18, 20 & - & 4 & C preprocessor. \\ \hline 14 & Nov 23, 25 & - & - & Object-oriented programming in C.\\ & & & & {\bf [Program 9 (Sorting/searching): Nov 25.]} \\ & & & &{\bf [Nov 26 is Thanksgiving]} \\ \hline 15 & Nov 30, Dec 2 & - & - & Leeway. {\bf [Study: Dec 3, 4.]} \\ \hline\hline & Dec 9 & & & {\bf [Final Exam, 1:30--4:15 pm]} \\ \hline \end{tabular} \vspace{-0.1in} \noindent {\bf Programs due: Fridays. } \vspace{-0.1in} \noindent {\bf Exams: Wednesdays.} \newpage \begin{center} {\largebold CS 1721, Tentative Laboratory Syllabus, Fall 1998 } \end{center} \noindent \begin{tabular} {|r|l|p{4.0in}|} \hline & {\bf Dates} & {\bf Topics Covered} \\ \hline \hline 1 & Aug 26 & Review of C, examples with structs. \\ \hline 2 & Sep 2 & Storage classes (static, auto). \\ & & {\bf [Jan 19 is MLK Day.]}\\ \hline 3 & Sep 9 & Working with linked lists. \\ \hline 4 & Sep 16 & More work with linked lists. \\ \hline 5 & Sep 23 & Working with strings and pointers. \\ \hline 6 & Sep 30 & Files in C. \\ \hline 7 & Oct 7 & Binary tree examples. \\ \hline 8 & Oct 14 & More binary tree examples. \\ \hline 9 & Oct 21 & A specific sort algorithm. \\ & & {\bf [Last day to drop: Oct 23.]} \\ \hline \hline 10 & Oct 28 & Another sort algorithm. \\ \hline 11 & Nov 4 & 2-dim arrays and pointers. \\ \hline 12 & Nov 11 & Structs and pointers. \\ \hline 13 & Nov 18 & C preprocessor. \\ \hline 14 & Nov 25 & Leeway \\ \hline 15 & Dec 2 & Leeway {\bf [Study: Dec 3, 4.]} \\ \hline \hline & Dec 9 & {\bf [Final Exam, 1:30--4:15 pm]} \\ \hline \end{tabular} Labs are used to help with assignments and to answer questions, as well as to cover special material. \renewcommand{\arraystretch}{1.0} \label{'thatsall'} \end{document}