CPSC 327: Data Structures and Algorithms

CPSC 327:
Data Structures and Algorithms
   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Spring, 2004.

   Instructor:  David J. Eck (eck@hws.edu).

   Monday, Wednesday, Friday; 10:10--11:05.
         Room Lansing 311 (Math/CS Seminar Room).
About CS327

This is a course in advanced programming. In many ways, it is a continuation of CPSC 225 (Intermediate Programming). The focus in this course is more theoretical, but the topics covered are important to any working computer scientist.

The idea of algorithm is the central concept of computer science. Closely related to algorithms are the data structures that they manipulate. In this course, you will encounter a variety of important data structures and the algorithms that are associated with them. We also focus on the analysis of algorithms, that is, the investigation of the efficency or resource requirements of algorithms.

We will not use a textbook for this course. Instead, the course will be based on weekly handouts and other assigned readings. See the tentative weekly schedule, below, for a list of specific topics that we will cover.

Homework and Programming Assignments

Most of the assignments for this course will be programming assignments in which you are asked to implement or use the data structures and algorithms that we cover. Many of the programming assignments can be done in your choice of Java or C++, but there will be some that require features that are unique to C++. On a few occasions, we will use all or part of a class for a lab, which will be held in the Math/CS computer lab (Lansing 312). These labs will be starting points for some of the assignments.

In addition to the programming assignments, there will be some written exercises that ask you to do problems or work with the more theoretical aspects of the course.

Unless specifically stated, the assignments for this course are individual assignments. You should do individual assignments on your own. You should not work on them with other people in the class.

Tests and Grading

There will be two in-class tests, which will be given on Friday, February 20 and Friday, April 2. There will also be a final exam during the scheduled final examination period, 3:00--6:00 PM on Sunday, May 9.

Your grade for the course will be computed as follows:
            First Test:        17%
            Second Test:       17%
            Final Exam:        22%
            Assignments:       44%
My expectation is that you will be in class unless you have a very good reason. I reserve the right to lower your final grade in the course by up to a full letter grade because of excessive absences.

Office Hours, E-mail, and WWW

My office is room 301 in Lansing Hall. My office phone extension is 3398. I am on campus most days, and you are welcome to come in any time you can find me there. I will announce regular office hours (when I promise to try my best to definitely be in my office) as soon as I schedule them.

My e-mail address is eck@hws.edu. E-mail is good way to communicate with me, since I usually answer messages the day I receive them.

The Web page for this course is at http://math.hws.edu/eck/cs327_s04/. This page will contain a weekly guide to the course, including links to readings and assignments.

Tentative Weekly Schedule

Here is a very tentative weekly schedule for the course. I might make changes to this schedule as the term proceeds. The last four weeks of the course are especially subject to change. See the course web page for updated weekly information.

Dates Topics

Jan. 19, 21, 23 Introduction to Analysis of Algorithms:
Asymptotic Analysis

Jan. 26, 28, 30 Abstract Data Types;
Lists, Stacks, and Queues

Feb. 2, 4, 6 Priority Queues, Heaps, and Heapsort

Feb. 9, 11, 13 Quicksort and radix sort

Feb. 16, 18, 20 Sets and Sorted sets; Hash tables
Test on Friday

Feb. 23, 25, 27 More on hashing; Binary trees

Mar. 1, 3, 5 B-Trees

Mar. 8, 10 Graphs and their representations

Spring Break
Friday March 12 -- Sunday, March 21

Mar. 22, 24, 28 Graph Algorithms:
Search; Shortest path algorithms

Mar. 29, 31; Apr. 2 Graph Algorithms: Spanning Trees
Test on Friday

Apr. 5, 7, 9 Greedy algorithms; Vertex coloring

Apr. 12, 14, 16 Dynamic Programming (or other topic)

Apr. 19, 21, 23 Amortized Analysis (or other topic);
Polynomial time and NP algorithms

Apr. 26, 28, 30 NP-complete problems

May 3 Last day of class.
Wrapping up the course.

May 9 Final Exam, 3:00 PM

Dates	Topics
Jan. 19, 21, 23	Introduction to Analysis of Algorithms: Asymptotic Analysis
Jan. 26, 28, 30	Abstract Data Types; Lists, Stacks, and Queues
Feb. 2, 4, 6	Priority Queues, Heaps, and Heapsort
Feb. 9, 11, 13	Quicksort and radix sort
Feb. 16, 18, 20	Sets and Sorted sets; Hash tables Test on Friday
Feb. 23, 25, 27	More on hashing; Binary trees
Mar. 1, 3, 5	B-Trees
Mar. 8, 10	Graphs and their representations
Spring Break Friday March 12 -- Sunday, March 21
Mar. 22, 24, 28	Graph Algorithms: Search; Shortest path algorithms
Mar. 29, 31; Apr. 2	Graph Algorithms: Spanning Trees Test on Friday
Apr. 5, 7, 9	Greedy algorithms; Vertex coloring
Apr. 12, 14, 16	Dynamic Programming (or other topic)
Apr. 19, 21, 23	Amortized Analysis (or other topic); Polynomial time and NP algorithms
Apr. 26, 28, 30	NP-complete problems
May 3	Last day of class. Wrapping up the course.
May 9	Final Exam, 3:00 PM