Design & Analysis of Algorithms

Download This Book

410441  Design And Analysis of Algorithms

Teaching Scheme:                                   Examination Scheme:

Theory:4 HourslWeek                             Theory:100 Marks                     

                                                                                                                     

Objectives :

. To study and perform analysis of algorithms.

. To study techniques/strategies in design of algorithms

UNIT I:

Introduction:

Big O, theta and omega asymptotic notations, Average, Best and Worst case analysis of algorithms for Time and Space complexity, Amortized Analysis, Solving Recurrence Equations, Proof Techniques: by Contradiction, by Mathematical Induction.

Priority Queues: Heaps & Heap sort.

8 Hours

UNIT II:

Divide And Conquer And Greedy Strategy:

Divide and Conquer: General Strategy, Exponentiation. Binary Search, Quick Sort and Merge Sort. Greedy Method ,General Strategy, Knapsack problem, Job sequencing with Deadlines, Optimal merge patterns, Minimal Spanning Trees and Dijkstra's algorithm.

9 Hours

UNIT III:

Dynamic Programming:

General Strategy, Multistage graphs, OBST, Oil Knapsack, Traveling Salesperson Problem, Flow

Shop Scheduling.                                                                                                            7 Hours

UNIT IV:

Backtracking & Branch And Bound:

Backtracking: General Strategy, 8 Queen's problem, Graph Coloring, Hamiltonian Cycles, 0/1 Knapsack.

Branch and Bound: General Strategy, 0/1 Knapsack, Traveling Salesperson Problem.

8 Hours

UNIT V:

Parallel Algorithms:

Computational Model, Basic Techniques and Algorithms (Complete Binary Tree, Pointer Doubling, Prefix Computation), Selection, Merging, Sorting Networks, Parallel Sorting, Graph Problems (Alternate Algorithm for Transitive Closure, All pairs shortest path)                                                                                                                 8 Hours

UNIT VI:

NP-Hard And NP-Complete Problems:

Algorithms, Complexity-intractability, Non-Deterministic Polynom:al time (NP) Decision

problems, Cooks Theorem.                 ­

NP-Complete problems- Statisfiability problem, vertex cover problem.

NP-Hard problems-graph, scheduling, code generation problems, Simplified NP Hard Problems. 6 Hours

Text Books:

I. Bressard, "Fundamental of Algorithm." , PHI

2. Horowitz and Sahani, "Fundamentals of computer Algorithms", Galgotia.

References:

I. Thomas H Connen and Charles E.L Leiserson, "Introduction to Algorithm" PHI

2. A. V. Aho and J.D. Ullman, "Design and Analysis of Algorithms", Addison Wesley