Course Outline


No.Study DetailAssignment
 1. 
<13 Aug 13>
  • Course Explanation
  • Introduction algorithm 
 2.
<20 Aug 13>
  • Fibonacci
  • Big-O Notation 
  • Algorithm with Number
    • Basic arithmetic
    • Modular arithmetic 
    • Primality Testing
    • Cryptography
    • Universal hashing
 3.
<27 Aug 13>
Randomized algorithms
  •  Divide-and-conquer algorithms
    • Multiplication 
    • Recurrence relations
    • Merge sort
    • Medians
    • Matrix multiplication
    • The fast Fourier transform
 
 4.
<3 Sep 13>
 Randomized algorithms
  • Greedy algorithms
    • Minimum sapnning trees
    • Huffman encoding
    • Horn formalas
    • set cover
 
 5.
<10 Sep 13>
 Randomized algorithms
  • Dynamics programming (1)
    • Shortest paths in dags, revisited
    • Longest increasing subsequences
    • Edit distance
 
 6.
<17 Sep 13>
 Randomized algorithms
  • Dynamics programming (2)
    • Knapsack
    • Chain matrix multiplication
    • Shortest paths
    • Independent sets in trees
 
 7.
<24 Sep 13>
  • Review  and Presentation
 
 8.
<4 Oct 13>
  • Self Study
  • Examination 
 
 9.
<15 Oct 13>
 Randomized algorithms
  • Linear programming and reductions (1)
    • An introduction to linear programming
    • Flows in networks
    • Bipartite matching
    • Duality
 
 10.
<22 Oct 13>
  Randomized algorithms
  • Linear programming and reductions (2)
    • Zero-sum games
    • The simplex algorithm
    • Postscript: circuit evaluation 
 
 11.
<29 Oct 13>
  Randomized algorithms
  • NP-complete problems
    • Search problem
    • NP-complete problems
    • The reductions 
 
 12.
<5 Nov 13>
  Randomized algorithms
  • Decomposition of graphs
    • Why graphs?
    • Depth-first search in un-directed graphs
    • Depth-first search in directed graphs
    • Strongly connected components
 
 13.
<12 Nov 13>
  Randomized algorithms
  • Paths in graphs (1)
    • Distances
    • Breadth-first search
    • Lengths on edges
    • Dijkstra's algorithm
 
 14.
<19 Nov 13>
  Randomized algorithms 
  • Paths in graphs (2)
    • Priority queue implementations
    • Shortest paths in the presence of negative edges
    • Shortest paths in dags
 
 15
<26 Nov 13>
  • Review  and Presentation
 
 
 16.
<3 Dec 13>
 
  • Self Study
  • Examination