====== EPGY - Day 3 ======

===== Morning =====

**Question of the Day:** You have two eggs and a 100 story building! You are told to find the highest floor that you can safely drop the eggs from without them breaking. These eggs could be pretty strong, so it is possible that they will not break even after being dropped from the very highest floor. Come up with a strategy to minimize the number of times you need to drop the eggs to discover the desired floor. One strategy is to drop an egg from the first floor, second floor, third floor, and so on until that egg breaks. This could require up to 100 egg drops though! A better strategy would be to start by dropping an egg from the 51th floor. If that egg breaks, then switching to our old strategy will take at most 50 drops. If the egg doesn’t break, then we can keep working our way up the floors. This strategy guarantees at most 50 drops. How much better can you do?

  * House Keeping
    * Poll Results
      * "Your value is not determined by how hard or easy something is."
    * Google Group
    * Syllabus is updated!
  * Transition from Believability: [[epgy:ai13:turing_test_papers|Turing Test Papers]]
  * AI Communities/Culture
    * [[http://www.theblaze.com/stories/2012/10/16/robosquirrel-moroccan-pottery-the-top-5-most-ridiculous-govt-expenses-found-in-this-years-wastebook/|Haters gonna hate!]] 
  * Recursion
    * Factorial
    * Fibonacci - http://www.mathsisfun.com/numbers/fibonacci-sequence.html
    * http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm
      * http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html
      * http://www.doc.ic.ac.uk/project/2012/163/g1216331/example.html
    * Discussion: Imperative vs Declarative (Functional)
      * [[http://simple.wikipedia.org/wiki/Imperative_programming#Declarative_vs._Imperative_programming|Simple Wikipedia]]

Declarative: Logic
<code prolog> 
% Towers of Hanoi via Logic Progamming

peg(a;b;c).
disk(1..4).
init_on(1..4,a).
goal_on(1..4,c).
moves(15).

% Generate
1 { move(D,P,T) : disk(D) : peg(P) } 1 :- moves(M), T = 1..M.

% Define
move(D,T) :- move(D,_,T).
on(D,P,0) :- init_on(D,P).
on(D,P,T) :- move(D,P,T).
on(D,P,T+1) :- on(D,P,T), not move(D,T+1), not moves(T).
blocked(D-1,P,T+1) :- on(D,P,T), disk(D), not moves(T).
blocked(D-1,P,T) :- blocked(D,P,T), disk(D).

% Test
:- move(D,P,T), blocked(D-1,P,T).
:- move(D,T), on(D,P,T-1), blocked(D,P,T).
:- goal_on(D,P), not on(D,P,M), moves(M).
:- not 1 { on(D,P,T) : peg(P) } 1, disk(D), moves(M), T = 1..M.

#hide.
#show move/3. </code>

Declarative: Functional
<code lisp>
;;; -*- Mode: LISP; Syntax: Common-lisp;
;;; http://www.apl.jhu.edu/~hall/lisp/Hanoi.lisp
;;;=========================================================================
;;; Simple towers of Hanoi program. Note that Start-Peg and Goal-Peg are
;;; integers from 1 to 3 indicating the peg number. Ie to move 4 discs, 
;;; starting on the first peg and finishing on the last one, execute
;;; (Towers 4 1 3)
;;;
;;; 1992 Marty Hall. hall@aplcenmp.apl.jhu.edu

(defun Towers (Number-of-Discs Start-Peg Goal-Peg)
  (cond
    ((= 1 Number-of-Discs) (format t "~%Move Top Disc from peg ~D to peg ~D."
				   Start-Peg Goal-Peg))
    (t                     (Towers (1- Number-of-Discs)
				   Start-Peg
				   (Remaining-Peg Start-Peg Goal-Peg))
			   (Towers 1 Start-Peg Goal-Peg)
			   (Towers (1- Number-of-Discs)
				   (Remaining-Peg Start-Peg Goal-Peg)
				   Goal-Peg))))

;;;=========================================================================
;;; Given two peg numbers, what is the peg number of the third peg?

(defun Remaining-Peg (Peg1 Peg2)
  (- 6 Peg1 Peg2))
</code>

  * Reviewing Code: Style, Approaches, Concepts
    * [[Notes on Style]]
    * Pass by Value vs Pass by Reference (Primitives and Objects)
    * Briefly touch on Android (SDK, ADT, AVD)
    * Debugging
  * Data Structures: http://docs.oracle.com/javase/7/docs/technotes/guides/collections/overview.html
    * Array
      * http://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
      * http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
      * http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
    * List
      * http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
    * Stack - Good for "Undo"
      * http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
    * Queue - does not use "push" and "pop"
      * http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
    * Map: http://docs.oracle.com/javase/7/docs/api/java/util/Map.html
    * Set: http://docs.oracle.com/javase/7/docs/api/java/util/Set.html

{{:epgy:ai13:51.jpg|}}

  * Algorithms
    * Search
      * Divide and Conquer!
    * Sort
      * http://www.sorting-algorithms.com/
      * http://visualsort.appspot.com/

===== Afternoon =====

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

----

Disclaimer: Not everyone filled out the form. Also, this isn't a measure of anyone's merit, it's just to get a sense of where things are in the class. "Easy" and "Hard" are very relative terms. 

{{:epgy:ai13:screen_shot_2013-07-18_at_1.14.52_am.png?500|}}