*
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.

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. `

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.

C.
** Programming
Language Concepts: **Concepts in Programming Languages by John Mitchell 2002.

D.
** Discrete
Structures and Logic: ** Discrete Mathematics
and Its Applications, Kenneth Rosen, 2007.

- 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

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)