Visvesvaraya Technological University, Karnataka, Computer Engineering Semester 4, Design and Analysis of Algorithms Syllabus

Unit - 1 Introduction

1.1 Notion of Algorithm

1.2 Review of Asymptotic Notations

1.3 Mathematical Analysis of NonRecursive and Recursive Algorithms

1.4 Brute Force Approaches Introduction

1.5 Selection Sort and Bubble Sort

1.6 Sequential Search and Brute Force String Matching

Unit - 2 Divide and Conquer

2.1 Divide and Conquer General Method

2.2 Defective Chess Board

2.3 Binary Search

2.4 Merge Sort

2.5 Quick Sort and its performance

Unit - 3 The Greedy Method

3.1 The General Method

3.2 Knapsack Problem

3.3 Job Sequencing with Deadlines

3.4 MinimumCost Spanning Trees

3.5 Prim‟s Algorithm

Unit - 4 Dynamic Programming

4.1 The General Method

4.2 Warshall’s Algorithm

4.3 Floyd’s Algorithm for the AllPairs Shortest Paths Problem

4.4 SingleSource Shortest Paths General Weights

4.5 01 Knapsack

4.6 The Traveling Salesperson problem

Unit - 5 Decrease-and-Conquer Approaches, Space-Time Tradeoffs

5.1 DecreaseandConquer Approaches Introduction

5.2 Insertion Sort

5.3 Depth First Search and Breadth First Search

5.4 Topological Sorting

5.5 SpaceTime Tradeoffs Introduction

5.6 Sorting by Counting

5.7 Input Enhancement in String Matching

Unit - 6 Limitations of Algorithmic Power and Coping with Them

6.1 LowerBound Arguments

6.2 Decision Trees

6.3 P Problems

6.4 NP Problems

6.5 NP Complete Problems

6.6 Challenges of Numerical Algorithms

Unit - 7 Coping with limitations of Algorithmic Power

7.1 Backtracking n Queens problem

7.2 Hamiltonian Circuit Problem

7.3 Subset – Sum Problem

7.4 BranchandBound Assignment Problem

7.5 Knapsack Problem

7.6 Traveling Salesperson Problem

7.7 Approximation Algorithms for NPHard Problems

7.8 Traveling Salesperson Problem

7.9 Knapsack Problem

Unit - 8 PRAM Algorithms

8.1 Introduction

8.2 Computational Model

8.3 Parallel Algorithms for Prefix Computation

8.4 List Ranking and Graph Problems