Final Oral Exam Info

What to expect

The final for this quarter will be a 5 to 10 minute oral exam. If you have not already signed up, please do so here. A zoom link will be emailed to you on Sunday, 8/15. You will meet with a staff member at that link during your scheduled timeslot. The exam will be very conversational and is designed to give you one last opportunity in this class to practice communicating your thinking about data structures & parallelism before you may have to do so in an actual interview. Therefore, you should consider treating this almost like an interview: we encourage you to turn on your camera so you can practice communicating while also being conscious about your body language, eye contact, etc (As always, this is optional, but this time very heavily encouraged). Your session will be optionally recorded, however if you opt out of recording we will not accept regrade requests.

In the exam, we will ask you 2 questions which you may spend 3 to 5 minutes answering each. The questions will be very conceptual and we will be listening for you to explain specific points for each question we ask (see Checkboxes under Grading). The questions we ask will be one of the following:

• What can you tell us about X?
• How would changing Y in X affect X?
• Explain why X is good/better/useful.
• Please give us an example of X.

Disclaimer: If you are late or miss your timeslot, we cannot guarantee a make up time. This may result in a poor grade. If you need to reschedule, please email the staff list at least 24 hours in advance so we can try to coordinate a make up time.

Grading

We will post a rubric for the subjective portions here by the weekend. The current grading breakdown is as follows:

• 40 points: Checkboxes based on the questions asked (ie, did you talk about X?)
• 10 points: Accuracy of information (Do you know what you're talking about?) Rubric will be from 1 to 5 and multiplied by 2 to make it 10 points
  • 5: Shows a full understanding of the topics
  • 4: Shows a good, but incomplete understanding of the topics
  • 3: Shows good understanding about parts of the topic
  • 2: Does not seem to understand things well
  • 1: Nothing said was correct
• 10 points: Clarity & Communication (Did you explain your thought process clearly?) Rubric will be from 1 to 5 and multiplied by 2 to make it 10 points.
  • 5: Clearly articulated explanations, organized, provides examples and underlying thought processes when appropriate
  • 4: Clearly articulated explanations, but no gives no insight into how the students think about the problem
  • 3: Mostly clear explanations, but hard to understand the logic, somewhat unorganized
  • 2: Unclear, unorganized explanations, all over the place
  • 1: Staff member has no idea what the student is talking about
• 10 points: Post exam reflection

You will receive an email in the evening after your exam with the checkboxes portion of your grade as it stands. There will be a question on the reflection in which you will be able to make back up to half the points you missed in this section.

Topics

• ADTs vs Data Structures
• Stacks, Queues, Lists
• Big Oh (and Omega & Theta)
• Amortization
• Recurrence Relations
• Binary Heaps
• Tries
• Dictionary ADT: insert, find, delete:
  • Binary Search Trees
  • AVL Trees
  • B+ Trees
  • Hash Tables
• Sorting
• Sorts:
  • Simple Sorts: Insertion Sort, Selection Sort
  • Heap Sort
  • Merge Sort
  • Quick Sort
  • Bucket Sort & Radix Sort
• Know run-times
• Know how to carry out the sort
• Lower Bound for Comparison-based Sorting
• Won't be asked to give full proof
• But may be asked to use similar techniques
• Be familiar with the ideas
• Graphs
• Graph Basics
  • Definition; weights; directedness; degree
  • Paths; cycles
  • Connectedness
  • DAGs
• Graph Representations
  • Adjacency List
  • Adjacency Matrix
  • What each is; how to use it; pros and cons of each.
• Graph Traversals
  • Breadth-First
  • Depth-First
  • What data structures are associated with each?
• Topological Sort
• Dijkstra's Algorithm for Finding Shortest Paths
• Parallelism
• ForkJoin Parallelism, and Associated Terms (Work, Span, etc.)
• ForkJoin Applications, ex: Parallel Summing of an Array
• Reduce: parallel sum, multiply, min, find, etc.
• Map: bit vector, string length, etc.
• Parallel Prefix Sum Algorithm, Filters, etc.
• Analysis of Parallel Algorithms
• Parallel Sorting
• Amdahl's Law
• Concurrency
• Race Conditions
• Data Races
• Bad Interleavings
• Synchronizing your code
  • Locks, Reentrant locks
  • Java's synchronized statement
  • Issues of lock scheme granularity: coarse vs fine
  • Issues of critical section size
  • Deadlock