Data Structures (2-1-1)

 

SPRING 2021-2022
Lecture: Wednesday (9:00 AM-11:00 PM); Lab : Monday (11:00 AM - 1:00 PM); Tut: Monday (3:00 PM - 5:00 PM)

Lectures/ Tut and Lab evaluation will be held physically

Announcements, Assignment submissions via Google Classroom

 

 

 

 

Course Objective:

The course introduces students to the logical and mathematical models of data organization. It also discusses different efficient data operations which the students would find useful while executing algorithms on data sets. In addition to the theoretical concepts, which help in problem solving, the course also aims at providing a practical knowledge of data structures so that the abstractions are made concerete. For all the data structures, the course follows a three step procedure - conceptualization, explaination and finally implementation using the C programming language as an implementation tool.

Course Outline:


Component / Unit Topics
C1 / Unit 1 Introduction - Basic Terminology, Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time and Space Complexity;
Asymptotic notations - Theta, Big-O, and Omega, Time-Space trade-off.
Arrays - Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Application of arrays, Sparse Matrices and their representations. Linked Lists - Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Header node based Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition, Generalized Linked List
Abstract Data Types (ADT) Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Recursion, Tower of Hanoi Problem, Simulating Recursion, Principles of recursion, Tail recursion, Removal of recursion Queues: Abstract Data Type, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Doubly Ended Queue.;
C1 / Unit 2 Searching - Sequential search, Binary Search, Comparison and Analysis;
Sorting - Internal Sorting: Bubble Sort, Selection Sort, Insertion Sort, Two Way Merge Sort, Heap Sort (to be discussed after Heaps), Quick Sort
C2 / Unit 1 Trees: Basic terminology, k-ary trees, Binary Trees, Binary Tree Representation: Array Representation and Linked Representation, Skew Binary Tree, Strict Binary Tree, Complete Binary Tree, Full Binary Tree, Binary Tree Traversals: In order, Preorder and Post order, Binary Search Trees, Threaded Binary trees, Traversing Threaded Binary trees, Forest, Expression Tree, Heaps, AVL tree, B Tree and B+ Tree. Priority Queues: Array based and Heap based
C2 / Unit 2 Hashing: Hash table, hash function, collison, collision resolution strategies - Direct Chaining, Open Addressing - Linear Probing and Quadratic Probing Graphs: Basic Terminology, Sequential and linked Representations of Graphs: Adjacency Matrix, Adjacency List, Graph Traversals: Depth First Search and Breadth First Search, Connected Components. Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm, single source shortest path-Dijkstra algorithm, Topological Sort.


 

 

Textbooks:

 

1.      Ellis Horowitz, Satraj Sahni and Susan Anderson-Freed, Fundamentals of Data Structures in C, W. H. Freeman and Company.

2.      Seymour Lipschutz , Data Structures, Schaum's Outlines Series, Tata McGraw-Hill.

3.      Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein , Data Structures Using C and C++, Prentice Hall of India.

4.      R. Kruse et al. , Data Structures and Program Design in C, Pearson Education.

References:

 

1.      Donald Knuth, The Art of Computer Programming, Volume 1 and 3, Addison-Wesley, Reading, Mass., 1973.

2.      Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, MIT Press.

3.      Ritchie and Kerningham, The C Programming Language,

4.      R. G. Dromey, How to Solve it by Computer, Prentice-Hall of India. .

5.      PDS notes @IIT KGP

 

 

 

 

Important Instructions:

1.         Classes will be conducted using slide presentation as well as chalk-board. Official slide sets and miscellaneous study materials from some of the main text books will be uploaded on the web site on a regular basis.

2.         The vehicular language for the course will be "C". All codes, assignments and lab exercises will be implemented in C language only.
.

3.         Every student is expected to have access to at least one of the text books .

4.         Attendance in the classes is mandatory. If the attendance of a student falls below 75%, he/she may will be dropped from the course after Component 2

5.         The course will consist of laboratory and take-home assignments, which has to be done very seriously. If a student does not submit the assignments, his/her grade will remain as incomplete.

6.         Grading Policy :

o   30%: Component 1 - Closed book exam (10%); Take home assignment (10%) and Lab assignment (10%)

o   30%: Component 2 - Closed book exam (10%); Take home assignment (10%) and Lab assignment (10%)

o   40%: Component 3 - Closed book written exam

7.         Take home assignments : They will be assigned at the beginning of a module (announcements will be made on the course web-site every week). These assignments will not only help you in development of an in-depth idea of each topic of the course but will also serve to prepare for your written examinations.
There will be two kinds of take home assignments :
(i) Homework assignments - To be done individually. These assignments need not be submitted but it is expected that the students complete them in order to have better understanding of the concepts covered in lecture sessions. Interact with your TAs during tutorial sessions to clear your doubts regarding the homework assignments.
(ii) Group Assignments - To be done in groups of four (max). These problems will be more harder problems involving rigorous mathematical/analytical treatement or implementation based assignments. Each Unit will have two such assignments which have to be completed within a given deadline and will be evaluated in each tutorial class.

8.         Tutorial Classes : The tutorial classes scheduled every week will have a dual role in the course. First they will serve as doubt clearing sessions where the TAs will interact with the students to clear their doubts and discuss the homework assignments. The second purpose of the tutorial classes would be to assess the understanding of the concepts though evaluation of the group assignments.

9.         The lab classes will mainly consist of implementation of programming concepts discussed in class and the assignments covered in tutorial sessions. Visit the Lab Page of the course website for details.

        

        

        

        

        

 

 

 

Lecture Slides:

The lecture slides have been prepared by consulting a number of books and online resources available on the internet. I would like to thank all the authors of all the sources from which the slides have been borrowed or consulted. Please note that the slides for each topic provide only a brief summary of the contents of a certain topic. They should not be treated as an alternative to books or class notes. Topics will be covered in more details in class and students are encouraged to consult textbooks and reference books for each topic.

-----------

Sl. No.

Topic

Homework Assignments (Practice Problems)

Tutorials / Resources


1.


Introduction

[ Slides ]



Homework Set 1

Recap : Introduction to Programming Using C



2.


Math Review

[ Slides ]



Homework Set 2



3.


Analysis of Algorithms

[ Slides ]





4.


Arrays-I

[ Slides ]


Arrays-II

[ Slides ]





5.


Structures in C

[ Slides ]


Linked List

[ Slides ]



Homework Set 3



[ Representing Polynomials ]




6.


Abstract Data Types - Stack and Queue

[ Slides ]


[ Video Lecture ]





Abstract Data Types




Stack and Queue




7.


Searching

[ Slides ]


[ Video Lecture ]



Homework Set 5



8.


Sorting

[ Slides ]


[ Video Lecture ]





9.


Efficient Sorting : Merge Sort and Quick Sort

[ Slides ]


[ Video Lecture ]



mergesort.c



quicksort.c



quicksort3.c





10.


Data Structuring Examples : Introducing Heap

[ No Slides ]



maxmin1.c



maxmin2.c



maxmin3.c



maxmin4.c



max_nextmax.c



tounament.c