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

==========
Final Exam
==========

Final Exam Structure
--------------------

.. revealjs-slide::

* In the regular classroom at the time specified for your section by
  the University.
* 100 points
* Format

  * Similar to Midterms
  * The questions of of types that we can autograde:
    Multiple Choice, True/False, fill-in-the-blank, etc.
  * 40-45 questions
  * While the official time available is 2 hours, the exam is not too
    much longer than the midterms.

* Anything covered during the semester is fair game, but the focus is
  on material not covered in the midterms, plus some integration
  questions.


Topics (1)
----------

.. revealjs-slide::

* Section 7.17-18: Huffman Coding Trees

  * An example of a Full Binary Tree, and a Trie

* Chapter 9: File Processing

  * Fundamental differences between RAM and peripheral storage, and
    how they affect performance and program implementation.
  * Buffer pools: How they work and the LRU replacement algorithm
  * External Sorting principles

* Chapter 11: Memory Management

  * Sequential Fit methods: First Fit, Circular First Fit, Best Fit,
    Worst Fit

  * Buddy Method

  * Failure policies and garbage collection
    
Topics (2)
----------

.. revealjs-slide::

* Chapter 12: Indexing

  * What is an index?

  * Linear Indexing

  * Principles of tree-based indexing (goals to minimize disk
    accesses)

  * 2-3 Trees and B-trees

    * Focus on B+ Trees.
    * Know the basic algorithms for insert and delete.

* Chapter 13: General Trees

  * Union/FIND algorithm and what it is used for
  * General tree representations
  * Sequential tree representations and serialization

Topics (3)
----------

.. revealjs-slide::

* Chapter 14: Graphs
  
  * Representations: Adjacency Matrix and Adjacency List
  * Graph Traversals: Depth First and Breadth First
  * Topological Sorting (two algorithms)
  * Shortest Paths problems

    * Single-source shortest paths: Dijkstra's algorithm (and two
      approaches to implementing minVertex)

    * All-pairs Shortest Paths: Floyd's Algorithm

  * Minimal Cost Spanning Trees: Prim's Algorithm (similar to
    Dijkstra's algorithm) and Kruskals's algorithm (uses Union/FIND)

* Chapter 15

  * Skip Lists: Randomized Algorithm

  * (You don't need to know the spatial data structures)

Topics (4)
----------

.. revealjs-slide::

* Integration questions:

  * Be prepared for questions that ask about what
    is the best data structure or algorithm for a given situation.

  * In particular, know when is the most appropriate time to use
    various search structures like Hash Tables, BSTs, Linear Index,
    B-tree.