The course described on this page ended May 10, 2004
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 PM. Room Lansing 311. Course Handout: http://math.hws.edu/eck/courses/cpsc327_s04.html
Information about CS 327
will be posted each week as the course is taught
during the Fall term of 2003.
First Week, January 19, 21, and 23.
The topic for this week is an introduction to the analysis of algorithms. The readings for this course will be handouts, some or all of which I will be writing as the course proceeds. Here is the reading for the first week:
Chapter 1: Asymptotic Analysis (PDF Format)
The first homework assignment is to do Exercises 1 and 2 from the end of this handout. These exercises are due in class next Monday, January 26.
Second Week, January 26, 28, and 30.
In the second week of the course, we turn to the second major topic: data structures. In particular, we will discuss the concept of Abstract Data Structures and look at stacks, queues, and lists as examples. On Monday, however, we will have a lab in the Math/CS computer lab, Lansing 312. The homework for he week consists of several exercises from the lab worksheet. These exercises will be due next Wednesday. Here is the worksheet for the lab:
And here is the reading for the week:
Chapter 2: Abstract Data Types (PDF Format)
Third Week, February 2, 4, and 6.
For the start of the week we will still be talking about Abstract Data Types, and the List data type in particular. You should finish reading Chapter 2. The homework for the week is Exercise 4 in that chapter, but starting with the randlist program from the lab. This exercise has a substantial writing component, which should be at least a page long (typed). Your programming for this assignment, and for all programming assignments in this course, must follow all the usual style guidelines, which you learned in Intermediate Programming. This assignment is due next Wednesday, February 11.
After finishing Chapter 2, we will move on to another abstract data type, the priority queue. We will see how the heap data structure can be used to implement priority queues. We will also use heaps to implement the efficient sorting algorithm known as HeapSort. Here is the reading for this material:
Chapter 3: Priority Queues and HeapSort (PDF Format)
Fourth Week, February 9, 11, and 13.
We will finish up HeapSort on Monday and then move on to some other sorting methods and some general facts about sorting. Remember that there is a test coming up on February 20 (Friday of next week).
Chapter 4: Sorting (PDF Format)
Fifth Week, February 16, 18, and 20.
We will finish up sorting on Monday by looking at a linear time sorting algorithm, Radix Sort. On Wednesday, we will start Chapter 5, which looks at the Set and Map ADT's and their implementation as hash tables. Here is a link to the reading:
Chapter 5: Hash Tables (PDF Format)
On Friday, we will have the first test of the term. It will cover Chapters 1 to 4. For more information, see:
Information sheet for the first test.
Sixth Week, February 23, 25, and 27.
After finishing up Hash Tables, we will be taking a look at the C++ standard template library (along with a review of C++ templates). The reading for the week will be handed out in class.
A programming assignment on Hash Tables is due next Monday, March 1.
Starting on Monday, February 23, several candidates for a computer science teaching position will be on campus. As one of your homework assignments for this course, you are required to attend three of the candidates' talks.
Seventh Week, March 1, 3, and 5.
After finishing up the standard template library, we will will look at binary sort trees and how they can be used to implement sets and maps. The reading for this material is:
Chapter 6: Trees (PDF Format)
A short assignment that uses the STL will be due next Wednesday:
Programming Assignment on Sets and Maps
Eighth Week, March 8 and 10.
There is no class on Friday of this week because of Spring Break. Classes resume on Monday, March 22. The topic for the week is B-Trees. Here is the reading:
Chapter 7: B-Trees (PDF Format)
Ninth Week, March 22, 24, and 26.
This week, we will start our study of graphs by looking at their representations and at algorithms for graph traversal. Here is the reading:
Chapter 8: Graphs (PDF Format)
There is an assignment on random graphs that will be due in three weeks, on Monday, April 12.
Please remember that there is a test next week on Friday, April 2.
Tenth Week, March 29 and 31; April 2
There is a test on Friday of this week. An information sheet about the test is available.
We will continue our study of graphs this week. On Monday, we will see how depth-first search can be used to do a topological sort of a directed acyclic graph. This is the last of the material that will be covered on the test. However, we will probably move on to other graph algorithms on Wednesday.
Here is the next reading. Note that only the first two sections of this reading are covered on the test:
Chapter 9: Graph Algorithms (PDF Format)
Eleventh Week: April 5, 7, and 9
After finishing Chapter 9, our next topic will be NP Complete Problems. The reading for this material is a handout that I will distribute in class.
Please remember that an assignment is due next Monday.
Twelfth Week: April 12, 14, and 16
We will continue with our study of NP-complete problems, based on the handout. The assignment that was due on Monday has been moved to Wednesday.
Don't forget that the annual department dinner is on Thursday at 6:00 PM in the Commons (Faculty Dining Room) in Scandling Center.
The final assignment for the term is now available and is due on the last day of class (Monday, May 3).
Thirteenth Week: April 19, 21, and 23
After finishing up NP-completeness on Monday, we will begin a new topic, dynamic programming. Here is the reading for this topic:
Chapter 10: Dynamic Programming (PDF Format)
(Note that there are several errors in this chapter that were corrected on a class handout.)
Fourteenth Week: April 26, 28, and 30
After finishing Chapter 10, we will begin our final topic of the term: cryptographic algorithms. We will start with an overview of cryptography. The reading for this is the Wikipedia entry on Cryptography at http://en.wikipedia.org/wiki/Cryptography. After this introduction, we will talk about some of the algorithms used. See the Wikipedia entry on RSA at http://en.wikipedia.org/wiki/RSA. Java has a class named BigInteger that provides many of the capabilities required for implementing RSA. I will discuss a demo program that uses these capabilities.
Remember that the last assignment of the term is due next Monday, May 3.
End of Term: May 3 and 10
Monday, May 3 is the last day of class. The final assignment is due is due in class on May 3 and will not be accepted late.
The final exam is scheduled for Monday, May 10, at 8:30 AM. (Note that the time given for the exam on the class handout was in error.) An information sheet is available for the exam. This sheet also contains more information about completing the assignments.
Congratulations and best wishes to graduating seniors. And to everyone, have a nice summer!