CSC-102 Data Structures
Spring 2023-24
Instructor: Balasubramanian Raman
Office: S-227, CSE Building
Class Meeting Time: Mondays, Tuesdays and Thursdays (5-6 pm).
Class Room: Gargi Block 102
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: Dr. Pradeep Singh (pradeep.cs at sric) (Post Doc), Anshul Pundhir (anshul_p at cs), Deepak Kumar (d_kumar at cs)(PhD students), Priyal Jain and Piyush Dhamdhere (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Announcements
February 12, 2024: Surprise Quiz held.
January 17, 2024: Practical classes have begun.
January 04, 2024: Classes have begun.
Course Objectives, Learning Outcomes and Prerequisites
To understand the basic concepts of data structures, including arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
To Analyze the time and space complexity of different data structures and operations.
To Choose the appropriate data structure for a given problem or application.
To Implement basic data structures in a chosen programming language (e.g., C++).
Course Outcomes:
After completing the course you will be able to:
explain and differentiate between various data structures like arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
calculate the time and space complexity of operations like insertion, deletion, and searching for different data structures, allowing you to choose the optimal structure for specific tasks.
recognize how certain algorithms rely on specific data structures for efficient operation and be able to analyze the impact of the chosen structure on the algorithm's performance.
understand how data structures are used in various domains like operating systems, database systems, compilers, computer graphics, artificial intelligence, and more.
Prerequisites: Programming Language.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (15%)
- Class participation (5%)
- Mid-Term Examination (30%)
- End Term Examination (40%)
Note: Assignments may require strong programming skills. You can choose C++.
Lecture Notes
01. Introduction to Data Structures (08/01/2024)
02. Asymptotic Notations in Time Complexity: Big O and Big Omega notations (09/01/2024)
03. Asymptotic Notations in Time Complexity: Big Theta, Small o and Small omega notations with practical examples (11/01/2024)
04. Space Complexity and Introduction to Linear Lists (15/01/2024)
05. Problems on Time Complexity and
Solution to last problem (16/01/2024)
06. Linear list and One Dimesional Arrays (18/01/2024, Extra Class: 9-10 AM)
07. More on One Dimesional Arrays (18/01/2024)
08. More on 1D Array and Introduction to Two Dimensional Arrays (22/01/2024)
09. More on Two Dimensional Arrays and Selection Sort (23/01/2024)
10. Bubble Sort and the Introduction to Linked list (25/01/2024)
11. Linked list: Insertion and Deletion Operations, Cicular linked list, Circular linked list with header node and Doubly linked list (29/01/2024)
12. Doubly linked list: Insertion, Merge Sort and Quick Sort (30/01/2024)
13. Quick Sort, Radix Sort, Introduction to Stacks (01/02/2024)
14. Stack Operations, Postfix to Infix using Stacks (05/02/2024)
15. Infix to Postfix, Infix to Prefix, Linked Stack and Introduction to Queues (06/02/2024)
16. Queues, Circular Queues and Linked Queues (09/02/2024)
17. Quiz, Solution (12/02/2024)
18. Practice Problems (13/02/2024)
19. Radix Sort using Linked List and Hashing (19/02/2024)
20. Hashing and LZW algorithm (04/03/2024)
21. LZW algorithm and Introduction to Binary Trees (05/03/2024)
22. Complete Binary Tree, Linked Binary Trees and Binary Search Trees (07/03/2024)
23. Binary Search Trees: Find, Insertion and Deletion algorithms, Max and Min heap (11/03/2024)
24. Construction of Max heap, Priority Queue and Heap Sort (12/03/2024)
25. Leftist Trees (14/03/2024)
26. Huffman coding and Introduction to Tournament Trees (18/03/2024)
27. Surprise Quiz 2, Solution (19/03/2024)
28. Tournament Trees and Bin Packing Algorithm (21/03/2024)
29. Balanced Binary Tree: AVL (26/03/2024)
30. AVL Search Trees: Rotations (28/03/2024)
31. Red-Black Tree: Insertion (01/04/2024)
32. Red-Black Tree: Deletion and Introduction to M-Way Search Tree (02/04/2024)
33. B-Tree of Order m, Insertion Algorithm and the Introduction to Deletion Algorithm (08/04/2024)
34. B-Tree of Order m: Deletion Algorithm and Graph Data Structures (09/04/2024)
35. More on Graph Data Structures (10/04/2024)
36. Dijkstra's Shortest Path Problem, Krushkal's Algorithm, Prim's Algorithm, DFS and BFS (15/04/2024)
37. Problems on Graphs (16/04/2024)
38. Quiz 3 (18/04/2024)
39. Exception Handling in C++, Iterators, List in C++ STL, Skip list and Equivalence Problem (22/04/2024)
40. Sets and Multi sets in STL and Bucket/Bin Sort (23/04/2024)
Assignments
01. Assignment 1 (Posted on 17/01/2024, Deadline 31/01/2024), solution (Posted on 13/02/2024),
02. Assignment 2 (Posted on 24/01/2024, Deadline 14/02/2024)
03. Assignment 3 (Posted on 01/02/2024, Deadline 05/03/2024)
04. Assignment 4 (Posted on 09/02/2024, Deadline 12/03/2024)
05. Assignment 5 (Posted on 20/03/2024, Deadline 07/04/2024)
06. Practice Assignment 6 (Posted on 05/04/2024)
07. Practice Assignment 7 (Posted on 21/04/2024)
- 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. Quiz, Solution (12/02/2024)
02. MTE (24/2/2024), Solution (04/03/2024)
03. Surprise Quiz 2, Solution(19/3/2024)
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. Michael T. Goodrich, Roberto Tamassia, David M. Mount, "Data Structures and Algorithms in C++", Wiley, Latest edition.
3. Wirth, N., "Algorithms and Data Structures", Prentice-Hall of India, 2017.
4. Drozdek, A., "Data Structures and Algorithms in C++", Vikas Publishing House.
5. 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: Mondays, Tuesdays and Thursdays (5-6 pm).
Class Room: Gargi Block 102
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: Dr. Pradeep Singh (pradeep.cs at sric) (Post Doc), Anshul Pundhir (anshul_p at cs), Deepak Kumar (d_kumar at cs)(PhD students), Priyal Jain and Piyush Dhamdhere (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Office: S-227, CSE Building
Class Meeting Time: Mondays, Tuesdays and Thursdays (5-6 pm).
Class Room: Gargi Block 102
Office Hours: Wednesdays, Fridays 11:00 a.m. - 1:00 p.m. and by appointment
TAs: Dr. Pradeep Singh (pradeep.cs at sric) (Post Doc), Anshul Pundhir (anshul_p at cs), Deepak Kumar (d_kumar at cs)(PhD students), Priyal Jain and Piyush Dhamdhere (M.Tech students)
Email: first four letters of first name at cs dot ac dot in
Announcements
February 12, 2024: Surprise Quiz held.January 17, 2024: Practical classes have begun.
January 04, 2024: Classes have begun.
Course Objectives, Learning Outcomes and Prerequisites
To understand the basic concepts of data structures, including arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
To Analyze the time and space complexity of different data structures and operations.
To Choose the appropriate data structure for a given problem or application.
To Implement basic data structures in a chosen programming language (e.g., C++).
Course Outcomes:
After completing the course you will be able to:
explain and differentiate between various data structures like arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
calculate the time and space complexity of operations like insertion, deletion, and searching for different data structures, allowing you to choose the optimal structure for specific tasks.
recognize how certain algorithms rely on specific data structures for efficient operation and be able to analyze the impact of the chosen structure on the algorithm's performance.
understand how data structures are used in various domains like operating systems, database systems, compilers, computer graphics, artificial intelligence, and more.
Prerequisites: Programming Language.
To Analyze the time and space complexity of different data structures and operations.
To Choose the appropriate data structure for a given problem or application.
To Implement basic data structures in a chosen programming language (e.g., C++).
Course Outcomes:
After completing the course you will be able to:
explain and differentiate between various data structures like arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
calculate the time and space complexity of operations like insertion, deletion, and searching for different data structures, allowing you to choose the optimal structure for specific tasks.
recognize how certain algorithms rely on specific data structures for efficient operation and be able to analyze the impact of the chosen structure on the algorithm's performance.
understand how data structures are used in various domains like operating systems, database systems, compilers, computer graphics, artificial intelligence, and more.
Prerequisites: Programming Language.
Evaluation Components
- Term tests/quizzes (10%)
- Assignments (15%)
- Class participation (5%)
- Mid-Term Examination (30%)
- End Term Examination (40%)
Lecture Notes
01. Introduction to Data Structures (08/01/2024)02. Asymptotic Notations in Time Complexity: Big O and Big Omega notations (09/01/2024)
03. Asymptotic Notations in Time Complexity: Big Theta, Small o and Small omega notations with practical examples (11/01/2024)
04. Space Complexity and Introduction to Linear Lists (15/01/2024)
05. Problems on Time Complexity and Solution to last problem (16/01/2024)
06. Linear list and One Dimesional Arrays (18/01/2024, Extra Class: 9-10 AM)
07. More on One Dimesional Arrays (18/01/2024)
08. More on 1D Array and Introduction to Two Dimensional Arrays (22/01/2024)
09. More on Two Dimensional Arrays and Selection Sort (23/01/2024)
10. Bubble Sort and the Introduction to Linked list (25/01/2024)
11. Linked list: Insertion and Deletion Operations, Cicular linked list, Circular linked list with header node and Doubly linked list (29/01/2024)
12. Doubly linked list: Insertion, Merge Sort and Quick Sort (30/01/2024)
13. Quick Sort, Radix Sort, Introduction to Stacks (01/02/2024)
14. Stack Operations, Postfix to Infix using Stacks (05/02/2024)
15. Infix to Postfix, Infix to Prefix, Linked Stack and Introduction to Queues (06/02/2024)
16. Queues, Circular Queues and Linked Queues (09/02/2024)
17. Quiz, Solution (12/02/2024)
18. Practice Problems (13/02/2024)
19. Radix Sort using Linked List and Hashing (19/02/2024)
20. Hashing and LZW algorithm (04/03/2024)
21. LZW algorithm and Introduction to Binary Trees (05/03/2024)
22. Complete Binary Tree, Linked Binary Trees and Binary Search Trees (07/03/2024)
23. Binary Search Trees: Find, Insertion and Deletion algorithms, Max and Min heap (11/03/2024)
24. Construction of Max heap, Priority Queue and Heap Sort (12/03/2024)
25. Leftist Trees (14/03/2024)
26. Huffman coding and Introduction to Tournament Trees (18/03/2024)
27. Surprise Quiz 2, Solution (19/03/2024)
28. Tournament Trees and Bin Packing Algorithm (21/03/2024)
29. Balanced Binary Tree: AVL (26/03/2024)
30. AVL Search Trees: Rotations (28/03/2024)
31. Red-Black Tree: Insertion (01/04/2024)
32. Red-Black Tree: Deletion and Introduction to M-Way Search Tree (02/04/2024)
33. B-Tree of Order m, Insertion Algorithm and the Introduction to Deletion Algorithm (08/04/2024)
34. B-Tree of Order m: Deletion Algorithm and Graph Data Structures (09/04/2024)
35. More on Graph Data Structures (10/04/2024)
36. Dijkstra's Shortest Path Problem, Krushkal's Algorithm, Prim's Algorithm, DFS and BFS (15/04/2024)
37. Problems on Graphs (16/04/2024)
38. Quiz 3 (18/04/2024)
39. Exception Handling in C++, Iterators, List in C++ STL, Skip list and Equivalence Problem (22/04/2024)
40. Sets and Multi sets in STL and Bucket/Bin Sort (23/04/2024)
Assignments
01. Assignment 1 (Posted on 17/01/2024, Deadline 31/01/2024), solution (Posted on 13/02/2024),
02. Assignment 2 (Posted on 24/01/2024, Deadline 14/02/2024)
03. Assignment 3 (Posted on 01/02/2024, Deadline 05/03/2024)
04. Assignment 4 (Posted on 09/02/2024, Deadline 12/03/2024)
05. Assignment 5 (Posted on 20/03/2024, Deadline 07/04/2024)
06. Practice Assignment 6 (Posted on 05/04/2024)
07. Practice Assignment 7 (Posted on 21/04/2024)
- 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. Quiz, Solution (12/02/2024)
02. MTE (24/2/2024), Solution (04/03/2024)
03. Surprise Quiz 2, Solution(19/3/2024)
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. Michael T. Goodrich, Roberto Tamassia, David M. Mount, "Data Structures and Algorithms in C++", Wiley, Latest edition.
3. Wirth, N., "Algorithms and Data Structures", Prentice-Hall of India, 2017.
4. Drozdek, A., "Data Structures and Algorithms in C++", Vikas Publishing House.
5. Cormen T, Leiserson C, Rivest R, and Stein C., "Introduction to Algorithms", MIT Press, 2009.