Department of Math and Computer Science
Computer Science Comprehensive Exam Review

[Note: All broadcasts originate from: nobody@mcs.csueastbay.edu]

To help students prepare for the Fall 2009 Comprehensive Exam, there will be a review day:

Date:	Sunday, October 4, 2009
Location:	Science South 125
Topics:	Data Structures and Operating Systems
Speaker:	Dr. Billard

All students taking the exam this spring are welcome. The review will be different than past years. Take a look at the past exams organized by TOPICS:

In the session, the past exams will be discussed conceptually by TOPIC, and some in particular are marked:

Try to do the SELF-STUDY below, that is, read the notes. But even more important is to read and print past exams. But you might want to print them out according to the TOPICS above, especially those marked with *. And you definitely want to print the DS SOLUTION OUTLINE, which are labeled with the name of the function, so you don't need the source question. Here are some examples which show how to use pointers in linked lists: Queue, Swap .

• Introduction: 10-10:15am
• Data Structure Review: 10:15am-12pm
• Break: 12-12:30pm
• Operating Systems Review: 12:30-2:30pm

SELF-STUDY OUTLINE:

Data Structure Review

• Lecture Notes: .html     .pdf
• Examination Syllabus [Slide # in Lecture Notes]
  • 1. Lists
    • a. Sorted and unsorted lists [7]
    • b. Arrays [8-13]
    • c. Linked lists [14-19]
    • d. Stacks [20]   [21-27]   [28-32]
    • e. Queues  [33]   [34-37]  [38-40] [41-44]
  • 2. Recursion
    • a. Recursive functions (base and general cases)  [45-46]
    • b. Activation records (stack frame) and the run-time stack
    • c. Removing recursion  [47-49]
  • 3. Trees
    • a. General trees [50]
    • b. Binary trees [55-58]
    • c. Tree traversals (preorder, inorder, postorder and level-order)[51-54]  [61]
    • d. Binary search trees [63-72]
    • e. Binary expression trees [59-60, 62]
    • f. Heaps and Priority Queues [117]   [118-123]
  • 4. Search
    • a. Sequential search
    • b. Binary search [88-91] (B-Trees are not on exam)
  • 5. Sorting
    • a. Elementary sorts (Insertion Sort, Selection Sort, Bubble Sort) [128-132]  [133-137]   [138-142]
    • b. Mergesort[143-148]
    • c. Heapsort [159-166]
    • d. Quicksort[149-158]
    • e. Radix Sort
  • 6. Hashing
    • a. Closed Hashing/Open Addressing (linear probing and quadratic probing)[103]   [109-116]
    • b. Open Hashing/Separate Chaining [104-108]
    • c. Rehashing [112]
  • 7. Big-oh/big-theta analysis of operations on the above data structures [CS 3240 Big-Oh]

Data Structure Past Exams

Operating Systems Review

• Lecture Notes: .pdf
• Examination Syllabus [Slide # in Lecture Notes, not Page #]
  • 1. Process management
    • a. Process control blocks [8]
    • b. Long and short-term schedulers [98]
    • c. Scheduling algorithms [20-29]
    • d. Context switching [9-10]
    • e. System calls and interrupts [11-12]
    • f. Interprocess communication, including critical sections, semaphores [30-40]
    • g. Standard synchronization problems, including producer/consumer, dining philosophers, readers/writers [41-60]
  • 2. Memory management
    • a. Logical/physical addresses [103, 117-118]
    • b. Contiguous storage [105-113]
    • c. Paging [114-116, 121-125]
    • d. Segmentation [119]
    • e. Replacement algorithms, working sets [126-151]
  • 3. Device management
    • a. Interrupt servicing
    • b. Disk scheduling [152-160]
  • 4. Deadlock
    • a. Characterization [61-63]
    • b. Prevention [64-66]
    • c. Avoidance [69-96]
    • d. Recovery [67-68]

Operating Systems Past Exams