Discrete Mathematics
03/23/2014
Math 203
Colorado Technical University (Online)
Part I: Look up a roulette wheel diagram. The following sets are defined: * A = the set of red numbers * B = the set of black numbers * C = the set of green numbers * D = the set of even numbers * E = the set of odd numbers * F = {1,2,3,4,5,6,7,8,9,10,11,12}
Answers:
* AUB {All BLACK and RED numbers} * A∩D {All numbers that are both RED and EVEN} * B∩C {NO numbers intersect between these two sets} * CUE {All ODD numbers and 00, 0} * B∩F {2,4,6,10,11} * E∩F {1,3,5,7,9,11}
Part II: The implementation of the program that runs the game involves testing. One of the necessary tests is to see if the …show more content…
Rule 1: E —› p
Rule 2: E —› q
Rule 3: E —› r
Rule 4: E —› E + E
Rule 5: E —› E – E
Rule 6: E —› E X E
Rule 7: E —› E/E
Rule 8: E —›(E)
(i). Use the above grammar to derive the string given by the mathematical expression E = (p + q) X p – r X p/(q + q) * E * E * E * E * E * E * E * E/E * (E) * E * E/E * (E + E) * E * E/E * (P+E) * E * E /E * (P + Q) * E * E/E * (P +Q) * (E0 * E/E * (P + Q) * (E  E) * E/E * (P + Q) * (P  R) * E/E * (P + Q) * (P  R) * P/E * (P + Q) * (P  R) * P/(E + E) * (P + Q) * (P  R) * P/(Q + E) * (P + Q) * (P  R) * P/(Q + Q) (ii.) Provide a Parse tree for the derivation. E
E

Q
Q
Q
E
+
+
E
E
Q
P
E
E
E

E
(E)
P
E
(E)
/
*
E
E
E
E
*
Part V: Algorithm Analysis * Consider searching algorithms on the following array of data:
[22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13]
Suppose you want to implement a searching algorithm to see if the data set contains the number 19. Demonstrate how the search would go if you used: * A sequential search starts with the first number and goes in order to the last number. It will take until the element number 12 find match * A binary search is always used on the sorted array.
State the runtime for each of the searches, in this example, and for general data sets of size n. Address the issue of the order of the