Course Syllabus

Welcome to B503 Algorithm Design and Analysis! We will use Canvas for online discussion, announcements, and homework posts.

Please visit the course webpage http://homes.soic.indiana.edu/yzhoucs/teaching/B503sp17/ for more information on course description and logistics. 

 

Final Exam:  Wednesday, May 3, 8:00 – 10:00 am in INFO East 130

 

Lecture Recaps:

Lecture 01: Interval Scheduling Problem

Lecture 02: Scheduling All Intervals and Minimum Spanning Trees

Lecture 03: Kruskal's Algorithm and the Reverse-Delete Algorithm

Lecture 04: Implementing Kruskal's Algorithm with the Union-Find Data Structure

Lecture 05: Prim's Algorithm and Boruvka's Algorithm

Lecture 06: Single Source Shortest Path and Dijkstra's Algorithm

Lecture 07: The Stable Matching Problem

Lecture 08: One-side Optimality of Gale-Shapley and the Parity of Intervals Problem

Lecture 09: Merge Sort and Solving Recurrences

Lecture 10: Counting Inversions and Peak Finding 

Lecture 11: Integer Multiplication

Lecture 12: Closest Pair of Points 

Lecture 13: Convolution and Fast Fourier Transform (Part I)

Lecture 14: Fast Fourier Transform (Part II) and Introduction to Dynamic Programming

Lecture 15: Segmented Least Squares

Lecture 16: The Knapsack Problem

Lecture 17: RNA Secondary Structure 

Lecture 18: Sequence Alignment

Lecture 19: Linear Space Algorithm for Sequence Alignment and Bellman-Ford Algorithm

Lecture 20: All-Pair Shortest Path Problem and Floyd-Warshall Algorithm

Lecture 21: The Maximum Flow Problem and Ford-Fulkerson Algorithm

Lecture 22: The Maximum Flow Minimum Cut Theorem

Lecture 23: Capacity-Scaling Algorithm and the Maximum Matching Problem

Lecture 24: Hall's Theorem and the Image Segmentation Problem

Lecture 25: Baseball Elimination

Lecture 26: Project Selection

Course Summary:

Date Details Due