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