Signups are done via the Comprehensive Exam Web Page with details from the Math/CS student center. To be eligible to take the exams, a student must have completed all prerequisites, the 3 required graduate level classes (6000, 6260, 6560) and at least 26 units towards the 45 required for the M.S. degree. Courses currently being taken can be counted.

In order to pass the comprehensive examinations, a student must pass all 3 parts. A student passing only 2 parts does not have to retake those sections, while a student who passes fewer than 2 parts must retake all 3 sections.

A student may not attempt just 2 of the 3 sections. A student must either attempt all 3 or just the 1 that remains after having passed 2 of 3 at the same time.

A student will be permitted 2 attempts to pass the exams, with a third attempt allowed only to pass a single remaining section. We call this a Category I student.

Otherwise, the student is in Category II and requests for an additional attempt must be made in writing to the Graduate Committee.

For a student in Category II, the following are possible decisions of the Committee.

1. If the student showed some reasonable performance already on the test (e.g. passed 1 out of 3 sections and was close to passing the others), then the Committee may allow an additional attempt. The student would be expected to submit a study plan and then check-in with the Graduate Advisor to demonstrate that they are following this study plan.
2. The Committee may ask the student to re-take a number of courses where the student needs improvement. The student must pass these courses with a grade of B or better before taking the exam again.
3. The Committee may choose not to permit an additional attempt due to repeatedly inadequate results.

Without a successful appeal, a Category II student will not be permitted to re-register for another attempt. Category I students are allowed to re-register and do not need special permission.

• 1. Processor management
  • a. Process control blocks
  • b. Long and short-term schedulers
  • c. Scheduling algorithms
  • d. Context switching
  • e. System calls and interrupts
  • f. Interprocess communication, including critical sections, semaphores
  • g. Standard synchronization problems, including producer/consumer, dining philosophers, readers/writers
• 2. Memory management
  • a. Logical/physical addresses
  • b. Contiguous storage
  • c. Paging
  • d. Segmentation
  • e. Replacement algorithms, working sets
• 3. Device management
  • a. Interrupt servicing
  • b. Disk scheduling
• 4. Deadlock
  • a. Characterization
  • b. Prevention
  • c. Avoidance
  • d. Recovery

• Silberschatz et al: Operating Systems Concepts
• Stallings: Operating Systems
• Tannenbaum: Modern Operating Systems

• 1. Digital Logic
  • a. Gates
  • b. Boolean algebra
  • c. Karnaugh maps
  • d. Combinational circuit design
  • e. Fundamental combinational circuits: decoders, multiplexers, etc.
• 2. Memory
  • a. Flip-flops/latches
  • b. Sequential circuit design
  • c. Fundamental sequential circuits: registers, counters, etc.
  • d. Memory organization
  • e. Bus organization
• 3. Processor organization
  • a. Registers
  • b. ALU
• 4. Machine language and assembly language design

• Mano: Computer System Architecture
• Mano and Kime: Logic and Computer Design Fundamentals
• Nelson, Nagle, Irwin and Carroll: Digital Logic Circuit An. & Design
• Tanenbaum: Structured Computer Organization
• Hennesey and Patterson: Computer Architecture, a Quantitative Approach
• Patterson and Hennesey: Computer Organization and Design

• 1. Lists
  • a. Sorted and unsorted lists
  • b. Arrays
  • c. Linked lists
  • d. Stacks
  • e. Queues
• 2. Recursion
  • a. Recursive functions (base and general cases)
  • b. Activation records (stack frame) and the run-time stack
  • c. Removing recursion
• 3. Trees
  • a. General trees
  • b. Binary trees
  • c. Tree traversals (preorder, inorder, postorder and level-order)
  • d. Binary Search Trees
  • e. Binary Expression Trees
  • f. Heaps and Priority Queues
• 4. Search
  • a. Sequential search
  • b. Binary search
• 5. Sorting
  • a. Elementary sorts (Insertion Sort, Selection Sort, Bubble Sort)
  • b. Mergesort
  • c. Heapsort
  • d. Quicksort
  • e. Radix Sort
• 6. Hashing
  • a. Closed Hashing/Open Addressing (linear probing and quadratic probing)
  • b. Open Hashing/Separate Chaining
  • c. Rehashing
• 7. Big-oh/big-theta analysis of operations on the above data structures

• Weiss: Data Structures and Algorithm Analysis (different versions use different languages)
• Horowitz, Sahni, Mehta: Fundamentals of Data Structures in C⁺⁺
• Sedgewick: Algorithms in C
• Dale: C⁺⁺ Plus Data Structures

• 1. Syntax
  • a. Grammars, extended grammars, parse trees, derivations
  • b. Syntax diagrams
  • c. Attribute grammars
• 2. Variables: names, types, locations, scope, value
  • a. Aliasing
  • b. Binding times
  • c. Scope rules
  • d. Types, type equivalence, subtypes
  • e. Storage allocation: stack, heap, static, garbage collection
• 3. Control Structures (selection, iteration, goto)
  • a. Design issues
  • b. Syntax
  • c. Semantic questions
  • d. Recursion
• 4. Procedures and Functions
  • a. Storage and scope issues
  • b. Parameter passing
  • c. Stack and static implementations
  • d. Methods
• 5. Language Design
  • a. Reliability, writability etc.
  • b. Imperative vs. functional languages
  • c. Compiled vs. interpreted languages

• Sethi: Programming Languages, Concerns and Constructs
• Sebesta: Programming Languages
• Pratt and Zellkowitz: Programming Languages, Design and Implementation

• 1. Analysis Framework
  • a. Asymptotic notations: big-oh, little-oh, big theta, big omega, little omega
  • b. Worst-case, best-case, average-case analysis of algorithms
• 2. Recursive Functions and Recurrence Relations
• 3. Graph Algorithms
  • a. Kruskal's algorithm and Prim's algorithm.
  • b. Dijkstra's algorithm.
  • c. Breadth-first search (BFS) and depth-first search (DFS).
• 4. Analysis of fundamental algorithms such as searching and sorting

• Aho, Hopcroft, Ullman: The Design and Analysis of Computer Algorithms
• Baase and Van Gelder: Computer Algorithms
• Corman, Leiserson, Rivest, Stein: Introduction to Algorithms
• Levitin: The Design and Analysis of Algorithms