CS711008Z: Algorithm Design and Analysis -- Fall 2011

Course Information

• Staff
  Instructor:
  Dongbo Bu
  Email: dbu AT ict.ac.cn
  Location: 1012I, ICT Building,
  Tel: 62601019
  
  
  TAs:
  Chao Wang , Haicang Zhang , Chunlin Huang, Jin Li , Qin Huang , Lei Nie
  Email: TA of alGorithm Courses
  Location: 1012H, ICT Building,
  Tel: 62601019
  Office Hours: 2:00pm-6:00pm, Wednesday



• Textbooks (recommended, not required):
  * T.H. Cormen, C.E. Leiserson, R. Rivest, and C. Stein, Algorithms (2nd ed.), MIT Press, 2001. Widely available.
  * J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.
  * R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge U. Press, 1995
  * Christos H. Papadimitriou, Kenneth Steiglitz, Kenneth Steiglitz. Combinatorial Optimization: Algorithms And Complexity. Courier Dover Publications, 1998
  
  Other reading material:
  * M. Mitzenmacher and E. Upfal, Probability and Computer. Cambridge U. Press, 2005.
  * V. Vazirani, Approximation Algorithms. Springer Verlag, 2001.
  * M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.
  


• Goals:
  * to master the ability to extract mathematically clean core of a problem,
  * then identify approximate algorithm design technique based on the problem structure observations,
  * and analyze algorithm performance.
  


• Prerequisites:
  We will assume knowledge of:
  * basic data structures such as lists, trees, heaps, sorting and searching
  * basic discrete mathematics such as proofs by mathematical induction;
  * computability and programming experience;
  


• Topics:
  We will cover the following topics if time permits.
  * Problem hardness, NP-completeness;
  * Algorithm analysis techniques, including worst-case and average-case, amortized, randomization, and competitive;
  * Basic algorithm techniques, including greedy, iteration, divide-and-conquer, dynamic programming, network flow, linear programming;
  * Algorithm techniques for hard problems, including approximation algorithms, local search, primal-dual algorithms, linear programming;
  * Randomized algorithms: basic techniques from discrete probability, and applications to optimization.
  * Specific problems from computational biology and Bioinformatics (if time permits).
  

Grading policies

Weekly Schedule

• Week 1: Introduction to algorithm
  • Lecture 1: Introduction to algorithm: some representative problems;
    Lec1.pdf ; Lec1-regular-expression-problem ; Lec1 demo of GS algo (by K. Wayne)
  • Lecture 2: Basic algorithm analysis techniques, worst-case, average-case, and amortized analysis;
    Lec2.pdf ; Lec2 TableInsert (by C. Leiserson)
    Reading material: Chapter 1 of Algorithm design, Chapter 17 of Introduction to Algorithms
    
  • Assignment 1
• Week 2 : Problem hardness
  • Lecture 3: Problem hardness: Polynomial-time reduction;
    Lec3.pdf
• Week 3: NP-Completeness
  • Lecture 4: NP-Hard problems: packing problem, covering problems, sequencing problem, partitioning, coloring, SAT, numbering problems, etc.
    Lec4.pdf , Turing machine demo (by Zhen Ji) . Turing machine demo (by Andrew Hodges, 2SAT is in P (by D. Moshko )
  Reading material: Computer and intractability, Chapter 8 of Algorithm design, Chapter 34 of Introduction to Algorithms
  Useful material: A compendium of NP optimization problems (Edited by Pierluigi Crescenzi, Viggo Kann, M. Halldorsson, M. Karpinski, and G. Woeinger )
  
  • Assignment 2
• Week 4: Basic Algorithm Techniques;
  • Lecture 5: Divide-and-conquer technique, and the combination with randomization;
    Lec5.pdf ; demo merge (by K. Wayne) ; demo merge inversion (by K. Wayne)
    
  Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design, Duality applied to the complexity of matrix multiplications and other bilinear forms (by J. Hopcroft, and J. Musinski, 1973) , The Coppersmith-Winograd matrix multiplication algorithm (by M. Anderson and S. Barman, 2009)
  
  • Assignment 3
• Week 4: More on basic algorithm techniques;
  • Lecture 6: Dynamic programming technique;
    Lec6.pdf ; RNA secondary structure prediction (by Sarah Aerni) ; Edit distance (by Andrew McCallum) ; PAM matrix for BLAST algorithm (by C. Alexander, 2002)
    
  Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design
  Useful material: A linear space algorithm for computing maximal common subsequences (by D. S. Hirschberg) ; P-value calculation (by J. Zhang )
  
  • Assignment 4
• Week 5: More on basic algorithm techniques;
  • Lecture 7: Greedy technique
    Lec7.pdf ; demo of Dijkstra's algorithm (by K. Wayne) ; demo of Interval Scheduling algorithm (by K. Wayne)
    Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design
    
  • Assignment 5
  • Lecture 8: Linear programming: Simplex algorithm
    Lec8.pdf , Klee-Minty example (by H. Greenberg) , Simplex examples , Smoothed complexity (by D. Spielman and S. Teng) , GLPK (GNU Linear Programming Kit
    Reading material: Chapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity.
• Week 5: Linear programming and network flow;
  • Lecture 9: Linear programming: duality;
    Lec9.pdf , Lec9-DIET.math , Lec9-DIET-Dual.math , Lec9-DIET-b1-2001.math , Lec9-DIET-b2-56.math , Lec9-DIET-b3-801.math
    Reading material: Chapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity.
  • Assignment 6
  • Lecture 10: Network flow and its applications;
    Lec10.pdf , Network-flow applications , Network-flow research history (by A. Schrijver) , demo of Ford-Fulkerson algorithm
    Reading material: Chapter 26 of Introduction to Algorithms, Chapter 7 of Algorithm design, Combinatorial optimization: algorithm and complexity.
  • Assignment 7
• Week 6: Solving hard problems: approximation and randomization
  • Lecture 11: Approximation algorithm: a brief introduction;
    Lec11.pdf , Parametric pruning algorithm for K-Center problem (by P. Potikas)
    Reading material: Chapter 35 of Introduction to Algorithms, Chapter 11 of Algorithm design, Approximation algorithm by V. Vazirani.
  • Assignment 8
  • Lecture 12: Randomized algorithm: a brief introduction;
    Lec12.pdf , Hashing (by K. Wayne)
    Reading material: Chapter 35 of Introduction to Algorithms, Chapter 13 of Algorithm design, Randomized Algorithm by R. Motwani and P. Raghavan.
  • Assignment 9 (not available)
• Week 7: Solving hard problems: special cases and heuristics
  • Lecture 13: Extending limits of tractability;
    Lec13.pdf
    Reading material: Chapter 10 of Algorithm design, and lectures by D. P. Williamson.
  • Lecture 14: Heuristics (local search strategy);
    Lec14 Local Search (by K. Wayne)
    Reading material: Chapter 11 of Algorithm design, and Combinatorial optimization: algorithm and complexity.
  • Assignment 10 (not available)
• Week 8: String matching problem, Selection problem, and Paging problem.
  • Lecture 15: Selection problem: linear deterministic algorithm, randomized divide-and-conquer algo, and random sampling;
    Lec15.pdf , Two papers on the selection problem (by BFPRT, and FR)
    
  • Lecture 16: Cache paging problem: FF, LRU, and randomized algo;
    Lec16.pdf
    
  • Lecture 17: String matching problem: DFA, KMP method, randomized finger-print, and Karp-Rabin algo;
    Lec17.pdf
    
• Week 9: Closest string and substring problem, Bi-clustering problem, Randomization algorithms
  • Lecture 18: Closest string and substring problems: random rounding and random sampling;
    Lec18.pdf
    
  • Lecture 19: Bi-Clustering problem: random rounding, a new random sampling idea;
    Lec19.pdf
    
• Week 10: MaxCut problem
  • Lecture 20: MaxCut problem: Hardness, Local search algorithm, randomization algorithm, derandomization, and SDP approach;
    Lec20.pdf

Powered by Loongson CPU . Loongson is a CPU developed at Institute of Computing Technology, Chinese Academy of Sciences.