csce350: Data Structures and Algorithms

Fall 2019 - University of South Carolina - Jason O'Kane

Past Present Future Undated
2019-08-21
Homework 0
This assignment is a very quick summary (hopefully, a reminder) of the some math that we'll use later. It is recommended but not required.
[hw00.pdf]
2019-08-22
Lecture 01
Introduction to the course. What is an algorithm?
2019-08-27
Complete online by 11:59pm. Worth 10 points.
2019-08-27
Lecture 02
Describing algorithms. Euclid's algorithm for greatest common divisors. Array search problem and linear search algorithm.
[notes-intro.pdf]
2019-08-29
Lecture 03
More on linear search. Steps for analyzing algorithms. Input size. Basic operations. Best-, worst-, and average-case analysis.
[notes-analysis.pdf]
2019-09-03
Homework 1
2019-09-03
Lecture 04
Big-$\Theta$, Big-$O$, and Big-$\Omega$ notations.
[notes-big.pdf]
2019-09-05
Homework 2
2019-09-05
Lecture 05
Counting operations in nonrecursive algorithms. Summations.
[notes-analysis-nonrecursive.pdf]
2019-09-10
Homework 3
2019-09-10
Lecture 06
More on summations. Counting basic operations in recursive algorithms.
[notes-analysis-recursive.pdf]
2019-09-12
Homework 4
2019-09-12
Lecture 07
More on analyzing recursive algorithms. Solving recurrences via backward substitution.
2019-09-17
Homework 5
2019-09-17
Lecture 08
Brute force. Integer powers. Selection sort. Brute force string matching.
[notes-brute-force.pdf]
(No homework due September 19.)
2019-09-19
Lecture 09
Exhaustive search. Traveling salesman. Knapsack problem.
2019-09-24
Homework 6
2019-09-24
Lecture 10
More on exhaustive search. Decrease and conquer. Integer powers. Insertion sort.
[notes-decrease.pdf]
2019-09-26
Test 1
Covering material up to and including September 19.
[review1.pdf]
2019-10-01
Lecture 12
More on insertion sort. Partitioning.
2019-10-03
Lecture 13
More on partitioning. Quickselect.
2019-10-08
Homework 7
2019-10-08
Lecture 14
Return Test 1. Discuss Project 2.
2019-10-10
Fall break
2019-10-15
Homework 8
2019-10-15
Lecture 15
Divide and conquer. The Master Theorem. Mergesort.
[notes-divide.pdf]
2019-10-17
Lecture 16
Quicksort. Multiplication of large numbers.
2019-10-22
Homework 9
2019-10-22
Lecture 17
More discussion of Project 2. More on multiplication of large numbers.
2019-10-24
Homework 10
2019-10-24
Lecture 18
Transform and conquer. Presorting. Binary search trees.
[notes-transform.pdf]
2019-10-24
Project 2
2019-10-29
Homework 11
2019-10-29
Lecture 19
AVL trees.
2019-10-31
Homework 12
2019-10-31
Lecture 20
Preview for Test 2. 2-3 Trees.
[extra-23trees.pdf]
2019-11-05
Test 2
2019-11-07
Lecture 22
Guest lecture on geometric algorithms.
2019-11-12
2019-11-12
Lecture 23
Discussion of Project 3. Heaps.
[notes-decrease.pdf]
2019-11-14
Lecture 24
Dynamic programming. Fibonacci numbers. Binomial coefficients.
[notes-dp.pdf]
2019-11-19
Homework 13
2019-11-19
Lecture 25
More on dynamic programming. Knapsack problem.
2019-11-19
Project 3
2019-11-21
Homework 14
2019-11-21
Lecture 26
Preview Project 4. More on knapsack program via dynamic programming. Top-down versus bottom-up.
2019-11-26
Lecture 27
Top-down dynamic programming.
2019-11-28
Thanksgiving break
2019-12-03
Homework 15
2019-12-03
Lecture 28
Greedy algorithms. Graph representations. Minimum spanning trees. Prim's algorithm. Kruskal's algorithm.
[notes-greedy.pdf]
[extra-disjoint-sets.pdf]
2019-12-05
Homework 16
2019-12-05
Lecture 29
More on greedy algorithms. Wrap up. Course evaluations.