Core Exam Information

Previous Core Exams

M.S. Core Comprehensive Exam (Core Exam) Registration Information

The Core Exam is generally offered on the third Friday following the start of the semester. The next Core Exam will be held on:

Friday, February 10, 2012 9:30 a.m.

The exam is held in room 412 WWH from 9:30 a.m. to 12:00 p.m and 1:45 to 3:15 p.m. Students must arrive at least 15 minutes before the start of each session to sign in and present their NYU ID card. The programming languages and operating systems questions are given in the morning session, the algorithms questions in the afternoon.

To register for the Core Exam, send an email to Jen Rose Alexander at jenrose@cs.nyu.edu.

Please include the following information on one line, in the body of your message:

Last Name, First Name UID (without the use of dashes separating the numbers)

For example:

 Doe, John N12345678


Students will receive a confirmation to their email requesting registration within two business days. Students must register at least one week in advance for the Core Exam. For the Spring 2012 Core Exam, the last day to register to take the Core Exam is Friday, February 3rd. We will not accept registrations after that day.

Core Exam (MS)

In addition to the course requirements, students in the MSCS program under the MSCS Degree Requirements Prior to Fall 2009 must pass the Core Exam. Please note that MSCS students under the MSCS Degree Requirements Effective Fall 2009 do not need to take the Core Exam.

This exam is based on three core courses: Fundamental Algorithms (G22.1170), Programming Languages (G22.2110) and Operating Systems (G22.2250), plus additional material listed in the syllabus below. All questions on the exam are given equal weight and are scored from 1 to 10. Both the individual answers and the total scores are curved to determine the passing grade.

Every student gets two chances to pass the Core Exam. A student who registers for and attends the exam will be considered to have used one of these two chances, even if he or she does not submit the exam. Cancellations of exam registration will be accepted until 5:00 P.M. the day before the exam. If the student fails both times, the student will be terminated from the program and will not receive the degree.

Graduation cannot take place earlier than three months after you have passed the Core Exam. If you pass the Core exam administered at the start of the spring term, and that is your final degree requirement, you will be eligible to graduate in May; you must then register for Maintenance of Matriculation (G47.4747-001) for the spring semester. Passing the exam administered in the beginning of the fall semester as your final requirement qualifies you for a January degree and you will have to register for Maintenance of Matriculation (G47.4747-001) for the fall semester.

All students are strongly urged to take the Core Exam at the first available opportunity after completing at least 6 courses in the MS program. For a typical full-time student admitted in the fall semester, it would mean taking the exam in September, at the start of your third semester. This is especially important for international students on a 2-year visa, as it would allow time for a second and final attempt in your final semester.

Syllabus

Algorithms

Topics:

  • Analysis of the correctness and running time of algorithms.
  • Basic data structures: arrays, stacks, queues, linked lists, binary trees.
  • Recurrence equations.
  • Sorting algorithms: mergesort, binsort, quicksort, heapsort.
  • Selection. Binary search. Hashing.
  • Binary search trees and balanced trees.
  • Graphs: spanning trees, shortest paths, connectivity, depth-first search, breadth-first search.
  • Algorithm design: dynamic programming, divide and conquer.

Bibliography:

  • Cormen, Leiserson, and Rivest, Introduction to Algorithms, UPDATED: chaps. 1-5 1-4 + appendix A, 7-14 6-13, 23-26 22-25.
  • Baase, Computer Algorithms, chaps. 2-4.

Operating Systems

Topics:

  • File systems.
  • Memory management: Segmentation, paging, virtual memory, storage allocation. Concurrent processes, classical coordination problems, semaphores, critical sections, monitors. processor scheduling. I/O. The structure of UNIX.

Bibliography:

  • Tannenbaum, Modern Operating Systems

Programming Languages

Topics:

  • Syntactic issues: regular expressions, context-free grammars (CFG), BNF.
  • Imperative languages: program organization, control structures.
  • Types in imperative languages: strong typing, type equivalence, unions and discriminated types in C and Ada.
  • Block structure, visibility and scoping issues, parameter passing.
  • Systems programming and weak typing: exposing machine characteristics, type coercion, pointers & arrays in C.
  • Run-time organization of block-structured languages: static scoping, activation records, dynamic and static chains, displays.
  • Programming in the large: abstract data types, modules, packages and namespaces in Ada, Java, and C++.
  • Functional programming: list structures, higher order functions, lambda expressions, garbage collection, metainterpreters in Lisp and Scheme. Type inference and ML.
  • Object-Oriented programming: classes, inheritance, polymorphism, dynamic dispatching. Constructors, destructors and multiple inheritance in C++, interfaces in Java.
  • Generic programming: parametrized units and classes in C++, Ada and Java.
  • Concurrent programming: threads and tasks, communication, race conditions and deadlocks, protected methods and types in Ada and Java.

Bibliography:

  • Scott: Programming Language Pragmatics
  • Stroustrup: The C++ Programming Languages
  • Barnes: Programming in Ada95
  • The Scheme Revised Report

Compilers (Starting with the September 2008 Core Exam, Compilers will no longer be part of the Core Exam)