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, Fridaysdays 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@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

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)


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)


Examinations


01. Quiz, Solution (12/02/2024)
02. MTE (24/2/2024), Solution (04/03/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.