About Subject

Pattern / Course2015 Course
Year & BranchTE (Information Technology)
Semester I/IIII
Course codeC311(304452)
Course titleDesign and Analysis of Algorithms
Teaching Scheme (Lect / Tut /  Pract)Lectures: 4 Hrs/ Week
Examination SchemeIn semester Assessment: 30 End Semester Assessment : 70 Total marks: 100

Course Objectives

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

Course Outcomes

CO1Identify the basic properties of algorithm and analyze it using different methods. and design paradigm for solving a few example problems and analyze them.
CO2Design 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.
CO3Apply dynamic programming paradigm to solve travelling sales person problem,0/1 knapsack problem, Optimal binary search tree.
CO4Apply traversal methods on search trees and search methods on graphs and backtracking search methods on state space trees for few example problems.
CO5Analyze branch and Bound search methods through problems such as 0/1 knapsack problem, Travelling sales person problem
CO6Evaluate P ,NP,NP hard, NP complete class of problems and algorithms

Syllabus

UnitContentHrs
IINTRODUCTION8
 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).. 
IIDIVIDE AND CONQUER AND GREEDYMETHOD8
 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. 
IIIDYNAMIC PROGRAMMING8
 General strategy, Principle of optimality, 0/1 knapsack Problem, Bellman-Ford Algorithm , Multistage Graph problem, Optimal Binary Search Trees, Travelling Salesman Problem. 
IVBACKTRACKING8
 General method, Recursive backtracking algorithm, Iterative backtracking method. 8-Queen problem, Sum of subsets, Graph coloring, Hamiltonian Cycle , 0/1 Knapsack Problem.. 
VBRANCH AND BOUND8
 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. 
VICOMPUTATIONAL COMPLEXITY AND PARALLEL ALGORITHMS8
 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.