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