Timeline
Tuesday, April 19th: Written exam review session (on Intractability), in McCosh 10.
Thursday, April 21st: Programming exam. See room assignments.
Tuesday, April 26th: Written exam review session, in McCosh 10.
Thursday, April 28th: Written exam. See room assignments.
Study Guide
Material
The second set of exams will cover all of the material in this course, with an emphasis on the second half of the semester: Lectures 9–20 and associated readings.
As with the first programming exam, the second programming exam will involve writing a small program from scratch. The best way to prepare for the programming exam is to practice with previous programming exams. Warning, some previous exams were 90 minutes long, whereas your exam will be 50 minutes long.
As with the first written exam, the second written exam will test content from the video lectures and textbook. The best way to study for the written exam is to practice by doing previous written exams and rewatch relevant lecture videos.
Review Session
Prof. Wayne will hold a written exam review session on Tuesday, April 26, where he will explain answers to previous exam questions. He will also solve previous exam problems in the class meetings on Thursday, April 14 (REs, DFAs, computability, universality) and Tuesday, April 19 (intractability, P, NP, NP-complete).
You can also ask us about previous exam questions in office hours or on Piazza.
Checklist
The following list is a summary of the main topics on the exam, for your use as a checklist while studying. Do you understand the main ideas behind each of these topics? Do you feel confident answering previous exam questions on these topics? If not, rewatch the appropriate video lectures and reread the relevant sections in the book.
Note, this checklist is not an exhaustive list of all possible exam questions. Your exam may have a topic that is not explicitly listed below, but related.
-
Chapter 3: Object-Oriented Programming
- using data types (declaring variables, invoking constructors and instance methods)
- defining data types (instance variables, constructors, instance methods)
- reference types vs. primitive types
- encapsulation (public/private)
- immutability
- modular programming
-
Chapter 4: Data Structures
- analysis of algorithms (empirical and mathematical)
- linked structures (linked lists and binary trees)
- stacks and queues
- symbol tables and binary search trees
- enhanced for loop to iterate over items in a collection
- which data structure is appropriate for which application?
-
Chapter 5: Theory of Computing
- regular expressions (union, concatenation, closure, parentheses, wildcard, + operator)
- DFAs and NFAs (tracing and understanding, designing from scratch)
- Turing machines (tracing and understanding, but not designing from scratch)
- universality, Church–Turing thesis, extended Church–Turing thesis, computability, halting problem
- intractability (P, NP, NP-complete, polynomial-time reductions)
-
Chapter 6: A Computing Machine
- number representation (binary, hexadecimal, two's complement)
- TOY instruction set
- tracing and understanding small TOY programs
- von Neumann architecture
-
Chapter 7: Building a Computer
- boolean logic
- AND, OR, and NOT gates
- sum-of-products circuits
- multiplexers and decoders
- ripple–carry adder
- no sequential circuits or TOY architecture
APIs
You should be familiar with the following static and instance methods. If we ask you to use other methods/libraries, we will describe how they work.
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()
String:
- charAt()
- substring()
- matches()
- indexOf()
- length()
- equals()
- compareTo()
|
Picture:
- width()
- height()
- get()
- set()
- show()
Queue:
- isEmpty()
- enqueue()
- dequeue()
- size()
- iteration
Stack:
- isEmpty()
- push()
- pop()
- size()
- iteration
ST:
- put()
- get()
- contains()
- size()
- iteration
|
Programming Exam
Room Assignments
See below for your room assignment. Because seating is limited, please go to the room you are assigned. There may be a grading penalty if you go to the wrong room.
| Lecture |
Precept |
Room |
| L01 (10am) |
P01, P01A, P01B, P01C |
Frist 302 |
| L01 (10am) |
All Other Precepts |
McCosh 10 |
|
|
| L02 (11am) |
All Precepts |
McCosh 10 |
Policies
Please read our policies carefully to ensure that you are prepared for the programming exam:
- You will have 50 minutes for the exam. Students who have been approved for extra testing time accommodations by the Office of Disabilities can request accommodations by filling out this form.
- The exam will be open book, open notes. You may access the course website, the booksite, Piazza, and you may look at all your old programs, including those you did with a partner. Accessing any other information or communicating with anyone other than a staff member (e.g., via email, instant messenger, text message, etc.) is prohibited.
- Unless you tell us otherwise, you will be taking the programming exam on your personal laptop. It is your responsibility to ensure that your laptop is fully charged before you begin the exam. There are typically very few, if any, accessible power outlets available in large lecture halls on campus. If your computer cannot hold a charge, fill out this form.
- If you need to take the exam on a COS cluster computer instead of your laptop, please fill out this form. We strongly advise you to practice using the lab in advance of the 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 the necessary files. More info can be found here.
- We advise that, in advance of the exam, you create an empty directory and download copies of the following files: ST.java, Stack.java, and Queue.java.
- If there are extraordinary circumstances that will prevent you from taking the exam as scheduled, please fill out this form. Makeup exam requests will be granted only with the recommendation of a Dean or Director of Studies and our preapproval.
Written Exam
Room Assignments
Remember, because seating is limited, there may be a grading penalty if you take the exam in a room other than the one you were assigned.
| Lecture |
Precept |
Room |
| L01 (10am) |
P01, P01A, P01B, P01C |
Frist 302 |
| L01 (10am) |
All Other Precepts |
McCosh 10 |
|
|
| L02 (11am) |
All Precepts |
McCosh 10 |
Policies
The rules for the exam are as follows:
- You will have 50 minutes to take the exam. If you have been approved for extra testing time accommodations by the Office of Disabilities please fill out this form.
- The written exam is closed book, closed notes, and closed computer.
- You may bring one two-sided 8.5-by-11 sheet with notes in your own handwriting to the exam.
- You may not use a calculator, phone, or computer of any kind during the exam.
- If there are extraordinary circumstance that will prevent you from taking the exam as scheduled, please fill out this form. Makeup exams will be granted only with the recommendation of a Dean or Director of Studies and our preapproval.
