Algorithm Analysis and Design for GTU 24 Course (V - IT - BE05016011) & Analysis and Design of Algorithms for GTU 24 Course (V - AI&DS/Prof. Elec.-II - BE05000141)

Syllabus Algorithm Analysis and Design - (BE05016011) (IT) Total Credits = TH/30 Assessment Pattern and Marks Total Marks Theory Tutorial / Practical ESE(E) PA(M) PA(I) PBL (I) ESE (V) 04 70 30 20 30 50 200 Unit No. Content 1. Introduction and Analysis of Algorithm : What is an algorithm?, Properties of good algorithm, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations, The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations (Big Oh, Big Theta, Big Omega), Analyzing control statement, Loop invariant and the correctness of the algorithm, Disjoint set operations, Union and find algorithms. (Chapter - 1) 2. Analysis of Sorting Algorithms : Comparison based sorting : Bubble sort, Selection sort, Insertion sort, Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort. (Chapter - 2) 3. Divide and Conquer : Introduction, General method, Recurrence and different methods to solve recurrence, Problem solving using Divide and Conquer : Binomial Coefficient, Binary Search, Max-Min problem, Merge Sort, Quick Sort, Strassen’s algorithm for Matrix Multiplication, Exponential. (Chapter - 3) 4. Dynamic Programming : Introduction, General method, Elements of Dynamic Programming, The Principle of Optimality Problem Solving using Dynamic Programming : Making Change Problem, Knapsack problem, Multi stage graph, Matrix chain multiplication, Longest Common Subsequence, Shortest Common Super sequence. (Chapter - 4) 5. Greedy Algorithm : Introduction, General method, Characteristics of greedy algorithms, Elements of greedy strategy Problem solving using Greedy method : Making change problem, Activity selection problem, Knapsack problem (0/1 and Fractional), Job Scheduling Problem, Huffman Trees. (Chapter - 5) 6. Graph Algorithms : Introduction, Types of graph, Representation Graph, Traversing Graphs : Depth First Search, and Breath First Search, Topological sort, Strongly Connected components. Problems solving : Finding articulation point, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm) using greedy approach, Dijkstra's Algorithm , Single pair shortest path using greedy method, All Points Shortest path using Dynamic Programming, (Chapter - 6) 7. Backtracking : Introduction, General method, n-queen problem, Sum of subset problem, Graph coloring problem, Hamiltonian cycle problem, Branch and Bound : General method, LC branch and bound, FIFO branch and bound, Traveling salesman problem. (Chapter - 7) 8. Introduction to NP-Completeness : The class P and NP, Polynomial reduction, NP- Complete Problems, NP-Hard Problems. Approximation Algorithm : TSP Randomized Algorithm : Quick sort. (Chapter - 8) Syllabus Analysis and Design of Algorithms - (BE05000141) (AI&DS) Total Credits Assessment Pattern and Marks Total Marks TH/30 Theory Practical ESE(E) PA(M) PA(I) PBL(I) ESE(V) 3 70 30 20 30 50 200 Unit No. Content 1. Introduction and Analysis of Algorithm : Introduction to algorithm, Properties of good algorithm, Average, Best and worst case analysis, Asymptotic Notations (Big Oh, Big Theta, Big Omega), Disjoint set operations, Union and find algorithms. (Chapter - 1) 2. Analysis of Sorting Algorithms : Comparison based sorting : Bubble sort, Selection sort, Insertion sort, Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort. (Chapter - 2) 3. Divide and Conquer : Introduction, General method, Recurrence and different methods to solve recurrence, Problem solving using Divide and Conquer : Binomial Coefficient, Binary Search, Max-Min problem, Merge Sort, Quick Sort, Strassen’s algorithm for Matrix Multiplication, Exponential. (Chapter - 3) 4. Dynamic Programming : Introduction, General method, Elements of Dynamic Programming, The Principle of Optimality Problem Solving using Dynamic Programming : Making Change Problem, Knapsack problem, Multi stage graph, Matrix chain multiplication, Longest Common Subsequence, Shortest Common Supersequence. (Chapter - 4) 5. Greedy Algorithm : Introduction, General method, Characteristics of greedy algorithms, Elements of greedy strategy. Problem solving using Greedy method : Making change problem, Activity selection problem, Knapsack problem (0/1 and Fractional), Job Scheduling Problem, Huffman Trees. (Chapter - 5) 6. Graph Algorithms : Introduction, Types of graph, Representation Graph, Traversing Graphs : Depth First Search, and Breath First Search, Topological sort, Strongly Connected components. Problems solving : Finding articulation point, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm) using greedy approach, Dijkstra's Algorithm , Single pair shortest path using greedy method, All Points Shortest path using Dynamic Programming, (Chapter - 6) 7. Backtracking : Introduction, General method, n-queen problem, Sum of subset problem, Graph coloring problem, Hamiltonian cycle problem, Branch and Bound : General method, LC branch and bound, FIFO branch and bound, Traveling salesman problem. (Chapter - 7) 8. Introduction to NP-Completeness : The class P and NP, Polynomial reduction, NP- Complete Problems, NP-Hard Problems. Approximation Algorithm : TSP Randomized Algorithm : Quick sort. (Chapter - 8)

Read More