DATA STRUCTURE & ALGORITHM
Importance of study of Data structure, Concept of data structure: Data and data structure, Abstract
data type and data type. Algorithm and programs, Basic idea of pseudo-code, Algorithm efficiency and
analysis, time and space analysis of algorithms-order notations.
Different representation: row major, column major.
Sparse matrix, its implementation and usage. Array representation of polynomials.
Singly linked list, circular linked list, doubly linked list, linked list representation of polynomial and
Stack & queue:
Stack and its implementation, (using array, using linked list) application.
Queues, circular queue, dequeue, Implementation of queue- both linear and circular (using array, using
linked list) applications.
Recursion: Principle of recursion- use of stack, difference between recursion and iteration, tail
recursion. Application-The Tower of Hanoi, Eight Queen Puzzle.
Nonlinear data structure:
Trees: Basic terminologies, forest, tree representation (using array, using linked list).
Basic trees, binary tree traversal (Pre-,in-,post-order), threaded binary tree(left, right, full), non
recursive traversal algorithm 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 tree orations ((insertion, deletion with examples only)
Graph definition and concept, (directed/undirected graph, weighted/un-weighted edges, sub-graph,
degree, cut vertex /articulation point, pendant node, clique, complete graph, connected –strongly
connected component, weakly connected component-path, shortest path, isomorphism.
Graph representation/storage implementation- adjacency matrix, adjacency list, adjacency multi-list.
Graph traversal and connectivity- Depth First Search (DFS), Breadth-First Search (BFS), concept of
edges used in DFS and BFS (tree-edge, back-edge, cross-edge, and forward-edge, application.
Minimal spanning tree-Prim’s algorithm ( Basic idea of greedy methods)
Sorting algorithm, Bubble sort and optimization, insertion sort, shell sort, selection sort, merge sort,
quick sort, heap sort (Concept, of max heap, application-priority queue, radix sort.
Searching, sequential search, binary search, interpolation search.
Hashing, Hashing functions, collision resolution techniques.
Data structure using C, Reema Thareja, Oxford.
2. Data structure, S.Lipschutz.
3. Data structure and program design in C, Robert L Krusse, B.P.Leung
1. Data structure using C++, Varsha H. Patil, Oxford