CS310 DATA STRUCTURES (was Math 370: Data Structures)
OVERVIEW
The main problem we considered here was what changes should be made now that students have an introduction to data structures in Math 108. A few of us who have taught 370 many times observed that the syllabus below doesn't took much different from our "ideal' syllabus of several years ago, but in the past we often did not have time to cover all the topics. The introduction students get in 108 is very helpful (and especially valuable for non-CS majors who won't take more CS courses). It enables as to go a little faster at the beginning of each major topic in 370, so that we can cover the syllabus well ad perhaps adda few short additional topics.
For instructors not very familiar with the content of Math 108 and Math 578. we have made a few notes in the syllabus concerning overlapping topics.
REQUIRED? Yes
PREQUISITES
Math 108. (Discrete math will be restored as a prerequisite in the 1989 catalog).
PREREQUISITE FOR
480 (Ada), 520 (the new programming languages course), 575 (compilers), 578, 580, 592 (data bases), 583 (simulation), 584 (graphics), 585 (operating systems, and indirectly 588 (networks and distributed systems), and computer security.
MAIN CONCEPTS
In addition to the concepts related to the specific topics the following concepts should be used throughout the course as appropriate.
The concept of an abstract data structure as a collection of data with specific properties and specific operations.
The idea of isolating the details of data structures implementation in a few routines, so that the implementation can be changed easily without extensive modification to a large program.
Analysis of the time and space used by various algorithms, Big oh notation should be used, (The analysis and explanation of big oh need not be very formal.)
SYLLABUS
1. Introduction to Data structures and the computer system used for the course (one week).
2. Array implementation and addressing (112 week).
This is done in 108, but appears to need review-. in 370 mapping special-f6rm matrices (e.g., tridiagonal, tridiagonal) intolinear ways can be covered.
3. Linked lism simply linked lists, list heads, circular lisu, doubly linked lists, orthogonal lists, generalized (recursive) lists (this one could be deftmed until after reviewing recursion), applications (2 weeks).
>From 108. most students seem to be already comfortable with pointers in Pascal, implementation of linked lists in arrays using array indexes for pointen, and simply linked lists. Beyond that, there is a fair amount of variation, (Many students, of course did not take 108 here.)
4. Stacks and queues (1 1/2 wccks).
Students should already be familiar with the basic ideas and with both array and linked representation. Prefix/indix/postfix expressions should be covered in the course (either in the context of stacks, for evaluation and conversion between notations. or along with expression trees later, or both). Priority queues and simulation could be used as queue applications.
5. Recursion (1-2 weeks).
Recursion is introduced in 108. but to quote Carl, the students don't "own" it yet. Recursion can be presented as an application of stacks and as an important programming tool for data structures like trees and recursive lists. Both how it works (what goes on the stack and when) and how to program recursively should be covered.
6. Trees (3 weeks).
General and binary trees, representations inserting nodes, traversals, threaded binary trees, representation of general am as binary trees, binary search mm (AVL trees or other search trees if there's time), applications.
It is recommended that induction proofs be given for some quantitative aspects of binary trees (e.g. that the number of nodes can be an exponential function of the depth) and for the correctectness of some claims or algorithms (e.g, that inorder traversal of a binary search tree gives the keys in sorted order).
7. Hashing (1 1/2 weeks).
Hash functions, collision-resolution techniques (chaining. linear offset, others), discussion of average behavior. (In the past hashing has sometimes been skipped in 370. It is an essential topic, it is used in later courses)
8. Dynamic storage management and garbage collection (2-3 weeks).
DSM: The fragmentation problem. first At. best fit, next fit, boundary tags, buddy system. Garbage collection- free lists, reference counts, marking algorithms.
Additional topics, as time allows. may include graph representations, various search trees (e.g. AVL trees). more applications, etc. Depth-first and breadth-first search of graphs and digraphs are covered extensively in Math 578 they could get a brief introduction in 370.
PROGRAMMNG PROJECTS
Usually 3-5 programming assignments are given. Some instructors prefer to give separate, relatively short assignments for practice with individual data structures; others prefer to include a larger project that combines several structures. it is recommended that one program use recursion.
POSSIBLE TEXTS
There are several good texts, some choices are.
Data Structures in Pascal by Rcingold and Harm.
Data Structures., Form and Function by Harry Smith
Data Structures and Program Design by Robert Kruse.