CS 577 Assignment 1 – Discrete Review solution

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 Spring 2022
(c) ¬P ∨ P ≡ true
(d) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
Page 2 of 15
CS 577 Assignment 1 – Discrete Review Spring 2022
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 Spring 2022
(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 Spring 2022 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 Spring 2022 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 Spring 2022 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 Spring 2022 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 Spring 2022 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 Spring 2022 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 Spring 2022 (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 Spring 2022
Recurrences
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 Spring 2022
(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 Spring 2022
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 Spring 2022
Hello, World!
Hello, Marc!
Hello, Owen!
Page 15 of 15