## Description

Logic

1. Using a truth table, show the equivalence of the following statements.

(a) P ∨ (¬P ∧ Q) ≡ P ∨ Q

(b) ¬P ∨ ¬Q ≡ ¬(P ∧ Q)

CS 577 Assignment 1 – Discrete Review

(c) ¬P ∨ P ≡ true

(d) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

Page 2 of 15

CS 577 Assignment 1 – Discrete Review

Sets

2. Based on the definitions of the sets A and B, calculate the following: |A|, |B|, A ∪ B, A ∩ B, A \ B,

B \ A.

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

(b) A = {x | x ∈ N} and B = {x ∈ N | 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}

Page 3 of 15

CS 577 Assignment 1 – Discrete Review

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

Page 4 of 15

CS 577 Assignment 1 – Discrete Review

Induction

6. Prove the following by induction.

(a) !n

i=1 i = n(n + 1)/2

(b) !n

i=1 i

2 = n(n + 1)(2n + 1)/6

(c) !n

i=1 i

3 = n2(n + 1)2/4

Page 5 of 15

CS 577 Assignment 1 – Discrete Review

Graphs and Trees

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

1 2

5 3

4

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

Page 6 of 15

CS 577 Assignment 1 – Discrete Review

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

10. Show by induction that, for all trees, |E| = |V | − 1.

Page 7 of 15

CS 577 Assignment 1 – Discrete Review

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

Page 8 of 15

CS 577 Assignment 1 – Discrete Review

Proofs

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

(a) By direct proof.

(b) By contradiction.

15. For all x, y ∈ R, show that |x + y| ≤ |x| + |y|. (Hint: use proof by cases.)

Page 9 of 15

CS 577 Assignment 1 – Discrete Review

Program Correctness (and invariants)

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

(a)

Algorithm 1: findMin

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

Output: The smallest element in the array

begin

min ← ∞

for i ← 1 to len(a) do

if a[i] < min then min ← a[i] end end return min end Page 10 of 15 CS 577 Assignment 1 – Discrete Review (b) Algorithm 2: InsertionSort Input: a: A non-empty array of integers (indexed starting at 1) Output: a sorted from largest to smallest begin for i ← 2 to len(a) do val ← a[i] for j ← 1 to i − 1 do if val > a[j] then

shift a[j..i − 1] to a[j + 1..i]

a[j] ← val

break

end

end

end

return a

end

Page 11 of 15

CS 577 Assignment 1 – Discrete Review

17. Solve the following recurrences.

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

(b) d0 = 4; dn = 3 · dn−1

Page 12 of 15

CS 577 Assignment 1 – Discrete Review S

(c) T(1) = 1; T(n) = 2T(n/2) + n (An upper bound is sufficient.)

(d) f(1) = 1; f(n) = !n−1

1 (i · f(i))

(Hint: compute f(n + 1) − f(n) for n > 1)

Page 13 of 15

CS 577 Assignment 1 – Discrete Review

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 to copy :

# Replace g++ -o HelloWorld HelloWord . cpp below with the appropriate command .

# Java :

# javac source_file . java

# Python :

# echo ” Nothing to compile .”

#C#:

# mcs -out : exec_name source_file .cs

#C:

# gcc -o exec_name source_file .c

#C ++:

# g++ -o exec_name source_file . cpp

build :

g++ -o HelloWorld HelloWord . cpp

# Run commands to copy :

# Replace ./ HelloWorld below with the appropriate command .

# Java :

# java source_file

# Python 3:

# python3 source_file .py

#C#:

# mono exec_name

#C/C ++:

# ./ exec_name

run :

./ HelloWorld

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

The output for the sample input should be the following:

Page 14 of 15

CS 577 Assignment 1 – Discrete Review

Hello, World!

Hello, Marc!

Hello, Owen!

CS 577 Page 15 of 15