CSC 225 Class Notes: Fall 2013

For a complete set of notes, please attend class or get notes from someone who attended. Only selected notes will be placed here.

  1. Lecture 1: Introduction to CSC 225.
  2. Lecture 2: Review of Linked Lists.
  3. Lecture 3: Review of Induction.
  4. Lecture 4: Review of recurrences.
  5. Lecture 5: Divide and Conquer.
    Lecture 5: Solution to recurrence relation.
  6. Lecture 6: Loop invariants.
  7. Lecture 7: Lower and Upper bounds.
  8. Lecture 8: Mergesort.
  9. Lecture 9: Big Oh, Omega, Theta, and the time complexity of mergeSort.
  10. Lecture 10: MaxSort.
  11. Lecture 11: MaxSort Proofs.
  12. Lecture 12: QuickSort.
  13. Lecture 13: Space.
  14. Lecture 14: Heaps.
  15. Lecture 15: Space usage of sorting algorithms.
  16. Lecture 20: A lower bound for comparison-based sorting algorithms.
  17. Lecture 21: Radix Sort.
  18. Lecture 22: Introduction to Graph Theory.
  19. Lecture 23: Union/Find.
  20. Lecture 24: Faster Union/Find.
  21. Lecture 25: Kruskal's algorithm for MST.
  22. Lecture 26: Breadth First Search.
  23. Lecture 27: Depth First Search.
  24. Lecture 28: Analysis of Kruskal's algorithm.
  25. Lecture 29: The Dijkstra/Prim MST algorithm.
  26. Lecture 30: Hashing.
  27. Lecture 31: Correctness of MST algorithms.
  28. Lecture 32: Shortest path.
  29. Lecture 33: Introduction to NP-completeness.
CSC 225 Notes / maintained by Wendy Myrvold / wendym@csc.UVic.ca / revised Dec. 3, 2013