COS 126 Exam 2 Information, Spring 2012

Practice Programming Exam.

There will be a practice programming exercise.

Saturday night, April 28, 7:00 pm, Room CS 104.

Q+A.

There will be a Q+A session.

Sunday night, April 29, 7:30 pm, Friend 101.

Written exam rules.

50 minutes, during lecture time on Tuesday, May 1 at 10am or 11am.
Closed book, closed note.
You may bring one 8.5-by-11 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.

You MUST take the exam in your assigned room at the assigned time. We reserve the right to disqualify or penalize those who do not comply in either regard.
Students in lecture L01 (10:00-10:50), and precept P01, P01A, P01B, P02, P02A, P02B, P02C, P03, P03A, P04, P04A, P05 will take the written exam in Friend 101 on Tuesday, May 1 at 10:00am.
Students in lecture L01 (10:00-10:50), and precept P06, P07, P07A, P07B, P08, P08A will take the written exam in McDonnell A01 on Tuesday, May 1 at 10:00am.
Students in lecture L02 (11:00-11:50), and precept P01, P01A, P01B, P02, P02A, P02B, P02C, P03, P03A, P04, P04A, P05 will take the written exam in Friend 101 on Tuesday, May 1 at 11:00am.
Students in lecture L02 (11:00-11:50), and precept P06, P07, P07A, P07B, P08, P08A will take the written exam in McDonnell A01 on Tuesday, May 1 at 11:00am.

Programming exam rules.

50 minutes, during precept on Tuesday, May 1 or Wednesday, May 2.
Open book, open note, open computer --- yes, including the booksite! 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 (many rooms do not have power outlets).
If you do not have a working laptop (e.g., Java programming environment installed, wireless connectivity in Friend, battery lasts for a full hour), you MUST sign up by April 25, using this link to make alternate arrangements. Students who have made such arrangements will receive a confirmation email on Sunday, April 29.
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.
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 the files 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 unless you have made alternate arrangements. For details of how to make alternate arrangements, see the rules above.
Students in P01, P01A, P01B who have a working laptop will take the programming exam in Friend 101 on Tuesday, May 1 at 12:30pm.
Students in P02, P02A, P02B, P02C who have a working laptop will take the programming exam in Friend 101 on Tuesday, May 1 at 1:30pm.
Students in P03, P03A, P04, P04A, P05 who have a working laptop will take the programming exam in their regular precept classrooms on Tuesday, May 1 at their regular precept times.
Students in P06 who have a working laptop will take the programming exam in CS 105 on Wednesday May 2 at 10:00am.
Students in P07, P07A, P07B who have a working laptop will take the programming exam in Robertson 100 on Wednesday, May 2 at 1:30pm.
Students in P08, P08A who have a working laptop will take the programming exam in their regular precept classrooms on Wednesday, May 2 at 12:30pm.

Material covered.

The exam will cover all material in the course, but with an emphasis on the second half of the course:

Introduction to Programming in Java, Sections 3.1-3.3, 3.5(booksite), 4.1, 4.3, 4.4.
Introduction to Programming in Java, Booksite 7.2-7.7
On-line Chapter 7 (link on Lecture page).
On-line Circuits Packet (link on Lecture page).
Lecture notes 12-22.
Programming assignments 4-8.

The written part of the exam (in lecture) covers all of the above. It will be multiple-choice 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 on-line packets and to study the lecture notes.

The second part of the exam in precept 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 work a few of the easy 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.

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)
- 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)
- DFAs (tracing and understanding, but not designing)
- Turing machines (tracing and understanding, but not designing)
- duality, universality, Church-Turing thesis, computability, halting problem
- Intractability (P, NP, NP-complete, P = NP question, extended Church-Turing thesis, reduction)
Scientific computing
- floating point
- roundoff error and catastrophic cancellation
- stable algorithms and well-conditioned problems
Combinational circuits and Architecture
- Boolean logic
- AND, OR, NOT gates
- sum-of-products
- Sequential circuits
- SR flip-flops
- 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.E
Math.PI

Integer.parseInt()
Double.parseDouble()
Double.POSITIVE_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()

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.