CS 5201 - Foundation of
Theoretical CS
disclaimer: the detailed syllabus posted are tentative and subjected to change
The written qualifier examination aims at testing the basic understanding of students on foundational knowledge in the discipline of computer science, and their ability to independently conduct research. The examination aims to achieve objective evaluation, since all the students answer questions which are set and graded by the same examiners. The examination will focus on concepts pertaining to basic understanding on the discipline and the students' ability to apply that knowledge to problems. In the CS department, the written qualifier consists of two papers, both of which are compulsory.
· CS 5201 Foundations of Theoretical Computer Science
· CS 5202 Foundations of Computer Systems
This page elaborates the first paper focusing on theoretical Computer Science. Here is a quick FAQ for the examination.
Brief Description
The purpose of this exam is to test the students on basic concepts in theoretical computer science. In particular, the students will be tested on the following areas (with possible corresponding SoC modules).
A. Data Structures and Algorithms
(CS1020 Data Structures and Algorithms I, CS2010 Data Structures and Algorithms
II, CS3230 Design and Analysis of Algorithms)
B. Theory of Computation (CS4232 Theory of Computation)
C. Programming Language Concepts (CS2104 Programming Language Concepts)
D. Discrete Structures
and Logic (CS1231 Discrete Structures)
The main focus of the exam is on fundamental concepts and analytical abilities. You will not need to remember specific knowledge because (a) this is an open-book exam and (b) very specific knowledge related to a question will be typically provided with the question.
Reading Materials (with suggested chapter/sections)
The CS5201
QE is based on undergraduate background in theoretical Computer Science.
Individuals who are deficient in this background may find the following reading
materials useful.
A.
Data
Structures and Algorithms: Introduction to Algorithms by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009.
B. Theory of Computation --- Introduction to Automata Theory, Languages and Computation by J. Hopcroft, R. Motwani and J. Ullman, Addison Wesley, 2001. Mapped Sections
C. Programming Language Concepts: Concepts in Programming Languages by John Mitchell 2002. Mapped Sections
D.
Discrete
Structures and Logic: Discrete Mathematics
and Its Applications, Kenneth Rosen, 2007.
Mapped Sections
- The
written Qualifier Exam in Theoretical Computer Science is a 3-hour
open-book examination.
- For
each of the four areas, there will be one question in the exam. You need
to answer three out of four questions. If your performance
in the attempted questions is unsatisfactory, you may be asked to re-take
(parts of) the paper.
- At
most two takes of the examination (or parts of it) is allowed for any
individual candidate.
- This
is a self-study module, where your background is tested as a qualification
for PhD. There are no lecturers for this module.
Here is a rough
analysis of the QE questions in CS Theory (as an example). QE papers from 2011 onwards can be found at NUS e-library.
- April 2011
- November 2010
- April 2010
- November 2009
- April 2009
- November 2008
- April 2008
- November 2007
- April 2007 and sample solution
- November 2006
- April 2006
- November 2005
Contact Persons
If you have further questions, you may get in
touch with any one of the following people.
·
Examination Coordinator:
Dong Jin
Song
·
Graduate Division Contact: Agnes Ang
(aang@comp.nus.edu.sg)