Data Structures and Algorithms (2019)

Lecture 1: Data Structures and Algorithms

• Reading Materials

• Syllabus & Grading Policy: Syllabus-DataStructures.pdf  

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

• Reference:
  * Reference01-Introduction.pdf Chapter 1 of "Data Structures and Algorithm Analysis" by Clifford A Shaffer, Dover Publications, 2012;  
  * Reference02-Preliminary.pdf Chapter 2 of "Data Structures and Algorithm Analysis" by Clifford A Shaffer, Dover Publications, 2012.  

• Latex Tutorial

• Latex Example:   LatexExample.pdf

• Latex Example Source: LatexExample.tex
  

• Figure Source:   Fig-GraphG1.pdf,  Fig-GraphG2.pdf

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

• Algorithm Package Helper:   AlgorithmPackage.pdf 

• Latex Tutorial:  LaTeXTutorial.pdf 

• Lab 0: Self-Introduction (Due: 16:00pm, 09/18/2019)

• Lab00-SelfIntroduction: Lab00-SelfIntroduction.pdf

• Lab 1: Preliminary (Due: 16:00pm, 09/20/2019)

• Lab01-Preliminary: Lab01-Preliminary.pdf (Updated on 9/15)

• LaTeX Source of Lab01: Lab01-Preliminary.tex (Updated on 9/15)

• Reading: Introduction on C++ Vector.pdf          

• Submission Requirements:  SubmissionRequirements.pdf

• Best Lab Works Bonus Policy: BonusPolicy.pdf

• Lab01 Solution: Lab01-Solution.pdf

• Best Labs: Lab01-YaxinChen.pdf, Lab01-TingShen.pdf, Lab01-HaoLin.pdf

• In-Class Vote Results

• • 

    Slide01P27: Do You Know Data Structures?

  • 

    Slide02P6: Which Statements Are True for Linear Search? Answer: ABD

Lecture 2: Algorithm Analysis

• Reading Materials

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

• Reference:

  * Reference03-AlgorithmAnalysis.pdf -- Chapter 3 of "Data Structures and Algorithm Analysis" by Clifford A Shaffer, Dover Publications, 2012. 
  * Reference04-Complexity.pdf -- Chapter 1 of "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999.

• Recitation Class (Tuesday 18:30pm, 9/17/2019, Room: 113F, TA: Shuxiang Xie)

• Slide: RC01-Preliminary.pdf 
  

• Tutorial on Latex (How to compile your Lab source)

• Tutorial on Vector C++

• Tutorial on Mathematical Derivations

• URGENT: please vote for the remaining recitation class schedule (Due: 10:00am, 9/17/2019)
  Link: https://umjicanvas.com/courses/1271/quizzes 

• In-Class Vote Results
  

• • 

    Slide02P23: How fast would you advertise it as? Answer: B

  • 

    Slide2P36: What Is the Time Complexity of the Following Code? Answer: C

  • 

    Voting for RC & OH schedule

Lecture 3: Sorting and Searching

• Reading Materials

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

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

• Reference: 
  * Reference05-Sorting.pdf  -- Chapter 7 of "Data Structures and Algorithm Analysis" by Clifford A Shaffer, Dover Publications, 2012.

  * Reference06-SearchSortComparison.pdf -- Pseudo Codes and Analysis of 7 Searching and Sorting Algorithms (Written by TA Shuxiang Xie).    

  * Reference07-StackUsage.pdf -- Two Examples for Stack Usage: Hanoi Tower and Parentheses Matching (Written by TA Shuxiang Xie).         

• Recitation Class (Tuesday 18:30pm, 9/24/2019, Room: 113F, TA: Qingmin Liu)

• Slide: RC02-SortingAndSearching.pdf

• Tutorial on Sorting and Searching Algorithms (Searching: Linear Search, Binary Search; Sorting: Selection Sort, Bubble Sort, Insection Sort, Merge Sort, Quick Sort)
  

• Tutorial on Complexity Analysis (Multiple Examples on Best Case Analysis, Worst Case Analysis, and Average Case Analysis)

• Lab 2: Sorting and Searching (Due: 16:00pm, 09/30/2019)
  

• Lab02-Soring and Searching: Lab02-SortingAndSearching.pdf

• LaTex Source of Lab02: Lab02-SortingAndSearching.tex

• Lab02 Solution: Lab02-Solution.pdf 

• Best Labs: Lab02-KaiFeng.pdf, Lab02-XiaoxueZhong.pdf, Lab02-YichaoYuan.pdf, Lab02-YiqingFan.pdf
  

• In-Class Vote Results

• • 

    Slide03P15: Which Statements Are Correct for Selection Sort? Answer: AB

  • 

    Slide03P32: What are 𝑎, 𝑏, 𝑑 for Binary Search? Answer: B

Lecture 4: Linear Time Selection

• Reading Materials

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

• Reference:

  * Reference08-LinearTimeSelection.pdf -- Lecture 4 of "CMU 15-451 (Algorithms), Fall 2011" by Avrim Blum, Manuel Blum, 2011.              

  * Reference09-MathematicalInduction.pdf -- Chapter 2.1 of "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002.            

• Recitation Class (Tuesday 18:30pm, 10/08/2019, Room: 113F, TA: Qingmin Liu)

• Analysis on Linear-Time Selection Algorithms (Randomized Version and Determinstic Version)
  

• Tutorial on Stack (Perenthesis Matching, Hanoi Tower, More Examples)

• Tutorial on Non-Comparison Sort

• Lab 3: Sorting and Searching (Due: 16:00pm, 10/11/2019)
  

• Lab03-Soring and Selection: Lab03-SortingAndSelection.pdf

• LaTex Source of Lab03: Lab03-SortingAndSelection.tex

• Submission Guidelines: JOJInstructions.pdf 

• Best Labs: Lab03-JingzheFang.pdf, Lab03-YaxinChen.pdf, Lab03-LiyingHan.pdf
  

• In-Class Vote Results
  

• • 

    Special Moment

  • 

    Slide05P8: Which Statements Are Correct? Answer: AB

Lecture 5: Hashing

• Reading Materials

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

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

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

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

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

• Reference:                 

  * Reference10-Hashing.pdf -- Chapter 9.4 of "Data Structures and Algorithm Analysis" by Clifford A Shaffer, Dover Publications, 2012.             

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

  * Reference12-U(L) and S(L).pdf [Optional] -- Chapter 6.4 in "The Art of Computer Programming (TAOCP)", Volume 3, Donald Knuth, Addison-Wesley, 1968.            

• Recitation Class (Wednesday 20:00pm, 10/16/2019, Room: 113F, All TAs)

• Midterm Review: Algorithm Analysis, Sorting and Searching, Hashing
  

• Tutorials on Labs: from Lab01 to Lab04

• Lab 4: Hashing (Due: 16:00pm, 10/16/2019)
  

• Lab04-Hashing: Lab04-Hashing.pdf

• LaTex Source of Lab04: Lab04-Hashing.tex 

• Lab04 Solution: Lab04-Solution.pdf 

• Best Labs: Lab04-ZhengWu.pdf, Lab04-YatingLiu.pdf, Lab04-XutingYang.pdf

• In-Class Vote Results

• • 

    Slide06P13: Insight of Collision: Birthday Problem. Answer: A

  • 

    Slide07P18: Which Statements Are Correct? Answer: AC

Lecture 6: Heap

• Reading Materials 

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

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

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

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

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

• Lab 5: Priority Queues and Application (Due: 16:00pm, 11/11/2019)

• Lab05-Priority Queues and Application: Lab05-PriorityQueuesAndApplication.pdf

• Lab05-RelatedFiles: Lab05-RelatedFiles.zip

• Best Labs: Lab05-LiqinZhang.pdf, Lab05-LiShi.pdf, Lab05-ZhijieZhao.pdf

• In-Class
  

• • 

    Special Moment

  • 

    Slide11P18: Which Statements Are Correct? Answer: CD

  • 

    Slide11P22: How Would You Represent a Right-skewed Binary Tree? Answer: C

• • 

    Slide12P9: What Is the Result of In-Order Depth-First Traversal? Answer: B

  • 

    Slide13P12: What’s the Height of a Heap of n Nodes? Answer: CD

Lecture 7 : Binary Search Tree

• Reading Materials

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

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

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

• Lab 6 : Heaps and BST (Due: 16:00pm, 11/18/2019)

• Lab06-HeapsAndBST: Lab06-HeapsAndBST.pdf

• LaTex Source of Lab06: Lab06-HeapsAndBST.tex

• Lab06 Solution: Lab06-Solution.pdf

• Best Labs: Lab06-JianShi.pdf, Lab06-XinyuTong.pdf, Lab06-YuankaiZhou.pdf

• In-Class

• • 

    Special Moment

  • 

    Slide16P3: Which of the Following Trees Are BST? Answer: AB

• • 

    Slide17P2: Which Statements Are Correct? Answer: AB & C

Lecture 8 : Trees

• Reading Materials

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

• Slide: Slide20-Tries.pdf (Print Version: 20-Tries.pdf)

• Slide: Slide21-AVLTrees.pdf (Print Version: 21-AVLTrees.pdf)

• Slide: Slide22-RedBlackTrees.pdf (Print Version: 22-RedBlackTrees.pdf)

• Recitation Class (Tuesday 18:30pm, 11/12/2019, Room: 113F, TA: Qingmin Liu)

• Decrease key

• Amortised analysis on heap

• Pointer of C++

• Lab 7 : Trees (Due: 19:00pm, 11/26/2019)

• Lab07-Trees: Lab07-Trees.pdf

• LaTex Source of Lab07: Lab07-Trees.tex

• Lab07 Solution: Lab07-Solution.pdf 

• Best Labs: Lab07-ChenyunTao.pdf, Lab07-JinHUANGFU.pdf, Lab07-QiSun.pdf
  

• In-Class

• • 

    Slide21P7:Which of the Following Trees Are AVL Balanced? Answer: ABC

  • 

    Slide22P7:Which Statements Are Correct? Answer: BCD

  • 

    Slide22P17:Which Statements Are Correct? Answer: B & D

Lecture 9 : Graphs

• Reading Materials

• Slide: Slide23-Graphs.pdf (Print Version: 23-Graphs.pdf)

• Slide: Slide24-BFSDFS.pdf (Print Version: 24-BFSDFS.pdf)

• Slide: Slide25-MST.pdf (Print Version: 25-MST.pdf)

• Slide: Slide26-ShortestPath.pdf (Print Version: 26-ShortestPath.pdf)

• Reference:

  * Reference13-SingleSource.pdf

  * Reference14-AllPair.pdf
  

• Recitation Class (Tuesday 18:30pm, 11/19/2019, Room: 113F, TA: Qingmin Liu)

• Slide: GraphTheoryTutorial.pdf 

• Lab 8 : Graphs (Due: 16:00pm, 12/2/2019)

• Lab08-Graphs: Lab08-Graphs.pdf

• LaTex Source of Lab08: Lab08-Graphs.tex  

• Figure Source: Lab08-figure1.jpg, Lab08-figure2.jpg 

• Lab08 Solution: Lab08-Solution.pdf

• Best Labs: Lab08-ZhiyuHao.pdf, Lab08-XingyuMing.pdf, Lab04-YifanQian.pdf

Lecture 10 : Algorithm

• Reading Materials

• Slide: Slide27-GreedyAlgorithm.pdf (Print Version: 27-GreedyAlgorithm.pdf)

• Slide: Slide28-DynamicProgramming.pdf (Print Version: 28-DynamicProgramming.pdf)

• Reference:

  * Reference15-GreedyAlgorithm.pdf -- Chapter 4.1-4.3 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. 

  * Reference16-DynamicProgramming.pdf -- Chapter 6.1-6.7 in "Algorithm Design " by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.