Prerequisites to the Area Star Courses

Although there are no formal prerequisites for admission to the doctoral program, the area star courses make certain assumptions about a student's prior knowledge. Each topic listed below is accompanied by an indication of the level of proficiency that is assumed. In general, this amounts to the ability to use fundamental concepts and techniques in technical discussions.

A student deficient in one or more of these subjects could take undergraduate courses to learn the material.

• Programming ability: Fluency in C or C++, with the ability to code efficient algorithms from high-level abstract descriptions. Some knowledge of assembly language programming.

• Programming Languages: Enough fluency in a high-level imperative language such as Pascal, Modula, Ada, or Java, and a functional language such as LISP, Scheme, or Standard ML to read examples and program exercises. Basic language concepts at the level of Parts 1 and 2 of Programming Languages: Concepts and Constructs by Sethi, or Chapters 1-9 of Principles of Programming Languages by Tennent.

• Program Design: As in Chapter 1 of Structured Programming by Dahl, Dijkstra, and Hoare, and Chapters 9, 13, and 14 of Abstraction and Specification in Program Development by Liskov and Guttag.

• Algorithms and Data Structures: At the level of the non-starred sections of Algorithms by Cormen, Leiserson, and Rivest.

• Compilers: At the level of Chapters 1-5, 7-8 of Compiler Design by Aho, Sethi, and Ullman.

• Operating Systems: Familiarity (as a user) with one or more interactive operating systems, e.g., Unix. Understanding of basic concepts in the design and implementation of operating systems, e.g., concurrent processes, semaphores. At the level of Modern Operating Systems by Tanenbaum or Operating System Concepts by Silberschatz, Peterson, and Galvin.

• Database Systems: At the level of Chapters 1-5, 8-11 of Database Management Systems by Ramakrishnan and Gehrke (that is, the relational data model, algebra, and calculus, basic SQL storage, files, tree- and hash-based indexing).

• Computer Architecture: Processors, registers, indexing, indirect addressing, interrupts, simple machine language programming, primary memory, secondary memory, peripherals.

• Discrete Mathematics: Basic concepts of sets, relations, functions, mathematical induction, and algebra as in Chapters 2-4 and 7 of Discrete Mathematics in Computer Science by Stanat and McAllister.

• Logic: Including propositional calculus, quantifiers, and the ability to manipulate and evaluate logical formulas, as in Chapters 1, 2, and 4 of The Science of Programming by Gries.

• Probability and Statistics: Basic probability and statistics as in Chapter 6 of Algorithms by Cormen, Leiserson, and Rivest, Chapters 1-7 of Probability and Statistics by Morris de Groot, or Chapters 1-7 of Introduction to Probability by Grinstead and Snell.

• Formal Languages: Regular sets, finite automata, regular expressions, nondeterminism, push-down automata, context-free languages, Turing machines, polynomial-time (P and NP) to the level of Introduction to Automata Theory, Languages, and Computation by Hopcroft and Ullman.