Data Structure & algorithms Handwritten Notes

Description

UNIT-I: Stack and Queue:
Introduction to data structure, Primitive data structure, Time and space complexities of algorithms,
Rate of growth and order notation, Basic time and space analysis of an algorithm. Stacks: Definition,
concepts, operation and application of Stacks, Polish notations, Queue, definition concepts,
operation, applications and types of Queue (Circular queue, Priority Queue).

UNIT-II: General List:
Linear data structures – List and its contiguous implementation, its drawbacks, Pointers and linked
allocation concepts and operations on singly linked list, types of linked lists(Circular Linked List,
Doubly Linked List), Application of linked lists.

UNIT-III: Trees and Its Representation:
Terminologies related to trees, Binary Tree, complete binary tree, almost complete binary tree;
Tree Traversals-preorder, in order and post order traversals, their recursive implementations;
Expression tree-evaluation; Linked representations of binary tree, operations. Basic idea of
AVL Tree; Definition, insertion and deletion operations, Basic idea of B-tree definition, order,
degree, insertion and deletion operations; B+ tree-definition, comparison with B-tree.

UNIT-IV: Searching, Hashing and Sorting:
Requirement of search algorithms; Sequential search, Binary search, Hashing- Basics, methods,
collision, Resolution of collision, chaining; Internal Sorting, External sorting – Selection sort, Bubble
sort, Heap Sort ,Divide and Conquer Method (Merge Sort, Quick Sort, Binary Search).

UNIT-V: Advanced Database Concepts:
Related definitions; Graph representations- adjacency matrx, adjacency list, Traversal schemes –
depth first search, breadth first search; Minimum spanning tree; Shortest path algorithm; Kruskal
and Dijkstra’s Algorithms, Dynamic programming-All pair shortest path(Floyd Warshal algorithm) ,
Greedy algorithm(minimal spanning tree).