TO:   M.S. Students in Computer Science
      Studying at the Coral Gables Campus
FROM: Comprehensive Examinations Committee
DATE: October 11, 1996
COMPREHENSIVE EXAMS
FOR STUDENTS CHOOSING THE NON-THESIS OPTION
IN THE M.S. PROGRAM IN COMPUTER SCIENCE
SPRING SEMESTER 1997
OBJECTIVE
Comprehensive exams will test general knowledge in computer science -- the knowledge every computer scientist is expected to possess. The questions in the comprehensive exams will concern important ideas, not technical details. Although certain computer science courses are recommended as helpful in preparing for the comprehensive exams, the questions asked will differ in character from the questions from corresponding final exams. An old proverb says "one cannot see the forest for the trees" ; in a comprehensive exam the students are expected to show that this is not the case for their understanding of computer science.

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.

REQUIREMENTS
A student who chooses the Non-Thesis Option is required to pass the the Core Comprehensive Exam and two Advanced Comprehensive 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.)

ADVANCED EXAMS

SCHEDULE

Students intending to take the Core Exam or any of the Advanced Exams must inform the Department of Mathematics and Computer Science in writing before April 2, 1997. Please specify which Advanced Exams you intend to take. 

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