CMP 741 - Advanced Analysis of Algorithms

CMP 741 - Advanced Analysis of Algorithms (Spring 2021)

CMP 741 - Advanced Analysis of Algorithms, (Virtual)

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2021/cmp741

Learning objectives
This is an in-depth course on the theory and analysis of algorithms.
Resources

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Algorithm Design by Jon Kleinberg, and Eva Tardos.

Jeff Erickson's Algorithm Notes (available online)

Course Notes for "CS15-251: Great Theoretical Ideas in Computer Science" at CMU (available online)

Similar Courses

CS125: Algorithms and Complexity at Harvard Uni.

15-251: Great Theoretical Ideas in Computer Science at Carnegie Mellon Uni.

COS423: Theory of Algorithms at Princeton Uni.

CS170: Efficient Algorithms and Intractable Problems at EECS, Berkeley Uni.

15-451: Algorithms at Carnegie Mellon Uni.

CS374: Algorithms and Models of Computation at Uni. of Illinois

CS473: Algorithms at Uni. of Illinois

Grading

Midterm Exam, 35%

Quizzes, 35%

Final Project, 30%

Schedule

Date Topic and Slides Notes Reading on Applications and
Notes by Jeff Erickson (JE)

Feb. 22 - 26 Graphs
[Slides: 1 ] Chapter 3 in KT

Mar. 1-5 Greedy Algorithms
[Slides: 1] Chapter 4 in KT
Further Examples on Greedy Algorithms

Mar. 8-12 Divide and Conquer
[Slides: 1, 2] Chapter 5 in KT

Mar. 15 - 19 Dynamic Programming
Deadline to Pick a Paper
[Slides: 1, 2] Chapter 6 in KT

Mar. 22 - 26 Network Flow
[Slides: 1, 2]
Chapter 7 in KT
Ford-Fulkerson Demo

Mar. 29 - Apr. 2 Intractability I: Polynomial Time Reductions
[Slides] Chapter 8 in KT

Apr. 5 - 9 Midterm Exam --

Apr. 12 - 16 Intractability II: P, NP, and NP-complete
[Slides] Chapter 8 in KT

Apr. 19 - 23 PSPACE: A Class of Problems beyond NP
[Slides] Notes Chapter 9 in KT

Apr. 26 - 30 Limits of Tractability [Slides] Chapter 10 in KT

May 3 - 7 Approximation Algorithms [Slides] Chapter 11 in KT
Approximation Algorithms (JE)

May 10 - 14 Local Search
Deadline for Paper Reading Submission
[Slides] Chapter 12 in KT

May 17 - 21 Randomized Algorithms [Slides] Chapter 13 in KT
Randomized Algorithms (JE)

May 24 - 28 Paper Presentations --

© 2021 Hacettepe University

Date	Topic and Slides	Notes	Reading on Applications and Notes by Jeff Erickson (JE)
Feb. 22 - 26	Graphs [Slides: 1 ]		Chapter 3 in KT
Mar. 1-5	Greedy Algorithms [Slides: 1]		Chapter 4 in KT Further Examples on Greedy Algorithms
Mar. 8-12	Divide and Conquer [Slides: 1, 2]		Chapter 5 in KT
Mar. 15 - 19	Dynamic Programming Deadline to Pick a Paper [Slides: 1, 2]		Chapter 6 in KT
Mar. 22 - 26	Network Flow [Slides: 1, 2]		Chapter 7 in KT Ford-Fulkerson Demo
Mar. 29 - Apr. 2	Intractability I: Polynomial Time Reductions [Slides]		Chapter 8 in KT
Apr. 5 - 9	Midterm Exam		--
Apr. 12 - 16	Intractability II: P, NP, and NP-complete [Slides]		Chapter 8 in KT
Apr. 19 - 23	PSPACE: A Class of Problems beyond NP [Slides]	Notes	Chapter 9 in KT
Apr. 26 - 30	Limits of Tractability [Slides]		Chapter 10 in KT
May 3 - 7	Approximation Algorithms [Slides]		Chapter 11 in KT Approximation Algorithms (JE)
May 10 - 14	Local Search Deadline for Paper Reading Submission [Slides]		Chapter 12 in KT
May 17 - 21	Randomized Algorithms [Slides]		Chapter 13 in KT Randomized Algorithms (JE)
May 24 - 28	Paper Presentations		--