CS580
Algorithm Design, Analysis, and Implementation

Instructor: Tamal K. Dey and Mikhail (Mike) Atallah
Content Description : In this course we will go through different paradigms for algorithm design such as divide-and-conquer, prune-and-search, dynamic progamming, greedy strategy, randomization, linear programming, approximation and different analysis techniques with different data structures. We will apply these design and analysis techniques to develop efficient graph and other algorithms. At the end, we will go over the concept of NP-completeness.
Objectives

Be familiar with topics in algorithms such as the ones listed above
Be familiar with how to design algorithms for problems with techniques listed above
Master a subset of algorithms: graph algorithms, linear programming, approximation algorithms
Be familiar with how to research the background of a topic in algorithms

Prerequisites: CS381; or grad standing and permission of instructor
Recommended Books:

Algorithm Design, J. Kleinberg and E. Tardos, Pearson, Addison-Wesley
Introduction to Algorithms, T. Cormen, C. Leiserson and R. Rivest, MIT press, McGraw-Hill Book Company.
Also see the free electronic copy of Algorithms by Jeff Erickson.

Class discussion:

This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and instructors. Rather than emailing questions to the teaching staff, we encourage you to post your questions on Piazza.

Find our class signup link at: https://piazza.com/purdue/fall2023/cs58000
Schedule and Policy

Materials (Hand written Transparencies and slides from Kleinberg-Tardos Book)

Topics	Class presentations on transparencies/slides posted on this page may be useful
1. Background, sorting, searching	a. Big O- and Big-Omega [slides]
	b. Heap sort [transparencies]
	c. Quick sort [transparencies]
	d. Selection [transparencies]
	e. Search trees [transparencies]
2. Dynamic Programming	a. Dynamic programming principles [slides] b. Dynamic programming example [transparencies] c. More dynamic programming examples [transparencies]
3. Greedy Algorithms	a. Greedy strategy in scheduling [transparencies] b. More problems solved with greedy strategy [ slides ]
4. Amortization	a. Amortization principle [transparecies] b. Fibinacci Heap I [transparencies] c. Fibonacci Heap II [transparencies] d. Union-Find [transparencies]
5. Graph search	a. Depth first search (DFS) [transparencies] b. Breadth first search (BFS) [transparencies] c. Topological sort [transparencies]
6. Graph algorithms	a. Minimum spanning tree [transparencies] b. Single source shortest path [transparencies] c. All-pairs shortest path [transparencies] d. Network flow [transparencies] e. Max-flow, min-cut [transparencies] f. Edmond-Karp algorithm [transparencies]
7. Linear programming	a. Framework [transparencies] b. Simplex algorithm [transparencies] c. Duality [transparencies] d. LP rounding and vertex cover [transparencies]
8. Approximation Algorithms	a. Vertex-cover and TSP [transparencies] b. TSP with 1.5-approximation [transparencies] c. Set-cover [transparencies] d. Subset-sum [transparencies]
9. Randomization	a. Randomized LP rounding [transparencies] b. Randomized global mincut [slides] c. Randomized max 3-SAT [transparencies]
9. NP-completeness	a. Intractability [slides] b.NP-completeness [slides] c. Reductions [slides]

Homework

Meeting Place: LILY G126
Meeting Time: 12:00--1:15 pm TuTh
Office Hours: 4:00-4:50 TuTh
Grading

Homework	25%
Midterm	35%
Final	40%

Latex Resource

Last updated 08/15/23

CS580 Algorithm Design, Analysis, and Implementation

CS580
Algorithm Design, Analysis, and Implementation