CS811PE: Computational Complexity CSE Syllabus for B.Tech 4th Year 2nd Sem R18 Regulation JNTUH (Professional Elective-6)

Computational Complexity detailed syllabus for Computer Science Engineering (CSE), R18 regulation has been taken from the JNTUHs official website and presented for the students of B.Tech Computer Science Engineering branch affiliated to JNTUH course structure. For Course Code, Course Titles, Theory Lectures, Tutorial, Practical/Drawing, Credits, and other information do visit full semester subjects post given below. The syllabus PDF files can also be downloaded from the universities official website.

For all the other CSE 4th Year 2nd Sem Syllabus for B.Tech R18 Regulation JNTUH scheme, visit Computer Science Engineering 4th Year 2nd Sem R18 Scheme.

For all the (Professional Elective-6) subjects refer to Professional Elective-6 Scheme. The detail syllabus for computational complexity is as follows.

Pre-requisites:

1. A course on �Computer Programming and Data Structures�
2. A course on �Discrete Structures and Graph Theory�

Course Objective:

For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.

Course Outcome:

• Ability to classify decision problems into appropriate complexity classes
• Ability to specify what it means to reduce one problem to another, and construct reductions for simple examples.
• Ability to classify optimization problems into appropriate approximation complexity classes
• Ability to choose appropriate data structure for the given problem
• Ability to choose and apply appropriate design method for the given problem

Unit – I

Computational Complexity: Polynomial time and its justification, Nontrivial examples of polynomial-time algorithms, the concept of reduction (reducibility), Class P Class NP and NP- Completeness, The P versus NP problem and why it�s hard

Unit – II

For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.

Unit – III

Randomized Algorithms: Finger Printing, Pattern Matching, Graph Problems, Algebraic Methods, Probabilistic Primality Testing, De-Randomization Advanced Algorithms.

Unit – IV

Graph Algorithms: Shortest paths, Flow networks, Spanning Trees; Approximation algorithms, Randomized algorithms. Approximation algorithms: Polynomial Time Approximation Schemes.

Unit – V

For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.

Text Books:

1. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Third Edition, McGraw-Hill, 2009.
2. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
3. J. J. McConnell, Analysis of Algorithms: An Active Learning Approach, Jones and Bartlett Publishers, 2001.
4. D. E. Knuth, Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition, Addison-Wesley Professional, 1998.
5. S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.

For detail syllabus of all other subjects of B.Tech Computer Science Engineering 4th Year 2nd Sem , visit CSE 4th Year 2nd Sem syllabus subjects.

For B.Tech Computer Science Engineering (CSE) 4th Year results, visit JNTUH B.Tech Computer Science Engineering semester results direct link.