## CPSC 327:

Data Structures and AlgorithmsDepartment 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

algorithmis the central concept of computer science. Closely related to algorithms are thedata structuresthat 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 theanalysisof 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

notwork 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.

DatesTopicsJan. 19, 21, 23 Introduction to Analysis of Algorithms:

Asymptotic AnalysisJan. 26, 28, 30 Abstract Data Types;

Lists, Stacks, and QueuesFeb. 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 FridayFeb. 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 21Mar. 22, 24, 28 Graph Algorithms:

Search; Shortest path algorithmsMar. 29, 31; Apr. 2 Graph Algorithms: Spanning Trees

Test on FridayApr. 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 algorithmsApr. 26, 28, 30 NP-complete problems May 3 Last day of class.

Wrapping up the course.May 9 Final Exam, 3:00 PM