**********************
Midterm 2 Topic Review
**********************

How to use this document
========================
+ All contents covered in Midterm I will not be specifically tested but will
  likely to be used in the questions.
+ Self-test using this document to see what concepts are challenging to you
+ Course notes document is the main resource for tips, pitfalls. High priority
  in midterm preparation.
+ Review all participation activities and challenge activities in zyBook
+ Practice your ability to finish the patterns listed here from scratch without
  the help from any editor/ IDE

Templates
=========
Concepts
--------
+ A function template is not a function
+ The instance of a function template is a function
+ A class template is not a class
+ The instance of a class template is a class

Syntax
------
+ The template clause must be used right above all entities using the typename

  * function declarations and definitions
  * class declarations
  * out-of-line method definitions

+ Single header module for templates

Linked-List
===========
Implementations
---------------
+ singly-linked

  * head pointer
  * tail pointer (optional)
  * node with next pointer
  * Cannot access previous node easily

+ doubly-linked

  * head pointer
  * tail pointer (optional)
  * node with next and prev pointers

+ Implementation details

  * recursive vs iterative
  * empty linked list is handled as a special case
  * first, last and middle nodes are handled differently
  * big three
  * search
  * insert before
  * insert after
  * remove

+ Compared to Array

  * dynamic size
  * insertion and removal are efficient
  * access by index is inefficient

Linear ADTs
===========
List
----
+ Sequential
+ Behaviors

  * add and remove at any position
  * search
  * access by index
  * check size

Stack
-----
+ LIFO or FILO
+ Implementation

  * Mostly as a linear data structure
  * linked-list
  * partially filled array

+ Behaviors

  * push
  * pop
  * peek/top
  * check empty

Queue
-----
+ FIFO or LILO
+ Implementation

  * Mostly as a linear data structure
  * linked-list
  * circular partially filled array (FYI)

+ Behaviors

  * enqueue
  * dequeue
  * peek
  * check empty

Deque
-----
+ Double-ended queue
+ Implementation

  * Mostly as a linear data structure
  * linked-list
  * circular partially filled array (FYI)

+ Behaviors

  * enqueue at both ends
  * dequeue at both ends
  * peek at both ends
  * check size

Wrapper class
-------------
+ One ADT can cover the usage of another ADT
+ Wrapper class
+ E.g. wrap the std::vector class to implement a Stack
+ E.g. wrap Deque to implement Stack and Queue

Sorting
=======
+ Sorting algorithms concepts

  * in-place (only swap) vs out-of-place (move data to another array)
  * general purpose (comparison based) sorting algorithms vs non-comparison
    based sorting algorithms
  * stable vs unstable (whether the original order of duplicate elements is
    preserved, FYI)
  * best complexity for comparison based sorting algorithms :math:`\Theta(n \log n)`

+ Quick sort

  * **Quick partition** as a sub-algorithm

    - Our variation of Hoare's scheme (different from the zybook algorithm,
      refer to the lab)

  * in-place algorithm
  * time complexity: :math:`\Theta(n \log n)` or :math:`\Theta(n^2)` in the
    worst case

+ Merge sort

  * top-down merge sort
  * out-of-place algorithm
  * **sorted merge** as a sub-algorithm
  * time complexity :math:`\Theta(n \log n)`
  * space complexity :math:`\Theta(n)`

+ Radix sort

  * not a general algorithm
  * out-of-place algorithm
  * time complexity :math:`\Theta(nk)` where :math:`k` is the number of digits
  * space complexity :math:`\Theta(n)`

+ Linked-list based sorting

  * recursive vs iterative
  * not all sorting algorithms are suitable
  * insertion sort

    - sorted insert

  * merge sort

    - sorted merge

Hashing
=======
+ Applications: hash table, cryptography, fingerprinting, checksum, etc.
+ Hash function

  * mapping data to data
  * collision - different keys mapped to the same hash value

Hash table
----------
+ Hash table

  * Requirements

    - Unique keys

  * Characteristics

    - fast lookup :math:`\Theta(1)`
    - redundant storage space
    - performance degradation when overfilled

      + load factor

  * buckets
  * hash function

    - key -\> index
    - modulo operator

  * collision

    - different keys mapped to the same index
    - something we always need to handle

  * collision resolution methods

    - chaining: let each bucket hold more than one element
    - open addressing: find another empty bucket

      + Probing methods

        * linear :math:`[h(key) + c*i]\%n`
        * quadratic :math:`[h(key) + c_1*i + c_2*i^2]\%n`
        * double hashing :math:`[h1(key) + c*i*h2(key)]\%n`

+ ADTs that are implemented using hash tables

  * hash map (key-value pairs)
  * hash set (only keys)

    - when we do not care about values

Patterns
========
+ Write a function template
+ Write a class template
+ Write C++ class declarations to describe ADTs (only need to write the
  declarations of public methods)
+ Write methods of common operations of linked-lists
+ Write sorting algorithms as functions (take C array as parameter)
+ Master how quick partition works on paper
+ Master how sorted merge works on paper
+ Write insertion sort on linked-list
+ Master open addressing collision resolution methods on paper

  * Calculate

    - hash value
    - probing sequence

  * Simulate how probing works on paper