Transcript ppt - Chair of Software Engineering

1
Introduction to Programming
Exercise Session Week 10
M. Piccioni
24/25 November 2008
Chair of Software Engineering
Announcement
In two weeks (December 9th)...
Mock exam 2
Chair of Software Engineering
2
Featuring today
Genericity
Recursion
 Recursion

Recursion

Recursion

Recursion

Recursion
and Trees!
Chair of Software Engineering
3
Genericity: Type parametrization
Type parameterization
LIST_OF_
PEOPLE
Type parameterization
LIST_OF_
ANIMALS
LIST_OF_
CARS
Chair of Software Engineering
4
Genericity - why?

To parametrize a class, abstracting away all the
operations in common

A single class text may be reused for many different
objects types.

To provide an implementation of type safe containers

Helps avoiding objects-test/assignment attempt
Chair of Software Engineering
5
A Generic List
class LINKED_LIST[G]
feature
Generic parameter
item: G
-- the element cursor is pointing at
do ... end
append(value: G)
-- append a value to the list
do ... end
end
G will be replaced by the compiler with the needed
type that has to be specified at some point.
Chair of Software Engineering
6
A “natural” example
class ANIMAL
create
make
feature -- Initialization
make (a_genus: STRING)
do
genus := a_genus
end
feature -- Status
genus: STRING
...
end
7
Chair of Software Engineering
Type safe Containers
x: ANIMAL
animal_list: LINKED_LIST [ANIMAL]
a_rock: MINERAL
animal_list.put(a_rock) -- does this rock?
the animals:
animal_list.start
from ____________________
animal_list.after _______________
until__________________
loop
animal_list.item
x := _____________
print(x.genus)
animal_list.forth
________________
end
Chair of Software Engineering
8
A Constrained Generic List
note: “Storage for resources”
class STORAGE [G ->RESOURCE] inherit LIST[G]
consume_all
do
Constrained generic
from start until after loop
parameter
item.consume
forth
item is checked for
conformance with
end
RESOURCE
end
-- client code
...
sf: STORAGE [FISH]
end
sg: STORAGE [GRAIN]
Chair of Software Engineering
9
The Waldgarten Project
We need to associate each plant in the
same category (categories are trees, bushes,
herbs and mosses) to a unique id.
Suggest one or more classes for the specified
context.
Chair of Software Engineering
10
Yes, we can (constrain)
class PLANT
...
species: STRING
...
end
Usage:
herbs: HASH_TABLE [HERB, STRING]
bushes: HASH_TABLE [BUSH, STRING]
...
herbs.add(myherb, myherb.species)
Chair of Software Engineering
11
Today
 Recursion
Chair of Software Engineering
12
Thoughts
Better use iterative approach if reasonable
Chair of Software Engineering
13
Iteration vs. Recursion
 Every recursion could be rewritten as an iteration
and vice versa.
 BUT, depending on how the problem is formulated,
this can be difficult or might not give you a
performance improvement
Chair of Software Engineering
14
Recursion warm-up exercise 1
If we pass n=4, how many numbers will be
printed and in which order?
print_int (n: INTEGER)
do
print (n)
if n>1 then
print_int (n-1)
end
end
Chair of Software Engineering
15
Recursion warm-up exercise 2
If we pass n=4, how many numbers will be
printed and in which order?
print_int (n: INTEGER)
do
if n>1 then
print_int (n-1)
end
print (n)
end
Chair of Software Engineering
16
Recursion exercise 3
Print a given string
in reverse order
using a recursive function
Chair of Software Engineering
17
Sequences and Recursion
Write a recursive and an iterative program to print the
following:
111,112,113,121,122,123,131,132,133,
211,212,213,221,222,223,231,232,233,
311,312,313,321,322,323,331,332,333.
Chair of Software Engineering
18
Magic Squares
 The sums in every row and column is constant
 Numbers are all different
4
3
8
9
5
1
2
7
6
Chair of Software Engineering
19
Magic Squares and Permutations
 Finding a magic square 3x3 is related to finding the
permutations of 1 to 9
123456789
123456798
123456879
123456897
123456978
123456987
...
987654321
There exist 72 magic 9x9
squares (8 of which distinct)
Chair of Software Engineering
20
Find the Magic Squares
Write a program that finds all the eight
9x9 magic squares.
Hint 1: Refactor the previous recursive algorithm
applying it to permutations (enforce no repetitions)
Hint 2: Use two arrays of 9 elements, one for the
current permutation and one to know if a number has
already been used or not
Hint 3: If you are desperate, have a look at the posted
solution with the debugger
Chair of Software Engineering
21
Going backwards pays off
 When the program finds, at the 9th recursion, that a
square is not magical, it goes back on the call stack
to the previous instance of the function, and even
more back if needed.
 This technique is called BackTracking and is used in
many recursive programs.
Chair of Software Engineering
22
Data structures
You have seen several data structures

ARRAY, LINKED_LIST, HASH_TABLE, …
We will now look at another data structure

(Binary) tree and its recursive traversal
Chair of Software Engineering
23
Tree
Chair of Software Engineering
24
Tree
Chair of Software Engineering
25
Tree – in a more abstract way
Node
Tree:
“ROOT”
“LEAF”
 One root
 Typically several leaves
Chair of Software Engineering
26
Binary Tree
Node
“ROOT”
“LEAF”
Binary tree:
 One root
 Typically several leaves
 Each node can have at most 2 children (possibly 0 or 1)
Chair of Software Engineering
27
Recursive traversal of a binary tree
 Implement class NODE with an INTEGER attribute
 In NODE implement a recursive feature that traverses
the tree and prints out the INTEGER value of each
NODE object
 Test your code by class APPLICATION which builds a
binary tree and calls the traversal feature
Chair of Software Engineering
28
Binary Search Tree
10
8
4
“ROOT”
13
9
20
“LEAF”
Binary search tree:
 Binary tree where each node has a COMPARABLE value
 Left sub-tree of a node contains only values less than the
node’s value
 Right sub-tree of a node contains only values greater
than or equal to the node’s value
Chair of Software Engineering
29
Creating a binary search tree
 Implement command put (n: INTEGER) in class NODE
which creates and links a new NODE object at the
right place in the binary search tree rooted by Current
 Test your code by class APPLICATION which builds a
binary search tree using put and prints out the values
using the traversal feature
 Hint: you might need to adapt the traversal feature
such that the values are printed out in order
Chair of Software Engineering
30
Questions?
Chair of Software Engineering
31
Backup slides
Chair of Software Engineering
32
Searching in a binary search tree
 Implement feature has(n: INTEGER): BOOLEAN
in class NODE which returns true if and only if n is in
the tree rooted by Current
 Test your code by class APPLICATION which builds a
binary search tree and calls has
Chair of Software Engineering
33