- Do you currently plan to talk regularly with any other CSE 222 students about homework and lab assignments? What acts constitute "going over the line" between acceptable collaboration and academic misconduct?
- Suppose you submitted for a lab assignment a "correct" program that was sloppily done and poorly documented, and was generally not something you'd want to show to, say, your boss. Approximately what mark would you expect to receive for it?
- Of the course's intended learning outcomes, which is the most surprising one, in the sense that you might not have expected to see it as an objective for this course? Why?
- What special relationship is there between your final exam grade and your course grade?
- What is the main problem with trying to design a software component catalog using only global operations (a.k.a. subroutines)?
- Suppose a concrete instance you need is a class named Timer_1 in the Timer component family. What #include statement would you use to bring it into scope?
- Write a line of code to declare an object of the type defined by Timer_1.
- Would it matter in the Monte_Carlo.cpp code if the code to check for a point's inclusion in the quarter circle used "<=" rather than "<" for the comparison? Why or why not?
- What problem does the #ifndef-#define-#endif idiom solve?
- What does the keyword public mean in a Resolve/C++ component?
- What are the "standard operations" for a Resolve/C++ component?
- What does the keyword is_abstract mean in a Resolve/C++ operation declaration?
- What is the default parameter mode of self for a procedure operation? For a function operation?
- What is the key difference between a template and an instance?
- There is one minor difference in behavior between the Add operation for Sequence<Character> and the Add operation for the built-in type Text. What is it? Hint: Look closely at the specifications of the two operations.
- Explain in English the meaning of the declaration of Polynomial_Coefficients in Poly_Eval.cpp.
- In the body of operation Horner_Recursive_Evaluation, why is it necessary to store the result in a local object, as opposed to using this code:
- Select any of the bullets at the end of Section 2.2.3 that requires you to think seriously before answering, answer the question(s) for that bullet item, and explain the thinking that went into your answer(s). (If none requires you to think hard, then select the last bullet.)
- In what circumstances, if any, is it appropriate for the body of an operation not to clear a produces-mode parameter before using it?
a.Remove (0, y);
return x * Horner_Recursive_Evaluation (a, x) + y;
a.Add (0, y);
- Set_Of_Integer
- Set_Of_Set_Of_Integer
- Queue_Of_Set_Of_Integer
An operation you'll need for Lab #1 is Get_Words. The meaning of the specification is that the operation should read one line at a time from input into a Text object; and if that Text value is not already in words, then it should add it to words. Assume that Set_Of_Text is an appropriately named concrete instance that has been previously declared.
/*!
math operation LINES (
s: string of character
): string of string of character satisfies
if s = empty_string
then LINES(s) = empty_string
else if "\n" is not substring of s
then LINES(s) = <s>
else there exists a, b: string of character
(s = a * "\n" * b and
"\n" is not substring of a and
LINES(s) = <a> * LINES(b))
!*/ global_procedure Get_Words (
alters Character_IStream& input,
produces Set_Of_Text& words
);
/*!
requires
input.is_open = true
ensures
input.is_open = true and
input.ext_name = #input.ext_name and
input.content = empty_string and
words = elements (LINES (#input.content))
!*/
- Design and code the body of this procedure.
-
Review your understanding of the formal specification as compared to the
informal specification. Pay special attention to the difference between
the mathematical model types string of character (the parameter
to LINES) and string of string of character (the result of LINES).
If you follow the inductive (i.e., recursive) definition of LINES,
you should be able to figure out why LINES("Here is a line\nand another.")
= <"Here is a line", "and another."> Then determine the values
of the following expressions:
- LINES("")
- LINES("Hello")
- LINES("Hello there!")
- LINES("Here is a line\nand another\nand another...\n")
- Suppose you decide to use an instance of Record to
store each entry in an electronic appointment book. Such a record
(say, concrete instance Apptmt_Entry) consists of a deadline --
a day of the week, an hour, a minute, and an AM/PM flag -- along with a short piece of
text that describes the appointment.
- Write the Resolve/C++ declaration to create this new concrete instance by instantiating concrete template Record with fields of the built-in types. (In practice, you might want to define types such as Day_Of_Week and Time_Of_Day and then create a Record instance with fields of these types. But for this exercise, just use the built-in types.)
- Write the Resolve/C++ declarations of appropriate field names for Apptmt_Entry.
-
One of the things you might want to do with a Apptmt_Entry object
is to print it, appropriately labelled. For example, if the value
of such an object is (6, 10, 30, false, "CSE 222 closed lab") then you might want
to print something like this:
Write a body for the following operation:Friday, 10:30 AM: CSE 222 closed lab
global_procedure Print_Entry (
alters Character_OStream& out,
preserves Apptmt_Entry& x
);
/*!
requires
out.is_open = true
ensures
out.is_open = true and
out.ext_name = #out.ext_name and
out.content = #out.content * [x printed as above]
!*/
- What is a transitive relation? Give an example of a transitive relation from everyday life, not from software engineering. (Hint: Think about a family tree.)
- Speaking of trees, suppose the dependency graph in Figure 3-3 were not quite so complicated. Suppose instead it were a dependency tree. To be specific, suppose the "top-level" (in the diagram, right-most) concrete component depended on exactly two other concrete components, and that each of those depended on two other different concrete components, and so on through three levels of dependency arrows. Draw the resulting tree. How many components are in it? If you changed something in one of the bottom-level components, how many other components potentially would be affected by the change (i.e., how many components depend on a bottom-level component)? To understand the top-level component, how many other components might you need to understand (i.e., how many components does the top-level component depend on)?
- Why does dependence on an abstract component tend to be less of a problem than dependence on a concrete component?
- What is the "defensiveness dilemma"?
- In Resolve/C++ programs (i.e., under the "design-by-contract" or "programming-by-contract" discipline), who is reponsible for making sure that the precondition is true at the time of the call to an operation: the implementer of the operation, or the client of the operation, neither, or both?
- What is a "checking component"?
- What benefits accrue from using templates for decoupling checks?
- What does a parameter box stand for in a CCD?
- In order to be consistent with the code it summarizes, what name should the parameter box have in the CCD that shows how to decouple a checks relationship? (This name normally is not shown in the CCD because it is entirely arbitrary; but you should be able to say which name in the code the parameter box in the CCD corresponds to.)
A second way to achieve this is as follows. You can instantiate Set_Kernel_1 with Item bound to Text, and then instantiate Set_Kernel_C with Item bound to Text and with Set_Base bound to the instance of Set_Kernel_1 you just created. Write the two template instantiations needed to do this.concrete_instance
class Set_Of_Text :
instantiates
Set_Kernel_1_C <Text>
{};
- What benefits accrue from using templates for decoupling extends?
- In order to be consistent with the code it summarizes, what name should the parameter box have in the CCD that shows how to decouple an extends relationship? (This name normally is not shown in the CCD because it is entirely arbitrary; but you should be able to say which name in the code the parameter box in the CCD corresponds to.)
- Rewrite the body of Put_To so self is swapped with temp after the loop, not before it.
- Why don't you need to know anything about the behavior of Open_Scope and Close_Scope in order to complete part A? That is, how do you know there are no "weird interactions" between those calls and the code you just modified?
- Suggest an application program in which Sorting_Machines might be useful.
- Which operations of Sorting_Machine would be overridden in a checking component for it?
-
Write a body for the following operation:
global_procedure Remove_Min (
alters Queue_Of_Text& q,
produces Text& min
);
/*!
requires
q /= empty_string
ensures
(q * <min>) is permutation of #q and
for all x: string of character
where (x is in elements (q))
(min <= x)
!*/ - Write a body for the global procedure Sort for an object q of type Queue_Of_Text, using the "selection sort" algorithm. This algorithm repeatedly calls Remove_Min until q is empty, placing the items it returns one-by-one into a temporary queue, and then finally swapping this temporary object with q.
global_procedure Find_Min_And_Max (
preserves Queue_Of_Integer& q,
produces Integer& min,
produces Integer& max
);
/*!
requires
q /= empty_string
ensures
{min, max} is subset of elements (q) and
for all x: integer
where (x is in elements (q))
(min <= x <= max)
!*/
- Show a tracing table with one statement, a call to this operation, that illustrates what the operation would do for some choice of legal values for the arguments.
- Why do you need the requires clause?
- Show a tracing table with one statement, a call to this operation, that illustrates the importance of the first line of the ensures clause (not the requires clause). That is, show how a correct implementation of the specification without that line might not do what the operation name suggests it does.
- Write a body for this operation that uses the "Noah's Ark" algorithm. This algorithm takes entries from q in pairs, first comparing them to each other, then comparing the smaller of the pair to the minimum so far and the larger of the pair to the maximum so far.
abstract_template <
concrete_instance class Item
>
class Queue_Reverse :
extends
abstract_instance Queue_Kernel <Item>
{
public:
procedure Reverse () is_abstract;
/*!
ensures
self = reverse (#self)
!*/
};
concrete_template <
concrete_instance class Item,
concrete_instance class Queue_Base
/*!
implements
abstract_instance Queue_Kernel <Item>
!*/
>
class Queue_Reverse_1 :
extends
concrete_instance Queue_Base,
implements
abstract_instance Queue_Reverse <Item>
{
public:
procedure Reverse ()
{
//-------- for students to fill in --------
}
};
procedure Reverse () is abstract;
/*!
ensures
self = reverse (#self)
!*/
function_body Integer Foo (
preserves Integer n
)
{
if (n <= 1)
{
return 1;
}
else if (n mod 2 == 0)
{
return Foo (n/2) + 1;
}
else
{
return Foo (3*n+1) + 1;
}
}
- How many tracing tables would you need to trace the call "Foo(3)" if you decided to trace into the body of each recursive call?
- What value is returned by "Foo(3)"?
- (Significant extra credit) Prove that the call "Foo(n)" terminates for every value of n.
- Suggest an application program in which Partial_Maps might be useful.
- In discussing how to implement a certain feature of a new product your company is developing, you suggest that a Partial_Map could be used. A co-worker scoffs at the suggestion, claiming that Partial_Maps are completely superfluous and should never have been invented. His reason is that you can always just instantiate a Record with two fields whose types are the D_Item and R_Item types you would have used to instantiate your Partial_Map, and then instantiate Set with this Record as the entry type. In other words, to use a bastardized C++-like notation, he claims:
Is he right? Why or why not?Partial_Map <D_Item, R_Item> = Set <Record <D_Item, R_Item> >
- You need to keep track of the assignments of guests to hotel rooms in a program that is used by the front desk, so the program can look up what room number a guest is in, given the guest's name.
- You need to keep track of a deck of playing cards in a program that plays a card game, so the program can shuffle the deck and deal the cards.
- You need to keep track of the times (possibly several per day) that the alarm should go off in an alarm clock utility program.
Software Originals, Inc., has been hired by Eaton Wright, the "pizza king", to help automate a new chain of pizza delivery stores. SOI's system engineering staff have asked you to implement a prototype for the telephone operator's console. To start the project they have assigned you to implement the following two operations (the first of which will be used to read files containing menus of pizza sizes and their prices, and pizza toppings and their prices; and the second of which will be used to read the first order from a file containing pizza orders whose total prices are to be calculated). They haven't had time to write formal specifications; hence the informal nature of the descriptions. The type Price_Map is an instance of some implementation of Partial_Map_Kernel where D_Item is bound to Text and R_Item is bound to Integer.
Design and code the bodies of the operations Get_Price_Map and Get_One_Order. Review your code carefully -- with someone else in the class if you can -- and trace it on some examples, but do not try to compile it until closed lab. The objective is to have code that works the first time you compile it (except perhaps for typos). Note that some useful detailed information about input/output and converting from one Resolve Foundation type to another (e.g., from Text to Integer) is available via this link.global_procedure Get_Price_Map (
preserves Text file_name,
produces Price_Map& p_map
);
/*!
requires
[file named file_name exists but is not open, and has the
format of one "word" and one price (in cents) per line,
with word and price separated by '\t'; the "word" may
contain whitespace other than '\t']
ensures
[p_map contains word -> price mapping from file file_name]
!*/
global_procedure Get_One_Order (
alters Character_IStream& input,
preserves Price_Map& sp_map,
preserves Price_Map& tp_map,
produces Integer& price
);
/*!
requires
input.is_open = true and
[input.content begins with a pizza order consisting of a
size (something defined in sp_map) on the first line,
followed by zero or more toppings (something defined in
tp_map) each on a separate line, followed by an empty line]
ensures
input.is_open = true and
input.ext_name = #input.ext_name and
#input.content = [one pizza order (as described
in the requires clause)] * input.content and
price = [total price (in cents) of that pizza order]
!*/
- Figure 1-1 shows the data representation selected for Natural_Kernel_18 to be a mathematical string of digits. Rather than using a Sequence, could you have chosen to use a Queue or a Stack to hold the digits for this representation? Explain your answer.
- The design described in Section 1.1 rules out <4,69,2> as a possible representation string. Is there a different design for the data representation in which this string should be allowed? Explain your answer in terms of convention and correspondence, even if only informally in English.
- Redraw Figure 1-7 with the sample operation Divide_By_Radix and the same two starting abstract values for self. (By now, you should know how to find the contract for this operation both in the textbook and in the on-line component catalog.)
-
Draw a commutative diagram for Set_Kernel_1 that you could use to
illustrate the Add operation. (Because Add changes
its argument as well as the receiver object, you should invent some way
to include that changed argument value in the diagram. There is no
wrong answer on this part; make up something that you consider sensible.)
Label a point in the "before" abstract state space {13,47,-694}, label
the top arrow across the diagram "s.Add (x)", and
suppose x = 75 at the time of this call. Then clearly label
the following additional things:
- The new value of s in the "after" abstract state space.
- The point in the "before" concrete state space that stands for the representation of the original s.
- The point in the "after" concrete state space that stands for the representation of the new s.
- The arrow between these points in the "before" and "after" concrete state spaces that stands for what the Add operation body does to achieve the desired effect on the representation of s.
- Do the same thing as above in the same starting configuration, but this time for the Set_Kernel_1 operation "s.Size ()". (Because Size is a function, you should invent some way to include the return value in the diagram. Again, there is no wrong answer on this part; make up something that you consider sensible.)
- Copy the Set_Kernel_1 CCD from the transparency that shows it. Label each box and arrow in the CCD -- except the "uses" arrow -- with a number, in any order. Print the first page of CT/Set/Kernel_1.h (from the Resolve/C++ Catalog), or copy either the first page of the code of CT/Set/Kernel_1_Part.h from the CSE 222 Course Packet or the first full page of Figure 1-11 from Software Component Engineering With Resolve/C++, Volume 3: The Implementer's View. On it, circle and label with the same number the Resolve/C++ encoding of the corresponding box or arrow of the CCD. (Note that the "uses" arrow doesn't match up with a Resolve/C++ keyword. The meaning of "uses" in the CCD is this: The component at the tail of the arrow depends on the component at the head of the arrow, but it holds no other specific named relationship with that component. In other words, "uses" is a catch-all dependency relationship that applies when nothing more specific -- implements, extends, checks, etc. -- is appropriate.)
Test Plans, Test Cases, and the Test Driver
As you know, a test plan consists of a set of test cases, each of which is intended to exercise a single call of a single operation. For each test case you should basically have three rows of a tracing table: the first row shows the state before the call, with values for all the operation's actual parameters including the distinguished object; the second row shows the call itself; and the third row shows the expected state after the call, again with values for all the operation's actual parameters including the distinguished object. You should review your notes from 221 for some hints on how to select test cases based on the specifications of the operations to be tested. As part of this homework, i.e., before closed lab, you should create a file that encodes the test plan in a format that greatly facilitates testing; see "Test Script" below.The method to be used to test an implementation of Sequence_Kernel is as follows. We provide a
test
driver main program that allows you to manipulate two special test
objects of type Sequence_Of_Text (which is an instance of some implementation
of Sequence_Kernel <Text> extended with the Put_To
operation). You tell the test driver which operation you wish to
perform and, where appropriate, on which of the two special test objects
you wish to invoke it (pretend their names are s1 and
s2)
and which values the other parameters should have. The test driver
then performs the operation and reports the values of the other parameters
-- but not the value of the special test object. In order to see that value,
you have to ask the test driver to print it. For example, suppose
you want to conduct the following test case:
| s1 = <>, pos = 0, x = "Foo" | |
| s1.Add (pos, x); | |
| s1 = <"Foo">, pos = 0, x = "" |
If the operations so far executed for s1 have left s1 empty (as claimed in the first row of the tracing table) then you can respond to the test driver's prompts with the following lines:
aThe "a" means "execute the Add operation". The "1" means to do this operation on special test object s1. The "0" means the first argument to the operation has the value 0, and the "Foo" means the next argument to the operation has the value "Foo". (Note that on both input and output for this test driver, a Text value does not have double quote marks around it.) After reading these lines, the test driver executes the operation and tells you that it has done so; it also reports the new values of pos and x. If you want to see the new value of s1, you have to ask the test driver to print it:
1
0
Foo
pHere, "p" means "execute the Put_To operation" and "1" means to do this operation on test object s1.
1
Test Script
The test driver gets input from stdin. This gives you the option of redirecting its input from a test script file in which you have encoded your entire test plan. So the "easy" way to test is to create a file whose first line contains only an "n" -- this is the appropriate response to the first question asked by the test driver. Following that you can put into the test script file all the commands you would have had to type into the test driver if you were using it interactively. In other words, you can encode in this file your entire test plan. This will save you a lot of typing during closed lab.Although it might not be evident when you try it, the test driver simply "echoes" any line that it doesn't understand as one of the menu options when you are selecting an operation to perform. You can use this feature to put comments into your test script. For example, just before the line containing the "a" in the above example, you might put the following line into your test script:
// Test case #1: Add to empty sequence in position 0
This line of input is treated as a comment because the first character
of the line ('/') is not one of the menu options the test driver recognizes.
Such comments can help you identify where you are as you wade through the
output of the test driver, and also can help you organize and read your
test script file.
- Review the functionality of abstract template class Sequence_Kernel by consulting the Sequence appendix. Use this information to create a specification-based test plan for an implementation of Sequence_Kernel, and encode it into a test script as described below. Make sure you annotate it with comments so the grader can understand it. If you enter this test script into a file before coming to closed lab, then you'll get a jump on closed lab and you can simply turn in a printout of the file for this homework problem. An executable test driver that uses a correct implementation of Sequence_Kernel, where Item is replaced by Text, is provided for you to use:
- Study the file CT/Sequence/Kernel_3.h (also in the code section of the CSE 222 Course Packet) and make sure you understand how a Sequence object is to be represented using two Stack objects. Then design and code the bodies of the operations Add, Remove, Length, and Set_Length_Of_Before (a private operation). The body of the accessor is provided in this file as a guide, partly because this is the first time you've seen how an accessor is implemented. Review your code carefully -- with someone else in the class if you can -- and trace it on some examples, type it into a file if you want to save closed lab time, but do not try to compile it until closed lab. The objective is to have code that works the first time you compile and run it.
/class/sce/now/222/closed-labs/closed-lab04/Closed_Lab04/Sequence_Test_SampleRun it and answer "y" to the first question ("Run in interactive mode (y/n)?"). You will see what you need to type in to get it to execute each of the available operations. You also will see what output the test driver produces, and what you need to tell it in order to conduct your testing.
- Write the header for a global procedure Sort that you could use to solve this problem. If you're ambitious, write a formal specification of Sort; but in any case write at least informal requires and ensures clauses.
- Write a body for Sort using any sorting algorithm you like. There are a couple restrictions just to make it interesting, however:
- It is not acceptable to copy a Text value using the assignment operator or Copy_To. This is actually quite a rational restriction, because if you were sorting an Array of an arbitrary type Item you could not assume that Items could be copied; and in any event, there is no need to copy Items in order to sort them.
- It is not acceptable to move the Text values from the Array_Of_Text into a Queue_Of_Text, sort there using something you wrote earlier this quarter, and then move them back. In other words, no tricks to avoid solving the real problem...
- There are many implementations of Hash that might seem reasonable when the argument type is Integer, as in the example of Section 1.7.1. For example, if you don't know anything in advance about the Integer values that might be likely to be put into a Set_Kernel_13 object, then this implementation for Hash is quite reasonable:
- Write any qualitatively different implementation of Hash for this situation that might seem "reasonable" (again, without thinking in advance about the particular elements of Figure 1-12). Then show how the elements in Figure 1-12 are distributed among the buckets by this hash function.
- (Extra credit) A student once wrote a solution to part (B)
above as follows:
Forget for a moment that this might overflow, and consider instead his astute observation: for a hash table of size 10 as shown in the notes, this hash function results in at least 4 of the 10 buckets remaining empty. The reason is that there is no square whose last digit is 2, 3, 7, or 8. Prove that, for any hash table of size greater than 2, this hash function will always leave some buckets empty.{
return x * x;
}
{
return x;
}
Show how the elements in Figure 1-12 are distributed among the buckets
by this hash function.
- Explain exactly what problem this would cause; i.e., explain what problem would arise if "292-OHIO" and "292-6446" were both considered legal phone numbers and your hash function from the previous problem could be applied to both of them, and therefore you actually decided to use that hash function for both of them.
- Explain how you could change the hash function to correct this problem; i.e., explain what the hash function would have to do to handle phone numbers like "292-OHIO" and "292-6446" in a proper way.
- While you're at it, you might as well also handle smoothly the case where the phone number is typed in as "292-ohio". Explain how you could further change the hash function to handle this situation, too.
math definition HEIGHT (
t: binary tree of Item
): integer satisfies
if t = empty_tree
then HEIGHT (t) = 0
else there exists x: Item, left, right: binary tree of Item
(t = compose (x, left, right) and
HEIGHT (t) = 1 + max (HEIGHT (left), HEIGHT (right)))
Without using the Height kernel operation, provide an implementation for the following global function.
global_function Integer Height (
preserves Binary_Tree_Of_Item& t
);
/*!
ensures
Height = HEIGHT (t)
!*/
global_function Boolean Is_In_Tree (
preserves Binary_Tree_Of_Integer& t,
preserves Integer i
);
/*!
ensures
Is_In_Tree = [i is an element in t]
!*/
global_procedure Copy_It (
preserves Binary_Tree_Of_Integer& t1,
produces Binary_Tree_Of_Integer& t2
);
/*!
ensures
t1 = t2
!*/
- The empty_tree is a Fibonacci tree of order 0.
- A tree with a single item is a Fibonacci tree of order 1.
- For n > 1, a Fibonacci tree of order n consists of a root item, a left subtree that is a Fibonacci tree of order n-1, and a right subtree that is a Fibonacci tree of order n-2.
Here are some examples of Fibonacci trees. As you can see, they do
have special structure; that is, they are not just any old binary
trees.
Provide a function body for the global operation Is_Fibonacci_Tree.
global_function Boolean Is_Fibonacci_Tree (
preserves Binary_Tree_Of_Item& t,
preserves Integer n
);
/*!
requires
n >= 0
ensures
Is_Fibonacci_Tree = [t is a Fibonacci tree of order n]
!*/
math definition ARE_IN_ORDER (
s1: string of character,
s2: string of character
): boolean is
s1 <= s2
Note that "s1 <= s2" means that s1 = s2 or s1 < s2; and "s1 < s2" means -- because s1 and s2 are strings of characters -- that s1 comes before s2 in lexicographic order using the ASCII collating sequence for characters. Operationally, you can think of "s1 <= s2" as follows -- though you don't have to write code to do this because the built-in "<=" operator for Text does it for you. First, remove any common prefix of s1 and s2, calling the remaining strings s1' and s2'. Then there are four possibilities. If s1' and s2' are both empty, then s1 = s2. If s1' is empty and s2' is not empty, then s1 < s2. If s1' is not empty and s2' is empty, then s2 < s1. If s1' and s2' are both non-empty, then they differ in their first characters, and s1 < s2 iff the first character of s1' precedes the first character of s2' in the ASCII code.
Using the binary search tree algorithms discussed in class:
- Draw the binary search tree that would result from inserting the
following sequence of items into an initially empty binary search tree:
Matt, Zeke, Pete, Lon, John, Mei, Larry, Bess, Merv, Adam, Kate, Lon
- Draw the binary search tree resulting from deleting
Petefrom the binary search tree in A. - Draw the binary search tree resulting from deleting
Johnfrom the binary search tree in B. - Draw the binary search tree resulting from deleting
Lonfrom the binary search tree in C. - Draw the binary search tree resulting from deleting
Mattfrom the binary search tree in D. - Assume that t is a Binary_Tree_Of_Text. Implement
the following operation that prints the items in t in sorted
order (in this case, ARE_IN_ORDER dictates that this is according to
the ASCII collating sequence).
global_procedure Print_Sorted_Items ( preserves Binary_Tree_Of_Text& t, alters Character_OStream& outs ); /*! requires IS_BST_ORDERED (t) and outs.is_open = true ensures outs.is_open = true and out.ext_name = #outs.ext_name and outs.contents = #outs.contents * [the items in t in sorted order and separated by newlines] !*/
global_function Boolean Is_Binary_Search_Tree (
preserves Binary_Tree_Of_Integer& t
);
/*!
ensures
Is_Binary_Search_Tree = IS_BST_ORDERED (t)
!*/
The math definitions below are included for completeness and to provide you with a precise definition of the binary search tree property. Note that the implementation of Is_Binary_Search_Tree is an interesting, non-trivial task. Plan to spend some time thinking about this. Also, note that you may want/need to declare and implement some extra auxiliary operations. Finally, remember that good design (e.g., readability and maintainability) and efficiency (don't copy Items--even integers--unless it is really necessary) are important concerns in the design of good software.
math definition OCCURS_COUNT (
t: binary tree of integer,
i: integer
): integer satisfies
if t = empty_tree
then OCCURS_COUNT (t, i) = 0
else there exists root: integer
left, right: binary tree of integer
(t = compose (root, left, right) and
(if i = root
then OCCURS_COUNT (t, i) =
1 + OCCURS_COUNT (left, i) +
OCCURS_COUNT (right, i)
else OCCURS_COUNT (t, i) =
OCCURS_COUNT (left, i) +
OCCURS_COUNT (right, i)))
math definition IS_BST_ORDERED (
t: binary tree of integer
): boolean satisfies
if t = empty_tree
then IS_BST_ORDERED (t) = true
else there exists root: integer
left, right: binary tree of integer
(t = compose (root, left, right) and
IS_BST_ORDERED (t) =
IS_BST_ORDERED (left) and
IS_BST_ORDERED (right) and
for all i: integer
where (OCCURS_COUNT (left, i) > 0)
(not ARE_IN_ORDER (root, i)) and
for all i: integer
where (OCCURS_COUNT (right, i) > 0)
(ARE_IN_ORDER (root, i)))
For this week's closed lab you will, as usual, team up with a partner. If you wish, you may find a partner early and work together on this homework exercise, too. If you do this you may turn in one homework submission with both names on it and you will both receive the same grade for it.
You will be implementing two global_procedures, Get_Tree and Put_Tree, in a provided test driver. Working with your partner and before closed lab, carefully read the math definitions below and the specifications of Get_Tree and Put_Tree. Then design and code the bodies of the two procedures. Review your code carefully and trace it on some examples. The objective is to have code that works the first time you type it in (except perhaps for typos).
The math operation PREFIX_DISPLAY explains the format to be used when displaying a binary tree through the Put_Tree operation, and also explains the format to be used when typing in a binary tree for the Get_Tree operation. Here are five examples of PREFIX_DISPLAY applied to binary trees. See if you can figure out the binary trees being described.
- ()
- a(()())
- a(b(()())c(()()))
- a(()b(()()))
- a(()b(c(()())()))
(By the way, you should assume that the characters "(" and ")" do not appear as items in trees.)
/*!
math definition PREFIX_DISPLAY (
t: binary tree of character
): string of character satisfies
if t = empty_tree
then PREFIX_DISPLAY (t) = "()"
else there exists ch: character,
t0, t1: binary tree of character
(t = compose (ch, t0, t1) and
PREFIX_DISPLAY (t) = <ch> * "(" *
PREFIX_DISPLAY (t0) *
PREFIX_DISPLAY (t1) * ")")
!*/
global_procedure Put_Tree(
preserves Binary_Tree_Of_Character& t,
alters Character_OStream& outs
);
/*!
requires
outs.is_open = true
ensures
outs.is_open = true and
outs.ext_name = #outs.ext_name and
outs.content = #outs.content * PREFIX_DISPLAY (t)
!*/
global_procedure Get_Tree(
alters Text& tree_as_text,
produces Binary_Tree_Of_Character& t
);
/*!
requires
there exists t1: binary tree of character
(PREFIX_DISPLAY (t1) is prefix of tree_as_text)
ensures
#tree_as_text = PREFIX_DISPLAY (t) * tree_as_text
!*/
Section A: How Would You Have Met Lab #2's Requirements Before Taking CSE 221/222?
Suppose you had been hired -- before you took CSE 221 or CSE 222 -- to write a program meeting the basic requirements of CSE 222 Lab #2.- What programming language and/or other application development systems would you have used?
- What data structures would you have used to keep track of the terms and their definitions?
- What algorithms would you have used to accomplish the following tasks?
- Determine whether a given word is a term.
- Find the definition, given a term.
- Output the terms in alphabetical order.
Section B: How Important Are Some Ideas You Have Learned In CSE 221/222?
Briefly explain, by relating your answers to those above, how you rate the significance of each of the following concepts. Please don't try to rank them in order of importance; just say how significant you think the individual ideas are.- Component-based software construction
- Unambiguous specifications for operations
- Templates
- Partial_Map
- The paper claims that "the key feature supporting easy evolution [changes to the software] was our confidence that the modular reasoning property would hold." Briefly explain this claim -- not the claim about the technical importance of the modular reasoning property itself, but the claim about the importance of having confidence that modular reasoning could be used.
- Most experienced software developers would not change their software after testing but before delivery, fearing that any untested change could cause the system to "break". In light of this, what do you think about the decision in this project to remove checking components after development and internal testing but before product delivery? Briefly support your conclusion.
- How does the swapping paradigm differ from traditional approaches to data movement?
- Review the functionality of abstract template Stack_Kernel by consulting the client-view appendix for Stack. Use this information to create a specification-based test plan for Stack_Kernel, and encode it into a test script as you did for closed lab #4. Make sure you annotate it with comments as explained in an earlier homework problem so the grader can understand your test plan. As before, if you enter this test script into a file before coming to closed lab, then you'll get a jump on closed lab and you can simply turn in a printout of this file for this homework problem. An executable test driver that uses a correct implementation of Stack_Kernel, where Item is replaced by Text, is provided for you to play with:
- Study the file CT/Stack/Kernel_1_Part.h (also in the CSE 222 Course Packet ) and make sure you understand how a Stack object is to be represented using a linked list of nodes and "raw C++" pointers. Then design and code the bodies of the operations Push, Pop, Length, and Finalize (a private operation). Review your code carefully -- with someone else in the class if you can -- and trace it on some examples, type it into a file if you want to save closed lab time, but do not try to compile it until closed lab. The objective is to have code that works the first time you compile and run it.
/class/sce/now/222/closed-labs/closed-lab07/Closed_Lab07/Stack_Test_SampleRun it and answer "y" to the first question ("Run in interactive mode (y/n)?"). You will see what you need to type in to get it to execute each of the available operations. You also will see what output the test driver produces, and what you need to tell it in order to conduct your various test cases.
procedure Reverse () is_abstract;
/*!
ensures
self = (reverse (#self.right), reverse (#self.left))
!*/
- Write a short but convincing argument that any problem you can solve using a Queue could be solved using a List. Hint: Focus on the operations of Queue_Kernel, since anything a client program can do with a Queue must be done using only these operations.
- You should be able to convince yourself that if you are successful
in making the above argument, then you must realize how to implement
Queue_Kernel by layering it on top of List_Kernel.
This implies you wouldn't have to implement Queue_Kernel using
pointers -- which is the only Queue_Kernel implementation we've
seen to date. Here is one possible way to do this:
concrete_template < concrete_instance class Item, concrete_instance class List_Of_Item = List_Kernel_1a <Item>, concrete_instance class Rep = Representation <List_Of_Item> > class Queue_Kernel_3 : implements abstract_instance Queue_Kernel <Item>, encapsulates concrete_instance Rep { private: rep_field_name (Rep, 0, List_Of_Item, item_list); /*! correspondence self = self.item_list.left * self.item_list.right !*/ public: standard_concrete_operations (Queue_Kernel_3); procedure_body Enqueue ( consumes Item& x ) { //------ for students to fill in ------ } procedure_body Dequeue ( produces Item& x ) { //------ for students to fill in ------ } function_body Item& operator [] ( preserves Accessor_Position& current ) { //------ for students to fill in ------ } function_body Integer Length () { //------ for students to fill in ------ } };Fill in appropriate bodies for the kernel methods that respect both the representation invariant given in the convention clause (there is none, so this means that every List represents some Queue), and the abstraction relation given in the correspondence clause.
procedure Prepend (
consumes Item& x
) is_abstract;
/*!
ensures
self.left = <#x> * #self.left and
self.right = #self.right
!*/
- Draw before-and-after pictures of a List_Kernel_1 object where the original value is self = (< >, <13, 7>), and the next call is to Prepend with x = 25.
- Write the body of Prepend as if it were part of List_Kernel_1, i.e., using pointers and full access to the representation (not layered). Your implementation should execute in constant time. Hint: there are two ways to do this, one of which requires code to handle two special cases while the other is straight-line code with no "if" statements at all. See whether you can discover the second way. It requires a little "out of the box" thinking about the smart node at the beginning of the list.
- Write a Resolve/C++ version of Names_1_C++.cpp from the CSE 222 Course Packet, and call it Names_1.cpp. You can get the value of an upper-case ASCII character in lower-case by invoking the global function To_Lower on a Character value; this is similar to tolower in the normal C++ version.
- Modify your Resolve/C++ program from above, creating Names_2.cpp, to make a simple change the boss has requested: "Modify the program so that it also prints out the names in reverse order." For example, if Names_1 were given input containing the three names Ed, Fred, Ted, it would print out:
- Look carefully through the code in Stack.h from the CSE 222 Course Packet, which is a template designed in a normal C++ style. Next examine the introductory comments and code in Names_2.1_C++.cpp-bug, then Names_2.2_C++.cpp, then Names_2.3_C++.cpp, which document the musings of a (semi-experienced?) C++ programmer during successive attempts to make the same "simple" change starting with Names_1_C++.cpp. Complete the code in Names_2.4_C++.cpp (the starting point provided in this file is identical to Names_2.3_C++.cpp) and make the modified program work as the boss wanted. Look up what you need in a C++ book or consult a C++ guru if you need help.
-
Compare and contrast:
- The original normal C++ program Names_1_C++.cpp and the Resolve/C++ program Names_1.cpp.
- The revised normal C++ program Names_2.4_C++.cpp and the Resolve/C++ program Names_2.cpp.
- The changes in the code required to get from Names_1_C++.cpp to Names_2.4_C++.cpp (the normal C++ versions), vs. the changes in the code required to get from Names_1.cpp to Names_2.cpp (the Resolve/C++ versions).
If Names_2 were given the same input, it should output:Ed
ed
Fred
fred
Ted
ted
Ed
ed
Fred
fred
Ted
ted
Names in reverse order:
ted
Ted
fred
Fred
ed
Ed
Hoare, C.A.R. "Retrospective: An Axiomatic Basis for Computer Programming", Communications of the ACM 52, 10 (October 2009), 30-32. [PDF]
procedure_body Reverse ()
{
object catalyst Stack_Reverse_1 temp;
while (self.Length () > 0)
/*!
alters self, temp
maintains
reverse (temp) * self = reverse (#temp) * #self
decreases
...
!*/
{
...
}
self &= temp;
}
- Suppose Stack_Reverse_1 is instantiated with Item = Integer. Trace the code for self = <9, 6, 90, -6, 6, 18, 92, -4>, assuming that the loop invariant is correct. That is, use the loop invariant to trace over the loop without tracing any statements in the loop body.
- Complete the loop body and argue that the loop invariant in the above procedure_body Reverse is correct for your code, i.e., explain why it holds at the two places where a loop invariant must hold.
- Before writing a body for the while loop, trace this code to the end for m1 = {("May", 5), ("day", -31)} and m2 = { ("Columbus", 1492)}. Explain how the loop invariant allows you to do this.
- Write a specification for Mystery; i.e., what do you think it does?
- Write an appropriate loop body.
- Explain why the loop invariant is correct for the body you just wrote.
procedure_body Mystery (
preserves Partial_Map_Text_To_Integer& m1,
produces Partial_Map_Text_To_Integer& m2
)
{
object Partial_Map_Text_To_Integer temp;
m2.Clear ();
while (m1.Size () > 0)
/*!
alters m1, m2, temp
maintains
for all t: string of character
(if IS_DEFINED_IN (m1, t)
then not IS_DEFINED_IN (m2, t)) and
m1 union temp = #m1 union #temp and
m2 = temp
decreases
... !*/
{
...
}
temp &= m1;
}