EECS 3101M: Design and Analysis of Algorithms, Winter 2025

Basic Information

IMPORTANT: This is the webpage intended for section M.

Instructor: Aditya Potukuchi

Time: TR 13:00-14:30PM, LSB105

Tutorial: F 13:00PM-14:30PM, SLH A

Office Hours: T 11:00AM-12:00PM or by appointment LAS 3052B

Basic info handout

Schedule

Jan 7: Administrivia, introduction to big Oh; Reading: DPV Ch 0.3.

Jan 9: basic math background, and big Oh recap; Reading: DPV Ch 0.

Jan 14: Divide and Conquer paradigm; Reading: DPV Ch 2.1, 2.2.

Jan 16: Divide and conquer contd..-Sorting and Median; Reading: DPV Ch 2.3, 2.4

Jan 21: Selection, Binary search, Majority; Reading: DPV Ch 2.4, Boyer-Moore algorithm

Jan 23: More divide and conquer practice;

Jan 28: nlogn lower bound for sorting, Divide and Conquer practice; Reading: DPV page 59, problems 2.17, 2.19

Jan 30: Assorted topics related to divide & conquer; Reading: check announcement on eclass.

Feb 4: Intro to Dynamic Programming; Reading: DPV Ch 6.2

Feb 6: Dynamic Programming contd..; Reading: check announcement on eclass

Feb 11: Single Source Shortest Paths in graphs; Reading: DPV 6.1

Feb 13: Dynamic Programming contd..; Reading: check announcement on eclass (after class)

Feb 25: Edit-distance; Reading: DPV Ch 6.3

Feb 27: More dynamic programming practice (leetcode problem #32)

Mar 4: Dynamic programming review

Mar 6: Dynamic programming review

Mar 11: no class

Mar 13: Introduction to graph search, DFS,BFS; Reading: DPV Ch 3, 4.1, 4.2

Mar 18: BFS/DFS contd..; Reading: DPV Ch 3, 4.1, 4.2

Mar 20: Bellman-Ford algorithm for shortest paths; Reading: DPV 6.6 (recommended), 4.6 

Mar 25: Floyd-Warshall algorithm for All-Pairs Shortest Paths; Reading: DPV 6.6