CSE 3101 - Design & Analysis of Algorithms
Summer 2008
Outline of Lectures
Lecture 12
(upcoming lecture)
Lecture 11
Lecture 10
Lecture 9
Lecture 8
Lecture 7
Lecture 6
Lecture 5
Lecture 4
Lecture 3
Lecture 2
Lecture 1
Lecture 12
- Closing lecture: conclude with NetFlows and revise DP and NetFlows
Lecture 11
- Network Flows (Chapter 7 and Lecture Notes)
Lecture 10
- Dynamic Programming (Chapter 6)
Lecture 9
- Discuss the questions from the midterm test
- Introduction to Dynamic Programming - Chapter 6
Lecture 8
- DFS and BFS graph traversals - Chapter 3
- Review of Greedy, DnC and greedy approximation algorithms
Lecture 7
- Mild introduction to approximation algorithms - Paragraph 11.1-11.2
and
lecture notes
Lecture 6
- Continue with Divide and conquer - Chapter 5
Lecture 5
- Finish with greedy algorithms: Dijkstra's SSSP algorithm - Chapter 4
- Divide and conquer: faster polynomial-time algorithms - Chapter 5
Tutorial (before lecture): Dijkstra's algorithm, applications of DFS &
BFS, MergeSort (if you don't attend the tutorial prepare these
topics)
Lecture 4
- Continuing with greedy algorithms - Chapter 4
Lecture 3
- Measuring the efficiency of an algorithm. Worst-case time and space
recourses - Paragraphs: 2.1-2.4
- First algorithmic paradigm: Greedy algorithms - Chapter 4
Lecture 2
- Analysis of stable-marriage algorithm
- Measuring the efficiency of an algorithm. Worst-case time and space resources
Lecture 1
- 3101: what is it about?
- The stable marriage problem