Algorithm Design and Analysis (2021)

Lecture 0: Preliminary

• Reading Materials

• Syllabus & Grading Policy: Syllabus-AlgorithmTheory.pdf

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

• Slide for Symbols: Slide02-Symbols.pdf  (Print Version: 02-Symbols.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 Tutorial: LaTeXTutorial.pdf 

• Latex Example: LatexExample.pdf (Latex Example Source: LatexExample.tex, Fig-Graph1.pdf, Fig-Graph2.pdf)

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

• AlgorithmSample: AlgorithmSample.pdf (Source: AlgorithmSample.tex)

• Algorithm Package Helper: AlgorithmPackage.pdf 

• VariableSample: VariableSample.pdf (Source: VariableSample.tex)

• Lab 0: Self-Introduction (Due:  23:59pm, 09/22/2021)

• Self-Introduction: Lab0-SelfIntroduction.pdf （自我介绍中英文皆可）

• Background Survey: https://www.wjx.cn/vj/Q1dER1T.aspx

Lecture 1: Algorithm Analysis

• Reading Materials 
  

• Slide: Slide03-AlgorithmAnalysis.pdf  (Print Version: 03-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);        

• Profile of Alonzo Church AlonzoChurch.pdf  The profile is from https://mathshistory.st-andrews.ac.uk/Biographies/Church/.  

• Analysis on Harmonic Number Analysis on Harmonic Number.pdf

• Lab 1: Algorithm Analysis (Due: 10:00 am, 09/29/2021)

• Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf

• LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex

• Lab01-Solution: Lab01-Solution.pdf

• Best Labs: BestLab-ZiyuWang.pdf, BestLab-ZhenlinQi.pdf, BestLab-XihuaiWang.pdf

• Poster and In-Class Quiz

• • 

    Poster

  • 

    Quiz1_1

  • 

    Quiz1-2

Lecture 2: Divide and Conquer

• Reading Materials

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

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

  * Reference06-MasterTheorem.pdf Chapter 4.4-4.6 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).              

• Poster and In-Class Note

• • 

    Poster

  • 

    Deduction of Master's Theorem

Lecture 3: Greedy Algorithm

• Reading Materials

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

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

• Movie: Wall Street.mp4

• Lab 2: Greedy strategy (Due:  10:00 am, 10/13/2021)

• Lab02-AlgorithmDesign: Lab02-AlgorithmDesign.pdf

• LaTeX Source of Lab02: Lab02-AlgorithmDesign.tex

• Lab02-Solution: Lab02-Solution.pdf

• Lab02-SummaryReport: Lab02-SummaryReport.pdf

• Best Labs: BestLab-MingjieLi.pdf, BestLab-MingquanFeng.pdf, BestLab-PeiyanDeng.pdf

• Poster and In-Class Quiz

• • 

    Poster

  • 

    Quiz2-1

  • 

    Answer for Quiz2-1

Lecture 4: Dynamic Programming

• Reading Materials

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

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

• Lab 3: Dynamic Programming (Due: 10:00 am, 10/22/2021)

• Lab03-DynamicProgramming: Lab03-DynamicProgramming.pdf

• LaTeX source of Lab03: Lab03-DynamicProgramming.tex

• Code source of Lab03: Code-Array.cpp

• Lab03-Solution: Lab03-Solution.zip

• Lab03-SummaryReport: Lab03-SummaryReport.pdf

• Best Labs: Lab03-KangpingYi.zip, Lab03-YanZhao.zip, Lab03-ZhantaoYang.zip, Lab03-ZiruiWang.zip

• Poster and In-Class Quiz

• • 

    Poster

  • 

    Quiz2-2

  • 

    Answer for Quiz2-2

Lecture 5: Graph Algorithm

• Reading Materials

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

  Slide08-ShortestPath.pdf (Print Version: 08-ShortestPath.pdf)

  Slide09-NetworkFlow.pdf (Print Version: 09-Network Flow.pdf)

• Demo: Slide10-GraphAlgorithmDemo.pdf
  

• Reference: 

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

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

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

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

  * Reference13-Heaps.pdf, Reference14-FibonacciHeaps.pdf Slides for Heap in Data Structure Class from Kevin Wayne @ Princeton;

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

• Lab 4: Graph Algorithm (Due: 10:00 am, 11/5/2021)

• Lab04-GraphAlgorithm: Lab04-GraphAlgorithm.pdf

• LaTeX source of Lab04: Lab04-GraphAlgorithm.tex

• Figure for Lab04: Fig-FlowNetwork.eps

• Code source of Lab04: Code-Dijkstra.cpp

• Lab04-Solution: Lab04-Solution.zip

• Lab04-SummaryReport: Lab04-SummaryReport.pdf

• Best Labs: Lab04-DuanJiaang.zip, Lab04-DuYuheng.zip, Lab04-WangXinzhou.zip

• Poster and In-Class Quiz

• • 

    Poster

  • 

    Quiz3-1

  • 

    Quiz3-2

Lecture 6: Approximation Algorithm

• Reading Materials

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

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

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

* Reference17-ApproximationII.pdf Chapter 14 in "Approximation Algorithms" by V.Vazirani, Springer-Verlag, 2001.

Final Exam

• Final Exam Information

• Time: Nov. 19, 2021 (Friday) 10:00 am-12:00 am

• Location: ExamOrganization.xlsx

• Question types: Problems may include Multiple Choices, True or False, Questions and Answers.

• Notice: English only, close note, close book, individual test

• Exam Survey:

• Please vote for your favorite final exam date in WeChat group (before 14:00, 11/03/2021), otherwise we consider that you accept any of the four selections for final exam.

• Majority (95%) of the class voted for 11/19/2021.

• Photo

• • 

    班级合影