CS 330 Advanced Algorithms

Homeworks

• CS330 HW03

• CS330 HW04

• CS330 HW05

• CS330 HW07

• CS330 HW08

• CS330 HW10

• Asymptotic Analysis

  • Recurrence Relation

• Divide and Conquer

  • Peak Element
  • Undominated Points
  • Quick Sort
    • Tournament Tree
  • Merge Sort

• Parallel Algorithms

  • Parallel Sum
  • Matrix Multiplication
    • Parallel Inner Product
  • Parallel Merge Sort

• Dynamic Programming

  • Fibonacci Sequence
  • Longest Common Sequence
  • Knapsack Problem
  • Matrix Chain Multiplication: increasing in gaps

• Depth First Search

  • Reachability and Connectivity
  • Directed Graph
    • Preand Post-time
    • Strongly Connected Component algorithm (Kosaraju’s)
    • Cycle detection → DAG
    • Topological Sort of DAG

• Shortest Path

  • Single Source Shortest Path
    • BFS Shortest Path (vertex creation, alarm clock method)
    • Dijkstra’s
    • A*
    • Bellman-Ford
  • All-Source Shortest Path: Floyd-Warshall

• Greedy Algorithm

  • Scheduling Problem
  • Huffman Text Compression Algorithm
  • Minimal Spanning Tree Problem
  • Ackerman Function

• Maximum Flow Problem (=Min-cut, Edge matching)

  • Min Cut
  • Edge Matching

• Computational Tractability

  • Polynomial Reduction
  • Boolean Decision Problem
    • Cooke-Levin Theorem
    • CNF-SAT ${\le }_p$ 3-SAT
    • Vertex Cover ${\le }_p$ Subset Sum
    • Subset Sum ${\le }_p$ Knapsack Problem
  • Common Graph Problems
    • Independent Set
    • Clique
    • Vertex Cover
    • Triangle Cover
  • Linear Programming

• Approximation Algorithms

  • Load Balancing
  • Set Cover
  • Traveling Salesperson Problem
    • Christofides Approximation (1.5-level)
  • K-Clustering Problem
    • K-Max: Maximum distance to closest center
    • K-Means: Mean per center
      • Llyod’s Approximation (2-level)
      • K-Means++ Approximation (<2-level)

• Hashing Algorithms

  • Uniformity
  • Universality
  • Linear Congruence Hashing
  • Multiply Shift Binary Hashing