These are subject to change as the course progresses. The links to the notes are from Prof. O'Kane's CSCE 750 class last Fall. I will be making adjustments to these as the course moves forward. The easiest way to tell if I've updated a document is when it no longer says "Fall 2020" but "Fall 2021" instead.

Homework 0 | (not graded) [hw00.pdf] | |

2021-08-19 | Lecture 01 | Introduction to the course [notes-intro.pdf] |

First day survey | ||

2021-08-24 | Lecture 02 | Models of computation; asymptotic notations [notes-asymptotics.pdf] |

2021-08-26 | Lecture 03 | Summations [notes-summations.pdf] |

2021-08-31 | Homework 1 |
[hw1.pdf] [hw1-ans.pdf] |

2021-08-31 | Lecture 04 | Solving recurrences; substitution method [notes-recurrences.pdf] |

2021-09-02 | Quiz 1 |
TBD |

2021-09-02 | Lecture 05 | More on recurrences; substitution method: proving a stronger bound |

2021-09-07 | Lecture 06 | More on recurrences; recursion trees; Master theorem |

2021-09-09 | Lecture 07 | Priority queues and heaps [notes-heaps.pdf] |

2021-09-14 | Homework 2 |
[hw2.pdf] |

2021-09-14 | Lecture 08 | Randomized algorithms; Quicksort [notes-randomized.pdf] |

2021-09-16 | Quiz 2 |
TBD |

2021-09-16 | Lecture 09 | More on randomized algorithms |

2021-09-21 | Lecture 10 | Order statistics; randomized Quickselect; deterministic selection in linear time [notes-selection.pdf] |

2021-09-23 | Lecture 11 | Lower bounds; hash tables [notes-lowerbounds.pdf] [notes-hash.pdf] |

2021-09-28 | Homework 3 |
[hw3.pdf] |

2021-09-28 | Lecture 12 | More on hash tables; binary search trees [notes-bst.pdf] |

2021-09-30 | Quiz 3 |
TBD |

2021-09-30 | Lecture 13 | More on binary search trees, including treaps |

2021-10-05 | Lecture 14 | Treap analysis; augmenting data structures [notes-augmenting.pdf] |

2021-10-12 | Lecture 15 | Dynamic programming [notes-dp.pdf] |

2021-10-14 | Homework 4 |
[hw4.pdf] |

2021-10-14 | Lecture 16 | Amortized analysis [notes-amortized.pdf] |

2021-10-19 | Quiz 4 |
TBD |

2021-10-19 | Lecture 17 | Fibonacci heaps: basic structure [notes-fibheap.pdf] |

2021-10-21 | Lecture 18 | Fibonacci heaps: operations |

2021-10-26 | Lecture 19 | Fibonacci heaps: analysis |

2021-10-28 | Homework 5 |
[hw5.pdf] |

2021-10-28 | Lecture 20 | TBD |

2021-11-02 | Quiz 5 |
TBD |

2021-11-02 | Lecture 21 | Disjoint sets [notes-disjoint-sets.pdf] |

2021-11-04 | Lecture 22 | More on disjoint sets; elementary graph algorithms [notes-graphs.pdf] |

2021-11-09 | Homework 6 |
[hw6.pdf] |

2021-11-09 | Lecture 23 | Minimum spanning trees [notes-mst.pdf] |

2021-11-11 | Quiz 6 |
TBD |

2021-11-11 | Lecture 24 | Shortest paths on graphs [notes-diskstra.pdf] |

2021-11-16 | Lecture 25 | NP-completeness [notes-npcomplete.pdf] |

2021-11-18 | Homework 7 |
[hw7.pdf] |

2021-11-18 | Lecture 26 | More on NP-completeness |

2021-11-23 | Quiz 7 |
TBD |

2021-11-23 | Lecture 27 | TBD, possibly pretaped |

2021-11-30 | Lecture 28 | TBD, possibly pretaped |

Homework 8 | (not graded) [hw8.pdf] | |

2021-12-02 | Review | [review.pdf] |

2021-12-09 | Final Exam |
12:30pm - 3:00pm |

- My old lecture notes
- Hand-written notes made while lecturing a previous class
- Fall 2009 quizzes with solutions
- Answer key to the Fall 2005 final exam.

Announcements (with dates) will be posted here in reverse chronological order.

(November 30, 2021) To find the recordings of make-up lectures, go to the course in Blackboard, then click Blackboard Collaborate Ultra in the left menu, then in the Sessions bar at the top, click on the menu icon (horizontal lines) on the left.

(August 17, 2021) The University requires wearing masks in all UofSC buildings and on campus transportation.

This page was last modified Thursday December 2, 2021 at 06:40:15 EST.