AID-525 Data Structures and Algorithms
Autumn 2021-22
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
Announcements
November 29, 2021: Grades Displayed.
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.
Course Objectives, Learning Outcomes and Prerequisites
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.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (10%)
- Class participation (5%)
- Mid-Term Examination (25%)
- End Term Examination (50%)
Note: Assignments may require strong programming skills. You can choose C++ or JAVA.
Lecture Notes
01. Introduction to Data Structures and Algorithms (31/7/2021)
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)
Assignments
01. Assignment 1 (Posted on 09/08/2021, due on 19/08/2021 except last problem)
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.
Examinations
01. Surprise Quiz 1 , Solution (03/09/2021)
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)
Recommended Study Material
The following will be used as a reference/text book for this course:
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.
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: 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
Announcements
November 29, 2021: Grades Displayed.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.
Course Objectives, Learning Outcomes and Prerequisites
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.
Prerequisites: NIL.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (10%)
- Class participation (5%)
- Mid-Term Examination (25%)
- End Term Examination (50%)
Lecture Notes
01. Introduction to Data Structures and Algorithms (31/7/2021)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)
Assignments
01. Assignment 1 (Posted on 09/08/2021, due on 19/08/2021 except last problem)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.
Examinations
01. Surprise Quiz 1 , Solution (03/09/2021)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)
Recommended Study Material
The following will be used as a reference/text book for this course: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.