Exams
Final Exam:
Stats:
MEDIAN  80 
MEAN  76.7 
STDEV  14.4 
CURVE  +2 
Grade  #  % of class 
As  34  19.4% 
Bs  57  32.6% 
Cs  37  21.1% 
Ds  24  13.7% 
Es  23  13.1% 
Total  175  100.0% 
class stats (curved scores)
Question  Median  Average  Possible 
Q1 BigOh  7  6.5  10 
Q2 Sort Tracing  10  8.6  10 
Q3 Sort Selection  8  7.2  10 
Q4 Sort Implementation  11  10.6  15 
Q5 Graph Properties  15  14.1  15 
Q6 Graph Paths  13  12.3  15 
Q7 Graph Implementation  10  8.5  15 
Q8 Parallel/Concurrent  8  6.9  10 
question stats

We had to throw out the Q2 (b) quick sort problem because we accidentally copied the same array as on Practice Exam #1.
So we gave everybody who made a reasonable attempt on that problem the full points.
Regrade Policy:
If you disagree with the grading, please follow the same regrade procedure as used on the midterm.
In particular, if you want us to regrade programming problems, you must submit a PracticeIt run of your code as evidence.
All final exam regrade requests must be submitted by the end of the second week of next quarter (Spring 2013).
Practice Exam(s):
Special thanks to TAs Janette and Staci for contributing many of these practice problems and their solutions!
These practice tests are intended to give you a general idea of the kinds of questions you may see on the real exam.
The real exam will have a generally similar number and style of questions as on the practice tests.
However, we do not promise that the real exam will exactly match the practice test in terms of questions, difficulty level, or exact concepts needed to solve each problem.
You are responsible for knowing all class material listed under 'Topics' below.
If you want more practice problems, go back to the Section Handouts from each week and try to solve those problems.
Topics:
The final exam will have approximately 89 questions about topics such as:
 BigOh (given a piece of Java code, indicate its complexity class in BigOh notation)
 Java/Guava collection programming (write a given method that uses Java and/or Guava collections to accomplish a task)

one of the following:
 Hash sets/map simulation (add/remove a given set of elements from a hash set/map using separate chaining and/or linear probing and show the resulting hash table)
 Heap simulation (add/remove a given set of elements from a heapbased priority queue and show the resulting heap tree and/or array)
 AVL tree simulation (add/remove a given set of elements to an AVL tree and show the resulting tree structure)
 Data structure implementation (add a method to a data structure class we have implemented in class, such as
HashSet
, HeapPriorityQueue
, TreeMap
, etc.)
 Sort algorithm tracing (given an array, write out the steps of a sorting algorithm(s) as they are in progress of sorting the array)
 Sort algorithm selection (given a problem situation, choose a sorting algorithm that is effective for sorting the given data)
 Sort algorithm implementation (write Java code to implement a sorting algorithm or a modified version of an existing sorting algorithm that we already learned)
 Graph properties (given a graph, answer questions about general properties of the graph, directedness, weighting, cycles, vertex degrees, internal representation, etc.)
 Graph path searching (given a graph, write out the steps of pathsearching algorithms DFS, BFS, and/or Dijkstra's Algorithm when searching for paths in that graph)
 Graph topological sort (given a graph, perform a topological sort on its vertices)
 Graph implementation (write a method that accepts a
Graph
object and performs a graph algorithm on it; or add a method that would go inside the SearchableGraph
class from HW8)
 Parallel or concurrent code (write code to parallelize a small algorithm, or answer questions about thread safety of a given piece of code)
The following topics are guaranteed NOT to be required to solve any problems on the final exam:
 writing proofs
 implementing an
Iterator
 Guava's
Range
related classes
 writing a
Comparator
or implementing the Comparable
interface
 any material we have not covered in lecture/homework, such as:
 double hashing
 quadratic probing in hash tables
 dheaps
 other kinds of heaps, e.g. leftist, skew
 other kinds of balanced binary trees, e.g. splay, redblack, btrees
 solving recurrence relations
If you are not sure whether you need to study a particular topic, please feel free to ask us.
Midterm Exam:
Stats:
MEDIAN  74 
MEAN  71.0 
STDEV  16.2 
CURVE  +6 
Grade  #  % of class 
As  44  24.7% 
Bs  46  25.8% 
Cs  33  18.5% 
Ds  32  18.0% 
Es  23  12.9% 
Total  178  100.0% 
class stats (curved scores)
Question  Median  Possible 
Q1 BigOh  12  15 
Q2 Collections  14.5  20 
Q3 Hashing  12  15 
Q4 Heaps  15  15 
Q5 AVL Trees  12.5  15 
Q6 Implementation  10  20 
question stats
Regrade Policy:
If you disagree with the grading, such as if you think your solution actually does work, or that your solution is more nearly correct than it was given credit for, the procedure for regrades is the following:
 If your complaint is about the correctness of your solution to a programming question (#2 and/or #6), type your code into PracticeIt. Fix any trivial syntax problems. Run it for yourself and see how nearly correct your solution is.
 If you feel your grading is incorrect after testing in PracticeIt: Submit your exam for a regrade. Slide it under Marty Stepp's office door, CSE 636. You must include a cover page with a brief written explanation of what specifically you think was misgraded and why. If your complaint is about overly harsh grading on a programming question, you should also include a printout of your PracticeIt run to help verify your claim. Because regrades are timeconsuming and difficult to judge, we can not accept any exam for a regrade unless it includes this cover page, and we will not reevaluate grading of the correctess of any programming questions without PracticeIt information being submitted by you first.
 Also note: When you submit an exam for a regrade, we will regrade your entire exam. If we notice anywhere that you were mistakenly given too many points, we will also correct this. So it is possible that a regrade request will result in you receiving a slightly lower mark than what you started with. We are not saying this to be mean, and we will not go out of our way to try to find things to take away points for. But we will make a brief look at your whole exam to make sure that everything is graded properly, whether that increases or decreases the overall score.
 We will not accept any regrade requests where the reason for regrading is essentially, "The grader didn't see my answer that was written on (the back side of the page / my scratch paper / elsewhere on the page)." Because it is too easy to add answers to these places after the exam, unfortunately we must trust that the grader was able to find all of your work and grade it appropriately. If this was not the case, we must assume that you did not sufficiently clearly label where the grader was supposed to look to find your work, and therefore that you are responsible for any such grading mistake.
 All midterm regrade requests must be submitted within one week of the date that midterms are given back.
Practice Exam(s):
These practice tests are intended to give you a general idea of the kinds of questions you may see on the real exam.
The real exam will have a generally similar number and style of questions as on the practice tests.
However, we do not promise that the real exam will exactly match the practice test in terms of questions, difficulty level, or exact concepts needed to solve each problem.
You are responsible for knowing all class material listed under 'Topics' above.
If you want more practice problems, go back to the Section Handouts from each week and try to solve those problems.
Topics:
The midterm exam will have approximately up to 7 questions about topics such as:
 BigOh (given a piece of Java code, indicate its complexity class in BigOh notation)
 Java collection programming (write a given method that uses Java collections to accomplish a task)
 Guava collection programming (write a given method that uses Guava collections to accomplish a task)
 Java class collectionrelated programming (write a fundamental Java class method such as
equals
, hashCode
, compareTo
; write a Comparator
; etc.)
 Deque implementation programming (add a given method to your
ArrayDeque
class from HW3)
 Hash sets/map simulation (add/remove a given set of elements from a hash set/map using separate chaining and/or linear probing and show the resulting hash table)
 Hash map implementation programming (add a given method to your
HashMap
class from HW4)
 Heap simulation (add/remove a given set of elements from a heapbased priority queue and show the resulting heap tree and/or array)
 Heap priority queue implementation programming (add a given method to your
HeapPriorityQueue
class from HW5)
 AVL tree simulation (add/remove a given set of elements to an AVL tree and show the resulting tree structure)
The following topics are guaranteed NOT to be required to solve any problems on the midterm exam:
 writing proofs
 implementing an
Iterator
 Guava's
Range
related classes
 any material we have not covered in lecture/homework, such as:
 sorting algorithms
 search algorithms e.g. binary search
 double hashing
 quadratic probing in hash tables
 dheaps
 other kinds of heaps, e.g. leftist, skew
 other kinds of balanced binary trees, e.g. splay, redblack, btrees
 solving recurrence relations
 ...
If you are not sure whether you need to study a particular topic, please feel free to ask us.
Resources:
You are permitted to bring and use any of the following resources on your exam:
 your course textbook or any other textbook
 scratch paper, writing utensils, standard office supplies
 practice exams or their solution keys
 printed homework solutions
 section handouts
 any other papers or documents
You are not permitted to use any other resources on the exam, such as:
 any electronic devices such as calculators, computers, mobile phones, tablets, laptops, music players
 friends or other humans
 other intelligent life forms that might give you answers (e.g. extraterrestrials; cats)
We will bring a single loaner copy of the textbook that you may be able to use during the exam.
But there may be a waiting queue to use them, so you may want to have your own copy with you if you believe you will need it.
If you are found using a forbidden resource during the test, you will be penalized.
This document and its content are copyright © Marty Stepp, 2013. All rights reserved.
Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form
is prohibited without the author's expressed written permission.