## Notes for Quiz #1 -- To be given Monday, April 24th

#### (Version of 4/22/00)

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 Thursday the 27th and go over the answers at that time.

Here is a copy of last quarter's quiz. The first four questions are similar to what will appear on the Spring quiz. Ignore the fifth question.

I spent all of Thursday's class, the 20th, reviewing for the quiz. Feel free to email me with questions before the quiz, futrelle@ccs.neu.edu.

Here is a brief description of the some of the topics that may be included. Not all will, of course:

• Quick-Find and Quick-Union algorithms
• The Quick-Find algorithm -- code analysis for data pairs input I will give you and/or drawing diagrams of the algorithm in operation. Any code you might need will be given to you.
• The Quick-Union algorithm -- as above.

• The following two examples were not discussed in the review, but you should be ready to answer such questions.
• Sequential search. How the code works. Complexity of the search -- best, average, and worst-case.
• Binary search -- as above.

• Iteration of a recurrence relation to derive the complexity of an algorithm.

• Graphs
• Understand the relation between adjacency-list representations of graphs and adjacency matrix representations. Similar to question 3 on last quarter's exam.
• Graph traversal, if included, would only be as an extra-credit question.

• Sorting
• You should understand the difference between a stable and unstable sort and be able to produce figures similar to Fig. 6.1 for data I give you.
• For insertion sort, I would give you the code of Prog. 6.1 and/or Prog. 6.3. You need to be able to show a small number of steps in an insertion sort and how they relate to execution of the statements in the code.

Go to Syllabus and Calendar page for COM1201