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 ( ≈ 3 hrs per Week)

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

Day → Details ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
Week 01	21/12/2020 11:10 to 12:10	22/12/2020 11:10 to 12:10	23/12/2020 09:00 to 10:00	-	-	-	-
Week 02	28/12/2020 11:10 to 12:10	29/12/2020 11:10 to 12:10	30/12/2020 09:00 to 10:00	-	-	-	-
Week 03	04/01/2021 11:10 to 12:10	05/01/2021 11:10 to 12:10	06/01/2021 09:00 to 10:00	-	-	-	-
Week 04	11/01/2021 11:10 to 12:10	12/01/2021 11:10 to 12:10	13/01/2021 09:00 to 10:00	-	-	-	-

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.

Assignments

TO BE UPLOADED AFTER COMPLETION OF THE FIRST MODULE!!

Course Progress and Resources

[ Not an updated list ]

Class No	Date	Time	Duration	ReadingList / Resources	Contents Discussed
1	21/12/2020	11:10 am	1 hr	Chapter 1 of T1	Overview of the course, motivation and introduction
2	22/12/2020	11:10 am	1 hr	Chapter 2 & 3 of T1	RAM model of computation, concepts of worst case, best case and average case time
3	23/12/2020	09:00 am	1 hr	Chapter 3 of T1	Need of Asymptotic notation, Different asymptotic notations: Definitions, interpretations and examples
4	28/12/2020	11:10 am	1 hr	Chapter 4 of T1 (Refer the second edition of the book)	Recurrence relation: Definition, significance; Solving recurrence relation using substitution method
5	29/12/2020	11:10 am	1 hr	Chapter 4 of T1 (Refer the second edition of the book)	Solving recurrence relation using recurrence tree method: Approach, solving examples, Deriving relations of code segments and examples
6	30/12/2020	09:00 am	1 hr	Exercise 2.1.3 and 2.3.5 of T1	Divide and Conquer: Genereal Structure, Binary Search (Algorithm, example and worst case complexity analysis, Extending the idea to ternary search
7	04/01/2021	11:10 am	1 hr	Section 2.3 of T1	Divide and Conquer: Merge sort (Problem Statement), Merge Procedure (example), Merge sort algorithm, worst case analysis and explanation
8	05/01/2021	11:10 am	1 hr	Chapter 7 of T1	Divide and Conquer: Quick sort: Idea, Partition procedure, example, Complexity of partition procedure, Worst case and best case analysis
9	06/01/2021	09:00 am	1 hr	Class notes	Divide and Conquer: Quick sort: Average case analysis of quicksort, How to avoid the worst case scenario in quicksort
10	11/01/2021	11:10 am	1 hr	Chapter 7 of T1 [ Class note ]	Heap sort: Definition, Properties, height of a n-element heap, basic building block of the heap sort algorithm