The readings for Monday, September 12 are:

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

• Chapter 10.1-2, 10.4 Review

• Chapter 11.1 - 2, 11.4

• Chapter 13.1, 13.3

2. VisuAlgo - Sorting

#### TL;DR

The focus of the reading is on priority queues, binary heaps, insertion sort, selection sort, and heap sort.

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

• 7.1 Sorting Terminology and Notation

• 7.2 Three O(n^2) Sorting Algorithms

• 7.6 Heapsort

2. Open Data Structures

## Questions

Once you have completed the readings, answer the following questions in the `reading03/README.md` file in your assignments repository:

1. Identify which of the following trees is a maximum binary heap? If a tree is not a maximum binary heap, explain why.

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

3. Trace the execution of selection sort for an array containing ```{9, 6, 0, 0, 7}```. That is show the contents of the array after each iteration of the sorting algorithm.

4. Trace the execution of insertion sort for an array containing ```{9, 6, 0, 0, 7}```. That is show the contents of the array after each iteration of the sorting algorithm.

## Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 03 - TA assignment list.

#### Development Branch

To facility the Merge Request workflow, you must do your development in its own branch:

```\$ cd path/to/repo                 # Go to your repository
\$ git checkout master             # Make sure we are on master branch first
\$ git pull                        # Make sure we have changes from GitLab
\$ git checkout -b reading03       # Create reading03 branch
...                               # Do your work
\$ git commit                      # Commit your work (can do this multiple times)
\$ git push -u origin reading03    # Push branch to GitLab
```