Computer Science 6783 -- Applied Algorithms, Winter 2012

Announcements |

Course information |

Important dates |

Assignments and tests |

Lecture notes

Assignments and tests

For typesetting please use LaTeX. A good introduction to LaTeX is "Essential LaTeX" .

Lectures: 15:30-16:50 Tuesday/Thursday (note the change!) in the seminar room (EN-2022)
Instructor: Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: -Mondays 5-6pm, Wednesday 1-2pm, or by appointment.
Textbook: There will be no official textbook for this course.

Reference book:

J. Kleinberg, E. Tardos. Algorithm Design.
Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.

We will also use other materials such as research papers.

Marking scheme (tentative!): 3 assignments 10% each, a test 30%, and a project 30% with a 10% presentation.

Description: The goal of this course is to study both classical and advanced algorithm design techniques with emphasis on real-world applications. We will cover greedy algorithms, dynamic programming, backtracking as well as fast Fourier transform, Integer Linear Programming, etc. The applications would come from many fields, including Bioinformatics and Cryptogaphy. Time permitting, we will consider randomized, parallel and distributed algorithms, and/or streaming algorithms.

Lecture Notes

A brief list of topics for the test (review sheet).

Lecture 1 (Jan 6): Introduction and Stable Marriage Problem
Lecture 2 (Jan 10): Stable matching problem analysis and "representative problems" (KT chapter 1)
Lecture 3 (Jan 13): Greedy algorithms: interval scheduling, scheduling with deadlines and profits, 1/2 approximation for knapsack
Lecture 4 (Jan 17): Data compression: Huffman code,(KT4.8) LZ77, gzip Additional readings: gzip algorithms
Lecture 5 (Jan 19): Minimum Spanning Tree: algorithms of Kruskal and Prim
Lecture 6 (Jan 24): String Matching: Rabin-Karp algorithm (scribed by Md. Asaduzzaman)
Lecture 7 (Jan 26): String Matching: Knuth-Morris-Pratt algorithm
Lectures on dynamic programming
Lecture 11 (Feb 14): Bellman-Ford algorithm (scribed by Abdullah Al Mamun)
Lectures on network flows (from previous course)
Lectures 14 and 15 (Feb 28 and Mar 1st): bioinformatics applications, guest instructor Lourdes Peña-Castillo
Lecture 17 (Mar 8th) Divide-and-conquer, closest points problem (from KT).
Lecture 18 (Mar 13th) Fast Fourier Transform and polynomial multiplication
Lecture 19 (Mar 15th) Limits of tractability, survey