DAA 2019 Course Page

Design and Analysis of Algorithm, January 2019

Instructor Details

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

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

Assignments

Assignment 1 is Out !!
- ~~Due Date:~~ ~~25-Feb-2019~~

Course Progress and Resources

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