CS504A (Data Structures) Syllabus - Rivier College - Spring 1982 Page 1 General Information Instructor Donald Braffitt Date 12-Jan-1982 ---------- (603) 888-1311 Rivier X60 (Box 895) ---- (603) 883-7192 Home (Nights) (603) 884-6163 Office (Days) Tuesdays 7 PM to 9 PM; Louis Pasteur room LP112; 3 semester credits Class starts: 12-Jan-1982; Holiday: 23-Feb-1982; Final Exam: 27-Apr-1982 Course Standish, Thomas A. Data Structure Techniques. Textbook Reading, Massacusetts: Addison-Wesley Publishing Company, 1980. -------- 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. Teaching Strategies ------------------- Class will usually include reviewing the solutions to the problems/quizzes turned in at the beginning of class. New material will usually be introduced that corresponds to the problems due the following week. Course Requirements ------------------- The course prerequisites include material equivalent to CS501/MA304 (Fundamentals of Computation) and CS503/CS304 (Programming Languages). 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 9 problem sets (assigned 1 week before due) and 5 programming problems (assigned 2 weeks before due). There will also be 4 take-home chapter quizzes (assigned 1 week before due). 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 and closed notes). However, you are allowed to discuss the problem and programming assignments with any other member of the class. The final product on each homework 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 including problems, programming assignments, take-home quizzes and reviewing for exams) should average 4 to 8 hours per week. Please keep all graded homework assignments (including problems, programs and quizzes) 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 - 9 @ 3% each 27% Programming Assignments - 5 @ 5% each 25% Take-home chapter quizzes - 4 @ 3% each 12% Midterm exam (Chapters 1-4) 09-Mar (1st hour) 10% Final exam (Chapters 1-9) 27-Apr (both hours) 26% Problems sets and programming assignments will be graded primarily on effort. Quizzes and exams will be graded on effort and correctness. CS504A (Data Structures) Syllabus - Rivier College - Spring 1982 Page 2 Course Outline Chap 1 - Introduction (1 wk) Chap 5 - Lists (1.5 wks) 1.1 Introduction and motivation 5.1 Introduction and motivation 1.2 How the book is organized 5.2 Definitions and basic concepts 1.3 Basic concepts 5.3 List representation techniques 1.4 Mathematical background 5.4 Storage reclamation 5.5 Compacting and coexistence Chap 2 - Stacks and queues (1 wk) 2.1 Introduction and motivation Chap 6 - Multilinked structures (1 wk) 2.2 Notation 6.1 Introduction and motivation 2.3 Quicksort 6.2 Dynamic storage allocation 2.4 Representation of stacks and techniques queues 6.3 Management algorithms for multilinked structures Chap 3 - Trees (2 wks) 3.1 Introduction and motivation Chap 7 - Strings (2 wks) 3.2 Definitions and basic concepts 7.1 Introduction and motivation 3.3 Binary trees 7.2 Representations in contiquous 3.4 Linked tree representations storage 3.5 Representations in contiguous 7.4 Representations for variable- storage length strings 3.6 Binary tree traversal algorithms 7.5 Examples of operations on strings 3.7 Additional tree structures Chap 8 - Arrays (1 wk) Chap 4 - Tables (2 wks) 8.1 Introduction and motivation 4.1 Introduction and motivation 8.2 Basic concepts and notation 4.2 Searching sequential tables 8.3 Storage allocation functions 4.3 Hash tables 8.4 Linked allocation 4.4 Decision tables 4.5 Symbol tables Chap 9 - Files (1 wk) 9.1 Introduction and motivation 9.2 Properties of physical storage 9.3 File organization techniques For a given week, the problems, programs and/or quizzes are due at the beginning of class. The "Text" and "Topics" refer to the material that will be presented in class that day. Week Class Text Topics Assignments Due ---- ----- ---- ------ --------------- 1 12-Jan Chap 1 Introduction 2 19-Jan Chap 2 Stacks and queues Chap 1 problems 3 26-Jan Chap 3 Trees Chap 2 problems 4 02-Feb Prog 1 /Chap 1-2 quiz 5 09-Feb Chap 4 Tables Chap 3 problems 6 16-Feb Prog 2 /Chap 3 quiz *7 02-Mar Chap 5 Lists Chap 4 problems 8 09-Mar Midterm exam (1st hour) 9 16-Mar Chap 6 Multilinked structures Prog 3 /Chap 5 problems 10 23-Mar Chap 7 Strings Chap 6 problems 11 30-Mar Prog 4 /Chap 5-6 quiz 12 06-Apr Chap 8 Arrays Chap 7 problems 13 13-Apr Chap 9 Files Prog 5 /Chap 8 problems 14 20-Apr Review Chap 7-8 quiz /Chap 9 problems 15 27-Apr Final exam (both hours) * Note there is no class 23-Feb CS504A (Data Structures) Syllabus - Rivier College - Spring 1982 Page 3 Bibliography Berztiss, A. T. Data Structures Theory and Practice. Second Edition. New York: Academic Press, 1975. (includes appropriate prerequisite material - CS501/MA304). Cohen, Jacques. "Garbage Collection of Linked Data Structures." ACM Computing Surveys, Vol. 13, No. 3, Sep-1981, 341-367. Gotlieb, C. C. and Leo R. Gotlieb. Data Types and Structures. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1978. Horowitz, E. and S. Sahni. Fundamental 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. 2: Semi-Numerical Algorithms. Second Edition. Reading Massachusetts: Addison-Wesley Publishing Company, 1980 (First edition 1969). Knuth, Donald E. The Art of Computer Programming; Vol. 3: Searching amd Sorting. Reading Massachusetts: Addison-Wesley Publishing Company, 1973. Ledgard, Henry and Michael Marcotty. The Programming Language Landscape. Chicago: Science Research Associates, Inc., 1981. (includes appropriate prerequisite material - CS503/CS304). Page, E. S. and L. B. Wilson. Information Representation and Manipulation in a Computer. Cambridge, Great Britain: Cambridge University Press, 1973. Pfaltz, John L. Computer Data Structures. New York: McGraw-Hill Book Company, 1977. Tennenbaum, Aaron M. and Moshe J. Augenstein. data structures and pl/I. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1979. Tennenbaum, Aaron M. and Moshe J. Augenstein. Data Structures Using PASCAL. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1981.