Syllabus
Unit I
Introduction and Review-Review of Asymptotic notation: motivation and types of notations. Recurrence relations and methods to solve them: Recursion tree, substitution, Master Method. Review of Sorting: Bubble –Insertion – Selection –Bucket – Heap, Comparison of sorting algorithms, Applications. Graph Algorithms – Graph Traversal: Applications of BFS: distance, connectivity and connected components and cycles in undirected graphs. Applications of DFS: Topological sort, cycles in directed graphs, Biconnected Components and Strong Connectivity. Path algorithms: shortest path algorithms (along with analysis) SSSP: Bellman Ford. APSP: Floyd Warshall’s. Review of Minimum Spanning Tree (with analysis and applications).
Unit II
Divide and Conquer: Merge sort, Quick Sort, Quick Select and Binary search type strategies, Pivot based strategies – Long integer multiplication – Maximum sub array sum – Closest Pair problem, convex hull etc. as examples. Greedy Algorithm – Introduction, Fractional Knapsack problem, Task Scheduling Problem, Huffman coding etc as examples. Dynamic Programming: Introduction, Fibonacci numbers, 0-1 Knapsack problem, Matrix chain multiplication problem, Longest Common Subsequence, Optimal Binary search Tree and other problems including problems incorporating combinatorics as examples.
Unit III
Backtracking, Branch and Bound 0-1 Knapsack, N- Queen problem, subset sum as some examples. String Matching: Rabin Karp, Boyer Moore, KMP. Network Flow and Matching: Flow Algorithms Maximum Flow – Cuts Maximum Bipartite Matching. Introduction to NP class: Definitions P, NP, SAT problem NP complete, NP hard, Examples of P and NP.
Scalable algorithms: Blind search, heuristic searching algorithms, hill climbing algorithm, gradient descent algorithm, Parallel algorithms
Objectives and Outcomes
Pre-Requisite(s): 23CSEXXX Data structure and Algorithms, 23MATXXX Discrete Mathematics
Course Objectives
This course aims to provide the fundamentals of algorithm design and analysis, specifically in terms of algorithm design techniques, application of these design techniques for real-world problem solving and analysis of complexity and correctness of algorithms.
Course Outcomes
CO1: Evaluate the correctness and analyze complexity of algorithms.
CO2: Implement various algorithmic design techniques and solve classical problems.
CO3: Design solutions for real world problems by identifying, applying and implementing appropriate design techniques.
CO4: Design solutions for real world problems by reducing to classical problems.
CO5: Analyze the impact of various implementation choices on the algorithm complexity.
CO-PO Mapping
| CO |
PO1 |
PO2 |
PO3 |
PO4 |
PO5 |
PO6 |
PO7 |
PO8 |
PO9 |
PO10 |
PO11 |
PO12 |
PSO1 |
PSO2 |
| CO1 |
3 |
3 |
1 |
1 |
1 |
|
|
1 |
|
1 |
|
|
3 |
2 |
| CO2 |
3 |
2 |
2 |
|
0 |
|
|
1 |
|
1 |
|
|
3 |
2 |
| CO3 |
3 |
2 |
3 |
2 |
0 |
|
|
1 |
|
1 |
|
|
3 |
2 |
| CO4 |
2 |
2 |
3 |
2 |
1 |
|
|
1 |
|
1 |
|
|
3 |
2 |
| CO5 |
2 |
2 |
3 |
1 |
1 |
|
|
1 |
|
1 |
|
|
3 |
2 |
Evaluation Pattern
Evaluation Pattern: 70:30
| Assessment |
Internal |
External |
| Midterm |
20 |
|
| *Continuous Assessment Theory (CAT) |
10 |
|
| *Continuous Assessment Lab (CAL) |
40 |
|
| **End Semester |
|
30 (50 Marks; 2 hours exam) |
*CAT – Can be Quizzes, Assignments, and Reports
*CAL – Can be Lab Assessments, Project, and Report
**End Semester can be theory examination/ lab-based examination
Text Books / References
Textbook(s):
Michael T Goodrich and Roberto Tamassia, “Algorithm Design and Applications ”, John Wiley & Sons Inc, 2014
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein, “Introduction to Algorithms”, Fourth Edition, Prentice Hall of India Private Limited, 2022
Reference(s)
Dasgupta S, Papadimitriou C and Vazirani U, “Algorithms”, Tata McGraw-Hill, 2009.
Jon Kleinberg, Eva Tardos. “Algorithm Design”. First Edition, Pearson Education India; 2013.
McConnell, J. J. “Analysis of Algorithms: An Active Learning Approach”, 2nd edn. Jones & Bartlett Learning, 200
Russell, Stuart J. “Artificial intelligence a modern approach”. Pearson Education, Inc., 2010.
