IAP
Course Outline
1
Searching
1.1
Summary Lecture
1.2
Linear Search 1
1.2.1
Correctness
1.2.2
Complexity
1.2.3
Optimality
1.3
Linear Search 2
1.3.1
Correctness
1.3.2
Complexity
1.4
Bisection Search
1.4.1
Correctness
1.4.2
Complexity
1.5
Bisection Search 2
1.5.1
Complexity
1.5.2
Optimality
1.6
References
2
Sorting
2.1
Max Sort
2.1.1
Correctness
2.1.2
Complexity
2.1.3
Optimality
2.2
Selection Sort
2.3
Bubblesort
2.4
Insertion Sort
2.5
Mergesort
2.6
Quicksort
2.7
Optimal Sorting
2.8
References
3
Greedy Algorithms
3.1
Summary Lecture
3.2
Optimal Service
3.2.1
Brute Force Solution
3.2.2
Greedy Solution
3.3
Greedy Algorithm Properties
3.4
Proof of Correctness for Optimal Service
3.5
Making Change
3.5.1
Brute Force Solution
3.5.2
Greedy Solution
3.6
Additional Reading
4
Dynamic Programming
4.1
Shortest Path Problem
4.1.1
Complexity
4.1.2
Correctness
4.2
Properties of Dynamic Programming
4.3
Floyd-Warshall
4.4
Summary Lecture (Part 1)
4.5
Making Change
4.6
Efficient Matrix Multiplication
4.7
Additional Reading
5
Computational Geometry
5.1
Summary Lecture
5.2
Introduction
5.3
Brute Force Approach
5.3.1
Correctness
5.4
Divide and Conquer Approach
5.5
An
\(O(n \lg n)\)
Algorithm
5.5.1
Optimality
5.5.2
Correctness
5.6
Additional Reading
6
Hashing
6.1
Direct Addressing
6.2
Introduction to Hashing
6.3
Closed Address Hashing
6.4
Open Address Hashing
6.5
Hash Functions
6.6
Summary Lecture
6.7
Additional Reading
Advanced Analysis of Algorithms
Advanced Analysis of Algorithms
COMS3005A
Steven James
Semester 2, 2022
[Updated: 2022-10-17]
