—- data course —-

Number: 2016 Title: Design of Algorithms English Title: Design of Algorithms Level: Micromaster Field: Software Units: 3 Type: Theoretical Category: Specialized Co-requisite: – Prerequisite: Data Structures and Algorithms Image: ds.png ID: 2016 Instructor: Mohammad Ali Abam Term: Summer 2025 Schedule: Monday and Wednesday 17:30 to 19:00 Priority: 3

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.