KTU 2024 Scheme · Semester 6 · Program Elective III — Computer Science and Engineering
Randomized Algorithms (PECST639) Syllabus
Official KTU 2024 Scheme syllabus for Randomized Algorithms, Semester 6, Program Elective III — Computer Science and Engineering (Computer Science and Engineering).
Course Code
PECST639
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
GAMAT301, PCCST302
Semester
Semester 6
Course Objective
To equip learners with the knowledge and skills to design and analyze algorithms that leverage randomness to improve performance, solve complex problems and achieve better average-case or worst-case guarantees, and to provide a deep understanding of advanced randomization techniques and their applications in hashing, graph algorithms, the probabilistic method and complexity theory.
Module-wise Syllabus
Module 1
9 contact hoursBasics of randomization: introduction to randomized algorithms, probabilistic analysis and expectations, benefits and applications of randomization. Probability review - basic probability theory, random variables and distributions, linearity of expectation. Basic randomized algorithms - randomized quicksort, randomized selection, randomized data structures.
Module 2
9 contact hoursRandomized graph algorithms: randomized algorithms for graph problems, minimum cut problems, randomized algorithms for network flows. Hashing and randomized data structures - universal and perfect hashing, skip lists, Bloom filters. Markov chains and random walks - introduction to Markov chains, random walks on graphs, applications in randomized algorithms.
Module 3
9 contact hoursThe probabilistic method: basics of the probabilistic method, linearity of expectation, first and second moment methods. Chernoff bounds and concentration inequalities - Markov's inequality, Chebyshev's inequality, Chernoff bounds, applications of concentration inequalities.
Module 4
9 contact hoursRandomized rounding and martingales: randomized rounding techniques, applications in approximation algorithms, introduction to martingales, Azuma's inequality. Randomized complexity classes - RP, ZPP and BPP, relationships between complexity classes, amplification and derandomization techniques.
Course Outcomes
- CO1Demonstrate a strong understanding of the basics of randomized algorithms, including probabilistic analysis, expectations and the benefits of randomization.
- CO2Illustrate basic randomized algorithms such as randomized quicksort, selection and data structures, and evaluate their performance against deterministic alternatives.
- CO3Apply advanced randomized techniques, including randomized graph algorithms, hashing and Markov chains, to address complex graph and data structure problems.
- CO4Show expertise in probabilistic methods, including Chernoff bounds, concentration inequalities and randomized rounding, and use these methods to solve approximation and analysis problems in algorithms.
- CO5Understand and apply concepts related to randomized complexity classes such as RP, ZPP and BPP, and explore amplification and derandomization techniques.
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
- Randomized Algorithms — Rajeev Motwani, Prabhakar Raghavan (Cambridge University Press, 1st edition, 2004)
- Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis — Michael Mitzenmacher, Eli Upfal (Cambridge University Press, 3rd edition, 2017)
- Introduction to Algorithms — Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (MIT Press, 4th edition, 2023)
- The Probabilistic Method — Noga Alon, Joel H. Spencer (Wiley-Blackwell, 4th edition, 2016)
- Approximation Algorithms — Vijay V. Vazirani (Springer Nature (SIE), 2nd edition, 2013)
- Computational Complexity: A Modern Approach — Sanjeev Arora, Boaz Barak (Cambridge University Press, 1st edition, 2019)
Reference Books
- Concentration of Measure for the Analysis of Randomized Algorithms — Devdatt Dubhashi, Alessandro Panconesi (Cambridge University Press, 1st edition, 2012)
- The Design of Approximation Algorithms — David Williamson, David Shmoys (Cambridge University Press, 1st edition, 2011)
- Algorithms — Robert Sedgewick, Kevin Wayne (Addison-Wesley, 4th edition, 2023)
Frequently Asked Questions
How many credits is KTU Randomized Algorithms (PECST639)?
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 PECST639 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 PECST639?
Randomized Algorithms (Rajeev Motwani, Prabhakar Raghavan); Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Michael Mitzenmacher, Eli Upfal); Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein); The Probabilistic Method (Noga Alon, Joel H. Spencer); Approximation Algorithms (Vijay V. Vazirani); Computational Complexity: A Modern Approach (Sanjeev Arora, Boaz Barak).
Is this syllabus specific to one branch, or common to others too?
This Semester 6 course is listed under Program Elective III — Computer Science and Engineering at KTU under the 2024 Scheme — check the course header above for which branches it's common to.
Need help with KTU Randomized Algorithms?
Learnizo offers live, 1-on-1 online tuition for KTU CSE subjects — matched to your exact module and semester.