Welcome to Design of Algorithms homepage

The site is dedicated to Design of Algorirthms, 2007 course. Be sure to read the General information page.

Syllabus

  • Reductions.
  • Greedy algorithms.
  • Dynamic programming.
  • Loop invariants and correctness proofs.
  • Union-Find data structure.
  • Amortized analysis.
  • Minimum spanning trees. Cuts.
  • Shortest paths algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall.
  • Depth First Search (DFS), strongly connected components, topological sort.
  • Maximum flow algorithms of Ford-Fulkerson, Dinitz. Applications to matching and assignment problems.
  • Randomized algorithms. Primality checking. RSA.
  • Introduction to complexity theory: complexity classes, Cook-Levin theorem, techniques for proving NP-completeness.

Text Books

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition.
    An online student source is available at CLRS for students.
  2. J. Kleinberg and E. Tardos, Algorithm Design.

Grade Calculation

The course grade will be composed of 65% final exam, 20% midterm and 15% homework assignments, provided the weighted average of the final exam and the midterm is at least 56. Otherwise the weighted average will be your course grade.

The weight of the midterm will decrease the higher the exam grade is, according to the following formula, let e - final exam grade, m - midterm grade, h - average homework grade, c - combined final exam and midterm grades and f - final course grade.

Here is the computation of f and c:

if (e > m) then:
    if (e-m < 45) then:
        w = 20-(e-m)/3
    else
        w = 5
else
    w = 20
c = ((85-w)*e + w*m)/85
if (c &ge 56) then:
    f = 0.85*c+0.15*h
else
    f = c