COS 126 Exam 2 Information, Spring 2008

Q+A.

There will be a Q+A Tuesday night, April 29, 8:30-10:00pm, Room Friend 101

The precept before the exam will be devoted to Q+A and review.

Rules: Written exam.

50 minutes, during last lecture time slot before reading period.
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 (or computers!)

Rules: Programming exam.

50 minutes, during last precept time slot before reading period.
Open book, open note, open computer --- yes, including the booksite!
Make sure that your laptop is charged (in case there aren't enough outlets in your precept room). If you don't have a working laptop, tell your preceptor.
Set up an empty directory on your laptop that includes a copy of StdIn.java, In.java and StdDraw.java.

Material covered.

The exam emphasizes but is not limited to everything in the second half of the course:

Introduction to Programming in Java, Sections 3.1-3.3, 4.2-4.4.
Introduction to Programming in Java, Booksite 7.2-7.7
Packet, Chapters 7 and 6.
Lecture notes 13-23.
Programming assignments 5-8.

The first 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 to study the lecture notes, including the Challenge questions that appeared in lecture. You are not responsible for knowing details of complicated applications examples like the random web surfer or IFS.

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 sumary 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.

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
Sorting
- Insertion sort
- Mergesort
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)
Combinational circuits
- Boolean logic
- AND, OR, NOT gates
- sum-of-products
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.abs()
Math.sin()
Math.cos()
Math.exp()
Math.log()
Math.random()
Math.E
Math.PI

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

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

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()

String data type:  charAt(), substring(), matches(), indexOf(), length()
```
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 sequential circuits, TOY programming, TOY architecture, percolation, programming generics (which includes parameterized types).
Warning 2: Studying questions that ask you to write code is worthwhile, but bear in mind that 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 and the purpose of the programming exam is to test your ability to write code. Also, the time allotment for the written exam is half as long, so there will not be as many questions this year as in the past.