Design of Algorithms

Instructor: Mohammad Ali Abam Certificate: Official (bilingual)
Term: Summer 2025 Prerequisite: Data Structures and Algorithms
Schedule: Monday and Wednesday 17:30 to 19:00 Online Class: Online Class

General Objective

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.

Topics

  • 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

Assessment

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

References

  1. T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
  2. J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
  3. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
  4. G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.