mca Syllabus

Data Structure & Algorithm
Code: CS302
Contacts: 3L +1T
Credits: 4
Pre-requisites: CS 201 (Basic Computation and Principles of C), M101 & M201 (Mathematics), basics of set theory

Module -I. [8L] Linear Data Structure
Introduction (2L):

Why we need data structure?
Concepts of data structures: a) Data and data structure b) Abstract Data Type and Data Type.
Algorithms and programs, basic idea of pseudo-code.
Algorithm efficiency and analysis, time and space analysis of algorithms – order notations.

Array (2L):
Different representations – row major, column major.
Sparse matrix - its implementation and usage. Array representation of polynomials.
Linked List (4L):
Singly linked list, circular linked list, doubly linked list, linked list representation of polynomial and applications.

Module -II: [7L] Linear Data Structure
[Stack and Queue (5L):
Stack and its implementations (using array, using linked list), applications.
Queue, circular queue, dequeue. Implementation of queue- both linear and circular (using array, using linked list), applications.
Recursion (2L):
Principles of recursion – use of stack, differences between recursion and iteration, tail recursion.
Applications - The Tower of Hanoi, Eight Queens Puzzle.

Module -III. [15L] Nonlinear Data structures
Trees (9L):
Basic terminologies, forest, tree representation (using array, using linked list).
Binary trees - binary tree traversal (pre-, in-, post- order), threaded binary tree (left, right, full) - non-recursive traversal algorithms using threaded binary tree, expression tree.
Binary search tree- operations (creation, insertion, deletion, searching).
Height balanced binary tree – AVL tree (insertion, deletion with examples only).
B- Trees – operations (insertion, deletion with examples only).
Graphs (6L):
Graph definitions and concepts (directed/undirected graph, weighted/un-weighted edges, sub-graph, degree, cutvertex/ articulation point, pendant node, clique, complete graph, connected components – strongly connected component, weakly connected component, path, shortest path, isomorphism).
Graph representations/storage implementations – adjacency matrix, adjacency list, adjacency multi-list.
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, forward-edge), applications.
Minimal spanning tree – Prim’s algorithm (basic idea of greedy methods).

Module - IV. Searching, Sorting (10L):
Sorting Algorithms (5L): Bubble sort and its optimizations, insertion sort, shell sort, selection sort, merge sort, quick sort, heap sort (concept of max heap, application – priority queue), radix sort.
Searching (2L): Sequential search, binary search, interpolation search.
Hashing (3L): Hashing functions, collision resolution techniques.

Recommended books:
1. “Data Structures And Program Design In C”, 2/E by Robert L. Kruse, Bruce P. Leung.
2. “Fundamentals of Data Structures of C” by Ellis Horowitz, Sartaj Sahni, Susan Anderson-freed.
3. “Data Structures in C” by Aaron M. Tenenbaum.
4. “Data Structures” by S. Lipschutz.
5. “Data Structures Using C” by Reema Thareja.
6. “Data Structure Using C”, 2/e by A.K. Rath, A. K. Jagadev.
7. “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

Learning outcome:
Ideally this course should act as a primer/pre-requisite for CS 503 (Design and Analysis of Algorithms). Oncompletion of this course, students are expected to be capable of understanding the data structures, their advantages and drawbacks, how to implement them in C, how their drawbacks can be overcome and what the applications are and where they can be used. Students should be able to learn about the data structures/ methods/algorithms mentioned in the course with a comparative perspective so as to make use of the most appropriate data structure/ method/algorithm in a program to enhance the efficiency (i.e. reduce the run-time) or for better memory utilization, based on the priority of the implementation. Detailed time analysis of the graph algorithms and sorting methods are expected to be covered in CS 503 but it is expected that the students will be able to understand at least the efficiency aspects of the graph and sorting algorithms covered in this course. The students should be able to convert an inefficient program into an efficient one using the knowledge gathered from this course.