Here are topics and exercises to review for the final exam:

• truth tables (and related definitions of satisfiability, unsatisfiability, tautologies)
  • Exam #1: Exercises #1 & #2
  • Exam #4: Exercise #5(a)
  • Quiz #1: Exercise #2
• set operations (union, intersection, power set, Cartesian product):
  • Exam #2: Exercises #2 & #4
• proofs (direct & indirect):
  • Exam #2: Exercises #1
  • Exam #4: Exercise #5(b)
  • Quiz #3
• recurrence relations:
  • Quiz #4: Exercise #2
  • Exam #3: Exercise #4
• algorithms:
  • Quiz #4: Exercise #1
  • Exam #3: Exercises #2 & #3
  • Exam #4: Exercise #3

If you need another copy of the take-home exam I handed out in class today, you can download it from Files.

The take-home exam is due at the beginning of class next Monday, Dec 17.  We will use Monday to review for the final exam (reminder: the final exam will be next Wednesday, Dec 19).

As I said in class, you should download the previous exam and quiz solutions I have posted over the course of the semester. Studying those solutions will help you with the take-home exam, and also help you start preparing for the final exam.

If you get stuck on the take-home exam, look for related examples & exercises on the previous exams & quizzes, in the textbook, on the homework assignments and in your class notes.

I will be in my office (N724) to answer questions about related examples & exercises during these extra office hours:

• Thursday, Dec 13: 10a-11:45a
• Friday, Dec 14: 12p-2p

You can also post questions to the Discussion page, and I will reply to them there.

The following topics will be covered on Exam #3, which will be on Wednesday, Nov 28:

• Algorithms:
  • work on HW#6
  • read Sec 3.1, pp194-198: review linear search, binary search, bubble sort, insertion sort
  • review Quiz #4 (questions #1 & #2)
• Functions (domain/range, one-to-one & onto functions):
  • review Exam #2, questions #2(c) & #4
  • review Sec 2.3: Examples 3-4, 8-15
  • exercises from HW#5: Sec 2.3, #5(a)(b), 10, 11
• Recurrence relations:
  • review Sec 2.4: Examples 5–8
  • exercises from HW#5: Sec 2.4, #10(a)(b) [also try #9(a)(b) & #11(a)(b)]
  • review Quiz #4 (question #3)

Use a proof by contradiction to show that the sum of an irrational number and a rational number is irrational (using the definitions of rational and irrational real numbers; cf p85 of the textbook, or your notes).

Theorem: If $r$ is an irrational number and $s$ is a rational number, then $latex r+s$ is irrational.

Proof: For a proof by contradiction, assume that the hypotheses are true (i.e., that $r$ is irrational and $s$ is  rational) but that the conclusion is false, i.e., $r+s$ is not irrational.

That means $r+s$ is rational, and so by the definition of rational numbers, $r + s = a/b$ for integers $a, b$.

Then $r = (a/b) – s$.  There are two cases for $s$:

(i) $s$ is irrational: this contradicts the hypothesis that s is rational.

(ii) $s$ is rational: then $s = c/d$ for integers $c, d$. But then

$$r = (a/b) – s = (a/b) – (c/d) = (ad – bc)/bd$$

meaning r is rational.  But that contradicts the hypothesis that r is irrational.

Since we get a contra

Let’s prove the statement “The square of any odd integer is also odd.”

First we restate the theorem in a way that will lead us towards the proof, by introducing a variable $n$ into the statement of the theorem to represent “any (given) odd integer”:

Theorem: If $n$ is odd, then $n^2$ is also odd.

In order to prove this, we will need the definition of what it means for a integer to be odd:

Definition: An integer $n$ is odd if $n = 2k+1$ for some integer $k$.

Proof of theorem: Assume $n$ is an odd integer.  Therefore, by definition, $n = 2k+1$ for some $k$.  Then $$n^2 = n*n = (2k+1)(2k+1) = 4k^2 + 2k + 2k + 1 = 4k^2 + 4k + 1 = 2( 2k^2 + 2k ) + 1$$ 

This shows that $n^2$ is odd, since $n^2 = 2j + 1$, where $j = 2k^2 + 2k$, so $n^2$ satisfies the definition of being odd.

We will use the programming language python later in the semester for some programming projects. Python has the advantage of being relatively easy to get started with.

You should do the following:

1. Create an account on trinket.io, which is a browser-based coding environment that is designed for teaching and coursework.
2. Take a look at one of their introductions to python, such as
   • https://hourofpython.trinket.io/a-visual-introduction-to-python
   • https://docs.trinket.io/getting-started-with-python
3. Since we are going to be talking about (mathematical) sets, get familiar with Python’s sets (e.g., see https://www.geeksforgeeks.org/sets-in-python/)

The CityTech Math Club has a speaker give a presentation most Thursdays. The first talk of this semester will be this Thursday (Sept 20) at 12:50pm in N720.  This week’s talk will be given by one of our math faculty, on a topic that involves discrete math, and has applications to computer science (specifically the branch of artificial intelligence called machine learning).  In fact, the talk will include some python programming (which is the programming language we will use later in the semester!)

Since this topic is so relevant to our course, you can earn a “participation point” by attending this talk.  I will be at the talk to verify attendance. 

(Recall that 5% of your final grade will come from attendance & participation; you can earn 1% by attending this talk. I will announce numerous other ways to earn participation points in class; by earning at least 5 such points you will get the full 5%.)

Here is the talk abstract:

Abstract: Suppose you have 5 pieces of fruit whose size, color, and label (the type of fruit it is) are known. Given the size and color of an unlabeled piece of fruit, is it possible to classify it given our previous observations? How sure can we be that we are right? This is a kind of classification problem.

Decision trees (used in machine learning) can be used to help with these types of problems. In this talk we will discuss how to construct a decision tree by hand and how to use the scikit-learn python module to create decision trees for larger data sets.