Problems
- HW01-Problems (updated 9/1: fixed Problem 1.2.43; due 9/6)
- HW02-Problems (updated 9/15: fixed Problem 1.3.18; due 9/16)
- HW03-Problems (updated 9/18: fixed Problem 1.6.12; due 9/23)
- HW04-Problems (updated 9/24; due 10/02)
- HW05-Problems (due 10/09)
- HW06-Problems (due 10/16)
- HW07-Problems (updated 10/30: to include 3.2 probs; due 11/01)
- HW08-Problems (due 11/08)
- HW09-Problems (due 11/15)
- HW10-Problems (due 11/20 by midnight)
- HW11-Problems (due 12/06)
Attention: The solutions to homework problems are no longer posted since the class has finished, so the links below will not work. If you were a student in the class and would like the solutions, please post a message in the comment box below.
Solutions
- HW01-Solutions (updated 9/12: fixed typo in solution to 1.2.44)
- HW02-Solutions (updated 9/19: fixed typo in solution to 1.4.7)
- HW03-Solutions (updated 9/24)
- HW04-Solutions
- HW05-Solutions (updated 12/09: added solution for Problem 2.2.41)
- HW06-Solutions (updated 10/22: added solutions for Sec 2.6)
- HW07-Solutions (updated 11/09: added solutions for Sec 3.2)
- HW08-Solutions
- HW09-Solutions
- HW10-Solutions
- HW11-Solutions
William DeMeo 
Dr. DeMeo,
Can you explain the first problem on HW 6 on expanding the Fibonacci numbers. This is how I’m attempting to do it.
F(N) = F(n-1) + F(n-2)
F(n-1) = F(n-2) + F(n-3)
F(n-2) = F(n-3) + F(n-4)
sub back in
F(N) = [F(n-2) + F(n-3)] + [F(n-3) + F(n-4)]
now this is where I get stuck.***
would I sub n-1 and n-2 back in? and get
F(n-1) = [F(n-3) + F(n-4)] + [F(n-4) + F(n-5)]
and for F(n-2) = [F(n-4) + F(n-5)] + [F(n-5) + F(n-6)]
sub
{[F(n-3) + F(n-4)]} + {[F(n-4) + F(n-5)]} + {[F(n-4) + F(n-5)]} + {[F(n-5) + F(n-6)]} but it isn’t matching up
Thanks
Dear Clayton,
I’m not sure what you mean by “sub n-1 and n-2 back in” and “it isn’t matching up.” However, in your last line you are almost there. Look at the expression you are trying to prove. How does it differ from your last line? Did you really want to expand the last F(n-4) as the sum of F(n-5) + F(n-6), or should you just leave it as F(n-4). I think if you leave it as F(n-4), you will find that you already have the right answer (once you collect like terms).
By the way, my solution to this problem is written up and posted online. Please consult it for guidance. If there’s something about my solution that’s confusing to you, please post again.
Hi Dr. Demeo! I am looking at question 2b from exam 1. And I am not sure how to solve it. I couldn’t find any similar homework problem to that question. Can you please help me briefly explain it ? Thanks!
Dear Truc, Please see the textbook. This problem is answered in the penultimate paragraph on page 67. If, after reading that section and thinking some more about it, you still have questions, please feel free to post again.
This is what I got. Line 1 becomes E(y,x) /\ A(x) –> Pr(x)
with line 2 E(b,fi)
the resolution is A(fi) –> Pr(fi) equivalent to [A(fi)] ‘ \/ Pr(fi)
with line 3 A(fi)
the resolution is Pr(fi)
Does this look right for you ?
Dr. DeMeo,
I was trying my own problems similar to HW 11, second problem.
Lets say g(x) = x^3/3 and f(x) = 3x^3 + 2x
so c1*g(x) <= f(x) <= c2*g(x)
lets choose c1 = 3 to cancel the denominator.
3*x^3/3 = x^3 <= 3x^3 + 2x
subtract x^3 to get 0 <= 2x^3 + 2x
subtract 2x to get -2x <= 2x^3
divide by 2x to get -1 <= x^2
what would Nsubzero be? wouldn't all x squared be greater or equal to -1?
I guess i'm asking how to find Nsubzero
Thanks
Yes, for the functions you have defined, the first inequality you are after is very easy to satisfy. In fact, you could have chosen c1=1, and the inequality would be satisfied for all x>0. (We only consider positive x values for these problems.)
As for the other inequality, you have to work a little bit harder. Try to find a c2 and N such that, if x>N, then f(x) is less or equal c2*g(x). If you still have trouble determining a good N for this problem, after thinking about this some more, please post again. (Note: there is no single correct answer. If a given N works, then so does every N’ greater than N.)
This what I tried,
C2 = 12
so…
= 3x^3 + 2x <= 4x^3Edit: please don’t write it this way; i.e. don’t use an equals symbol when you mean “is equivalent to” or “holds if and only if”. Instead, write:
holds if and only if
Now, subtracting 3x^3 from both sides,
Dividing both sides by x, we have
2 = 2so I could use c1 = 3 and c2 = 12 but i’m still wondering what Nsubzero is what should this be? 2 or 3?
Yes, you can set
, if you like, since it’s clear that, for 
we have 
. But you can also define 
. The point is that you don’t have to find the “best” N. You only have to find an N that works. I.e., you must find an N so that, if x>N, then the desired inequalities are satisfied. You could have chosen N=100… Though that might seem like an odd, or unnecessarily conservative choice to make, it’s not incorrect.
I’m a bit confused about HW#3, 1.5.10.b
Where the answer provided is which(x: capital(x,y) and small(y)) …but at the top of the solution, it says capital(x,y) “x is the capital of y”. Wouldn’t y need to be a state, so in this case it should be small(x)? Or perhaps I am missing something?
Dear Joseph, You are correct. This is a typo.
Can you post some sort of solution for HW 5 number 41? I don’t have the solution in my notes.
I added a solution for that problem.
For HW03 1.6.12, I know the Hoare triples are:
1.
2.
But I am not quite sure the first two statements of the bottom up approaches are equivalent. That is, I don’t know whether
and 
are equivalent.
Dear Ming,
Yes, the conditions
and 
are equivalent. (Do you see why? One holds if and only if the other holds.)
If that doesn't answer your question, please post again.
I will revise your post for you, on the assumption that I have correctly understood what you are asking. If the result, which will show up in a few minutes, is not what you meant, please post again.
Professor DeMeo,
Would this be a correct proof for solving a postage stamp problem? I understand this method clearer than others I’ve seen.
Claim: Every amount of postage of 12 cents or greater can be made by using 4 or 5 cent stamps?
Proof:
Base Case: S(12) = 4+4+4 = 12.
S(13) = 5+4+4 = 13.
S(14) = 5+5+4 = 14.
S(15) = 5+5+5 = 15.
Induction Step:
Need to show k+1.
Since I showed postage up to 15 cents can be made in the base step, then (k+1 >=16, k+1-4>=12)
From induction hypothesis we can make ((k+1)-4) postage using m 4 cent stamps and n 5 cent stamps for some natural numbers m and n.
In other words…
((k+1)-4) = 4m + 5n
= k+1 = 4m + 4 + 5n
= k+1 = 4(m+1) +5n
So, k+1 postage greater than 12 cents can be made using (m+1) 4 cent stamps and n 5 cent stamps, which is what we need to show.
QED
Dear Clayton,
Yes, your proof is essentially correct, though the wording could be better. In particular, “Need to show k+1” is not how one begins an induction step. Always begin an induction step with “Fix an integer n greater than or equal to c.” (In the present example c is 15). Then the induction hypothesis will be the assumption that the claim holds for all k between m and n. (In the present example, m is 12.) Then prove the claim holds for n+1.
If you look at the Homework 5 solutions posted above, you will see that your proof is essentially the same as the one that I give in my solution to Problem 2.2.70. However, I think my wording is clearer. Please read my solution and compare it to yours, and consider how it makes the proof clearer.
Can you post a set of hw problems similar to the set that was given for the second exam? I’m meeting with someone, going over the questions today.
Dear Kevin,
I am quite busy creating two final exams right now, as well as writing up solutions to your second exam, as requested by a number of your classmates. (These solutions will be posted soon.) So, unfortunately, I don’t have time to create a list of suggested review problems. However, there are plenty of exercises in the textbook that are similar to the problems on Exam 2.
My apologies, I forgot to reply to your response. You answered the request via email yesterday. I was only asking for a list of problems to focus on while studying.
No problem.
Dr. DeMeo,
I’m having some trouble understanding the definition of Isomorphic graphs. In 5.1.12, all of the graphs contain the same number of nodes, with the same degrees and the same number of edges. The only thing that seems to change is the position of the nodes. Is that what makes a difference here?
In addition, is there a function that describes/establishes isomorphism?
Dear Joseph, I believed we covered your questions in office hours, but if you have anymore concerns, please post them.
For 4.4.6 Letter A wouldn’t the answer be true because every single value in the domain must be mapped to a value in the co-domain?
Good question. You must take the word “means” literally. The statement in question is
“An onto function means that every element in the domain must have an image.”
That is, the claim is that this is the definition of an onto function, which is false. This property—that every element in the domain must have an image—is part of the definition of “function,” and certainly all onto functions have this property. But this property is not the definition of “onto.”
Dr. DeMeo,
Can you explain the rules for finding cardinality in sets like {a, {null}, null}? I went over the review notes, but I didn’t really get a firm grasp of this. Stuff like why the cardinality of set {a, {a,{a}}} is 2 and not 3.
Also in 3.1.13, I’m not sure if I’m doing this right. Is null set a subset of C, an element of C, or both? Does an element need curly braces in order to be a subset?
The empty set is a subset of every set. In 3.1.13, it also happens to be an element of C. (The empty set is not an element of every set.)
Dear Joe,
The cardinality of a finite set is the number of elements in the set. For example, the set { a, {a, {a}} } has two elements, namely the element a and the element {a, {a}}. (The second element, {a, {a}}, happens to look like a set, but all elements of all sets are themselves sets; even the first element, a, represents some set.)
Dr. DeMeo,
On 4.1.46 on the homework, I set up a refinement of
to be two blocks of two numbers from 
that are each split into two block to total 4. I’m not sure what to do when showing it is a partial ordering of all partitions of S. So I need to write out all possible partitions of S and put it in a hasse diagram?
Dear Joe,
For this one, you don’t want to talk about specific sets or specific partitions on those sets. You want to prove that, in general, refinement is a partial order on the set of all partitions of some set. So you need to check that refinement satisfies the definition of a partial order. You can assume refinement is a binary relation, but you need to check that it is reflexive, antisymmetric, and transitive.
To get you started with the reflexive property, let
denote the set of all partitions of some set. We must prove
where
denotes the refinement relation. (This implication is very easy to check, based on the definition of 
, but you still must check it.) After you prove that 
is reflexive, then do the same for antisymmetry, then transitivity. (Transitivity and antisymmetry are also easy, but be careful with antisymmetry, and write a rigorous proof showing that refinement satisfies the definition of these properties.)
Dr. DeMeo,
With the antisymmetric property, does this fit all cases that are not symmetric, or does it specifically need a kind of ordered pair? The consequent seems to mean we would need a ordered pair like (13,13).
Dear Joseph, Recall that an implication will be true if the antecedent is false. So, no, antisymmetry does not require pairs that satisfy its consequent. For example, the relation
on the integers is antisymmetric.
Dr. DeMeo,
When making the closure on a property of a relation, is there a specific way it should be written out? I just went with ” closure S* on S is {…}” . Does this need a more detailed answer?
I meant to say “[Property] closure S* on S is {…}”
Dr. DeMeo,
I’m trying to figure out how to set up combinations where I’m looking for specific objects to be in the combination. Like, “How many ways can you have only a pair of cards in a poker hand?” Or “How many different ways can you have a flush?”.
Actually the second example question wasn’t really what I meant. I’m on problem 3.4.27 and I’m trying to think of how to structure this combination problem, and others similar to it. Thank you for your help.
Dear Joseph, I’m not sure what you mean by “have only a pair of cards in a poker hand.” As for Prob 3.4.27, that one asks for the number of 5-card hands that have one card from each suit. One way to think about it is that there will be one suit that appears twice in the hand. The other three suits each appear exactly once. (Think about why this must be.) So, you choose the suit that will appear twice (4 ways), then you select 2 cards of that suit (C(13,2) ways), now select the remaining 3 cards, one card from each suit (C(13,1)=13 ways in each case). Use the multiplication principle to put it all together in your final answer. Let me know if you have more questions.
Dr. DeMeo,
I’m going over HW 3.4.9. It seems this is a combination problem, with 19 different people and 19 different seats. So, it would seem, “19, choose 19”. Which when I put into the formula C(19, 19) it ends up as 19!/19! = 1
This can’t be right. Any idea what I could be doing wrong?
Dear Joseph, The question asks, “In how many different ways can you seat 11 men and 8 women in a row?” You can imagine there are 19 seats numbered 1 to 19, from left to right, say. You have 19 individuals. You will select one of them to sit in seat 1, another in seat 2, and so on. In how many ways can you do this? (The fact that some are men and some women doesn’t matter for this problem, though it will matter in other problems.) The number of ways to seat the 19 individuals is the same as the number of ways to arrange 19 distinct objects in a row. (So this is a permutation problem, not a combination problem.) Let me know if it’s still not clear.
Once you solve that problem, here’s a related question to think about: What if we can only distinguish men from women, but within one gender the individuals are indistinguishable? In how many different ways can we seat them in a row? Can you see how to answer this by modifying your answer to the question above? (Hint: Consider the number of ways in which 11 men can be ordered, and the number of ways in which 8 women can be ordered. Each of these orderings gave distinct seating arrangements in the first version of the problem.)
Dr DeMeo, I just noticed a disagreement between the schedule and the homework PDF. On the PDF it says to do number 13 a-f, but on the schedule it says 13 a-i, so I was just wondering which one was correct.
I also noticed that on the schedule there are two homework 6 listings and no homework 8 listing.
Dear Matt, You should do 13a–f. Thanks for letting me know about the homework numbering typo. It is fixed now.
Will you still be posting the solutions for the last two homeworks (homeworks 5 and 6) for study purposes before the exam tomorrow?
Dear Michael, Solutions to hw 5 are now posted. HW 6 solutions will be posted within the next two hours.
Solutions for hw 6 Sections 2.4 and 2.5 are up. The file will be updated to include Section 2.6 solutions by early afternoon.
All solutions for hw 6 are now posted.
There was a problem with hw 5. It only provides solutions to the Sec 2.2 problems. I am adding the Sec 2.3 solutions now. Should be up within the hour. Sorry about that.
All solutions for hw 5 are now posted.
HI Dr. Demeo!
I don’t see file for HW05. I also want to know when it will due. Thanks!
Dear Truc,
The homework assignments and due dates are posted in the tentative schedule, as usual. The next homework is due this Wednesday. I suggest you get started on it right away, if you haven’t already. Do not wait for a pdf. I might not make one this week. If I do, it will be posted this evening.
Prof. DeMeo, do you plan on being in your office tomorrow before class? I’ve been having consistent difficulty finding how to prove correctness on program segments with conditionals.
I will be available tomorrow from 11 to noon. If that time doesn’t work for you, please email me directly so we can set up an appointment.
Did you look for me in my office? I’m here now. If you still need help, please let me know. (I tried contacting you at the email address you submitted. Not sure it’s valid. Please use at least your real last name in posts in the future, so I know how to contact you.) Thanks.
Hi Dr. Demeo
for question 1.3.18, what is in the PDF is different than what is in the book in ‘d’ and ‘f’.
Do you want us to go with what is in the book?
Dear Ibrahim, Thank you for noticing the typos. They have been fixed. Yes, please go with what is in the book.
thank you
When is the second homework due? It is not posted in the PDF or in the description
As stated in the Tentative Schedule (see link above and on the main webpage), the second homework is due on Friday the 13th. I have updated the pdf file so that it now indicates the due date.
For Homework1, based on the textbook, problem 43 at section 1.2 should read:
The crop is good, but there is not enough water. If there is a lot of rain or NOT a lot of sun, then there is enough water. Therefore, the crop is good and there is a lot of sun.
You are correct. Thank you for noticing this. I have updated the pdf file.
For the homework, should we print out the problems PDF and do the work on it (since there appear to be spaces to do so), or should we do it on a separate sheet of paper?
Either option is acceptable, as long as you write neatly and staple your pages together before submitting them. (By the way, I was in the bookstore at Russell House today and noticed they sell mini staplers for $4—a great investment!)
I’ll be doing it on the PDF sheet then, since my hand writing isn’t exactly neat. I did get one of those mini staplers the other day too. Thanks.
I guess you could say (“You use the PDF” \/ “You use your own paper”) → (“You write legibly” /\ “You staple the pages”).
haha… not quite, more like “your hw is acceptible” –> (“you use the PDF” \/ “you use your own paper”) /\ “you write legibly” /\ “you staple the pages”. That is, these are necessary (but not sufficient) conditions for an acceptable hw submission. (For example, I left off “you submit it before the deadline,” also a necessary condition.)