Name of Subject: DESIGN & ANALYSIS OF ALGORITHMS ( 6 IT 3)

Unit

Contents

BACKGROUND:

Review of Algorithm Complexity and Order Notations and Sorting Methods.

DIVIDE AND CONQUER METHOD:

Binary Search, Merge Sort, Quick sort and strassen's matrix multiplication

I

algorithms.

GREEDY METHOD:

Knapsack Problem, Job Sequencing, Optimal Merge Patterns and Minimal Spanning Trees.

DYNAMIC PROGRAMMING:

Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack

Problem.

II

BRANCH AND BOUND: Traveling Salesman Problem and Lower Bound Theory.

Backtracking Algorithms and queens problem.

PATTERN MATCHING ALGORITHMS:

Naïve and Rabin Karp

string matching algorithms, KMP Matcher and

III

Boyer Moore Algorithms.

ASSIGNMENT PROBLEMS:

Formulation of Assignment and Quadratic Assignment Problem.

RANDOMIZED ALGORITHMS.

Las Vegas algorithms, Monte Carlo algorithms, randomized algorithm for Min-Cut,

IV

randomized algorithm for 2-SAT.

Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity assignment problems.

PROBLEM CLASSES NP, NP-HARD AND NP-COMPLETE:

Definitions of P, NP-Hard and NP-Complete

V

Problems. Decision Problems. Cook's Theorem. Proving NP-Complete Problems - Satisfiability problem and