CS 234 | SCS

To study efficient algorithms and data structures in a language-independent setting. To become familiar with a number of standard data structures and algorithm design approaches. To gain additional experience in program design and implementation, and to appreciate the formal analysis of algorithms. This course combines many of the highlights of CS 240 and CS 341, but does not treat topics as thoroughly.

Intended Audience

This is a required course for all CS minors. It is intended to be of benefit to those wishing to understand the source of potential improvements and efficiencies in programs.

Related Courses

Prerequisites: One of CS 116, 126/124, 134, 136, 138, 145 taken fall 2010 or earlier, CS 146; Not open to Computer Science students.

Hardware/Software

References

Data Structures and Algorithm Analysis in Java, 2nd ed., by M.A. Weiss, Benjamin/ Cummings Publishing Company, 1995.

Schedule

Three hours of lecture per week, plus one hour tutorial. Normally available in Fall and Spring.

Notes

Outline

Introduction (4 hours)

Review of the analysis of algorithms, order notation and machine models. Top-down design of algorithms and data structures. Review of basic data types including lists, stacks, queues, and binary search trees. Choices of implementations of these primitive data types.

Trees and Search Trees (8 hours)

Trees as data types and data structures. The use of trees in several aspects of computing. The abstract data types ordered set and priority queue. Binary search trees and balanced search trees including B-trees. Considerations for use on secondary storage.

Hashing (4 hours)

The abstract data type unordered set and its implementation through hash tables. Particular attention paid to separate chaining and its efficiency, other approaches also discussed.

Graph Algorithms (7 hours)

Basic graph algorithms including shortest paths and minimum spanning tree. Depth-first search, breadth-first search, and their application to several problems. The use of previously introduced data structures in guaranteeing the efficiency of these methods.

Algorithm Design Techniques (8 hours)

A brief introduction to advanced algorithm design techniques including greedy algorithms, divide and conquer, and dynamic programming.

NP-Completeness and Concluding Remarks (4 hours)

The notion of NP-completeness and its consequences. The applications of techniques discussed in the course to approximate solutions to NP-complete problems.