University of Illinois at Urbana-Champaign
Department of Computer Science
CS 497 Object-Oriented Programming and
Design
Fall 2000
TIME LIMIT = 3 HOURS
COVER SHEET + 8 PAGES
Print your name and
netid neatly in the space provided below; print your name in the upper right
corner of every page.
|
Name: |
|
Netid: |
This is a closed book, closed notes examination. You may not use calculators or any other electronic devices. Any sort of cheating on the examination will result in a zero grade.
Do all the problems
in this booklet. Do your work inside
this booklet, using the backs of pages if needed. The problems are of varying
degrees of difficulty so please pace yourself carefully, and answer the
questions in the order which best suits you. Answers to essay-type questions
should be as brief as possible. The maximum grade on this exam is 100 points.
|
Problem |
Score |
Problem |
Score |
Problem |
Score |
|
1 |
|
11 |
|
21 |
|
|
2 |
|
12 |
|
22 |
|
|
3 |
|
13 |
|
23 |
|
|
4 |
|
14 |
|
24 |
|
|
5 |
|
15 |
|
25 |
|
|
6 |
|
16 |
|
26 |
|
|
7 |
|
17 |
|
27 |
|
|
8 |
|
18 |
|
28 |
|
|
9 |
|
19 |
|
29 |
|
|
10 |
|
20 |
|
|
|
|
Total |
|
|
|
|
|
The following might be names of patterns: Abstract Class, Abstract Factory, Adapter, Bridge, Builder, Chain
of Responsibility, Collaborator, Command, salaComposite, Decorator, Façade,
Factory Method, Flyweight, Interpreter, Iterator, Mediator, Memento, Mentor,
Observer, Prototype, Proxy, Singleton, Specification, State, Strategy, Template
Method, Visitor
The purpose of many of the design patterns is to make it easy to change
some property of the system. What
design pattern would you use to make it easy to change:
1.
(2 points) The
way a set of objects interact.
2.
(2 points) The
class of the object that a method returns.
3.
(2 points) The kind and number of objects
that react to changes in the object you are designing.
4.
(2 points) The
algorithm that is being applied to a tree of objects, where the nodes in a tree
are in many different classes.
5.
(2 points) The
internal state of an object, but you want to be able to remember this state and
then later tell the object to go back to that state.
6.
(2
points) What design pattern should you
think of first when you want to implement undo?
7.
(2 points)
What design pattern should you think of first when you want to implement one
and only one instance of a class?
8.
(2 points)
Which pattern do you think about when a design requires a tree of objects?
9.
(2 points)
What design pattern should you think of when you want to hide how you construct
a complex object?
10. (2 points) What design pattern should you
think of when you want to reuse an object but it has the wrong interface?
11. (2 points) What design pattern should you
think of when you want to reuse an object but it must run on another computer?
12. (5
points) Observer/Strategy.
Suppose you are building a simulation of a chemical factory. Your simulation contains a class called
Container that represents a container that holds chemicals. Chemicals can flow into it and out of it. It has a method
addVolume: aNumber
volume := volume + aNumber.
volume > maximum ifTrue: [self
overflow].
channels do: [:each | each
calculateInput].
displays do: [:each | each
redisplay]
There are a variety
of "Channel" classes, each of which implements
"calculateInput", and a variety of "ContainerDisplay"
classes, each of which implements "redisplay". You decide that it would be better to use
the Observer pattern and make Channels and ContainerDisplays be observers of
the Container. Show the new version of
addVolume:
13. (5 points) How would the Channel and
ContainerDisplay classes have to change?
14. (5 points) What else would change? (Hint: how do the variables
"channels" and "displays" get their values?)
15. (10 points) Suppose there is a whole class
hierarchy of Containers, many of which specify how the container overflows by
redefining the "overflow" method.
You decide that you want to change the system so that each container has
a strategy for specifying how it overflows.
How would you change the system so that it would use the Strategy
pattern? Describe the steps that you
would take. If you write ten steps, it
is too many! For example, step one is
1) Create a class OverflowStrategy that is a subclass of Object.
16. (10 points) The following methods were taken
from two classes, class A and class B, which had a common superclass C.
Refactor these
methods to use the Template Method pattern.
Show all the methods you would create.
Clearly state which class each method is in.
Class A
keyFrom: aRequest
aRequest identifier size < self depth
ifTrue:
[^aRequest postDataAt:
#COMMAND
ifAbsent: [aRequest
postDataAt: #DEFAULT_COMMAND
ifAbsent: [self rootKey]]].
(self containsAction: (self matchingElementFromPathIn: aRequest))
ifTrue: [aRequest decodeUrlencodedFormData: aRequest
lastIdentifier].
^self matchingElementFromPathIn: aRequest
Class B
keyFrom:
aRequest
aRequest
identifier size < self depth ifTrue: [^self rootKey].
^self
matchingElementFromPathIn: aRequest
There are lots of ways to make streams in Smalltalk. For example,
ReadStream on: 'this is a string'
'input.txt' asFilename readstream
WordStream on: ('input.txt'
asFilename readstream)
17. (2 points) The first two lines would return
a stream of characters. But the third
returns a stream of what? Note that
there is not a standard class 'Word'.
18. (4 points) Show how you would use a stream
to iterate over the elements of a collection.
This is an example of the Iterator pattern. Streams are the "external iterator" variation.
19. (4 points) Most of the time you want to
iterate over a collection in Smalltalk, you would use an "iternal
iterator". Show a simple example
of Smalltalk code that is using an internal iterator.
20. (4 points) Explain how WordStream is like
the Decorator pattern. Explain how it
is like the Adapter pattern. Which one
do you think it is most like?
A system for
modeling routes between cities has classes City and Road. A road runs from one city to another. A city
has a name, and a road has a length. A
city knows the roads connected to it. A
road knows the cities it connects.
21. (2 points) What are the instance variables
of City and Road? Describe the contents of each variable.
22. (5 points) Suppose that City has a class
method named: that creates a new City, and it has an instance method makeRoadTo:length:
that creates a Road to another City of a particular length. You could then create a network of cities
and roads as follows:
| city1 city2 city3
city4 |
city1 := City
named: 'Champaign'.
City2 := City
named: 'Chicago'.
City3 := City
named: 'St. Louis'.
City4 := City
named: 'Indianapolis'.
City1 makeRoadTo:
city2 length: 130.
City1 makeRoadTo:
city3 length: 150.
City1 makeRoadTo: city4
length: 100.
City2 makeRoadTo:
city4 length: 160.
Define all the class and instance methods of City and Road that are
needed to make this work.
Suppose that there is also a class Route. A route is a sequence of cities such that any pair of cities on
the route has a road between them. A
route can enumerate both its cities and its roads. "->" is a binary message just like "+" or
"=". We would like to build a
route from Indianapolis to St. Louis that passes through Chicago and Champaign
by
city4 -> city2 -> city1 -> city3
The "->" method takes a city as an argument. When sent to a city, it returns a route from
one city to the next. When sent to a
route, it returns a new route that traces the first route and then adds a road
to the next city.
23. (5 points)
What are the instance variables of Route? Define the -> method for City and Route and any methods on
City, Route, or Road that they require.
24. (2
points) Define a "length" method on Route that returns the length of
the route.
25. (2 points) Define a < method on Route
that returns true if the length of the receiver is less than the length of the
argument.
26. (2 points) Define a neigboringRoutes method
for City that returns a collection of routes from that city to its immediate
neighbors.
27. (3 points) Define a neighboringRoutes method
for Route that returns a collection of routes that are the same as the receiver
except that they have added on a road from the last city on the Route to one of
its neighbors. Suppose that lastCity returns the last city in a route. Then, for any Route r, r neighboringRoutes
size = r lastCity neighboringRoutes size.
28. (4 points) What happens if you try to make a
route between two cities without a road between them? One solution is to generate an error. A second solution is to generate an IllegalRoute, i.e. to make a
special object to represent the error.
An IllegalRoute would have the same interface as a Route, but if you try
to extend an IllegalRoute, you end up with the same IllegalRoute. Implement
IllegalRoute and show how you would have to change City and Route to use it.
29. (4
points) It is possible to implement City and Route without Road. Each city can have a dictionary that tells
it the distance to each neighboring city.
Show how you would implement makeRoadTo:length: and -> if there were
no class Road.