**Instructor: **Dr. William DeMeo

**Office:** LeConte 314C

**Office Hours:** Wed, Thu, Fri 11–12

**Tentative Schedule **(updated 11/27)

**Course Outline:** We will cover as much as time permits of the following topics: propositional and predicate logic; proof techniques; recursion and recurrence relations; sets and combinatorics; functions, relations and matrices, lattices, graphs and trees.

Logic, proof techniques, and recursion provide the mathematical foundation for both writing a program and demonstrating its correctness. Sets, combinatorics, functions, relations, matrices and lattices comprise the most basic objects and relationships that are used in computer science. Graphs and trees can be used as models of many real world pheneomena, while also being amenable to computer programming.

The exam will cover the sections of the textbook from which homework problems were assigned.

I just finished preparing solutions to Exam 2. I will post these solutions now. (Be warned, there may be typos.) Unfortunately, I do not have time to do the same for Exam 1, as I must focus on creating the final exam for this and my other class. If you have questions about any of the Exam 1 problems, please post them here.

Dr. DeMeo,

Is the final cumulative, and if so, is it skewed more towards the chapters since the last test?

Dear Joseph, Yes the final is cumulative. It will not be intentionally skewed toward any particular chapter. However, since you have not been tested on graphs, you can be certain there will be a question about graphs.

I’m a little confused on how to read a given Hasse diagram. Ive looked at my notes and i’m still stuck. I’m looking over exam 2 question 9.Can you just generally explain how you would go about moving through the graph to get the ordered pairs?

Dear Clayton,

Good question. A partial order determines a Hasse diagram and, conversely, a Hasse diagram determines a partial order. To write down the partial order corresponding to a Hasse diagram, first note that for every node x in the diagram, the pair (x,x) belongs to , since is reflexive. The other pairs that belong to are pairs (x,y) such that x appears below y in the diagram.

For example, in Problem 9 part (a), is the set containing all pairs (x,x) for x in {0,1,2,3,4}, as well as the pairs (0,1), (0,2), (0,3), (0,4), (1,4), (2,4), (3,4).

Similarly, the answer to part b of question 9 is .

If any of this is confusing, please post another comment.

Dr. Demeo,

I remember you saying we had an assignment that we should start over Thanksgiving break (assignment 11 I presume), but I have been unable to find a homework handout, or the numbers listed in the schedule. Could you tell me the numbers or post the PDF handout?

Thanks,

Daniel Harper

Dear Daniel,

Thanks for the reminder. The updated schedule and HW11 pdf have been posted. Homework 11 is due on December 6. It is the last homework assignment.

Thank you, this cleared it up!

Professor DeMeo,

Can a set be (reflexive and and not reflexive) or ( symmetric and anti-symmetric) at the same time?

I am trying to determine whether the empty set is reflexive and symmetric or not, but I seem to find it symmetric and anti-symmetric, and reflexive and and not reflexive at the same time.

Dear Ibrahim,

For the properties that we have studied so far, the answer to your question is no, a binary relation cannot have a property and the negation of that property. So a binary relation defined on a given set cannot be both reflexive and not reflexive.

Note, however, that symmetry and antisymmetry are not negations of one another, and in fact it is possible for a relation to be both symmetric and antisymmetric. Example: The relation {(1,1)} on the natural numbers.

If you carefully consider the definitions of these properties, the empty set relation should not cause difficulty.

Recall that a binary relation on a set S is reflexive if the following holds:

If happens to be the empty set, and if S happens to be nonempty, then what can you say about the implication above? Is it true? If so, the empty set is reflexive. If the implication above is not true, then the empty set is not reflexive. (What if the set S is empty? Would this change your answer? It’s important to note that the answers to these questions depend both on the relation and the set on which it’s defined.)

As for the symmetric property, the definition is

Consider the antecedent and consequent of the implication above, and then consider whether the implication is true when is the empty set. Similarly, for antisymmetry, look carefully at the definition of this property to decide if the empty set has it. As with many of our homework problems, this one is merely checking your understanding of the definitions.

I am not sure I am remembering the question correctly, but getting the number of even divisions you can make to a size n set. Should be n – phi(n). Where phi is eulers totient function. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers I wouldn’t be surprised if this is wrong but it makes sense to me.

Dear Brian, I’m not sure to which question you are referring. The “extra credit” question was about the number of partitions of the set {0, 1, 2, …, n-1} that have “uniform blocks.”

One example of such a partition is |0,1|2,3|4,5|…|n-2,n-1| (assuming n is even). If n is divisible by 3, here’s another example: |0,2,4|1,3,5|6,8,10|…|n-5,n-3,n-1|. Note also that |0,1|2,3| and |2,3|0,1| and |3,2|0,1| etc are all the same partition of the set {0,1,2,3}. That is, we don’t care about ordering of the blocks or ordering within blocks. On the other hand, |0,1|2,3| and |0,2|1,3| are distinct partitions.

Given n, you want to count the number of partitions with uniform blocks. You must consider all possible block sizes. To develop your intuition, start with some small n and work out the answer. Then work out the answer for general n, and then write a formal proof that your answer is correct.

A few more observations/hints: if n is prime, then the answer is 2. (Why?) If n > 1 and n is not prime, then the answer is even bigger than , where n = rm. (You should verify this.) This number is quite large, and certainly much bigger than n. For example, when n=16, r=2, m=8, this number is about 2 million.

You suggested that the answer might be n – phi(n). While this is not correct, it is true that you will need to consider all pairs of positive integers r and m such that n = rm. That is, you will consider the set of positive integers that evenly divide n, which is related to the phi(n) function, but you don’t need to refer to the phi(n) function in your answer, and special knowledge about this function is not needed.

By the way, the extra credit problem is an opportunity for you to try to develop your own counting ability and intuition. You might, for example, try to apply the multinomial counting principle that we learned in class. Please resist the temptation to look up the answer, or to look for references on the internet for background that you might feel you are missing. You already have the tools necessary to answer this question. I suspect a clear answer with an explanation is not available on the internet, and even if it is, credit will only be given if you provide your own proof that makes it clear to me that your answer is correct. If you decide to write a computer program to answer this, that’s okay, but it is probably more work than necessary, since you will also have to supply a proof that your program is correct and that it answers the question.

Thanks for your comment. Please post again if you have other ideas, questions, or comments.

I was look at the tentative schedule and it says that the next HW is due on 11/14 which is a Thursday. That is obviously not right. Is it due next Friday ?

Dear Ibrahim, Thanks for bringing this to my attention. As you note, the dates were messed up. This has been fixed. Also, a pdf for HW 9 (problems from Section 4.1) is now posted. We will get through most of Section 4.1 on Monday.

On homework problem 3.1.7.c,

I am looking at the part (y even –> x != y).

Does this mean “if y is even, then x != y” ?

Yes, that’s correct.

I’m reviewing Proof of Correctness on Ch 1.6. On 1.6.11, When reading over the answer sheet, it says that the first hoare triple is true automatically because the antecedent is true. Is that not supposed to be that the antecedent is false? The preconditions are x=7, x<= 0, which is a contradiction. I'm just trying to make sure I've figured this out.

Yes, you are correct. That must be a typo. If the antecendent is *false* then the implication is true.

The following question was just emailed to me (please post questions like this here).

Question: “Are you going to give us the logic rules and the formulas from last chapter in the test or we are to supposed to memorize them?”

Answer: “The logic rules required for the exam will be the ones that have come up most often in class and in the homework. I expect you to know these by now.”

Professor DeMeo,

In problem 2.5.40, it asks us to prove the recurrence relation. Maybe my vocabulary is off, but I has assumed we had to prove S(n) = x, but the problem only gives n=2^m and the domain of n. What am I supposed to show?

I’m working on the homework for Section 2.4. I don’t really have a firm grasp of this, so I’m trying to figure out how to begin with the base step(s). For instance, problem #12 starts n at 6. But the function is recursive with values of n < 6. I'm not really sure what values those are, since F(1) or F(2) doesn't seem to be defined.

Would it be possible to meet in your office before the Homework is due?

Sorry, this keeps changing login profile. This is student Joseph McDowell

The Fibonacci sequence is defined in Example 30 on page 130. In particular, it tells you F(1) = F(2) = 1. Also, Example 31 on the same page demonstrates how to prove a statement about the Fibonacci sequence, which is what you have to do in Problem 2.4.6.

Of course we can meet in my office before the homework is due. Please send me an email to set up a time, or come to office hours on Wednesday.

I’m going over section 2.3, playing catch-up. I’m confused about how to find Q. This is the loop invariant, right? But for problem 1, the only locally declared variables are i and j, and they are both changed through the loop. Would Q be x^2 for x=> 1?

You are given

Qin problem 2.3.1. Perhaps it’s hard to notice because it appears after the problem statement. It says,Q: j = i. Let me know if you’re still having trouble.^{2}Running into issues with Proof by Induction. Despite the lecture today, I’m still having a rough time getting through any of the induction steps. I imagine there’s some algebraic rearranging required, but I’m not sure what direction go with.

It’s hard for me to reply to your post, since I’m not sure what part of the induction step is causing trouble. Please come to my office hour so I can help you, or post a more specific question that I can answer. Also, it’s better to use your real name when posting, so we can communicate directly. Thanks!

Ah, sorry. Unfortunately, a lot of classes overlap the office hours.

40b is an example, or really anything with inequalities. At the induction step, I’m not sure how to algebraically prove the inequality. …other than using an infinite sum to prove that at any n, the sum is less than 2 (if that’s really a proof). But I don’t believe that’s in the spirit of the lesson. I’m reading through the section in the book and having a rather hard time finding any good example that’s similar.

I will try to make it to your office hours tomorrow. I have a lab until about 10:30.

Hi Dr. Demeo

where exactly can we find the slides that you lectured from a few classes ago?

Dear Ibrahim, I forgot to post the slides! Thank you for the reminder. They are now posted on the Handouts page.