Algorithm Design and Analysis, IUB CSCI B503

Description

• Covering
  • fundamental techniques in designing algorithms
  • bounds on time and space complexity
• Prerequisite
  • mathematical background
    • elementary combinatorics
    • discrete probability
    • basic linear algebra and calculus
  • elementary algorithms
    • basic data structures
    • basic sorting and searching
    • elementary graph terminology
    • asymptotic analysis of time and space complexity
      • big-O/Omega/Theta notation

Textbook

KT: Algorithm Design, J.Kleinberg, E.Tardos, 2005

Syllabus and Readings

• Basics of Algorithm Analysis
  • The Stable Matching Problem - KT 1.1
  • One-Side Optimality of Gale-Shapley and the Parity of Intervals Problem
• Greedy Algorithms
  • Interval Scheduling Problem - KT 4.1
  • Scheduling All Intervals and Minimum Spanning Trees - KT 4.1, 4.5
  • Kruskal's Algorithm and the Reverse-Delete Algorithm - KT 4.5
  • Implementing Kruskal's Algorithm with the Union-Find Data Structure - KT 4.6
  • Prim's Algorithm and Boruvka's Algorithm - KT 4.5, Wikipedia Page on Boruvka's Algorithm
  • The Single Source Shortest Path Problem and Dijkstra's Algorithm - KT 4.4
• Divide and Conquer
  • Merge Sort and Solving Recurrences - KT 5.1 & 5.2
  • Counting Inversions and Peak Finding - KT 5.3
  • Integer Multiplication - KT 5.5
  • Closest Pair of Points - KT 5.4
  • Convolution and Fast Fourier Transform - KT 5.6
• Dynamic Programming
  • Introduction to Dynamic Programming - KT 6.1 & 6.2
  • Segmented Least Squares - KT 6.3
  • The Knapsack Problem - KT 6.4
  • RNA Secondary Structure - KT 6.5
  • Sequence Alignment - KT 6.6
  • Linear Space Algorithm for Sequence Alignment and Bellman-Ford Algorithm - KT 6.7, 6.8 & 6.10
  • All-Pair Shortest Path Problem and Floyd-Warshall Algorithm, Wikipedia page on
    Floyd-Warshall Algorithm
• Network Flow
  • The Maximum Flow Problem and Ford-Fulkerson Algorithm - KT 7.1
  • The Maximum Flow Minimum Cut Theorem - KT 7.2
  • Capacity-Scaling Algorithm and the Maximum Matching Problem - KT 7.3
  • Hall's Theorem and the Image Segmentation Problem - KT 7.5 & 7.10
  • Baseball Elimination - KT 7.12
  • Project Selection - KT 7.11

Knowledge Frame

• https://mubu.com/edit/38LqMoseUF