Data Structures And Files

Algorithm AnalysisFrequency count, Time and space complexity, Notations, Graphical representation of time complexities, Analysis of algorithms e.g. searching and sorting techniques. Simple and fast transpose of sparse matrices, Various operations on data structures like link list etc.Non Linear Data StructuresTrees and binary trees - Concept and terminology. Data structures for binary trees. Algorithm for tree traversals (recursive and non recursive). Conversion of general tree to binary, Binary search trees, Insertion and deletion of nodes in inorder threaded binary tree. Preorder, Inorder and traversals of inorder threaded binary search tree, Heap data structure, Concept of red and black trees.GraphsConcepts and terminology, Representation of graphs using adjacency matrix, Adjacency list, Depth first search and Breadth first search. Algorithms for minimal spanning tree (Prim s and Kruskal s) and shortest path - Dijkstra s algorithm (The instructor will discuss only algorithm and rest of the topics are left for self study ).Generalized link lists, Polynomial representation using GLL.Symbol Tables and Hashing TechniquesNotion of a symbol table, AVL trees, Static and dynamic trees, OBST, Heap sort, Huffman s algorithm.Algorithmic StrategiesType of algorithms : Use and the peculiar characteristics of each type, Divide and conquer (e.g. Quick sort, Mergesort, Tower of Hanoi), Dynamic programming (e.g. The triangulation problem, Matrix multiplication, 0-1, Knapsack), Greedy algorithms (e.g. Graph coloring problem, Job scheduling, Knapsack), Backtracking (e.g. Tic tac toe, Eight queens problem, Mazing problem) Randomized algorithms (Travelling salesman problem).FilesOrganization of files, Types of file. Organization-sequential and direct access file, Simple index file (primitive operations and implementation in C), Hashing function and it s characteristics, Collision, Resolution, Linear probing, Chaining with and without replacement, Rehashing.