Guided Studies on Theoretical Computer Science (2011 – 2012)

Coach: Dr. Byron Choi
Meeting time: TBA (once a week, 1-hour session) (No meeting in Week 1)

Office hour: By appointment)
Venue: TBA
Medium of instruction: A mixture (free-style) of Mandarin, Cantonese and English

Objectives: This study group aims at preparing undergraduates (CS and IS) in ALL years for postgraduate studies and is basing on the materials of GRE CS subject tests.

Approach: The study group will solve a large number of sample questions (grouped by topics) to get ourselves to familiar with foundations of Computer Science. Hence, participants' involvement is crucial. Guides will be provided upon requests. A brief tutorial/summary will be provided at the end of each topic.

Prerequisite: Simply put: participants should have the determination to obtain a good score from the subject test. All students (UG and RPg) are welcome.

Outline:
The tentative outline of the study group is simplified from the computer science subject test content [1]. (The topics covered may vary dramatically :) according to our progress and students' suggestions.)

 

Previous study group: 2009 - 2010 (Photos 1 and 2)

Alumni: Chuishi Ren (UPenn, MSE, Start date: 09/11); Fei Liu (HKBU, PhD, 09/11); Du Rui (Northeast, MSE, Start date: 09/10); Gao Shen (HKBU, MPhil, Start date: 09/10); Yu Shizhuo (UC Davis, PhD, Start date: 09/10)

Other study group at the Department: Programming Interest Group

 

Semester 1

Part I Software Systems (Partial)

A. Compilers

(3 weeks)

B. Operating systems

(3 weeks)

 

Part III Theory and Mathematical Background


A. Algorithms and complexity

(4 weeks)

Data structures; Recurrence relation

Call by reference, name, value and value-result; Intro to NP-complete problems

Divide-and-conquer; Dynamic Programming; A showcase of some NP-complete problems

 

B. Automata and language theory

(4 weeks)

 

Recommended reference books:

1. John Martin. Introduction to languages and the Theory of Computation. McGraw-Hill.

2. Thomas Cormen, Charles Leiserson and Ronald Rivest. Introduction to Algorithms. The MIT Press.

 

 

 

Semester 2

 

Part III Theory and Mathematical Background


Regular expressions and finite state automata, NFA, epsilon NFA

Subset Construction (NFA to DFA), minimization of DFA, Turing machine

Recursively enumerable and recursive languages, context free grammars and pushdown automata

Context free grammars and pushdown automata

Decidibility vs undecidibility

(4 weeks)

C. Discrete structures

(4 weeks)

 

Part II Computer Organization and Architecture

A. Digital logic design

 

        System-related GRE questions

 

B. Processors and control units

 

C. Memories and their hierarchies

(4 weeks for A, B, C)

D. Networking and communication

1 week

E. High-performance architectures

1 week

 

 

Recommended reference books:

3. John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach.

 

 

References:

[1] ETS. GRE. Computer Science. http://www.ets.org/portal/site/ets/menuitem.1488512ecfd5b8849a77b13bc3921509/?vgnextoid=e9952d3631df4010VgnVCM10000022f95190RCRD&vgnextchannel=6ef946f1674f4010VgnVCM10000022f95190RCRD

2009.