CS Comprehensive Exam

General Information on the CS Comprehensive Exam

The comprehensive experience for computer science majors is designed to be an integrative capstone educational experience providing students an opportunity to demonstrate the accumulated expertise and understanding of four years of academic study. This experience is a two-stage process that combines (1) a certification component, in which a student demonstrates mastery of the fundamentals of the discipline in a written comprehensive competency examination, and (2) a subsequent oral presentation and examination of a particular facet of computer science, demonstrating that the student has achieved an appropriate level of mastery and maturity in the discipline. Both components are described in more detail below.

To help develop the level of mastery required for the oral component, an increasingly ambitious series of oral presentations are integrated into our computer science classes. Beginning in the sophomore year students are given increasing responsibility for digesting, absorbing, explaining, and presenting theoretical concepts and underlying implementation details. By increasing the expectations for these presentations as students progress through the program and by giving students assessments of their performance at each point, we hope to prepare them for a meaningful and successful comprehensive experience.


The following links will guide you through the comprehensive exam process, which is described in greater detail below.

There are two parts to the exam:


I. Written Comprehensive Examination Covering Minimum Competencies

Written examination is to be taken during second comprehensive exam period of the Advent (Fall) semester

departmental exam

covers minimum competencies (see syllabus)

graded on a pass/fail basis

students must pass the written exam in order to graduate

students must pass the written exam prior to taking the oral

II. Oral Comprehensive Examination

Oral exam must be taken during second comprehensive exam period of the Easter (Spring) semester

Procedures:

The topic must be approved by the computer science faculty at least eight weeks (see recommended timeline) before the time of the oral examination

Student must discuss the topic with a member of the computer science faculty and demonstrate that she or he is prepared for the exam in order to qualify to take the oral examination

A one-hour oral examination on the student's understanding of the material in the paper is conducted by the computer science faculty and graded as pass/fail

Students must pass the examination to graduate

Content of exam:

The student will select or be assigned a topic in consultation with a member of the faculty and be expected to lead a technical discussion on the topic (20-30 minutes) followed by a question/answer session with the attendees.

During your Exam:

Attendees will and can only be faculty members. Upon inquiry, it seems this is a formal procedure at which other students are not permitted.

You can expect the attending faculty members will have an understanding of the topic, however, YOU are the person in the room who has the most in-depth knowledge about the material.

You will be expected to understand the broad as well as the detailed concepts of the paper and be able to explain them to an educated audience (us!).

You will not be expected to know everything (but I'd try to minimize it if I were you)

If you get in trouble with some questions, you should try to work them through "on your feet", possibly with the aid of the attendees, but you're tempting fate if you try to bluff.

You should not "lecture" but rather give a fairly detailed but brief (20-30min) summary with examples and then lead a technical discussion on it's content. This means more than answering questions. You should be prepared to jump-start such a discussion if questions do not arise.

New Be sure in your talk to tie the material under discussion back to your Sewanee classes (mostly computer science!) whenever possible. A large part of what we look for in a good comprehensive exam is evidence that your entire education has been brought to bear on the material at hand and you are making connections and creating ever more sophisticated understanding from them.

New Examples presented should EXTEND the set which may be found in your background materials. It will not be considered sufficient to recreate the examples in the resources given. You must demonstrate the ability to abstract and extend the principles you are presenting by applying them to additional examples.

New Although PowerPoint or other presentation media may prove extremely helpful to you, your talk should not depend exclusively or primarily upon technology. If the university were to experience a power failure during your exam, you should be capable of continuing using the whiteboards and markers. The largest problems we have observed in past exams have included beautiful PowerPoint transcriptions of a paper under "discussion" which the candidate for degree then read to the committee.

Past Topics

As of 2016 we have limited oral comp topics to natural extensions of important concepts (algorithms, data structures, analyses) from core courses. These paper-based topics from prior yers are included for historical interest. 

2010

  • Reed Tomlinson selected:
    "GPU-Quicksort: A Practical Quicksort Algorithm for Graphics Processors" 
    by Daniel Cederman & Philippas Tsigas 
    ACM Journal of Experimental Algorithmics (Vol. 14, No. 1.4, July'09)

 2008:

  • Joseph Garcia selected:
    "Coherent Line Drawing" 
    by Henry Kang, Seungyong Lee and Charles K. Chui 
    Non-Photorealistic Animation and Rendering (NAPR'07) 
    Sponsored by : ACM SIGGRAPH 
  • Minh Duong selected:
    "Can Machine Learning Be Secure?" 
    by Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph and J.D. Tygar 
    ASIACCS'06

2007:

  • Georgi Kapitanov selected:
    "Fast and accurate goal-directed motion synthesis for crowds"   pp. 291-300 
    by Mankyu Sung, Lucas Kovar and Michael Gleicher 
    ACM SIGGRAPH Symposium on Computer Animation (2005).
  • Teddy Lewis selected:
    "DDoS Defense by Offense"   pp. 303-314 
    by Michael Walfish, Mythili Vutukuru, Hari Balakrishnan, David Karger and Scott Shenker 
    ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Pisa, Italy. (Sept 2006).
  • Andrew Melo selected:
    "Explicit Window Adaptation: A Method to Enhance TCP Performance"   pp. 338-350 
    by Lampros Kalampoukas, Anujan Varma, and K. K. Ramakrishnan 
    IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 3, JUNE 2002
  • Matt Skinner selected:
    "Implementation and Use of the PLT Scheme Web Server" 
    by Shriram Krishnamurthi, Peter Walton Hopkins, Jay McCarthy, Paul T. Graunke, Greg Pettyjohn, and Matthis Felleisen 
    Higher-Order and Symbolic Computation, 2007.
  • Jonathan Watson selected:
    "Network processor acceleration for a Linux* netfilter firewall"   pp. 115 - 123 
    by Accardi, Bock, Hady & Krueger 
    ACM/IEEE Proc. 2005 Symposium on Architecture for Networking and Communications Systems (ANCS 2005)

2006:

  • Kevin Biss selected:
    "Functional reactive animation"   pp. 263 - 273 
    by Conal Elliott & Paul Hudak 
    Proc. 2nd ACM SIGPLAN Int'l Conf. on Functional Programming (ICFP'97)
  • Vishal Nehru selected: 
    "An Aristotelian Understanding of Object-Oriented Programming"   pp. 337-353 
    by Derek Rayside and Gerard T. Campbell 
    ACM SIGPLAN Conference on Object-Oriented Programming, Systems (OOPSLA'00)

2005:

  • Mitch Perry selected:
    "EigenTrust Algorithm for Reputation Management in P2P Networks"   pp. 640-651 
    by Sepandar D. Kamvar, Mario T. Schlosser,B Hector Garcia-Molina 
    Proc. 12th Int'l Conf. on World Wide Web 2003 (WWW'03)
  • Jason Smith selected: 
    "Dimensioning Server Access Bandwidth and Multicast Routing in Overlay Networks," 
      pp. 83 - 91 
    by Sherlia Y. Shi, Jonathan S. Turner, and Marcel Waldvogel 
    Proc. 11th ACM Int'l Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV'01)
  • Ross Sowell selected: 
    "Approximate Convex Decomposition of Polygons"   pp. 17 - 26 
    by Jyh-Ming Lien and Nancy Amato 
    Proc. 20th Annual Symposium on Computational Geometry (SCG'04); ACM Publication

2004

  • Jacob Barrett selected:
    "Task-Model Based Human Robot Cooperation Using Vision" 
    by Hiroshi Kimura and Tomoyuki Horiuchi 
    Proc. of the 1999 IEEE/RSJ Int'l Conference on Intelligent Robots and Systems
  • Nana Bempong selected:
    "Notes on the use of RTP for shared workspace applications" 
    by Colin Perkins and Jon Crowcroft 
    ACM Proc. of Special Interest Group on Data Communications (SIGCOMM'00) 
    Vol 30, Issue 2, pp. 35-40
  • Donald Davis selected:
    "Dynamic Access Control: Preserving Safety and Trust for Network Defense Operations" 
    by Prasad Naldurg and Roy H. Campbell 
    Symposium on Access Control Models and Technology (SACMAT'03)
  • John Edinburgh selected:
    "Scalable Timers for Soft State Protocols" 
    by Puneet Sharma, Deborah Estrin, Sally Floyd, and Van Jacobson 
    IEEE International Conference on Computer Communications (INFOCOM '97)
  • Chris Engels selected:
    "RRT-Connect: An Efficient Approach to Single-Query Path Planning" 
    by James J. Kuffner,Jr. and Steven M. LaValle 
    IEEE International Conference on Robotics & Automation (ICRA'2000)
  • Hannah Johnson selected:
    "Information Theoretic Construction of Probabilistic Roadmaps" 
    by Brendan Burns and Oliver Brock 
    IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'03).
  • John Paul Swamickannu selected:
    "Visual Simulation of Smoke", pp. 15-22 
    by R. Fedkiw and J. Stam and H.W. Jensen 
    ACM Proc. of Special Interest Group on Graphics (SIGGRAPH'01).
  • Geoff Williams selected:
    "The Influence of Caches on the Performance of Heaps" 
    by Anthony LaMarca and Richard E. Ladner 
    ACM Journal of Experimental Algorithmics(ACM JEA'96, Vol. 1)

2003

  • Jason Downs selected:
    "A Scalable Content-Addressable Network" 
    by Ratnasamy, Francis, Handley, Karp, Shenker 
    ACM Proc. of Special Interest Group on Data Communications (SIGCOMM'01).
  • Jonathan Jarrett selected:
    "IP Multicast Channels: EXPRESS Support for Large-Scale Single-Source Applications" 
    by Holbrook, Cheriton 
    ACM Proc. of Special Interest Group on Data Communications (SIGCOMM'99).
  • John Markham selected:
    "Practical Network Support for IP Traceback" 
    by Savage, Wetherall, Karlin, and Anderson 
    ACM Proc. of Special Interest Group on Data Communications (SIGCOMM'00)
  • Neil Mock selected:
    "Selecting Examples for Partial Memory Learning" 
    by Maloof, Michalski 
    Machine Learning, ?, 1-28 (1999)
  • Gary Rogers selected:
    "Promoting the Use of End-to-End Congestion Control in the Internet" 
    by Floyd and Fall 
    To Appear (as of May 3, 1999) in IEEE/ACM Transactions on Networking.

2002

  • Fahd Arshad selected:
    "Web Mining: Information and Pattern Discovery on the World Wide Web" 
    by Cooley, Mobasher, Srivastava 
    IEEE Int'l Conf on Tools with Artificial Intelligence (ICTAI'97).
  • Crile Crisler selected:
    "Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection" 
    by Belhumeur, Hespanha, Kriegman 
    IEEE Transactions on Pattern Analysis & Machine Intelligence, 1997.
  • Kramer Lovelace selected:
    "Interactive Simulation of Fire in Virtual Building Environments" 
    by Bukowski, Sequin 
    ACM Proc. of Special Interest Group on Graphics (SIGGRAPH'97).
  • Steve Marlowe selected:
    "Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols" 
    by Maltz, Johnson, Hu, Jetcheva 
    ACM/IEEE Int'l Conf on Mobile Computing & Networking, 1998.

2001

  • Andrew Ngau selected:
    "Data Mining. The Search for Knowledge in Databases" 
    by Marcel Holsheimer, Arno Siebes 
    Technical Report CS-R9406, Amsterdam, 1994.
  • John McCloskey selected:
    "Wormhold Routing Techniques for Directly Connected Multicomputer Systems" 
    by Prasan Mohapatra 
    ACM Computing Surveys, Vol. 30, No. 3, September 1998.
  • S.P. Kalita selected:
    "The Essence of Functional Programming" 
    by Philip Wadler 
    19th Annual Symposium on Principles of Programming Languages, Santa Fe, 1992. 

III. Student Presentations in Computer Science Courses

400-level computer science courses

will include a requirement of a talk similar to the current senior talks

criteria for the talks will be given to students

talk will require reading research papers on a topic relevant to the course and an investigation of the topic in some detail

other faculty and students outside the class will be invited to attend the presentation; students are responsible for advertising their own talks

grade for the talk will be part of the course grade

a student who has begun research early and would like to gain experience delivering a talk in preparation for a senior honors talk will be given the opportunity and encouraged to do so

300-level computer science courses

will require students to make an oral presentation of some type, generally shorter than those in 400-level courses

faculty teaching 300-level computer science courses will give students both criteria for these oral presentations and an evaluation so that they can improve their performance on the 400-level talks

200-level computer science courses

will incorporate student projects and short presentations as a prelude to these activities

IV. Honors

Departmental honors may be conferred on students considered worthy of distinction. 
Most of the following accomplishments are generally expected:

    1. an average of at least 3.5 in computer science courses numbered 300 and higher;
    2. a superior performance on both the written and oral comprehensive examination;
    3. an original project, usually as part of a 444 computer science elective course, and oral defense or presentation of the work;
    4. additional course work in computer science beyond the minimum requirement.

Syllabus for the CS Comps

CS157, 257 Object Oriented Programming

  • Foundations
    • hierarchy of abstractions in a computer
    • operator precedence (arithmetic, logical, bitwise)
    • control structures
    • recursion
    • lists, stacks, queues, linked lists, binary search trees

  • Design & Use of User-Defined Data Types
    • data (scoping, typing, class vs object)
    • methods (return types and argument list)
    • inheritance
    • linear and binary search

CS284 Databases with Web Applications

  • Normalization (thru 3rd Normal Form)
  • SQL queries
  • DBA vs User permissions and tasks

CS320 Algorithms

  • Growth of functions
  • Loop Invariants and proving correctness
  • Recurrences - induction, recursion, MasterMethod
  • Sorting - SelectionSort, MergeSort, QuickSort, CountingSort, RadixSort, BucketSort
  • Heaps, priority queues, and heapsort
  • Hashing
  • Design strategies
    • greedy algorithms
    • divide and conquer
  • Graphs and their algorithms
    • representation (adjacency list vs matrix)
    • breadth-first search, depth-first search
    • minimum spanning trees
    • shortest paths
  • Running time complexity
    • Polynomial time
    • Intractibility
    • NP-completeness
    • NP-complete problems

CS370 Computer Organization

  • Computer Arithmetic
    • binary, hexidecimal
    • integer and floating point representations
    • arithmetic
  • Machine Instructions
    • Op codes
    • Addressing modes
    • RISC vs. CISC
    • assembly programming
    • Stacks, exception handling, subprogram calls
  • Logic Design
    • Gates, truth tables and logic equations
    • Logical expressions and circuits
    • Design of elementary computer components

  • The Processor: Datapath and Control
    • Functional unit design
    • Single vs. multiple cycle data paths
    • Pipelining, hazards, forwarding

Oral Comprehensive Timeline for Success

thru Dec Read paper selection criteria.

Begin searching for paper. DuPont may not have online or available so leave yourself time to utilize InterLibrary Loan Requests.

by mid-Jan

Read & skim paper selections yourself at this time.

After narrowing your selection to a paper or two, make an appointment with a member of the CS faculty to discuss. Provide faculty member copies of these papers to consider (perhaps online). Be prepared to discuss why this paper is appropriate for your exam. This may take more than one iteration, so start early.

by Feb 1 Paper is APPROVED by a member of the CS faculty and student provides allmembers a copy (paper if they so request).

Read your paper thoroughly and start serious preparation for your presentation. Visuals strongly recommended (powerpoint, etc).

early March Schedule paper discussion with your faculty mentor (usually the member who approved your paper in the first place and with whom you've had the most contact on this subject).
mid March Schedule the room and any equipment you will need for your exam. Inform all CS faculty of location.

Finalize details of your presentation -- both content and supporting material (powerpoint, etc).

late March Oral Comp's (2nd comp exam period) typically take place at end of March or early April.