Design of Algorithms

The objective of this course is to familiarize students with common methods in designing efficient algorithms for various problems. The presentation will emphasize algorithm efficiency analysis and correctness proofs. Additionally, some advanced data structures used in designing efficient algorithms will be presented.

• Preliminaries and Sample Problems (1 session)
  • 3-SUM problem, introduction to o and ω notations
• Induction-based Algorithms (1 session)
  • Polynomial evaluation, one-to-one mapping, famous star problem
• Divide and Conquer (1 session)
  • Closest pair of points, matrix multiplication
• Greedy Algorithms (1 session)
  • Huffman coding, stable matching
• Dynamic Programming (2 sessions)
  • Knapsack problem, longest increasing subsequence, independent set on trees
• State Space Search (1 session)
  • Backtracking, branch and bound
• Advanced Data Structures (3 sessions)
  • Amortized analysis
  • Balanced BSTs: Red-Black trees, AVL trees
  • Disjoint sets
  • Trie trees
• Graph Algorithms (3 sessions)
  • Topological sorting, strongly connected components
  • Shortest path in graphs: Bellman-Ford algorithms
  • All-pairs shortest path: Floyd-Warshall and Johnson's algorithms
  • Minimum spanning tree: Kruskal's and Prim's algorithms
• Flow Networks (2 sessions)
  • Max flow and min cut: Ford-Fulkerson algorithm
  • Variants and applications: Bipartite matching, disjoint paths, matrix rounding
• Linear Programming (2 sessions)
  • Standard form, modeling problems with linear programming
  • Simplex algorithm for solving linear programming
• Geometric Algorithms (2 sessions)
  • Sample geometric problems, convex hull
  • Sweep line algorithm, smallest enclosing circle

• Practical exercises: 3 points
• Quizzes: 3 points
• Final exam: 14 points