Задание 02 курса ADT and Algorithms

Question 1

50 MARKS

Consider a “RedBlueStack” which behaves like a normal stack, except for the fact that items inserted into the stack can be labelled as either “red” or “blue” and that there are two pop operations which return the most recently inserted “red” or “blue” item, respectively. A “RedBlueStack” should provide the following methods:

isEmpty()
Test if the stack is logically empty.

makeEmpty()
Make the stack logically empty.

popRed()
Remove the most recently inserted red item from the stack.

pushRed(Object)
Insert a new red item into the stack.

topRed()
Get the most recently inserted red item in the stack.

topAndPopRed()
Return and remove the most recently inserted red itemfrom the stack.

popBlue()
Remove the most recently inserted blue item from the stack.

pushBlue(Object)
Insert a new blue item into the stack.

topBlue()
Get the most recently inserted blue item in the stack.

topAndPopBlue()
Return and remove the most recently inserted blue item from the stack.

toString()
Return a string representation of the stack (showing all current elements in reverse chronological order and with a red/blue indication for each element).

(a) Design a RedBlueStack interface. [5 MARKS]
(b) Design a class RedBlueStackLi which implements a RedBlueStack interface through a linked list. [40 MARKS]
(c) Design a test program for the class RedBlueStackLi and hand in output of test runs which show that all methods work correctly. [5 MARKS]

IMPORTANT: All methods except toString() should be implemented to run in time O(1).

Question 2

50 MARKS

When a share of common stock of some company is sold, the capital gain is the difference bewteen the share’s selling price and the price originally paid to buy it. This rule is easy-to-understand for a single share, but if we sell multiple shares of stock (of the same company) bought over a long period of time, then we must identify the shares actually being sold. A standard accounting principle for identifying which shares of stock were sold in such a case is to use a FIFO protocol. That is, the shares sold are the ones that have been held longest (indeed this is the default method built into several personal finance packages). For example, suppose we buy 100 shares at $20 each on day 1, 20 shares at $24 on day 2, 200 shares at $36 on day 3, and then sell 150 shares on day 4 at $30 each. The applying the FIFO protocol means that of the 150 shares sold, 100 were bought on day 1, 20 were baought on day 2, and 30 were bought on day 3. The capital gain in this case would therefore be 100 x $10 + 20 x $6 + 30 x (-$6) = $940.

(a) Design a Stock interface class which supports the following operations [4 MARKS]:
- buy x shares at $y each
- sell x shares at $y each and return the TOTAL capital gain from all buy/sell actions so far. (If the stocks in the portfolio are insufficient, sell all available stocks.)
- toString(): print current portfolio
- makeEmpty(): reset portfolio to empty

(b) Design a class StockLi which implements a Stock interface through a linked list. [40 MARKS]

(c) Design a test program for the class StockLi and hand in output of test runs which show that all methods work correctly. [6 MARKS]


Решение:

    29 Май 2009 by freetonik

This website uses IntenseDebate comments, but they are not currently loaded because either your browser doesn't support JavaScript, or they didn't load fast enough.

Comment Form


Warning: Parameter 1 to id_generic_callback() expected to be a reference, value given in /home/users/f/freetonik/domains/css.freetonik.com/wp-content/plugins/intensedebate/intensedebate.php on line 911

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 8629040 bytes) in /home/users/f/freetonik/domains/css.freetonik.com/wp-includes/functions.php on line 959