CMSC 220 Lab 5

Lab Assignment 5

CSC 220

Posted: March 3, 2005
Due: March 20, 2005

DO NOT IMMEDIATELY ATTEMPT TO PRINT THIS OUT. YOU WILL SWAMP THE PRINTERS AND WASTE PRECIOUS LAB TIME. YOU MAY OPEN MORE THAN ONE WINDOW! KEEP THIS PAGE OPEN WHILE YOU WORK.

Introduction

Control structures are used in methods to "control" the order of statement execution. This lab provides practice in using a variety of control structures including if statements, nested if statements, switch, while, for and do repetition statement. The method to be introduced later called "recursion" also provides a means of controling program flow.

Selection control statements allow for some pretty sophisticated decision making and they form the basis of artificial intelligence expert systems. In part A of this lab you will expand a very small expert system that gives advice.

Repetition statements and recursion allow tasks to be repeated again and again. Part B provides experience with designing and writing simple repetitions with a variety of constructs.

When control structures are included in methods, program flow is usually determined by the values of inputs, consequently, robust testing to ensure the reliability of the code is a problem. This lab also illustrates what it means to thoroughly and systematically test a program that contains selection structures.

This lab reinforces the repetitions constructs. It also gives you an opportunity to write a fairly complicated solution with a partner.

Objectives of the Lab:

This lab introduces

the distinction between an application that tests a solution, and one that receives input from the user.
the notion of program efficiency: how long will a coded solution take
the notion of trade-offs between efficiency and human readability

This lab gives you practice in the following:

writing if else statements
writing switch statements
analyzing the problem statement to simplify the need for selection statements
defining the space of possible results, and testing that space
give you experience using various repetition statements
give you experience defining the state that exists before, during and after a repetition statement
require you to develop solutions without sample programs
give you practice using the software development method to construct a complicated algorithm involving selection and repetition statements.

Background

Selection Structures:

Selection statements can be used whenever you want to make a choice. In this lab we will model a small "expert system" in which advice is given based on some input.

To find good solutions for these problems you must select a structure that meets your needs. If statements can take on the following kinds of structure.

Flat lists.
Cascading elses
Decision trees

The solution may also lend itself to a switch statement which is discussed in your text.

So far the programs you have written have been rather easy to test. You gave a few input examples via a user interface and then verified that the results were correct. In the graphics programs you could see whether your output looked as you intended. In more complex programs, especially those involving selection statements it is absolutely necessary to confirm that all paths lead to the expected output. This is often extremely time consuming.

There are two places where error can be introduced. During design and analysis you can make a mistake in your logic. During implementation you can make a mistake in translating your logic to code. Consequently it is important to be systematic. Take care in developing a solution long before you begin to implement code. Then, when the code compiles, thoroughly test it. Download the class ActivityExpert from ActivityExpert.java that shows the result of the design phase within a comment. It also contains two methods, testRules() and userInput() that illustrate the difference between thorough testing and getting user input.

Repetition Structures

Doing repetitive tasks in a program involves identifying the following:

The start state, controlled by the initialization statement
The end state, controlled by the repetition condition
The state update, controlled by the update statement
The repetitive process within the body

Java has four ways of doing repetitive tasks, we will study three of them in this lab:

while:

// start state defined before the while statement
while (repetition condition)
{body; update statement;}
for

for (initialization statement;repetition condition; update statement )
{body}
do

// start state defined before do statement
do {body; update statement}
while (repetition condition)
The technique "recursion" which is defined in terms of selection statement that distinguishes the base case from the recursive case (to be covered later)

The Task:

PART A:

Step 1: Study the code in ActivityExpert.java. Analyze the efficiency of each alternative as follows: How many statements must be executed in the worst case. Recall from the class discussion that the worst case is the one that will take the longest. Make sure you identify the worst case. Which solution do you think is the most efficient? Which is the easiest to read?

Step 2: Attempt to write a switch statement to model the expert system in ActivityExpert. Can you do it? How much easier/harder is the switch than the various if/else statements? Characterize the type of problem that the expert system is. Does this kind of problem lend itself to a switch statement? Why or why not?

Step 3: Add another predicate to the ActivityExpert. For example, include an option to determine whether you are caught up at work. Add corresponding consequences. Choose one of the four implementations above (flat list, cascading list, decision tree, switch) and augment the code to include your new predicate. Modify the ActivityExpert testing methods (testRules() and userInput() ) to test your new code.

PART B: (There are two parts)

Part B1:

Assign labels "A" and "B" to each member of a pair. If you are a group of three, then assign a tag "C" and make sure each partner experiences each of the repetitive techniques three times. Four problems are listed below. Each partner is to do each problem using the technique assigned.:

Problem	Partner A	Partner B
1	"while" and "for"	"do" and "while"
2	"for" and "do"	"for" and "while"
3	"do" and "while"	"do" and "for"
4	"for" and "while"	"while" and "do"

Problem 1: Write a function that sums the integers from n to m .. This exercise should suggest a "closed form", a simple formula that solves this problem. Do NOT write the solution using the closed form, instead do the sequence of calculations in your solution. Use your solution to explain why the closed form is correct (e.g. an "informal" inductive proof).

Problem 2: Write a function that sums n ODD numbers beginning at m. Warning this problem has a different input specification than 1.1. Again this exercise should suggest a closed form solution. Find it, and prove it is correct.

Problem 3: Write a function that sums n EVEN numbers beginning at m. Is there a closed form? If so, prove it is correct.

Problem 4: Write a function that multiples n integers beginning at m.

You should write all of your methods within one class, and then use another class to test demonstrate a test run that does a reasonable test on all functions.

Summary analysis for part 1:

Answer these questions in the summary of this part of the lab:

The problems above all have the same characteristic input. Explain what numbers you used to test your methods. HINT: you will need more than a single test case for each method, but you should be able to apply the same test cases to each method.
These three problems do essentially the same kind of task with one hitch. Comment on which statement type was most useful for doing each task. You will have to compare results with your partner. Which was most difficult. Did the input specification impact your choice? What if all four problems had been written with the input specification of the first problem vs. the second?
Intuitively it makes sense that if there is a simple math formula (closed form), then use it. But does it? For each of the problems above, calculate the cost of computation with the following constraints:

Version 1: Evaluation of a condition costs 100 times what it costs to do arithmetic (plus, times etc.)
Version 2: Evaluation of arithmetic costs 100 times what it costs to evaluate a condition.

To get a handle on this problem, start by calculating the cost of doing each problem above where 10 numbers will be summed. Extrapolate to 100 numbers, then to 1000 numbers, and then generalize to n numbers. For each version, which do you think is best: doing the closed form or doing the series? Give a GOOD explanation (bordering on formal proof).

Part B2:

Write a program that displays a calendar for a year. Your input should be the day of the week on which January 1 falls and whether the year is a leap year.

You and your partner should design this solution with great care. Although not required, you may submit a design before beginning to implement. Obviously this will probably help you a great deal. DO NOT simply start to program this one. You will waste a lot of time. Do not initially get bogged down in fancy display. Simply use a String object to get the entire calendar into and the JOptionPane method "showMessageDialog" to print the calendar in the history window.

OPTIONAL: have some fun with this one. Use the graphics primitives you have learned to display a more interesting calendar. For this part of the lab, let your imagination roam a bit. Use on line resources to find JAVA graphics primitives to control font type, style and size. Make the calendar a "work" calendar, with the weekend diminished. Better yet, make it a weekend calendar, with the week diminished. Or try printing it in a non-traditional form.

REQUIREMENTS

Work on this assignment with a partner. Submit one lab report per pair, however each person must be prepared to demonstrate and discuss the code in a lab session following the due date. You may choose how to divide the work. For example, you may work together on all parts, one may write the expert system, the other the testing code. I suggest that at the analysis stage, each of you, individually work through the solution and compare results.

In this lab you are required to produce a lab report and to arrange for a demo of your solutions.

Demo:

Be organized when you are ready to demonstrate your lab to your professor. For each step for both Labs 4a and 4b, first demonstrate a testing run, then demonstrate a user input run, then s the code. Both members of the team should be prepared to explain any of the code, regardless of who wrote what.

The code you write should include:

A clearly defined header identifying
- the programmers
- the course
- the date
- and the lab assignment
Clearly commented code

Lab report:

The lab report should be produced on a word processor. Do not use a report cover. The lab report should include in order:

a cover page identifying the programmers
for each step in Parts 1 and 2 above
- the statement of the task (don't just cut and paste the instructions, summarize them.)
- an analysis section that shows how you designed the implementation(s) (you do not need to belabor this, simply show that some work went into design and analysis BEFORE implementation)
- The code, clearly documented
- clearly state where the code may be accessed e.g. ~studentName/Lab4/Step1
- include any discussion relevant to the questions that appear in the steps above.

a general summary stating
- what you found easy about this lab
- what you found difficult about this lab
- if you worked as a team, who did what, and whether collaboration helped or hindered your work

Hints and Other Advice:

Sketch out the solutions on paper using the analysis methods presented in class. This will save you a LOT of work debugging your implementation.

ASK!!!!!!! questions, in class, in lab, during office hours and especially via the class newsgroup. Please do not phone.

You may get help from classmates, tutors and other students outside your team on system technicals, syntax bugs, and small issues related to the Java language.

You may NOT get help from the above groups to develop the solution or to initially implement your code. If you cannot get to the stage of implementing Java code, please see me during lab, send email or visit during my office hours.

A "down" system on the morning the lab is due will not cause an extension of the due date. Other universal calamities may be negotiated with the entire class. The point: hand SOMETHING of worth (e.g. the first few steps) in by the due date.

What if your lab partner has vanished? Find another. At this stage of the game you should have your lab partner's email address and phone. Whenever you work together, each of you should keep a copy of the results. If you are not sure of the mechanics of copying files etc. ASK!!