-
middle age
algiros + arithmus
( painful ) ( number )
- algorithmus infinitesimals
-
Given positive integers m, n, find the GCD ( greatest common divisor )
(i.e. largest integer that divides m and n )
Definitions:
An algorithm is a finite set of rules, which gives a sequence of operations for solving a specific problem and satisfies the following criteria:
- Finiteness
- terminate in finite time
- Definiteness
- each step must be precisely defined
- Input
- zero or more inputs
- Output
- one or more outputs
- Effectiveness
- in principle, each step should be able to be traced by
humans
-
2 x 3, 4 x 5, 6 x 7, ...
( 2, 3 ) is an instance of the problem
To show that an algorithm is incorrect, we need only find one instance of the problem for which it gives a wrong answer
e.g. int elements: { 0, +1, -1, +2, -2, ..., INT_MAX, INT_MIN }
operators: + - * / %
- Defined by its interface, not its internal structure or implementation
- Same ADT can have different implementation at different times without affecting the code that uses it
- In C++, classes are used for data abstraction by hiding the implementation of a type in the private part of the class definition and provide an interface of publicly accessible operations
|
Problem Statment |
|
ADT |
|
Implemented Program ( depends on language ) |
Example: The card game war
|
|
|
|
|
|
|
|||||||||||||
| Player A | Player B | ||||||||||||||||||
|
|
- Player A and B each draws 3 cards ( a hand )
- A and B each randomly picks a card from her hand
- Compares the two cards to see which is larger; winner scores a point
- A and B each draws a card from the deck to replace the picked one
- Repeat 2 - 4 until the deck is empty
Need a few classes :
class Card
- Reflect the properties of a real card
class Deck
- must maintain a collection of cards
- must be able to shuffle the cards it has
- must be able to tell the user if its empty
- the user of the deck must be able to draw a card
class Player
must
- ability to hold a hand of 3 cards
- randomly draws one from three to play
- replace the drawn card
preferable
- remember her own score
- add a point to her score
//card.h
#ifndef CARD_H
#define CARD_H
#include <iostream.h>
enum suits { diamond, club, heart, spade};
class Card {
public:
//constructors
Card();
Card( suits, int );
//data fields
int rank; //rank of card
suits suit; //suit of card
};
ostream & operator << ( ostream &out, Card c );
#endif
|
//card.cpp
#include "card.h"
Card::Card()
//default
{
rank = 1;
suit = spade;
}
Card::Card( suits s, int r )
{
rank = r;
suit = s;
}
//suit_oper.cpp
#include "card.h"
#include <iostream.h>
ostream & operator << ( ostream &out, Card c )
{
//first output rank
switch ( c.rank ) {
case 1: out << "Ace"; break;
case 11: out << "Jack"; break;
case 12: out << "Queen"; break;
case 13: out << "King"; break;
default:
out << c.rank; break;
}
//then output suit
switch( c.suit ) {
case diamond: out << " of Diamonds"; break;
case spade: out << " of Spadess"; break;
case heart: out << " of Heartss"; break;
case club: out << " of Clubs"; break;
}
return out;
}
|
//deck.h
#ifndef DECK_H
#define DECK_H
#include "card.h"
class Deck {
public:
//constructor
Deck();
//operations on a deck
void shuffle();
bool isEmpty();
Card draw(); //return the next card
protected:
Card cards[52]; //hold collection of cards
int topCard; //points to top card in deck
};
class randomInteger {
public:
unsigned int operator () ( unsigned int );
};
#endif
|
#include "deck.h"
#include <algorithm>
#include <math.h>
unsigned int randomInteger::operator () ( unsigned int max )
{
unsigned int r = rand();
return r % max;
}
Deck::Deck()
{
topCard = -1; //deck empty
for ( int i = 1; i <= 13; i++ )
{
Card c1(diamond, i ), c2( spade, i), c3( heart, i ), c4( club, i );
cards[++topCard] = c1;
cards[++topCard] = c2;
cards[++topCard] = c3;
cards[++topCard] = c4;
}
}
randomInteger randomizer; //global variable
void Deck::shuffle()
//randomly shuffle cards array, using generic algorithm random_shuffle
{
random_shuffle( cards, cards+52, randomizer );
}
Card Deck::draw()
//return topCard
{
if ( !isEmpty() )
return cards[topCard--];
else{
Card specialCard( spade, 14 );
return specialCard;
}
}
bool Deck::isEmpty()
{
return topCard < 0;
}
|
| cards | cards+1 | cards+50 | cards+51 | cards+52 | |||||
| ↓ | ↓ | ↓ | ↓ | ↓ | |||||
|
|
... |
|
|
random_shuffle() -- generic algorithm
#include <algorithm>
randomizer -- function objects :
Advantages:
- more resilient to design changes because the object can be modified internally without changing its external interface
- can have data members that store the result of a previous call ( rather than using static or global variables )
- compilers can inline a call made through a function object, thereby enhancing performance
//player.h
#ifndef PLAYER_H
#define PLAYER_H
class Player {
public:
Player ( Deck & );
Card draw();
void addPoints ( int );
int score();
void replaceCard( Deck & );
protected:
Card myCards[3]; //player holds three cards and randomly draw one
int myScore;
int removedCard;
};
#endif
|
//player.cpp
#include "deck.h"
#include "player.h"
Player::Player( Deck &aDeck )
{
myScore = 0;
for ( int i = 0; i < 3; i++ )
myCards[i] = aDeck.draw();
removedCard = 0;
}
extern randomInteger randomizer;
Card Player::draw()
{
removedCard = randomizer( 3 );
return myCards[removedCard];
}
void Player::addPoints( int npoints )
{
myScore += npoints;
}
int Player::score()
{
return myScore;
}
void Player::replaceCard( Deck &aDeck )
{
myCards[removedCard] = aDeck.draw();
}
|
//game.cpp
#include "card.h"
#include "deck.h"
#include "player.h"
#include <iostream.h>
void main()
{
//create and shuffle deck
Deck theDeck;
theDeck.shuffle();
//create 2 players
Player p1( theDeck );
Player p2( theDeck );
//play until deck empty
while ( !theDeck.isEmpty() ) {
Card c1 = p1.draw();
cout << "Player 1 plays " << c1 << endl;
Card c2 = p2.draw();
cout << "Player 2 plays " << c2 << endl;
if ( c1.rank == c2.rank ) { //tie
p1.addPoints( 1 );
p2.addPoints( 1 );
cout << "Players tie" << endl;
} else if ( c1.rank > c2.rank ) {
p1.addPoints( 2 );
cout << "Player 1 wins round " << endl;
} else { //player 2 wins
p2.addPoints( 2 );
cout << "Player 2 wins round " << endl;
}
//replace cards drawn
p1.replaceCard( theDeck );
p2.replaceCard( theDeck );
} //while
cout << "Total score for Player 1 : " << p1.score() << endl;
cout << "Total score for Player 2 : " << p2.score() << endl;
}
|
#Makefile for suit EXEC=game SRCS=card.cpp deck.cpp player.cpp game.cpp suit_oper.cpp OBJS=$(SRCS:.cpp=.o) $(EXEC): $(OBJS) g++ -o $@ $(OBJS) #$< evaluates to the target's dependencies, #$@ evaluates to the target $(OBJS): g++ -c $*.cpp clean: rm $(OBJS) |
Accessor and mutator functions
-
t1 ( n ) = n + 3
t1 &isin O(n) linear time
t2 ( n ) = 5n2 + 2n
t2 &isin O(n2) quadratic time
constant time O(1)
Examples:
int sum ( int n )
{
int s = 0;
for ( int i = 0; i < n; ++i )
s += i; O(n)
return s;
}
x = 9; O(1)
s = 0;
for ( int i = 0; i < n; ++i )
for ( int j = 0; j < n; ++j )
s = s + j; O(n2)
O ( 1 ) O ( log n ) O ( n ) O ( n2 ) polynomial time O ( n3 ) . . . O( 2n ) exponential time ( hard )Example:
Recursive Algorithm ( complexity can be found by solving characteristic equations )
- From 2., we move all n - 1 rings from A to C with help from B
- Move last ring to B ( A → B )
- Move n - 1 rings from C to B with help from A
Use top-down approach ( divide-and-conquer )
Towers of hanoi:
A
|
B
|
C
|
|
Move all rings from tower A to B with help from C. Smaller rings need to be
on top of larger rings all the time.
Solve by Mathematical induction Consider n rings
n = 2 |
||
A
|
B
|
C
|
|
A → C A → B B → C |
||
3. Consider n rings.
|
A
|
B
|
C
|
|
A
|
B
|
C
|
|
A → C ( n - 1 rings ) A → B ( last ring ) B → C ( n - 1 rings ) |
||
void hanoi ( int n, char A, char B, char C )
{
hanoi ( n - 1, A, C, B );
cout << A << " --> " << B << endl;
hanoi ( n - 1, C, B, A );
}
|
Need an exit case!
void hanoi ( int n, char A, char B, char C )
{
if ( n <= 0 )
return;
else {
hanoi ( n - 1, A, C, B );
cout << A << " --> " << B << endl;
hanoi ( n - 1, C, B, A );
}
}
|
increase the confidence in the correctness of their algorithms
a major tool ~ invariant:
Example:
- 1 if equilateral triangle
- 2 if isoceles
- 3 if no sides equal
int triangle ( int a, int b, int c )
{
if ( a == b ) {
if ( b == c ) {
//inv: a equals b, b equals c
return 1; // so a equals c, and all sides equal
} else { //inv: a equals b, but b ≠ c
return 2; // so two sides are equal
}
} else { //inv: a ≠ b
if ( b == c ) { //inv: a not equal b, but b equal c
return 2; // so 2 sides equal
} else { //inv: a ≠ b, b ≠ c
return 3; // so no sides are equal ( ? )
}
}
}
|
invariants should not be assumed to be true until proved by argument.
Loop invariants -- a quantity whose value does not vary in the loop iterations
Example: Converting decimal to binary
/*
input: a decimal integer n
output: binary representation of n with k digits: b[k-1]....b[1]b[0]
*/
void d2b( int n, int b[] )
{
int i = 0;
int x = n;
while ( x != 0 ) {
b[i] = x % 2;
x = x / 2;
++i;
}
}
|
loop invariant
At the beginning, i = 0, x = n, b = 0
Assume that (H) is true at the end of the j-th loop ( i.e. i = j )
= n
Consider the end of (j+1)-th loop ( i.e. i = j + 1 )
(i) xj is even ( b[j] = xj % 2 ) == 0 xj+1 = xj / 2 = [xj / 2] Ij+1 =xj+1 * 2j+1 + b[j]b[j-1]...b[0] = ( xj/2 ) * 2j+1 + b[j-1]...b[0] = xj * 2j + b[j-1]...b[0] = Ij = n by ( 1 ) (ii) xj is odd ( b[j] = xj % 2 ) == 1 xj+1 = xj / 2 = (xj - 1)/ 2 Ij+1 =xj+1 * 2j+1 + b[j]b[j-1]...b[0] = ((xj - 1)/2 ) * 2j+1 + 2j + b[j-1]...b[0] = xj * 2j - 2j + 2j + b[j-1]...b[0] = xj * 2j + b[j-1]...b[0] = Ij = n by ( 1 )Thus, ( H ) is true for i = j + 1
and we can conclude that it is always true!Upon exiting the loop
x = 0 n = I = 0 * 2k + b[k-1] .... b[0] = b[k-1] .... b[0]
Therefore, b[k-1] .... b[0] is the binary representation of n.
Asserting Outcome is correct
assert the conditions corresponding to the desired outcome
bool isPrime ( unsigned int n ) //returns true if n is prime and false otherwise { for ( int i = 2; i * i <= n; i++ ) { //invariant 1 : n has no factors between 2 and i - 1 if ( 0 == n % i ) { //invar. 2 : i divides n, thus n is not prime return false; } //invar 3 : n has no factors between 2 and i } //invar. 4 : n has no factors between 2 and n½ // thus number must be prime return true; }
- Program Testing
Testing can, and should be performed at all levels:
- individual functions or methods can be tested as they are written
- a class can be tested in isolation
- a complete program can be tested as an application
- driver code ~ calling procedure
- stub code ~ simulates the action of any procedures that may be called by the algorithm under test
- every statement needs to be executed
- if, while -- test both true, false
- if-else -- test all branches
- switch -- test all cases
- if there is a minimal legal input value, use this as one of the test case
- test legal, illegal inputs
- loop -- try zero times, nozero times