Data Structures and Algorithm Analysis (CSC317)

• Aug 21: Introduction to algorithms: Algorithms1aSlides_fall18.pdf
• Aug 23: Introduction to algorithms: Algorithms1bSlides_fall18.pdf
• Aug 28: Loop invariants in Aug 23 slides; Started intro to complexity classes and growth of functions, including big Oh, Omega, Theta: Algorithms2aSlides_fall18.pdf
  Website on complexity classes beyond scope of class: ComplexityZoo
  Loop Invariants for Findmin: LoopInvariantExample
  Loop Invariant Example Code: LoopInvariantExampleCode2.pdf
  
• Aug 30: Continued intro to complexity classes and growth of functions, including big Oh, Omega, Theta. Slides above and also: Algorithms2bSlides_fall18.pdf
  Started Divide and Conquer part 1 up to and including Max Subarray problem: Algorithms3aSlidesClass_fall18.pdf
• Sept 4: Continued Divide and Conquer part 1 and 2. Divide and Conquer part 2: Algorithms3bSlides_class_fall18.pdf
• Sept 6: Continued Divide and Conquer part 2 (slides above), and part 3: Algorithms3c_2018.pdf
• Sept 11: Continued divide and Conquer part 3 (slides 3c above).
• Sept 13: Randomized algorithms 1, Probability review: Algorithms4aSlides_fall18.pdf
• Sept 18: Randomized algorithms 2, and Quicksort: Algorithms4b_fall18.pdf
Algorithms4c_fall18.pdf
Partition algorithm for quicksort animation by Burt Rosenberg: Partition
We also talked about optimal stopping algorithms for hiring and other applications in the book: Algorithms to Live By: The Computer Science of Human Decisions (Brian Christian, Tom Griffiths).
• Sept 20: Finished Randomized algorithms with brief mention of Order Statistics (slides above). Review/Intro of data structures: Algorithms5aSlides_fall18.pdf
• Sept 25: Hash functions part 1: Algorithms5b_fall18.pdf
• Sept 27: Hash functions part 2: Algorithms5c_fall18.pdf
• Oct 2: Binary Search trees: Algorithms6aClass_fall18.pdf
• Oct 4: Red Black Trees part 1: Algorithms6b_RedBlackTree_fall18.pdf (material not on midterm)
• Oct 9: Review for midterm.
• Oct 11: Midterm in class.
• Oct 16: Red Black Trees part 2: Algorithms6c_RedBlackTreeCont_fall18.pdf
  See also Red Black Tree animation website by David Galles.
• October 23: Graph algorithms 1: Intro and BFS.
  friendsArticle2018.pdf
  Networks, Crowds, and Markets book. By David Easley and Jon Kleinberg
  BFS_animation website by David Galles.
  AlgorithmsGraphsClass1_fall18.pdf
  
• October 25: Graph algorithms 2: DFS and Topological Sort.
  DFS_animation website by David Galles.
  AlgorithmsGraphsClass2_fall18.pdf
  Topological Sort in: AlgorithmsGraphsClass3_fall18.pdf
  
• October 30: Graph algorithms part 3: Strongly Connected Components: Strongly Connected Components in: AlgorithmsGraphsClass3_fall18.pdf
  Broder paper on web connectivity
  
• Nov 1: Graph algorithms part 4: Dijkstra: AlgorithmsGraphsClass4_fall18.pdf
  
• Nov 6: Dynamic programming part 1: Fibonacci and (only motivation for) Longest Common Subsequence:
  DP1_2018.pdf (notes up to the intuition of Longest Common Subsequence).
  Bellman birth of Dynamic Programming
  Fibonacci animation website by David Galles.
  Fibonacci compute time by Burt Rosenberg.
  Cipher Thomas Jefferson.
  
• Nov 8: Dynamic programming part 2: Longest Common Subsequence from slides above. LCS animation website by David Galles.
  
• Nov 13: Dynamic programming part 3: Rod cutting problem: Algorithms7b_DynamicP_fall18.pdf
• Nov 15: Greedy algorithms part 1: Activity Selection problem: Algorithms8a_greedy_fall18.pdf
• Nov 20; 22: Thanksgiving break!
• Nov 27: Greedy algorithms part 2: Huffman coding: (slides also include the knapsack problem we discussed in the previos class) Algorithms8b_greedy_fall18.pdf
  Compression intro slides
  

• Introduction to algorithms
• Sorting as example
• Correctness
• Growth of functions and Big-Oh notation
• Divide and conquer and recursion equations
• Randomized algorithms
• Hashing
• Trees and Red Black Trees
• Algorithmic paradigms: Dynamic programming, Greedy algorithms
• Graph Algorithms