In this assignment, you will be solving the same problem in ALL FOUR languages that we have used in this course: Java, rex, prolog, and ISCAL. The goal of this assignment is both to reinforce your comfort with these languages and also to help you identify the relative merits of using different languages. Therefore, there is also a short fifth part of the assignment where we ask you to compare and contrast the relative strengths and weaknesses of two of the languages for solving this problem. We'll revisit this problem in a few weeks when we study algorithm analysis.
Here's the story: You've been hired as the Chief Technical Officer of the Wall Street firm Weil, Proffet, and Howe. The firm's specialty is assessing the past history of the stock market. In this problem, you will be given an array (or a list, if you are using rex or prolog) of positive integer values where the element at position i in the array indicates the value of a share of Millisoft stock on day i.
That is, if the array (or list) has length n, it represents a history of n days of the values of this stock. Our objective is to find the maximum profit that could be made by purchasing a single share on some day and selling on that day or later. (Buying and selling on the same day makes 0 profit, so you can't do worse than that!) Remember, you cannot sell on a day before your buy day!
For example, consider the array A[1] = 100, A[2]=30, A[3]=32, A[4]=35, A[5] = 7. Note that although the lowest value of the stock is 7 and the highest value is 100, we cannot make 100-7=93 dollars profit because we cannot sell before we buy! The best we can do here is to buy on day 2 and sell on day 4 for a profit of 35-30 = 5 dollars.
Your job is to write four different programs to solve the stockmarket problem: One in Java, one in rex, one in prolog, and one in ISCAL. Make sure to comment your code in all cases. Here are the details of the assignment:
In the directory /cs/cs60/assignments/assignment11 you will find several files: SMHelper.java and StockMarket.java contain code and prices1.txt and prices2.txt contain stock market prices.
Copy these files into your directory. The first file, SMHelper.java contains some code for reading data from files. You don't need to touch it (although you're welcome to look at and see what's there - you'll discover that it has some extra features that we'll be using again in a few weeks).
Take a look at the file StockMarket.java. You'll notice that it has a main method which uses SMHelper to read in some stock prices from a file. After obtaining the stock market prices and putting them in an array, it calls the function solve by passing in the array. You will write the REAL part of this program, namely the solve function. This function computes the maximum profit obtainable and returns that value to main which then prints it.
How do you compile and run this program once you've written the code? First compile SMHelper.java. Then compile StockMarket.java. Then run it by typing java StockMarket prices1.txt or you can use another file (that you create) with stock prices other than prices1.txt or prices2.txt.
Notice that the format of these stock price files is as follows: The first line contains the number of stock prices. Then, each subsequent line contains a single stock value. After the very last stock value be sure to have a carriage return (that is, hit the RETURN or ENTER key after the last stock value).
Submit your StockMarket.java file using cs60submit.
(In a few weeks, we'll learn some ways to write super fast programs for this and many other problems. For now, speed is not an issue. Just be sure that your program is correct. Test it thoroughly to make sure that it always finds the correct solution.)rex> stockmarket([2, 4, 1, 10]); 9 rex> stockmarket([4, 3, 2, 1]); 0
Place your code in a file called stockmarket.rex and submit it using cs60submit.
prolog> stockmarket([2, 4, 1, 10], X). X = 9; no prolog> stockmarket([4, 3, 2, 1], X). X = 0; noIn the second case, it's also fine if the rule does not give the answer 0 but instead just says "no". Notice, however, that stockmarket([2, 4, 1, 10], 2) is not true, even though we can make 2 dollars in profit. The only value for which stockmarket([2, 4, 1, 10], X) is true for X=9.
Place your code in a file called stockmarket.pl and submit it using cs60submit.
Finally, you'll solve this problem in assembly language. The best approach is to effectively translate (or "compile") your Java solve function from Part 1 into ISCAL.
Here's the idea. When the program is started, it will query the user to type in numbers one at a time. These numbers will be positive numbers representing stock values. When the user enters 0, this indicates the end of the input. Notice that the user does not specify in advance how many stock values she plans to enter!
Where do those stock values get stored? In an array! How do we make arrays in machine/assembly language? Remember that your program resides in memory beginning at memory address 0. After the last line of code, there is plenty of memory. We used that memory for our stack in the last assignment. In this case, we'll use that memory to store the array. That is, each element entered by the user will be stored in its own memory location! What we see here, is that arrays are just data elements stored in contiguous memory locations. How cool!
So, your program will take input from the user and store that input into memory. When the user finally enters 0, your program will call a function to compute the maximum profit in that array. You'll need to pass that function some input. For example, you might pass it the address of the beginning of the array and the address of the end of the array. That function will return a result, namely the maximum profit achievable in the array. Your program will print that result and halt.
How do we make an ISCAL program halt? If you jump to memory address 0, this causes ISCAL to halt. That's weird, but that's what ISCAL does.
You may borrow any code you like from code that you've written for Assignment 10 or that we provided for that assignment. In particular, you'll want to use Professor Keller's input and output code.
Here is some sample input and output:
turing> isc stockmarket.isc 1 2 3 0 2Notice that we entered three real stock values: 1, 2, and 3. Then we entered 0 to indicate end of input. That is, the first four lines indicate the user entering numbers. The maximum profit here was 2 and that's what ISCAL printed.
Submit your program stockmarket.isc using cs60submit.
One objective of this course is to have you reflect on how different languages provide very different ways of solving a computational problem. Now that we've seen four very different representative languages, we'd like you to think about these languages.
Choose two of the four languages in this assignment and write a paragraph or two comparing and contrasting their strengths and weaknesses for solving this problem. You may want to consider issues such as how much code was required, ease of debugging, the way in which the language forced you to think about the problem, how naturally suited the language was for this task, the readability of the code, your own perception of the "elegance" of the solutions in these languages, etc. You are invited to include your own personal views in this short essay, but try to explain the basis for your positions. Saying "I just don't like language X" isn't sufficient. You can say "Language X does not seem very well-suited for this problem because..." We look forward to reading what you write!
Please write clearly and make sure that your prose is grammatical and free of typographical errors. Submit your text in a file called part5.txt using cs60submit.