THE PROBLEM SOLVING PROCESS - McMaster University



THE PROBLEM SOLVING PROCESS

DATA TYPE VERSUS ABSTRUCT DATA TYPE

DATA TYPE: Set of values (or objects)

ABSTRUCT DATA TYPE (ADT): Set of objects + a mathematical model with a collection of operations defined on the model.

DATA TYPE: Set of values (or objects).

Fortran 77: INTEGER, REAL, CHARACTER/STRING LOGICAL

Composite types: Array of Integers

Array of reals

Etc.

Pascal:

Basic types: integer, real, character, Boolean

Composite types: array of integers

Array of characters

Etc.

Record of integers/reals/characters

Etc.

Set of….

File of…

• THERE ARE OPERATIONS ASSOCIATED WITH EACH TYPE

• AGGREGATING TOOLS: array, record, file

C:

Basic types: int, real, char

Composite types: arrays, structures

WHAT ABOUT POINTERS?

Pointer can be treated as a data type, but usually it’s treated as a DATA STRUCTURING FACILTY.

ABSTRUCT DATA TYPE (ADT)

Set of objects plus a mathematical model with a collection of operations defined on the model

Example: List a1, a2 ,…, an

LIST (of integers) is an ADT with the following operations:

1. Calculate the length of the list

2. Get the fist member of the list and return null if empty

3. Retrieve the member at position P and return null if P doesn’t exist

4. Locate X in the list

5. Insert X into the list at position P

6. Delete the member at position P

P = 1 2 3 4 5 6 7 8

L = 50, 60, 23, 47, 21, 39, 60, 40

1. LENGTH (L) = 8

2. FIRST (L) = 50

3. RETRIEVE (4, L) = 47

RETRIEVE (9, L) = null

4. LOCATE (60, L) = 2

5. INSERT (30, 5, L) gives the result:

L = 50, 60, 23, 47, 30, 21, 39, 60, 40

6. DELETE (3, L) gives the result

L = 50, 60, 47, 21, 29, 39, 60, 40

ALL OPERATIONS ARE ATOMIC EXCEPT FIRST SINCE:

FIRST (L) = RETRIEVE (1, L)

EXAMPLE: ADT STACK (OF INTEGERS)

1. Retrieve the top element

2. Delete the top element (POP)

3. Insert x at the top (PUSH)

4. Test if the stack is empty

|27 |

|40 |

|32 |

•

•

S =

1. TOP (S) = 27

|40 |

|32 |

•

2. POP(S) = results in S =

|0 |

|27 |

|40 |

|32 |

•

3. PUSH (0, S) results in

S =

3. EMPTY (S) = false

Example: ADT MATRIX (OF REALS)

1. Return number of rows

2. Return number of columns

3. Multiply matrices A and B

4. Add A and B

5. Compute the transpose of matrix A

6. Delete a rows/column

7. Add a row/column

8. Multiply matrix A by real number 6

OBSERVATIONS:

1. Domain of an operation may involve more than one ADT

Type

2. Some operations are partial

3. Range of an operation may be a different ADT

A simple application of ADT – evaluation of arithmetic express

a + b*c/d **e +f

Algorithm: Value (x : expression);

oprnd: STACK OF REALS

optor: STACK OF CHARS

x1, x2 : REAL

i: INTEGER

Initialize oprnd and optor

for i:= to LEN (x) do

case x[i] of

real: PUSH (x[i], oprnd)

char: if TOP (optor) < x[i] then

PUSH (x[i], optor)

else

repeat

x2: = TOP (oprnd);

POP (oprnd);

x1: = TOP (oprnd);

POP (oprnd);

x1: = x1 TOP (optor) x2; PUSH (x1, oprnd);

POP (optor)

until TOP (optor) < x[i];

PUSH (x[i], optor)

end if

endcase

Value: = top (oprnd)

Comparison of ADT’s with procedure – the advantages

1. GENERALIZATION

Procedures are generalization of primitive operations

(e.g. +, -, *,….)

ADT’s are generalizations of primitive data types.

2. ENCAPSULATION (OR MODULARITY)

A procedure encapsulates all the statements relevant to a certain aspect of a program.

An ADT encapsulates all the definitions and the operations relevant to a data type.

How to implement an ADT?

Note that a data structure doesn’t have to be associated with an ADT.

Data Structure: A collection of data objects connected in various ways.

A data structure is always associated with a specific programming

language.

FORTRAN 77: the only data structuring facility is ARRAY

PASCAL: we have: ARRAY, RECORD, and POINTER

C: ARRAY, STRUCTURE, POINTER

Some important terms:

Cell: a box capable of holding a value drawn from some basic or composite data types (e.g. integer, record…)

CELL IS BASIC BUILDING BLOCK OF DATA STRUCTURE

Pointer: a cell whose value indicates another cell

Cursor: an integer-valued cell, used as a pointer to an array

Example: A simple data structure is given below.

It may be used in the implementation of ADT MATRIX.

|a11 | | |

|a11 | | |

|a11 | | |

|a22 | | |

|a22 | | |

|a22 | | |

|am1 | | |

|am1 | | |

|am1 | | |

A pointer A CELL

Type

Cell type = record

Element: real

Down: cell type

Right: cell type

End

Example: A data structure below way be used in the implementation of ADT LIST

|1.2 3 |

| |

|3.4 0 |

| |

|5.6 2 |

| |

|7.8 1 |

1

2

3

4

A CURSOR

L = 7.8, 1.2, 5.6, 3.4

|2 | |

| 4 | |

|1.2 3 |

| |

|3.4 0 |

| |

|5.6 2 |

| |

|7.8 1 |

1

2

3

4

ALGORITHM VERSUS PROGRAM

• An algorithm is a finite sequence of instructions satisfying the following criteria.

1) Definiteness : - each instructions must be clear and unambiguous

2) Finiteness: - the algorithm will terminate after a finite number of steps for all cases.

3) Effectiveness:- each instruction can be performed using a finite amount of resource (time and space)

• A (well-defined) program in principle is similarly described, but program:

1) is always associated with a specific programming

Language

2) May not half (e.g. Operating systems)

All the programs. We are interested in; half pseudo-Pascal is our chosen language

WE WILL USE ALGORITHM AND PROGRAM INTERCHANGABLE

Examples:

Proc search (x: integer; A : array [1…10] of integer)

i=1;

while x A[i] and I 0 THEN 3n3 -6n2 >Cn2 (( 3n – 6 > C

Hence if n > C + 6 then 3n3 – 6n2 > Cn2

3

k

Σ ai ni = 0 (nk) when ak > 0

i= 0

106 = 0 (1) = 0 (2)

100n + 105 = 0 (n)

n4 + n2 + n + 6 = 0(n4)

2n + n100 = 0(2n)

3n >> 0 (2n)

log10 n = 0 (log2n) since log10n = log2n

log210

0 (f(n)) is an upper bound of the at the growth rate order of T (n) if T (n) = 0 (f(n))

To specify a lower bound, we use Ω.

DEFINITION:

T (n) is Ω (f(n)) if there is a constant C such that T (n) ≥ c f(n) infinitely of ten.

½ n + 100 = Ω (n)

T (n)

F (n)

C = ½ ( ½ n + 100 > C n

T (n) = n n is odd & n ≥ 1

n2 /100 n is odd & n ≥ 1

T (n) = Ω (n2)

C = 1/100 ( T (n) ≥ C n2 for n = 0, 2, 4, 6,

WHY IT IS IMPORTANT?

5n2

2n n3/2

100n

3000

2000

1000

5 10 15 20 n

Running times of 4 programs

1000 jek ≈ 17 minutes

• HOW LARGE A PROBLEM CAN WE SOLVE

• SUPPOSE THAT WE NOW WE BUY A MACHINE THAT RUN 10 TIMES FASTER AT NO ADDITIONAL COST. THEN FOR THE SAME COST WE CAN SPNED 104 SECONDS ON A PROBLEM WHRE WE SPENT 103 SEC BEFORE

|Running time T (n) |Max Problem size for 103 sec |Max problem |Increase in Max problem size |

| | |size for 104 sec | |

|100 |10 |100 |1000% |

|5n2 |14 |45 |320% |

|n 3/2 |12 |271 |230% |

|2n |10 |13 |130% |

THE 0 (2n) PROGRAMS CAN SLOVE ONLY SMALL PROGRAMS NO MATTER HOW FAST THE UNDERLYING COMPUTER IS.

THEOREM

IF T1 (n) = 0 (f(n)) AND T2 (n) = 0 (g(n))

THEN T1 (n) + T2 (n) = 0 (max (f (n)), g (n)).

PROOF

THERE ARE c1, n1, c2, n2 SUCH THAT

n ≥ n1 ( T1 (n) ≤ c1 f (n)

n ≥ n2 ( T2 (n) ≤ c2 g (n)

LET n3 = max (n1,n2). THEN

n ≥ n3 ( T1 (n) + T2 (n) ≤ c1 f (n) + c2 g (n) ≤ (c1 + c2) max (f(n), g (n)).

ENDPROOF

HENCE: 0 ( f (n)) + 0 (g (n)) = 0 (max (f (n),g (n)))

0 ( n2) + 0 (n3) = 0 (n3)

0 (n2) + 0 (2n2) = 0 (2n2) = 0 (n2)

THEOREM

IF T1 (n) = 0 (f (n)) AND T2 (n) = 0 (g (n))

THEN T1 (n) T2 (n) = 0 (f (n) g(n))

PROOF

THERE ARE c1, n1, c2, n2 SUCH THAT

n ≥ n1 ( T1 (n) ≤ c1 f (n)

n ≥ n2 ( T2 (n) ≤ c2 g (n)

LET n3 = max (n1,n2). THEN

n ≥ n3 ( T1 (n) T2 (n) ≤ c1 c2 f(n) g (n)

ENDPROOF

HENCE: 0 ( f (n)) 0 (g (n)) = 0 (f (n) g (n))

0 ( n2) 0 (n5) = 0 (n7)

0 (n2) 0 (2nh) = 0 (n22h) = 0 (2h+2logh)

OTHER IMPLICATIONS

f(n) f (n)

Σ 0 (g (i, n)) = 0 ( Σ g (i,n))

i=1 i=1

max (0 (f(n)), 0(g (n)) = 0 (max(f (n)), g(n)))

0 (f(n)) = 0 (g (n)) * ASYMMETRIC!

↨

0 (f (n)) ≤ 0 ( g(n))

• ═ Means IS

MY CAT IS BLACK ≠ BLACK IS MY CAT

0 : FUNCTION → SET OF FUNCTIONS

0 (n2)

n2 0

DEF: 0 (f (n) 0 (f (n) == 0 (f (n) g (n))

Any Operator

+, ., ETC.

OTHER USEFUL RULES

f(n) ═ 0 (f (n))

C 0(f(n)) ═ 0 (f(n))

0 (f(n)) + 0 (f(n)) ═ 0(f(n))

0 (0 (f(n)) ═ 0 (f(n))

0 (f(n))0(g(n)) ═ 0 (f(n))g(n))

0 (f(n)g(n)) ═ f(n)0(g(n))

REMEMBER: ═ HERE IS ASYMMERIC!

CALCULATING COMPLEXITIES OF ALGORITHMS

Procedure : bubble (var A : array [1…..n] of int);

BUBBLE SORT A INTO INCREASING ORDER

Var i, j, temp: interger:

Begin

1 for i: = 1 to n -1 do

2 for j:=n down to it 1 do

3 if A[j-1] > A[j] then begin

4 temp: = A[j-1]; swap

A[j-1] and A[j]

5 A[j-1] := A[j];

6 A[j] := temp

end

(3) – (6) TAKES 0(1)

(2) – (6) TAKES (n -1) 0(1) + 0(1) = 0(n-1)

(1) – (6) TAKES:

n n

Σ [0(n-i) + 0(1) = 0 ﴾Σ (n-i) = 0 (n(n-1))

i=1 i=1 2

═ 0(n2-n) ═ 0 (n2)

2

Function test (m: integer) : Boolean;

TESTS IF m IS A POWER OF 2, I.E. M═2K FOR SOME k

Begin

if m =1 then test:= true

else

if (m mod 2 = 0) then test:= test (m/2)

else test:=false

end

LET T(m) = time complexity of test

1→C1

2 →C2

3→C1

4→C2 + T(m/2)

5→C2 C1 +C2 m =1

2c1 + c2 m odd, m >1

T (m) = 2C1 + C2 + T (m/2) m even

A recurrence equation

Define a new function:

C1 + C2 m ≤ 1

T’(m) =

2C1 + C2 + T’ (m/2) m > 1

Then T(m) ≤ T ‘(m) for all the m > 0 i.e.

T ‘(m) is an upper bound of T (m).

Note: T ‘(m) is defined for all real numbers.

T ‘(m) = 2C1 + C2 + T’ (m/2)

= 2(C1 + C2 )+ T’ (m/22)

= 3(2C1 + C2 ) + T’(m/23 )

…

= [log2m] (2C1 + C2) + T’ m 2[log2m]

= ( 2C1 + C2 ) [log2m] + C1 + C2

= 0(logm)

THUS: T’(m) = 0 (logm), T(m) = 0 (logm)

Ceiliuy :

[x] is the smallest integer ≥ x

→

e.g. [1.5] = 2

[3.1] = 4

[3.0] = 3

NOTE THAT:

2[log2m] ≥ m

IF m = 2k log2m = k,

[log2m] = k and 2[log2m] = m

m = 6

log24 = 2 & log2 8 = 3 → 2 m

Problem:

What is T (m) ? Is m the length of input!

M is 100, 15, 64, etc, just number!!

• IF m is BINARY and is the number of bits of m, THEN

n = [log2m]

And T (m) = 0 (log2m) → T (n) = T ([log2m]) = 0 (log2m)

i.e. T (n) = 0 (n)

• M CAN BE TREATED AS : 000….0,

m

I.E. m UNITS, THEN

THEN “LENGTH” OF M IS m, and

T (n) = T (m) = 0 (log n)

DESIGN OF A PROGRAM

• TOP – DOWN / BOTTOM – UP APPROACH

• STEPWISE REFINEMENT, COOSE ADT’S AND DATA STRUCTURES

• CODING

A REMARK ABOUT RUNNING TIME

• ALTHOUGH THE ORDER OF RUNNING TIME IS VERY IMPORTANT, WE SHOULD ALSO CONSIDER THE FOLLOWING FACTORS IN PRACTIC.

1. THE TIME IT TAKES TO WRITE AND DEBUG THE PROGRAM

2. READABILITY, MODULARITY, ETC. HOW HARD IS TO MAINTAIN THE PROGRAM

3. SOMETIMES CONSTANTS ARE ALSO IMPORTANT

4. SPACE (OR STORAGE) COMLEXITY

5. ACURACY

ADT LIST

A list is a sequence of zero or more elements of a given type (element type).

L = a1, a2, a3, …., an

length = n

first = a1

last = a1 some data type

ai is at postion i

ai1 precedes ai

ai followa ai1

END(L) = position n+1

Operations

INSERT (x,p,l); DELETE(p,L);

LOCATE (x,L); RETRIEVE(p,L);

MAKENULL(L): L ← Є

FIRST(L); NEXT(p,L); PREVIOOUS(p,L)

PRINT(L); LENGETH(L); REVERSE(L)

CONCAT(L1, L2); etc. EMPTY(L)

Array implementation of lists

Last 1

2 list

empty

max

Const

max =?;

type

position = 1..max;

LIST = record

elements: array [positions] of elements type:

last: o ..max

end;

function END (var L: LIST) : integer;

begin

END : = L.last+1

end;

last

1 2 3 p max

|a1 |a2 |a3 | |ap | |an-1 |an | | | |

Procedures INSERT (x: elements type; p: position; var L:LIST);

Var

q: position

begin

if L.last = max then

error (‘list is full)

else

if (p>L.last+1) or (p>1) then

error

else begin

for q:=L.list downto p do

L.elements[q+1]:=L.elements[q];

//shifting to the right//

L.last:=L.last+1;

L.elements[p]:=x

End

End;

Time co,plexity: INSERT, DELETE, LOCATE – O(n)

RETIEVE, NEXT, PREVIOUS

END, FIRST, MAKENULL – O(1)

Avg. time INSERT, DELETE, LOCATE – O(n)

Pointer implementation (linked list)

Cell 0 cell 1 cell 2 cell n

..

Header

list

L

Type

Celltype = record

Element : elementtype;

Next: ↑ ceeltype

End;

LIST = ↑ celltype;

Position = ↑ celltype;

Position i : a pointer to cell i -1, 1≤ i ≤n+1

Function END(L.LIST) : position

Var

q: position

begin

q:=L;

while q. ↑. Next < > nil do

q := q. ↑. Next;

END:=q

End;

LIST: record

first: ↑ celltype;

last: ↑ celltype

end;

Insert x at p time O(1)

…… …..

p

Delete cell at p

Time O(1)

…

….

p

Time O(n)

L

Header p

PREVIOUS (p, L)

INSERT, DELETE, RETRIVE, NEXT, FIRST, MAKENULL –O(1)

PREVIOUS, LOCATE, END – O(n)

Compare the two implementations

1. maximum size of the list – array

2. waste of space – both

3. operation speeds

array pointer

INSERT O(n) O(1)

DELETE O(n) O(1)

PREVIOUS O(1) O(n)

END O(1) O(1) or O(n)

4. pointer representation can be dangerous!

e.g. q:=NEXT(p,L);

INSERT (X,P,L)

.

.

.

IF q=NEXT(p,L) then

P q q≠NEXT(p,L)!

DOUBLY – LINK – LISTS

Cell 1 cell 2 cell3 cell n

Type

Cell type = record

Element: elementtype;

Next, previous: ( celltype

End;

Position: ( celltype;

Position I: a pointer to cell I

Function LAST (L)

Begin

LAST : = L(.previous

End;

PATTERN MATCHING IN STRINGS

ALPHABET A = {a1, a2, …. , ak }

SYMBOL/CHARACTER

A STRING x = a1, a2, …. , an n ( 0 , ai ( A

STRINGD A SPECIAL CAST OF LISTS

PATTERN MACTHING: x = a1, a2, …. , an

Pat = b1, b2, …. , bm

Is pat a substring of x?

i.e. (( I : 1 ( I ( n – m +1) ai ai+1 …. = b1b2 …bm

x = aabbbabbbaaa pat = bab

1234567891011

x = aabbabbbaaa yes i= 4

pat = bab

pat = abab => No

SIMPLE ALGORITHM

x = aabbabbbaaa pat = bab

aabbabbbaaa NO

bab

aabbabbbaaa NO

bab

aabbabbbaaa YES!

bab

BUT FOR pat = aaa WE NEED TO MOVE

FROM aabbabbbaaa TO aabbabbbaaa

aaa aaa

SIMILARLY for pat = abab, from

1234567891011

aabbabbbaaa TO aabbabbbaaa

abab abab

8 = 11 – 4 +1

WORST CASE

x = a1, a2, …., am am+1 …..an-m+1 …. an

b1 b2…bm b1 b2… bm

n-m+1 passes

EACH PASS TAKES O(m) comparisons, HENCE

(n-m+1) O(m) = O(m(n-m+1)) = O (mn)

procedure find (x, pat : STRING; var found : Boolean; var i : position)

Found is set to false if pat doesn’t occur int x, otherwise found is set to take and I is set to the first position in x where pat begins)

Var p,q : position;

Begin

If not EMPTY (x) and not EMPTY (pat) then

Begin

Found: = false;

i:= FIRST(x);

while not found and i ( END (x) do

begin

p:= i; q: = FORST(pat);

while RETRIEVE (p,x) = RETRIEVE (q, pat) and not found do

begin

p: = NEXT(p,x);

q:= NEXT(q,pat)

IF q= END (pat) then found : = true

End;

If not found then i:=NEXT(i,x)

End;

IF END(L) IS O(1) THEN T(n,M) = O(MN)

END

END

THE KNUTH, MORRIS PRATT ALGORITHM ( KMP)

X = abaababaabacabaababaabaab

MISMATCH

Pat= abaababaabaab

WHAT DO YOU DO NEXT?

X =

Pat =

NEXT MOVE

X =

Start comparison

X= abaababaabacabaababaabcab

abaababaabaab

math

u

abaababaaba

u

abaababaabacabaababaabaab

abaaba baabaab

start comparing & mismatch

abaaba

abaababaabacabaababaabaab

abaababaabaab

START COMPARING & MISMATCH

U

aba

u

abaababaabacabaababaabaab

abaababaabaab start comparing & mismatch

abaababaabacabaababaabaab

↕

abaababaabaab

↑

mismatch

abaababaabacabaababaabaab

abaababaabaab

COMPARING

NUMBER OF COMPARISON IS O (n) BUT HOW TO FIND

OUT WHAT IS U?

LET pat = b1b2 … bm

OR EACH 1 ≤ j ≤ m, LET

Largest i sud that 0 < i < j and

b1… bi = bj –i+1 … bj

f (j) =

0. if sud i does not exist

f (j) < j FAILURE FUNCTION

|j |1 |2 |3 |4 |6 |7 |8 |9 |10 |11 |12 |13 |14 |

|Pat = |a |b |a |a |b |a |b |a |a |b |a |a |B |

|f(j) |0 |0 |1 |1 |2 |3 |2 |3 |4 |5 |6 |4 |5 |

aba abaa abaab abaaba

abaabab abaababa abaababaa

abaababaab abaababaaba

abaababaabaa abaababaabaab

TIME COMPLEXITY:

T (n, m) = O (n + complexity of defining g)

= O (n + complexity of defining f)

0. if j = 1

f(j) = fs(j -1) +1 where s is the smallest I such

that bfi(j-1) +1 = bj

0. if no such i exist

f i (j -1) = f (f(… f(j -1)…..)

i times

f 3 (j -1) = f (f (f (j-1)))

T(j-1) T1 j - 1

j

f(j- 1)

HERE f(j) = f (j -1) +1

j -1

i= f(j -1) j

u j -1

w

w

j

f(i) = f (f(i-1)) = f2 (i-1)

f2(i-1) +1

proc fail (pat[1…m], vav f: away [1…m] of integer )

vav i, j = integer;

begin

f[1] : = 0;

for j: = 2 to m do

begin

i:= f [j -1];

while (pat[j] ≠ pa[i+1} and i > 0) do i:= f[i];

if pat[j] = pat[i+1] then f[j]:= i+1

else f[j]:=0

and

end

T (m) = O (m) !

Procedure KMP (x, pat, g, found, i);

{ x[1..n] , pat [1..m] are strings ;

g[j] = g (j), 1 ≤ j ≤ m}

var p, q : position

begin

if n ≠ 0 and m ≠ 0 then

begin

p:=1; q:=1;

while (p ≠ n+1 and q ≠ m+1) do

if x[p] = pat [9] then

begin p: = p+1;

q: = q+1;

end else if q =1 then p:= p+1

else q: = g[q];

Time = 0(m)

If q = m+1

then begin found : = true; i: = p-m

end else found :=false

end

else ……

end ;

ADT STACK

“ LAST-IN-FIRST – OUT” LIST (LIFD)

OPERATIONS:

MAKENULL(S) : make stack S empty

TOP(s) : Return the top element of s RETRIEVE (FIRST, S)

TOP (s) = RETRIEVE (I, S)

POP(S) : Delete the top element of S

Sometimes POP is defined as function that returns the element being popped out DELETE (FIRST (s) , S)

POP (s) = DELETE (I, S)

PUSH (X,S); insert x at the top of S

PUSH (x, s) = INSERT (x, I , s)

INSERT (x, FIRST(S), S)

EMPTY (s) : Return true if S is empty, false otherwise

A SIMPLE EXAMPLE:

F: erase characters, if cancels the previous uncancelled character

@: kill character, if cancels all previous characters on the line

abc # d @ aa#b = ab

Procedure EDIT

Var S : STACK OF CHAR;

C: CHAR

Begin

MAKENULL (S);

Read (c);

While not end ( c ) do

Begin

If c = ‘#’ then POP (s)

Else if c = ‘@’ then MAKENULL(S)

Else PUSH (c, S);

Read (c)

End;

PRINT S IN REVERSE ORDER

End

ARRAY IMPLEMENTATION OF STACKS

TOP

1 1

2 force

K K

stack

max MAX

type : position = 1 … max;

STACK = record

Top : 1 .. max +1;

Elements : away [position] of element type

• PUSH, POP, TOP – O ( 1)

MORE SPACE – EFFICIENT IMPLEMENTATION

POINTER IMPLEMENTAION

Stack

• MANY STACKS IN ONE ARRAY

TOP

1

2 tree

3

BOTTOM

1

2

3

Stack pace

ADT QUEUE

A QUEUE IS A “First – in – First – Out” LIST > (FIFO)

OPERATIONS:

MAKENULL (Q);

FRONT (Q) : return the first element of Q

FRONT (Q) = retrieve (first (Q), Q)

ENQUEUE (x, Q) : inserts x at the end of Q

ENQUEUE (X, Q) = INSERT (X, END (Q), Q)

DEQUEUE (Q): DELETES THE FIRST ELEMENT OF Q

DEQUEUE (Q) = DELETE (FIRST (Q),Q)

EMPTY (Q):

POINTER IMPLEMENTATION

header

…

front

near

type celltype = record

element : elementtype;

next : ↑ celltype

end;

QUEUE = record

Front, rear : ↑ celltype

End;

FUNCTION EMPTY (Q : QUEUE) : Boolean;

Begin

If Q. front = Q.rear then EMPTY: = true

Else EMPTY : = false

End

EACH OPERATION – 0 (1)

ARRAY IMPLEMANTATION

FRONT TREE

1

QUEUE

REAR

MAX

TREE

ENQUEUE – 0 (n)

CIRCULAR ARRAY IMPLEMENTATION

(BUFFER!)

Max -1

max

real 1

2

HOW DO WE DISTRINGUSH BETWEEN FULL AND EMPTY

• MAINTAIN AN EXTRA BIT

• FULL ≡ (FRONT = addone(addone(real)))

1 if have been to (i, j)

• Mark [i, j] =

0 otherwise

• IF NO WAY OUT, BEACK UP ONE CELL AND TRY A DIFFERENT MOVE

• MUST STRORE THE CURRENT PATH SOMEWHERE

A PATH: (i, j), (i2, j2), …., (is, js)

STACK

Type offsets = record

X: -1 …1

Y: -1 …1

End

Directions = (N, NE, E, SE, S, SW W, NW);

Var move : away [directions] of offsets

|d |Move[d] .x |Move[d].y |

|N |-1 |0 |

|NE |-1 |1 |

|E |0 |1 |

|SE |1 |1 |

|S |1 |0 |

|SW |1 |-1 |

|W |0 |-1 |

|NW |-1 |-1 |

Var maze : array [0 : m+1, 0 … n + 1] of 0 …1

Mark : array [1..m, 1…n] of 0…1

Type: dir = (N, NE, E, SE, S, SW,W,NW,D)

Type: elementtype = recond DEAD END

X: 1 … m;

Y: 1 … n;

Start: dir

End

STACK = ……..

Var path : STACK

Fuy NEXTMOVE (loc : elementtype) : dir

Var d: dir;

S, r, i, j: out

Found : bool;

begin

i = loc.x; j := loc.y; d:=loc.start; found:= false;

while d# D ∩ not found do

Begin

s: = move [d].x; r: = move[d].y;

if maze [i + s, j+r] = 0 and

mark [ i + s, j +r] = 0

then found : = true else d:= Succ (d)

end; NEXTMOVE : = d

end

proc rat ( var: maze [0 … m+1, 0 … n+1] of 0…1);

var mark: array [1 …m, 1…n] of 0…1;

path : STACK;

location : elementtype;

d: dir

function NEXTMOVE (X: elementtype): dir; ….;

begin mark: = (0); MAKENULL (path); initialzation

(should be specified last)

location:= (1,1, E) ; mark [1,1] : = 1;

PUSH (location, path );

While not EMPTY (pathy) do

begin

location: = TOP (path) ; POP (path);

d: = NEXTMOVIE (Location)

if d = D then

begin

location.start: = succ(d); PUSH (location, path);

location.x : = location.x + move [d].x;

location.y : location.y + move [d].y;

if location.x = m and location.y = n then

begin print(path); return end

else begin

PUSH ((location.x, location.y, N), path);

Mar(location.x, location.y) =1

End

End

End

end

end

TIME COMPLEXITY OF RAT : O (mn)

SPACE COMPLEXITY OF RAT :O (mn)

BUT WITHOUT SING MARK

O (8mn) = O (2mn)

An application of queues - breadth-first search in trees

tree T

V1

V2 V3

V4

V5

V6

V11

V9

V7 V8 V10

binary

LEFT (v), RIGHT(v)

║ ║

left child right child

of V of V

e.g., LEFT (v3 = null, RIGHT (V3) = V6

DATA(V1) = a1

ROOT(T) = v1

Searching in tree

Given tree T and data x,

find a node v of T s.t. DATA(v) = X.

Possible approaches:

1. Breadth-first search

try level 1, then level 2, then

level 3, ...etc.

2. Depth-first search:

search along the leftmost path until the leaf is reached, then back-

up, try the 2nd leftmost path, ...etc.

Breadth-first

X = 20

V1

V2 V3

V4

V5

V6

V12

V10

V7 V8 V9 V11

Searching v1, v2, v3, v4, v5, v6, . . .

Depth-first

Searching order: v1, v2, v3, v4, v5, v6, . .

Procedure DSearch(x,T)

begin

if x = DATA(ROOT(T))’ then

PrintROOT(T)

Else

DSearch left subtree;

DSearch right subtree;

end;

nonrècursive version

procedure DSearch (x,T);

var path : STACK of nodes

v: node;

begin

v := ROOT(T); MAKENULL (path);

PUSH(v,path);

while not empty (path) do begin

v := TOP(path); pop(path);

if DATA(v) = X then Print v

elsel PUSH (LEFT(v));

PUSH(RIGHT(v)); e // swap//

end

end

Time: 0(n)

Space: 0(n)

Space avg: 0(Iogn)

Procedur BSearch(x,T)

Var level : QUEUE of nodes;

V : node;

begin

v := ROOT(T);

MAKENULL(level);

ENQUEUE(vjevel);

while not empty (level);

begin

V := FRONT(level);

DEQUEUE(Ievel);

if DATA(V) = x then

Print v; stop

else begin

ENQUEUE(LEFT(v), level);

ENQUEUE(RIGHT(v), level)

end

end

end;

Time:O(n) n =/T/ (--------------size of T

Space: 0(n)

Avg :0(n)

Application – implement a DOS command cd:\

Cd:\ name – change current directory to subdirectory name

What should cd:\letters do?

BFS DFS?

When do we use DFS?

e.g., solution tree

Ellmination of Recursion

Sometimes it is absolutely necessary to eliminate recursive

• recursive calls are not supported e.g., FORTRAN

• speed is the first priority - do it by yourself

Solution: STACK of activation records

Generally, an activation record holds

1. current values of the parameters (pass by value)

2. current values of the local variables

3. a label indicating return address

Assume that if procedure p(x1, x2 …. var y1, y2, ….)

then the recursive call is p(a1, a2, …, y1, y2, ….)

General Rules:

Procedure P (x1, x2: int; var y: int);

Var i, j: int;

Begin

____________________________________;

____________________________________;

. . .

P(a1, a2,y)

_________________________________________;

_________________________________________;

. . .

end;

Example 1

procedure Ackerrnann (m,n:integer, var A:int);

1. begin

if n ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download