CSE 373: Data Structures and Algorithms, Winter 2013

• final exam
• answer key

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 Practice-It 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):

• practice final exam #1 | answer key
• practice final exam #2 | answer key

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 8-9 questions about topics such as:

• Big-Oh (given a piece of Java code, indicate its complexity class in Big-Oh 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 heap-based 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 path-searching 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
  • d-heaps
  • other kinds of heaps, e.g. leftist, skew
  • other kinds of balanced binary trees, e.g. splay, red-black, b-trees
  • solving recurrence relations

If you are not sure whether you need to study a particular topic, please feel free to ask us.

• midterm exam | answer key

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 Practice-It. 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 Practice-It: 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 Practice-It run to help verify your claim. Because regrades are time-consuming and difficult to judge, we can not accept any exam for a regrade unless it includes this cover page, and we will not re-evaluate grading of the correctess of any programming questions without Practice-It 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):

• practice midterm #1 | answer key
• practice midterm #2 | answer key
• practice midterm #3 | answer key (Practice Midterm #3 will be used as Tue 2/19's section handout. So if you are in a TA section, you may want to wait until after section to look at these problems.)

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:

• Big-Oh (given a piece of Java code, indicate its complexity class in Big-Oh 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 collection-related 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 heap-based 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
  • d-heaps
  • other kinds of heaps, e.g. leftist, skew
  • other kinds of balanced binary trees, e.g. splay, red-black, b-trees
  • 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. extra-terrestrials; 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.