Syllabus
Professional Electives
Other Branches
Unit I
Introduction and Review- Algorithms vs. programs. Flow charts and pseudo code, Rate of growth of functions. 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 and Binary search type strategies, Pivot based strategies – Long integer multiplication – Maximum sub array sum – Closest Pair problem etc as examples. Greedy Algorithm – Introduction to the method, Fractional Knapsack problem, Task Scheduling Problem, Huffman coding etc as examples. Dynamic Programming: Introduction to the method, Fibonacci numbers, 0-1 Knapsack problem, Matrix chain multiplication problem, Longest Common Subsequence, 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, NP complete, NP hard, Examples of P and NP.
Objectives and Outcomes
Pre-Requisite(s): Data Structures and Algorithms
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: Understand and 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 problem by mapping to classical problems.
CO5: Analyze the impact of various implementation choices on the algorithm complexity.
CO-PO Mapping
|
PO/PSO
|
PO1
|
PO2
|
PO3
|
PO4
|
PO5
|
PO6
|
PO7
|
PO8
|
PO9
|
PO10
|
PO11
|
PO12
|
PSO1
|
PSO2
|
|
CO
|
|
CO1
|
2
|
3
|
1
|
1
|
1
|
|
|
|
|
|
|
|
3
|
2
|
|
CO2
|
3
|
2
|
2
|
|
1
|
|
|
|
|
|
|
|
3
|
2
|
|
CO3
|
3
|
2
|
3
|
2
|
|
|
|
|
|
|
|
|
3
|
2
|
|
CO4
|
2
|
2
|
3
|
2
|
|
|
|
|
|
|
|
|
3
|
2
|
|
CO5
|
2
|
2
|
3
|
1
|
|
|
|
|
|
|
|
|
3
|
2
|
Evaluation Pattern
Evaluation Pattern: 70:30
|
Assessment
|
Internal
|
End Semester
|
|
MidTerm Exam
|
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/ project presentation
Text Books / References
Textbook(s)
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein. “Introduction to Algorithms”. Third Edition, Prentice Hall of India Private Limited; 2009.
Reference(s)
Michael T Goodrich and Roberto Tamassia. “Algorithm Design Foundations – Analysis and Internet Examples”. John Wiley and Sons, 2007.
Dasgupta S, Papadimitriou C and Vazirani U. “Algorithms”. Tata McGraw-Hill; 2009.
Jon Kleinberg, Eva Tardos. “Algorithm Design”. First Edition, Pearson Education India; 2013.
