.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer

.. slideconf::
   :autoslides: False

=========
Midterm 2
=========

Midterm 2
---------

.. slide:: Midterm 2

   | Scheduled for Tuesday, November 7
           
.. slide:: What to study (1)

   | Chapter 7: Heaps
   |        
   | Chapter 8: Sorting
   |    :math:`O(n^2)` sorts: Insertion sort, Bubble Sort, Selection Sort
   |    Cost of exchange sorting
   |    Shellsort
   |    :math:`O(n \log n)` sorts: Mergesort, Quicksort, Heapsort
   |    Binsort and Radix Sort
   |    Proof that Sorting lower bound is :math:`O(n \log n)'.
   |
   | Chapter 9: File Processing
   |    Memory hierarchy: RAM vs Disk Drives
   |    Buffer Pools


.. slide:: What to study (2)


   | Chapter 10: Hashing
   |    Hash Functions
   |    Open hashing vs. bucket hashing vs. closed hashing
   |    Collision resolution methods: linear probing, linear
        probing by steps, pseudo-random probing, quadratic probing,
        double hashing
   |    Deletion