I will meet with 10 people on Monday and 10 on Tuesday. We will suggest groups by Wednesday, which will give you more than a week to complete your projects.

Check out a solution for the EPGYDraw program via example code. At the very minimum, have a shape that can be drawn by mouse clicking. Document your work with animation and graphics in a blog post (if you haven't already).

(Deliverable) Blog post! and have the zipped project folder in your Google Drive under Day 3.

You will need to import the acm library and jar file. You must start your program as an extension of GraphicsProgram to make use of the package methods. If you don't want to learn how to do that just use this as your starter code:

http://www.stanford.edu/~bholtz/AIClass/ExampleCode/ACMGraphics.zip

Create a new project called MyVisualSort. Take your favorite sort, and create a visual representation of random 20 elements being sorted. Have a RESET and a START button to give the user control of the program. If you found this to be easy, then do it for all the sorts you know.

It should look like these in some simpler form (it doesn't matter which way the bars face):

• http://www.sorting-algorithms.com/
• http://visualsort.appspot.com/

(Deliverable) Take a screen shot of your program in action. Write one sentence about it. Save the code in Pastebin, if you want to. Finally, upload your project folder (zipped) into your Google Drive.

(Deliverable) New Blog Post!

This blog post will be titled: Final Project Proposal: #TITLE OF YOUR PROJECT HERE#

You can take two directions with what you decide to write about.

1. You can briefly look through and find a new project that you like better
2. You can take one that you've already researched and find a more specific application of it (continuing from where you left off)

Your proposal must answer these questions:

1. What is the specific area you are working within?
2. What is it that you would like to learn about it?
3. Why is this interesting to you?
4. Why should other people care?
5. What are the practical applications of this topic?
6. What is the closest example (researched from the web) of what you want to build or investigate?
7. What do I want to accomplish? (For example…)
   1. Building a demo/prototype/interactive experience?
   2. Collecting a set of foundational psuedocode/approaches?
   3. Creating a way to teach or explain it to others?
   4. Pooling together a set of current cutting edge research in this area?
   5. Any or all of the above?
   6. etc.
8. My order set of steps I plan to take to accomplish it?
9. Foreseeable obstacles?
10. What tools am I using?
11. How much money do I need?… just kidding!

(This doesn't have to be long, unless you want it to be)

You are in a forest and the path forks in front of you. Down one path, you notice that the trees are oddly symmetrical. In fact, the trees look like they are composed of smaller versions of itself. You realize that this path takes you down a spirally road of more recursion than you could ever imagine. Go to the last section of this assignment, if you love recursion.

Down the other path is a dark and dim trail. You notice it is a but glitchy and determine that this must be Java and the Google Glass that you are wearing won't support it.

Continue down the path.

The road splits once again and you are forced to choose your fate, knowing that you may not get a chance to backtrack on this adventure. Down one path is ridden with red squiggles as a thick forest of .java files do not seem to be cooperating. If you are willing to do some conflict resolution in Eclipse click here.

You notice that the first path was ridden with perilous bottomless pits and decided to go down the latter. The glitches intensify and you lose a bit of your momentum, as if gravity, itself, was shifting. As you glide down this path you soon encounter, the gate keeper, SVN, A giant tortoise that prevents you from getting to your source.

The increased momentum and lack of friction pull you in and, short of going back in time, you click here.

As you drift into another realm of consciousness YOU REMEMBER THAT THE INSTRUCTOR HAS NOT HAD A CHANCE TO FIGURE OUT THE SET UP AND INSTALLATION FOR THESE CONTESTS… I mean, quests. And won't get a chance until the weekend.

You wake up from a dream and you realized that you still need to fill out your Feedback form for the day.

More Recursion than You Have EVER Imagined!!!

Part 1: Recursion

Download the starter project: Lab03-Starter

(deliverable) Pick at least 2 of the following 7 problems to do, depending on how familiar you are with recursion. Challenge yourself!

1. Phone Mnemonics (Easy)

On standard TouchTone telephone keypads, each digit besides 1 and 0 is mapped to a set of letters. This allows businesses and other groups to have phone numbers with catchy names like 1-800-PICK-UPS or 1-888-BEST-BUY or 1-888-3M-HELPS. See here for more examples. The mappings are as follows: 2 (ABC), 3 (DEF), 4 (GHI), 5 (JKL), 6 (MNO), 7 (PQRS), 8 (TUV) 9 (WXYZ).

Create a function that, given a number inputted as a string, will generate all possible letter combinations formed by that number. This recursive pattern is commonly called recursive enumeration, or generating combinations, and can be applied to a wide variety of problems.

Your declaration should look like

public void mnemonicPlease(String str)

You may choose to use the method String.charAt(int position) to get the character at a position.

2. Subset Sums (Easy)

Instead of just generating subsets, your goal is to determine whether we can have a subset of the numbers sum up to a desired target value. Make sure it works efficiently (i.e, don’t double generate sets).

Your declaration should look like

 public boolean canSumTo(Set<Integer> nums, int target) 

3. A puzzle (Medium)

Suppose you have a puzzle as follows. You have a row of integers drawn inside squares with large chalk on the sidewalk. The last integer is always a ’0′, but the other integers can be anything. You start by standing at the integer farthest away from the 0. At each move, you may only move the number of squares indicated by the number you are standing on, in either direction. You may not move past the end of the row of squares. You win if you reach the 0. For example, if we have the numbers [3, 6, 4, 1, 3, 4, 2, 5, 3, 0], you would start on the first 3, and you can reach the 0 by taking the steps right3, left1, right4, right2, left3, right4. Notice that a puzzle may not necessarily have solutions. Write a method that will determine whether a puzzle of this sort is solvable.

 public boolean isSolvable(int[] row) 

4. Scrabble Scoring (Medium)

If you haven’t played Scrabble, it’s a game where you have tiles with letters, and you try to arrange them into words to score points. Each letter is worth points, with trickier letters like ‘z’ and ‘j’ and ‘q’ worth more. So, given a set of letters represented by a String, find the highest scoring word that you can make with those letters.

String highestScoringWord(String letters) We provide 3 text files of words. FullLexicon.txt contains 354984 English words. InterestingWords.txt contains words that are 5 letters or longer. ShorterLexicon.txt is just a set of 73 arbitrarily chosen words to allow you to test with fewer words. Read in one of these files and store it efficiently as an instance variable.

The method

int scoreCharacter(char c)

is also provided, and will return the score associated with a character.

Keep in mind that because there are so many words in the larger lexicons, having an efficient data structure to store the words and having an efficient algorithm is crucial.

5. Anagrams (Medium)

An anagram is a rearrangement of the letters in a word of phrase to make another word or phrase. For example, “Computer Science” can anagram to “Concept Mice User,” which the early designers of the computer mouse would certainly approve of. The Internet Anagram Server has a great list of anagrams to whet your appetite.

So, given a letters in a String, write an algorithm that will find any anagram that can be made from those letters. If an anagram is found, return the anagram as a List of Strings that correspond to the words in the anagram. If no anagram is found, return null. Do not return the original string that was entered. Your method will be as follows:

List<String> findAnagram(String word)

See #4 for a description of the lexicons (word lists) you can use.

You may extend the program to find all anagrams and return a Set<List<String» instead of just a single anagram.

6. Stock Cutting (Challenge)

You’re off to the hardware store to buy some wood for building a chicken coop in your backyard. You draw up the design, and then make yourself a list of the length of each piece of lumber needed. However, the closest hardware store unfortunately only has lumber of one length. You know you can just but some the wood, and just cut it later, but you want to buy the minimum pieces of lumber possible (treated wood is expensive!). As a freshly minted recursion expert, you decide to write a recursive algorithm to figure this out. Your method declaration will be as follows:

int cutStock(List<Integer> requests, int stockLength)

For example, given {4,3,4,1,7,8}, and a stock length of 10, you can purchase three pieces of lumber, and cut one of them in to lengths {4,4,1}, another into {3,7}, and another into {8}.

7. Koch Snowflake (Not too recursively challenging, but can be mathematically, and graphically challenging)

The Koch Snowflake is a recursive fractal curve that is defined as follows:

Start with an equilateral triangle. At each step, take each straight line segment, and divide it into three equal segments. Remove the center segment and construct an outward-facing equilateral triangle with the removed center segment. Repeat.

Make a graphical program that will draw a Koch Snowflake.

Notice that the number of line segment grows exponentially, so make sure to start testing with low numbers of iterations (3 is good). A possible extension is adding buttons to increase or decrease the number of iterations to calculate. Another possible extension allows you to generalize the Koch curve, by consider what happens if you do not use an equilateral triangle. Depending on how you do this, trigonometric functions may be required. All of Java’s math functions are in the Math class. For example Math.sin(Math.PI/6).