{"content":[{"text":"Design and Analysis of Algorithms Exam","bbox":{"left":0.213858,"top":0.103485,"width":0.572496,"height":0.021758}},{"text":"• This is a closed book exam; only 1 sheet (both sides) of handwritten notes is permitted. \n • No cell phones, calculators, nor any other electronics. \n • You will have 135 minutes for this exam. \n • It consists of 5 problems worth 50 points each, plus a problem 6 for an extra 30 points credit. \n • Make sure you have answered all problems from the ﬁrst 5 problems before moving on to \n problem 6. \n • Your score will be taken out of 225 points. \n Instruction \n Work as many problems as possible. All problems have the same value, but subparts of a problem may \n have diﬀerent values (depending on their diﬃculties, importance, etc). Provide a short preliminary \n explanation of how an algorithm works before running an algorithm or presenting a formal algorithm \n description, and use examples or diagrams if they are needed to make your presentation clear. \n Please be concise and give well-organized explanations. Long, rambling, or poorly written/organized \n explanations, which are diﬃcult to follow, will receive less credit.","bbox":{"left":0.08726,"top":0.150115,"width":0.8283090000000001,"height":0.292296}},{"text":"Grading \n Expect questions of the following form (note that a problem may consist of a few questions):","bbox":{"left":0.088235,"top":0.46378,"width":0.777753,"height":0.03334999999999999}},{"text":"• A series of short-answer questions. For example, I may ask you to provide a deﬁnition, \n explanation, or run time analysis. Although the answers are short, some of the questions may \n require some thought. Don’t worry about skipping a question, or guessing an answer, if you \n don’t see the answer right away.","bbox":{"left":0.116722,"top":0.508719,"width":0.797775,"height":0.07020699999999991}},{"text":"• Work through some algorithm on a given input, showing intermediate results. I’ll pick the \n algorithm at random because I want you to learn them all. For some more complex algorithms \n (e.g. matrix chain product), I may ask you to do only one operation.","bbox":{"left":0.116722,"top":0.59301,"width":0.795179,"height":0.051966999999999874}},{"text":"• Design and analyze simple algorithms. These are much more unpredictable. I try to ask at \n least a couple of questions that involve a very simple modiﬁcation to a homework problem, so \n be sure you understand the solutions to all the homework problems. Other questions usually \n involve a slight modiﬁcation to a problem that we have worked on in class.","bbox":{"left":0.116722,"top":0.659062,"width":0.795819,"height":0.07020499999999996}},{"text":"• One challenging problem. Don’t be upset if you cannot solve this problem. (But at least be \n sure to read it, since sometimes the problem is not as challenging as I think it is, and there \n may be a very simple solution.) If you cannot see how to solve the problem, feel free to write \n down your wild ideas or observations. You might get some partial credit if your idea is good.","bbox":{"left":0.116722,"top":0.743352,"width":0.798861,"height":0.07020599999999999}},{"text":"When it comes to grading, I tend to give more credit for insight than for memorization. For \n example, if a problem involves inorder traversal of a binary tree, you will get little credit for just \n writing down the algorithm. (You could just copy that out of your cheat sheet.) However, if you \n can say something intelligent about the mathematical structure of the particular problem, or about \n why some approach is not useful, you may get some partial credit (depending on how much your \n observation indicates about your understanding of the problem).","bbox":{"left":0.087547,"top":0.825525,"width":0.824867,"height":0.10630799999999996}}],"images_bbox":[],"images_bbox_not_text_overlap":[]}