Transcript CS2007Ch05

COSC2007
Data Structures II
Chapter 6
Recursion as a
Problem-Solving Technique
Topics
2

8-Queen problem

Languages

Algebraic expressions

Prefix & Postfix notation & conversion
Introduction

Backtracking:


A problem-solving technique that involves
guesses at a solution, backing up, in reverse
order, when a dead-end is reached, and trying a
new sequence of steps
Applications
8-Queen problems
 Tic-Tac-Toe

3
Eight-Queens Problem

Given:



Required:

4
64 square that form 8 x 8 - rows x columns
A queen can attack any other piece within its row, column,
or diagonal
Place eight queens on the chessboard so that no queen
can attack any other queen
Eight-Queens Problem

Observations:

Each row or column contain exactly one queen

There are 4,426,165,368 ways to arrange 8 queens on
the chessboard


Wrong arrangements could be eliminated to reduce the
number of solutions to the problem


5
Not all arrangements lead to correct solution
8! = 40,320 arrangements
Any idea?
Eight-Queens Problem

Solution Idea:




6
Start by placing a queen in the first square of column 1
and eliminate all the squares that this queen can attack
At column 5, all possibilities will be exhausted and you
have to backtrack to search for another layout
When you consider the next column, you solve the same
problem with one column less (Recursive step)
The solution combines recursion with backtracking
Eight-Queens Problem

How can we use recursion for solving this
problem?

For placing a queen in a column, assuming that
previous queens were placed correctly
a)
b)
c)

Base case:


7
If there are no columns to consider  Finish – Base case
Place queen successfully in current column  Proceed to
next column, solving the same problem on fewer columns –
recursive step
No queen can be placed in current column  Backtrack
Either we reach a solution to the problem with no columns
left
 Success & finish
Or all previous queens will be under attack
 Failure & Backtrack
Eight-Queens Problem

8
Pseudocode
PlaceQueens (in currColumn: integer)
// Places queens in columns numbered Column through 8
if (currColumn > 8)
Success. Reached a solution
// base case
else
{ while (unconsidered squares exist in the currColumn & problem is
unsolved)
{determine the next square in column “currColumn” that is
not under attack in earlier column
if (such a square exists)
{
Place a queen in the square
PlaceQuenns(currColumn + 1)
// Try next column
if ( no queen possible in currColumn+1)
Remove queen from currColumn &
consider next square in that column
} // end if
} // end while
} // end if
Eight-Queens Problem

Implementation:

Classes:


QueenClass
Data members

board:


square

9
How?
Indicates that the square has a queen or is empty
Eight-Queens Problem

Implementation:

Methods needed:

Public functions (methods)




Private functions (methods)





10
ClearBoard: Sets all squares to empty
DisplayBoard: Displays the board
PlaceQueens: Places the queens in board’s columns & returns
either success or failure
SetQueen: Sets a given square to QUEEN
RemoveQueen: Sets a given square to EMPTY
IsUnderAttack: Checks if a given square is under attack
Index: Returns the array index corresponding to a row or column
Textbook provides partial implementation
Languages

Language:

A set of strings of symbols

Can be described using syntax rules

Examples:

Java program

program =
{ w : w is a syntactically correct java program}

Algebraic expressions

11
Algebraic Expression = { w : w is an algebraic expression }
Languages

Language recognizer:


Recognition algorithm:


12
A program (or machine) that accepts a sentence and
determines whether the sentence belongs to the
language
An algorithm that determines whether a given string
belongs to a specific language, given the language
grammar
If the grammar is recursive, we can write
straightforward recursive recognition algorithms
Languages

Example: Grammar for Java identifiers
Java Ids = {w:w is a legal Java identifier}

Grammar
< identifier > = < letter > | < identifier > < letter >
| < identifier > < digit >
< letter >
=a|b|...|z|A|B|...|Z|_
< digit >
=0|1|...|9

Syntax graph
Letter
Letter

Observations


The definition is recursive
Base case:


13
A letter ( length = 1)
We need to construct a recognition algorithm
Digit
Languages

Java Identifiers’ Recognition algorithm
isId (in w: string): boolean
// Returns true if w is a legal Java identifier;
// otherwise returns false.
if (w is of length 1 )
// base case
if (w is a letter)
return true
else
return false
else if
(the last character of w is a letter or a digit)
return isId (w minus its last character)
// Point X
else
return false
14
Palindromes

String that read the same from left-to-right as it does from
right-to-left

Examples
RADAR
Madam I’m Adam (without the blanks and quotes)
 Language:
Palindromes = { w : w reads the same from left to right
as from right to left }

Grammar:
<pal > = empty string | < ch > | a <pal > a | . . . | z <pal> z |
A < pal > A | . . . | Z < pal > Z
< ch > = a | b | . . . | z | A | B | . . . | Z



15
The definition is recursive
Base cases:
 ?
We need a recognition algorithm
Palindromes

Recognition algorithm
isPal(in w: string) : boolean
If (w is of length 0 or 1)
return true // Base-case success
else
if (first and last characters are the same)
return IsPal( w minus first and last characters)
else
return false
16
// Base-case failure
An Bn Strings

Language:
L = { w : w is of the form An Bn for some n  0 }

Grammar:
< legal word > = empty string | A < legal word > B


The definition is recursive
Base case:

17
?
An Bn Strings

Recognition algorithm
IsAnBn(in w: string): boolean
If (w is of length 0)
return true
// Base–case success
else if (w begins with ‘A’ & ends with ‘B’)
return IsAnBn( w minus first & last characters) // Point A
else
return false
// Base–case failure
18
Algebraic Expressions

Algebraic expression

A fully or partially parenthesized infix arithmetic
expression

Examples



Solution

19
A+(B–C)*D
{ partially parenthesized}
( A + ( ( B – C ) * D )) {Fully parenthesized}
Find a way to get rid of the parentheses completely
Algebraic Expressions

Infix expression:


Binary operators appear between their operands
Prefix (Polish) expression:

Binary operators appear before their operands

Postfix (Reverse Polish) expression:

Binary operators appear after their operands
Examples:

Infix
a+b
a+(b*c)
(a + b) * c
20
Prefix
+ab
+a*bc
*+abc
Postfix
ab+
abc*+
ab+c*
Prefix Expressions

Language:
L = { w : w is a prefix expression }

Grammar:
< prefix >
= <identifier>
| < operator > < prefix1> < prefix2 >
< operator > = + | - | * | /
< identifier > = A | B | . . . | Z



Definition is recursive
Size of prefix1 & prefix2 is smaller than prefix, since they
are subexpressions
Base case:

21
When an identifier is reached
Prefix Expressions

How to Determine if a Given Expression is a Prefix
Expression?
22
Prefix Expressions

How to Determine if a Given Expression is a Prefix
Expression:
1. Construct a recursive valued function End-Pre (First, Last )
that returns either the index of the end of the prefix
expression beginning at S(First), or -1 , if no such
expression exists in the given string
2. Use the previous function to determine whether a
character string S is a prefix expression
23
Prefix Expressions

End-Pre Function: (Tracing: Fig 6.5, p.309)
endPre(first, last)
// Finds the end of a prefix expression, if one exists.
// If no such prefix expression exists, endPre should return –1.
24
if ((First < 0) or (First > Last)) // string is empty
return –1
ch = character at position first of strExp
if (ch is an identifier)
// index of last character in simple prefix expression
return First
else if (ch is an operator)
{ // find the end of the first prefix expression
firstEnd = endPre(First+1, last)
// Point X
// if the end of the first expression was found
// find the end of the second prefix expression
if (firstEnd > -1)
return endPre(firstEnd+1, last)
// Point Y
else
return -1
} // end if
else
return -1
Prefix Expressions

IsPre Function

Uses endPre() to determine whether a string is a prefix or not
IsPre(): boolean
size= length of expression strExp
lastChar = endpre(0, size-1)
if (lastChar >= 0 and lastChar == strExp.length()-1)
return true
else
return false
25
Prefix Expressions

EvaluatePrefix Function

26
E is the expression beginning at Index
evaluatePrefix( strExp: string)
// Evaluates a prefix expression strExp
{
Ch = first character of strExp
Delete the first character from strExp
if (Ch is an identifier)
return value of the identifier
else if (Ch is an operator named op)
{
Operand1 = EvaluatePrefix(strExp)
Operand2 = EvaluatePrefix(strRxp)
return Operand1 op Operand2
} // end if
}
// base case
// Point A
// Point B
Review

______ is a problem-solving technique
that involves guesses at a solution.




27
Recursion
Backtracking
Iteration
Induction
Review

In the recursive solution to the Eight
Queens problem, the problem size
decreases by ______ at each recursive
step.




28
one square
two squares
one column
two columns
Review

A language is a set of strings of ______.




29
numbers
letters
Alphabets
symbols
Review
The statement:
JavaPrograms = {strings w : w is a syntactically

correct Java program} signifies that ______.




30
all strings are syntactically correct Java programs
all syntactically correct Java programs are strings
the JavaPrograms language consists of all the
possible strings
a string is a language
Review

The Java ______ determines whether a
given string is a syntactically correct Java
program.




31
applet
editor
compiler
programmer
Review

If the string w is a palindrome, which of the
following is true?





32
w minus its first character is a palindrome
w minus its last character is a palindrome
w minus its first and last characters is a
palindrome
the first half of w is a palindrome
the second half of w is a palindrome
Review

Which of the following strings is a
palindrome?




33
“bottle”
“beep”
“coco”
“r
Review

The symbol AnBn is standard notation for
the string that consists of ______.




34
an A, followed by an n, followed by a B,
followed by an n
an equal number of A’s and B’s, arranged in a
random order
n consecutive A’s, followed by n consecutive
B’s
a pair of an A and a B, followed another pair
of an A and a B
Review

Which of the following is an infix
expression?




35
/a+bc
abc+/
ab/+c
a / (b + c)
Review

What is the value of the prefix expression:
– * 3 8 + 6 5?




36
11
23
13
21