Linked ListsConcepts of linked organization, singly linked list, Operations such as as Insertion, deletion, inversion, concatenation, Computation of length, traversal on linked list, Applications : Representation and manipulations of polynomials using linked lists, Representation of sparse matrix using linked organization, Linked Stacks and Queues, circular linked list, doubly linked list and dynamic storage management, Representation of polynomial/set using generalized linked list, Dynamics memory management : Garbage collection and compaction.TreesReview of basic terminology, binary trees and its representation using sequential and linked organization, full and complete binary trees, converting tree to a binary tree, binary tree traversals (recursive and non recursive), operations such as copy, equal etc, Threaded binary trees, Insertion and deletion of nodes in in-order threaded binary tree, preorder, in-order and post-order traversals of in-order threaded binary tree, applications of binary trees : Gaming, Expression and decision trees.GraphsReview of basic terminology, Representation of graphs using adjacency matrix, adjacency list and adjacency Multi-list, Traversals : Depths First and Breadth First, connected components and spanning trees, Kruskal's and Prim's algorithms for minimum spanning tree, Algorithm for shortest path and topological sorting.Symbol TablesNotion of symbol table, representation, static tree tables and dynamic tree tables.Hash TablesHash Tables, Hash Functions : Division and Multiplication methods, Collusion Resolution strategies : Chaining and Open addressing, Table overflow : Expansion and extendible hashing.HeapsConcepts, Binary Heaps : Operations, Applications : The selection problem, Event simulation etc., Introduction to d-Heaps, Leftists and Skew Heaps.IndexingIndexing Techniques : Hashed indexes, Tree indexing - B tress, B+ Trees and Trie Indexing.(Implementation not expected for the following topics of this unit)Introduction of Top-down Splay Trees, Red-black trees, AA trees, k-d trees.FilesExternal storage devices, Files : Definition and concepts, Files organization : Sequential files random, linked, inverted and cellular partitions. Processing of sequential, Index-sequential and direct files.Linked ListsConcepts of linked organization, singly linked list, Operations such as as Insertion, deletion, inversion, concatenation, Computation of length, traversal on linked list, Applications : Representation and manipulations of ...
|Author||:||A.A.Puntambekar N.A.Deshpande S.S.Sane|
|Publisher||:||Technical Publications - 2006-01-01|