Algorithm and Complexity (2018)

Lecture 1: Introduction to Algorithm

• Reading Materials

• Syllabus & Grading Policy: Syllabus-AlgorithmComplexity.pdf
  

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

• References: 

* 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 Tutorials

• Latex Example: LatexExample.pdf (Latex Example Source: LatexExample.tex)

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

• Algorithm Package Helper: AlgorithmPackage.pdf 

• Latex Tutorial: LaTeXTutorial.pdf 

• Lab 0: Preliminary

• Complete self-introduction

• Try to compile LatexExample.tex

• Learn Pseudo Code from Wikipage

Lecture 2: Algorithm Analysis

• Reading Materials

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

• Additional Remarks on Average Case Analysis: Slide02-AverageCaseAnalysis.pdf

• Reference: Reference03-AlgorithmAnalysis.pdf Chapter 1 of "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999.

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

• Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf (Lab01-AdditionalNotes: Lab01-AdditionalNotes.pdf)

• LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex

• Submission Requirements : SubmissionRequirements.pdf

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

• Lab01-Solution: Lab01-Solution.pdf (Discussion of Lab01-Q2-Best Case Complexity: DiscussionOfLab01-Q2-BestCase.pdf)

• Best Labs: Lab01-ChachaChen.pdf, Lab01-KaiwenZha.pdf, Lab01-SichengZuo.pdf.

Lecture 3: Divide and Conquer

• Reading Materials

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

• Reference: Reference05-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: Slide04-SortingNetwork.pdf (Print Version: 04-SortingNetwork.pdf)

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

• Microsoft Visio Tutorials

• 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: 16: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.tex

• Best Labs: Lab02-HongyiGuo.pdf, Lab02-JianhuaSun.pdf, Lab02-SichengZuo.pdf.

Lecture 5: Greedy Strategy

• Reading Materials 

• Slide: 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.  

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.

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

• Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf

• LaTeX Source of Lab03: Lab03-GreedyStrategy.tex

• Code Source: Code-SetCover.cpp

• Lab03-Solution: Lab03-Solution.pdf

• Best Labs: Lab03-YifanZhang.pdf, Lab03-AoyangYan.pdf, Lab03-HaoqiZhang.pdf.

Lecture 7: Dynamic Programming

• Reading Materials

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

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

• Lab 4: Dynamic Programming (Due: 16:00, 03/26/2018)

• Lab04-DynamicProgramming: Lab04-DynamicProgramming.pdf

• LaTeX Source of Lab04: Lab04-DynamicProgramming.tex

• Code Source: Code-Targets.cpp

• Lab04-Solution: Lab04-Solution.pdf

• Best Labs: Lab04-YifanZhang.pdf, Lab04-KaiwenZha.pdf, Lab04-YanjunFu.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).

Lecture 9: Linear Programming

• Reading Materials

• Slide: Slide09-LinearProgramming.pdf (Print Version: 09-LinearProgramming.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.

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

• Lab05-Amortized Analysis: Lab05-AmortizedAnalysis.pdf

• LaTeX Source of Lab05: Lab05-AmortizedAnalysis.tex

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

• Lab05-AdditionalNotes: Lab05-AdditionalNotes.pdf

• Lab05-Solution: Lab05-Solution.pdf

• Best Labs: Lab05-HanXue.pdf, Lab05-JiakunYan.pdf, Lab05-XuehanSun.pdf.
  

Lecture 10: Simplex Algorithm

• Reading Materials

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

• Reference: 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).
  

Lecture 11: 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: 16:00, 04/16/2018)

• Lab06-CPLEX: Lab06-CPLEX.pdf

• LaTeX Source of Lab06: Lab06-CPLEX.tex

• Lab06-Solution: Lab06-Solution.pdf

• Best Labs: Lab06-ZhengGong.pdf, Lab06-SiyuanZhou.pdf, Lab06-ChachaChen.pdf.

Lecture 12: Graph Exploration

• 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 Exploration (Due: 16:00, 04/26/2018)
  

• Lab07-GraphExploration: Lab07-GraphExploration.pdf

• LaTeX Source of Lab07: Lab07-GraphExploration.tex

• Data Source of Lab07: Data-CCC.txt

• Lab07-Solution: Lab07-Solution.pdf, Lab07-3-Solution.zip

• Best Labs: Lab07-JinbiaoYe.pdf, Lab07-HongjianCao.pdf, Lab07-HanXue.pdf

• Best Visualization:

• • 

    Ge Huang (d3)

  • 

    Han Xue (Gephi)

  • 

    Jianhua Sun (Gephi)

• • 

    Jinbiao Ye (js)

  • 

    Shuodian Yu (Gephi)

  • 

    Sicheng Zuo (Gephi)

Lecture 13: 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: 16:00, 05/03/2018)

• Lab08-ShortestPath: Lab08-ShortestPath.pdf

• LaTeX Source of Lab08: Lab08-ShortestPath.tex

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

• Lab08-Solution: Lab08-Solution.pdf

• Best Labs: Lab08-AoyangYan.pdf, Lab08-SichengZuo.pdf, Lab08-HongxiangYu.pdf.

Lecture 14: Network Flow

• Reading Materials

• Slide: Slide14-NetworkFlow.pdf  (Print Version: 14-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). 

Lecture 15: 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: 16:00, 05/10/2018)

• Lab09-TuringMachineAndReduction: Lab09-TuringMachineAndReduction.pdf

• LaTeX Source of Lab09: Lab09-TuringMachineAndReduction.tex

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

• Lab09-Solution: Lab09-Solution.pdf

• Best Labs: Lab09-KaiwenZha.pdf, Lab09-XuehanSun.pdf, Lab09-ChengeSun.pdf

Lecture 16: NP and Reduction

• Reading Materials

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

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

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

• Lab10-NPReduction: Lab10-NPReduction.pdf

• LaTeX Source of Lab10: Lab10-NPReduction.tex

• Lab10-Solution: Lab10-Solution.pdf

• Best Labs: Lab10-YifengGao.pdf, Lab10-YongqingXu.pdf, Lab10-WenhaoLi.pdf.

Lecture 17: Approximation Algorithm I

• Reading Materials

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

• Lab11-ApproximationAlgorithm: Lab11-ApproximationAlgorithm.pdf

• LaTeX Source of Lab11: Lab11-ApproximationAlgorithm.tex

• Lab11-Solution: Lab11-Solution.pdf

• Best Labs: Lab11-YanjunFu.pdf, Lab11-RuofanLiang.pdf, Lab11-ChenxuZhu.pdf.

Lecture 18: Approximation Algorithm II

• Reading Materials

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

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

• Lab 12: Approximation Algorithm II (Due: 16:00, 06/01/2018)

• Lab12-ApproximationAlgorithmII: Lab12-ApproximationAlgorithmII.pdf

• LaTeX Source of Lab12: Lab12-ApproximationAlgorithmII.tex

• Lab12-Solution: Lab12-Solution.pdf

• Best Labs: Lab12-JisenChen.pdf, Lab12-RenjieWu.pdf, Lab12-HongjianCao.pdf.