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

CS 312 Design and Analysis of Algorithms
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: Monday and Wednesday, 12:15 p.m. - 1:45 p.m.
Office Hours: Monday, 2:30 p.m. - 3:30 p.m.
Google Classroom: https://classroom.google.com/c/NjI4MTY5NTc4NDU0?cjc=am3ri7b

Grading:

Quizzes	25%
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

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