It's time for your FINAL computing exam wooo! View this not as an intimidating obstacle to be overcome, but a chance at reflection to see how much you've learned and where your gaps of knowledge may be.

Here's how this is going to go:

• The "exam" will be largely programmatic with some conceptual elements to test your understanding of the material.

• The exam will take place in our typical classroom and will last only 90 minutes; see the final exam schedule for the time and day:

  LMU Final Exam Schedule

• The exam is non-cumulative and will only quiz you on the material after the midterm. See topics of exam below.

• The exam is CLOSED note and CLOSED computer. You may NOT collaborate with peers or any other person during the duration of the exam.

• You are allowed to bring ONE 8.5" x 11" (double sided) cheat sheet with any information you'd like with you for consultation into the exam.

Grading

• The exam may feel long, but that's OK! Take your time, a deep breath or two, and don't worry if you don't finish everything -- it will be likely that your classmates do not either, which will be by design.

• The exam does not have a forced curve (i.e., that only some set number of people can receive A's, B's, etc.), but it WILL have a difficulty adjustment (upward bonus) if it was too hard.

• Remember the class' exam policy: your worse exam counts for half as much as the other. If your midterm grade wasn't where you wanted it to be, here's your chance to catch up!

• The last question on the exam will always be a bonus to illustrate a pun on this section's material; come prepared with an idea, those are easy points.

This exam will cover the topics only in this half of the class. These include:

• Runtime Analysis: objectives of runtime complexity, total cost functions (T(n)), asymptotic analysis, big-O notation, and how each relates to heretofore covered data structure operations (including Lists).

• Trees: vocabulary (children, parents, ancestors, descendants, height, tree-depth, etc.) structure, implementation, n-ary and binary trees, traversal methods, and implementing recursive algorithms.

• Binary Search Trees: binary search, semantics of node organization, algorithms for search and insertion (including being able to perform by hand), utility of inorder traversal, balance-factors (just be able to identify trees that are balanced / unbalanced by the AVL definition), implementations of TreeSets, runtime complexities.

• Tries: utility for storing lexical data, implementations as ternary search trees, operations such as membership search and insertion, (though with no expectations for programming parts of one).

• Heaps: node vs. array-based representation, semantics of node structure, operations for insertion, removal, re-heapifying (including being able to perform by hand), implementations of PriorityQueues, JCF PriorityQueue, runtime complexities.

• Hash Tables: basic properties and performance guarantees, hash functions (including design, desirable traits, and pitfalls), collisions, load factor, rehashing, the "checkAndGrow" behavior akin to ArrayLists', Entries and implementations for Maps and Sets.

• Graphs: basic properties, differences from trees, implementations (Node-based vs. adjacency maps), traversals.

• Data Structure Decisions: data types vs. data structures, knowing when to use certain implementations over others (e.g., Hash vs. Tree Sets), and how to use certain JCF collections (I'll provide all methods you need, no need to memorize any interfaces, but you should know, e.g., what put(key, value) does on a HashMap).

Things you do *NOT* need to know for the exam:

• Problem vs. Solution complexity (as mentioned with the GCD example in L8-1)

• Tree balancing algorithms, including tree rotations. Don't need to know anything about red-black trees.

• Undirected graphs, adjacency matrix graphs, Djikstra's algorithm.

The examination format may include:

• Vocabulary and fill-in-the-blank questions

• Multiple choice

• Understanding drawings of trees, heaps, hash tables, etc

• Structured-response code writing (I give you a skeleton, you fill in the requested parts)

Be prepared to answer some questions similar to those on the assignments and in-class exercises.

Furthermore, although I won't ask you anything about mechanics we haven't covered in class, you might be expected to apply the mechanics we've learned about in a way that we didn't see in class. If you thoroughly understand the material, there should be no surprises, but still challenges.

Here is my suggestion for preparation order:

1. Re-read my course notes, re-doing the exercises if you aren't clear on any of them. Note that there are also suggestions for activities we did NOT see in class that will make for good practice.

2. Study any available classwork and homework solutions.

3. Consult the syllabus' recommended extra-practice sites for problems on topics that you're still unfamiliar with; there are plenty for all of our data structures.

4. Still not confident on a topic? Feel free to ping on Slack and ask anything, including requests for questions / specifications on a particular problem type.