CS 5201 - Foundation of Theoretical CS

disclaimer: the detailed syllabus posted are tentative and subjected to change


Background for this exam

 

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. Mapped Sections

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

Procedural Issues

 Past Exams in CS Theory

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.

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)