MCA 503: Design and Analysis of Algorithms

Lectures: 4 Periods/Week Sessional Marks: 30
University Exam: 3 Hours University Examination Marks: 70


UNIT-I
Introduction
What is Algorithm – Algorithm Specification : Pseudocode Conventions – Recursive Algorithms ; Performance Analysis: Space Complexity – Time Complexity – Asymptotic notation – Performance Measurement; Randomized Algorithms : Basics of probability theory – Randomized algorithms – Identifying the repeated element, Primality Testing – Advantages and Disadvantages.
Elementary Data Structures
Stacks and Queues ; Trees : Terminology – Binary Trees ; Dictionaries : Binary Search Trees ; Priority Queues : Heaps – Heapsort ; Sets and disjoint set Union : Introduction – union and find operations. ; Graphs: Introduction – Definitions – Graph Representations.
Divide – and – conquer
General Method – Defective Chess Board – Binary Search – Finding MaximumandMinimum– Merge Sort – Quick sort – Selection Problem ; Strassen’s Matrix Multiplication, Convex Hull: some geometric Primitives – The Quick Hull Algorithm– Graham’s scan – An 0(nlogn) divide – and – conquer algorithm.

UNIT-II
The Greedy Method
The general Method – Container loading – Knapsack Problem – Tree Vertex Splitting – Job sequencing with deadlines ; Minimum cost spanning trees : Prim’s Algorithm – Kruskal’s Algorithm – Optimal Storage on tapes – Optimal Merge patterns – Single Source shortest paths.
Dynamic Programming
The general method – Multi-stage graphs – All pairs shortest paths – Single source shortest paths – Optimal Binary Search Trees – String editing – 0/1 Knapsack – Reliability design – The traveling sales person problem– Flow shop Scheduling.

UNIT-III
Basic Traversal and Search Techniques
Techniques for Binary Trees – Techniques for graphs : Breadth First Search and Traversal – Depth First Search ; Connected Components and Spanning Trees – Bi-connected components and DFS.
Back Tracking
The general method – The 8-queens problem – sum of subsets – Graph coloring – Hamiltonian Cycles – Knapsack Problem.

UNIT-IV
Branch and Bound
The Method: Least Cost search – The 15 puzzle – control abstractions for LC search – Bounding – FIFO Branch – and –Bound – LC Branch and Bound; 0/1 knapsack problem: LC Branch and Bound solution – FIFO Branch and Bound solution; Traveling Sales person.
NP-Hard and NP – complex problems
Basic concepts : Non deter- ministic algorithms – The classes NP hard and NP complex ; Cook’s theorem – NP hard graph problems : Clique Decision Problem – Node cover decision problem – chromatic number decision problem – Directed Hamiltonian cycle – Traveling sales person decision problem – and/or graph decision problem; NP-hard scheduling Problems: scheduling identical processors – flow shop scheduling – jop shop scheduling; NP-hard code generation problems:code generation with common subexpressions – Implementing parallel assignment instructions; Some simplified NP-hard problems.


Text Books

  1. Sartaj Sahni,”Fundamentals of Computer Algorithms”, Second Edition, Universities Press (2008)

    Chapters : 1 to 8 and 11
Reference Books
  1. Anany Levitin, “Introduction to the Design & Analysis of Algorithms”, Second Edition, Pearson Education (2007).
  2. I.Chandra Mohan, ”Design and Analysis of Algorithms”, PHI.
  3. Parag Himanshu Dave, “Design and Analysis of Algorithms”, Pearson Education (2008)
  4. Prabhakar Gupta, Vineet Agrawarl, “Design and Analysis of Algorithms”, PHI.