About Subject

Pattern / Course	2015 Course
Year & Branch	TE (Information Technology)
Semester I/II	II
Course code	C311(304452)
Course title	Design and Analysis of Algorithms
Teaching Scheme (Lect / Tut /  Pract)	Lectures: 4 Hrs/ Week
Examination Scheme	In semester Assessment: 30 End Semester Assessment : 70 Total marks: 100

Course Objectives

1	To understand the problem solving and problem classification.
2	To know the basics of computational complexity analysis and various algorithm design strategies.
3	To provide students with solid foundations to deal with a wide variety of computational problems.
4	To provide a thorough knowledge of the most common algorithms and data structures.
5	To analyze a problem and identify the computing requirements appropriate for its solutions.
6	To understand the design of parallel algorithms.

Course Outcomes

CO1	Identify the basic properties of algorithm and analyze it using different methods. and design paradigm for solving a few example problems and analyze them.
CO2	Design algorithms using divide and conquer and Greedy method for searching & sorting, knapsack problem, minimum cost spanning tree, single source shortest path problem etc. and analyze them.
CO3	Apply dynamic programming paradigm to solve travelling sales person problem,0/1 knapsack problem, Optimal binary search tree.
CO4	Apply traversal methods on search trees and search methods on graphs and backtracking search methods on state space trees for few example problems.
CO5	Analyze branch and Bound search methods through problems such as 0/1 knapsack problem, Travelling sales person problem
CO6	Evaluate P ,NP,NP hard, NP complete class of problems and algorithms

Syllabus

Unit	Content	Hrs
I	INTRODUCTION	8
	Brute Force method: Introduction to Brute Force method & Exhaustive search, Brute Force solution to 8 queens’ problem. Proof Techniques: Minimum 2 examples of each: Contradiction, Mathematical Induction, Direct proofs, Proof by counterexample, Proof by contraposition. Analysis of Algorithm: Efficiency- Analysis framework, asymptotic notations – big O, theta and omega. Amortized Analysis: Aggregate, Accounting & Potential method with the example of stack operations. Analysis of Non-recursive and recursive algorithms: Solving Recurrence Equations (Homogeneous and nonhomogeneous)..
II	DIVIDE AND CONQUER AND GREEDYMETHOD	8
	Divide & Conquer: General method, Control abstraction, Merge sort, Quick Sort – Worst, Best and average case. Binary search, Finding Max-Min, Large integer Multiplication (for all above algorithms analysis to be done with recurrence). Greedy Method: General method and characteristics, Prim’s method for MST , Kruskal’s method for MST (using nlogn complexity), Dijkstra’s Algorithm, Optimal storage on tapes, Fractional Knapsack problem, Job Sequencing.
III	DYNAMIC PROGRAMMING	8
	General strategy, Principle of optimality, 0/1 knapsack Problem, Bellman-Ford Algorithm , Multistage Graph problem, Optimal Binary Search Trees, Travelling Salesman Problem.
IV	BACKTRACKING	8
	General method, Recursive backtracking algorithm, Iterative backtracking method. 8-Queen problem, Sum of subsets, Graph coloring, Hamiltonian Cycle , 0/1 Knapsack Problem..
V	BRANCH AND BOUND	8
	The method, Control abstractions for Least Cost Search, Bounding, FIFO branch and bound, LC branch and bound, 0/1 Knapsack problem – LC branch and bound and FIFO branch and bound solution, Traveling sales person problem.
VI	COMPUTATIONAL COMPLEXITY AND PARALLEL ALGORITHMS	8
	Computational Complexity: Non Deterministic algorithms, The classes: P, NP, NP omplete, NP Hard, Satisfiability problem, Proofs for NP Complete Problems: Clique, Vertex Cover. Parallel Algorithms: Introduction, models for parallel computing, computing with omplete binary tree, Pointer doubling algorithm.