# William Koch

Ranch Hand
since Sep 26, 2012
Cows and Likes
Cows
0
In last 30 days
0
Total given
0
Likes
3
0
Total given
0
Given in last 30 days
0
Scavenger Hunt
Ranch Hand Scavenger Hunt
Greenhorn Scavenger Hunt

## Recent posts by William Koch

So for my Algorithms Analysis and Design course, our instructor wants us to put together a visual presentation to review one of any of the topics we have covered in the course thus far. I personally want to put together a funny video but it also has to be educational. It needs to be primarily visual. Some people in the past have done parodies of past or done a dance of different sorting algorithms. I wonder if anyone has any good ideas for a humorous video/presentation I could put together for the following topics (maybe an everyday occurrence of algorithms we see everyday that many people do not even notice):

IT MUST BE PRIMARILY VISUAL IN NATURE AND I PREFER NOT TO DO POWERPOINT UNLESS YOU HAVE A REALLY GOOD IDEA FOR ONE.

Brute Force
Brute Force with Recursion (Subtopic of Brute Force)
Decrease and Conquer (Decrease by One or by Half)
Divide and Conquer
Transform and Conquer
Memoization or Dynamic Programming
Greedy Algorithms
Recurrence Relations/Recursion Tree Method/Amortization
Binary Search
Data Structures and Invariants (How invariants can improve Big-O for certain operations (i.e. AVL Trees)
Graph Algorithms (Dijkstra's or Prim's or Depth/Breadth first search)

Please offer some suggestions if you can.

Thanks,

Will
8 years ago
So for my Algorithms Analysis and Design course, our instructor wants us to put together a visual presentation to review one of any of the topics we have covered in the course thus far. I personally want to put together a funny video but it also has to be educational. I wonder if anyone has any good ideas for a humorous video I could put together for the following topics:
• Brute Force
• Brute Force with Recursion (Subtopic of Brute Force)
• Decrease and Conquer (Decrease by One or by Half)
• Divide and Conquer
• Transform and Conquer
• Memoization or Dynamic Programming
• Greedy Algorithms
• Recurrence Relations/Recursion Tree Method/Amortization
• Binary Search
• Data Structures and Invariants (How invariants can improve Big-O for certain operations (i.e. AVL Trees)
• Graph Algorithms (Dijkstra's or Prim's or Depth/Breadth first search)

• Please offer some suggestions if you can.

Thanks,

Will
8 years ago
correct but you also need to assume you know everyones estimated times for all three events. So how do you organize it so the entire event takes the least amount of time?
8 years ago
There is only enough room for one person in the pool at a time but during this race unlimited people can bike and run at the same time. We want the race to be completed as early as possible. The order is Swim, Bike, Run. You have records that let you calculate approximate times for each person for each event.

My greedy strategy would to have the slowest swimmer go in the pool first, followed by the next fastest, and so on so the fastest swimmer would go last. You also know their run and bike times though, so I am having trouble coming up with a counter example that proves this strategy won't work. Can anyone provide me with one. Your example can have any number of racers involved in it.
8 years ago
I am willing to pay for help, and pay is negotiable and can be done via PayPal.

Tutor must have a good background in coding in Java, everything from GUI's to Data Structures.
Also needs to know Design Patterns.
Needs to be able to spend a few hours a week online via webcam to help but will probably only do one hour per session.
Also would like a background in JUnit testing but not required.

I am use to using Eclipse for my IDE so someone who also is familiar with eclipse is preferable.

8 years ago
The assignment requires that we build a game that has four players that play on their own (very basic AI) where each one has their own strategy (strategy pattern) and uses the model view controller the game needs to have a basic GUI.
8 years ago
I have no idea where to start when creating a class diagram. I am just drawing it out on a piece if paper so I do not need any special software at the moment. How do you know what all your classes need to be and how do you know what methods and fields/attributes that they are going to have? One thing to keep in mind (I do not know if this will affect any answers). This game I am creating needs to implement the strategy pattern, and it also needs to use the model view controller. Thanks a bunch.
8 years ago
I have no idea where to start when creating a class diagram. I am just drawing it out on a piece if paper so I do not need any special software at the moment. How do you know what all your classes need to be and how do you know what methods and fields/attributes that they are going to have? One thing to keep in mind (I do not know if this will affect any answers). This game I am creating needs to implement the strategy pattern, and it also needs to use the model view controller. Thanks a bunch.
8 years ago
here are some test cases greg

HELLO
HELLO
0
DOG
DOGS
1
COMUTER
COMPUER
2
CAT
DOG
6
CAT
BAT
2
TUDAY
THRDAY
3
MARKET
8
CALIFORNIA
NEWYORK
13
CONSTITUTION
DECLARATIONOF
15
8 years ago
Oh my goodness that was not suppose to go in this forum. It is pseudo code. Please move it to a more appropriate forum for me.
8 years ago
How can I change this algorithm so the distance only takes into account insertions.
For example: If I have the words CAT and BAT you would need to insert a B in CAT and a C in BAT for the words to be equal so the distance would be 2. The actual algorithm below returns 1 because it allows you to substitute(it also allows for removal). Is there anyway to change the algorithm below to ONLY do insertion? And can anyone provide insight on it?

int LevenshteinDistance(string s, string t)
{
int len_s = length(s), len_t = length(t)

if(len_s == 0) then return len_t
if(len_t == 0) then return len_s
if(s[len_s-1] == t[len_t-1]) then cost = 0
else cost = 1
return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,
LevenshteinDistance(s, t[0..len_t-1]) + 1,
LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)
}
8 years ago
my point exactly. There is a way to do this where you can use recursion and I started it at the beginning of the thread but it is incomplete does anyone know how to complete this and take into account duplicates, triplets, etc? If my initial part is incorrect please let me know.
8 years ago
Jayesh that will not work. For example if there is a string of length 5 then there are 3^5 ways to arrange those 3 characters (you can resuse them) so 3^5=243 , now we need to look through those 243 and find out which ones have the string ABC in it, count those and subtract that count from 243 to get our answer in this case the correct answer would be 216 ( there are 27 strings where ABC appears). Your approach does not hold for all cases.
8 years ago
Using only letters A B & C, how many different messages of length N can you type? with the constraint that ABC cannot appear anywhere in the string. For example, typing BACBBC would be fine, but typing BCABCB would not. With this constraint, how many different messages of length N can you type? Does anyone know how to solve it using recursion?

N is the length so my solution so far say if it starts with an B or C then there are f(N-1) ways the rest of the string could be arranged. If it starts with an A then there are 4*f(N-3) ways we can arrange it. Therefore:

f(N) = f(N-1) + f(N-1) + 4*f(N-3).... this is incomplete can anyone point me in the right direction?
8 years ago
Limited to only passing in one parameter into the main function. There was no rule saying we could not use a helper function.
8 years ago