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.