ADA MTech

Algorithm Design and Analysis (Nov-Feb, 2020)

Instructor Details

Name: AJAYA KUMAR DASH
Email:
@Office:
- 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.
R6. The algorithm design manual, Second Edition, by Steven S. Skiena, Springer-Verlag London Limited.

Evaluation

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

Assignments

To be Declared

Course Progress and Resources

Some fundamental Research Articles
- To be updated
Course Progress

[ Not an updated list ]

Serial No			Reading List	Topics Discussed
1	04/11/2020	1hr	-	Overview of the course, motivation and introduction
2	06/11/2020	1hr	[T1] Chapter 2 & 3	Model of computation, concepts of worst case, best case and average case time, Asymptotic notations (Definitions, interpretations)
3	09/11/2020	1hr	[T1] Chapter 4 (Refer the second edition of the book)	Recurrence relation: Definition, significance; Solving recurrence relation using substitution method
4	11/11/2020	1hr	[T1] Chapter 4 (Refer the second edition of the book)	Solving recurrence relation using recurrence tree method: Approach, solving examples
5	13/11/2020	2hrs	[T1] Chapter 7 (Refer the second edition of the book)	Divide and Conquer: Quick sort: Idea, Partition procedure, example, Complexity of partition procedure, Worst, best and average case analysis
5	18/11/2020	2hrs	Class Notes (Google meet recording)	Divide and Conquer: Binary search(Problem statement, algorithm, complexity), extend binary search idea to ternary search, comparision between binary and ternary search algorithms
6	09/12/2020	1hr	[T1] Chapter 8 (Section 8.1)	Lower bound for sorting (problem statement, mathematical proof)
7	09/12/2020	1hr	[T1] Chapter 30 (Section 30.1)	Polynomials and FFT: Representation of polynomials (coefficient vs point-value), addition, multiplication, evaluation and interpolation of polynomials
8	14/12/2020	1hr	[T1] Chapter 30 (Section 30.2, 30.3)	Polynomials and FFT: Basics of complex number, roots of unity, properties of roots of unity, building FFT algorithm (D&C approach), complexity analysis
9	16/12/2020	1hr	[T1] Chapter-15 (Section 15.3)	Dynamic Porgramming: Elements of dynamic programming, principle of optimality, advantage of memoization in dynamic programming through example
10	18/12/2020	1hr	[T1] Chapter-15 (Section 15.2)	Dynamic Porgramming: Matrix chain multiplication - problem statement explanation through an example, developing the recursive solution, algorithm, complexity analysis, example
11	21/12/2020	2hrs	[T1] Chapter-15 (Section 15.4)	Dynamic Programming: Longest Common Subsequence: Problem statement, solution approach, developing algorithm, complexity analysis, example
12	28/12/2020	1hr	[T1] Chapter-16 (Section 16.2)	Greedy Approach: Elements of Greedy strategy, Activity Selection (Problem statement, developing the dynamic programming solution, complexity of dynamic programming based activity selector)
13	01/01/2021	1hr	[T1] Chapter-16 (Section 16.1, 16.2)	Greedy Approach: Elements of Greedy strategy, Activity Selection (Problem statement, developing the dynamic programming solution, complexity of dynamic programming based activity selector)
14	04/01/2021	2hrs	[T1] Chapter-16 (Section 16.1, 16.2)	Greedy Approach: Greedy activity selector (selection of greedy criteria, validate greedy criteria for optimal solution using mathematical proof, algorithm, analysis, example)
15	06/01/2021	1hr	Class Notes (Google meet recording)	Greedy Approach: Knapsack problem(fractional and 0-1 knapsack problem, selection of greedy criteria for fractional knapsack, greedy algorithm, dynamic programming solution of 0-1 knapsack, complexity analysis)
16	08/01/2021	2hrs	[T1] Chapter-6	Heap sort: Definition of heap, properties, basic building blocks to develop the heap sort algorithm, developing heapify algorithm, example to check the heapify procedure