Algorithm: Analysis and Theory (2019)

Lecture 0: Preliminary

• Reading Materials

• Syllabus & Grading Policy: Syllabus-AlgorithmComplexity.pdf

• Slide: Slide01-Prologue.pdf  (Print Version: 01-Prologue.pdf)

• Reference:
  * Reference01-Set.pdf Appendix B.1-B.3 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
  * Reference02-Proof.pdf Chapter 2.1 of "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002.

• Latex Tutorial

• Latex Example: LatexExample.pdf (Source: LatexExample.tex, Fig-GraphG1.pdf, Fig-GraphG2.pdf)

• Latex Helper: LatexHelper(ENG).pdf (Chinese Version: LatexHelper(CHI).pdf)

• Algorithm Package Helper: AlgorithmPackage.pdf

• Latex Tutorial: LaTeXTutorial.pdf

Lecture 1: Algorithm Design and Analysis

• Reading Materials 
  

• Slide: Slide02-AlgorithmAnalysis.pdf  (Print Version: 02-AlgorithmAnalysis.pdf)

• Reference:  

  * Reference03-AlgorithmAnalysis.pdf Chapter 1 in "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999.

  * Reference04-Summation.pdf  Appendix A of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition); 

Lecture 2: Amortized Analysis

• Reading Materials 
  

• Slide: Slide03-AmortizedAnalysis.pdf  (Print Version: 03-AmortizedAnalysis.pdf)

• Reference:  

  * Reference05-AmortizedAnalysis.pdf Chapter 17 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition)

• Lab 01: AlgorithmAnalysis (Due: 10:00 am, 03/07/2019)

• Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf 

• LaTeX Source of Lab01: Lab01-AlgorihtmAnalysis.tex 

• Lab01-Solution: Lab01-Solution.pdf

Lecture 3: Divide and Conquer

• Reading Materials

• Slide: Slide04-DivideConquer.pdf (Print Version: 04-DivideConquer.pdf)

• Reference: Reference06-DivideConquer.pdf Chapter 2 of "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

Lecture 4: Sorting Network

• Reading Materials

• Slide: Slide05-SortingNetwork.pdf (Print Version: 05-SortingNetwork.pdf)

• Reference: Reference07-SortingNetwork.pdf Chapter 27 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2002. (2nd Edition).

• Tkinter Tutorial

• Official Documentation: Tkinter - Python interface to Tcl/Tk

• Tkinter Tutorial: TkinterTutorial.pdf

• Sorting Network: Code-SortingNetwork.py

• Lab 2: Divide and Conquer (Due: 10:00 am, 03/14/2019)

• Lab02-DivideConquer: Lab02-DivideConquer.pdf

• LaTeX Source of Lab02: Lab02-DivideConquer.tex

• Figure Source: Fig-Transposition.pdf

• Code Source: Code-Pairs.cpp

• Submission Requirements: SubmissionRequirements.pdf

• Lab02-Solution: Lab02-Solution.pdf

Lecture 5: Greedy Strategy

• Reading Materials 

• Slide: Slide06-GreedyAlgorithm.pdf (Print Version: 06-GreedyAlgorithm.pdf)

• Reference: Reference08-GreedyAlgorithm.pdf Chapter 4.1-4.3 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.  

• Movie: Wall Street (1987)

Lecture 6: Matroid

• Reading Materials 

• Slide: Slide07-Matroid.pdf (Print Version: 07-Matroid.pdf) 

• Reference: 
  * Reference09-Matroid.pdf Chapter 16.4 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition); 
  * Chapter 2.1-2.2 in "Design and Analysis of Approximation Algorithms" by D.-Z. Du, K.-I. Ko, and X. D. Hu, Springer, 2012.

• Lab 3: Greedy Strategy (Due: 10:00, 03/21/2018)

• Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf

• LaTeX Source of Lab03: Lab03-GreedyStrategy.tex

• Figure Source of Lab03: Fig-Lab03.pdf

• Lab03-Solution: Lab03-Solution.pdf 

Lecture 7: Dynamic Programming

• Reading Materials 

• Slide: Slide08-DynamicProgramming.pdf (Print Version: 08-DynamicProgramming.pdf)

• Reference: Reference10-DynamicProgramming.pdf Chapter 6.1-6.7 in "Algorithm Design " by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.

• Lab 4: Dynamic Programming (Due: 10:00, 03/28/2019)

• Lab04-DynamicProgramming: Lab04-DynamicProgramming.pdf

• LaTeX Source of Lab04: Lab04-DynamicProgramming.tex

• Code Source: Code-SequenceAlignment.cpp

• Lab04-Solution: Lab04-Solution.pdf 

Lecture 8: Linear Programing

• Reading Materials

• Slide: Slide09-LinearProgramming.pdf (Print Version: 09-Linear Programming.pdf)

• Reference:  

  * Reference11-LinearProgramming.pdf Chapter 29.1 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);

  * Chapter 7.4 in "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

  * Reference12-SimplexAlgorithm.pdf Chapter 29.3 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

• CPLEX Tutorial
  

• Get CPLEX from IBM ILOG CPLEX Optimization Studio

• Get official documentation from IBM Knowledge Center

• CPLEX Tutorial: CPLEXTutorial.pdf

• Lab 5: Linear Programming (Due: 24:00, 04/01/2019)

• Lab05-LinearProgramming: Lab05-LinearProgramming.pdf

• LaTeX Source of Lab05: Lab05-LinearProgramming.tex

• Lab05-Solution: Lab05-Solution.pdf 

Lecture 9: Graph Exploration

• Reading Materials

• Slide: Slide10-GraphAlgorithm.pdf (Print Version: 10-GraphAlgorithm.pdf)

• Slide: Slide11-BFSDFS.pdf (Print Version: 11-BFSDFS.pdf)

• Learn Borüvka Algorithm from Wikipedia

• Reference: Reference13-GraphDecomposition.pdf Chapter 3, 4 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

• Gephi Tutorial

• Get Gephi from official website

• Gephi Tutorial: GephiTutorial.pdf

• Lab 6: Graph Exploration (Due: 10:00, 04/18/2019)

• Lab06-GraphExploration: Lab06-GraphExploration.pdf

• LaTeX Source of Lab06: Lab06-GraphExploration.tex

• Code Source: Code-SCC.cpp

• Graph Information: scc.in
  

• Lab06-Solution: Lab06-Solution.pdf

Lecture 10: Shortest Path

• Reading Materials

• Slide: Slide12-ShortestPath.pdf (Print Version: 12-ShortestPath.pdf)

• Reference:  

  * Reference14-ShortestPath.pdf Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);

  * Reference15-ShortestPathDP.pdf Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005;

  * Reference16-AllPairShortestPath.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lecture 11: Network Flow

• Reading Materials

• Slide: Slide13-NetworkFlow.pdf  (Print Version: 13-NetworkFlow.pdf)

• Reference:  Reference17-NetworkFlow.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).  

• Lab07-NetworkFlow: (Due: 10:00, 04/25/2019)

• Lab07-NetworkFlow: Lab07-NetworkFlow.pdf

• LaTeX Source of Lab07: Lab07-NetworkFlow.tex

• Lab07-Solution: Lab07-Solution.pdf

Lecture 12: Turing Machine

• Reading Materials

• Slide: Slide14-TuringMachine.pdf  (Print Version: 14-TuringMachine.pdf)

• Reference: Reference18-TuringMachine.pdf  Chapter 1 in "Computational Complexity: A Modern Approach", by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006 

Lecture 13: NP and Reduction

• Reading Materials

• Slide: Slide15-NPReduction.pdf  (Print Version: 15-NPReduction.pdf) 

• Reference: Reference19-NPReduction.pdf  Chapter 8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005

• Music: The Longest Path (1988)

• Lab 8: Turing Machine and Reduction (Due: 10:00, 05/09/2019)

• Lab08-TuringMachineAndReduction: Lab08-Computational Complexity.pdf

• LaTeX Source of Lab08: Lab08-Computational Complexity.tex

• Lab07-Solution: Lab08-Solution.pdf

Lecture 14: Approximation Algorithm I

• Reading Materials

• Slide: Slide16-ApproximationI.pdf (Print Version: 16-ApproximationI.pdf)

• Reference: Reference20-Approximation.pdf Chapter 1.1, 2.1, 2.3 in "Design of Approximation Algorithms " by D. Williamson, and D. Shomoys, Cambridge University Press, 2010.

• Lab 9: Approximation Algorithm (Due: 10:00, 05/16/2019)

• Lab09-ApproximationAlgorithm: Lab09-ApproximationAlgorithm.pdf

• LaTeX Source of Lab09: Lab09-ApproximationAlgorithm.tex

• Lab09-Solution: Lab09-Solution.pdf

Lecture 15: Approximation Algorithm II

• Reading Materials

• Slide: Slide17-ApproximationII.pdf (Print Version: 17-ApproximationII.pdf)

• Reference: Reference21-ApproximationII.pdf Chapter 14 in "Approximation Algorithms" by V.Vazirani, Springer-Verlag, 2001.

Lecture 16: Randomized Algorithm

• Reading Materials

• Slide: Slide18-RandomizedAlgorithm.pdf (Print Version: 18-RandomizedAlgorithm.pdf)

• References: 

* Lecture 19 of CS 38: Introduction to Algorithms  by Chris Umans, California Institute of Technology;

* CPSC 536N: Randomized Algorithms by Nicholas Harvey, University of British Columbia;

* CSE525: Randomized Algorithms and Probabilistic Analysis by James R. Lee, University of Washington.

• Lab 10: Approximation & RandomizedAlgorithm (Due: 10:00, 05/23/2019)

• Lab10-Approximation&RandomizedAlgorithm: Lab10-Approximation&RandomizedAlgorithm.pdf

• LaTeX Source of Lab10: Lab10-Approximation&RandomizedAlgorithm.tex

• Lab10-Solution: Lab10-Solution.pdf

Lecture 17: Online Algorithm

• Reading Materials

• Slide: Slide19-OnlineAlgorithm.pdf (Print Version: 19-OnlineAlgorithm.pdf)

• References: CS369: Topics in Analysis of Algorithms by Serge Plotkin, Stanford University.