Unit-1: INTRODUCTION TO DATA STRUCTURE
Teaching Hours: 10 Hrs,
Elementary Data Structures: Stack – Queues – Trees – Priority Queue – Graphs – What
is an Algorithm? –
Algorithm Specification – Performance Analysis: Space Complexity – Time Complexity
– Asymptotic Notation –
Randomized Algorithms.
Unit-2: SEARCH AND SORTING Teaching Hours: 11 Hrs.
General Method – Binary Search – Recurrence Equation for Divide and Conquer –
Finding the Maximum
and Minimum–– Merge Sort – Quick Sort – Performance Measurement – Randomized
Sorting Algorithm –
Selection Sort – A Worst Case Optimal Algorithm – Implementation of Select2 –
Stassen‟s Matrix Multiplications.
Unit-3: TREES Teaching Hours: 11 Hrs.
The General Method – Container Loading – Knapsack Problem – Tree Vertex Splitting –
Job Sequencing
with Deadlines – Minimum Cost Spanning Trees – Prim‟s Algorithm – Kruskal‟s
Algorithm – An optimal
Randomized Algorithm – Optimal Storage on Tapes – Optimal Merge Pattern – Single
Source Shortest Paths.
Unit-4: GRAPHS Teaching Hours: 10 Hrs.
The General Method – Multistage Graphs – All Pair Shortest Path – Optimal Binary
Search Trees – String
Editing – 0/1 Knapsack – Reliability Design – The Traveling Salesperson Problem.
Techniques for Binary Trees –
Techniques for Graphs – BFS – DFS.
Unit-5: PROBLEM SOLVING METHODS
Teaching Hours: 10 Hrs.
The General Method – The 8– Queens Problem – Sum of Subsets– Graph Coloring –
Hamiltonian Cycles –
Branch and Bound: General Method – LC Branch and Bound – FIFO Branch and Bound
