Computational problem solving

There was a question about determining constants for complexity analysis in problem 8. For this problem, you must determine the cost and the number of times each step executes.

I uploded the lecture slides for steps.

Please review the homework and slides before you accept.

I will give a good tip if delivered on time and correct

This course is really about Computational
Problem Solving.
It is the process of coming up with a correct AND
efficient computational solution (i.e., one or more
algorithms) to a given problem.
The various steps of computational problem
solving, and the mathematical tools and design
techniques you can use for this, are what we will
discuss next.
Computational Problem Solving
– Problem specification
– Designing solution strategies
– Developing corresponding algorithms
• Understand existing algorithms and modify/reuse, or
• Design new algorithms
– Understanding an algorithm by simulating its
operation on an input
– Ensuring/proving correctness
– Analyzing and comparing performance/efficiency
• Theoretically: Using a variety of mathematical tools
• Empirically: Code, run and collect performance data
– Choosing the best algorithm to implement
Solving problems computationally
• What do you do first?
• Write code? Bad idea!
• Specify the problem
• Come up with multiple strategies
• Design corresponding algorithms (or
understand, modify and reuse existing ones)
• Then choose the best
• How do you choose?
– Correctness
– Efficiency
Strategy vs. Algorithm
Strategy without tactics is the slowest
route to victory. Tactics without strategy is
noise before defeat
– Sun Tzu
Specifying the problem
Restate the problem in such a way that you
begin to get an idea of the complexity of
the problem, and a computational solution
to it (i.e. a strategy to solve it, leading to an
algorithm) can be developed.
E.g., online dating  matching problem
Another Example
How will you specify the
problem?
Simplified Boggle
Given a nxn array of characters; find all
English words horizontally and vertically
in any direction.
Assume that you have a function
Dict_lookup(s: string) available that
returns True if the string s is an English
word, else it returns False.
Now, we can start to think about how
complex is this “simplified” Boggle is
and computational strategies to play the
game.
Complexity
How many strings must be tested?
Approximately n3 strings!
Precisely, n3-n2 strings…
Why?
Designing strategies
Strategy # 1
1. Construct all possible substrings
2. Check each
• Is this correct? What does it mean for this
strategy to be correct?
Strategy # 1: Algorithm # 1
How do you construct all possible substrings?
• You can take one row at a time and construct all
of its substrings
• But it has to be done twice (why?)
• Repeat for each column
• Divide the problem into subproblems
• Solve each subproblem the same way
• Then construct the overall solution from the
subproblem solutions
• Solving the problem for a 4X4 matrix
– Solving the problem 8 times, once for each
row and column
• Solving the problem twice for each row/column
(once in the forward and once in the backward
direction)
• So, once you figure out how to solve the
problem for a row/column in one direction,
you are done!
Notes about Notation
• A[p…p] is an array with one cell with index p
• A[q…p] where q>p is an empty array
• A[p…q] where q≥p is an array with at least one
element
• Two kinds of for loops: “for i←p to q” is an
incrementing loop and “for i←q downto p” is a
decrementing loop
• for i←q to p where q>p and for i←p downto q
where q>p will both fail immediately without
executing.
First Step
how to solve the problem for a row in one direction?
i←1
For j ← 1 to 4
For k ← j to 4
temp←make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
Next Step
Solving the problem twice for a row (once in the
forward and once in the backward direction)
i←1
For j ← 1 to 4
For k ← j to 4
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Next Step
•
•
Is this piece of algorithm correct?
Is this piece of algorithm efficient?
Issues:
1.
Is it more efficient to avoid duplicate dictionary lookups for single
character strings?
2.
Is it more efficient to call make-string again instead of stringreverse?
Making the algorithm piece more
efficient
For a 4-character row a single character needs to be
looked up once, but will be looked up twice: 4 extra calls
to dict_lookup
For a 4X4 matrix a single character needs to be looked up
once, but will be looked up 4-times: 48 extra calls to
dict_lookup
For a nXn matrix a single character needs to be looked up
once, but will be looked up 4-times: 3n2 extra calls to
dict_lookup
looking up a dictionary is expensive and should be
minimized!
Making the algorithm piece more
efficient
Solving the problem twice for the first row (once in
the forward and once in the backward
direction) but checking one-character strings
only once:
i←1
For j ← 1 to 4
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k ← (j+1) to 4
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Next Step
Generalizing: solving the problem twice for all 4 rows (once in the
forward and once in the backward direction)
For i ← 1 to 4
For j ← 1 to 4
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k ← (j+1) to 4
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Next Step
Reusing the same loops a second time to solve the problem
twice for each column (upward and downward) as well as
for each row, i.e. for the full matrix:
For i ← 1 to 4
For j ← 1 to 4
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k ← (j+1) to 4
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For j ← 1 to 4
For i ← 1 to 4
temp ← make-string(A[i,j])
if dict_lookup(temp)=T then print temp
For k ←(i+1) to 4
temp ← make-string(A[i,j]…A[k,j])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Making it more efficient
We can make this more efficient by noticing that since all
single character strings would have been considered in
the first set of nested loops, they don’t have to be
considered again in the second set of loops.
For i ← 1 to 4
For j ← 1 to 4
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k ← (j+1) to 4
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For j ← 1 to 4
For i ← 1 to 4
For k ←(i+1) to 4
temp ← make-string(A[i,j]…A[k,j])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Last Step
Generalizing: solving the problem for any nXn matrix:
For i ← 1 to n
For j ← 1 to n
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k ← (j+1 to n
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For j ← 1 to n
For i ← 1 to n
For k ←(i+1) to n
temp ← make-string(A[i,j]…A[k,j])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Algorithm
Boggle(A: n X n array of characters)
1 For i ← 1 to n
2
For j ← 1 to n
3
temp ← make-string(A[i,j]…A[i,j])
4
if dict_lookup(temp)=T then print temp
5
For k ← (j+1) to n
6
temp ← make-string(A[i,j]…A[i,k])
7
if dict_lookup(temp)=T then print temp
8
temp ← string-reverse(temp)
9
if dict_lookup(temp)=T then print temp
10 For j ← 1 to n
11 For i ← 1 to n
12
For k ←(i+1) to n
13
temp ← make-string(A[i,j]…A[k,j]
14
if dict_lookup(temp)=T then print temp
15
temp ← string-reverse(temp)
16
if dict_lookup(temp)=T then print temp
Questions
We discussed why the strategy {construct all
possible substrings and check each
against the dictionary} is correct. Does it
mean that the algorithm is correct as well?
How efficient is the algorithm?
Are there other algorithms that implement
the same strategy?
Could those be more efficient?
How efficient this algorithm?
– How much does make-string cost?
• O(n): why?
– How much does string-reverse cost?
• O(n): why?
– How much does dict_lookup cost?
• O(n); why?
– What is the total cost?
• approximately (and at most) 8n4+2n2
• why? we will work this out in class
• So this algorithm is O(n4)
• Using same assumptions as when we discussed
the selection problem, how long will it take to solve
a 4X4 Boggle board?
What is the performance of this
board time
algorithm?
size
6000
4
0.01 ms
5
0.03 ms
5000
6
0.06 ms
4000
7
0.12 ms
3000
8
0.20 ms
9
0.33ms
10
0.5 ms
50
300 ms
100
5000 ms
boggle
boggle
2000
1000
0
4
5
6
7
8
9
10
50
100
Strategy #1: Algorithm # 2
• Look at each cell
– Check if that cell makes a one-letter word
– Construct and check strings (and their reverses) made up of the
character in that cell and the ones above it until array boundary
is reached
– Construct and check strings (and their reverses) made up of the
character in that cell and the ones to the left of it until array
boundary is reached
– Construct and check strings (and their reverses) made up of the
character in that cell and the ones below it until array boundary
is reached
– Construct and check strings (and their reverses) made up of the
character in that cell and the ones to the right of it until array
boundary is reached
• What is the corresponding algorithm?
Corresponding Algorithm
Boggle(A: n X n array of characters)
For i=1 to n
For j=1 to n
temp ← make-string(A[i,j]…A[i,j])
if dict_lookup(temp)=T then print temp
For k=(i-1) to 1
temp ← make-string(A[i,j]…A[k,j])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For k=(j-1) to 1
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For k=(i+1) to n
temp ← make-string(A[i,j]…A[k,j])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
For k=(j+1) to n
temp ← make-string(A[i,j]…A[i,k])
if dict_lookup(temp)=T then print temp
temp ← string-reverse(temp)
if dict_lookup(temp)=T then print temp
Thinking Assignment
Make sure you
understand how/why
this algorithm
implements the same
strategy but with a
different approach
Same Algorithm Made More Efficient
Boggle(A: n X n array of characters)
Thinking
1 For i=1 to n
Assignment
2 For j=1 to n
Make sure you
3
temp ← make-string(A[i,j]…A[i,j])
4
if dict_lookup(temp)=T then print temp
understand how
5
For k=(i+1) to n
we get this
6
temp ← make-string(A[i,j]…A[k,j])
7
if dict_lookup(temp)=T then print temp algorithm from
the one on the
8
temp ← string-reverse(temp)
9
if dict_lookup(temp)=T then print temp previous slide
10
For k=(j+1) to n
and why this is
11
temp ← make-string(A[i,j]…A[i,k])
more efficient
12
if dict_lookup(temp)=T then print temp
13
temp ← string-reverse(temp)
14
if dict_lookup(temp)=T then print temp
Thinking Assignment Compute the efficiency
of this algorithm
Thinking Assignment
• Is this algorithm correct?
• Based on what you haver learned so far,
are you able to determine which of these
two algorithms implementing the same
strategy is more efficient?
• Are there other strategies/algorithms?
• Could those be more efficient?
Thinking Assignments
• Strategy # 2: So far we’ve created strings from the board and
looked these up in the dictionary. Instead, what if you go in the other
direction: get each full word from the dictionary and see if it is on the
board?
• Develop this strategy further and write down the corresponding
algorithm on paper. Assume the dictionary contains m words of
length at most n characters and the only function you have for
accessing it is get_next_word that will fetch the next word (or return
nil when all words have been fetched).
• Which strategy/algorithm is most efficient? Why?
• Can strategy 2 be made more efficient if the dictionary is organized
in a particular way and/or provided other functions? Which
functions? How much more efficient will this strategy become?
COMP 3270
Introduction to Algorithms
Homework 1
Due: June 7th , Friday by 11:59 PM (midnight)
Please submit as a PDF document using Canvas
Instructions:
1. This is an individual assignment, but you are encouraged to collaborate with others to
brainstorm and discuss potential solution strategies. However, you need to express and
document your answers on your own.
2. Think carefully; formulate your answers, and then write them out concisely using English,
logic, mathematics, and pseudocode (no programming language syntax).
3. Type your final answers in a Word (or Latex) document and submit online as a PDF
through Canvas.
4. Don’t turn in handwritten answers with scribbling, cross-outs, erasures, etc. If an answer
is unreadable, it will earn zero points. Neatly and cleanly handwritten submissions are
also acceptable.
(1. 5pts) Computational problem solving: Estimating problem solving time
Bill has an algorithm, find2D, to find an element x in an n × n array A. The algorithm find2D
iterates over the rows of A and calls the algorithm arrayFind (see below) on each one until
x is found or it has searched all rows of A. What is the worst-case running time of find2D in
terms of n? Explain. Is this a linear-time algorithm? Why or why not?
1
(2. 10pts) Computational problem solving: Problem specification
Problem Definition: Suppose you are asked to develop AI software to solve the problem of
placing 8 chess queens on an 8 × 8 chessboard so that no two queens attack each other.
Specify the problem to a level of detail that would allow you to develop solution strategies
and corresponding algorithms. State the problem specification in terms of (1) inputs, (2) discrete structures for data representation, and (3) desired outputs. No need to discuss solution strategies. You must use discrete structures (e.g., sets, arrays, relations, functions,
sequences, propositional logic, predicates, logical operators, and quantifiers). Each chess
queen has a position defined by a row and column number in the range [1, 8]. So, a position is
defined as a pair of row and column numbers. The row and column numbers cannot be outside
the range of the chessboard. You need to determine the input representation, the representation of the solution, and constraints that specify acceptable/valid solutions (e.g., what does it
mean for two chess queens not to be threats to each other and how can these conditions be
defined by logical and mathematical constraints imposed on their positions?)
(3. 10pts) Computational problem solving: Developing strategies
An array A contains n − 1 unique integers in the range [0, n − 1]; that is, there is one number
from this range that is not in A. Describe a strategy (not an algorithm) for finding that number.
You are allowed to use only a constant number of additional spaces beside the array A itself.
2
(4. 5pts) Computational problem solving: Developing strategies
Given a string, S, of n digits from 0 to 9, describe an efficient strategy for converting S into the
integer it represents.
(5. 10pts) Computational problem solving: Developing strategies
Explain a correct and efficient strategy to check what the maximum difference is between any
pair of numbers in an array containing n numbers. Your description should be such that the
strategy is clear, but at the same time, the description should be at the level of a strategy, not
an algorithm. Then state the total number of number pairs any algorithm using the strategy
“compute the difference between every number pair in the array and select that pair with the
largest difference” will have to consider as a function of n.
(6. 15pts) Computational problem solving: Understanding an algorithm and its strategy
• Explain what the above Mystery algorithm outputs and simulate its operation on a valid
input instance (e.g., an array of n elements – you can choose n to be 10)
• What is the approximate time complexity (running time) of the above algorithm (you can
use Big-Oh notation)
• How does the following algorithm improve the time complexity of the algorithm (what is
its strategy)? What is its time complexity?
3
(7. 10pts) Computational problem solving: Calculating approximate complexity
Using the approach described in class (L5-Complexity), calculate the approximate complexity
of the Mystery algorithm above (on page 3) by filling in the table below.
(8. 10pts) Calculate the detailed complexity T(n) of algorithm Mystery in the table below, then
determine the expression for T(n) and simplify it to produce a polynomial in n.
T(n) =
4
(9. 5pts) Computational problem solving: Proving correctness/incorrectness
Is the algorithm below correct or incorrect? Prove it! It is supposed to count the number of all
identical integers that appear consecutively in a file of integers. E.g., If f contains “1 2 3 3 3 4
3 5 6 6 7 8 8 8 8″ then the correct answer is 9.
Count(f: input file)
count, i, j : integer
count = 0
while (end-of-file(f) = false)
i = read-next-integer(f)
if (end-of-file(f) = false) then
j = read-next-integer(f)
if i=j then count = count+1
return count
(10. 5pts) Computational problem solving: Proving Correctness
Prove by induction that algorithm g is correct if it is intended to compute the function 3n − 4n ,
for all n ≥ 0
Function g(n: nonnegative integer)
if n = 0 then return (0)
else
if n = 1 then return (-1)
else
return (7*g(n-1)-12*g(n-2))
5
(11. 5pts) Computational problem solving: Proving Correctness
Complete the proof by loop invariant method to show that the following algorithm is correct.
Algorithm Max(A: Array[1..n] of integer)
begin
max = A[1]
for i=2 to n
if A[i] > max then max = A[i]
return max
end
Loop Invariant:
Initialization:
Maintenance:
Termination:
(12. 10pts) Computational problem solving: Algorithm Design
(a. 6pts) Describe a recursive algorithm to reverse a string that uses the strategy of swapping
the first and last characters and recursively reversing the rest of the string. Assume the string
is passed to the algorithm as an array A of characters, A[p..q], where the array has starting
index p and ending index q , and the length of the string is n = q − p + 1. The algorithm should
have only one base case, when it gets an empty string. Assume you have a swap(A[i], A[j])
function available that will swap the characters in cells i and j . Write the algorithm using
pseudocode without any programming language specific syntax. Your algorithm should be
correct as per the technical definition of correctness.
(b) (4pts) Draw your algorithm’s recursion tree on input string “i