CSC301.01 2015F, Class 41: Wrapup
=================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Course goals.
* An inventory of learning outcomes.

Preliminaries
-------------

### Admin

* Update on grading
    * Everyone who has made reasonable effort will pass.
    * I will let you know your likely grade a week before I submit them.
      You can argue for higher or lower.
* We need a grader for CSC 301 next semester.  Is anyone interested?
* We also need more individual tutors for next semester.

### Upcoming Work

* Exam 2 due class time Friday.
* Final exam next Tuesday at 2pm, probably here.

### Extra Credit

* CS Extras Thursday - Summer Opportunities in CS.
* Kington Inside the Loop talk tomorrow 11am or 2pm in JRC 101.
* Composing class concert tonight, Sebring-Lewis
* Symphonic Band Sunday at 2 in Sebring-Lewis

### Questions

An inventory of learning outcomes
---------------------------------

### Habits of thought in dealing with algorithm design

* Find potential algorithms to solve a problem
* Work though examples
* Try to find a counter-example
* Try to prove it correct
* Analyze it
* Do it all over again ("can I do better")

### Approaches to Algorithm Design

* Use one of the main techniques
    * Greed
    * Divide and Conquer
    * Dynamic Programming
    * Turn the problem into a graph and solve a problem on that graph.
* Adapt algorithms you already know (know "the literature")
* Think about what structures might help, or what new structures you
  might design.
* Change the requirements
* Use randomness

### "The Literature" - Classic algorithms, ADTs, and Data Structures

Algorithms

* Dijkstra's algorithm for shortest path in directed graphs with non-negative
  edge weights.  Greedy algorithm, choosing the nearest node at each
  step.
* Floyd-Warshall.  All-pairs shortest path.  Has a distance matrix that
  we enhance by allowing paths to go through more and more nodes.
  Clever use of data structure.  Effectively a dynamic programming
  algorithm.
* Prim's Algorithm for MSTs.
* BFS and DFS.
* Sorting
    * Radix
    * Quicksort
    * Bucket sort
    * Merge sort (we knew already)
    * Clever approaches to merge sort
    * Heap sort
* Ford-Fulkerson Max Flow
* Kruskal's algorithm for MST's
* Pattern Matching algorithms
    * Using hash functions & The cool hash function
    * Knuth-Morris-Pratt
    * (less intelligent approaches)
* Minimum stamps
* Approximate string matching using dynamic programming
* Knapsack
* Kth-largest

Data Structures

* Self-balancing trees.
    * Red-Black
    * 2-3-4 trees
    * Generalized 2-3-4 trees (B-trees)
    * AVL trees (kinda)
* Tries
* Hash Tables and the design of hash functions
* Union-Find
* Heaps
* Implementations of Graphs
    * Adjacency matrix
    * Edge lists
    * Adjacency lists
* Linked lists (?)

Abstract Data Types

* Set
* Queue and Stack
* Dictionary
* Priority Queues
* Graphs

### Everything else

* The formal definition of Big-O 
* How to use the formal definition of Big-O to figure out implications
  of Big-O (e.g. if f(x) is in O(cg(x)), then f(x) is in O(g(x))).
* Laugh at what you do; sometimes even laugh at Dad jokes.
* P vs. NP
* Proof Techniques (or some practice)
    * Authority
    * Waving hands
    * Induction (normal, strong, structural)
    * Contradiction
* Summation formulae
* Master theorem for solving recurrence relations
* Other mechanisms for solving recurrence relations
    * Recursion trees
    * Working out recurrence relations "by hand"
* Other notations: Big Theta, Big Omega
* TSP
* Amortized analysis 
* Lower bounds for sorting (comparison-based is O(nlogn)
* n! is approximately 2^(nlogn) [although none of us remember]
* Sam sometimes screws up significantly.  Sympathize.

Course goals
------------