Instructor: **Balasubramanian Raman**

Office:**S-227, CSE Building**

Class Meeting Time:** Tuesdays (11:05 am -12 noon), Wednesdays and Fridays (12:05-1:00 p.m).**

Class Room:** Microsoft Teams**

Office Hours:** Mondays, Thursdays 11:00 a.m. - 1:00 p.m. ** and ** by appointment **

TAs:** Puneet Kumar and Phoolpreet**

Email:** first four letters of first name at cs dot ac dot in**

Office:

Class Meeting Time:

Class Room:

Office Hours:

TAs:

Email:

November 15, 2021: End Term Examination.

November 15, 2021: Suprize Quiz 3 marks have been posted in MS Teams.

November 12, 2021: Quiz 3 has been conducted.

November 03, 2021: Assignments 6 and 7 have been posted.

November 03, 2021: Suprize Quiz 2 marks have been posted in MS Teams.

October 23, 2021: Suprise Quiz 2 has been conducted.

October 18, 2021: Assignment 5 has been posted.

September 24, 2021: MTE marks have been uploaded

September 24, 2021: MTE Solutions have been uploaded

September 20, 2021: Mid-Term Examination.

September 15, 2021: Suprize Quiz 1 marks have been posted in MS Teams.

September 13, 2021: Assignment 4 has been posted.

September 06, 2021: Assignment 3 has been posted.

September 03, 2021: Suprise Quiz 1 has been conducted.

August 23, 2021: Assignment 2 has been posted.

August 09, 2021: Assignment 1 has been posted.

August 09, 2021: Tutorials have begun.

July 31, 2021: Classes have begun.

To introduce advanced concepts in data structures and algorithms. The topics covered will be similar to those found in introductory data structures and algorithms courses in computer science departments across the world: sorting and searching algorithms, categorising efficiency in time and memory use, linked list and tree data structures, hash tables, stacks and queues. Then advance topics like Divide and Conquer, Greedy Algorithms, Dynamic Programming and Back Tracking algorithms and Graph algorithms will be addressed. The objectives are that you should know something of all of these by the end of the course. As well as knowing about them, you should be familiar enough with the concepts that should you need to take any of them further and make use of them, you will be able to do so.

**Prerequisites:** NIL.

- Term tests/quizzes (10%)
- Assignments (10%)
- Class participation (5%)
- Mid-Term Examination (25%)
- End Term Examination (50%)

02. Introduction to Data Structures and Time Complexity (03/08/2021)

03. Time Complexity (04/08/2021)

04. Asymtotic notations in Time Complexity (06/08/2021)

05. More on Time Complexity with examples (10/08/2021)

06. Space Complexity with examples (11/08/2021)

07. Linear Lists (13/08/2021)

08. More on Linear Lists (17/08/2021)

09. One Dimensional Array (18/08/2021)

10. More on One Dimensional Arrays (24/08/2021)

11. Arrays and Pointers (25/08/2021)

12. Two Dimensional Arrays (27/08/2021)

13. Character Arrays and Sorting Algorithms (31/08/2021)

14. Linked Lists (01/09/2021)

15. Dictionary Operations on Linked List (02/09/2021, Extra Class)

16. Surprise Quiz 1 , Solution (03/09/2021)

17. Circular Linked List, Doubly Linked List and Merge Sort (04/09/2021)

18. Merge Sort Analysis, Quick sort and its Analysis (07/09/2021)

19. Radix sort and Introduction to Stacks (08/09/2021)

20. Recursive function using Stack and Stack Operations (14/09/2021)

21. Towers of Hanoi, infix, prefix and post fix operations (15/09/2021)

22. Infix to Postfix (17/09/2021)

23. Infix to Prefix and Stack implementation using Linked List (28/09/2021)

24. Linked Stack Operatons, Queues and Circular Queues (29/09/2021)

25. Linked Queues, Circular Linked Queues, Finding path in maze, N-Queens Problem, Introduction to Trees (01/10/2021)

26. Binary Trees (05/10/2021)

27. Binary Search Trees (06/10/2021)

28. Binary Search Tree Insertion and Deletion, Max heap, Min heap, Priority Queue (07/10/2021, Extra Class)

29. Heap Sort and Randomized Binary Search algorithm and analysis (08/10/2021)

30. Dynamic Programming: Fibonacci numbers, Memoization (Top Down), Tabulation (Bottom up), Knapsack 0-1 Problem-Tabulation (Bottom up) (12/10/2021)

31. Dynamic Programming: Knapsack 0-1 Problem-Memoization (Top Down), Greedy Algorithms: Fractional Knapsack (13/10/2021)

32. Divide and Conquer Algorithms: Randomized Quick Sort, Strassen's Matrix multiplication (14/10/2021, Extra Class)

33. Optimal Binary Search Tree (20/10/2021)

34. 0-1 Knapsack problem using Branch and Bound, N-Queens Problem using backtracking (21/10/2021, Extra Class)

35. Introduction to Graphs (22/10/2021)

36. Surprise Quiz 2 , Solution (23/10/2021)

37. More on Graphs, Representation of Graphs and Eigenvalues of Graphs (26/10/2021)

38. Dijkstra's Shortest Path Problem, Krushkal's Algorithm, Prim's Algorithm and DFS (27/10/2021)

39. BFS and Travelling Salesman Problem (29/10/2021)

40. Topological Sort by Kahn's Algorithm and by DFS (02/11/2021)

41. Sollin's algorithm for MST, P and NP Complexity Classes (03/11/2021)

42. NP Complete and NP Hard Complexity Classes (09/11/2021)

43. Quiz 3, Solution (12/11/2021)

02. Assignment 2 (Posted on 23/08/2021, due on 06/09/2021)

03. Assignment 3 (Posted on 06/09/2021, due on 04/10/2021)

04. Assignment 4 (Posted on 13/09/2021, due on 18/10/2021)

05. Assignment 5 (Posted on 18/10/2021, due on 08/11/2021)

06. Assignment 6 (Posted on 02/11/2021)

07. Assignment 7 (Posted on 02/11/2021)

- There will be five to eight assignments.
- Late assignments will be accepted, with a 10% penalty per day, up to five days.
- Submission procedure and other requirements will be stated in individual assignments.
- Students are responsible for backing up and protecting their work.

02. Mid Term Examination (Held on 20/09/2021, 12:00 noon to 1:30 pm), Solution (24/09/2021)

03. Surprise Quiz 2 , Solution (23/10/2021)

04. Quiz 3 , Solution (12/11/2021)

05. End Term Examination (Held on 15/11/2021, 2:30 to 5:30 pm) Solution (22/11/2021)

1. Sahni, S., "Data Structures, Algorithms, and Applications in C++", WCB/McGraw-Hill. (Latest Edition)

2. Wirth, N., "Algorithms and Data Structures", Prentice-Hall of India, 2017.

3. Cormen T, Leiserson C, Rivest R, and Stein C., "Introduction to Algorithms", MIT Press, 2009.