**DATA AND FILE STRUCTURES**

OBJECTIVE: In this course student will become familiar with Algorithm analysis: Trees, Graphs, searching and sorting and files.

**UNIT – I**

Fundamentals of algorithm analysis Big ‘O’ notations, Time and space complexity of

algorithms, linked lists: singly and doubly linked lists, stacks, queues, double stack, multistacks and multiqueues, deques, polynomial arithmetic, infix, postfix and prefix arithmetic expression conversion and evaluations.

__UNIT – II__

Trees: Binary trees: Definition, Binary Search Tree basic operations, Tree Traversals (recursive and stack based non-recursive), Heaps and priority queues, Threaded binary tree, AVL Trees BTree: need, properties, creation, uses. B+ tree, B* tree.

__UNIT – III__

Graphs: Representation (Matrix and Linked), Traversals, Connected components, Spanning

trees, Shortest path and Transitive closure, Topological sort, Activity network, Critical path, Path enumeration. Dijkstra’s Algorithm, Floyd Warshall’s Algorithm, Coloring of Graphs, Spanning Tree, Minimum Spanning Tree Algorithms (Kruskal’s Algorithm, Prim’s Algorithm)

Searching & Sorting: Binary search, Hash function, Hash table, Search tree. Internal sort:

Radixsort, Insertion sort, Selection sort, Shell sort, Quick sort, Merge sort, Heap sort.

__UNIT – IV__

Files: Sequential file organization, creating updating retrieving from sequential files advantages and disadvantages of sequential file organization. Data representation and denisity, parity and error control techniques, devices and channels, double buffering and block buffering, handling sequential files in C language, seeking, positioning, reading and writing binary files in C. External Sorting and merging files k way and polyphase merge.