Here's my approach: http://pastebin.com/FrgZztGK
If you can get that far, that's the bare minimum before moving on. Get it to work, take a screenshot and write your blog post about the program (with a screenshot of it running).
Here's my MyVisualSort with the buttons:
https://dl.dropboxusercontent.com/u/3235343/Teaching/EPGY/MyVisualSort.zip
Now, do a reply-to-all to my Question of the Day email.
Go to this website: http://www.compileonline.com/execute_lisp_online.php
If you figure this out before everyone else, HELP THEM!
Here is an example function:
(defun triple (X) "Compute three times X." (* 3 X)) (print (triple 4)) ; Display that function with 4 as a param
Here is a Fibonacci function that returns the Nth number of the sequence:
(defun fibonacci (N) "Compute the N'th Fibonacci number." (if (or (zerop N) (= N 1)) 1 (+ (fibonacci (- N 1)) (fibonacci (- N 2))))) (print (fibonacci 6))
(Deliverable) This is what I want you to do on the compile site (linked below):
http://www.compileonline.com/execute_lisp_online.php
For this project will you HIGHLY encouraged to work in pairs.
The summer has gone by quicker than you could realize and, at home, you begin to go through and organize the possessions from your travels. As you unpack, you realize that something very important is missing– your lucky underwear! (or teddy bear… or spoon). You email Stanford, and they swear that they do not have it. Conclusively, one of your classmates might have accidentally taken it.
You have the choice of 3 starting points:
(If it were me, I'd probably do Option 2. Maybe Option 1, if I wasn't feeling lazy. Option 3, only if I really want to spend time on the details of OOP and Graph Theory… Otherwise, I'd just try getting something that looks like the following below as soon as I could). If you get Option 2 working, then give Option 3 a try for practice. Animations are cool, but optional!
(Deliverable) Take your program. Make a screen shot and write a blog post describing the algorithm you used to determine the shortest path.
On paper, solve these problems. Save the answers for tomorrow's lab.
“Closed Form Expression” is like what we did in class (not the same as the problem above):
T(n) = 2 T(n/2) + n = 2 [2 T(n/4) + n/2] + n = 4 T(n/4) + 2n = 4 [2 T(n/8) + n/4] + 2n = 8 T(n/8) + 3n ... = 2k T(n/2k) + k n
Given: n/2k = 1 OR n = 2k OR log2 n = k = 2k T(n/2k) + k n = 2log2 n T(1) + (log2n) n = n + n log2 n [remember that T(1) = 1] = O(n log n)
Getting the O(f(n)) is Part (a). Now do another induction proof for Part (b).