3 hours, during lab on Wednesday, Feburary 15th, 3-6pm
No makeups will be considered without an official University excuse
The exam will consist of two parts:
Written part
50 minutes
Closed book, closed notes
You are allowed a one-sided 8 1/2 x 11 note sheet, hand-written
You are allowed a handheld calculator (not a cell phone or other mobile device)
Programming part
100 minutes
Open web, open notes
This will be like a mini-programming assignment
You may use code from your past programming assignments or from the course web site
You will submit your final program(s) into the Moodle Exam #1 dropbox
Your program will be graded on correctness, clarity (including comments), design, and efficiency
You will lose a substantial number of points if your program(s) do no compile or if they crash on typical inputs
You can use a lab machine or your own laptop
No communication with any non-staff members is allowed.
This includes all forms of real-world and electronic communication (talking, sign language, ESP, email, twitter, IRC, facebook, SMS, posting questions on forums, smoke signals, etc).
Material covered:
Lectures 1-8
Head First Java Ch. 1-11, 16
Programming assignments
Detailed topics:
Topics covered in CSCI 135, but with a heavy emphasis on the topics below:
Abstract Data Types (ADTs): what they are, common examples
Data structures: what they are, common examples
Stack ADT: what it is, basic operations, example applications, LIFO policy
Queue ADT: what it is, basic operations, example applications, FIFO policy
Difference between sequential data structures (arrays) and linked data structures (linked list)
Linked lists: inserting item, iterating through items, deleting an item, implementing a queue/stack using
Dynamic sized ADTs: fixed size vs. doubling array vs. linked list
Java generics: defining a class that can hold any reference type, polymorphism
Java wrapper classes for primitive data types, auto-boxing, un-boxing
Java collections API: set of useful classes that hold things, e.g. ArrayList, HashMap
List: holds a collection of objects and maintains ordering, duplicates can exist in list, e.g. ArrayList, LinkedList
Set: holds a collection of objects, no duplicates, e.g. HashSet
Map: maps keys to values, one key may map to multiple values, e.g. HashMap
Iterating over elements in a List, Set, or Map
Hashing: mapping key to some integer bucket, storing items in separate buckets, why this is superior to storing in single list
Performance, difference between time and space
Empirical order of growth using doubling hypothesis
Given timing data, determine most likely order of growth and constant factor
Extrapolate from existing performance data to larger input sizes
Recognize common code patterns and their order of growth
Efficiency issues with appending to a String object, using StringBuilder instead
Sorting collections using Collections.sort
Making your own data types sortable by implementing the Comparable interface
Programming practice exams:
Princeton has a large collection of past programming exams available online.
A good way to prepare for the programming portion of the exam would be to complete some of these programming exams in a timed-environment.
Note their exams are 50-minutes while ours are 100-minutes.
Also their exams are in a first course for non-majors.
You are in your second course for majors.
They also cover somewhat different material than we do.
