Data Structures (211)
Lectures/ Tut and Lab evaluation will be held physically
Announcements, Assignment submissions via Google Classroom
Course Objective:
Course Outline:
Component / Unit  Topics 

 Introduction  Basic Terminology, Elementary Data Organization, Asymptotic notations  Theta, BigO, and Omega, Efficiency of an Algorithm, Time and Space Complexity and tradeoff. Arrays  Definition, Single and Multidimensional Arrays, Representation of Arrays, Application of arrays, Sparse Matrices and their representations. Linked Lists  Implementation of Single, Double and 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.; 
 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 
 Trees: Basic terminology, kary 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 
 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 pathDijkstra algorithm, Topological Sort. 
1. Ellis Horowitz, Satraj Sahni and Susan AndersonFreed, Fundamentals of Data Structures in C, W. H. Freeman and Company.
2. Seymour Lipschutz ,
Data Structures, Schaum's Outlines Series, Tata McGrawHill.
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.
1. Donald Knuth,
The Art of Computer Programming, Volume 1 and 3, AddisonWesley, 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, PrenticeHall of India. .
Important Instructions:
1.
Classes will be conducted using slide presentation and chalkboard. 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 takehome
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
MidSem  Closed book exam (25 marks); Take home assignments and Lab test (15 marks); Attendance (2.5 marks)
o
EndSem  Closed book exam (40 marks); Take home assignments and Lab test (15 marks); Attendance (2.5 marks)
o 40%:
7.
Take home assignments : They will be assigned at the beginning of a module (announcements will be made on the course website every week). Interact with your TAs during tutorial sessions to clear your doubts regarding the homework assignments. These assignments will not only help you in development of an indepth idea of each topic of the course but will also serve to prepare for your written examinations.
8.
Tutorial Classes : The tutorial classes scheduled every alternate 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:
Sl. No. 
Topic 
Tutorials / Resources 
Homework Assignments 
1. 
Introduction 
Introduction to Programming Using C 

2. 
Analysis of Algorithms 
Math Review 

3. 
Review of Basic Data Structures 
Structures in C 

4. 
Problem Solving Through Data Structuring  I 


5. 
Recursion 


6. 
Search Algorithms 


7. 
Sorting 


8. 
Efficient Sorting 


9. 
Abstract Data Types  Stack and Queue 
Code : Stack using Linked List 

10. 
Heap and Priority Queues 


11. 
Hashing 


12. 
Trees 


13. 
Graph
[ Slides  Connected Components, Directed Graphs, Topologocal Sort ] 
