====== EPGY - Day 4 ======
===== Morning =====
Question of the day: I am given 1000 random integers between 0 and 100. What is the least number of steps it will take you to sort the list of numbers?

House Keeping
  * Procedural Literacy
    * http://www.bogost.com/writing/process_intensity_and_social_e.shtml
  * Puzzle Solution: http://www.datagenetics.com/blog/july22012/
  * Final Projects: http://eldar.mathstat.uoguelph.ca/dashlock/CIG2013/competitions.html
  * Blogs!

Review
  * Comparing 2 languages: (Processing and Java)
  * http://jtf.acm.org/demos/acm.graphics/index.html
  * Hash Tables: [[http://www.sparknotes.com/cs/searching/hashtables/terms.html|terminology]]
    * int hashed by mod
    * name hashed by sum of letters
    * complex class hashed by big complex equation
  * http://www.csanimated.com/browse.php

{{:epgy:ai13:240px-hash_table_4_1_1_0_0_1_0_ll.svg.png|}}

Big O
  * Sorting: 
    * http://www.sorting-algorithms.com/
    * http://visualsort.appspot.com/


  * Merge Sort - recursion!
    * [[http://en.literateprograms.org/Merge_sort_(Lisp)|Lisp Merge]]

Lisp 
  * [[https://simple.wikipedia.org/wiki/Lisp_(programming_language)|Simple Wikipedia]]
  * [[https://en.wikipedia.org/wiki/Lisp_(programming_language)|Normal Wikipedia]]
  * http://classes.soe.ucsc.edu/cmps148/Spring07/micro-talespin.lsp
  * http://www.dynamiclearningcenter.com/samples/

More recursion
  * http://www.cs.man.ac.uk/~pjj/cs2121/fix.html
  * [[http://www.gnu.org/software/emacs/manual/html_node/elisp/Arithmetic-Operations.html|Lisp Arithmetic]] 

<code lisp>(defun merge-sort (list)
  (if (small list) list
    (merge-lists
		(merge-sort (left-half list))
		(merge-sort (right-half list)))))

(defun right-half (list)
  (last list (ceiling (/ (length list) 2))))
(defun left-half (list)
  (ldiff list (right-half list)))
  
(defun small (list)
  (or (null list) (null (cdr list))))
  
(defun merge-lists (list1 list2)
  (merge 'list list1 list2 #'<))
  
(print (merge-sort '(2 4 1 2 4 2 3 1)))</code>

Deeper into Datastructs:
  * Binary Trees
    * BST
    * Red Black Trees
  * Non-Binary Trees
    * 2-3 (B) Trees 
    * kD Tree
  * Heap
    * Heap Sort
    * Binomial Heap
    * Fibonacci Heap
  * Graph Theory

{{:epgy:ai13:qogay.png?600|}}


NP-Complete Problems
  * http://en.wikipedia.org/wiki/Travelling_salesman_problem

Big O
  * O(polynomial degree k) = O(n^k)
  * O(1) - constant time
    * query i-th element in array
    * query hashmap
  * O(log n)
    * binary search
  * O(n) - linear time
    * remove element from array
    * find element in linked list
  * O(nlogn) - 
    * quicksort
  * O(n^2) - quadratic time
    * find closest pair of points
  * O(2^n) - exponential time
    * consider all subsets
  * Sorting algos, find their Big O (Best, Worst, Average)
    * insertion - B O(n), W O(n^2), A O(n^2)
    * qsort - B O(nlogn), W - O(n^2), A O(nlogn)
    * bogo - B O(n), W = O(inf), A O(n! * n)
  * Big O for recursive algos
    * fib O(2^n)
    * memorization -> O(n)

{{:epgy:ai13:800px-p_np_np-complete_np-hard.svg.png?600|}}


===== Afternoon =====

  * [[Journal 4]]
  * [[Assignment 4]]
  * [[https://docs.google.com/forms/d/1-6WMYV3I5FO9hISXbFHjsYlol_F0JBSjQuHYjZGm0bw/viewform|Feedback]]