H/w 5 and final: Note: When you try to run MATLAB from the machines in Upson Lab, it will prompt you for a username and password. Use the following: Name: Engineer Password: Spr00Eng These machines have the default MATLAB work directory: C:\Program Files\MATLABR11\work If you put the .m files that you create into that directory, MATLAB will be able to find them. That is also where it will save things by default. 1. A stack is a data structure which allows data to be inserted and removed from one end of the structure only. The stack is known as a "Last In First Out" (LIFO) structure. Create a MyStack class which stores strings in the structure and implements the following interface: public interface Stack { // ------------- instance methods ----------------------------- public void push(String item); // insert an item at the top of the stack public String pop(); // remove and return an item at the top of the stack public String peek(); // return an item at the top of the stack without removal public int capacity(); // return the maximum number of items the stack can hold public int numberOfItems(); // return the number of items currently in the stack public boolean isEmpty(); // obvious!! public String [] showStack(); // outputs the whole stack as an array of Strings without // actually changing the stack } Using a one dimensional array (or otherwise) and a 'stack top' index (or other way of 'knowing' where the top of the stack is) as two of the 'appropriate data fields', implement this interface and write a GUI program to allow a user to enter strings and manipulate the stack whilst showing a continually updated image of the stack. Demonstrate that your program works by providing a mechanism whereby the user can enter a sentence, and which outputs that sentence in reverse word order by pushing each word onto the stack and then popping them off one by one. I recommend that 2. Update and refine your GUI graphing program so that it runs as an applet from an HTML page. 3. Write a simple program which has methods to (i) read in words from a (large) file, (ii) sorts these words alphabetically (in a case-insensitive way) (iii) finds any user-specified word (or returns that the word was not in the file). Ensure that your program is very well organised. 4. Easy 3-D graphics MATLAB question. Persuade MATLAB to draw 3-D graphs of the following functions for -3 <= x <= 3, and -3 <= y <= 3. Each graph should have a title saying which function it shows. Save each plot as a separate encapsulated postscript file. (These files are all you need to hand in for this problem). Call these files prob1a.eps, prob1b.eps, prob1c.eps, and prob1d.eps. HINT: remember that when you want to perform the operations *, /, and ^ on two arrays of numbers, you should use .*, ./, and .^ to get MATLAB to apply the operation entry by entry. This is not needed for + and -. z = x^2 - y^2 z = 3*(x-x^3)/(0.25 - y^2) z = x^2 * y / (x^4 + y^2) z = y * exp((-1/2)*(x^2 + y^2)) 5. Another MATLAB question. You can start working on this problem interactively at first, but the final 'solution' must be MATLAB source files that can be called from inside MATLAB. In what follows, let the range of x be given by -10<=x<=10. 5a. First, to get a feel for what's going on, persuade MATLAB to draw the graph of y=cos(x) (use plot to do this). Then get it to draw y=cos(p*x) for a few different positive integer values of p. Repeat this for y=q*cos(p*x), where q=various real numbers between -2 and 2. Now you're warmed up, the first part of the exercise is to create a .m file called "prob2cos.m" that gets MATLAB to draw the graphs of y=S(n,x) for different values of n, where S(n,x) = cos(x) + (1/3)cos(3x) + (1/5)cos(5x) + ... + (1/n)cos(nx). It should make graphs for each n=1,3,5,7,.. 21 (thus drawing 11 pictures -- notice that this example uses only odd numbers). MATLAB should pause between drawing each graph. You can write a function called S(n,x) if you like, but it is not needed to do this problem. It's the succession of (cumulative) graphs that we want t0 see. (Watch out for the slightly different syntax used in MATLAB for "for loops" compared with Java). Next, do the same thing for a different y=S(n,x), where S(n,x) = sin(x) + (1/2)sin(2x) + (1/3)sin(3x) + ... + (1/n)sin(nx). Your .m file should be called "prob2sin.m" and should make graphs for each n=1,2,3... 21, pausing between each graph (thus drawing 21 pictures, since it uses both odd and even numbers). 5b. This refines the MATLAB question 5a. You will hand in a MATLAB source file called fourierApprox.m that defines a function called fourierApprox. What this function will do is take in the name of a function as an input parameter (given in single quotes), and draw successive partial sum approximations to that function. There are three .m files available on the course webpage that provide functions you can use to help do this problem. These are a.m, b.m, and proj.m. The files a.m and b.m define functions that you can use to get the coefficients you will need below. (After downloading the files, type "help a" and "help b" from the Matlab prompt to get help with these functions. If you're curious about the math, take a look at these files to see what they do!). The file proj.m is used by the files a.m and b.m. In what follows, (a1) and (b1), (a2) and (b2), etc., are constants whose values your program will find by calling the functions 'a' and 'b' provided on the website, and again we let the range of x be given by -10<=x<=10. Your function fourierApprox(funcname) should draw the graphs of y=S(n,x,funcname) for each n = 1,2,..21, where S(n,x,funcname) = (1/2)(a0) + (a1)cos(x) + (b1)sin(x) + (a2)cos(2x) + (b2)sin(2x) + .. + (an)cos(nx) + (bn)sin(nx) where (ak) = a(k,funcname), (bk) = b(k,funcname) for k=1..n. Once you have written fourierApprox (and saved it in your MATLAB working directory), try it out on some actual functions! For example, if you type fourierApprox('abs') from the MATLAB prompt, it will show you approximations to y=abs(x) (the approximations will be accurate for -pi<=x<=pi, though not for larger or smaller x). Similarly, try fourierApprox('exp'), which will approximate e^x. Save the resulting figures (for n=21) as encapsulated postscript files. Finally, write a function of your own called myfunc, which is of the form y=myfunc(x) and saved in a file called myfunc.m. It can be whatever you like, but must work when x is a vector, and return some y that has the same dimensions as x. Then call fourierApprox('myfunc'), and save the final plot (with a title saying what function you used) as an encapsulated postscript file. Also save a plot of the actual function (i.e. plot(x,myfunc(x)) ) as an encapsulated postscript file. Submit fourierApprox.m, myfunc.m, and the specified postscript files as your problem solution. And you're done! EITHER do question 6 _OR_ question 7. Both questions are very open-ended -- the minimum requirements are to get a simple functioning program, so do that first. Only afterwards should you try to make it more elaborate. Think out carefully how you want to organise the program, and sketch out the overall stucture and snippets of code on paper/board before sitting in front of the computer in hacking mode. 6. Entertainment time! You have control of a robot kangaroo which can hop from a stepping stone to the stepping stone immediately in front of it (or even hop across whole bunches of stones in a straight line -- but not gaps(!) -- in one jump). The commands that can be given are: (a) to face North, East, South, or West; and (b) to hop forwards n stones (where n is a positive integer of course!) The stones have been laid out in a grid aligned with the South-North and West-East axes. However, not all of the stones are there, the kangaroo is incapable of making hops over any missing stones (gaps), and there is a fearsome monster lurking in the gaps. Effectively, your kangaroo is looking at a maze. The kangaroo starts at the only entrance to the maze, and has to retrieve a valuable treasure from a cache hidden in a stone somewhere inside the maze, and then escape back through the place it entered. The only input you can have is to tell it to start -- it must 'solve' the maze itself. (Sorry, but your kangaroo is terribly myopic -- it can only see one spot in front; so it can tell whether or not there is a stone in front to hop to, but it cannot see any further ahead, and it can't tell if there is any treasure until it lands on the treasure stone.) The treasure is vey delicate and heavy, so the kangaroo can only ove one square at a time in its escape (but still has the ability to 'remember' the way out). The maze may well have many dead ends and 'circuits' which could be gone round for ever. Since the routes are only N-S and E-W (both directions in both cases), the only junctions you could arrive at would be T-junctions or cross-roads (and the only other routes are straight, or left corners, or right corners, or dead-ends). Write a Java program to direct your robot kangaroo to achieve its objectives in a reasonably efficient way (i.e., don't continually go down the same dead-ends!!). So that you know what's happening, if the kangaroo would be about to hop one step forwards, and such a step would take it into the mire, then the kangaroo will yell "I don't want to get eaten!". Be warned, however, one a kangaroo (even a robot one) has any serious momentum (i.e., if it tries to hop 2 or more stones forwards), then it can't stop early, and if it lands in the mire it can't hop out; so if ther is a stone missing 3 spots ahead, and the kangaroo is about to hop 3 (or 4, or 5, etc.) spots forwards, then it will yell "I hope that your next kangaroo fares better!", and all its acquired knowledge dies with it! As a suggestion, you might like to ask for the stones in the maze to be given as a pair of integer coordinates. The next step in the 'prettification' of your program is to persuade the computer to show an image of the maze together with an indicator of the current location of the robot kangaroo (and any adversaries it may have -- see later) while it traverses the maze. To make things more interesting, the treasure sits on a square which is connected to an alarm system, and as soon as the kangaroo leaves that square with the treasure, alarms sound throughout the land. This awakens the voracious Gorrschae (a breed of slow-moving spider). These Gorrschae move at a tenth of the kangaroo's speed (i.e., one square after every ten kangaroo squares). They start from the darkest end of the dead-ends (aptly named!), and spin a web of noxious stickiness behind them (produced by a heady diet of vast quantities of Rhubarb!). If the kangaroo and a spider arrive on the same square, the robot kangaroo is devoured (along with the treasure, which passes via tortuous intestinal routes back to the original hiding place). The kangaroo can see the spiders only if they're on an adjacent (not diagonally adjacent) square, however, the kangaroo (being rather panicked in its escape), has to move somewhere each 'move' -- it can't stand still. So if the kangaroo has no valid move other htat stepping on a spider square, then it does so and suffers terminal spidery slaivary decomposition. Also, if the kangaroo has to step on a square which has sticky web on it, then its relative speed drops by one (so the spiders now move after every ninth kangaroo move). This process is cumulative; so after stepping on 10 webbed squares the kangaroo can no longer move, and merely awaits its demise demurely while the spiders prowl. All that remains is to see how the spiders move. They move simultaneously and independetly of each other, they're unaffected by web stuff (sic!), and if already moving along a junctionless 'corridor', simply continue moving in the same direction. If faced with a choice at a junction, they decide radomly amongst all the available choices. The have no memory of where they've been, but if given a choice between webbed and unwebbed squares will always choose unwebbed ones. Happy treasure-hunting! 7. Write a Java program to play Checkers (Draughts) on an NxN board (it would normally be played on an 8x8 board, but that might take rather long, so perhaps it's best to do this on a 6x6 grid instead). If your board is NxN then have N pieces for each player. You should make full use of distinct classes for this simulation, and life would be much easier for you if you first plan out very carefully how to aportion the various jobs amongst the various classes you forsee. As a matter of sanity don't try to write a particularly intelligent player -- just keep to legal moves! Later you can build a rather more clever version. Once you have the classes and associated methods defined, and congealed into a functioning program, you can start adding bells and whistles to the project. (Those which follow are suggestions, not requirements.) -- Computer moves first. -- Allow pawns to be promoted to kings. -- Allow for multiple jumps. -- Have the computer select the "best" move rather than a random one. This would require a static evaluator to determine "bestness" for each of the possilble moves. This might require extending the class you used to handle moves. -- Have the display be GUI rather than screen based. Color. Animation. Sound efffects. ..................!!!! -- Mouse input instead of keyboard input. Or both. -- Code it as an applet, not a program. -- Have the computer look ahead n moves.