PrimeEx A program with various approaches to determine if an int is prime or not. Used to demonstrate Java syntax. You need the Stopwatch class, a non standard Java class, as well.
2D array Example. A simplified version of filtering a picture represented by ints.
2D array example. Very simple version of the Conway's Game of Life.
Program to create ASCII frequency table from file and url. Demonstration of try / catch blocks. The CIA 2008 Factbook may be downloaded from Project Gutenberg.
IntListVer1 First version of the IntList class developed in class. Developing class to illustrate various class design and implementation issues in Java.
IntListVer2 Added default add method, equals method, and toString methods. Includes versions of toString using String concatenation and StringBuffer to illustarte performance differences.
IntListVer3. Added insert and remove methods.
SortedIntList. Inherits from InListVer3 to create a SortedIntList. Class is 'broken' because random insertions still allowed.
GenericList. Altered the list to store anything, not just ints.
Die class. A class that models a playing die.
DemoClass: This illustrates some of the more confusing concepts in class syntax and mechanics such as constructors, static vs. instance methods, and method overloading.
Stopwatch class. A class for measuring how long it takes for a program to run.
Create a Set. A method that using polymorphism to create a set from an array.
Recursion examples. Includes examples on finding space taken up by files in a directory including all files in all subdirectories, recursive factorial, recursive power, recursive Fibonacci numbers, and a simple knapsack problem.
Eight Queens example. Code to find a a solution to an N queens problem. Note the queensAreSafe method has not been completed.
Airlines example. Determine if airlines can be moved from airline to another based on network of airline partners. Here is a sample input file.
Minesweeper. Another example of recursion from the game minesweeper.
GenericListVersion2. Changed the GenericList class so that it implements the Iterable interface in order to demonstrate how to implement an iterator using an inner class.
GenericListVersion3. Changed GenericList so it is generic based on Java generics syntax instead of relying on Object.
ListNode. A singly linked node class used to build linked lists
IList. A simple list interface
LinkedList. Similar to the LinkedList developed in class. Does not contain all the methods you would expect of a LinkedList. Also implements the iterator remove method in O(N) time. An O(1) time remove method is possible.
UnsortedHashSet - An unsorted set that uses a hashtable with closed address hashing to store values. Currently only the add method is implemented.
UnsortedSetTest - A method to compare Java's TreeSet and HashSet to the BianrySearchTree, UnsortedSet, and UnsortedHashSet classes developed in class. Note you need a lot of other files for this to work.
SimpleWordCount - Program demonstrating use of a map to count the frequency of words in a file.
WordCount - Program that compares counting words in files using an ArrayList and a Map.
There are many ways to complete a task---even a seemingly simple one like eating cereal.
When programming a computer to complete a task or solve a problem, repetitive techniqueslike iteration and recursion are extremely useful. In this video, we will look at theseproblem-solving techniques.
This video is part of the Problem Solving video series. Problem-solving skills, in combinationwith an understanding of the natural and human-made world, are critical to the design and optimizationof systems and processes.
Hi, my name is Niaja Farve. I am a doctoral student in Electrical Engineering and ComputerScience at MIT.
Before watching this video, you should be familiar with introductory programming andsimple data structures.
After watching this video, you will be able to: Divide a programming problem into simpler,analogous pieces. And, solve the problem by combining solutions to the simpler pieces.
In computer science, we often want to solve complex problems. However, computers dealbest with performing easy tasks over and over again. We utilize the computer's ability byimplementing repetitive techniques to incrementally solve our complex problems.
Though eating a bowl of cereal is a fairly simple task that most of us can complete automatically,we need to think carefully about how to program a computer to do the same. Let's take a closerlook at the problem and identify the fundamental steps used to frame cereal eating for repetitivecomputation.
In this example, let's suppose the computer understands the basic operation of eatinga single bite of cereal, but does not understand how to eat an entire bowl of cereal. So howdo we 'teach' the computer to eat a bowl of any size greater than one bite? Pause thevideo here and think about it.
The first step when approaching a complex programming problem is to break the problemup into analogous, but simpler pieces that we can tell the computer how to directly solve.
So what is a simpler version of eating a whole bowl of cereal?
One possibility is eating a smaller amount of cereal.
We already mentioned that a small, non-zero amount of cereal the computer can handle eatingis a single bite.
Going one step up, eating two bites-worth of cereal is equivalent to eating a singlebite twice. The next step when approaching a complex problem is to deduce a pattern.
That is, how does a generally larger problem look in comparison to the simpler version?
Here, we notice that eating any amount of cereal is equivalent to the sum of eatingmultiple bites-worth of cereal.
Now that we've broken up our problem and understand how the pieces will fit back together, wecan put our solution into a generalized code framework:Start with telling the computer the procedure for solving the simplest problem. Then, repeatthis procedure on subsequent pieces until the desired endpoint is reached:If the bowl contains cereal, take one bite of cereal. Repeat until there is no more cereal.
You may recognize this type of solution as an iterative approach.
Or we could also take the following alternative approach:Start with telling the computer how to solve the simplest problem. Then, break the probleminto simpler and simpler pieces until we reach the version we've already told the computerhow to solve. Does the bowl contain 1 bite of cereal? Ifso, take the bite. If not, divide it up into a bowl containing one bite and a bowl containingthe remainder. Repeat this procedure on the resulting bowls.
In this case, we end, up with a series of bowls containing one bite, which the computerknows how to eat.
Breaking up a problem into progressively simpler, but analogous pieces in this way is knownas a recursive approach. Because the solution to the most complex problem depends on solutionsto the simpler pieces, recursion creates a queue of jobs waiting to be completed.
In contrast, when using iteration, there is no such dependency from one instance of theproblem to the next.
So even though the computer ends up consuming n bites of cereal in both cases, the iterativeand recursive approaches arrive at this answer in very different ways.
There are many different ways to successfully eat a bowl of cereal or solve any given programmingproblem. The key is to 1. Break the problem into analogous pieces that the computer cansolve, and 2. Combine the solutions to the pieces into a solution for the more complexproblem.
In our previous cereal-eating example, breaking down the problem into simpler pieces was fairlystraightforward. Now, let's look at a slightly more complex problem.
We would like to write a function, downup, that takes an input string and prints outprogressively smaller and larger sub-strings of the word as so.
To help us work with strings, we have a helper function, substring, which extracts a portionof a string, beginning from the first character up though a specified end index.
Following the framework we discussed earlier, what is a simpler version of downup that wecan easily handle?
How about downup of a single letter string. The desired output is achieved by simply printingthe string.
Moving one step up, we see that the desired output of a two-letter string can be accomplishedby printing the string, printing the string shortened by one letter, and printing thefull string a second time.
And moving up one more step to a 3 letter string...
Are you starting to notice any patterns? Pause the video to think of a possibility.
Though there are many different patterns, here is one you may have come up with: Withevery string, we are sandwiching the _solution_ to a string one character shorter betweentwo printings of the full string. With this mindset, we are poised for a recursive solutionto this problem.
Recall the general framework for a recursive solution: Tell the computer how to solve thesimplest problem. Then break the problem into simpler pieces until we reach the simplestproblem: If the string is a single letter, print it. Otherwise, print the string, solvefor downup of the string one character shorter, and print the string again.
Try now, if you haven't already done so, to frame the problem in a more iterative manner.
Pause the video to discuss.
We can notice that we are repeatedly printing substrings of the full string, with each stepmoving the end index from the original length down to 1. This is followed by again printingsubstrings, but this time increasing the end index back up to the original length.
We can program this solution using two iterative loops. Recall the general iterative code framework:Tell the computer the procedure for the simplest problem. Repeat the procedure on subsequentpieces until the endpoint is reached.
In our first loop, we print the substring, decrease the index by one, and repeat theprocedure until the index reaches one.
In the second loop, we move in the opposite direction. Print the substring. Increase theindex by one and repeat the procedure until the index is greater than the original length.
Both approaches, while very different, are completely valid! There is no one correctway to solve a problem. Some solutions may even have both recursive and iterative elements.
Now lets solve a third problem with an even more complex pattern.
In the famous Towers of Hanoi problem, the goal is to transfer a stack of rings frompillar A to pillar C. We can only move a single ring at a time, and can use pillar B as 'extra'workspace. We cannot place a larger ring on top of a smaller ring.
Lets follow the framework and start by working out the simplest problem: transferring 1 ring.
Here we can simply move the ring from A to C.
Okay, now let's try to transfer a stack of two rings. First we move the ring 1 to B,then ring 2 to C, then move ring 1 from B to C.
Now, let's try something a bit harder. Let's try to transfer a stack of three rings. Ring1 moves to C, ring 2 goes to B, and ring 1 goes to B. Now ring 3, which was on the bottom,is free to move to C. Then, ring 1 goes to A, ring 2 goes to C, then ring 1 finally goesto C.
Notice that after we moved the bottom ring to C, we essentially arrived at the same conformationas when trying to transfer 2 rings: We have two stacked rings and an extra empty pillar.
And because the largest ring is in the desired, final position and does not impede the movementsof any of the remaining smaller rings, we can treat the pillar as being empty.
This observation is crucial to the recursive implementation of the towers of Hanoi solution.
We transferred n-1 rings to the extra pillar, moved the largest ring to the final position,then transferred the n-1 rings to the final position.
Can you frame a pseudocode solution to the problem? Pause the video here to work outa possible solution.
Recall again the general recursive framework: Tell the computer how to solve the simplestproblem: If we're transferring a single ring, move it to the destination pillar.
Then, break the problem up into progressively simpler pieces:Transfer n-1 rings from the source to the extra pillar, transfer ring n from the sourceto the destination, and transfer n-1 rings from the extra pillar to the destination.
Note that the source, destination, and extra pillar designations change with each functioncall!
It's always a good idea to check your code with a test case. Pause the video here andcheck your code for the case of N equals 4. You may also wish to check our code and comparethe two solution methods.
Now lets check our code and traverse through the solution for transferring 4 rings.
We're not transferring a single ring, so lets transfer 3 rings from A to B.
We're still not transferring one ring, so lets transfer 2 rings from A to C.
We're still not transferring one ring, so lets transfer 1 ring from A to B. And we canfinally move this single ring!
Now we return to the previous call, and can move ring 2 from A to C. Then we transferour n-1 stack from B to C. This results in transferring 2 rings from A to C!
Returning one more step back, we move ring 3 to B. Now we transfer 2 rings from C toA.
Finally, we've returned back to our original function call, and we've completed transferring3 rings from A to B. So, we can move our largest ring number 4 from A to C.
Now we need a whole other set of recursive function calls to transfer the 3 ring stackfrom B to C! Pause the video now to finish checking the second half of our solution.
Notice how quickly the number of function calls grew! Good thing we have a computerthat is very good at following repetitive instructions!
To Review In this video, we showed you how recursion and iteration take advantage ofa computer's ability to repeat simple tasks.
To approach a complicated programming problem, first solve some simpler versions and tryto identify a pattern. Then, depending on the type of pattern you found, fill in a recursiveor iterative code framework. And remember, iterative, recursive and even mixed solutionsto a single problem may all be correct!
