MAT2540 Discrete Structures and Algorithms II

1. Prove using induction: 1 + 3 + 5 +···+ (2n − 1) = n^2
2. Give a big-O estimate for the number of operations (where an operation is an addition or multiplication) used in this segment of an algorithm:

t:=0
for i:=1 to 3
for j:=1 to 4
t:=t+ij

Explain your answer.
3. Suppose that there are n = 2^k teams in an elimination
tournament, where there are n/2 games in the first round,
with the n/2 = 2^k−1 winners playing in the second round,
and so on. Develop a recurrence relation for the number
of rounds in the tournament.
4.  Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.
5. a) Let f(n) and g(n) be functions from the set of positive integers to the set of real numbers. State the definition of the fact that f(n) is O(g(n)).
b) Use your definition from (a) to prove that 1^2 + 2^2 + ……. + n^2 is O(n^3).

1. a) Using quick sort, sort 3, 5, 7, 8, 1, 9, 2, 4, 6. Show each step.
   b) Count the number of comparisons in 1a
2. a) Set up a binary tree for the following list, in the given order, using alphabetical ordering: SHE< SELLS< SEA SHELLS BY THE SEASHORE.
   b) How many comparisons with words in the tree are needed to determine if the word SHARK is in the tree? Explain your answer.
   c) How many comparisons with word in the tree are needed to determine if the word SHELLS is in the tree? Explain your answer.
3. a) Determine the codes for the letters d, i, o, t, u, and y if the coding scheme is represented by the following tree:
   d: 00
   i: 010
   o: 011
   t: 11000
   u: 11001
   y: 111
   b) given the coding scheme represented by the tree above, find the words represented by: 11101111001 0001000 01011000
4. a) Perform a depth first search to find a spanning tree for the graph, beginning at vertex A. Show each step
   b) Perform a breadth first search to find a spanning tree for the graph, beginning at vertex A. Show each step.
5. The map of New York State below shows cities and major highways. Distances between cities are indicated in miles. A major blizzard blankets the whole state in 40 feet of snow. Governor Cuomo is responsible for making sure there that every city can be accessed by a highway. He must decide the most efficient way to plow the stretches of highway, but he never took discrete math.
   a) Determine the stretches of highway that Governor Cuomo should plow so that all the cities are connected in the most efficient way. Indicate on the graph above.
   b) Write a short note to Governor Cuomo describing how you came up with your answer.
6. a) Let f(n) and g(n) be functions from the set of positive integers to the set of real numbers. State the definition of the fact that f(n) is O(g(n)).
   b) Use your definition from (a) to prove that 1^2 + 2^2 + ……. + n^2 is O(n^3).
7. Give a big O estimate for an increasing function “f” which satisfies for n = 2^k. f(n) = f(n/2) +1 with f(1) = 1.
8. Solve the recurrence relation:
   a_n = a_n-1 + 6a_n-2 for n >= 2 with initial conditions a₀ = 3 and a₁ = 6.

1.Describe an algorithm that takes as input a list of n integers and finds the location of the last even integer or returns 0 if there are no even integers on the list

2. Show that f(x)=x²+x+1 is O (x²)

3. Use mathematical induction to prove that the sum of the cubes of the first n positive integers in n²(n+1)²∖4

4. Solve the recurrence relation an = an-1+ 6 an-2  for n>=2 with initial conditions a0 = 3, a1 = 6

5.Give a big O estimate for an increasing function f which satisfies n=2^k,  f(n)=f(n/2)+1 with f(1)=1

6.Find a close form for the generating sequence  : 0 ,0, 3, -3, 3 ,-3, 3, -3

7.What is a minimum spanning tree?

8. Construct a binary tree with prefix codes representing these code schemes

d = 00

i = 010

o = 011

t = 11000

u = 11001

y =111

Final Exam Review 

Section 11.2 # 6

6. Howmany weighings of a balance scale are needed to find a lighter counterfeit coin among four coins? Describe an algorithm to find the lighter coin using this number of weighings.

Section 11.2 #8

∗8. How many weighings of a balance scale are needed to find a counterfeit coin among eight coins if the counterfeit coin is either heavier or lighter than the others?

Describe an algorithm to find the counterfeit coin using this number of weighings.

Section 11.2 # 12

∗12. Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.

11.2 # 38 Suppose that the first four moves of a tic-tac-toe game are as shown. Does the first player

(whose moves are marked by Xs) have a strategy that will always win?

Section 8.1 #2a

Find a recurrence relation for the number of permutations of a set with n elements.

Section 8.1 #8

1. Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0s.

1. What are the initial conditions?

1. c) How many bit strings of length seven contain three consecutive 0s?

Section 8.1 #14

1. Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0’s.

1. What are the initial conditions?

1. c) How many ternary strings of length six contain two consecutive 0s?

Section 8.1 #28

Show that the Fibonacci numbers satisfy the

recurrence relation f_n = 5f_n−4 + 3f_n−5 for n = 5, 6, 7, . . . , together with the initial conditions f₀ = 0, f₁ = 1, f₂ = 1, f₃ = 2, and f₄ = 3 Use this recurrence relation to show that f_5n is divisible by 5, for n = 1, 2, 3, . . . .

Section 8.2 #8

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years.

1. a) Find a recurrence relation for {L_n}, where L_n is the number of lobsters caught in year n, under the assumption for this model.

2. b) Find L_n if 100,000 lobsters were caught in year 1 and 300,000 were caught in year 2.

8.3 #14. Suppose that there are n = 2^k teams in an elimination tournament, where there are n/2 games in the first round, with the n/2 = 2^k−1 winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.

If there is only one team, then no rounds are needed, so the base case is R(l) = 0. Since it takes one round to cut the number of teams in half, we have R(n) = 1 + R(n/2).

8.3 #15.  How many rounds are in the elimination tournament described in Exercise 14 when there are 32 teams?

8.3 #16. Solve the recurrence relation for the number of rounds in the tournament described in Exercise 14.

8.4 #2. Find the generating function for the finite sequence 1, 4, 16, 64, 256.

5.1 #6  Prove that 1 · 1! + 2 · 2!+· · ·+n · n! = (n + 1)! – 1 whenever n is a positive integer.

5.1 #18 Let P(n) be the statement that n! < nⁿ, where n is an integer greater than 1.

1. a) What is the statement P(2)?
2. b) Show that P(2) is true, completing the basis step of the proof.
3. c) What is the inductive hypothesis?
4. d) What do you need to prove in the inductive step?

5.1 #18

1. e) Complete the inductive step.

f ) Explain why these steps show that this inequality is true whenever n is an

integer greater than 1.

5.2 #4 Let P(n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that P(n) is true for n ≥ 18.

1. a) Show statements P(18), P(19), P(20), and P(21) are true, completing the basis step of the proof.
2. b) What is the inductive hypothesis of the proof?

1. c) What do you need to prove in the inductive step?
2. d) Complete the inductive step for k ≥ 21.
3. e) Explain why these steps show that this statement is true whenever n ≥ 18.

5.2 #12 Use strong induction to show that every positive integer n can be

written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2⁰ =1, 2¹ =2, 2² =4, and so on. [Hint: For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.]

1. Describe in words how the binary search algorithm works and give a example how it works.
2. Use pseudo code to describe an algorithm for finding the largest and second largest element in a list
3. Build a binary search tree for the words, oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology in alphabetical order

4/5. Find the minimal spanning tree using both breadth first and depth search method starting at point A

1. 
   6. Show the step of a quick sort algorithm using the list 3,5,7,8,1,9,2,4,6
   7. consider the algorithm:
   procedure power (a: non zero real number, n: negativeness integer)
   if n = 0 then return 1
   else return a * power(a,n-1)

   what is the purpose of this code and prove that this algorithm is correct using induction.

Final Review

Good luck to everyone!

1)List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using

a) linear search.                                                                            b) binary search.

2)Show that xlog(x) is O(x^2) but that x^2 is not O(xlog(x)).

3)Construct a complete binary tree of height 4 and a complete 3-ary tree of height 3.

4) Using alphabetical order, construct a binary search tree for the words in the sentence “The quick brown fox jumps over the lazy dog.”

5) Solve these recurrence relations together with the initial conditions given:

a) an = 6an−1 − 8an−2 for n ≥2, a0 =4, a1 =10

b) an+2 =− 4an+1 + 5an for n ≥0, a0 =2, a1 =8

6) Suppose that f(n) = f(n/5)+3n^2 when n is a positive integer divisible by 5, and f(1) =4. Find               a) f(5)                                       b) f(125)                                      c) f(3125)

7)For each of these generating functions, provide a closed formula for the sequence it determines.

a) x^2 +3x +7+(1/(1−x^2))                                             b) [(x^4)/(1−x^4))]−x^3 −x^2 −x −1

8)Use induction to prove that 12 +32 +52 +···+(2n+1)2 = (n+1)(2n+1)(2n+3)/3 whenever n is a nonnegative integer.