CS504A/CS304E (Data Structures) - Rivier College - Spring 1983 Page 1 Syllabus - General Information INSTRUCTOR Donald Braffitt DATE 11-Jan-1983 ---------- (603) 888-1311 Rivier X60 (Box 895) ---- (603) 883-7192 Home (Nights) (603) 881-2139 Office (Days) Tuesdays 7:45 PM to 9:45 PM; Mendel Hall Room MH201; 3 semester credits Class starts: 11-Jan-1983; Holiday: 22-Feb-1983; Final Exam: 26-Apr-1983 COURSE Aho, Alfred V., John E. Hopcroft and Jeffrey D. Ullman. TEXTBOOK Data Structures and Algorithms. Reading, Massacusetts: -------- Addison-Wesley Publishing Company, 1983. OBJECTIVES ---------- This course will introduce the following data structure concepts: lists; strings; arrays; trees; graphs; storage systems and structures; storage allocation and garbage collection; searching and sorting techniques; generalized data management systems. PREREQUISITES ------------- CS501/MA304 (Fundamentals of Computation) or material equivalent to Schaum's Outline for Theory and Problems of Discrete Mathematics, and proficiency in at least 2 programming languages. COURSE REQUIREMENTS ------------------- The required work for the course consists of a set of problems, programs and take-home quizzes as well as in-class written midterm and final exams. There will be 12 problem sets (assigned 1 week before due) and 5 programming assignments (assigned 2 weeks before due). There will also be 5 take-home chapter quizzes (assigned 1 week before due). Problems sets and programming assignments will be graded primarily on effort. Quizzes and exams will be graded on effort and correctness. You are responsible for all material presented in class as well as the appropriate textbook material. Attendance will be taken each class period. Regular attendance is expected. The work you turn in on quizzes and exams must be entirely your own (all in-class exams will be closed book - 1 page of notes will be allowed). However, you are allowed to discuss the problem sets and programming assignments with any other member of the class. The final product on each problem set and programming assignment must be substantially your own work. Homework must be handed in at or prior to the beginning of class on the day it is due. The work you do outside of class for this course (reviewing class notes, reading, homework assignments and reviewing for exams) should average 6 to 10 hours per week. Please keep all graded homework assignments and exams until the course is over. The homework assignments and exams should generally be handed back graded the following week. HOMEWORK AND EXAMINATIONS GRADING WEIGHTS ------------------------- --------------- Problem sets 12 @ 3% each 36% Programming assignments 5 @ 4% each 20% Take-home chapter quizzes 5 @ 2% each 10% Midterm exam (Chapters 1-5) 08-Mar (1st hour) 10% Final exam (Chapters 1-12) 26-Apr (both hours) 24% CS504A/CS304E (Data Structures) - Rivier College - Spring 1983 Page 2 Syllabus - Course Outline / Bibliography COURSE OUTLINE -------------- For a given week, the assignments are due at the beginning of class, and the indicated material will be introduced in class that day. Week Class Text Topics Assignments Due ---- ----- ---- ------ --------------- 1 11-Jan Chap 1 Algorithm Design/Analysis 2 18-Jan Chap 2 Basic Data Types Chap 1 probs 3 25-Jan Chap 3 Trees Chap 2 probs 4 01-Feb Chap 4 Basic Operations on Sets Chap 3 probs Prog 1 5 08-Feb Chap 5 Advanced Set Structures Chap 4 probs Chap 1-2 quiz 6 15-Feb Chap 6 Directed Graphs Chap 5 probs Prog 2 * 22-Feb ** No Class -- School Holiday ** 7 01-Mar Chap 7 Undirected Graphs Chap 6 probs Chap 3-4 quiz 8 08-Mar Midterm exam (1st hour) 9 15-Mar Chap 8 Sorting Chap 7 probs Prog 3 10 22-Mar Chap 9 Algorithm Analysis Chap 8 probs Chap 6 quiz 11 29-Mar Chap 10 Algorithm Design Chap 9 probs Prog 4 12 05-Apr Chap 11 External Structures Chap 10 probs Chap 7-8 quiz 13 12-Apr Chap 12 Memory Management Chap 11 probs Prog 5 14 19-Apr Chap 12 probs Chap 9-10 quiz 15 26-Apr Final exam (both hours) BIBLIOGRAPHY ------------ Aho, Alfred V., John E. Hopcroft and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Reading, Massachusetts: Addison-Wesley Publishing Company, 1974. [advanced data structure techniques] Berztiss, A. T. Data Structures Theory and Practice. Second Edition. New York: Academic Press, 1975. [set theory, graph theory, algebra, introduction to languages and automata, data structure examples in FORTRAN; CS501/MA304 (Fundamentals of Computation) text - fall 1981] Lipshutz, Seymour. Schaum's Outline for Theory and Problems of Discrete Mathematics. New York: McGraw-Hill Book Company, 1976. [set theory, graph theory, algebra, combinatorics, matrices; good self-teaching text for CS501/MA304 (Fundamentals of Computation) material]. Liu, C. L. Elements of Discrete Mathematics. New York: McGraw-Hill Book Company, 1977. [set theory, graph theory, algebra, combinatorics; CS501/MA304 (Fundamentals of Computation) text - fall 1982]. Horowitz, E. and S. Sahni. Fundamentals of Data Structures. Woodland Hills, California: Computer Science Press, 1976. Knuth, Donald E. The Art of Computer Programming; Vol. 1: Fundamental Algorithms. Second Edition. Reading, Massachusetts: Addison-Wesley Publishing Company, 1973 (First edition 1968). Knuth, Donald E. The Art of Computer Programming; Vol. 3: Searching and Sorting. Reading, Massachusetts: Addison-Wesley Publishing Company, 1973. Standish, Thomas A. Data Structure Techniques. Reading, Massacusetts: Addison-Wesley Publishing Company, 1980. [Knuth-style algorithm notation; CS504/CS304 (Data Structures) text - spring 1982]