Archived Class

Charles Cusack
Computer Science
Hope College

All Homework

Comments for all assignments

Exercises taken from Discrete Mathematics and its Applications, Seventh Edition unless otherwise noted.
You must show all of your work for each problem!
Points will be deducted if you do not show all of your work.
Each problem is generally worth 10 points. Problems with multiple parts may be assigned more points if there are enough parts or each part is significant enough.
The Review Questions are always related to the section that will be discussed on the assignment due date.

Homework 1

Section Problem
1.1 10ceg
1.1 14cef
N/A The questions below

This question is worth double. Answer the following questions based on the course website. For each one, give an answer and specify which link on the left you clicked to get the information. For instance, your answer for one might be:

      45. Certainly (Gradebook)

Each question is worth 1 point, right or wrong.

How many assignments can you turn in late?
If you turn in an assignment 2 minutes into the class, is it late?
What percentage of your grade are exams? What percent is each exam?
If you want to see me in my office, what should you do?
If you want to submit anonymous feedback, can you? How?
Does neatness/organization of homework matter at all?
Do I have to show all of my work on homework problems, whether or not the problem says so?
Can you tell exactly what grade you got on any assignment in the course at any time? Can you get an idea of how your grade compares with the grade of others?
If you have a disability of any kind, what should you do?
Will I give extra credit assignments to students who are not performing well in the course?
What is the reading assignment for Monday?
At exactly what time are homework assignments due (be precise)?
How many problems are on Homework 4?
Is there class on Friday? Is it required?
What dates are the exams? Do you plan on being in class on those days?
Is reading the textbook optional?
Is attending department colloquiums required? How many? What day/time are they usually?
Are there any solutions available for the exercises in the book? If so, where?
What should you do after every homework assignment is handed back?
What is the earliest possible date and time you can leave Hope College at the end of the semester?

Homework 2

Section Problems Notes
1.1 18
1.1 32ae
1.2 8
1.2 10
Review Questions 4ab On page 111

Homework 3

Section Problem notes
1.1 20
28 Phrases these using the same language that is in the original.
36f Show intermediate columns and list the variable columns and rows in the same order as the examples in the textbook.
1.3 10d See previous comment. Also, explain why the truth table justifies your answer.
14 Clearly justify your answer.
16 Read the paragraph before the problem.
Review Questions 6 On page 111

Homework 4

Section Problem Comments
1.1 42 Remember to say something to justify your answers. It doesn't have to be much.
1.2 18 Clearly justify your answer(s).
1.4 4 Briefly explain each.
8 One of these is tricky. Think carefully.
50 Define a universe of discourse and choose statements P and Q on that universe such that the given statements have different truth values. Notice that 49 is similar...

Homework 5

Section Problem Notes
1.3 22 Read the paragraph before the problem and do the problem according to the directions given there.
1.4 14 Justify your answers by providing an example, counter example, and/or brief explanation.
1.6 8 Express the statements using predicates, quantifiers, and logical connectives (e.g. negation, and, or). Then identify the rules used.
16 Clearly state whether or not the argument is correct and give the specific rule(s) of inference or fallacy used.
Review Question 10a On page 111.

Homework 6

Section Problems Notes
1.2 40 Look at #41 to see what sort of answer it is looking for.
1.3 58 Briefly describe how you arrived at your answer.
1.4 32 See the solution to #33 for an example of what it is asking for. In particular, for each one you need to:
Specify the domain and define appropriate predicate(s).
Express the statement using your predicate(s) and the appropriate quantifier(s).
Negate the expression and then move the negation as far to the right as you can.
Express the negation in English, phrasing it "nicely".
(This one is worth 20 points)
1.7 2 Be very precise, using the definition of even (In particular, you cannot not say, for instance, that 10x+14y-6z+12 is even. You must use algebra to make it look like 2k for some integer k. Similarly for future problems with either odd or even.). A common mistake on this kind of proof is to write it in such a way that you are essentially assuming the two numbers are the same number without realizing it.
16 As with the previous problem, make sure you don't construct a proof that only ends up proving it for m=n.
Review Question 12 On page 111

Homework 7

Section Problem Notes
1.1 22
1.3 30 Begin by realizing that it can only be false if the premise is true but the conclusion is false. Then argue that if the conclusion is false, the premise is, too.
1.4 56
1.7 18 Take the assumption that n is an integer as a given, and read the problem as "If 3n+2 is even, then n is even."
1.8 6 Make sure to use the official definitions of odd and even throughout the proof. Also, the phrase about opposite parity simply means that one is odd and the other is even.

Homework 8

Section Problem Notes
1.3 28 Read the paragraph before the problem.
1.4 44
1.6adf 10
1.7 32 Three keys to this problem: First, you need each to be equivalent to the others. This will require 3 or 4 mini-proofs, depending on how you go about it. Second, you do not start all of the mini-proofs by assuming x is rational. Finally, you must use the formal definition of rational throughout your proof.
1.8 30 Make sure you consider every possibility.
36 There is in some sense an obvious number to try. That is, given two distinct numbers, there is one number that you can be certain is between them. The trick is then to prove that this number is irrational. If it isn't clear how to do that, what sort of proof comes to mind?
Review Question 1 On page 186
3 On page 186

Homework 9

Section Problem Notes
1.2 42
1.3 44 Read the paragraph before problem 43. Use the result of Problem 43. In other words, you just need to show that you can implement ∨ using ¬ and ∧.
1.7 24
2.1 16 In case it isn't clear, give a single diagram showing the relationship between A, B, and C.
28
36
2.2 4 If the answer to any of these is A or B, say so.

Homework 10

Section Problem Notes
1.1 44 Show intermediate results
1.6 20 Explain why or why not, specifying rules of inference/fallacies.
1.8 8+addition Read carefully. It says "not exceeding it", so the number itself should be included. The addition is to answer the same problem, but with the phrase "not exceeding it" replaced with "less than it".
2.2 12 Use a "set containment proof". See Examples 10 and 12. Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
16a See note for the previous problem.
2.3 8abcd
12+addition Also specify whether each is onto. For both one-to-one and onto, justify.

Homework 11

Section Problem Notes
1.4 36
1.7 38 Clearly show why your counterexample works. Also, read the problem carefully so you do not come up with a false counterexample.
2.1 30 Prove your conclusion.
2.2 16e Use a "set containment proof". Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
2.3 20 N is the set of natural numbers ({0, 1, 2, ...}). Also, when part c says "different than the identity", it means it cannot always map a number to itself, regardless of what the function looks like. So functions like f(x)=⌊x⌋ or f(x)=2*(x/2) don't count.
36 Make sure you clearly indicate which answer is which.
2.4 4ad
16b
26bh Do not give a recursive formula. I should be able to determine a₁₀₀ by just plugging in 100, for instance. Assume the first term is a_1.
32c Make sure to show your work.
34b Make sure to show your work.
40 Make sure to show your work.

Homework 12

Section Problem Notes
2.2 26c
2.3 56
58
2.4 26a
Review Question 1ab On page 378

Homework 13

Section Problem Notes
2.2 24 You may use any of the valid techniques from the book.
2.4 26e Do not give a recursive formula. I should be able to determine a₁₀₀ by just plugging in 100, for instance. Assume the first term is a₁. If you are having a hard time with this, try adding or subtracting 1 from the term and seeing if the numbers look more familiar. Then you should be able to determine a formula.
32d
34d
5.1 4 This problem is much easier if you assume P(k-1) and show P(k).
50

Homework 14

Section Problem Notes
1.6 24
2.4 16e
5.1 6 Look at the solutions to similar problems (e.g. #5, #7)
18 Look at the solution to problem #19
5.2 4 Look at problem #3 and the solution in the back of the book.

Homework 15

Section Problem Notes
1.4 10
2.3 38 Your answer should be one or more equations that relate the constants (e.g. ab=c+d). An answer that gives an example of specific values of constants that work is not enough.
5.1 10 It should be a very simple formula.
5.2 8 Your answer should be something of the form "For $5n, where n≥a" for some integer a (which you need to find). Then you will need strong induction to prove it. This is probably one of the more confusing problems, but look for the solutions of the similar ones in the book for some help.
10 I will give you the answer to the first part: It is always n-1 breaks. For the inductive step, don't over think it. When you break the chocolate the first time, just make up sizes it breaks into (e.g. one piece will be size i (where i is at least 1), and the other then has to be what?). Strong induction makes this pretty straightforward.
30
32

Homework 16

Section Problem Notes
1.3 62b Clearly justify your answer.
5.1 20 Don't make this one harder than it is. It is fairly straightforward.
5.3 8ab For b: recursive definitions do not always have to be based on the immediately preceding term.
12 Recall that f₀=0 and f₁=1. This one should not be too difficult if you use the correct proof technique.
24a The empty string (λ) is a palindrome.
38
Review Question 1 On page 439

Homework 17

Section Problem Notes
1.1 36e For old time's sake.
5.1 12 This one involves some tricky algebra.
5.3 8cd
24b
6.1 10
12
40 You do not have to write out the equivalent decimal expression for this one (Josh).
Review Question 6 On page 440

Homework 18

Section Problem Notes
1.4 52 Briefly justify/explain your answer for each.
5.3 18 Aⁿ is A multiplied by itself n times. If you need a refresher on how to multiply matrices, ask me or look at section 2.6.
6.1 32 Do not make these ones harder than they are. Also, do not simplify your answers. For examples, 26³ or 26*25*24 are acceptable.
56 You do not need to simplify your answer.
8.5 8
20
6.2 16 Justify/Explain your answer.
Review Question 10 On page 440

Homework 19

Section Problem Comments
1.3 18 Read the paragraph before this group of problems.
6.1 14
60
6.2 12 x mod 5 is the remainder when x is divided by 5. So, for instance, 13 mod 5 = 8 mod 5.
26 The easiest way to show this is to give a graph where the vertices are people and edges indicates friendship. Then you need to argue why your example suffices.
34
6.3 8
22

Homework 20

Section Problem Comments
1.7 10
5.3 40 This one can be tricky. Make sure you don't miss any possibilities.
6.3 24
30
6.4 4

Homework 21

Section Problem Notes
1.8 14 This one is really easy if you try some examples. You will quickly discover whether or not it is true.
2.4 16f Recall that sometimes you are better off not multiplying everything out as you go. Also, this one might be more clear if you work downward.
6.3 38
Review Question 2 On page 634

Homework 22

Section Problem
2.2 14
6.1 46
8.5 14
6.4 8
9.1 4
12
28
34aceg

Homework 23

Section Problem
1.8 16
5.1 56
6.3 16
9.3 4c
8c
14ab

Homework 24

Section Problem Notes
2.2 16c
6.1 74 Read the problem very carefully. Also, if you are able to write the decimal representation of the answer to d on less than 100 sheets of paper, you don't have the correct answer.
6.2 36
9.3 18c
32
9.5 12
36c
Review Question 1 On page 844

Homework 25

Section Problem Notes
2.3 20
5.3 14
6.4 6
9.3 22
9.5 16 You need to prove that the relation has the three required properties. The complicated thing about this problem is the notation--the relation is ordered pairs of ordered pairs. This might help you think about it correctly: One thing you need to show is that if ((a,b), (c,d)) is in R, then ((c,d), (a,b)) is in R.
46
12.1 4a
6c
12

Homework 26

Section Problem Notes
6.2 40 Don't use induction. There is a much easier way to think about it. (Hint: What section if this in?)
6.4 28
9.1 34b
36b
9.5 44
12.1 2
12.2 2b
6