Truth Table to Karnaugh Map

Credit: 3



Importance of study of Data structure, Concept of data structure: Data and data structure, Abstract
data type and data type. Algorithm and programs, Basic idea of pseudo-code, Algorithm efficiency and
analysis, time and space analysis of algorithms-order notations.
Different representation: 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
Stack & queue:
Stack and its implementation, (using array, using linked list) application.
Queues, circular queue, dequeue, Implementation of queue- both linear and circular (using array, using
linked list) applications.
Recursion: Principle of recursion- use of stack, difference between recursion and iteration, tail
recursion. Application-The Tower of Hanoi, Eight Queen Puzzle.
Nonlinear data structure:
Trees: Basic terminologies, forest, tree representation (using array, using linked list).
Basic trees, binary tree traversal (Pre-,in-,post-order), threaded binary tree(left, right, full), non
recursive traversal algorithm 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 tree orations ((insertion, deletion with examples only)
Graph definition and concept, (directed/undirected graph, weighted/un-weighted edges, sub-graph,
degree, cut vertex /articulation point, pendant node, clique, complete graph, connected –strongly
connected component, weakly connected component-path, shortest path, isomorphism.
Graph representation/storage implementation- adjacency matrix, adjacency list, adjacency multi-list.
Graph traversal and connectivity- Depth First Search (DFS), Breadth-First Search (BFS), concept of
edges used in DFS and BFS (tree-edge, back-edge, cross-edge, and forward-edge, application.
Minimal spanning tree-Prim’s algorithm ( Basic idea of greedy methods)

Searching, Sorting:
Sorting algorithm, Bubble sort and optimization, insertion sort, shell sort, selection sort, merge sort,
quick sort, heap sort (Concept, of max heap, application-priority queue, radix sort.
Searching, sequential search, binary search, interpolation search.
Hashing, Hashing functions, collision resolution techniques.

Text Books:
Data structure using C, Reema Thareja, Oxford.
2. Data structure, S.Lipschutz.
3. Data structure and program design in C, Robert L Krusse, B.P.Leung
Reference Books:
1. Data structure using C++, Varsha H. Patil, Oxford