# Exam Syllabus

### Effective: Fall 2010

## Overview of New Exam Structure

Features retained from the old Comprehensive Exam:

- 3 exams, each 1.5 hours
- Answer 2 out of 3 questions, each question worth 20 points, total is 120 points
- Systems Exam is the same

New Features:

- Programming Languages has been
**removed**from Theory, but note that Automata still has Grammars - Analysis of Algorithms has been
**moved**from Theory to Data Structures & Algorithms - Theory is now just Automata and Complexity

There are no other changes to the syllabus so the same topics are covered, with the exception of Programming Languages.

See the CS 6901 Catalog Description for prerequisites.

## Details of the Exam Structure

The three part examination will be given in the context of CS 6901, and this is the only **mandatory** aspect of the course. The offerings will be Fall and Spring quarters. On each part, a student must choose to answer 2 of 3 questions. One and a half hours are allotted for each exam. The exams are closed book, closed notes.

- Section 1: SYSTEMS (1.5 hours - answer 2 out of 3 questions)

- Section 2: DATA STRUCTURES & ALGORITHMS (1.5 hours - answer 2 out of 3 questions)

- Section 3: THEORY (1.5 hours - answer 2 out of 3 questions)

The 3 questions may come from anywhere in the syllabus, which generally flows directly from Automata to Complexity.

## Grading

The course grade is based soley on the exam scores and results in CREDIT/NO CREDIT. The student must receive a total score of 72/120 points (60\% rule) to receive a CREDIT (PASS) grade. The following is the standardized Student Learning Outcome (SLO) for each exam:

Result | Grade | Student Learning Outcome |
---|---|---|

Excellent | 34-40 pts | : Understands essentially correct solution |

Good | 27-33 pts | : Understands correct solution, but errors in execution |

Adequate | 22-26 pts | : Some understanding of solution, but has serious errors |

Poor | 13-21 pts | : No understanding of solution, but has some knowledge of topic area |

No Effort | 0-12 pts | : No understanding of the solution, or the topic area |

The above descriptions are on a per answer basis, and do not account for the variety between the two selected problems in the section. For example, scores of 17 and 17 are both essentially correct and yield an overall Excellent (34) result. Another example is an Adequate (22) result derived from an Excellent (17) understanding of one problem but No Effort (5) on the other problem.

These are examples of passing all three sections with a 72 score overall:

- Adequate (24)+ Adequate (24)+ Adequate (24)
- Good (28)+ Adequate (22)+ Adequate (22)
- Excellent (34)+ Excellent (34)+ No Effort (4)
- Excellent (34)+ Adequate (25)+ Poor (13)

If the student does not pass the course, an INCOMPLETE or NO CREDIT grade will be issued. See below about re-taking the exam.

## Re-Taking the Exam

If the student does not pass the examination in CS 6901, the following provides information on re-taking the exam.

In all cases, the student must take all 3 sections of the exam. After the first attempt, an INCOMPLETE will be issued and the student is allowed to re-take the exam (but all 3 sections) the next time the course is offered. If the student passes, then CREDIT will be assigned as usual. If the student does not pass the second attempt, then NO CREDIT will be assigned, and the student must start over by re-registering for CS 6901.

This is summarized in cs6901.pass.pdf

## Systems Syllabus

**Operating Systems**

- 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

**References:**

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

**Computer Architecture**

- 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

**References:**

- 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

## Data Structures & Algorithms Syllabus

**Data Structures**

- 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

**References:**

- 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

**Analysis of Algorithms**

- 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

**References:**

- 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

## Theory Syllabus

**Automata**

- 1. Alphabets, Strings, and Languages
- 2. Regular Languages
- a. Deterministic Finite Automata
- b. Nondeterministic Finite Automata
- c. Regular expressions and operators
- d. Pumping Lemma for Regular Languages

- 3. Context-Free Languages
- a. Grammars and Ambiguity
- b. Context-Free Grammars and Chomsky Normal Form
- c. Pushdown Automata
- d. Pumping Lemma for Context-Free Languages

**Complexity**

- 1. Turing Machines and Decidability
- a. Decidable, Acceptable and Co-Acceptable Languages
- b. Turing-Completeness
- c. Reducibility
- d. The Halting Problem and Undecidable Problems

- a. Polynomial Reducibility
- b. Time Complexity: P, NP, coNP and EXPTIME
- c. Space Complexity: PSPACE, NPSPACE, EXPSPACE
- d. NP-Completeness and NP-Complete Problems

**References:**

- Garey and Johnson: Computers and Intractability
- Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation
- Johnson and Reiter: The Limits of Computation
- Kozen: Automata and Computability
- Sipser: Theory of Computation