Fundamental Algorithms

Alan Siegel

Lecture: T 5:10-7:00, Room 109

Recitation: Th 5:10-6:00, Room 109

Office Hours: T 2-3, Th 6-7 and by appointment
Office: 330 Phone: 998-3122



This course covers the design and analysis of combinatorial algorithms. The curriculum is concept-based and emphasizes the art of problem-solving. The class features weekly exercises designed to strengthen conceptual understanding and problem solving skills.

Attendence in the recitation sessions is MANDATORY. In a few recitations, sophisticated problems will be solved by the class in closely supervised individual, collaborative, and group efforts. However, MOST of these sessions will be used to present additional course content.

Prerequisites: Although some mathematical sophistication is very helpful for this course, the necessary mathematics is contained within the curriculum.
However, students are presumed to have adequate programming skills and to have a solid understanding of basic data structures and their implementation in the programming languages of their choice. For example, students should be able to insert a record as a new leaf in a binary search tree. For those with no prior programming experience, a B or better in PAC II is expected. Anyone who lacks this background is expected to secure the written permission of the course instructor or the Director of the MS program.

Required Text: To be Announced.

A BRAND NEW edition of the coursee text will be available before the first day of class.
Information about how to acquire it will be posted here.

Course Topics

Algorithmic Design Paradigms

Recursion
Depth-First-Search
Breadth-First-Search
The Greedy Method
Divide-and-Conquer
Dynamic Programming
Sorting- and Selection-based processing
Randomization
Algorithm Redesign and Adaptation
Problem Transformations

The Analysis of Algorithmic Performance

Asymptotic Growth
Recurrence Equations
The Recursion Tree Solution Method
Probabilistic Analysis
Structural Analysis
Lower Bounds

Managing Data for Efficient Processing

Lists, Stacks, Queues, Priority Queues, Trees and Graphs
Tarjan's Categorization of Data Structures
Search Trees and their Enhancement
Union-Find
Sorting, Selection, and Hashing

Selected Representative Algorithms/problems

Topological Sort
Connected Components
Biconnected Components and Strong Components
Representative styles of Dynamic Programming and their applications
Standard Sorting and Selection Algorithms
Selected topics in Hashing
Shortest Path Problems
Minimum Spanning Trees

An approximate schedule of topics can be found here.

It will change as the lectures and organization are adapted to fit the evolving time constraints.

Homework

Course Grading Policy