Exam Syllabus

The three part examination will be given in the context of CS 692, and this is the only mandatory aspect of the course. The offerings will be Fall and Spring semesters. 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: 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:

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.

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

 

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

 

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