Students can prepare for comprehensive exams by taking courses and/or by individual study. Normal course selection will prepare the student adequately for the Core Comprehensive Exam. However the student must be careful to select appropriate courses to prepare for the Advanced Comprehensive Exams. Course sequences are highly recommended to establish the concentration required for success in the Advanced Exams.
The Core Comprehensive Exam covers the material required for a B.S. in Computer Science and additional topics specified by the Curriculum Committee. These topics are essential to every computer scientist, independently of the specialization.
Each Advanced Comprehensive Exam corresponds to a possible specialization offered by the department's computer science curriculum at the M.S. level. The Advanced Comprehensive Exams must be chosen from the list prepared for the given semester by the Curriculum Committee.
Detailed list of topics for the Core Exam is available. (The list may undergo slight adjustments from one semester to another, so please make sure that you are using the current list.) The list includes references to literature. The books which are quoted are not required, there are other sources of the same information.
It is not necessary to pass an examination at the first attempt. Nor is it necessary to take the exams in the same semester. (The Comprehensive Exams are offered once in the fall semester and once on the spring semester.)
CORE EXAM
TOPICS
Basic programming methodology
modularity
structured programming
abstract data types
pre-conditions, post-conditions, loop invariants (proving correctness)
proving termination
recursion vs. iteration
Fundamental data structures [CLR] or [AHU]
linked lists
heaps
trees
Fundamental abstract data types and their implementations [CLR] or [AHU]
lists
sets
stacks
queues, priority queues
tables
Fundamental algorithms [CLR] or [AHU]
sorting
selection-sort
insertion-sort
radix-sort (bin-sort)
quick-sort
merge-sort
heap-sort
tree-sort
searching
search trees
binary search
self-balancing trees, e.g. AVL and 2-3 trees
hashing
conflict resolution
hash functions
basic graph algorithms
tree traversals
minimum weight spanning tree
shortest path
depth first search
breadth-first search
topological sorting
strongly connected components
Basic algorithm analysis [CLR] or [AHU]
the big O and Omega notation
worst case and average case analysis
solving simple recurrence relations
efficiency of the algorithms above
computing efficiency of other algorithms
Problem solving strategies [AHU]
divide and conquer
dynamic programming
greedy algorithms
backtracking
local search (local optimization, hill climbing)
Fundamentals of computer architecture and logic design [M]
design of logic components
combinatorial logic
sequential logic
components of the CPU
interrupts
caching
direct memory access
principles of assembly language programming
Fundamentals of operating systems [PS]
kernel
semaphores, monitors, etc.
interprocess communication
file systems
scheduling
memory management
deadlock
protection
Basic theory of programming languages [FG]
identifier binding, scope and range, parameter passing
scoping and block structure
activation record structure
recursion
static links, nested procedures
co-routines, etc.
syntax and translation
implementation of abstraction and encapsulation
Fundamentals of databases [EN]
DBMS vs. file processing systems
catalog
three-level architecture
access methods for files
sequential search
binary search
external hashing
indices: primary, clustered, secondary, multilevel, B+ trees
operations on files
double buffering
entity-relationship diagram
relational model
constraints
mapping from the ER-diagram
querying a relational database (relational algebra or calculus or SQL)
Basic discrete mathematics [Rm]
induction
relations and partially ordered sets
elements of propositional logic
Boolean expressions vs. truth tables
Boolean expressions vs. circuits
combinatorics and counting
countable and uncountable sets
propositional logic
basic graph theory
generating functions
Basic probability theory [Rs]
sample space and probability
conditional probability and Bayes Theorem
independent events
random variables
expected value and variance
probability distributions
discrete: hypergeometric, binomial, Poisson
continuous: uniform, exponential, normal, normal approximation to binomial
Vectors and matrices [S]
vector spaces and linear independence
ortogonality
scalar product
matrix multiplication and inversion
determinants
solving a system of n linear equations with m variables
Basic automata theory [LP]
deterministic and nondeterministic finite automata
regular expressions
context-free grammars and BNF
deterministic and nondeterministic Turing machines
recursive sets
non-recursive sets: halting problem
r.e sets
computational time/space complexity, P and NP
RELEVANT COURSES
MTH210 Vectors and Matrices,
MTH220 Programming II,
MTH224 Probability,
EEN228 Assembly Languages,
EEN304 Logic Design,
MTH309 Discrete Math,
MTH322 Unix and C,
EEN414 Computer Architecture,
MTH517 Data Structures,
MTH519 Theory of Programming Languages,
MTH596 or EEN521 Operating Systems,
MTH523 Databases,
MTH527 Automata and Formal Languages,
REFERENCES
[AHU] A. Aho, J. Hopcroft and J. Ullman,
Data Structures and Algorithms,
Addison-Wesley, 1983.
[CLR] T. Cormen, Ch. Leiserson, R Rivest
Introduction to Algorithms
MIT Press, 1990
[EN] Elmasri and Navathe
Fundamentals of Database Systems
Second Edition
Benjamin/Cummings Publishing Co., 1994.
[FG] Fisher and Grodzinsky
The Anatomy of Programming Language
Prentice Hall
[LP] H. Lewis and C. Papadimitriou,
Elements of the Theory of Computation,
Prentice-Hall, 1981.
[M] M. Mano,
Digital Design,
Prentice-Hall, 1984.
[PS] J. Peterson, A. Silbershatz,
Operating System Concepts,
third edition, Addison-Wesley, 1991.
[Rm] S. Roman,
An Introduction to Discrete Mathematics,
Harcourt Brace and Jovanovich, 1989.
[Rs] S. Ross
A First Course in Probability
Third Edition
Collier Macmillian Publishers, 1988.
relevant sections from chapters 1-5, 7.
[S] Introduction to Linear Algebra
Strang
Wellesley Cambridge Press