CS 344 Algorithms and Data Structures
Spring 2002

Official Course Description. The primary goal of this course is to build on the programming skills gained in CS 141 and 142 to introduce students to more sophisticated algorithms and data structures and the notion of algorithm design. The course also introduces the basic formalism and concepts used in the analysis of algorithms. The relative efficiency of the algorithms studied is estimated by informal application of these ideas. The algorithms and data structures discussed include those for sorting and searching, pattern matching, set representation, graph problems, dynamic programming and others. Programming exercises based on "realistic" applications help students to understand the often difficult process of reducing a real-world problem to a standard algorithmic question.

Pre and corequisites. Prerequisite: CS142 (or EE363). Corequisite: MA211 or MA346.

Instructor. James Lynch
Office: Science Center 381
Phone: 268-2374
E-mail: jlynch@clarkson.edu.

Office Hours. M 2:30-4:00, Tu 10:00-11:00, W 10:00-11:30, Th 4:00-5:00.

Required Text.

Course Objectives.

  1. To learn more advanced data structures such as trees, hash tables and priority queues.

  2. To be introduced to more advanced algorithmic issues such as a detailed analysis of sorting, some graph algorithms, some algorithm design techniques and the P vs NP question.

  3. To further develop coding and debugging skills.

Demonstrable outcomes. By the end of the semester,

  1. You will be familiar with the basic data structures and algorithms provided in the C++ Standard Template Library.

  2. You will understand how and when to use more sophisticated data structures such as trees, hash tables and priority queues.

  3. You will be able to implement and analyze those data structures.

  4. You will have a fairly complete understanding of sorting algorithms.

  5. Time permitting, you will also be familiar with some graph algorithms, with some techniques for algorithm design and with the P vs NP question.

Topics to be covered. Algorithm analysis, sorting, the STL, trees, binary search trees, balanced trees, hash tables, priority queues (heaps), and, as time permits, a selection of graph algorithms, of algorithm design techniques, and the P vs NP question.

Grading. You will be evaluated based on several homework assignments (which will likely be mostly programming assignments), two tests and a final exam. Your course grade will be computed using the following formula:

20% A + 20% T1 + 20% T2 + 40% F

Policy for missed work. There will be no make-up assignments. Late assignments may be accepted if a good excuse is provided and if arrangements are made at a reasonable time, in advance, if possible. Make-up tests can be arranged under the same conditions. Other special arrangements can be made for students forced to miss more than a few days of class.