KTU 2024 Scheme · Semester 6 · Program Core — Artificial Intelligence and Data Science
Design and Analysis of Algorithms (PCCRT602) Syllabus
Official KTU 2024 Scheme syllabus for Design and Analysis of Algorithms, Semester 6, Program Core — Artificial Intelligence and Data Science (Artificial Intelligence and Data Science).
Course Code
PCCRT602
Credits
4
Teaching Hours
3:1:0:0 (L:T:P:R)
CIE Marks
40
ESE Marks
60
Exam Duration
2 Hrs 30 Min
Prerequisites
PCCST303
Semester
Semester 6
Course Objective
To gain a foundational understanding of algorithms and their analysis, to develop problem-solving skills using algorithm design paradigms like divide and conquer and dynamic programming, and to understand tractable and intractable problems and the complexity classes P, NP, NP-hard and NP-complete.
Module-wise Syllabus
Module 1
11 contact hoursAlgorithms — characteristics, criteria for analysing algorithms; time and space complexity — best, worst and average case complexities; asymptotic notations and their properties; time and space complexity calculation of simple algorithms. Analysis of recursive algorithms — recurrence equations, solution by the iteration method, recursion tree method, substitution method and Master's theorem (proof not expected). Balanced search trees — AVL trees (insertion and deletion with all rotations in detail, algorithms not expected).
Module 2
11 contact hoursDisjoint sets — disjoint set operations, union and find algorithms, analysis of union by rank with path compression, connected components of a graph. Graphs — representations, traversals: BFS, DFS and their analysis, strongly connected components, topological sorting. Divide and conquer strategy — control abstraction, merge sort, Strassen's matrix multiplication, analysis.
Module 3
11 contact hoursGreedy strategy — control abstraction, fractional knapsack; minimum cost spanning tree — Kruskal's and Prim's algorithms, analysis; shortest path problem — Dijkstra's algorithm, analysis. Dynamic programming — control abstraction, optimality principle, matrix chain multiplication, analysis; all pairs shortest path — Floyd-Warshall algorithm, analysis. Backtracking — control abstraction, N-Queens problem, algorithm.
Module 4
11 contact hoursBranch and bound — control abstraction, Travelling Salesman Problem, algorithm. Complexity — tractable and intractable problems; complexity classes P, NP, NP-hard and NP-complete; NP-completeness proofs — clique problem and vertex cover problem. Approximation algorithms — bin packing. Randomized algorithms — definitions of Monte Carlo and Las Vegas algorithms, randomized quick sort with analysis.
Course Outcomes
- CO1Analyse any given algorithm and express its time and space complexities in asymptotic notation.
- CO2Solve recurrence equations using the iteration, recursion tree, substitution and Master's methods to compute the time complexity of algorithms.
- CO3Illustrate the operations of advanced data structures like AVL trees and disjoint sets.
- CO4Illustrate the representation, traversal and different operations on graphs.
- CO5Demonstrate divide-and-conquer, greedy, dynamic programming, branch-and-bound and backtracking algorithm design techniques.
- CO6Classify a problem as computationally tractable or intractable, and discuss strategies to address intractability.
Assessment Pattern (CIE: 40 marks, ESE: 60 marks)
Continuous Internal Evaluation (CIE)
| Attendance | 5 |
| Assignment / Microproject | 15 |
| Internal Examination 1 (Written) | 10 |
| Internal Examination 2 (Written) | 10 |
End Semester Examination (ESE)
Total 60 marks, 2 Hrs 30 Min. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.
Textbooks & Reference Books
Textbooks
- Introduction to Algorithms — T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (Prentice-Hall India, 4th edition, 2018)
- Fundamentals of Computer Algorithms — Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran (Orient Longman Universities Press, 2nd edition, 2008)
- Computer Algorithms: Introduction to Design and Analysis — Sara Baase, Allen Van Gelder (Pearson Education, 3rd edition, 2009)
Reference Books
- Design and Analysis of Algorithms — Michael T. Goodrich, Roberto Tamassia (Wiley, 1st edition, 2021)
- Algorithm Design — Jon Kleinberg, Eva Tardos (Pearson Education, 1st edition, 2005)
- Algorithms — Robert Sedgewick, Kevin Wayne (Pearson Education, 4th edition, 2011)
- Fundamentals of Algorithmics — Gilles Brassard, Paul Bratley (Pearson Education, 1st edition, 1996)
- The Algorithm Design Manual — Steven S. Skiena (Springer, 2nd edition, 2008)
Frequently Asked Questions
How many credits is KTU Design and Analysis of Algorithms (PCCRT602)?
4 credits, with 3:1:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.
How many modules are in the PCCRT602 syllabus?
4 modules, 44 total contact hours.
What is the CIE and ESE mark split for this course?
CIE (Continuous Internal Evaluation): 40 marks. ESE (End Semester Examination): 60 marks, 2 Hrs 30 Min. Total: 100 marks.
What are the recommended textbooks for PCCRT602?
Introduction to Algorithms (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein); Fundamentals of Computer Algorithms (Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran); Computer Algorithms: Introduction to Design and Analysis (Sara Baase, Allen Van Gelder).
Is this syllabus specific to one branch, or common to others too?
This Semester 6 course is listed under Program Core — Artificial Intelligence and Data Science at KTU under the 2024 Scheme — check the course header above for which branches it's common to.
Need help with KTU Design and Analysis of Algorithms?
Learnizo offers live, 1-on-1 online tuition for KTU AI&DS subjects — matched to your exact module and semester.