Computer Science Department

Comprehensives

  1. Home
  2. Academics
  3. Graduate Program
  4. Comprehensives

Comprehensives

Students that do not earn a B or higher in a core course are required to take a comprehensive examination for that core course.

A comprehensive exam is similar in scope to a final exam in the core course. Each core course comprehensive examination is designed to last approximately one hour however students are allowed 1.5 hours per exam being taken. Failure of a core course comprehensive examination requires a second comprehensive exam covering the part failed. A failure of a second comprehensive examination renders the student ineligible to continue in the computer science MS program.

Students needing to take multiple comprehensive examinations do so in a single examination period and receive all necessary examination parts at the start of the examination period. This allows students to work on exams in any order and at their own pace. Students are allowed 1.5 hours for each exam being taken.

Contact the graduate program director or your core course instructor regarding scheduling to take a comprehensive examination.

Algorithms

Topics

  • Issues involved in the analysis of algorithms: big-Oh notation, worst case analysis, recurrence relations, the master method
  • Advanced Data Structures: red-black trees, B-trees
  • Greedy algorithms: be able to describe the method and examples
  • Dynamic programming: be able to describe the method and examples
  • Amortized Analysis: aggregate method, accounting method, potential method
  • Selected topics from network flow, sorting networks, linear programming, and DFT/FFT
  • Probabilistic algorithms with particular applications in cryptography
  • NP-completeness: what does it mean for a problem to be NP-complete, parts of an NP-completeness proof
  • Approximation algorithms: the goal of an approximation algorithm, examples
  • Undergraduate data structures topics: lists, trees, graphs, searching, sorting

Suggested Readings

From Introduction to Algorithms, by Cormen, Leiserson, and Rivest:

  • Chapter 3/4: Complexity and Recurrence Relations
  • Chapter 13: Red Black Trees
  • Chapter 15: Dynamic Programming
  • Chapter 16: Greedy Algorithms
  • Chapter 17: Amortized Analysis
  • Chapter 18: B-Trees
  • Chapter 26: Network Flow
  • Chapter 27: Sorting Networks
  • Chapter 28: Matrix Operations
  • Chapter 29: Linear Programming
  • Chapter 30: Fast Fourier Transform
  • Chapter 31: Number Theoretic Algorithms and Cryptography
  • Chapter 34: NP-Completeness
  • Chapter 35: Approximation Algorithms

Operating Systems

Topics

  • What an operating system is; special terminology; the notion of system call.
  • Operating system structure. Monolithic, layered, virtual machines, client-server.
  • Processes. The process model and its implementation. IPC. Scheduling.
  • I/O. Principles of I/O hardware. Principles of I/O software. Interrupts. Device drivers. Block vs character devices. Deadlocks.
  • Memory management. Basic, swapping, and virtual memory.
  • File systems. Files. Directories. The "Unix model". Implementation.
  • Security and protection.
  • We used Minix as an important example. I won't ask detailed questions about the code, but you need to understand the structure, fundamental communication mechanisms, "world view" of Minix

Suggested Readings

  • Class notes.
  • William Stallings, Operating Systems: Internals and Design Principles, Pearson, 9th edition.
  • Andrew S. Tanenbaum and Albert S. Woodull, Operating Systems, 2nd ed., Prentice Hall, 1997
  • Bruce Jacob and Trevor Mudge, Virtual Memory: Issues of Implementation, Computer, Vol. 31, No. 6, June, 1998, pp 33-43.

Software Engineering

Topics

  • History of software development, software product and process, system life cycles
  • System engineering, abstraction and modeling, system specification and design
  • Requirements analysis and specification, analysis modeling - data, function and behavior
  • Object-oriented analysis, use case diagrams and scenarios, class diagrams and state diagrams
  • Design principles and concepts: coupling; cohesion; SRP; OCP, LSP, etc.
  • Object-oriented design, interaction diagrams, design patterns, software architecture
  • Software testing methods, white- and black-box testing
  • Agile Manifesto; XP/Scrum values, principles, practices

Suggested Readings

  • Agile Software Development: Principles, Patterns, and Practices , Robert C. Martin, Pearson Prentice-Hall, 2003.
  • Extreme Programming Explained, Kent Beck and Cynthia Andres, 2nd edition, Addison-Wesley, 2005.
  • Essential Scrum, Kenneth Rubin, Addison-Wesley, 2013.