Chat with us on WhatsAppCall Learnizo

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).

This page compiles APJ Abdul Kalam Technological University's officially published 2024 Scheme syllabus for Artificial Intelligence and Data Science, Semester 6, sourced directly from KTU's official website (ktu.edu.in). Learnizo is an independent online tuition platform and is not affiliated with, endorsed by, or officially connected to APJKTU. The university may revise syllabus content after this page was last updated — always cross-check with the official KTU source for the current, authoritative version.

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 hours

Algorithms — 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 hours

Disjoint 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 hours

Greedy 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 hours

Branch 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)

Attendance5
Assignment / Microproject15
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.