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.