Data Structures and Algorithm Analysis (CSC317)

• September 24: Quiz (Sarkar).
  Dynamic programming part 1: Fibonacci and (only motivation for) Longest Common Subsequence.
  Bellman birth of Dynamic Programming
  Fibonacci animation website by David Galles.
  Fibonacci compute time by Burt Rosenberg.
  Cipher Thomas Jefferson.
  AlgorithmsDP1.pdf
  


• September 26: Dynamic programming part 2: Longest Common Subsequence.
  LCS animation website by David Galles.
  AlgorithmsDP2.pdf
  


• October 1: Dynamic programming part 3: Rod cutting problem.
  We continued the DP2 slides above with the rod cutting example.


• October 3: Wrapped up dynamic programming and started greedy algorithms:
  csc317Fall2019Lecture13
  


• October 8: Greedy algorithms continued:
  csc317Fall2019Lecture14
  


• October 10: Greedy algorithms part 3: Huffman coding: Algorithms8c_greedy_fall19.pdf
  Compression intro slides
  


• October 15:
  Quiz.
  Review/Intro of data structures:
  AlgorithmsDataStructuresReview


• October 22: Hash functions part 1: Algorithms_hash1.pdf


• October 24: Hash functions part 2: algorithms_hash2.pdf


• October 29: Binary Search Trees: Algorithms_binarySearchTrees.pdf


• October 31: Red Black Trees part 1: Algorithms_RedBlackTree1.pdf


• November 5: Red Black Trees part 2: Algorithms_RedBlackTree2.pdf
  Algorithms_RedBlackTree3.pdf
  See also Red Black Tree animation website by David Galles.


• November 7: Red Black Trees part 3: Algorithms_RedBlackTree3.pdf See also Red Black Tree animation website by David Galles.


• November 12: 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_fall19.pdf
  


• November 14: Graph algorithms 2: DFS.
  DFS_animation website by David Galles.
  AlgorithmsGraphsClass2_fall19.pdf
  


• November 19: Graph algorithms 3: Topological Sort, Starting Strongly Connected Components.
  AlgorithmsGraphsClass3.pdf
  Broder paper on web connectivity
  


• November 21: Graph algorithms part 4: Dijkstra: AlgorithmsGraphs4.pdf
  

• 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