C321 (Data Structures) Syllabus

Description:

The student will learn how to organize data for faster, more maintainable solutions to common programming problems such as sorting, searching, and optimization problems. The course focuses on a few fundamental structures and alternative machine representations. Thus, we consider lists, stacks, queues, trees, graphs, linked lists, heaps, and arrays. The advantages of data abstraction are described and illustrated. Algorithms based on the above topics are developed for some specific problems. Some tools of analysis are presented to provide the student with a rudimentary means of comparing alternative algorithms.

Prerequisites: CS 15-625-226 (Computer Science II)

Grading (approx):

The midterm counts 35%, the final 35%, and homeworks 30%. Class participation helps to bias things a bit. Grades are assigned on an informal "curve".

Homework Policy:

1. Up to seven homeworks may be assigned this quarter. It is expected that most of these will be rigorously graded. It is hoped that the student will be self-motivated and complete all the assignments for his/her own benefit.

2. Solutions will be graded on a scale of 0-10 by the grader.

3. Of course, students may discuss homework assignments with each other, may write solutions together, copy, or cheat in any way they can think of (except on the exams or any other graded component of the course). However, it is customary that any significant help from another student or book should be acknowledged in a comment when you ask me to review what you have.

Policy on Incompletes:

None given except in extreme emergency (death etc.)

Textbook:

Data Abstraction and Problem Solving with C++: Walls and Mirrors by F. M. Carrano, Addison-Wesley, ISBN: 0-8053-1226-9 (1995)

Schedule: (approximate, SUBJECT TO CHANGE)

Week	Class Material	Reading
March 31	Software Design Objectives, Review ADT	Chapters 1,3
April 7	Linked Lists, Stacks, Templates; Recursion	Chapters 4,6,2,5
April 14	Queues and Applications	Chapter 7
April 21	Algorithm Efficiency and Sorting	Chapter 9
April 28	Trees and Applications	Chapter 10
May 5	Review, Midterm; Priority Queues	Chapter 11
May 12	Conference	---
May 19	Heapsort and Balanced Trees	Chapters 11,12
May 26	Hashing and Graph Algorithms	Chapters 12,13
June 2	Graph Algorithms and B-Trees	Chapters 13,14