COS 126 Midterm Exam 2 Information, Spring 2010

Q+A.

There will be a Q+A Session on Sunday April 25, beginning at 7:30pm in Friend 101.

The precept before the exam will have a substantial amount of time for Q+A and review.

Written exam rules.

50 minutes, during lecture on Tuesday, April 27 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 or you will receive no credit.
Go to Friend 006 at 10am for the written exam IF AND ONLY IF you are in P06, P06A or P06B AND you are registered for L01 (the 10am lecture).
All other students take the written exam in Friend 101 at their officially scheduled lecture time.

Programming exam rules.

50 minutes, during precept on Tuesday, April 27 or Wednesday, April 28.
Open book, open note, open computer, open web—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).
Set up an empty directory on your laptop that includes a copy of StdIn.java, StdOut.java, StdDraw.java, In.java, Queue.java, Stack.java and ST.java.
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 Friend, battery lasts for a full hour), you MUST notify your preceptor one week in advance to make alternate arrangements.
Students in P01, P01A, P01B, P01C and P01D who have a working laptop will take the programming exam in Friend 101.
Students in P02 and P03 who have a working laptop will take the programming exam in their regular precept classrooms.
Students in P04 who have a working laptop will take the programming exam in Friend 004.
Students in P05 who have a working laptop will take the programming exam in Friend 008.
Students in P06 who have a working laptop will take the programming exam in Friend 006.
Students in P06A and P06B who have a working laptop will take the programming exam in their regular precept classrooms.

Material covered.

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

On-line Circuits Packet (link on Lecture page).
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.1-7.7
On-line Chapter 7 (link on Lecture page).
Lecture slides 12-21.
Programming assignments 5-8.

The first part of the exam (in lecture) covers all of the above. It will contain multiple-choice and short answer questions. The best way to prepare for this part of the exam is to read the book and to review the lecture slides. You are not responsible for knowing details of complicated application examples like binomial coefficients.

The second part of the exam in precept is a programming exam. You will be asked to write a program from scratch (a mini programming assignment). Given the time limitation, the program will be less involved than a typical weekly programming assignment. A good way to prepare is to do the Spring 2009, Programming Exam 2 in a timed environment.

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? If so, fine; if not, reread the appropriate sections in the book and lecture slides.

Combinational circuits
- Boolean logic
- AND, OR, NOT gates
- sum-of-products
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
Performance
- Doubling Hypothesis
- Empirical Analyisis, Mathematical Analysis
- Order of Growth Classifications
Data structures
- linked lists
- binary trees
- stacks and queues
- symbol tables
- which data structure is appropriate for which application
Theory of computing
- regular expressions (the 5 basic ops, don't need extra Java add-ons)
- 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)
APIs.
You should be familiar with the following static methods (the ones we've encountered 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.log()
Math.random()
Math.E
Math.PI

Integer.parseInt()
Double.parseDouble()
Double.POSITIVE_INFINITY
Double.NEGATIVE_INFINITY

System.out.println()
System.out.print()

StdOut.println()
StdOut.print()

StdIn.readInt()
StdIn.readDouble()
StdIn.readString()
StdIn.isEmpty()

StdDraw.line()
StdDraw.point()
StdDraw.circle()
StdDraw.setXscale()
StdDraw.setYscale()
StdDraw.clear()
StdDraw.show()
StdDraw.picture() 
StdDraw.filledPolygon()
```
You should be familiar with the following instance methods (the ones we've encountered in the lectures and assignments). If we want you to use some other library function, we'll remind you how it works.
```
In: In(), readInt(), readDouble(), readString(), readAll(), isEmpty()

Stack: Stack(), isEmpty(), push(), pop()

Queue: Queue(), isEmpty(), enqueue(), dequeue()

ST: ST(), put(), get(), contains()
```
Old Exams.

A good way to practice for the midterm 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 Sorting and Sequential circuit timing diagrams.
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. This year, 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.