KTU 2024 Scheme · Semester 5 · Common to CS/CD/CM/AM/CB/CN/CU/CG

Design and Analysis of Algorithms (PCCST502) Syllabus

Official KTU 2024 Scheme syllabus for Design and Analysis of Algorithms, Semester 5, Common to CS/CD/CM/AM/CB/CN/CU/CG (Computer Science and Engineering).

This page compiles APJ Abdul Kalam Technological University's officially published 2024 Scheme syllabus for Computer Science and Engineering, Semester 5, 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

PCCST502

Credits

Teaching Hours

3:1:0:0 (L:T:P:R)

CIE Marks

ESE Marks

Exam Duration

2 Hrs 30 Min

Prerequisites

PCCST303 (Data Structures and Algorithms)

Semester

Semester 5

Course Objective

To gain a foundational understanding of algorithms and their analysis; to develop problem-solving skills using various algorithm design paradigms like divide and conquer, dynamic programming, etc.; and to understand the concepts of tractable and intractable problems and different complexity classes (P, NP, NP-hard, 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; asymptotic notations and their properties; complexity calculation of simple algorithms; analysis of recursive algorithms — recurrence equations, solution via iteration method, recursion tree method, substitution method and Master's theorem (proof not expected); balanced search trees — AVL trees (insertion and deletion with rotations in detail, algorithms not expected).

Module 2

11 contact hours

Disjoint Sets: 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, 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 proof — clique problem and vertex cover problem. Approximation algorithms: bin packing. Randomized Algorithms: definitions of Monte Carlo and Las Vegas algorithms, randomized version of quick sort with analysis.

Course Outcomes

CO1Analyze any given algorithm and express its time and space complexities in asymptotic notations.
CO2Solve recurrence equations using iteration, recurrence tree, substitution and master's method to compute 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 strategy, 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 and 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 (PCCST502)?

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 PCCST502 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 PCCST502?

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 and Allen Van Gelder).

Is this syllabus specific to one branch, or common to others too?

This Semester 5 course is listed under Common to CS/CD/CM/AM/CB/CN/CU/CG 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 CSE subjects — matched to your exact module and semester.

Explore BTech CSE Tuition