Sign In With Google
Course Description
-
Course Name
Computation & Complexity
-
Host University
Maynooth University
-
Location
Dublin, Ireland
-
Area of Study
Computer Science
-
Language Level
Taught In English
-
Prerequisites
CS151 or equivalent
Co-Requisites: CS210 or equivalent
-
Course Level Recommendations
Upper
ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.
-
ECTS Credits
5 -
Recommended U.S. Semester Credits2
-
Recommended U.S. Quarter Units3
Hours & Credits
-
Overview
Computability theory: Turing machines and Church Turing thesis, decidable and recognisable languages, proofs of undecidability, Turing and many-one reducibility, Rice's theorem, the recursion theorem. Computational complexity: measures of complexity and asymptotic analysis. Complexity classes, P and NP; intra-class reductions; complexity analysis (best, worst, average case) of algorithms. More complexity classes, nondeterminism; NP-hardness, NP-completeness.
Course Disclaimer
Courses and course hours of instruction are subject to change.
Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.
ECTS (European Credit Transfer and Accumulation System) credits are converted to semester credits/quarter units differently among U.S. universities. Students should confirm the conversion scale used at their home university when determining credit transfer.
Please reference fall and spring course lists as not all courses are taught during both semesters.
Please note that some courses with locals have recommended prerequisite courses. It is the student's responsibility to consult any recommended prerequisites prior to enrolling in their course.