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