Name of Subject  :  DATA STRUCTURES AND ALGORITHMS  (3 IT 3)

Unit

Contents

Data Structure: Definition, Implementation, Operation, Application, Algorithm writing and convention. Analysis of

algorithm, Complexity Measures and Notations.

I

Arrays: Representation of arrays (multidimensional), Address calculation using column and row major ordering.

Linked Lists : Implementation, Doubly linked list, Circular linked list, unrolled linked list, skip-lists,  Splices, Sentinel

nodes, Application (Sparse Matrix, Associative Array, Functional Programming)

Stacks : Definition, Implementation, Application (Tower of Hanoi, Function Call and return, Parentheses Matching,

II

Back-tracking, Expression Evaluation)

Queues : Definition, deque, enque, priority queue, bounded queue,  Implementation, Application

Tree:  Definition of elements, Binary

trees:

Types (Full, Complete, Almost complete), Binary Search Tree,

Traversal (Pre, In, Post & Level order), Pruning, Grafting.    Application: Arithmetic Expressions Evaluation

III

Variations: Indexed Binary Tree, Threaded Binary Tree, AVL tree, Multi-way trees, B tree, B+ tree, Forest, Trie and

Dictionary

Graphs: Elementary definition, Representation (Adjacency Matrix, Adjacency Lists) Traversal (BFS, DFS)

IV

Application: Spanning Tree (Prim and Kruskal Algorithm), Dijkstra's algorithm, Shortest path algorithms.

Sorting: Bubble, Selection, Insertion, Quick, Radix, Merge, Bucket, Heap, Searching: Hashing, Symbol Table,

V