Data Structures and AlgorithmsDepartment of Mathematics and Computer Science Hobart and William Smith Colleges Spring, 2004. Instructor: David J. Eck (email@example.com). Monday, Wednesday, Friday; 10:10--11:05. Room Lansing 311 (Math/CS Seminar Room).
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 firstname.lastname@example.org. 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:
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