(c) -P v P = true

(d) P v (Q V R) = (P v Q) V (P v R)

Sets

2.  Based on the definitions of the sets A and B , calculate the following:  IAI, IBI, A n B , A n B , A / B , B / A.

(a)  A = {1, 2, 6, 10} and B = {2, 4, 9, 10}

(b)  A = {x I x e N} and B = {x e N I x is even}

Relations and Functions

3.  For each of the following relations, indicate if it is reflexive, antireflexive, symmetric, antisymmetric, or transitive.

(a)  {(x, y) : x < y}

(b) {(x, y) : x > y}

(c)  {(x, y) : x < y}

(d)  {(x, y) : x = y}

4. For each of the following functions (assume that they are all f : Z → Z), indicate if it is surjective (onto), injective (one-to-one), or bijective.

(a)  f (x) = x

(b)  f (x) = 2x _ 3

(c)  f (x) = x2

5. Show that h(x) = g(f (x)) is a bijection if g(x) and f (x) are bijections.

(b) i31(n) i2  = n(n + 1)(2n + 1)/6

(c) i31(n) i3  = n2 (n + 1)2 /4

Graphs and Trees

7.  Give the adjacency matrix, adjacency list, edge list, and incidence matrix for the following graph.

8.  How many edges are there is a complete graph of size n? Prove by induction.

9. Draw all possible (unlabelled) trees with 4 nodes.

10. Show by induction that, for all trees, IEI = IV I _ 1.

Counting

11.  How many 3 digit pin codes are there?

12. What is the expression for the sum of the ith line (indexing starts at 1) of the following:

1

2 3

4 5 6

7 8 9 10

13.  A standard deck of 52 cards has 4 suits, and each suit has card number 1 (ace) to 10, a jack, a queen, and a king.  A standard poker hand has 5 cards.  For the following, how many ways can the described had be drawn from a standard deck.

(a)  A royal flush: all 5 cards have the same suit and are 10, jack, queen, king, ace.

(b) A straight flush: all 5 cards have the same suit and are in sequence, but not a royal flush.

(c) A flush: all 5 cards have the same suit, but not a royal or straight flush.

(d) Only one pair (2 of the 5 cards have the same number/rank, while the remaining 3 cards all have different numbers/ranks):

Proofs

14.  Show that 2x is even for all x e N.

(a)  By direct proof.

(b)  By contradiction.

15.For all x, y e R, show that Ix + yI < IxI + IyI.  (Hint: use proof by cases.)

Program Correctness (and invariants)

16.  For the following algorithms, describe the loop invariant(s) and prove that they are sound and complete.

Algorithm 1: findMin

Input: a: A non-empty array of integers (indexed starting at 1)

Output: The smallest element in the array

begin

min - o

for i - 1 to len(a) do

   if a[i] < min then

end

Recurrences

17.  Solve the following recurrences.

(a)  c_  = 1; cn  = cn − 1 + 4

(b) d_  = 4; dn  = 3 . dn − 1

Coding Question

Most assignments will have a coding question. You can code in C, C++, C#, Java, or Python. You will submit a Makefile and a source code file.

Makefile:   In the Makefile, there needs to be a build command and a run command. Below is a sample Makefile for a C++ program.  You will find this Makefile in assignment details.  Download the sample Makefile and edit it for your chosen programming language and code.

# Build   commands # Replace   g ++   - o # Java :

to   copy :

HelloWorld   HelloWord . cpp   below   with   the   appropriate   command .

#                 javac   source _ file . java

# Python :

build :

g ++   - o   HelloWorld   HelloWord . cpp

# Run   commands   to   copy :

# Replace   . / HelloWorld   below   with   the   appropriate   command .

HelloWorld Program Details   The input will start with a positive integer, giving the number of instances that follow.  For each instance, there will be a string.  For each string s, the program should

output Hello, s! on its own line.

A sample input is the following:

3

World

Marc

Owen