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