User Tools

Site Tools


epgy:ai13:assignment_5

Assignment 5

Lab 1: MyVisualSort

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.


Lab 2: Lisp

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):

  • Write a function for addition, subtraction, and multiplication of two numbers
  • Write a function for factorial to return the factorial of one number
  • Your submission:
    • You may put the code in Pastebin for reference
    • Post the code on your blog with a quick shout out to Imperative, Declarative, and Functional programming. Try your best to define what each means. The post can be really short. Then, write another sentence about Lisp, where it came from, and it's relation to AI.

http://www.compileonline.com/execute_lisp_online.php


Lab 3: EPGYTraveler

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.

  • Go to the class syllabus page and look at everyone's latest entry. They will have listed some information about their hometown
  • Your job is to write a program that will:
    1. Load in an image file of the map of the world (scaled and cropped appropriately)
    2. Somehow store the 20 approximate points of where all students live relative to the map you chose to upload (Don't mess with FileIO or User Input unless you have time at the end)
      1. Point Class?
      2. 2-Dimensional Array?
      3. 2 Arrays? (one for x[20] and one for y[20])
    3. Have your program draw a GOval over each of the the 20 locations
    4. Now, create a Weighted Adjacency Matrix for the locations:
      1. an Adjacency Matrix is a float based matrix of size NxN (rowsXcolumns)
      2. N is the number of locations in the graph– the nodes
      3. Stored in the matrix is the distance from each node to every other node– the weight
        1. Since we are doing physical distances this Matrix should be SYMETRICAL
    5. Finally, there are many things you can do next, but I want to see the shortest amount of distance you'd need to fly (assuming you have your own magic hover craft AND the world is FLAT) to check with each of your EPGY classmates
    6. Have the program draw the finished path by putting edges between the nodes from the path that you will be taking and printing the final amount of travel by adding the weights stored in your Adjacency Matrix somewhere on the canvas of the path that was taken

You have the choice of 3 starting points:

  1. Start your own project and link to the acmgraphics jar
  2. Here's a pathfinding starterkit for those who are REALLY comfortable with Object Oriented Programming

(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.


Lab 4: Algorithms

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).

/soe/sherol/.html/teaching/data/pages/epgy/ai13/assignment_5.txt · Last modified: 2013/07/22 12:12 by ffpaladin