Guided Studies on Theoretical Computer Science (2009 - 2010)

Coach: Dr. Byron Choi
Meeting time: Thursday 15:30-16:20 (once a week, 1-hour session) (No meeting in Week 1)
Office hour: TBA (once a week, 1 hour)
Venue: FSC1111
Medium of instruction: A mixture (free-style) of Mandarin Chinese and English

Objectives: This study group aims at preparing undergraduates (CS and IS) in ALL years for 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 CS subject tests. 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.

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


Semester 2
Part II Computer Organization and Architecture
A. Digital logic design
W2: 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

Part I Software Systems (Partial)
A. Compilers (3 weeks)
B. Operating systems (3 weeks)

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


Semester 1

Part III Theory and Mathematical Background
A. Algorithms and complexity (4 weeks)
W2: Data structures; Recurrence relation

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

W4: Divide-and-conquer; Dynamic Programming; A showcase of some NP-complete problems
B. Automata and language theory (4 weeks)
W5: Regular expressions and finite state automata, NFA, epsilon NFA

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

W7: Recusrively enumerable and recursive languages, context free grammars and pushdown automata

W8: Cancelled due to conference deadline

W9: Context free grammars and pushdown automata

W10: Decidibility vs undecidibility

C. Discrete structures (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.


Attendance Record:

Participants (17/03): Ren Chushi, Gao Shen and Yang Xiaofei

Participants (10/03): Ren Chushi, Gao Shen, Yang Xiaofei and Xie Chun

Participants (03/03): Canceled due to Byron's sick leave

Participants (11/02): Ren Chushi, Fei Liu, Gao Shen, Yang Xiaofei and Xie Chun

Participants (04/02): Ren Chushi, Fei Liu, Gao Shen, Yang Xiaofei and Xie Chun

Participants (28/01): Ren Chushi, Gao Shen, Yang Xiaofei and Xie Chun

Participants (21/01): Ren Chushi, Gao Shen, Du Rui, Yang Xiaofei and Xie Chun



Participants (10/09): Yang Aobo, Ren Chushi, He Yanda, Gao Shen, Du Rui, Yang Xiaofei

Participants (17/09): Yang Aobo, Ren Chushi, He Yanda, Gao Shen, Du Rui, Yang Xiaofei and Liu Fei

Participants (24/09): Yang Aobo, Ren Chushi, He Yanda, Gao Shen, Du Rui, Yang Xiaofei and Liu Fei

Participants (08/10): Yang Aobo, Ren Chushi, Gao Shen, Du Rui and Liu Fei

Participants (15/10): Yang Aobo, Ren Chushi, He Yanda, Gao Shen, Du Rui, Yang Xiaofei and Liu Fei

Participants (22/10): Yang Aobo, Ren Chushi, He Yanda, Gao Shen, Du Rui, Yang Xiaofei, Liu Fei and Michael Cheng

Participants (29/10): Yang Aobo, Ren Chushi, Gao Shen, Du Rui, Yang Xiaofei and Liu Fei

Participants (05/11): Cancelled due to conference deadline

Participants (12/11): Ren Chushi, Gao Shen, Du Rui, Yang Xiaofei, Peng Yun and Michael Cheng

Participants (19/11): Ren Chushi, Gao Shen, He Yanda, Liu Fei and Yang Xiaofei

Participants (26/11): Cancelled due to workshop deadline





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