CS5202 is an exam-only module that is part of School of Computing's
Ph.D. requirements. All CS graduate students admitted after January 2005 are
required to take and pass the exam (along with CS5201).
The exam aims to test students' research skills, including
analytical skills, problem solving skills, creativity, ability to
judge ideas, experimental skills, and rigor of thought.
CS5202 examination is a 3-hour, open book, written exam.
The exam paper consists of
four questions, from which students are required to answer three out of
the four questions to the satisfaction of the examiners.
CS5202 covers the basic areas in computer systems:
operating systems, computer networks, database systems, and
computer organization/architecture. Understanding of common systems
concepts such as caching, transactions, concurrency, logging,
redirection, storage management, pipelining, and layering is important.
Student should also be familar with common systems design goals, such as
scalability, robustness, efficiency, and modularity.
(Note that the information in this section only serves as
a guideline to the kind of questions students can expect in
the exam and is not meant to be comprehensive).
In general, the questions for CS5202 can be categorized into the
following categories.
-
Students are given a problem and are asked to design a solution.
Guidelines and partial solutions may be given to guide the students.
- 0506S1, OS: distributed virtual memory
- 0607S1, OS: microkernel
- 0607S1, Networking: TCP with delay spikes
- 0607S2, Database: database recovery with non-volatile memory
- 0607S2, Networking: geolocation using DNS
-
Students are asked to quantitatively analyze a scheme.
- 0506S1, Database: cost of join algorithms
- 0506S2, Networking: analysis of Ethernet
- 0607S2, Architecture: number of page faults
-
Students are asked to qualitatively compare a number of schemes or describe the pros and cons of a scheme.
- 0506S2, OS: disk block allocation
- 0506S1, Architecture: caching with load/lock instructions
- 0607S2, Networking: geolocation with DNS
- 0607S2, OS: interrupt-based semaphore
- Students may be asked to analyze a situation and explain why/how a
given phenomenon occurs.
- 0506S2, Architecture: cache hit ratio on HT processor
- 0607S2, OS: priority inversion
-
Students are asked to design experiments to evaluate a scheme.
- 0506S2, OS: disk block allocation
The following contains a list of topics that students are
expected to know before taking the examination. Note that the emphasis
is on understanding of the concepts, principles, and techniques behind
these topics, NOT on knowing/memorizing the details. For instance,
understanding the issues and tradeoffs in file system design is more
important than knowing MSDOS FAT format. If the examination questions
require any such detailed knowledge, the details will be supplied to
you as part of the question.
Operating Systems
Students are expected to be familiar with the structure, design, and underlying principles of operating systems, including:
- Processes and Threads:
Life-cycle of processes and threads, process hierarchy,
implementation of processes and threads
- CPU Scheduling and Program Execution: Preemptive/non-preemptive
scheduling, scheduling policies (including round-robin scheduling,
priority-based scheduling), I/O and interrupt, subroutine
calls/return, stacks and recursions.
- Concurrent Programming and Synchronization: Mutual exclusion,
critical section, semaphore, mutex, monitors, locking, deadlock
(causes, conditions, detection, recovery, avoidance), starvation,
race conditions, producer-consumer problem, dining philosophers problem.
- Memory Management Techniques: Address space, memory allocation, swapping,
paging, virtual memory, pages, frames, page tables, TLB, segmentation,
working set, page replacement algorithms.
- Secondary and Tertiary Storage Management:
Memory-mapped I/O, DMA, interrupt, buffering, polling, busy waiting, disk scheduling,
file and directory, file systems implementation, disk space management.
- Distributed Systems: Remote execution, remote file systems, client-server computing.
Computer Networks
Students are expected to be familiar with the basic concepts and principles of protocol
layering and internetworking, including:
- Application Layer: HTTP, FTP, DNS
- Transport Layer: Congestion control, flow control, reliability, connection setup, TCP, UDP
- Network Layer and Routing: Circuit switching, packet switching, router, IP, IP routing
- Link Layer and LAN:Error detection, error correction, framing, flow control, MAC addressing,
ARP, Ethernet, CSMA/CD, interconnections.
Database Systems
Students are expected to be familiar with the basic concepts and principles of data
modeling, storage, updates, and retrieval. These concepts include:
- Data Modeling: ER model, relational algebra and tuple calculus, SQL
- Storage and Buffer Management:
File structure, buffer manager, cost of I/O, sequential vs. random access.
- Indexing: Hash-based index, tree-based index (B+-tree)
- Query Processing and Optimization: Evaluation of join/select/sort/projection, cost model for query
- Transaction Management, Concurrency Control and Recovery: ACID properties, transactions, locking, logging, crash recovery
Computer Organization and Architecture
Students are expected to be familiar with the functional components of a computer
system, their characteristics, and interactions with each other. These concepts include:
- Gates and Circuits: Logic gates, flip-flops, counters, registers, PLA
- Processor Design and Instruction Set Architecture:
Machine-level data representation, instruction fetch/decode/execution cycle,
instruction sets and types, addressing modes
- I/O Devices and Bus: Buffering, handshaking, interrupts, programmed I/O, interrupt-driven I/O, bus
protocols, arbitration, DMA
- Pipelining: Instruction pipelining
- Memory Hierarchy and Cache: Memory hierarchy, main memory organization, address mapping, replacement
policy, virtual memory
- Parallel Architecture: Concurrency, shared memory, multi-processor design,
memory and cache consistency, SIMD/MIMD/VLIW/EPIC
CS5202 is a self-study module. Students who lack background in certain topics
may find auditing related undergraduate modules helpful.
- Database Systems: CS2102, CS3223
- Computer Networks: CS2105, CS3103
- Operating Systems: CS2106, CS3221
- Computer Architecture: CS1104, CS3220
Note that the syllabus of these modules are a superset of CS5202's syllabus and
may cover the concepts listed above in more depth than is required by CS5202.
In addition, the following books
are useful references on the topics covered in CS5202.
- Andrew Tanenbaum, "Modern Operating Systems", Prentice Hall, 2nd Edition.
- James Kurose and Keith Ross, "Computer Networking", Addison Wesley, 2nd Edition.
- Raghu Ramakrishnan and Johannes Gehrke, "Database Management Systems", McGraw-Hill, 2001, 3rd Edition.
- John L. Hennessy and David A. Patterson, "Computer Architecture: A Quantitative Approach",
Morgan Kauffman, 3rd Edition.
The current coordinator for CS5202 is
Ooi Wei Tsang.
Questions regarding format and scope of CS5202
may be forwarded the coordinator. You may use the
IVLE forum
to discuss about CS5202 in general with fellow students and the faculty members.