Exam Syllabus
Section 1: OPERATING SYSTEMS (1.5 hours - answer 2 out of 3 questions)
Section 2: ADVANCED ALGORITHMS (1.5 hours - answer 2 out of 3 questions)
Section 3: THEORY OF COMPUTATION (1.5 hours - answer 2 out of 3 questions)
The 3 questions on each test may come from anywhere in the respective syllabus.
The course grade is based solely on the exam scores and results in CREDIT/NO CREDIT for the course. The student will complete 2 questions on each test, where each question is worth 20 points. The student must pass each test individually, with a score of 24/40 (60% rule) or better. If the student passes all 3 tests, they will receive a CREDIT (PASS) grade. If the student does not pass all 3 tests, a NO CREDIT grade will be issued. In this case, the student should contact the graduate coordinator about re-taking the exam.
The following is the standardized Student Learning Outcome (SLO) for each exam:
| Result | Grade | Student Learning Outcome |
|---|---|---|
| Excellent | 35-40 pts | : Understands essentially correct solution |
| Good | 29-34 pts | : Understands correct solution, but some errors in execution |
| Passing | 24-28 pts | : Some understanding of solution, but has 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.
Operating Systems Syllabus
Topics:
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.
g. Definition of critical sections, requirements for solution to critical section problem.
h. Concurrency solutions, including hardware solutions (disabling interrupts, atomic ops), and software solutions (semaphores, monitors)
i. Standard synchronization problems, including producer/consumer, dining philosophers, readers/writers
j. Concurrency and parallel processing.
2. Memory management
a. Logical/physical addresses
b. Contiguous storage including slab allocation and free lists
c. Paging
d. Page table implementation, including multi-level paging, hashed, inverted page tables
e. Segmentation
f. Page replacement algorithms
g. Frame allocation algorithms, working sets, reactive scheme using page fault rate
3. Device management
a. Interrupt servicing
b. Disk scheduling
4. Deadlock
a. Characterization including necessary conditions
b. Detection (Safe State), Prevention
c. Avoidance, including Banker’s algorithm
d. Recovery
5. Virtualization and Virtual Machines.
a. Virtual Machine Memory Management.
6. OS Architectures - Monolith, Module, or Layered - benefits and disadvantages
References: (Textbooks)
Silberschatz et al: Operating Systems Concepts
Stallings: Operating Systems
Tannenbaum: Modern Operating Systems
Advanced Algorithms Syllabus
Topics:
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
c. Counting operations
2. Basic data structures, including specification, use, and storage analysis
a. Stacks
b. Queues
c. Hashing
d. Trees
e. Heaps and priority queues
f. Linked Lists
3. Search, sequential, exhaustive and analysis
4. Recursive functions and recurrence relations and their analysis
5. Sorts and their analysis
a. Elementary sorts (Insertion, Selection, Bubble)
b. Heapsort
c. Quicksort
d. MergeSort
e. Radix Sort
6. Tree types and analysis
a. AVL trees
b. 2-3 trees
c. Red-black trees
7. Graph Algorithms
a. Graph representations, adjacency matrix, adjacency list
b. Kruskal's algorithm and Prim's algorithm.
c. Dijkstra's algorithm.
d. Breadth-first search (BFS) and depth-first search (DFS)
e. Heuristics and heuristic search
f. MST, SPT via Prim’s Kruskal’s and Djikstra’s algorithms
8. Analysis of fundamental algorithms such as searching and sorting
9. Numerical probabilistic algorithms, Las Vegas and Monte Carlo algorithms, game-theoretic techniques
10. String-matching methods
References: (Textbooks)
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
Weiss: Data Structures and Algorithm Analysis
Theory of Computation Syllabus
Topics:
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
2. Complexity Classes
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: (Textbooks)
Automata:
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
Complexity:
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