S.no 
Topic 
Lecture(hrs) 
1 
Algorithm efficiency and analysis, order notations 
1 
2 
Array: Different representations – row major, column major. Sparse matrix  its implementation and usage 
2 
3 
Array representation of polynomials 
1 
4 
Linked List: Singly linked list, circular linked list, doubly linked list 
2 
5 
Representation of polynomial expression and Sparse Matrix using suitable Linked List 
2 
6 
Stack and its implementations, Principles of recursion – use of stack, Tail recursion, Applications  The Tower of Hanoi, Eight Queens Puzzle 
2 
7 
Queue, circular queue, Dequeqe, Priority Queue and its different Implementation, Applications

1 
8 
Trees: Basic Concepts & representation, Binary trees  Traversal (pre, in, post order), Threaded binary tree (left, right, full), Expression tree

3 
9 
Binary search tree operations (creation, insertion, deletion, searching)

2 
10 
B Trees & B+ Tree – operations

1 
11 
Heaps: Balanced Search Trees as Heaps, ArrayBased Heap, HeapOrdered Tress and HalfOrdered Trees, Leftist Heaps, Skew Heap, Binomial Heaps, Changing Keys in Heaps

2 
12 
HeightBalanced Trees and Weight Trees

2 
13 
RedBlack Trees and Trees of Almost Optimal Height
 1 
14 
TopDown Rebalancing for RedBlack Trees, Trees with Constant Update Time at a Known Location, Finger Trees and Level Linking

2 
15 
Trees with Partial Rebuilding: Amortized Analysis, Splay Trees: Adaptive Data Structures

1 
16 
Skip Lists: Randomized Data Structures, Joining and Splitting Balanced Search Trees

1 
17 
Interval Trees, Segment Trees, Trees for IntervalRestricted Maximum Sum Queries, Orthogonal Range Trees, and HigherDimensional Segment Tree

2 
18 
Searching: Sequential search, binary search, interpolation search.
 2 
19 
Sorting Algorithms: Bubble sort and its optimizations, insertion sort, shell sort, selection sort, merge sort, quick sort, heap sort, radix sort

4 
20 
Graph definitions and concepts. Graph representations/storage implementations – adjacency matrix, adjacency list, adjacency multilist

2 
21 
Graph traversal algorithm: Breadth First Search (BFS) and Depth First Search (DFS) – Classification of edges  tree, forward, back and cross edges – complexity and comparison

1 
22 
Basic Hash Tables and Collision Resolution, Universal Families of Hash Functions, Perfect Hash Functions, and Hash Trees, Extendible Hashing, Membership Testers and Bloom Filters

2 
23 
Divide & Conquer Algorithms

2 
24 
Greedy Algorithms: Basic method, use, Examples

2 
25 
Dynamic Programming: Basic method, use, Examples

4 
26 
Backtracking Algorithms:

4 
26 
Notion of NPcompleteness: P class, NP class, NP hard class, NP complete class – their interrelationship, Satisfiability problem, Cook’s theorem, Clique decision problem

4 

Total lecture (hrs.)

50 