lECTURE pLAN

 

Design and Analysis of Algorithm

MCA 3RD

 

Unit-I Introduction:

1.      Algorithms, Analysis of Algorithms, Design of Algorithms

2.      Complexity of Algorithms,

3.      Asymptotic Notations,

4.      Growth of function,

5.      Recurrences

6.      Recurrence Tree

7.      Recurrence Master Method

Sorting in polynomial Time:

8.      Insertion sort,

9.      Merge sort,

10.  Quick sort,

11.  Heap sort

Sorting in Linear Time
  1. Counting sort, 
  1. Radix Sort, Bucket Sort
  1. Medians and order statistics

Unit-II Elementary Data Structure:

  1. Stacks, Queues, Linked list, Binary Search Tree, Hash Table

16.  Advanced Data Structure:  Red Black Trees, Splay Trees, Augmenting Data Structure

17.  Binomial Heap, B-Tree, Fibonacci Heap,

18.  Data Structure for Disjoint Sets
  1. Union-find Algorithm, Dictionaries and priority Queues,
  1. Mergeable heaps, Concatenable queues

Unit-III Advanced Design and Analysis Techniques:

  1. Dynamic programming,
  1. Dynamic programming
  1. Greedy Algorithm,
  1. Greedy Algorithm,
  1. Backtracking,
  1. Branch-and-Bound,
  1. Amortized Analysis

Unit-IV Graph Algorithms:

  1. Elementary Graph Algorithms, Breadth First Search,
  1. Depth First Search,
  1. Minimum Spanning Tree, Kruskal’s Algorithms, Prim’s Algorithms,
  1. Single Source Shortest Path,
  1. All pair Shortest Path,
  1. Maximum flow and Traveling Salesman Problem

Unit IV
  1. Randomized Algorithms,
  1. String Matching,
  1. NP-Hard and NP-Completeness
  1. Approximation Algorithms,
  1. Sorting Network,
  1. Matrix Operations,
  1. Polynomials & the FFT,
  1. Number Theoretic Algorithms,
  1. Computational Geometry

 

 

References

1. Coremen Leiserson etal, “ Introduction to Algorithms”, PHI

2. Horowitz Sahani, “ Fundamentals of Computer Algorithms”, Golgotia

3. Brassard Bratley, “Fundamental of Algorithms”, PHI

4. M T Goodrich etal, “Algorithms Design”, John Wiley

Hosted by www.Geocities.ws

1