COS 126 Exam 2 Information, Spring 2013
Q+A.
There will be a Q+A session Sunday night, April 28, 7:30 pm, Friend 101.
Written exam rules.
 50 minutes, during lecture on Tuesday, April 30 at 10am or 11am.
 Closed book, closed note.
 You may bring one 8.5by11 sheet (two sides) with notes in your own
handwriting to the exam.
 No calculators, computers, or communication devices.
 No makeup exams will be considered without the recommendation of a Dean.
Written exam rooms.
Programming exam rules.
 90 minutes, on Monday, April 29, 7:309:00pm.
 Open book, open note, open computer,
open browser— but only our course website!
Of course, no internal or external communication is permitted
(e.g., talking, email, IM, texting, cell phones) during the exam.
 Bring your laptop and make sure the battery is fully charged
(There are not accessible power outlets in the room.)
 Students who have a nonCOS class on Monday nights should attend their
regularly scheduled class. Contact David Pritchard (dp6@cs.princeton.edu) to schedule a
Tuesday makeup exam.
 Students who have an Organic Chemistry exam on Monday night, April 29
should take their chemistry exam on Monday night.
Contact David Pritchard (dp6@cs.princeton.edu) to schedule a Tuesday makeup exam.
 Set up an empty directory on your laptop
that allows use of:
StdIn.java,
StdOut.java,
StdDraw.java,
ST.java,
Stack.java
and
Queue.java.
 With the exception of students who have a verified class conflict
or the Organic Chemistry exam listed above,
NO makeup exams will be considered without the recommendation of a Dean.
Programming exam rooms.

You MUST take the exam in your assigned room at the assigned time
or you will receive no credit.
 If you do not have a working laptop
(e.g., Java programming environment installed,
wireless connectivity in your exam location, battery lasts for a full hour and a half),
you MUST contact David Pritchard (dp6@cs.princeton.edu) by April 24
to make alternate arrangements. Please specify whether you need to use a cluster
machine or if you simply need access to a power outlet.
 Students in P01, P01A, P01B, P05 who have a working laptop
will take the programming exam in COMPU 104
on Monday, April 29 at 7:30pm.
 Students in P03, P03A who have a working laptop
will take the programming exam in COMPU 105
on Monday, April 29 at 7:30pm.
 Students in
P02, P02A, P02B, P02C, P02D, P06, P07, P07A, P07B, P09
who have a working laptop
will take the programming exam in McDonnell A02
on Monday, April 29 at 7:30pm.
 Students in P04, P04B, P08, P08A who have a working laptop
will take the programming exam in McDonnell A01
on Monday, April 29 at 7:30pm.
 Students without working laptops, who have contacted David Pritchard
as described above, will take the exam in Friend 016 at the normal time.
 Students who need access to a power outlet, who have contacted David Pritchard
as described above, will take the exam in either Friend 004 or Friend 016
(whichever room David emails them about) at the normal time.
If you plan to use a cluster machine in Friend 016 for your exam,
make sure you know how to use a cluster machine and set up a directory
for the exam on your university H: drive that includes a copy of
StdIn.java, StdOut.java, StdDraw.java,
ST.java, Stack.java, Queue.java.
Here is a link to some helpful instructions.
Material covered.
The exam will cover all material in the course, but with an emphasis
on the second half of the course (i.e., the material since the first exam):
 Scientific Computing: Introduction to Programming in Java, Booksite 9.1, 9.4, 9.5
 OOP and ADT: Introduction to Programming in Java, Sections 3.13.3,
3.5(booksite), 4.3, 4.4.
 Theory: Introduction to Programming in Java, Booksite 7.27.7
 RE and DFA: Online Chapter 7 (link on Lecture page).
 Online Circuits Packet (link on Lecture page).
 Lecture notes 1222.
 Programming assignments 58.
The written part of the exam (in lecture) covers all of the above. It
will be multiplechoice or short answer questions on the important material.
The best way to prepare for this part of the exam is to read the book
and the online packets,
study the lecture notes,
and practice taking old exams. (See Old Exams section below.)
The Monday evening part of the exam is strictly about programming.
You will be asked to write a program from scratch (a mini programming
assignment). Given the time limitation, this program will not be conceptually
difficult, just a test of your ability to write a program that solves
a simple problem. The best way to prepare for this part of the exam is to
program: Work
a few of the exercises in the book and on the booksite that call
for writing small programs.
List of topics.
This list is a summary of the main topics on the exam, for your
use as a checklist when studying. Do you understand the basic ideas
behind each of these topics? Do you know the names and contributions of
the major players? If not, reread the appropriate
sections in the book and lecture slides.
 Scientific computing
 floating point
 roundoff error and catastrophic cancellation
 stable algorithms and wellconditioned problems
 Using data types
 declaring variables
 invoking constructors
 invoking methods
 reference types vs. primitive types
 Creating data types
 instance variables
 constructors
 instance methods
 Designing data types
 encapsulation (public/private)
 static constants
 modular programming
 immutability
 Data structures and algorithms
 linked structures (linked lists and binary trees)
 stacks and queues
 symbol tables and binary search trees
 enhanced for loop to iterate through objects (see p. 588 and p. 629)
 which data structure is appropriate for which application
 analysis of algorithms
 Theory of computing
 regular expressions (the 5 basic ops, the + operator)
 DFAs (tracing and understanding, but not designing)
 Turing machines (tracing and understanding, but not designing)
 duality, universality, ChurchTuring thesis, computability, halting problem
 Intractability (P, NP, NPcomplete, P = NP question,
extended ChurchTuring thesis, reduction)
 Combinational circuits and Architecture
 Boolean logic
 AND, OR, NOT gates
 sumofproducts
 Sequential circuits
 SR flipflops
 Multiplexer, Decoder
 TOY architecture
 Processor design
APIs.
You should be familiar with the following static methods
(the ones we've encountered frequently in the lectures
and assignments).
If we want you to use some other library function, we'll remind you
how it works.
Math.sqrt()
Math.max()
Math.min()
Math.abs()
Math.sin()
Math.cos()
Math.exp()
Math.pow()
Math.log()
Math.random()
Math.round()
Math.ceil()
Math.E
Math.PI
Integer.parseInt()
Integer.MAX_VALUE
Integer.MIN_VALUE
Double.parseDouble()
Double.POSITIVE_INFINITY
Double.NEGATIVE_INFINITY
StdOut.println()
StdOut.print()
StdOut.printf()
StdIn.readInt()
StdIn.readDouble()
StdIn.readString()
StdIn.isEmpty()
StdIn.readAll()
StdDraw.line()
StdDraw.point()
StdDraw.circle()
StdDraw.square()
StdDraw.setXscale()
StdDraw.setYscale()
StdDraw.clear()
StdDraw.show()
StdDraw.picture()
StdDraw.polygon()
StdDraw.filledPolygon()
StdDraw.rectangle()
StdDraw.filledRectangle()
You should also be familiar with the following data types and instance
methods:
String data type: charAt(), substring(), matches(), indexOf(), length(), equals()
Picture data type: width(), height(), get(), set(), show()
Queue data type: isEmpty(), enqueue(), dequeue(), size(), iteration
Stack data type: isEmpty(), push(), pop(), size(), iteration
ST data type: put(), get(), contains(), size(), iteration
Old Exams.
A good way to practice for the EXAM is to solve problems from
old exams.
Warning 1: Some old exams include questions on topics that we have not
covered this semester, for example percolation and Quicksort.
Warning 2: Studying questions that ask you to write code is worthwhile,
but bear in mind that some of the old exams were two hours, closed
book, no computers. When looking at an old exam,
check the cover sheet to
see if it was a 50 minute exam or a 2 hour exam.
This term, the written exam will not have questions that ask you to write
a significant amount of code. The purpose of the programming exam is
to test your ability to write code.
Updated April 25, 2013.