COS 126 Exam 2 Information, Fall 2011

Q+A.

There will be a Q+A Wednesday night, December 14, beginning at 7:30pm, Friend 101.

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

Written exam rules.

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, 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.
Room assignments:
All COS126 students in precepts P01, P01A, P01B, P02, P02A, P02B, P02C, P03, P04, P06 will take the written exam in McCosh 10 on Thursday, December 15 at 10am.
All COS126 students in precepts P05, P05A, will take the written exam in McCosh 4 on Thursday, December 15 at 10am.

Programming exam rules.

50 minutes, during precept on Thursday, December 15 or Friday, December 16.
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 enough power outlets for everyone).
Set up an empty directory named Exam2 on your laptop that can access StdIn.java, StdOut.java and StdDraw.java. This directory should also have the following implementations from the booksite: Picture.java, ST.java, Stack.java and Queue.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 (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.
Programming exam rooms:
P01: Friend 101 on Thursday, December 15 at 12:30 pm
P01A: Friend 101 on Thursday, December 15 at 12:30 pm
P01B: Friend 101 on Thursday, December 15 at 12:30 pm
P02: Friend 101 on Thursday, December 15 at 1:30 pm
P02A: Friend 101 on Thursday, December 15 at 1:30 pm
P02B: Friend 101 on Thursday, December 15 at 1:30 pm
P02C: Friend 101 on Thursday, December 15 at 1:30 pm
P03: Friend 108 on Thursday, December 15 at 2:30 pm
P04: Friend 108 on Thursday, December 15 at 7:30 pm
P06: Friend 004 on Friday, December 16 at 12:30 pm
P05: Friend 109 on Friday, December 16 at 1:30 pm
P05A: Friend 110 on Friday, December 16 at 1:30 pm

Material covered.

The exam will cover all material in the course, but with an emphasis on the material covered after Exam 1:

Introduction to Programming in Java, Sections 3.1-3.3, 4.2-4.4.
Introduction to Programming in Java, Booksite 7.1-7.7
On-line Chapter 7 (link on Lecture page).
On-line Chapter 6 (link on Lecture page).
Booksite 5.1-5.4 TOY.
Lecture notes 10-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 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.

Number representation.
- Binary, decimal, hexadecimal. Two's complement notation.
TOY machine.
- Basic features and components (and how it relates to Java and real computers).
- Parsing and interpreting TOY instructions.
- Tracing through small TOY programs that do assignment statements, arithmetic, loops, conditionals, arrays, functions.
- We will supply the TOY reference card.
Using data types
- declaring variables
- invoking constructors
- invoking methods
- reference types vs. primitive types
Creating data types
- instance variables
- constructors
- instance methods
- static constants
Designing data types
- encapsulation (public/private)
- modular programming
- immutability
Sorting
- Insertion sort
- Mergesort
Data structures
- linked lists
- binary trees
- stacks and queues
- symbol tables
- enhanced for loop to iterate through objects (see p.588 and p.629)
- which data structure is appropriate for which application
Programming Languages
- Different philosophies: see Lecture 17 slide 22
- Features: encapsulation, type checking, libraries, immutability
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)
Combinational circuits
- Boolean logic
- sum-of-products
- Combining gates to make circuits

Designing a CPU

Building blocks
Organization
Layers of Abstraction

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.log()
Math.random()
Math.E
Math.PI

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

StdOut.println()
StdOut.print()
StdOut.printf()

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

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

StdDraw.line()
StdDraw.point()
StdDraw.circle()
StdDraw.setXscale()
StdDraw.setYscale()
StdDraw.clear()
StdDraw.show()
StdDraw.picture() 
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()

Color data type: getRed(), getGreen(), getBlue()  

Picture data type: width(), height(), get(), set(), show(), save()

Queue data type: isEmpty(), size(), enqueue(), dequeue()

Stack data type: isEmpty(), size(), push(), pop()

ST data type: put(), get(), contains()

BST data type: size(), put(), contains(), get()

How to use enhanced for loop to iterate through Queue, Stack, ST or BST.

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 circuit timing diagrams, percolation, 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.