Syllabus (COMPUTER APPLICATION)

Course Type: MAJ-7

Semester: 5

Course Code: BBCAMAJ07C

Course Title: Design and Analysis of Algorithm

(L-P-Tu): 4-2-0

Credit: 6

Practical/Theory: Combined

Course Objective: Course Objectives: The educational Objectives of this Course are: To Introduce various designing techniques and methods for algorithms Performance analysis of Algorithms using asymptotic and empirical approaches Demonstrate a familiarity with major algorithms and data structures. To give clear idea on algorithmic design paradigms like Divide-and-Conquer, Dynamic Programming, Greedy, Branch and Bound etc.

Learning Outcome: Course Outcomes: On successful completion of the course, the student will: Understand the concept of pseudo code for writing an algorithm and acquire ability to analyze the asymptotic performance of various algorithms. Explore the concept of trees and graphs and get familiarity of analysis of various graph, tree traversal algorithms. Understand algorithm designing techniques such as Greedy approach Dynamic programming and explore to various related application problems. Synthesize efficient algorithm design paradigms back tracking, Branch & Bound in solving common analytical problems. Understand the variations among tractable and intractable problems and able to classify P and NP classes.

Syllabus:

Unit I: Theory Credit: 4 (L 60)

Introduction to Algorithm: Definitions, Correctness of Algorithm, Basics of Recursive and Non- Recursive algorithms. [L 6]

Analysis of Algorithms: Orders of Magnitude (Asymptotic notations), Growth rates, some common bounds (constant, logarithmic, linear, polynomial, exponential), Average and Worst case analysis, Analyzing control statements, Recurrence Relations- substitution, change of variables, master’s method, Analysis of Sorting and Searching Algorithm (Bubble Sort, Insertion Sort, Linear Search). [L 12]

Divide and conquer algorithms: Introduction, Worst and Average case complexity of Quick Sort and Merge sort, Analysis of binary search tree. [L 6]

Greedy algorithms: General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm- Activity selection problem, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, Floyd Warshall Algorithm, Dijkstra Algorithm, The Knapsack Problem. [L 8]

Dynamic programming: Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming- Making Change Problem, 0/1 Knapsack problem, Matrix chain multiplication, Longest common Subsequence. [L 8]

Graph Algorithms: An introduction using graphs and games, Traversing Trees– Pre conditioning, Depth First Search, Undirected Graph, Directed Graph, Breath First Search, Backtracking–The Knapsack Problem, The Eight queens’ problem. [L 8]

String matching: Introduction, The naive string-matching algorithm, The Rabin-Karp algorithm. [L 6]

Introduction to Complexity Theory: The class P and NP, Polynomial reduction, NP- Complete Problems, NP-Hard Problems. [L 6]

Unit II: Design and Analysis of Algorithm Lab Credit: 2 (L 60)

Divide and Conquer Approach (Merge Sort, Quick Sort, Binary Search), Greedy Approach (Making Change Problem, Knapsack Problem), Dynamic Programming (Knapsack Problem, Finding Optimal Matrix Chain Order Problem, Longest Common Subsequence Problem, Finding Optimal Matrix Chain Order Problem using Memorization), Graph Algorithms (Depth First Search of a graph, Breadth First Search of a graph, Kruskal’s method of finding Minimum Spanning Tree, Prim’s method of finding Minimum Spanning Tree, Dijkstra’s method of finding Single Source Shortest Paths).

Reading References:

1. Thomas H. Cormen, Introduction to Algorithms, The MIT Press.
2. J. Kleinberg, E. Tardos, Algorithm Design, 1st edition, Pearson Education India, Additional Resources.
3. Ellis Horowitz, Satraj Sahni, Sanguthevar Rajasekharan, Fundamentals of Computer Algorithms, Universities Press.
4. A. Levitin, Introduction to the Design and Analysis of Algorithms‖, Pearson Education.

Alfred V. Aho, John E. Hopcroft, Jeffrey D., The Design And Analysis Of Computer Algorithms, Pearson India.