KTU 2024 Scheme · Semester 5 · Program Core — Information Technology
Algorithm Analysis and Design (PCITT502) Syllabus
Official KTU 2024 Scheme syllabus for Algorithm Analysis and Design, Semester 5, Program Core — Information Technology (Information Technology).
Course Code
PCITT502
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
Data Structures (PCITT303)
Semester
Semester 5
Course Objective
To understand and apply fundamental algorithmic concepts, and to master algorithm design paradigms and complexity analysis.
Module-wise Syllabus
Module 1
11 contact hoursAlgorithms — properties of a good algorithm, 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 of recurrence equations — iteration method, recursion tree method, substitution method and Master's theorem (proof not required). Amortized complexity — aggregate analysis, cost-accounting and potential methods.
Module 2
11 contact hoursBalanced search trees — AVL trees (insertion and deletion operations with all rotations in detail, algorithms not expected); Red Black trees — properties. 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.
Module 3
11 contact hoursDivide and conquer — control abstraction, finding minimum and maximum, Quicksort, Merge Sort, Strassen's matrix multiplication, analysis. Greedy algorithms: control abstraction, fractional knapsack, minimum cost spanning tree — Kruskal's and Prim's, analysis, job sequencing with deadlines. Dynamic programming: control abstraction, optimality principle, DP solution for Travelling Salesman Problem and 0/1 Knapsack Problem. Backtracking: control abstraction, N-Queens problem, algorithm.
Module 4
11 contact hoursBranch and bound: control abstraction, FIFO, LIFO and LC branch and bound, 15-puzzle problem. String matching — KMP algorithm, Rabin-Karp algorithm. Tractable and intractable problems, complexity classes — P, NP, NP-Hard and NP-Complete classes. Approximation algorithms — planar graph coloring, vertex cover.
Course Outcomes
- CO1Explain asymptotic notations used in the performance analysis of algorithms, solve recurrence equations and study the amortized analysis.
- CO2Apply divide and conquer strategy to solve practical problems efficiently.
- CO3Apply greedy and dynamic programming techniques in algorithm design.
- CO4Apply backtracking and branch and bound techniques in algorithm design.
- CO5Explain Balanced Search Trees, Graph Traversals, and sophisticated algorithms such as string matching and approximation algorithms.
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, 2nd edition, 2001)
- 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
- Algorithm Design — Jon Kleinberg and Éva Tardos (Pearson, 1st edition, 2005)
- Algorithms — Robert Sedgewick and Kevin Wayne (Addison-Wesley, 4th edition, 2011)
- Computers and Intractability: A Guide to the Theory of NP-Completeness — Michael R. Garey and David S. Johnson (W. H. Freeman, 1st edition, 1979)
Frequently Asked Questions
How many credits is KTU Algorithm Analysis and Design (PCITT502)?
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 PCITT502 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 PCITT502?
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 Program Core — Information Technology at KTU under the 2024 Scheme — check the course header above for which branches it's common to.
Need help with KTU Algorithm Analysis and Design?
Learnizo offers live, 1-on-1 online tuition for KTU IT subjects — matched to your exact module and semester.