|
UNIT 1 :
PERFORMANCE MEASUREMENT : Space complexity and Time complexity, big
oh, omega and theta notations and their significance. Linear Lists - Array
and linked representation, Singly & Doubly linked lists. Concept of
circular linked lists.
UNIT 2 : ARRAY & MATRICES - Row and Column Major mapping &
representation, irregular 2D array, Matrix operations, Special matrices:
diagonal, tri-diagonal, triangular, symmetric. Sparse matrices
representation and its transpose.
UNIT 3 : STACKS - Representation in array & linked lists, basic
operation, Applications of stacks in parenthesis matching, towers of Hanoi
etc. Queues - Representation in array & linked lists, applications,
circular queues.
UNIT 4 : TREES - Binary Tree, representation in array & linked
lists, basic operation on binary trees, binary tree traversal (preorder,
post order, in order). Search Trees - Binary search tree, indexed-binary
search tree, basic operation, AVL tree, B-tree.
UNIT 5 : GRAPHS - Representation of un weighted graphs, BFS, DFS,
Minimum cost spanning trees, Single source shortest path. Sorting - Bubble
sort, insertion sort, merge sort, selection sort, quick sort, heap sort.
|