******************
Final Topic Review
******************
**The final exam is comprehensive. This outline focuses on contents after
midterm II and should be used together with the past midterm reviews.**

Materials to prepare (sorted by the order of importance)
========================================================
#. Practice exam
#. Past midterm exams
#. Past projects (know what you did wrong)
#. This outline and outlines for past exams
#. Course notes website
#. Zybook content and activities

Hint and tips for preparation
=============================
+ All contents covered in the semester will be tested
+ 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.
+ The past midterm exams are important materials to prepare.
+ Re-do all participation activities and challenge activities in zyBook
+ Practice your ability to finish the patterns listed here from scratch without
  editor or IDE

Tree
====
+ Concepts

  * definition

    - graph theory: connected undirected graph
    - computer science: root and sub-trees

  * recursive definition
  * terms: tree, sub-tree, node, root, leaf, internal node, edge, parent,
    child, sibling, ancestor, descendant, height, path, ordered

+ Binary tree

  * definition
  * ordered, degree 2
  * full tree, complete tree, perfect tree

+ Binary search tree

  * definition
  * applications
  * behaviors (know the big O complexity)

    * search
    * insert
    * remove/delete
    * in-order traversal

  * implementation

    * node class
    * BST class
    * implementation of behaviors

Heap
====
+ Logically a complete binary tree, physically an array
+ Min Heap and Max Heap
+ behaviors

  * insert - add to last and percolate up
  * remove
  * percolate up/down

+ Make a heap

  * heapify an array :math`\Theta(n)`
  * insert to an empty heap one by one :math:`\Theta(n \log n)`

+ Heap sort

  * heapify first
  * repeat

    - take the root
    - put into the sorted region
    - percolate down

+ Priority queue ADT

  * not really a queue

Backtracking and Exhaustive Algorithms
======================================
Both algorithms search in a tree problem space for solutions.

Exhaustive Algorithms
---------------------
+ Exhaustive searches all possible solutions
+ Always generate final solutions and check, never check partial solutions
+ Implementation

  * Recursive

+ Examples

  * All permutations
  * All combinations

Backtracking
------------
+ Backtracking searches tree problem spaces with pruning (reject partial
  solutions)
+ Similar/identical to DFS
+ Implementation

  * Recursive
  * iterative - stack

+ Applications

  * N queens - reject when attacking each other
  * Maze - reject when hitting the dead end
  * Sudoku - reject when violating the rule

+ Recursive implementation

Graph
=====
+ Nodes/Vertices and Edges/Arcs
+ Types: directed/undirected, weighed/unweighed, cyclic/acyclic,
  complete/dense/sparse, connected/unconnected
+ Terms: too many to list, check course note
+ Representations: adjacency list, adjacency matrix, pro and con
+ Traversal

  * Depth-first search (DFS)
  * Breadth-first search (BFS)

+ Shortest path problem

  * BFS for unweighted
  * Dijkstra's for weighed/unweighed

    - select minimal (priority queue or other)

Patterns
========
Must be able to reproduce in an exam environment.

+ Write class declarations of ADTs (Priority Queue), may ask templated
  version
+ Write simple recursive exhaustive/backtracking algorithm
+ Mimic a graph traversal given a graph as diagram, adjacency list or matrix
+ Write typical algorithms of BST (search, insert, traversal)
+ Write typical algorithms of Heap (insert, remove, heapify, percolate up/down,
  heap sort)
+ Write typical algorithms of Graph (BFS, DFS)
+ Understand how algorithm works (Dijkstra)