DAA(BTech) 2022 Course Page

Design and Analysis of Algorithms, January - April 2022

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- CB-51, Faculty chambers, IIIT Bhubaneswar

Online Class schedule ( ≈ 4 hrs per Week)

Attention: Due to COVID-19 pandemic, the classes will be taken in Google Classroom.

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
CS	10:00 am	12:00 pm	11:00 am	09:00 am	-	-	-
CE	03:00 pm	09:00 am	09:00 am	-	02:00 pm	-	-

Objective

The main objective of this course is to discuss the techniques necessary to propose practical algorithmic solution for real world problems, which still permit strong theoretical bounds on time and space utilization. Students will study a wide collection of important and useful algorithms with necessary data structures in different areas of applications, focusing on fundamental concepts.

Learning Outcomes

Upon successful completion of this course, the student should be able to:

Compare, differentiate and apply the key algorithmic design paradigms: Divide and conquer, dynamic programming, greedy, brute force etc.
Compare, contrast, and apply algorithmic trade-offs: time vs. space, deterministic vs. randomized, exact vs. approximate
Model and implement algorithms for various applications areas with suitable data structure.
Argue correctness of algorithms using different proof techniques.
Implement and apply fundamental algorithms and data structure to real-world problems.

Syllabus

You can find the syllabus ~~[here]~~.

Books

Text Book

T1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. (CLRS, 3rd Ed.)

Reference Books

R1. Handbook of Data Structures and Applications by Dinesh P Mehta, Sartaj Sahni, Chapman and Hall/CRC.
R2. Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw Hill Education (India) Pvt. Ltd.
R3. The Design and Analysis of Computer Algorithms by Aho, Hopcroft, Ullman, Addison-Wesley.
R4. Algorithm Design: Foundations, Analysis, and Internet Examples by M. T. Goodrich, R. Tamassia, John Wiley & Sons.
R5. Algorithm Design by Jon Kleinberg, Éva Tardos, Pearson.

Evaluation

Note: Following the uncertainty caused by COVID-19, this evaluation process may subject to change.

Course Progress and Resources

Sl No #	Date	Time	Duration	Reading List and Resources	Contents Discussed
1	-	-	1 hr	Chapter 1 of T1 ~~[ Lecture Slide ]~~	Overview of the course; Motivation and introduction; RAM model of computation, concepts of worst case, best case and average case time.
2	-	-	1 hr	Chapter 2 & 3 of T1 ~~[ Lecture Slide ]~~	Necessity of the asymptotic notations; Different asymptotic notations: Definitions, interpretations and examples.
3	-	-	1 hr	Chapter 4 of T1 ~~[ Lecture Slide ]~~	Recurrence relation: Definition, solution of a recurrence relation, significance; Solving recurrence relation using substitution method.
4	-	-	1 hr	Chapter 4 of T1 ~~[ Lecture Slide ]~~	Recurrence relation: Soving recurrence relation by recurrence tree method; Analyzing code fragments.
5	-	-	1 hr	Exercise 2.1.3 and 2.3.5 of T1 ~~[ Lecture Slide ]~~	Divide and Conquer: Binary Search (Algorithm, example and worst case complexity analysis).
6	-	-	1 hr	Class notes ~~[ Lecture Slide ]~~	Divide and Conquer: Ternary Search (Algorithm, example and worst case complexity analysis).
7	-	-	1 hr	Chapter 7 of T1 (Refer the class note)	Divide and Conquer: Quick sort (Idea, Partition procedure, example of partition procedure).
8	-	-	1 hr	Chapter 7 of T1 (Refer the class note)	Divide and Conquer: Quick sort (Complexity of partition procedure, Worst case and best case complexity of quick sort).
9	-	-	1 hr	Chapter 7 of T1 (Refer the class note)	Divide and Conquer: Quick sort (Average case time complexity of quick sort).
10	-	-	1 hr	Chapter 6 of T1 [ Class note ]	Heap sort: Definition, Properties, Basic building blocks to develop the heap sort algorithm
11	-	-	1hr	Chapter 6 of T1 [ Class note ]	Heap sort: Heapify, Build heap, Heap sort, Examples
12	-	-	1hr	Chapter 6 of T1 [ Class note ]	Heap sort: Complexity analysis of Heapify, Build heap, Heap sort
13	-	-	1hr	Chapter 4 of T1 [ Class note ]	The Master Method: Basic and generalized master method, examples; Basic concept of lower bound for sorting
14	-	-	1hr	Chapter 8 of T1 [ Class Note ]	Lower bound for Sorting: Detailed analysis and derivation
15	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Elements of dynamic programming, Matrix chain multiplication - problem statement explanation through an example
16	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Matrix chain multiplication: Developing the recursive solution and idea behind memoization
17	-	-	1hr	Chapter 15 of T1 [ Class Notes ]	Dynamic Programming: Matrix chain multiplication: Developing Algorithm, Complexity Analysis, Example
18	-	-	2hrs	Chapter 15 of T1 ~~[View class note]~~	Dynamic Programming: Longest Common Subsequence: Problem statement, Solution approach, Developing algorithm, Complexity analysis, Example
19	-	-	1hr	Chapter 16 of T1 ~~[View class note]~~	Greedy Paradigm: Elements of Greedy paradigm, Fractional Kanpsack: Problem statement, Example, Building solution, algorithm, Complexity
20	-	-	1hr	Chapter 16 of T1 ~~[View class note]~~	Greedy Paradigm: Huffman Codes: Problem statement, Example, Building solution, algorithm, Complexity
21	-	-	1hr	Chapter 16 of T1 ~~[View class note]~~	Greedy Paradigm: Activity Selection: Problem statement, Example, Building solution, algorithm, Complexity
22	-	-	1hr	Chapter 21 of T1 ~~[Lecture Slide]~~	Data Structure for Disjoint Sets: Definition, Basic Operations, Representation, Application: connected component
23	-	-	1hr	~~[View class note]~~	Graphs and their representation
24	-	-	1hr	Chapter 22 of T1 ~~[View class note]~~	Graph Traversal: Breadth First Search (BFS) Problem statement, Algorithm, Complexity, Example
25	-	-	1hr	Chapter 22 of T1 ~~[View class note]~~	Graph Traversal: Depth First Search (DFS) Problem statement, Algorithm, Complexity, Example
26	-	-	1hr	Chapter 23 of T1 ~~[View class note]~~	MST: Prim’s algorithm, Example, Complexity
27	-	-	1hr	Chapter 23 of T1 ~~[View class note]~~	MST: Kruskal’s algorithm, Example, Complexity
28	-	-	3hrs	Chapter 24 of T1 ~~[View class note]~~	Single Source Shortest Path: Bellman-Ford Algorithm, Example, Complexity; Dijkstra’s Algorithm, Example, Complexity
29	-	-	2hrs	Chapter 25 of T1 ~~[View class note]~~	All pair Shortest Path: Floyd-Warshall’s Algorithm, Example, Complexity
30	-	-	2hrs	Chapter 32 of T1 ~~[View class note]~~	String Matching: Problem statement, Preliminary Idea, Naive algorithm, Example, complexity of naive algorithm; Rabin-Karp Method: Basic idea, Mathematical background, Horner’s rule, Polynomial evalution; Algorithm, Complexity, Example
31	-	-	2hrs	Chapter 34 of T1 ~~[View class note]~~	Complexity Classes: P, NP, NP Complete Definition reduction, NP complete problems
32	-	-	1hr	Chapter 35 of T1 ~~[View class note]~~	Handling NP complete problems: Approximation algorithms (Introduction, Definition, significance)
33	-	-	1hr	Chapter 35 of T1 ~~[View class note]~~	Handling NP complete problems: Vertex cover problem (2 - Approximation algorithm, Example, complexity)
34	-	-	1hr	Chapter 35 of T1 ~~[View class note]~~	Handling NP complete problems: TSP (2 - Approximation algorithm, Example, complexity analysis)

Obligatory Links 👍

P vs NP ‼ Did they Solve it 😲😲❓ [ Click here ] to check the list.
Spend some time at the complexity zoo. [ Enter the zoo ]. Your 📸 is of no use here 😜 (excuse the pun).