Algorithm: Analysis and Theory (2018)

Lecture 1: Introduction to Algorithm

• Reading Materials

• Syllabus & Grading Policy: Syllabus-AlgorithmTheory.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 (Latex Example Source: LatexExample.tex)

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

• Algorithm Package Helper: AlgorithmPackage.pdf 

• Latex Tutorial:  LaTeXTutorial.pdf 
  

Lecture 2: Algorithm Analysis

• Reading Materials

• Algorithm Analysis: 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);  

• Lab 1: Algorithm Analysis (Due: 10:00am, 03/05/2018)

• Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf 

• LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex

• Submission Requirements:  SubmissionRequirements.pdf

• Lab01-Solution: Lab01-Solution.pdf 

• New Solution of Lab01-Q2: Excellent Works by Jonas Windmüller

Lecture 3: Divide and Conquer

• Reading Materials

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

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

Lecture 4: Sorting Network

• Reading Materials

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

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

• Microsoft Visio Tutorial

• Official Tutorial from Microsoft: A Beginner's Guide to Visio

• Another version from Tutorials Point: Microsoft Visio Tutorial.pdf

• Lab 2: Divide and Conquer (Due: 10:00, 03/12/2018)

• Lab02-DivideConquer: Lab02-DivideConquer.pdf

• LaTeX Source of Lab02: Lab02-DivideConquer.tex

• Figure Source: Fig-Transposition.pdf (You need to compile the .tex file and the .pdf figure file together)

• Code Source: Code-Range.cpp

• Additional Figure Source: Fig-RecurrenceTree.vsdx (You can modify this figure and save as a .pdf figure file to insert into your .tex file)

• Submission Requirements: SubmissionRequirements.pdf

• Lab02-Solution: Lab02-Solution.pdf

Lecture 5: Greedy Strategy

• Reading Materials

• Greedy Strategy:  Slide05-GreedyAlgorithm.pdf (Print Version:  05-GreedyAlgorithm.pdf)
  

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

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

• Lab02-GreedyStrategy: Lab03-GreedyStrategy.pdf

• LaTeX Source of Lab03: Lab03-GreedyStrategy.tex

• Code Source: Lab03-Code.zip

• Lab03-Solution: Lab03-Solution.zip

Lecture 6: Matroid

• Reading Materials

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

• Reference: 
  

  * Reference08-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.

Lecture 7: Dynamic Programming

• Reading Materials

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

• Reference: Reference09-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/26/2018)

• Lab04-DynamicProgramming: Lab04-DynamicProgramming.pdf

• LaTeX Source of Lab04: Lab04-DynamicProgramming.tex

• Lab04-Solution: Lab04-Solution.pdf

Lecture 8: Amortized Analysis

• Reading Materials

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

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

• Lab 5: Amortized Analysis  (Due: 10:00, 04/02/2018)

• Lab05-AmortizedAnalysis&LinearProgramming: Lab05-AmortizedAnalysis.pdf

• LaTeX Source of Lab05: Lab05-AmortizedAnalysis.tex 

• Figure Source of Lab05: Fig-Multistack.pdf

• Lab05-Solution: Lab05-Solution.pdf

Lecture 9: Linear Programming

• Reading Materials

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

• Slide: Slide09-SimplexAlgorithm.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 "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.  

Lecture 10: Solving Linear Programming in Practice

• CPLEX Tutorial
  

• Get CPLEX from IBM ILOG CPLEX Optimization Studio

• Get official documentation from IBM Knowledge Center

• CPLEX Tutorial: CPLEXTutorial.pdf

• Lab 6: CPLEX  (Due: 10:00, 04/16/2018)

• Lab06-CPLEX: Lab06-CPLEX.pdf

• LaTeX Source of Lab06: Lab06-CPLEX.tex

• Lab06-Solution: Lab06-Solution.pdf
  

Lecture 11: Graph Algorithms

• Reading Materials

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

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

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

• Lab 7: Graph (Due: 10:00, 04/26/2018)
  

• Lab07-Graph: Lab07-Graph.pdf

• LaTeX Source of Lab07: Lab07-Graph.tex  Fig-Graph.pdf

• Resources of Lab07:  Lab07-Stack.vsd  Data-Graph.txt  

• Lab07-Solution:  Lab07-Solution.pdf  Lab07-Solution-Code.zip
  

Lecture 12: Shortest Path

• Reading Materials

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

• References: 

* 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).

• Lab 8: Shortest Path (Due: 10:00, 05/03/2018)
  

• Lab08-ShortestPath: Lab08-ShortestPath.pdf

• LaTeX Source of Lab08: Lab08-ShortestPath.tex  Fig-example.pdf

• Lab08-Solution: Lab08-Solution.pdf

Lecture 13: Network Flow

• Reading Materials

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

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

Lecture 14: Turing Machine

• Reading Materials

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

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

• Lab 9: Turing Machine and Reduction (Due: 10:00, 05/10/2018)

• Lab09-TuringMachineAndReduction: Lab09-TuringMachineAndReduction.pdf

• LaTeX Source of Lab09: Lab09-TuringMachineAndReduction.tex  

• Figure Source of Lab09: Fig-ZigZag.pdf

• Lab09-Solution: Lab09-Solution.pdf

Lecture 15: NP Reduction

• Reading Materials

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

• Solution of Reduction Example in Class: Solution-Reducing-3_SAT-to-3D_Matching.pdf
  

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

• Lab 10: NP Reduction (Due: 10:00, 05/17/2018)

• Lab10-NPReduction: Lab10-NPReduction.pdf

• LaTeX Source of Lab10: Lab10-NPReduction.tex  

• Figure Source of Lab10: Fig.pdf

• Lab10-Solution: Lab10-Solution.pdf

Lecture 16: Approximation

• Reading Materials

• Slide: Slide17-Approximation.pdf  (Print Version: 17-Approximation.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 11: Approximation (Due: 10:00, 05/24/2018)

• Lab11-Approximation: Lab11-Approximation.pdf

• LaTeX Source of Lab11: Lab11-Approximation.tex

• Lab11-Solution: Lab11-Solution.pdf

Lecture 17: Approximation II

• Reading Materials

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

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

• Lab 12: RandomizedAlgorithm (Due: 10:00, 05/31/2018)

• Lab12-RandomizedAlgorithm: Lab12-RandomizedAlgorithm.pdf

• LaTeX Source of Lab12: Lab12-RandomizedAlgorithm.tex  

• Lab12-Solution: Lab12-Solution.pdf

Lecture 18: Randomized Algorithm

• Reading Materials

• Slide: Slide19-RandomizedAlgorithm.pdf (Print Version: 19-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.