B.Tech in Computer Science and Engineering Programme
Data Structures
Code: CS302
Contacts: 3L
Credits: 3
Allotted Lectures: 36L
Prerequisite:
1. Familiarity with the fundamentals of C or other programming language
2. A solid background in mathematics, including probability, set theory.
Course Objective(s)
1. To learn the basics of abstract data types.
2. To learn the principles of linear and nonlinear data structures.
3. To build an application using sorting and searching.
Course Outcome(s)
On completion of the course students will be able to
1. Differentiate how the choices of data structure & algorithm methods impact the performance of program.
2. Solve problems based upon different data structure & also write programs.
3. Identify appropriate data structure & algorithmic methods in solving problem.
4. Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing
5. Compare and contrast the benefits of dynamic and static data structures implementations.
Module I: Linear Data Structure [10L]
Introduction (2L):
Concepts of data structures: a) Data and data structure b) Abstract Data Type and Data Type.
Algorithms and programs, basic idea of pseudo-code (1L)
Algorithm efficiency and analysis, time and space analysis of algorithms – order notations (1L)
Array (2L):
Different representations – row major, column major (1L)
Sparse matrix - its implementation and usage, Array representation of polynomials (1L)
Linked List (6L):
Singly linked list – operations, Doubly linked list – operations (4L)
Circular linked list – operations, Linked list representation of polynomial and applications (2L)
Module II: Linear Data Structure [6L]
Stack and Queue (4L):
Stack and its implementations (using array and linked list) (1L)
Applications (infix to Postfix, Postfix Evaluation) (1L)
Queue, circular queue, de-queue (1L)
Implementation of queue- linear and circular (using array and linked list) (1L)
Recursion (2L):
Principles of recursion - use of stack, tail recursion. (1L)
Applications - The Tower of Hanoi(1L)
Module III: Nonlinear Data structures [12L]
Trees (8L):
Basic terminologies, forest, tree representation (using array and linked list) (1L)
Binary trees - binary tree traversal (pre-, in-, post- order) (1L)
Threaded binary tree (1L)
Binary search tree- operations (creation, insertion, deletion, searching) (1L)
Concept of Max-Heap and Min-Heap (creation, deletion) (1L)
Height balanced binary tree – AVL tree (insertion with examples only) (1L)
Height balanced binary tree – AVL tree (deletion with examples only) (1L)
m –Way Search Tree, B Tree – operations (insertion, deletion with examples only) (1L)
Graphs (4L):
Graph theory review (1L)
Graph traversal and connectivity – Depth-first search (DFS), Breadth-first search (BFS) - concepts of edges used in DFS and BFS (tree-edge, back-edge, cross-edge, and forward-edge) (2L)
Minimal spanning tree – Prim’s algorithm, Kruskal’s algorithm (basic idea of greedy methods) (1L)
Module IV: Searching, Sorting [8L]
Sorting Algorithms (4L):
Bubble sort, Insertion sort, Selection sort – with notion of complexity (1L)
Quick sort, Merge sort – with complexity (2L)
Radix sort – with complexity (1L)
Searching (2L):
Sequential search – with complexity (1L)
Binary search, Interpolation Search– with complexity (1L)
Hashing (2L):
Introduction to Hashing and Hashing functions (1L)
Collision resolution techniques (1L)
Text books:
1. Data Structures Through 'C' Language by Samiran Chattopadhyay, Debabrata Ghosh Dastidar, Matangini Chattopadhyay, Edition: 2001, BPB Publications
2. Fundamentals of Data Structures of C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-freed 2nd Edition, Universities Press
Recommended books:
1. Data Structures, Algorithms, and Software Principles in C by Thomas A. Standish, 1 Edition, Pearson
2. Data Structures by S. Lipschutz, Special Indian Edition, Tata McGraw Hill Education (India) Private Limited
3. Data Structures and Program Design In C by Robert L. Kruse, Bruce P. Leung 2nd Edition, Pearson
4. Data Structures in C by Aaron M. Tenenbaum, 1St Edition, Pearson
Comments