2023 DAA(BTech) Course Page

Design and Analysis of Algorithms (DAA), August - December 2023

Instructor Details

Name: Ajaya Kumar Dash
Email:
Address:
- (Most likely) AR Lab, 1st Floor, C-Block, IIIT Bhubaneswar
- CB-51, Faculty chambers, IIIT Bhubaneswar

Class schedule ( ≈ 4 hrs per Week)

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
CSE-A (C 114)	09:00 am ~~02:00 pm~~	12:00 pm	-	11:00 am	12:00 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

You can find the DAA theory and lab 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/Homeworks

Assignmen/Homework 01
- Due Date: ~~25-09-2023~~ ~~29-09-2023 ( 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 STUDENTID_hw_sol_01_DAA2023.pdf (Strictly follow this naming convention)
  - Use your official mail id provided by IIIT Bhubaneswar to upload the file using google form.
  - Submission link [Click Here]

Course Progress and Resources

Sl No #	Date	Time	Duration	Reading List and Resources	Contents Discussed
1	22/08/23	12:00	1 hr	Chapter 1 of T1 [ Lecture Slide ]	Course overview; Introduction to DAA; Tools for algorithm analysis: RAM model of computation, concepts of worst case, best case and average case time.
2	28/08/20	02:00	1 hr	Chapter 2 & 3 of T1 [ Lecture Slide ]	Concept of asymptotic notations; Asymptotic notations: Definitions, interpretations and examples.
3	31/08/23	11:00	1 hr	Chapter 4 of T1 [ Lecture Slide ]	Recurrence relations: Definition, Interpretation of the solution of a recurrence relation; Solving recurrence relations using substitution (iterative) method.
4	01/09/23	12:00	1 hr	Chapter 4 of T1 [ Lecture Slide ]	Soving recurrence relation by recurrence tree method; Analyzing code fragments.
5	04/09/23	9:00	1 hr	Exercise 2.1.3 and 2.3.5 of T1 [ Lecture Slide ]	Genereal Structure of divide and conquer approach; Binary Search (problem statement, algorithm, example and analysing the worst case complexity).
6	07/09/23	11:00	1 hr	Class notes [ Lecture Slide ]	Ternary Search (problem statement, algorithm, example and analysis of worst case complexity); Comparision of binary and ternary search algorithms.
7	08/09/23	12:00	1 hr	Chapter 2.3 of T1 [ Lecture Slide ]	Merge sort (problem Statement), merge procedure (example), worst case analysis of merge sort.
8	11/09/23	09:00	1 hr	Chapter 7 of T1 [ Lecture Slide ]	Divide and Conquer: Quick sort: Idea, Partition procedure, example, Complexity of partition procedure
9	12/09/23	12:00	1 hr	Chapter 7 of T1 [ Class note ]	Divide and Conquer: Quick sort: Complexity Analysis (Worst, best and average case)
10	14/09/23	11:00	1hr	Class Notes	Divide and Conquer: Strassen’s matrix multiplication, Complexity analysis
11	15/09/23	12:00	1 hr	Chapter 6 of T1 [ Class note ]	Heap sort: Definition, Properties, Basic building blocks to develop the heap sort algorithm
12	18/09/23	09:00	1hr	Chapter 6 of T1 [ Class note ]	Heap sort: Heapify, Build heap, Heap sort, Examples
13	21/09/23	11:00	1hr	Chapter 6 of T1 [ Class note ]	Heap sort: Complexity analysis of Heapify, Build heap, Heap sort; Priority queue
14	22/09/23	12:00	1hr	Chapter 4 of T1 [ Class note ]	The Master Method: Basic and generalized master method, examples; Basic concept of lower bound for sorting
15	26/09/23	12:00	1hr	Chapter 8.1 of T1 [ Class Note ]	Lower bound for Sorting: Detailed analysis and derivation
16	28/09/23	11:00	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Elements of dynamic programming, Matrix chain multiplication - problem statement explanation using an example
17	10/10/23	12:00	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Matrix chain multiplication: Developing the recursive solution and idea behind memoization
18	12/10/23	11:00	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Matrix chain multiplication: Developing Algorithm, Complexity Analysis, Example
19	13/10/23	12:00	1hr	Chapter 15 of T1 [ Class Note ]	Dynamic Programming: Longest Common Subsequence: Problem statement, Solution approach, Developing algorithm, Complexity analysis, Example
20	16/10/23	09:00	1hr	Chapter 16 of T1 [ Proof ]	Greedy Paradigm: Elements of Greedy paradigm, Fractional Kanpsack: Problem statement formulation, Example, Building solution
21	16/10/23	12:00 (Extra)	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Fractional Kanpsack: algorithm, Complexity; 0-1 Knapsack failure with greedy, (Optional) Dynamic programming solution of 0-1 knapsack
22	17/10/23	12:00	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Huffman Codes: Problem statement, Example, Applications of Huffman code
23	19/10/23	09:00	1hr	Chapter 16 of T1 [ Class Note ]	Greedy Paradigm: Building the solution idea of Huffman Code, algorithm, complexity analysis
24	30/10/23	12:00	1hr	Chapter 16 of T1 [ Proof ]	Greedy Paradigm: Activity selection (Problem statement, description of the greedy criteria, developing the greedy algorithm, solving an example)
25	31/10/23	12:00	1hr	Chapter 21 of T1 [ Lecture Slide ]	Data Structure for Disjoint Sets: Definition, Basic Operations, Linked-list representation of disjoint sets
26	02/11/23	11:00	1hr	[ Lecture Slide ]	Graphs and their representations
27	06/11/23	09:00	1hr	Chapter 22 of T1 [ Lecture Slide ]	Graph Traversal: Breadth First Search (BFS) Problem statement, Algorithm, Complexity, Example
28	07/11/23	12:00	1hr	Chapter 22 of T1 [ Lecture Slide ]	Graph Traversal: Depth First Search (DFS) Problem statement, Algorithm, Complexity, Example
29	09/11/23	11:00	1hr	Chapter 23 of T1 [ Lecture Slide ]	MST: Kruskal’s algorithm, Example, Complexity
30	10/11/23	12:00	1hr	Chapter 23 of T1 [ Lecture Slide ]	MST: Prim’s algorithm, Example, Complexity
31	13/11/23	12:00	1hr	Chapter 24 of T1 [ Lecture Slide ] [ Class Note ]	Single Source Shortest Path: Bellman-Ford Algorithm, Example, Complexity
32	14/11/23	12:00	1hr	Chapter 24 of T1 [ Lecture Slide ]	Single Source Shortest Path: Dijkstra’s Algorithm, Example, Complexity
33	17/11/23	12:00	1hr	Chapter 25 of T1 [ Lecture Slide ]	All pair Shortest Path: Floyd-Warshall’s Algorithm, Example, Complexity
34	17/11/23	05:30	1hr	Online Mode	QUIZ Test
35	20/11/23	02:00	1hr	Chapter 34 of T1 [ Refer class 36 ]	Complexity Classes: P, NP, NPC basic idea, intractable vs tractable problems, optimization vs decision problems, definition of P class, examples of P class problems
36	21/11/23	12:00	1hr	Chapter 34 of T1 [ Lecture Slide ]	Complexity Classes: NP hard, NP complete, co-NP classes, polynomial time reduction and its significance, relationship between P, NP, NPC, NP-hard, co-NP
37	23/11/23	11:00	1hr	Chapter 35 of T1 [ Lecture Slide ] [ Lecture Slide ]	Handling NP complete problems: Idea of approximation algorithms, approximation ratio, 2-approximation algorithms for Vertex cover and Euclidean TSP, examples
38	25/11/23	10:15	1hr	Chapter 32 of T1 [ Lecture Slide ]	String Matching: 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
39	25/11/23	11:15	1hr	Chapter 30 of T1 [ Refer class 40 ]	FFT: Polynomial addition, multiplication, evaluation; coefficient vs point-value representaion of polynomials and basic operations,
40	25/11/23	12:15	1hr	Chapter 30 of T1 [ Lecture Slide ]	FFT: 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