CS 577 Assignment 1 – Discrete Review Fall 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS 577
Assignment 1 – Discrete Review
Fall 2022
Logic
1. Using a truth table, show the equivalence of the following statements.
(a) P v (-P A Q) = P v Q
(b) -P v -Q = -(P A Q)
(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.
Induction
6. Prove the following by induction.
(a) i31(n) i = n(n + 1)/2
(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
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 a[j] - val break end end end return a end |
Recurrences
17. Solve the following recurrences.
(a) c_ = 1; cn = cn − 1 + 4
(b) d_ = 4; dn = 3 . dn − 1
(c) T (1) = 1; T (n) = 2T (n/2) + n (An upper bound is sufficient.)
(d) f(1) = 1; f(n) = 1(n) − 1 (i . f(i))
(Hint: compute f(n + 1) _ f(n) for n > 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 :
# |
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 |
# Rust : |
|
# |
rustc source _ file . rs |
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 |
# Rust : |
|
# |
. / source _ file |
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:
Hello, World!
Hello, Marc!
Hello, Owen!
2022-09-15