College of Computer Science, Northeastern U., Boston, MA

The quiz will last the entire class period. Closed book, no calculators allowed. I plan to return the return the graded quiz to you on Monday, January 31st and go over the answers at that time.

**Important: I will spend all of Tuesday's class, the 25th, reviewing for the quiz.
Be there!**

Here is a brief description of the some of the topics that may be included:

- The Quick-Find algorithm -- code analysis for data pairs input I will give you and drawing diagrams of the algorithm in operation. Any code you might need will be given to you.
- The Quick-Union algorithm -- as above.
- Sequential search. How the code works. Complexity of the search -- best, average, worst-case.
- Binary search. As above.
- Complexity analysis of some data. Using estimates by powers of 2, decide on the complexity class of some runtimes I give you for various N's.
- Iteration of a recurrence relation to derive the complexity of an algorithm.
- Breaking up code into the proper files. I will give you a single piece of code with various definitions, including a main(). You are to indicate how it would be broken into three files, and use the proper terminology to motivate and explain your breakup and anything you might need to add to make the breakup complete and consistent. Some of your explanation of what you do should be in the form of source code comments.
- Some topic drawn from Chapter 3, to be decided. One example would be the two methods of representing graph structures, discussed starting with the last paragraph of pg. 121 and going through the next-to-last paragraph of pg. 124.

113 112 108 105 104 102 101 100 93 92 92 91 91 89 89 86 86 85 85 84 83 83 83 82 81 79 77 75 72 68 63 61 60 57 49

Note that I only gave myself a "90" on my writing of the test. So I gave everyone an extra 10 points to make up for the imperfections in the exam. The grade written on the your exam includes the 10 point bonus.

I am very sorry that eleven people did not come to class on Monday to hear the answers and the ideas discussed at length. I'm particularly concerned about the students who did not do very well on the quiz and could have profited from the discussion but did not show up in class.

Please do everything you can to make it to class. The textbook is long and potentially complex. But if you come to class you'll see that I'm doing my best to make the material understandable and also to focus on particular concepts and strategies rather than trying to cover large amounts of material.

-- Prof. Futrelle

Go to Syllabus and Calendar page for COM1201

Return to Prof. Futrelle's home page