Course Code 21CS42 CIE Marks 50
Teaching Hours/Week (L:T:P: S) 3:0:2:0 SEE Marks 50
Total Hours of Pedagogy 40 T + 20 P Total Marks 100
Credits 04 Exam Hours 03
Course Learning Objectives:
CLO 1. Explain the methods of analysing the algorithms and to analyse performance of algorithms.
CLO 2. State algorithm’s efficiencies using asymptotic notations.
CLO 3. Solve problems using algorithm design methods such as the brute force method, greedy method, divide and conquer, decrease and conquer, transform and conquer, dynamic programming, backtracking and branch and bound.
CLO 4. Choose the appropriate data structure and algorithm design method for a specified application.
CLO 5. Introduce P and NP classes.
Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework- Time efficiency and space efficiency, Worst-case, Best-case and Average case efficiency. Performance Analysis: Estimating Space complexity and Time complexity of algorithms. Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation ( ) with examples, Basic efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples. Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity Analysis. Textbook 1: Chapter 1 (Sections 1.1,1.2), Chapter 2(Sections 2.1,2.2,2.3,2.4), Chapter 3(Section3.1,3.2)Textbook 2: Chapter 1(section 1.1,1.2,1.3)
Notes/PPT : Notes/PPT
Laboratory Component:
1. Sort a given set of n integer elements using Selection Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the brute force method works along with its time complexity analysis: worst case, average case and best case. Program
Divide and Conquer: General method, Recurrence equation for divide and conquer, solving it using Master’s theorem. , Divide and Conquer algorithms and complexity Analysis of Finding the maximum & minimum, Binary search, Merge sort, Quick sort. Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms, Topological Sorting. It’s efficiency analysis. Textbook 2: Chapter 3(Sections 3.1,3.3,3.4,3.5,3.6) Textbook 1: Chapter 4 (Sections 4.1,4.2,4.3), Chapter 5(Section 5.1,5.2,5.3)
Notes/PPT : Notes/PPT
Laboratory Component:
1. Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case. Program
2. Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case. Program
Greedy Method: General method, Coin Change Problem, Knapsack Problem, solving Job sequencing with deadlines Problems. Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm with performance analysis. Single source shortest paths: Dijkstra's Algorithm. Optimal Tree problem: Huffman Trees and Codes. Transform and Conquer Approach: Introduction, Heaps and Heap Sort. Textbook 2: Chapter 4(Sections 4.1,4.3,4.5) Textbook 1: Chapter 9(Section 9.1,9.2,9.3,9.4), Chapter 6( section 6.4)
Notes/PPT : Notes/PPT
Laboratory Component:
Write & Execute C++/Java Program
1. To solve Knapsack problem using Greedy method. Program
2. To find shortest paths to other vertices from a given vertex in a weighted connected graph, using Dijkstra's algorithm. Program
3. To find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal's algorithm. Use Union-Find algorithms in your program. Program
4. To find Minimum Cost Spanning Tree of a given connected undirected graph using Prim's algorithm. Program
Dynamic Programming: General method with Examples, Multistage Graphs. Transitive Closure: Warshall’s Algorithm. All Pairs Shortest Paths: Floyd's Algorithm, Knapsack problem, Bellman-Ford Algorithm, Travelling Sales Person problem. Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching- Harspool’s algorithm. Textbook 2: Chapter 5 (Sections 5.1,5.2,5.4,5.9) Textbook 1: Chapter 8(Sections 8.2,8.4), Chapter 7 (Sections 7.1,7.2)
Notes/PPT : Notes/PPT
Laboratory Component:
Write C++/ Java programs to
1. Solve All-Pairs Shortest Paths problem using Floyd's algorithm. Program
2. Solve Travelling Sales Person problem using Dynamic programming. Program
3. Solve 0/1 Knapsack problem using Dynamic Programming method. Program
Backtracking: General method, solution using back tracking to N-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles Problems. Branch and Bound: Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem NP-Complete and NP-Hard problems: Basic concepts, non- deterministic algorithms, P, NP, NP- Complete, and NP-Hard classes. Textbook 1: Chapter 12 (Sections 12.1,12.2) Chapter 11(11.3) Textbook 2: Chapter 7 (Sections 7.1,7.2,7.3,7.4,7.5) Chapter 11 (Section 11.1)
Notes/PPT : Notes/PPT
Laboratory Component:
1. Design and implement C++/Java Program to find a subset of a given set S = {Sl, S2,..., Sn} of n positive integers whose SUM is equal to a given positive integer d. For example, if S = {1, 2, 5, 6, 8} and d= 9, there are two solutions {1, 2, 6} and {1, 8}. Display a suitable message, if the given problem instance doesn't have a solution. Program
2. Design and implement C++/Java Program to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using backtracking principle. Program
Course Outcomes:
At the end of the course the student will be able to:
CO 1. Analyze the performance of the algorithms, state the efficiency using asymptotic notations and analyze mathematically the complexity of the algorithm.
CO 2. Apply divide and conquer approaches and decrease and conquer approaches in solving the problems analyze the same
CO 3. Apply the appropriate algorithmic design technique like greedy method, transform and conquer approaches and compare the efficiency of algorithms to solve the given problem.
CO 4. Apply and analyze dynamic programming approaches to solve some problems. and improve an algorithm time efficiency by sacrificing space.
CO 5. Apply and analyze backtracking, branch and bound methods and to describe P, NP and NPComplete problems.
Suggested Learning Resources:
Textbooks
1. Introduction to the Design and Analysis of Algorithms, Anany Levitin: 2nd Edition, 2009. Pearson.
2. Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014, Universities Press.
Reference Books
1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.
2. Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)
Weblinks and Video Lectures (e-Resources):
1. http://elearning.vtu.ac.in/econtent/courses/video/CSE/06CS43.html
2. https://nptel.ac.in/courses/106/101/106101060/
3. https://www.youtube.com/watch?v=mB5HXBb_HY8
4. https://www.youtube.com/watch?v=FtN3BYH2Zes
5. https://www.youtube.com/watch?v=TU52VhL0wTQ