KTU 2024 Scheme · Semester 4 · Program Elective I — Artificial Intelligence
Algorithm Analysis and Design (PECAT415) Syllabus
Official KTU 2024 Scheme syllabus for Algorithm Analysis and Design, Semester 4, Program Elective I — Artificial Intelligence (Artificial Intelligence).
Course Code
PECAT415
Credits
3
Teaching Hours
3:0:0:0 (L:T:P:R)
CIE Marks
40
ESE Marks
60
Exam Duration
2 Hrs. 30 Min.
Prerequisites
PCCST303
Semester
Semester 4
Course Objective
To impart the concept of time complexity, space complexity, and other metrics to evaluate the performance of algorithms. To quip the learners to design and implement efficient algorithms using various techniques such as divide and conquer, dynamic programming, and greedy algorithms. To teach the complexity classes and the limitations and capabilities of different algorithmic approaches.
Module-wise Syllabus
Module 1
9 contact hoursIntroduction to Algorithm Analysis:- Characteristics of Algorithms, Criteria for Analysing Algorithms, Time and Space Complexity - Best, Worst and Average Case Complexities, Asymptotic Notations - Big-Oh (O), Big - Omega (Ω), Big-Theta (Θ), Little-oh (o) and Little- Omega (ω) and their properties. Classifying functions by their asymptotic growth rate, Time and Space Complexity Calculation of simple algorithms. Analysis of Recursive Algorithms: Recurrence Equations, Solving Recurrence Equations - Iteration Method, Recursion Tree Method, Substitution method and Master's Theorem (Proof not required).
Module 2
9 contact hoursDivide & Conquer and Greedy Strategy:- General method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum, Merge sort, Strassen's matrix multiplication, Advantages and Disadvantages of divide and conquer; Decrease and Conquer Approach - Topological Sort; The Control Abstraction of Greedy Strategy- Fractional Knapsack Problem, Minimum Cost Spanning Tree Computation - Kruskal's Algorithms, Analysis; Single Source Shortest Path Algorithm - Dijkstra's Algorithm, Analysis.
Module 3
9 contact hoursDynamic Programming - General method with Examples, Multistage Graphs; Transitive Closure - Warshall's Algorithm; All Pairs Shortest Paths - Floyd's Algorithm, Optimal Binary Search Trees; Knapsack problem; Bellman-Ford Algorithm; Travelling Salesperson Problem; Reliability design.
Module 4
9 contact hoursBacktracking and Branch & Bound:- Backtracking - General method, N-queen problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles. Branch and Bound - General method, Travelling Salesperson Problem, 0/1 knapsack problem, LC branch and bound solution, FIFO branch and bound solution.
Course Outcomes
- CO1Explain the characteristics of algorithms and apply various criteria to analyze them, including time and space complexity and asymptotic notations.
- CO2Implement divide and conquer algorithms such as binary search, merge sort, and Strassen's matrix multiplication, and analyze their recurrence equations and performance.
- CO3Design greedy algorithms for optimization problems, such as the fractional knapsack problem and minimum cost spanning trees using Kruskal's algorithm, and evaluate their efficiency.
- CO4Develop dynamic programming solutions for various problems, including multistage graphs, shortest path algorithms, and the traveling salesperson problem, and analyze their computational complexity.
- CO5Solve complex computational problems using backtracking and branch & bound techniques, including the n-queen problem, sum of subsets problem, and 0/1 knapsack problem.
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 — Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (MIT Press, 3/e, 2009)
- Fundamentals of Computer Algorithms — Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran (Orient Longman Universities Press, 2/e,2008)
- Computer Algorithms, Introduction to Design and Analysis — Sara Baase and Allen Van Gelder (Pearson Education, 3/e, 2009)
Reference Books
- The Algorithm Design Manual — Steven S. Skiena (Springer, 2/e, 2008)
- Algorithms — Robert Sedgewick, Kevin Wayne (Pearson, 4/e, 2011)
- Algorithm Design — Jon Kleinberg, Eva Tardos (Pearson, 1/e, 2005)
- Fundamentals of Algorithmic — Gilles Brassard, Paul Brately (Pearson, 1/e, 1996)
Frequently Asked Questions
How many credits is KTU Algorithm Analysis and Design (PECAT415)?
3 credits, with 3:0:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.
How many modules are in the PECAT415 syllabus?
4 modules, 36 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 PECAT415?
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford 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 4 course is listed under Program Elective I — Artificial Intelligence 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 AI subjects — matched to your exact module and semester.