DS (MCA 2nd)

Section A

ï‚· Introduction to Data Structure: Concept of data, problem analysis, data structures

and data structure operations, notations, mathematical notation and functions,

algorithmic complexity, Big-O Notation and time space trade off.

ï‚· Overview of Arrays, Recursion, Pointers, Pointer Arithmetic, Array of pointers,

Arrays in terms of pointers, Static and Dynamic Memory Management, Garbage

Collection.

ï‚· Understanding and Implementation of various Data Structures with applications

ï‚· Stack: operations like push, pop and various applications like conversion from infix

to postfix and prefix expressions, evaluation of postfix expression using stacks

ï‚· Queues: operations like enqueue dequeue on simple, circular and priority queues.

ï‚· Linked Lists: operations like creations, insertion, deletion, retrieval and traversal on

single, circular and doubly linked list.

Section B

ï‚· Trees definitions and concepts: Root, Node, Leaf Node, Level, Degree, Height and

ï‚· Tree representation using Linked List and Array

ï‚· Types of Trees: Binary trees, Binary search tree, Height balanced (AVL) tree, B-trees,

B+ Tree

ï‚· Tree operations: creation, insertion, deletion and traversals (Preorder, In-order,

Post-ordered) and searching on various types of trees.

ï‚· Heap: Definition, Structure, Algorithms and applications

Section C

ï‚· Graph definitions and concepts: Edge, Vertices, and Graph representation using

Adjacency matrix, Adjacency lists

ï‚· Types of graphs: Weighted, Unweighted, Directed, Undirected Graphs

ï‚· Graph operations: creation, insertion, deletion, traversals and searching (depth-first,

breadth-first) of various types of graphs and Dijkstra’s algorithm for shortest

distance calculation.

Section D

ï‚· Searching: Concept and efficiency of linear and binary search algorithms.

ï‚· Sorting: Concepts, Order, Stability, Efficiency of various algorithms (Selection

ï‚· Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort)

ï‚· Hashing: Definition, Implementation and applications