DAA 2020 Course Page

Design and Analysis of Algorithm, January 2020

Instructor Details

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

Online Class schedule ( ≈ 4 hrs per Week )

Attention: Due to privacy concern, the meeting details will be posted inside the intranet(IIIT BBSR), notice board..

Day → Details ↓	Monday	Wednesday	Friday	Saturday	Sunday
Week 1	-	-	03/04/2020 5:00 pm	04/04/2020 5:00 pm	-
Week 2	-	08/04/2020 9:00 am	-	11/04/2020 5:00 pm	-
Week 3	-	15/04/2020 9:00 am	-	18/04/2020 5:00 pm	-
Week 4	-	22/04/2020 9:00 am	-	-	26/04/2020 5:00 pm
Week 5	27/04/2020 8:30 am	-	-	-	-

Note: Download zoom.us and register with your institute email.

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].

Course Forum

Visit [here] to register into the DAA course. Use your official email-id for the registration.

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

Assignments

Assignment 1
- Due Date: College reopen date + 2 days
- Download the questions [Link]
- Solution report format [Link]

Course Progress and Resources

Attention: Due to CoronaVirus outbreak, some of the classes will be taken online. (Class number 27 onwards)

Class No	Date	Time	Duration	ReadingList / Resources	Contents Discussed
1	07/01/2020	03:15 pm	1 hr	Chapter 1 of T1	Overview of the course, motivation and introduction
2	09/01/2020	09:15 am	1 hr	Chapter 2 & 3 of T1	RAM model of computation, concepts of worst case, best case and average case time
3	09/01/2020	10:15 am	1 hr	Chapter 3 of T1	Need of Asymptotic notation, Different asymptotic notations: Definitions, interpretations and examples
4	10/01/2020	02:15 pm	1 hr	Chapter 4 of T1 (Refer the second edition of the book)	Recurrence relation: Definition, significance; Solving recurrence relation using substitution method
5	14/01/2020	03:15 pm	1 hr	Chapter 4 of T1 (Refer the second edition of the book)	Solving recurrence relation using recurrence tree method: Approach, solving examples
6	-	-	1 hr	Class Notes	Deriving relations of code segments and examples
7	-	-	1 hr	Class Notes	Deriving relation of recursive procedures and TOH example, analysis
8	-	-	1 hr	Section 2.3 of T1	Divide and Conquer: Genereal Structure, Merge sort (Problem Statement), Merge Procedure (example)
9	-	-	1 hr	Section 2.3 of T1	Divide and Conquer: Merge sort worst case analysis and explanation
10	-	-	1 hr	Exercise 2.1.3 and 2.3.5 of T1	Divide and Conquer: Binary Search (Algorithm, example and worst case complexity analysis
11	-	-	1 hr	Chapter 7 of T1	Divide and Conquer: Quick sort: Idea, Partition procedure, example, Complexity of partition procedure
12	-	-	1 hr	Chapter 7 of T1 [ Class note ]	Divide and Conquer: Quick sort: Complexity Analysis (Worst, best and average case)
13	-	-	1hr	Class Notes	Divide and Conquer: Strassen’s matrix multiplication
14	-	-	1 hr	Chapter 7 of T1 [ Class note ]	Heap sort: Definition, Properties, Basic building blocks to develop the heap sort algorithm
15	-	-	1hr	Chapter 7 of T1 [ Class note ]	Heap sort: Heapify, Build heap, Heap sort, Examples
16	-	-	1hr	Chapter 7 of T1 [ Class note ]	Heap sort: Complexity analysis of Heapify, Build heap, Heap sort
17	-	-	1hr	Chapter 4 of T1 [ Class note ]	The Master Method: Basic and generalized master method, examples; Basic concept of lower bound for sorting
18	-	-	1hr	Chapter 8 of T1 [ Class Note ]	Lower bound for Sorting: Detailed analysis and derivation
19	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Elements of dynamic programming, Matrix chain multiplication - problem statement explanation through an example
20	-	-	1hr	Class Note	Surprise Interaction and Revision Module 1
21	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Matrix chain multiplication: Developing the recursive solution and idea behind memoization
22	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Matrix chain multiplication: Developing Algorithm, Complexity Analysis, Example
23	-	-	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Longest Common Subsequence: Problem statement, Solution approach, Developing algorithm, Complexity analysis, Example
24	-	-	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Elements of Greedy paradigm, Fractional Kanpsack: Problem statement, Example, Building solution, algorithm, Complexity
25	-	-	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Huffman Codes: Problem statement, Example, Building solution, algorithm, Complexity
26	-	-	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Activity Selection: Problem statement, Example, Building solution, algorithm, Complexity
27	-	-	1hr	Chapter 21 of T1 [Link]	Data Structure for Disjoint Sets: Definition, Basic Operations, Representation, Application: connected component
28	-	-	1hr	[Link]	Graphs and their representation
29	-	-	1hr	Chapter 22 of T1 [Lect 1][Lect 2][Link]	Graph Traversal: Breadth First Search (BFS) Problem statement, Algorithm, Complexity, Example
30	-	-	1hr	Chapter 22 of T1 [Link]	Graph Traversal: Depth First Search (DFS) Problem statement, Algorithm, Complexity, Example
31	-	-	1hr	Chapter 23 of T1 (refer class 32 notes)	MST: Kruskal’s algorithm, Example, Complexity
32	-	-	1hr	Chapter 23 of T1 [Link]	MST: Prim’s algorithm, Example, Complexity
33	-	-	1hr	Chapter 24 of T1 (refer class 34 notes)	Single Source Shortest Path: Bellman-Ford Algorithm, Example, Complexity
34	-	-	1hr	Chapter 24 of T1 [Link]	Single Source Shortest Path: Dijkstra’s Algorithm, Example, Complexity
35	-	-	1hr	Chapter 25 of T1 [Link]	All pair Shortest Path: Floyd-Warshall’s Algorithm, Example, Complexity
36	-	-	1hr	Chapter 32 of T1 [Link]	String Matching: Problem statement, Preliminary Idea, Naive algorithm, Example, complexity of naive algorithm
37	-	-	1hr	Chapter 32 of T1 (refer the slides of Class 36)	String Matching: Rabin-Karp Method: Basic idea, Mathematical background, Horner’s rule, Polynomial evalution
38	-	-	1hr	Chapter 32 of T1 (refer the slides of Class 36)	String Matching: Rabin-Karp Method: Algorithm, Complexity, Example
39	-	-	1hr	Chapter 34 of T1 [Link]	Complexity Classes: P, NP, NP Complete Definition reduction, NP complete problems
40	-	-	1hr	Chapter 35 of T1 [Link]	Handling NP complete problems: Approximation algorithms (Introduction, Definition, significance)
41	-	-	1hr	Chapter 35 of T1 [Link]	Handling NP complete problems: Vertex cover problem (2 - Approximation algorithm, Example, complexity)
42	-	-	1hr	Chapter 35 of T1 [Link]	Handling NP complete problems: TSP (2 - Approximation algorithm, Example, complexity analysis)