CS 161 Midterm: CS 161 Midterm Winter 2016

• School: Stanford University
• Department: Computer Science
• Course: CS 161
• Professor: all

Document Summary

Instructions: please answer the following questions to the best of your ability. If you are asked to design an algorithm, please brie y describe your algorithm, analyze its running time, and prove its correctness. If you are asked to show your work, please include relevant calculations for deriving your answer, explaining steps as you go. If you are asked to prove a result, please write a complete proof at the level expected on your homework. When writing proofs, please strive for clarity and brevity (in that order). You have 75 minutes to complete the exam. You may use 1 sheet (front and back) of notes as reference. The last page of the exam is a blank page (you may use it as scratch paper or write your answers). By signing your name below, you acknowledge that you have abided by the stanford honor code while taking this exam. Recall that a bst is a binary search tree.