Centralised Online Undergraduates Registration System (CORS)

      


Module Detailed Information for [CS5230]
Academic Year : 2018/2019 Semester : 2
Correct as at 14 Dec 2018 20:00

Back to Module Information Listing
Module Information
Module Code :
CS5230 IVLE LumiNUS
Module Title : Computational Complexity
Module Description : The aim of this module is to study the various measures of difficulty of problem solving in computing, and to introduce some techniques in theoretical computer science such as non-determinism, digitalisation, simulation, padding, reduction, randomisation and interaction. Topics covered include: space and time complexity - the classes P, NP, co-NP, PSPACE, EXP, etc.; tape compression; linear speedup; polynomial reduction; Cook's theorem; Savitch's theorem; translation lemma; Gap theorem; NP-completeness and NP-hard problems; probabilistic complexity classes; approximation algorithms; and interactive protocols.
Module Examinable : -
Exam Date : 09-05-2019 AM
Modular Credits : 4
Pre-requisite : CS4232 Theory of Computation
Preclusion : CS4230
Module Workload (A-B-C-D-E)* : 2-1-0-3-4
Remarks : Nil
* A: no. of lecture hours per week
B: no. of tutorial hours per week
C: no. of laboratory hours per week
D: no. of hours for projects, assignments, fieldwork etc per week
E: no. of hours for preparatory work by a student per week


Lecture Time Table
Class TypeWeek TypeWeek DayStartEndRoom
1 LECTUREEVERY WEEKFRIDAY18302030LT14,

Tutorial Time Table
Attention: The tutorial timetables could be updated from time to time. Students are advised to check regularly for the latest update on the change of tutorial timing.
Class TypeWeek TypeWeek DayStartEndRoom Iteration
1 TUTORIALEVERY WEEKFRIDAY20302130LT14,
Not Available in Tutorial Balloting yet.





  NUS Help NUS Home Search Site Map Contact NUS Legal