DATA STRUCTURE & ALGORITHM

EE-504A

Credit: 3

Introduction:

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

applications.

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:

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)

Searching, Sorting:

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.

Text Books:

1.

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

Reference Books:

1. Data structure using C++, Varsha H. Patil, Oxford