B-Tech Third Semester - Data Structure & Algorithm

B-Tech Third Semester

Subject:  Data Structure & Algorithm

• Why we need data structure?
• Concepts of data structures: a) Data and data structure b) Abstract Data Type and Data Type.
• Algorithms and programs, basic idea of pseudo-code.
• Algorithm efficiency and analysis, time and space analysis of algorithms – order notations.

• Different representations – row major, column major.
• Sparse matrix - its implementation and usage. Array representation of polynomials.

• Singly linked list, circular linked list, doubly linked list, linked list representation of polynomial and applications.

• Stack and its implementations (using array, using linked list), applications.
• Queue, circular queue, dequeue. Implementation of queue- both linear and circular (using array, using linked
• list), applications.

• Principles of recursion – use of stack, differences between recursion and iteration, tail recursion.

• Basic terminologies, forest, tree representation (using array, using linked list).
• Binary trees - binary tree traversal (pre-, in-, post- order), threaded binary tree (left, right, full) - non-recursive
• traversal algorithms using threaded binary tree, expression tree.
• Binary search tree- operations (creation, insertion, deletion, searching).
• Height balanced binary tree – AVL tree (insertion, deletion with examples only).
• B- Trees – operations (insertion, deletion with examples only).

• Graph definitions and concepts (directed/undirected graph, weighted/un-weighted edges, sub-graph, degree, cutvertex/
• articulation point, pendant node, clique, complete graph, connected components – strongly connected
• component, weakly connected component, path, shortest path, isomorphism).
• Graph representations/storage implementations – adjacency matrix, adjacency list, adjacency multi-list.
• Graph traversal and connectivity – Depth-first search (DFS), Breadth-first search (BFS) – concepts of edges
• used in DFS and BFS (tree-edge, back-edge, cross-edge, forward-edge), applications.
• Minimal spanning tree – Prim’s algorithm (basic idea of greedy methods).

•  Bubble sort and its optimizations, insertion sort, shell sort, selection sort, merge sort, quick sort, heap sort (concept of max heap, application – priority queue), radix sort.

• Sequential search, binary search, interpolation search.

• Hashing functions, collision resolution techniques.