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
- 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:
- 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)
See this python trinket here which implements linear search (a translation of the pseudocode found in the textbook: see slide 9 here).
And see here for a python trinket which implements binary search–again, a translation of the pseudocode found in the textbook: see slides 10-12.
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:
- Create an account on trinket.io, which is a browser-based coding environment that is designed for teaching and coursework.
- Take a look at one of their introductions to python, such as
- 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/)
A reminder that we will have Exam #1 this Wednesday (Oct 3). The exam will cover Sections 1.1-1.6.
See below for a list of HW exercises from those sections to review (as well as some additional exercises that you can work through for additional review). You should also review Quizzes #1 & #2 (solutions have been posted to Files).
- Sec 1.1 (Propositional Logic):
- #10, 14, 32
- in addition review “exclusive-or”: pp5-6, #32(c)
- Sec 1.3 (Propositional Equivalences):
- #9, 10 (tautologies using truth tables)
- in addition: review “satisfiability”: pp30-31, #61
- Sec 1.4 (Predicates & Quantifiers):
- Sec 1.5 (Nested Quantifiers):
- from HW#3: #4(b)(d), 10(a)-(c), 30(a)-(d)
- Sec 1.6 (Rules of Inference):
- read pp72-73
- from HW#3: #5, 6 (similar to Examples 3-6)
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:
Speaker: Dr. Johann Thiel
Date/Room: Thursday September 20, 2018, 12:50-2:00pm, Namm 720
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.