# Fundamental Algorithms

## W 5-6:50, Room 101 M 5-5:50 Room 101

Alan Siegel
Office Hours: M: 6-7,W: 7-8.
Phone: 998-3122
The Mondays session is for recitation;
Recitation attendance is Highly Recommended

Teaching Assistance:
Jihun Yu
Room 308
Office Hours: M: 6-7,W: 7-8.
phone 998-3073

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. 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. Although some mathematical sophistication is very helpful for this course, the necessary mathematics is contained within the curriculum.

Because of the emphasis on problem solving, students are expected to attend the Monday recitation sessions, where sophisticated concepts will be reviewed and illustrated in depth.

Recursion
Depth-First-Search
The Greedy Method
Divide-and-Conquer
Dynamic Programming
Sorting- and Selection-based processing
Randomization
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
Minimum Spanning Trees
Shortest Path Problems

## Homework

• There will be approximately 11 written homework assignments that have, on average, about 10 exercises each. Perhaps one-third to one-half of these problems will be extremely challenging. That is, the necessary concepts will have already been taught, but a good deal of thought will be needed to figure out how to apply these techniques to solve the more challenging exercises.
• Students are not required to solve even the majority of the difficult problems, but they are expected to write down what ideas/methods they used, and where their solution method seems to have broken down.
• Students are also expected to compare their own answers with the solution handouts to see what concepts and techniques were overlooked. Because more than a third of the course is embedded in the exercises, students are expected to study the answers as a vehicle for mastering the material.