Design and Analysis of Algorithms -- CS 312, Department of Computer Science, PU

CS 312 Design and Analysis of Algorithms
Fall 2022
Nazar Khan

Algorithms lie at the heart of Computer Science. The journey from a problem to its algorithmic solution can be messy. It involves two stages:

extracting the mathematically clean core of the problem, and
identifying the appropriate algorithm design technique based on problem structue

This course introduces algorithms as a process of crisply understanding problems and designing efficient solutions.

CS 312 is an undergraduate course worth 3 credit hours.

Lectures:
Morning Section: Monday and Wednesday, 9:45 a.m. - 11:15 a.m.
Afternoon Section: Monday and Wednesday, 2:30 p.m. - 4:00 p.m.
Office Hours: Wednesday, 12:00 p.m. - 1:00 p.m.

Grading:

Assignments	15%
Quizzes	10%
Mid-Term	35%
Final	40%

Prerequisites

Data Structures

Text

KT: Algorithm Design by Jon Kleinberg and Éva Tardos
CLRS: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein (2nd Edition)

Lectures

#	Date	Topics	Readings	Miscellaneous
1	October 17	Introduction
2	October 19	Stable Matching	KT 1.1
3	October 24	Analysis of Stable Matching	KT 1.1
4	October 26	5 Representative Problems	KT 1.2
5	October 31	Computational Tractability	KT 2.1
6	November 2	Computational Tractability (contd.)	KT 2.1
7	November 7	Asymptotic Order of Growth	KT 2.2
8	November 9	Gale-Shapely Implementation Using Lists and Arrays	KT 2.3
9	November 14	Survey of Common Running Times	KT 2.4
10	November 16	Survey of Common Running Times (contd.)	KT 2.4
11	November 21	Graphs I: Introduction	KT 3.1
12	November 23	Graphs II: Connectivity and Traversal	KT 3.2
13	November 28	Graphs III: Traversal using Queues and Stacks	KT 3.3
14	November 30	Graphs III: Traversal using Queues and Stacks (contd.)	KT 3.3
15	December 5	Greedy Algorithms I: Interval Scheduling Problem	KT 4.1
16	December 7	Greedy Algorithms II: Interval Scheduling Problem	KT 4.1
	December 16	Mid-term Examination
17	December 19	Greedy Algorithms III: Shortest Paths in Weighted Graph	KT 4.4
18	December 21	Greedy Algorithms IV: Minimum (Cost) Spanning Tree (MST)	KT 4.5
19	January 9	Divide & Conquer I: Merge Sort	KT 5.1, CLRS 2.3 for Merge Sort
20	January 11	Divide & Conquer II: Solving Recurrence Relations	KT 5.2
21	January 16	Divide & Conquer III: Integer Multiplication	KT 5.5
22	January 18	Dynamic Programming I: Fibonacci Sequence
23	January 23	Dynamic Programming II: Longest Increasing Subsequence Weighted Interval Scheduling
24	January 25	Dynamic Programming III: Longest Common Subsequence	CLRS 16.4
25	January 30	Dynamic Programming IV: Travelling Salesperson Problem
26	February 1	P versus NP and NP-Complete Problems
27	February 6	Probabilistic Analysis and Randomized Algorithms	CLRS Ch. 5
28	February 8	Quicksort and Randomized Quicksort	CLRS Ch. 7
29	February 13	Approximation Algorithms I	CLRS Ch. 35
30	February 16	Approximation Algorithms II
	February 23	Final Exam