Reading 03

The assigned reading prior to Tuesday, February 13th is an re-review of heaps, heap sort and related priority queues. We'll also ask a followup questions to quick sort since you should've completed Project2 by now.

You are also allowed to (re)look at Dr. Plank's/my notes and google if you so choose.

Please refer to:

  1. Data Structures and Other Objects Using C++:

    • Chapter 10.1-2, 10.4 Review

      15.1 - 15.3

    • Chapter 11.1-2 (also a review)

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • 5.5 Heaps and Priority Queues

      11.1 - 11.3

    • 7.6 Heapsort

  2. Open Data Structures

Questions (due 2/13, 1:30pm)

Once you have completed the readings, please answer the following questions:

  1. Look over the lecture notes from Dr. Plank and the discussion therein. Why do you think most real-world sorting (i.e., C++ Sort) implementations use some form of quick sort?

  2. When inserting an entry into a binary heap, we must perform reheapification. What is the purpose and complexity of this process?

  3. Briefly explain what it means for a graph to be: A. Connected? B. Acyclic? C. Directed? D. Simple? E. Weighted?

  4. What is a reason for using an adjacency matrix instead of an adjacency list to represent a graph?

Submission

To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class