**COM 1201 Algorithms and Data Structures 2**

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

#### Spring 2000 -- Professor Futrelle

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

#### (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

Return to Prof. Futrelle's home page