- Analysis of Algorithms: Basics about analysis of algorithms, worst case behavior, Order notation, Asymptotics.
- Some simple algorithms, stable marriages, gcd, primality, binary search.
- Sorting and Selection: Sorting techniques, Selection.
- Heaps and other Data Structures.
- Elementary Graph Theory.
- Graphs and search techniques: Depth first search, Breadth first search, Shortest Paths.
- Applications of Algorithms: DNA sequencing, Google, Mapquest.
- NP-completeness: What does it mean for a problem to be NP-complete? Examples of NP-complete problems.
- Lecture 1: Course Overview, General discussion of Algorithms, Euclid's GCD algorithm.
- Lecture 2: Running time of Euclid's algorithm. Fibonacci numbers.
- Lecture 3: Stable Marriage Problem. Proofs by Induction.
- Lecture 4: Analysis of algorithms.
- Lecture 5: Order notation. Selection.
- Lecture 6: Sorting .
- Lecture 7: Heaps.
- Lecture 8: Elementary graph theory. Orienting Graphs to make them strongly connected. DFS.
- Lecture 9: Representation of Graphs. Graph coloring. Planar Graphs.
- Lecture 10: Exam Review.
- Midterm Exam.
- Lecture 11: Matchings and their applications.
- Lecture 12: Google and pagerank. Hubs and authorities.
- Lecture 13: Hubs and authorities. BFS.
- Lecture 14: Euler tours and their applications. Hamilton tours.
- Lecture 15: Discuss projects and Euler tour algorithm.
- Visit to Cryptology museum. on Fri, Apr 9.
- Lecture 16: Dynamic Programming. Knapsack problem.
- Lecture 17: Dynamic Programming. Applications to Sequence comparison.
- Lecture 18: Cake cutting (guest lecture by Dr. Gasarch).
- Lecture 19: Dynamic Programming.
- Lecture 20: Shortest paths (Bellman-Ford) and Huffman coding.
- Lecture 21: Shortest paths (Dijkstra). NP-completeness.
- Lecture 22: Guest lecture by Bobby (Algorithms in Networking).
- Lecture 23: Review for final. NP-completeness.
- Lecture 24: Elementary Cryptography.
- Lecture 25: Guest lecture by Dr. Mount (Data compression).

Spring 2004

General Information Course Overview Homeworks and Handouts Lectures Related Stuff

Class Time |
Tue, Thu 3:30-4:45. |

Room |
CSIC 3118 |

Instructor |
Samir Khuller |

Office |
A.V. Williams 3369. |

Office phone |
405 6765 |

Office Hours (for rest of semester) |
Office hours will be THURSDAY, May 13 11-12am and TUES May 18th 11-12am. |

Email |
samir@cs.umd.edu |

The main point of this course is to study a few topics, and to explore the algorithmic methods and technology behind these methods. For the first few weeks we will review the history of algorithms, study many diverse (and easy) to understand algorithms. Finally we will pick a few topics and study the required graph theory and algorithmic tools required to understand the principles behind these software tools and packages.

Other readings will be given out in class.

General Course Information

Notes on GCD, Stable Marriages and Selection

Homework 1 Due on 2/17/04 Average: 27

Homework 2 Due on 2/26/04 Average: 30

Homework 3 Due on 3/11/04 Average: 36 Solution 3

Homework 4 Due on 4/6/04 Average: 34

In class MIDTERM on March 16 (Tuesday). Average 38.5

Homework 5 Due on 4/20/04 Average 29

Homework 6 Due on 5/06/04 Average: 36

Final is on May 19th (Wed) 10:30-12:30am.
**I WILL BE AVAILABLE ON FRI, MAY 21 11-12am to discuss the exam,
hand back project reports. You may also look over your graded exam
then**

Projects are due on May 17th (Mon) by 4:30pm.