Course Profile Computer and Information Science (ICS4M), Grade 12, University/College Preparation, Combined

Unit 3: Exploring Advanced Algorithms

Time: 22 hours

Activity 1 | Activity 2 | Activity 3 | Activity 4

Unit Description

Students explore alternative algorithms for solving problems. They examine and program solutions to problems similar to those encountered in ICS3M (e.g., binary search or factorials), using new techniques such as recursion. They also plan solutions to more complex problems using industry-standard methodology (e.g., flow charts, pseudocode, structure charts). Students apply advanced algorithms, such as a recursive sort, to develop more efficient solutions to complex programming problems. Strategies for testing and debugging of programs are developed. Students also calculate cost savings generated by using advanced algorithms as an example of using God-given resources wisely.

Unit Synopsis Chart

Activity	Time	Learning Expectations	Assessment Categories	Tasks
3.1 New Solution for Old Problems	5 hours	TFV.04, TF2.03 CGE5a	Thinking/Inquiry Knowledge/ Understanding	Group problem solving, discussion, exercises, assignment
3.2 Applying Recursion to Simple Problems	5 hours	TF1.04, SP2.06 CGE3c	Thinking/Inquiry Application	Discussion, lab exercises, assignment
3.3 Planning a Solution	6 hours	SP1.02, SP2.07 CGE2e	Application Thinking/Inquiry Communication	Group problem solving, writing algorithms, creating flowcharts and pseudocode, communicating solutions
3.4 Simple Solutions to Complex Problems	6 hours	TF1.06, SP1.07, SP1.08, SP2.10 CGE7i, 7j	Thinking/Inquiry Application	Discussion, group problem solving, assignment, unit test

Activity 1: New Solutions for Old Problems

Time: 5 hours

Description

Students examine problems that can be solved using more than one algorithm (e.g., determining the factorial value of a number). Some of these problems were solved in ICS3M using a different method. Using brainstorming or other group problem-solving techniques, students develop alternative algorithms using recursive and non-recursive techniques. Students identify the components of a recursive algorithm and develop criteria for recognizing when a recursive algorithm may be applied.

Strand(s) & Learning Expectations

Strand(s): Theory and Foundation

Overall Expectations

TFV.04 - explain the importance of program correctness and efficiency.

Specific Expectations

TF2.03 - explain how recursion can be used to solve specific kinds of computing problems.

Prior Knowledge & Skills

Students:

· can use problem-solving models and develop appropriate algorithms to solve problems;

· are able to write pseudocode.

Planning Notes

· Review the nature of recursion (see Appendix 3.1.1).

· Gather examples of problems that can be solved using more than one method, including recursion, and determine which problems may be solved using a recursive algorithm.

Teaching/Learning Strategies

· The class is divided into groups of two or three students.

· The teacher reviews the brainstorming problem-solving technique.

· The teacher presents a problem that can be solved using a familiar but complex algorithm and may also be solved using a less familiar but simpler algorithm (e.g., determining the quotient and remainder of the division of two).

· Students, in their groups, develop more than one algorithm for the solution.

· The teacher facilitates a class discussion to develop criteria for the evaluation of algorithms, including the efficiency of the solution and the complexity of the required coding. Both processing and user interface efficiencies are considered.

· Groups evaluate the algorithms using the developed criteria and share their algorithms and evaluations with the class.

· The teacher introduces the recursive method of problem solving and illustrates a recursive algorithm for the solution to a different problem (e.g., calculating the factorial value of a number).

· Groups develop a recursive algorithm to the initial problem and evaluate its efficiency.

· The teacher facilitates a class discussion to establish criteria for determining if a recursive algorithm is an appropriate solution and identifies additional problems that may be solved using recursion.

· Working in groups, students develop recursive and non-recursive algorithms for additional, assigned problems (see Appendix 3.1.2).

Assessment & Evaluation of Student Achievement

The teacher and students gather assessment information based on specific expectations, including:

· a formative assessment of the assigned in-class work in the form of roving conferences;

· a summative assessment in which students complete an assignment requiring the development of both a recursive and a non-recursive algorithm (see Appendix 3.1.3).

Accommodations

· Provide print copies of examples of algorithms using recursive and non-recursive methods, including graphic illustrations, and use models to illustrate the algorithms.

Resources

Data Structures Lecture Notes, Recursion – http://www.csi.uottawa.ca/~holte/T26/lecture3.html

The Fibonacci Series – http://library.thinkquest.org/27890/mainIndex.html

Hume, J.N. Patterson and Christine Stephenson. Introduction to Programming in Java. Toronto: Holt Software Associates Inc., 2000. ISBN 0-921598-39-4

Hume, J.N.P. and D.T. Barnard. Programming: Concepts and Paradigms. Toronto: Holt Software Associates Inc., 1997. ISBN 0-921598-27-0

Activity 2: Applying Recursion to Simple Problems

Time: 5 hours

Description

Students work in pairs to write programs, applying the algorithms developed in Activity 1. Using the criteria developed in Activity 1, students evaluate the efficiency of their programs and the appropriateness of the recursive method.

Strand(s) & Learning Expectations

Strand(s): Theory and Foundation, Skills and Processes

Specific Expectations

TF1.04 - evaluate the efficiency of different algorithms and their applicability to solving the same programming problem;

SP2.06 - use recursion in simple programs.

Prior Knowledge & Skills

Students:

· can manipulate data in one- and two-dimensional arrays;

· can incorporate user-defined functions in programs and can write subroutines that pass parameters;

· have knowledge of local and global variables.

Planning Notes

· Review the application of recursive programming techniques in the chosen programming language.

· Select examples of problems that can be solved by using recursive programming techniques.

Teaching/Learning Strategies

· Working in pairs, students program a non-recursive solution to a problem introduced in Activity 1 (e.g., finding the quotient and remainder of the division of two numbers) (see Appendix 3.2.1).

· The teacher illustrates the application of recursive programming techniques by demonstrating a simple recursive solution (e.g., finding the factorial value of a number), tracing the execution of the program to illustrate how recursion functions.

· The teacher reviews variable scope, parameter passing, and the criteria for use of user-defined functions and sub-programs.

· Students develop additional programs using the algorithms developed in Activity 1.

· The teacher facilitates a class discussion to develop criteria for evaluating the efficiency of the application of the algorithms and the efficiency of program code (see Appendix 3.2.2).

· Groups evaluate their solutions using the established criteria.

· The teacher introduces the binary search algorithm.

· Students individually complete a programming assignment requiring them to develop a recursive binary search algorithm (e.g., finding a telephone number in a list of names and telephone numbers).

Assessment & Evaluation of Student Achievement

The teacher and students gather assessment information based on specific expectations, including:

· a formative assessment of the assigned in-class work in the form of roving conferences;

· a summative assessment of the programming assignment (see Appendix 3.2.3).

Accommodations

· Provide “scaffolded” programs (i.e., incomplete program listings with subroutine headings and basic structure included) to help struggling students.

· Provide code examples that demonstrate use of recursive sub-programs and functions.

· Challenge students to attempt more complex problems.

Resources

Hume, J.N. Patterson and Christine Stephenson. Introduction to Programming in Java. Toronto: Holt Software Associates Inc., 2000. ISBN 0-921598-39-4

Hume, J.N.P. and D.T. Barnard. Programming: Concepts and Paradigms. Toronto: Holt Software Associates Inc., 1997. ISBN 0-921598-27-0

Programming with Recursions – http://erwnerve.tripod.com/recursion.htm

Recursion – http://et.nmsu.edu/~etti/winter98/computers/jenkins/jenkins.html

Activity 3: Planning a Solution

Time: 6 hours

Description

Students work in groups to analyse complex problems (e.g., Towers of Hanoi) and to develop appropriate algorithms using the recursive and non-recursive techniques examined in Activities 1 and 2. Students create flowcharts and pseudocode to assist them in planning a solution and assess these representations of code as problem-solving tools.

Strand(s) & Learning Expectations

Strand(s): Skills and Processes

Specific Expectations

SP1.02 - use industry-standard methodology (e.g., flow chart, pseudocode, structure chart) in the design process;

SP2.07 - compare effectiveness of several algorithms for solving the same problem.

Prior Knowledge & Skills

Students:

· can apply the steps in the software design life cycle;

· have used pseudocode, diagrams, and charts to summarize program design;

· can develop appropriate algorithms to solve problems.

Planning Notes

· Review the application of top-down problem solving (see Appendix 3.3.1).

· Select a problem to use in developing a model solution (see Appendices 3.3.2, 3.3.3, and 3.3.4)
and prepare the appropriate models.

Teaching & Learning Strategies

· The class is divided into groups of two or three students and each group is assigned a problem.

· Groups investigate the problem, using a variety of problem-solving techniques to analyse it.

· Each group uses brainstorming or other group problem-solving techniques to develop an algorithm for the solution to the problem. In a class discussion, groups present and share their algorithms.

· Students compare the effectiveness and efficiency of the algorithms presented and then the groups refine their algorithms.

· Each group develops a flow chart, structure chart, and/or pseudocode to represent the application of the algorithm. The teacher conferences with each group to discuss and assess the solution design.

Assessment & Evaluation of Student Achievement

The teacher and students gather assessment information based on specific expectations, including:

· a formative peer assessment of the presented algorithms (see Appendix 3.3.6);

· a formative assessment of the design for the solution to the problem (see Appendix 3.3.7).

Accommodations

· Provide print sample algorithms similar to the one studied.

· Use graphical models to illustrate the problem.

· Selectively pair/group students to assist problem solving.

· Provide problems of varying complexity to provide an appropriate challenge.

Resources

How to Draw Flowcharts – http://www.smartdraw.com/resources/centers/flowcharts/tutorial1.htm

Hume, J.N. Patterson and Christine Stephenson. Introduction to Programming in Java. Toronto: Holt Software Associates Inc., 2000. ISBN 0-921598-39-4

Hume, J.N.P. and D.T. Barnard. Programming: Concepts and Paradigms. Toronto: Holt Software Associates Inc., 1997. ISBN 0-921598-27-0

Pseudocode Guidelines – http://www.caam.rice.edu/~caam211/JZoss/pseudocode.html

Structured Pseudocode – http://mstack.cs.niu.edu/c360/spring01/notes/StruPseu.html

Activity 4: Simple Solutions to Complex Problems

Time: 6 hours

Description

Students write programs to apply the algorithms developed in Activity 3. They explore differing levels and types of errors, and develop test data and troubleshooting routines to ensure robust programs.

Strand(s) & Learning Expectations

Strand(s): Theory and Foundation, Skills and Processes

Specific Expectations

TF1.06 - explain the levels of program correctness: syntax errors, runtime errors, valid data, invalid data, robustness;

SP1.07 - ensure program correctness by developing a complete suite of test data (valid and invalid data) to eliminate syntax, runtime, and logic errors;

SP1.08 - use a problem-solving protocol to troubleshoot computer programs;

SP2.10 - perform line-by-line walkthroughs of computer programs that include all program structures.

Prior Knowledge & Skills

Students:

· can use recursion in simple programs and trace through a recursive routine;

· can apply industry-standard methodology in designing programs;

· can analyse the effectiveness of different algorithms.

Planning Notes

· Review notes on errors (see Appendix 3.4.1) and debugging/testing strategies (see Appendix 3.4.2).

· Review the software life cycle and its application to program testing and maintenance.

· Prepare programs with a number of errors for debugging purposes.

Teaching/Learning Strategies

· Students work in groups to identify the types of errors present in sample programs, including compile-time (errors of syntax or semantic), run-time, and logic errors.

· Using sample programs, students test for robustness and input validity using the black box and glass-box approaches (see Appendix 3.4.2).

· Students use debugging and tracing to review the recursive algorithms developed in Activity 2 and develop a suite of test data to test these algorithms (see Appendix 3.4.3).

· Students write the code for an algorithm developed in Activity 3 and then create a test driver subroutine or method to test their programs for robustness and input validity.

· Students individually complete an assignment (see Appendix 3.4.4) and write a unit test (see Appendix 3.4.6).

Assessment & Evaluation of Student Achievement

The teacher and students gather assessment information based on specific expectations, including:

· a formative assessment of the assigned work as students complete the programming assignment;

· a summative assessment of the programming assignment using a rubric (see Appendix 3.4.5);

· a summative unit test (see Appendix 3.4.6).

Accommodations

· Use graphical models to illustrate the example program errors.

· Challenge students to attempt more complex problems.

Resources

Hume, J.N.P. and D.T. Barnard. Programming: Concepts and Paradigms. Toronto: Holt Software Associates Inc., 1997. ISBN 0-921598-27-0

Kruse, Robert. Data Structures & Program Design. Prentice Hall PTR, 1994.

Schneider, G.M. and S.C. Bruell. Concepts in Data Structures and Software Development. Wiley, 1991.

Verifying, Testing, and Debugging – http://www.cs.und.edu/~jo/cs161/note/02/ppframe.htm

Appendix 3.1.1

An Introduction to Recursion

Recursion is not just a computer programmer’s problem-solving technique; there are many examples of recursion around us. Consider a TV camera that is focused on a scene that includes a TV monitor displaying the image recorded by the camera. The image seen on the monitor includes an image of the monitor displaying an image of the monitor and so on – that’s recursion.

We also see recursion in the “House of Mirrors” at the Fall Fair. Two flat mirrors face each other. Looking into one of the mirrors, we see our own image and that of the mirror behind us, which includes a view of our back and the mirror in front of us, which includes an image of the mirror behind, and so on.

There are recursive solutions to everyday problems as well. Faced with the chore of lifting a truckload of shingles to a rooftop, we are presented with two alternatives. Hire a crane to lift them all at once or use a recursive method consisting of:

· sub-divide the pile of shingles into groups until the shingles are divided into groups small enough to be carried – individual shingles if necessary;

· carry a group up the ladder and place it on the roof;

· climb down the ladder;

· pick up another group of shingles;

· carry it up the ladder and place it on the roof.

And so on. Continue until there are no more shingles on the ground, and it is time to carry the tools to the roof to begin installing the shingles.

For a problem to have a recursive solution it must meet the following criteria:

· There must be a way of reducing the problem to smaller, repetitive elements (e.g., dealing with the shingles one bundle at a time rather than the entire load of shingles).

· There must be a way of identifying, recognizing, and dealing with the endpoint of the solution (e.g., there are no more shingles left on the ground so carry the tools to the roof).

· There must be a way of achieving the larger result from the component elements (e.g., the end result of both methods is the entire load of shingles on the roof).

Calculating the factorial value of a number (!) is an example of a problem that may be solved recursively. The factorial value is defined as the product of all natural numbers equal to or less than the number

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

A non-recursive solution for calculating the factorial value may be achieved with a loop structure.

The problem may also be solved with a recursive solution. To satisfy the first criterion, the problem may be reduced to these repetitive elements:

7! = 7 × 6!
	6! = 6 × 5!
		5! = 5 × 4!
			And so on.

The end point of the problem (also known as the base or degenerate case) comes with the definition
that 1! = 1 and at that point the algorithm has reached its endpoint. This satisfies the second criterion.

Linking each of the smaller problems satisfies the third criterion. The solution to the base case is 1. That allows determining that the second to last case (2! = 2 × 1!) has a value of 2. This value is passed to the preceding case allowing it to have a solution of 6, and so on.

Learning to recognize when a recursive method may be applied in the solution of a problem is an important skill to a programmer.

Appendix 3.1.2

Simple Problems with Recursive and Non-Recursive Solutions.

1. Your calculator is broken and the divide button no longer works. List the steps that would be required to find the quotient and remainder for the division of two numbers using the broken calculator.

2. A geometric sequence of numbers is created from a “first term” (T1) and a “common ratio” (R). The second term is formed by multiplying the first term times the common ratio, the third term is formed by multiplying the first term times the common ratio squared, the fourth term by multiplying the first term time the cube of the common ratio and so on.

For example, if the first term is 3 and the common ratio is 2 then:

T₁=3

T₂=3×2=6

T₃=3×2²=12

T₄=3×2³=2

T₅=3×2⁴=48

And so on.

Unfortunately, your calculator doesn’t have any kind of power function, only buttons labelled +, -, ×, and / (but that one’s broken). Describe at least two methods for calculating the value of a particular term in a geometric series with this calculator.

3. The greatest common divisor is defined as the largest number that divides into two other numbers. List the steps required to determine the greatest common divisor of two given numbers.

4. In the year 1202, a mathematician by the name of Leonardo Fibonacci described a very simple series that has intrigued other mathematicians ever since. The Fibonacci series is:

1 1 2 3 5 8 13 21 34 55 …

Describe a recursive and non-recursive method of determining the value of any specified term of the Fibonacci series.

5. Develop a recursive algorithm to determine if there is a palindrome hidden within a longer word or phrase. A palindrome is a word or phrase that has the same sequence of letters when read from left to right and when read from right to left, ignoring the spaces (e.g., “Some like cake, but I prefer pie” contains the palindrome “I prefer pi”).

Appendix 3.1.3

Developing Alternative Algorithms Assignment

In 1653, a French mathematician named Blaise Pascal described a triangular arrangement of numbers that is used to determine the probability of certain events. Pascal’s Triangle is constructed as follows:

· the first row has only one element and it is 1;

· each successive row contains 2 more elements than the previous row;

· the first and last elements of each row are 1;

· the value of the remaining elements in each row are found by adding together the two elements found in the row above.

The first seven rows of Pascal’s triangle are:

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

Develop a non-recursive and a recursive algorithm for determining the value of an element in the triangle given the row and element number (e.g., given row 6 and element 5, the value to be found is 10).

Assessment Checklist

Task	Demonstrated	Comment
Solution allows for user-selected number of rows.	Y / N
Solution allows for user-selected element from the row.	Y / N
Non-Recursive Solution
Identifies the need for a two-dimensional array.	Y / N
Correctly initializes the array values appropriate for the inputted data.	Y / N
Returns the correct value for selected test data.	Y / N
Recursive Solution
Correctly identifies sub-program parameters.	Y / N
Correctly identifies the recursive sequence.	Y / N
Identifies the base case.	Y / N
Returns the correct value for selected test data.	Y / N

Appendix 3.2.1

Program Code Example
(Determining the Quotient and Remainder for the Division of Two Numbers)

Non-recursive Solution (Visual Basic)

Option explicit

Dim dividend, divisor, quotient, remainder as single

dividend = text1.text

divisor = text2.text

quotient = 0

subtotal = dividend

do

subtotal = subtotal - divisor

quotient = quotient + 1

loop until subtotal < divisor

Label1.Caption = “The quotient is ” + STR(quotient) + “ with remainder ”+STR(subtotal)

Recursive Solution

Option Explicit

Private Sub divide(dividend As Single, divisor As Single, quotient As Single, remainder As Single)

If dividend >= divisor Then

Rem subtract divisor from dividend and increment quotient

quotient = quotient + 1

dividend = dividend - divisor

call divide(dividend, divisor, quotient, remainder)

Else

Rem base case

remainder = dividend

End If

End Sub

Private Sub Command1_click()

Dim num1, num2, q , r as single

Rem divide num1 by num 2, returning the divisor and remainder

num1 = text1.text

num2 = text2.text

Call divide (num1, num2, q, r)

Label1.Caption = “The quotient is ” +STR(q) + “ with remainder ” + STR(r)

End Sub

Appendix 3.2.2

Efficient Programs

There are three aspects of efficiency in programming: 1) hardware utilization (i.e., CPU and memory usage), 2) code authoring, and 3) the user interface.

Measuring hardware utilization is relatively simple and clearly defined. We can measure the number of steps required to complete an operation. The program that requires the fewest steps is the most efficient. The number of steps required may depend on the input. In Appendix 3.2.1, for the non-recursive division algorithm, there are several steps that are required regardless of the size of the divisor or dividend (e.g., the four assignment statements). The number of times the statements within the loop are executed depends on the values for the divisor and dividend. Therefore, measuring the efficiency of this program requires determining the number of steps involved in solving the problem with a set of test data designed to test the range of possibilities. In this case, appropriate test data would include large and small values for dividend and divisor as well as cases in which the dividend and divisor are similar in value and cases in which the divisor is much smaller than the dividend.

A second aspect of efficiency considers the efficient writing of code, which is distinct from the processing issues. In fact, the most efficient program may not be the one that is most efficiently written. For example, consider a program that is to place the numbers from 1 to 100 into an array. You could write this program by writing 100 assignment statements of the form item(1)=1, item(2)=2, item(3)=3,etc. This requires 100 steps in execution. You are more likely, though, to write the program as follows:

counter = 1

DO

item(counter) = counter

counter = counter + 1

LOOP UNTIL counter > 100

From the programmer’s perspective, this is a more efficient solution. From the processor perspective, though, this program requires 401 steps in execution and is clearly less efficient! (For each iteration of the loop – 1. assign the value of the counter to the array element, 2. add 1 to the counter, 3. assign the new value of the counter, and 4. compare the counter to the exit value.) This program is also less efficient in memory usage as the value of the counter is stored as well as the required data.

Finally, the third area to consider is the efficiency of the user interface. An interface should not require the user to make repetitive data entry and should avoid the need for unnecessary keystrokes. Programs should avoid situations that require the user to move from keyboard to mouse and input screens should be designed so that data entry is optimized, taking into account a logical flow of data.

Appendix 3.2.3

Binary Search Assignment

Plan and write a program to read a list of school clubs or teams, including the name of the club and the name of the teacher/sponsor, from a data file. When the program is executed, the stored data is loaded into a two-dimensional array and sorted in alphabetic order by team name. When the user enters the name of a club, the program uses a recursive binary search to locate and display the name of the teacher/sponsor.

Marking Scheme for Binary Search Assignment

Criterion	Mark	Comment
Communication
Program header contains name, date, and title.	/2
Indentation is used properly throughout.	/2
Variables are declared appropriately and commented.	/2
Variable names are appropriate.	/2
Thinking/Inquiry
Problem is fully defined.	/2
Input and output are fully defined.	/2
Sub-program parameters are identified.	/2
Recursive sequence is identified.	/2
Base case is identified.	/2
Application
Data is correctly read from and stored in 2-D array.	/4
Data is sorted correctly by team name.	/4
User input is accepted.	/2
Binary search method returns correct value.	/2
Binary search method implements recursion correctly.	/4
The program implements modularity.	/4

Note: Zero value – criterion not attempted. Full Marks – criterion fully implemented. Partial marks according to teacher’s professional judgement of degree of implementation.

Appendix 3.3.1

Approaching a Complex Problem

Top-down programming is really top-down problem solving. It is just as effective when you are trying to solve a problem alone as when you are trying to share a solution with one or several other programmers. It is a way of looking at the problem and searching for a solution. Top-down problem solving moves from the general to the particular.

The essence of top-down programming is to take a difficult problem and simplify it to make it easier to solve. Don’t just sit in front of the keyboard and try bits of code until something starts to work. Think first. Break the overall problem into manageable segments (blocks). Plan a logical sequence of blocks and identify parts that demand more in-depth planning. When you start to code, think of all those modules as procedures. Functions occur when you find a single calculation or evaluation that must be performed repeatedly. Begin with the easy procedures, assuming that the others will work out eventually. It’s a good idea to leave the graphics and screen layout until you have the problem more or less solved. Text output is just fine until you have the problem solved.

Appendix 3.3.2

The Bumble Bee and the Honeycomb

For this challenge problem, we need to start with a plan – an algorithm. Whatever planning tool you use, the first step is not to decide the number of stripes to place on your bumblebee!

A very busy bee is crawling through a honeycomb, which consists of hexagonal cells (six equal sides) that together form a figure that is also a hexagon (i.e., the lines joining the centres of the outermost cells form a regular hexagon).

Starting at a given cell (randomly selected), the bee wanders randomly from cell to cell throughout the honeycomb. It is trying to visit every cell of the honeycomb but becomes confused and can visit a cell more than once. In one step, it moves from its present cell to any adjacent cell with equal probability. Fortunately for the bee, there are walls around the outside of the honeycomb so that it cannot fall off the outer edge.

Trace the bee’s movements from the time that it starts moving until it either visits every cell or it becomes exhausted and goes to sleep.

Conclude the program by showing: the total number of steps taken by the bee, the reason it stopped (exhaustion or it visited every cell) and a representation of the honeycomb showing the number of times that each cell was visited.

Strategies

In analysing this problem, students should come up with the following details, and possibly others.

· If the bee is in a cell at the perimeter, there could be adjacent cells on three or four sides, depending on whether the cell is at a corner or along a side.

· If the bee is in an interior cell, there are six adjacent cells.

· We need to find a way to identify all the cells and keep a record of the cells that have been visited.

· We need to keep track of the number of moves that the bee takes.

· We need to determine the number of moves available before the bee become too tired to move.

After brainstorming, students write an algorithm for the overall solution to the problem, as well as either pseudocode or a flowchart for one part of the solution. For example, if the bee is in a cell at the perimeter, there are fewer moves. Depending on which side the cell is on, the directions of the moves are different.

Appendix 3.3.3

Challenge Puzzle: Peril At Sea

Your screen represents an area at sea. Using the x-/y-co-ordinate as locations, there are 12 ships randomly scattered across the sea. You are given the speed – in nautical ‘pixelmeters’ per second – which each ship can achieve. One of the ships urgently needs a doctor. Several of the other ships have a doctor on board. There are five pieces of data for each ship:

first:	1 or 0 (1 needs a doctor);
second:	1 or 0 (1 has a doctor);
third:	X-co-ordinate;
fourth:	Y-co-ordinate;
fifth:	speed {in nautical pixelmeters per second}

You are given the first, second, and fifth pieces of data. Let the computer find the third and the fourth. Make sure no two ships are on top of each other. They aren't subs! Find the ship with a doctor that can reach the ship with the patient in the shortest time. Find the co-ordinates where the two ships will meet if they immediately move directly towards each other. Try some graphics to show your various ships and the two ships moving to meet.

There are several jobs in this problem, such as creating the grid to represent the area at sea, creating the graphics of the ships, moving the ships on the grid, and calculating the correct answers based on the information. How do you think we should approach this problem?

Strategies

In analysing the problem, students should come up with the following details, and possibly others.

· How big are the ship graphics? The x-/y-coordinates are only part of the each graphic. Should we use a function to determine if each position is permissible?

· What is the distance between any two points on the screen? Would a function be appropriate for determining this distance?

· Should we include speed in the distance calculation or do it separately after determining distance? Would it be more efficient to calculate speed starting with the nearest ship?

After brainstorming, students write an algorithm for the overall solution to the problem. As there are at least two places for functions in this problem, some students write pseudocode solutions for one function while the rest write pseudocode solutions for another. Students should then explain their solutions to other students. This is an opportunity for using communication as well as problem solving skills.

Appendix 3.3.4

A Recursive Classic – The Towers of Hanoi

The Towers of Hanoi problem is said to be based on a legend in which the monks in a monastery near Hanoi, Vietnam came into possession of 64 golden disks mounted on one of three diamond needles. The disks are in order with the smallest on top and the largest on the bottom. The task given to the monks was to try to move all the disks from one needle to another needle using the following rules.

1. Only one disk may be moved at any one time.

2. No disk may be placed on top of a smaller disk.

According to the legend, after all the disks have been moved, the universe will come to an end. If we suppose that the monks began their task 3000 years ago, and that they have been moving disks constantly at a rate of one per second ever since, calculate the approximate number of years from now to the time when the universe will supposedly end. But don’t worry about it too much.

Tracing the Development of a Complex Recursive Solution

Think of the needles as needle 1, needle 2, and needle 3. The disks are numbers 1, 2, 3 … n; 1 is the smallest and n is the largest. Move all the disks from needle 1 to needle 3, using needle 2 to help the process.

If there is only one disk on needle 1 then the problem is insignificant, simply move that disk to needle 3.

Think of a tower with two disks as a one-disk tower placed on top of a larger disk. The instructions for moving such a tower would be:

Move the one-disk tower from needle 1 to needle 2 (1 à 2).

Move the bottom disk from needle 1 to needle 3 (1 à 3).

Move the one-disk tower from needle 2 to needle 3 (2 à 3).

Similarly, think of a tower with three disks as a two-disk tower placed on top of the largest disk. The instructions for moving such a tower would be:

Move the two-disk tower from needle 1 to needle 2; adapt the previous solution (1 à 3) (1 à 2) (3 à 2).

Move the bottom disk from needle 1 to needle 3 (1 à 3).

Move the two-disk tower from needle 2 to needle 3; once again, adapt the previous solution (2 à 1)
(2 à 3) (1 à 3).

The pattern should now be clear. If there are n disks on needle 1, then think of it as a tower of n-1 placed on top of the largest disk. Before you can move disk n to needle 3, you must move disks 1 through n-1 out of the way by moving them to needle 2. Then, after you move disk n to needle 3, you must move disk 1 through n-1 from needle 2 to needle 3.

Break this pattern down into three sub-problems:

1. Move n-1 disks from needle 1 to needle 2.

2. Move n disk from needle 1 to needle 3.

3. Move n-1 disks from needle 2 to needle 3.

Sub-problem 2 is very simple because only one disk is moving. Sub-problems 1 and 3 appear to be very complex but in fact can be divided into further sub-problems until you reach a point where you are only moving one disk. But you will be doing that many times!

Appendix 3.3.4 (Continued)

Examine this recursive algorithm for solving The Towers of Hanoi problem:

If there is only one disk

then

simply move it from the first needle to the last needle

else

move n-1 disks from the first needle to the intermediate needle

move the bottom disk to the third needle

move the n-1 disks from the intermediate needle to the last needle

Using that algorithm, this is pseudocode for a method called moveTower which has three parameters:

· the height of the tower to be moved;

· the number of the needle on which the tower starts;

· the number of the needle on which the tower finishes.

procedure moveTower (height, start, finish : integer)

variable intermediate : integer // represents the intermediate needle number

if height is equal to 1

then

just move it from start to finish // exit from the method

else

· determine the location for the intermediate needle by using the fact that the sum of the values of the needle numbers is always six.

intermediate is assigned the value of 6 – ( start + finish )

move all but one disk from start to intermediate using moveTower method

moveTower (height – 1, start, intermediate )

move the bottom disk

output start , “à”, finish

move the remaining disks from intermediate to finish using moveTower method

moveTower (height-1, intermediate, finish )

end procedure

Strategies

Students should trace the algorithm and the pseudocode together. Understanding them can be difficult. By tracing the steps, students should be able to determine the number of moves for 1, 2, 3, 4, 5, and 6 disks. After, they should be able to develop a pattern and predict mathematically the number of moves for larger numbers.

Students should also look for problems in the pseudocode, such as what happens when invalid data is entered. What if you entered 0 disks or tried to use four needles? Consideration should be given to developing an efficient solution.

Appendix 3.3.5

Towers of Hanoi Java Code Sample

// The “TowersOfHanoi” class.

/*This program shows a recursive method used to solve the Towers of Hanoi problem.

It demonstrates the moving of a disk as a print statement.

It uses a global variable to record the number of moves needed*/

import java.awt.*;

import hsa.Console;

public class TowersOfHanoi

{

static Console c; // The output console

static int count; // global variable for keeping track of the number of moves

public static void main (String [] args)

{

c = new Console ();

final int DISKS = 3; // change this value to investigate any number of disks

count = 1; // initialize the count to 1

moveTower (DISKS, 1, 3);

} // main method

public static void moveTower (int height, int start, int finish)

{

if (height == 1)

{ // the is final task before exiting from the method

// move the disk from start to finish

c.println (count + ": " + start + " --> " + finish);

// increase the count each time there is output to record a move

count++;

}

else

{ // this is the recursive part of the method

// determine the location of the intermediate needle

int intermediate = 6 - (start + finish);

// move all but 1 disk from start to intermediate

moveTower (height - 1, start, intermediate);

// move the bottom disk

c.println (count + ": " + start + " --> " + finish);

// increase the count each time there is output to record a move

count++;

// move the remaining disks from intermediate to finish using recursion

moveTower (height - 1, intermediate, finish);

}

}

} // TowersOfHanoi class

Appendix 3.3.6

Peer Assessment of Group Algorithm Presentation

Group: _________________________ Assessed by: ____________________

Key Points – List four key points or steps in the algorithm.

1

2

3

4

Group Explanation – Complete this checklist.

Was the overall structure explained clearly?	Yes No
Did the explanation deal with all parts of the algorithm?	Yes No
Did the explanation explain all parts of the algorithm clearly?	Yes No
Did the explanation deal with the data being used?	Yes No
Did the explanation deal with the data clearly?	Yes No
Did all members of the group contribute to the explanation?	Yes No

Identifying Strengths of the Algorithm – List the two best aspects of this algorithm.

1

2

Identifying Problems in the Algorithm – List at least one area that you think could be a problem and should be considered.

1

2

Teacher Comments (on the quality of the assessment)

Area of Assessment	Comment
Key Points
Group Explanation
Identifying Strengths
Identifying Problems

Appendix 3.3.7

Rubric for Assessment of Problem Design

Achievement Category	Level 1 (50-59%)	Level 2 (60-60%)	Level 3 (70-79%)	Level 4 (80-100%)
Problem Definition (T/I)	- states and addresses few components of the problem	- states and addresses most components of the problem	- clearly states and addresses most components of the problem	- clearly states and addresses all or almost all components of the problem
Evidence of brainstorming (T/I)	- describes solutions that have limited effectiveness	- describes solutions that are somewhat effective	- describes solutions that are considerably effective	- describes solutions that are highly effective
Refinement of solution (T/I)	- develops few components of the solution	- develops some components of the solution	- develops most components of the solution	- fully develops selected solution
Implementation of methodology (C)	- selected methodology illustrates a few components of the solution	- selected methodology illustrates some components of the solution	- selected methodology illustrates most components of the solution	- selected methodology fully illustrates the solution
Solution of problem (A)	- solves few elements of the problem	- solves some elements of the problem	- solves most elements of the problem	- fully solves problem by the chosen solution

Note: A student whose achievement is below Level 1 (50%) has not met the expectations for this assignment or activity.

Appendix 3.4.1

Types of Errors and Run-Time Behaviour

1. Compile-time Errors

a. Syntax errors are mostly typographic errors, such as missing semi-colons, misspelled variable names, or mismatched parentheses.

b. Semantic errors (e.g., forgetting to declare/initialize variables and illegal mixing of variable types).

2. Run-time Errors: Errors that occur when program is executing (e.g., division by zero or invalid data).

3. Logic Errors: Your program compiles and runs but does not produce the correct output. These are the hardest errors to find and require that the programmer anticipate the possibility of such errors and use defensive programming to avoid them. A process called testing and debugging can detect logic errors. The goal is to have a robust program that can withstand any input.

a. Robustness

i. A robust program produces meaningful results from any data set, regardless of how improper.

ii. The results may not be correct but we should always be able to perform an operation that is useful to the user. This may be an appropriate error message or the resetting of data within allowable limits and resubmission with explanation.

iii. Under no circumstance must the program terminate abnormally.

b. Input Validation

i. Thorough validation is essential for a robust program. Data entry errors include:

· Data-entry errors by the user (hitting 7 instead of 4);

· improper ordering of the data items on a line;

· format entry errors (e.g., date value of 10/16/2002 or 16/10/2002);

The GIGO (garbage in-garbage out) principle applies.

Appendix 3.4.2

Test Drivers

The quality of the test data is more important than the quantity. Test drivers are subroutines or methods. Their only purpose is to test the program with a variety of test data. All possible cases and scenarios must be incorporated into the test data. The following must be considered when creating test data:

1. The Black-box Method: Test data is chosen according to the specifications of the problem without regard to the internal details of the program. At a minimum, the test data should include:

i. Easy values. The program should be debugged with basic data to ensure that it works. Far too often programmers select complex data only for testing.

ii. Typical, realistic values. Choose data representative of the normal program use with easy values so that results can be checked by hand.

iii. Extreme values. Programmers must assume entry beyond the limits, as it is very easy for counters or array indices to be off by one.

iv. Illegal values. Programs must take into account illegal values and provide some indication of the likely errors in input, continuing to perform calculations after disregarding the erroneous data.

Appendix 3.4.2 (Continued)

2. The Glass-box Method: All components of the program must be thoroughly tested. In this method, the logical structure of the program is examined. Test data are devised that lead to each and every alternative in each conditional case statement and at the termination of each loop. In larger programs, glass-box testing is not practical, but in smaller programs it becomes an excellent debugging tool. In larger programs, each module is tested individually, starting with the most primitive methods which are used by other methods.

Appendix 3.4.3

Debugging and Testing Strategies

Testing merely confirms the presence of errors, not the absence.

Debugging is a process of locating and correcting errors in a program. This can be a painfully slow process unless proper guidelines are followed from the outset. Studies indicate that programmers spend over half of their time finding and correcting errors. Programmers must incorporate methods to avoid these bugs and reduce the time needed to correct them.

1. Place “trace” output statements (e.g. breakpoints or variable watches) at strategic places throughout the program as you develop the code. Inserting debug statements upon entering and exiting subroutines or methods, upon entering a loop, or at other strategic places will avoid errors.

2. Write code that is as logical and readable as possible. Proper style is important but it is also critical for ensuring efficient code.

3. Understand the error completely before fixing it. Use a debugger if one is available with your programming interface. Watch carefully as an error is produced to determine the nature of the error and be able to reproduce the error if necessary. Don’t operate on the “it just worked that way” or the “my friend told me to” principle.

4. Create test drivers for both the black-box and the glass-box methods.

Appendix 3.4.4

Assignment

Using the methodology developed in Activity 3, students:

1. code a complete solution for the problem;

2. demonstrate proper debugging techniques by implementing output statements at strategic locations;

3. prepare a set of test data to properly test all conditions, using the black box and glass-box scenarios as guidelines;

4. create a test driver subroutine that runs through the test data developed in step 3.

Appendix 3.4.5

Programming Assignment Rubric

Achievement Category	Level 1 (50-59%)	Level 2 (60-60%)	Level 3 (70-79%)	Level 4 (80-100%)
Programming Style (C)	- applies few standard programming practices	- applies some standard programming practices	- applies most standard programming practices	- program conforms to standard programming practices
Program Organization (A)	- demonstrates the use of modularity to a limited degree	- demonstrates the use of modularity to some degree	- demonstrates the use of modularity to a considerable degree	- demonstrates the use of modularity to a high degree
Variables (A)	- few variables have appropriate scope	- some variables have appropriate scope	- most variables have appropriate scope	- all or almost all variables have appropriate scope
Solution of problem (A)	- produces correct output for limited test data cases	- produces correct output for some test data cases	- produces correct output for most test data cases	- produces correct output for all or almost all data cases
Processing Efficiency (T/I)	- avoids a limited number of unnecessary or repetitive processing steps	- avoids some unnecessary or repetitive processing steps	avoids most unnecessary or repetitive processing steps	- uses the minimum number of processing steps
Coding Efficiency (T/I)	- applies a non-recursive and non-efficient solution	- applies a non-recursive but efficient solution	- applies an inefficient recursive algorithm	- efficiently applies a recursive algorithm
User Interface Efficiency (T/I)	- interface requires many additional user actions	- interface requires some additional user actions	- interface requires a few additional user actions	- user interface is highly efficient
Debugging (A)	- contains statements to assist with debugging that have limited effectiveness	- contains statements to assist with debugging that are somewhat effective	- contains considerable statements to assist with debugging that are considerably effective	- contains statements to assist with debugging that are highly effective
Test Data (A)	- develops few test cases	- develops some test cases	- develops data to test most cases	- develops a complete suite of test data

Note: A student whose achievement is below Level 1 (50%) has not met the expectations for this assignment or activity.

Appendix 3.4.6

Unit Test

1. The “Decadent Search” is based on the number 10. To locate an item in a large, sorted list containing n items, the list is first divided into 10 subgroups each containing n/10 items (i.e., a list of 8742 items would be divided into 10 subgroups containing 875 items). The last group may not always contain as many items as the rest – the number of items per group is always rounded up.

The first item in each subgroup is compared to the search value to locate the subgroup containing the search item. The group containing the search value is divided into 10 subgroups, in the same way that the first groupings were formed.

The breaking of the list into 10 subgroups and searching for the correct subgroup continues until the subgroup contains less than 10 items. At that point the items in the subgroup are individually compared to the search value until the search item is located.

a) Create a flowchart to illustrate the Decadent Search. (4 marks)

b) Write pseudocode for a recursive function that implements the Decadent Search. (4 marks)

c) Describe the data that properly tests all conditions for the Decadent Search. (3 marks)

d) Use the sample data file, cities.dat, which contains the names of a large number of cities sorted by name and the population of the city. Write a program that allows the user to enter the name of a city and then displays the population of the city. Your program must use a recursive Decadent Search. (10 marks)

e) Compare the efficiency of the Decadent Search to the Binary Search. (5 marks)

2. Explain the difference between a syntax error and a runtime error and give an example of each. (4 marks)

Overview | Unit 1 | Course Profiles Main Menu