CSRU 1100 Structures of Computer Science



CISC 1100 Structures of Computer Science

Dr. Weiss

Spring 2011 Practice Final Exam Solutions

Name: _____________________________________________________

This is a closed book, closed note, closed calculator, exam. You will have 75 minutes to complete the exam. Show your work for non-trivial problems so that you can get partial credit for wrong answers.

Terminology:

Z = All Integers = {…-2, -1, 0, 1, 2…}

N = Natural Numbers = {0, 1, 2, 3, 4, 5, …}

P(A) = Power Set of A

Ac is the set complement of A

|AND |( |

|OR |v |

|IMPLIES |( |

|NOT |( |

|Problem |Points |Topic |Score |

|1 |8 |Sets | |

|2 |7 |Sets | |

|3 |3 |Sets | |

|4 |11 |Sequence | |

|5 |15 |Logic | |

|6 |16 |Probability | |

|7 |16 |Counting | |

|8 |15 |Algorithms | |

|9 |9 |Algorithms | |

|Total |100 | | |

Score: ______ out of 8

1) Consider the following three sets when answering the parts below. U, the universal set, represents all of the subjects taught at Mary’s (somewhat limited) university.

T = {English, History, Math, Science} T represents subjects Mary is taking

I = {History, Journalism, Math} I represents subjects Mary finds Interesting

U = {English, History, Journalism, Math, Psychology, Science, Spanish}

a. T ( I = {History, Math}_________________

b. T – I = {English, Science}_______________

c. P(I) = { {}, {History}, {Journalism}, {Math}, {History, Journalism}, {History, Math}, {Journalism, Math}, {History, Journalism, Math}}

d. IC = {English, Psychology, Science, Spanish}____________________

Score: ______ out of 7

2) If in classroom there are 20 people who speak Spanish, 12 who speak French, and 6 who speak both Spanish and French, then how many people speak Spanish or French (i.e., one of the two languages or both of the languages)?

Answer: ________ people speak Spanish or French

Make sure you show any work below

|S| = 20 |F| = 12 |S ( F| = 6 what is |S U F|?

|S U F| = |S| + |F| - |S ( F| = 20 + 12 – 6 = 26

Score: ______ out of 3

3) For each of the following parts, there is only one answer. The answer does not depend on the specific contents of A and you need to answer generally, in terms of A and any of the operators that we learned about, if appropriate. See the sample answer for guidance.

Example: A ( AC = ? Answer: {}

a. A – AC = A

b. (AC)C = A

c. U – A = AC

Score: ______ out of 11

4) Insert the missing number in the sequence below and then provide a closed and recursive formula that describes the sequence.

1, 3, 5, 7, 9

Recursive:

a1 = 1

an = an-1 + 2

Closed:

an = 2n -1

Score: ______ out of 15

5) Write out the truth table to determine if the equivalence shown below holds. Do not apply more than one operator at a time. Also, circle the correct answer below to indicate if it holds or not.

[(a ( b) ( (c] ( a ≡ a

The equivalence (circle one): holds does not hold

|a |b |c |(a ( b) |(c |(a ( b) ( (c |[(a ( b) ( (c] ( a |

|T |T |T |T |F |T |T |

|T |T |F |T |T |T |T |

|T |F |T |T |F |T |T |

|T |F |F |T |T |T |T |

|F |T |T |T |F |T |F |

|F |T |F |T |T |T |F |

|F |F |T |F |F |F |T |

|F |F |F |F |T |T |F |

Score: ______ out of 16

6) Answer the following 4 parts given that you have one fair 7-sided die. Please show all of your work for full credit and to have any chance of partial credit!

a. What is the probability that you roll once and get an odd number?

P = |E|/|S| E={1, 3, 5, 7} so |E| = 4 and we know |S| = 7 so P = 4/7

b. What is the probability that I roll the die 3 times and get the same value on all 3 rolls?

P=second and third rolls match first = 1/7 x 1/7 = 1/49

Alternatively, P=|E|/|S|, where |E| = 7 (all 1’s, all 2’s, .. all 7’s) and |S| = 73

So, P = 7/73 = 1/49

c. What is the probability that I roll the die 7 times and get the following sequence of values (in order): 1, 2, 3, 4, 5, 6, 7?

P = |E|/|S|, where |E| = 1 and |S| = 77. So P = 1/77

d. What is the probability that I roll the die 3 times and do not roll a 6,6,6?

P(not 666) = 1 – P(666). P(666) = 1/73 so answer is 1 - 1/73 = 342/343

Score: ______ out of 16

7) You need to create a committee of 7 people from a pool of 30 possible committee members, of which 20 are women and 10 are men. Determine the total number of ways to form each committee, based on the conditions specified below. You need not simplify your answer.

a) How many ways are there to form a committee of 7 people?

C(30,7) = 30!/(23! x 7!)

b) If the committee has a chairman but the remaining 6 members all serve equally, then how many ways are there to form the 7 person committee?

C(30,1) x C(29,6) or

P(30,1) x C(29,3) or

30 x 29!/(26!3!)

c) If 4 of the committee members must be women and the remaining 3 must be men, then how many 7 person committees can be formed?

C(20,4) x C(10,3)

d) If a coed committee is not permitted (no mixing of men and women), then how many 7 person committees can be formed?

C(20,7) + C(10,7)

Score: ______ out of 15

8) Apply the binary search algorithm to the following sorted list, where the value you are searching for is 34.

(1 5 6 8 12 22 34)

The binary search algorithm is provided below. In your answer, specify the values of min, max, and midpoint for each iteration of the repeat loop (lines 2 -4). That is, show how the algorithm operates, just as was done for the homework.

Binary Search Algorithm: finds the value x in the list L with n items

1. Initialize min = 1 and max = n

2. Repeat until min > max

3. midpoint = ½ (min + max) always round down if a fractional value

4. Compare x to L[midpoint]

(a) if x = L[midpoint] then return “FOUND”

(b) if x > L[midpoint] then min= midpoint + 1

(c) if x < L[midpoint] then max = midpoint - 1

5. return “NOT FOUND”

After you are done, determine the list values that get checked (line 4), in the order they were checked, and list them here: _8, 22, 34_____________________________

Show your work below. I provide the template for you to fill in for each iteration. I may have provided more iterations than you will need. Just stop when you are done. Remember that

Min and Max are positions in the list, not list values.

Iteration 1 Iteration 2

Min = 1 Min = 5

Max = 7 Max = 7

Midpoint = 4 Midpoint = 6.5 rounded to 6

Iteration 3 Iteration 4

Min = 7 Min =

Max = 7 Max =

Midpoint = 7 Midpoint =

Iteration 5 Iteration 6

Min = Min =

Max = Max =

Midpoint = Midpoint =

Score: ______ out of 9

9) Answer the following short questions about algorithms.

a. Which of the following two sorting algorithms is quicker in terms of the number of comparisons required? Circle one: Mergesort Bubblesort

b. Algorithms did not exist prior to the development of modern digital computer. Circle one: True False

c. What did the term “computer” originally refer to? Answer below with a single sentence.

It referred to humans who performed long calculations

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download