Grades are official!

Your official grades have been submitted to the registrar. You can now see grades for all items in Blackboard’s Gradebook, including grades for individual components of your project. Parts 1(a), 1(b), and 1(c) are each out of 10; Part 2 is out of 50, and Part 3 is out of 20. Your extra-credit homework grade is out of 5. Participation is out of 10; it is made up of your in-class participation and your OpenLab participation, each grades out of 5. Everything else that’s new should be a grade out of 100. Your lowest test and lowest quiz grades were dropped (not included in the calculation).

For a reminder of the grading scheme, check here. Interestingly enough, only one person’s grades satisfied the conditions for the proposed alternative grading scheme announced a few weeks ago in class and, even so, that person’s letter grade was unaffected. This means that the original grading scheme was used to calculate everyone’s grade.

Overall, your projects were done quite well. I do have a few thoughts about the projects that I may share on the OpenLab in the next couple of days, before I forget all of them, so you can check back here. Some of you got pretty creative with the assignment!

Not everyone will be receiving the overall grade he or she had hoped for at the beginning of the semester, but I hope none of you are discouraged! Some of the topics we tackled this semester were pretty tough and you all made a valiant effort. Please keep this in mind as you tackle tough topics in the future…if you keep picking away at them, eventually things will become clear…and sometimes it takes a while!

Best wishes for the future. Keep me posted on all the wonderful things you get up to!

HAVE A GREAT SUMMER!

Posted in Uncategorized | Leave a comment

Hints/reminders from today’s class

As announced in class today…

  • There were be fewer questions on the final than on the term tests. Each of the questions will be somewhat involved; some have two parts and some have three or four. The more involved or longer questions from the term tests are good models for the exam questions.
  • Because of this, you’ll have to understand the topics in a deep way, not just in a superficial way. Some of the questions include definitions, which you should have memorized by now, but most of the others will require some thinking to complete.
  • You will have some choice about which questions to answer (like you did on Test #3). None of the questions are mandatory so it’s completely up to you which one to skip.
  • A few of the exam questions are taken directly from the term tests. One is taken directly from last week’s worksheets.
  • I posted solutions to Test #1 questions way back when it was returned. I did not post solutions to Test #2 or Test #3 questions. (I am not interested in your trying to memorize my solutions and then feed them back to me; I’d rather see that you understand something.) However, you may post your own solutions here for extra participation credit. Depending on the timing, I may or may not get a chance to comment on them myself, but you are all welcome to discuss each others’ work.
  • You are also welcome to post solutions to any (and all) of the final exam reviews that your classmates have posted. Whether you share your solutions or not, you are encouraged to use these questions as practice! Don’t forget to practice the tougher questions multiple times.

Good luck with your final exam prep for this class and your other classes. Plan to arrive *early* on Wednesday. See you then!

Posted in Uncategorized | 1 Comment

Final exam review – Carlos Paredes

Final test review - Carlos Paredes

Posted in Final Exam Review | 1 Comment

Final Exam Review

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).

Posted in Final Exam Review | 2 Comments

Final Review

  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 = 2k. f(n) = f(n/2) +1 with f(1) = 1.
  8. Solve the recurrence relation:
    an = an-1 + 6an-2 for n >= 2 with initial conditions a0 = 3 and a1 = 6.
Posted in Final Exam Review | Leave a comment

Final Review. Francisco Tamay

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

                                                                   

 

 

Posted in Final Exam Review | Leave a comment

Final Exam Review .MarkE

Final Exam Review 

Section 11.2 # 6

  1. 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 fn = 5fn−4 + 3fn−5 for n = 5, 6, 7, . . . , together with the initial conditions f0 = 0, f1 = 1, f2 = 1, f3 = 2, and f4 = 3 Use this recurrence relation to show that f5n 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 {Ln}, where Ln is the number of lobsters caught in year n, under the assumption for this model.

 

  1. b) Find Ln 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 = 2k teams in an elimination tournament, where there are n/2 games in the first round, with the n/2 = 2k−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! < nn, 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 20 =1, 21 =2, 22 =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.]

 

 

 

 

 

 

 

 

 

 

 

 

Posted in Final Exam Review | Leave a comment

Benjamin Lin final review

  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.

Posted in Final Exam Review | Leave a comment

Angel Garcia – Final Review

Final Review

 

Good luck to everyone!

Posted in Final Exam Review | Leave a comment

Final Exam Review

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.

Posted in Final Exam Review | 1 Comment