CSCI 235
Analysis of Algorithms
College of the Holy Cross, Spring 2024
Date
Week
Lecture
Topic
Algorithms
Aug-27
1
1
Introduction
Karatsuba multiplication
Aug-29
2
Run-time of Algorithms
Insertion sort, FindMax
Sep-3
2
3
Asymptotic Analysis
Sep-5
4
Mathematical Foundation - Exponents, Logs, Series Sum etc
Sep-10
3
5
Recursive Analysis
Tower of Hanoi
Sep-12
6
Divide and Conquer
Merge sort, Binary search
Sep-17
4
7
Divide and Conquer II
Sep-19
8
Divide and Conquer III
Sep-24
5
9
Probabilities
Sep-26
10
More Probabilities
Hiring Problem
Oct-1
6
11
Exam review
Oct-3
12
Heapsort and Quicksort
Heapsort, Quicksort
Oct-8
7
13
Dynamic Programming
Fibonacci, Change-making
Oct-10
14
Dynamic Programming II
Longest increasing subsequence, Edit Distance
Oct-15
break
Oct-17
break
Oct-22
8
15
Dynamic Programming III
Edit Distance, Knapsack
Oct-24
16
Greedy Algorithms I
Fractional Knapsack, Scheduling
Oct-29
9
17
Heaps revisited, Priority Queues
Priority Queue operations
Oct-31
18
More Data Structures (BSTs, Sorted Lists)
Nov-5
10
19
AVL Trees
Rotations in BSTs
Nov-7
20
Graphs and Representation
DFS, TopSort
Nov-12
11
21
Exam review
Nov-14
22
Graph Algorithms I
DFS recap, BFS started
Nov-19
12
23
Graph Algorihtms II
Dijsktra
Nov-21
24
Graph Algorihtms III
MST, Prim's Algorithm
Nov-26
13
25
Computational Complexity, P-vs-NP
Size of input, P, NP, NP-Hard problems
Nov-28
break
Dec-3
14
26
NP-Complete Problems and Reductions
Dec-5
27
Review for Finals
Last modified: Aug 26, 2024