2024 DAA Course Page

Design and Analysis of Algorithms, August 2024 - November 2024

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- CG-19, Ground Floor, IIIT Bhubaneswar (Faculty chamber)
- Augmented Reality Lab, 1st Floor, C-Block, IIIT Bhubaneswar (Lab)

Branch-wise Class Schedule ( Weekly ≈ 4 hrs per Branch )

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
CS-A (C114)	10:30 am	12:30 pm	02:30 pm	02:30 pm	-	-	-
CS-B (C115)	12:30 pm	03:30 pm	-	11:30 am	02:30 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

Find the syllabus by visiting the Download link. [Download]

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

Assignment/Homework

Due Date: November 15, 2024 ( 5:00 pm )
- Questions: Submit the solution of all the homeworks given during the lecture.
- LaTeX submission template [ Link ]
- Learn LaTeX: Take the help of Youtube. You can find a number of quick start guide to LaTeX. Here is possibly a good one to follow. [Link]
- Submission instructions
  - Use the LaTeX typesetting to submit your solution.
  - Generate a .pdf file of the solution using the LaTeX template provided above.
  - The solution file must be a single .pdf containing all the answers and the naming convention of the file should be YourStudentID_hw_sol_DAA2024.pdf (Strictly follow this naming convention)
  - Use your official mail id provided by IIIT Bhubaneswar to upload the file using google form.
  - Read the instruction provided in the google form clearly before uploding your solution file.
  - Submission link for CS-A [CS-A Click Here]
  - Submission link for CS-B [CS-B Click Here]

Course Progress and Resources

👉 Attention: The lecture slides are not the replacement of books. The instructor is suggesting you to develop a habit of reading from the text/reference books.

Sl No #	Date	Time	Lecture Duration	Reading List and Resources	Contents Discussed
01	-	-	2.0 hrs	◦ Chapter 1 of T1 ◦ View Lecture Slide	Course overview, Pre-reqisites, Motivation, Informal introduction to DAA; Tools for algorithm analysis: RAM model of computation, concepts of worst case, best case and average case time.
02	-	-	1.0 hr	◦ Chapter 2 & 3 of T1 ◦ View Lecture Slide	Idea of asymptotic notations; Asymptotic notations: Definitions, interpretations, asymptotic relation among common functions, and examples.
03	-	-	1.0 hr	◦ Chapter 4 of T1 ◦ View Lecture Slide	Recurrence relations: Definition, Interpretation of the solution of a recurrence relation; Solving recurrence relations using substitution (iterative) method with examples
04	-	-	1.0 hr	◦ Chapter 4 of T1 ◦ View Lecture Slide	Soving recurrence relation by recurrence tree method; Analyzing the complexity of code fragments.
05	-	-	2.0 hrs	◦ Chapter 2.3 of T1 of T1 ◦ View Lecture Slide	Divide and Conquer: Genereal Structure of divide and conquer approach; Merge sort (Problem Statement), merge procedure (example), complexity analysis of merge process, merge sort algorithm, worst case analysis of merge sort.
06	-	-	1.0 hr	◦ Exercise 2.1.3 and 2.3.5 of T1 ◦ View Lecture Slide	Divide and Conquer: Binary and ternary Search (problem statement, algorithm, example and analysing the worst case complexity); (HW) Comparision of binary and ternary search algorithms.
07	-	-	2.0 hrs	◦ Chapter 7 of T1 ◦ View Lecture Slide	Divide and Conquer: Quick sort: Idea, Partition procedure, example, complexity of partition procedure, complexity analysis of quicksort (worst, best and average case)
08	-	-	1.0 hr	Refer class lecture	Divide and Conquer: Naive matrix multiplication revisited, matrix multiplication using divide & conquer approach, Strassen’s matrix multiplication, Complexity analysis
09	-	-	3.0 hrs	◦ Chapter 6 of T1 ◦ Refer class lecture	Heap sort: Definition, Properties, Basic building blocks and proofs to develop the heap sort algorithm; Heapify, Build heap, Heap sort with examples, complexity analysis of Heapify, Build heap, Heap sort; (Self-reading) Concepts of priority queue
10	-	-	1.0 hr	◦ Chapter 8.1 of T1 ◦ Refer class lecture	Lower bound for Sorting: Basic concept of lower bound for sorting, detailed analysis and mathematical derivation
11	-	-	1.0 hr	◦ Chapter 4 of T1 ◦ Refer class lecture	The Master Method: Basic and generalized master method mathematical expressions with examples
12	-	-	1.0 hr	◦ Chapter 15 of T1 ◦ Refer class lecture	Dynamic Programming: Necessary elements of dynamic programming, principle of optimality, idea of memoization using example; Matrix chain multiplication (MCM) - problem statement explanation using an example
13	-	-	1.0 hr	◦ Chapter 15 of T1 ◦ Refer class lecture	Dynamic Programming: Matrix chain multiplication: deriving mathematical expression of the recursive solution, developing algorithm, complexity analysis, example
14	-	-	1.0 hr	◦ Chapter 15 of T1 ◦ Refer class lecture	Dynamic Programming: Longest Common Subsequence: Problem statement, solution approach and deriving the mathematical expression, developing algorithm, complexity analysis, example
15	-	-	2.0 hrs	◦ Chapter 16 of T1 ◦ Refer class lecture ◦ Greedy criteria	Greedy Paradigm: Elements of Greedy paradigm; Fractional Kanpsack: Problem statement formulation, example, building solution on greedy criteria, algoritm and complexity analysis; 0-1 knapsak problem statement, failure of 0-1 knapsack with greedy, dynamic programming solution of 0-1 knapsack problem, complexity analysis
16	-	-	1.0 hr	◦ Chapter 16 of T1 ◦ Refer class lecture	Greedy Paradigm: Huffman Codes: Explanation of the problem statement, example, applications of Huffman code, building the solution idea of Huffman Code, algorithm, tracing the algorithm for an example, and complexity analysis
17	-	-	1.0 hr	◦ Chapter 16 of T1 ◦ Refer class lecture ◦ Greedy criteria	Greedy Paradigm: Activity selection problem statement formulation, description of the greedy criteria, developing the greedy algorithm, complexity analysis, solving an example
18	-	-	1.0 hr	◦ Chapter 21 of T1 ◦ View Lecture Slide	Data Structure for Disjoint Sets: Definition, Basic Operations, Linked-list representation of disjoint sets and operations with complexity analysis
19	-	-	1.0 hr	◦ View Lecture Slide	Graphs, basic terminologies, and graph representations
20	-	-	1.0 hr	◦ Chapter 22 of T1 ◦ View Lecture Slide	Graph Traversal: Breadth First Search (BFS) Problem statement, development of the algorithm, complexity analysis, example
21	-	-	1.0 hr	◦ Chapter 22 of T1 ◦ View Lecture Slide	Graph Traversal: Depth First Search (BFS) Problem statement, development of the algorithm, complexity analysis, example
22	-	-	1.0 hr	◦ Chapter 23 of T1 ◦ View Lecture Slide	MST (Greedy): Kruskal’s algorithm, complexity analysis, example
23	-	-	1.0 hr	◦ Chapter 23 of T1 ◦ View Lecture Slide	MST (Greedy): Prim’s algorithm, complexity analysis, example
24	-	-	1.0 hr	◦ Chapter 24 of T1 ◦ View Lecture Slide	Single Source Shortest Path: Basic terminologies, Bellman-Ford Algorithm, Example, Complexity analysis
25	-	-	1.0 hr	◦ Chapter 24 of T1 ◦ View Lecture Slide	Single Source Shortest Path: Dijkstra’s Algorithm, Example, Complexity analysis
26	-	-	1.0 hr	◦ Chapter 24 of T1 ◦ View Lecture Slide	All-pairs Shortest Path: Floyd-Warshall’s Algorithm, Example, Complexity analysis
27	-	-	2.0 hrs	◦ Chapter 34 of T1 ◦ View Lecture Slide	Complexity Classes: P, NP, NPC basic idea, intractable vs tractable problems, optimization vs decision problems, definition of P class, examples of P class problems, NP hard, NP complete, co-NP classes, polynomial time reduction and its significance, relationship between P, NP, NPC, NP-hard, co-NP
28	-	-	2.0 hrs	◦ Chapter 35 of T1 ◦ View Lecture Slide-1 ◦ Vertex cover example ◦ Approx. TSP	Handling NP-Complete Problems: Idea of approximation algorithms, approximation ratio, 2-approximation algorithms for Vertex cover and Euclidean TSP, examples
29	-	-	1.5 hrs	◦ Chapter 32 of T1 ◦ View Lecture Slide ◦ Slide video	String Matching: (Optional) 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
30	-	-	2.5 hrs	◦ Chapter 30 of T1 ◦ View Lecture Slide	Fast Fourier Transform: (Optional) Polynomial addition, multiplication, evaluation; coefficient vs point-value representaion of polynomials and basic operations, Fourier transform, DFT and inverse DFT to translate between polynomial representations, quick discussion on complex roots of unity; Divide and conquer algorithm of FFT, complexity analysis