Stepwise Refinement and Algorithmic Abstractions

The assignment is for Algorithms and Data Structures I, and it requires students to demonstrate understanding of stepwise refinement and its application to solve a set of problems. The assignment consists of three tasks: the first task involves finding the truth table of a proposition using stepwise refinement, the second task involves writing an algorithm in ADL notation that implements the mysterious function, and the third task involves calculating permutations when repetition is allowed or not allowed.

55-4793 Algorithms and Data Structures I
Referral Assignment 1
(Individual Work)
As indicated in the module description, the learning outcomes for this unit are that
the student should be able to:
1. describe the importance of algorithms;
2. explain the concept of algorithms and their use to manipulate data;
3. describe fundamental data structures in an appropriate notation;
4. describe algorithms in an appropriate abstract notation;
5. implement algorithms and data structures using a suitable language.
Accordingly, for this assignment, you are required to demonstrate understanding
of a problem solving technique called stepwise refinement and its application to
solve a set of problems. Hence, this assignment directly addresses learning
outcomes 1, 2 and 4.
This module is assessed on a 100% coursework basis. This assignment
represents 50 of the (100) total coursework marks available in this
module.
For this assignment you should be working individually.
HAND-IN Date
Refer to Blackboard
Please ensure that your work is handed in to Cantor reception on or before the
deadline. Make sure that you write my name on the assignment form before you
hand your assignment to reception as I will be marking your assignment report.
1 of 4

SPECIFIC TASKS
1. Consider the proposition and complete the following tasks associated with
it:
(p  q) → (p  q), where p and q are statements (or verbal assertions).
i. find the truth table of the proposition;
(4 marks)
ii. explain how the stepwise refinement technique can be applied to find
the truth table and briefly discuss the benefits of this approach;
(6 marks)
iii. Assume that there are two procedural abstractions that calculate
conjunction and disjunction of given two truth values. They are as
follows:
procedure and(IN p, IN q, OUT result)
procedure or(IN p, IN q, OUT result)
, where p and q represent Boolean values (i.e. T or F) and result
represents the outcome (i.e. T or F). For example, to calculate outcome
 p  q you can write the following step in ADL (Algorithmic Definition
Language taught in lectures), using the CALL statement:
CALL and(p, q, outcome)
Assume further that there is a procedural abstraction that negates the
truth value of a given truth value. It is as follows:
procedure not(IN p, OUT result), where p represents a Boolean
value (i.e. T or F) and result represents the outcome (i.e. T or F).
(a) Using the above abstractions write a simple algorithm using the
ADL notation that inputs p and q, and displays the outcome of the
above proposition. Explain your problem solving strategy.
(20 marks)
(b) Discuss the suitability of using procedural abstractions to solve this
problem and suggest an alternative abstraction mechanism for this
problem, and illustrate it.
(5 marks)
2 of 4

2. Consider the following algorithm written in ADL:
procedure mysterious(IN number, OUT result, OUT status)
declare i, number1, number2, sum
status  true
if number < 0 then [status  false]
else
if number = 0 then [result  0]
else
if number = 1 then [result  1]
else
[number2  0
number1  1
for i  2 to number do
sum  number1 + number2
number2  number1
number1  sum
end
result  sum
]
endif
endif
endif
end // mysterious
Using this algorithm, you are required to complete the following tasks:
i. pretend to be a processor and execute the above algorithm by using the
code walkthrough technique taught in lectures. Devise your own test
data for this purpose, and explain what this algorithm does.
(18 marks)
ii. write an algorithm that represents an application of the above algorithm
in ADL. This algorithm is typically required to accept a number from
users and outputs the outcome after 'mysterious' has been invoked.
(12 marks)
3. Permutations
"In mathematics, the notion of permutation is used with several slightly
different meanings, all related to the act of permuting (rearranging) objects
or values."1
"There are basically two types of permutation:
1. Repetition is allowed: such as a luggage lock, which could be '333'.
2. No repetition is allowed: for example the first three people in a
running race. You can't be first and second."2
1 Wikipedia (http://en.wikipedia.org/wiki/Binomial_coefficient)
2 http://www.mathsisfun.com/combinatorics/combinations-permutations.html
3 of 4

i. Using the definitions of the two types of permutations explained in
footnote 2, write an algorithm as a suitable abstraction in ADL that
calculates the number of permutations of a given number when
repetition is allowed.
(10 marks)
ii. Using the definitions of the two types of permutations explained in
footnote 2, write an algorithm as a suitable abstraction in ADL that
calculates the number of permutations of a given number when
repetition is not allowed. Explain your problem solving strategy while
devising the algorithms
(25 marks)
Dr MB Özcan
4 of 4