Discrete Structures

**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin

Class Time: **T TH at** **Busn**** 209**

· Contact Dr. Lin in advance to set up an appointment.

· Monday to Thursday: 8:30am~10:30am.

Course Syllabus: compact version

**About the reading reports:**

· **Effort (2
points):** How much time have you
spent for the reading? What percentage of the contents in the reading do you
think you understand? Have you come to the class this week? **Assessment**: The student is
expected to **(i)** have attended the
class this week at least once (0.5 point), and**(ii) have either **gained
a good understanding of **80% or more of the contents** **or** have
spent at least **three hours** in the reading (1.5 points).

· **Reflection on
the reading (2 points)**: Put down 1~2 paragraphs of your thoughts such as notes of new
insight you gained, interesting things encountered, questions of things you
don’t understand, and so forth.** ****Assessment**: the student is
expected to show substantial evidence of understanding or effort of trying to
understand the contents in the reading.

*****************************************************************************************************

**Week 1: Introduction
to Propositional Logic**

- Reading
#1, due Thursday,
**Feb. 9****:**(i) Carefully read Sections 1.1 and 1.3 in Discrete*Mathematics and Its Applications*, 7th Ed. Submit your report online under Canvas. (ii) Read Section 1.2 if it takes**less than****3 hours**for you to read 1.1 and 1.3 in (i). **Homework #1,**Thursday,**Feb. 9****: Please click here**to download**propositional logic.**Either**hand in your work on paper**in the class or**scan and upload an electronic version**under Canvas.**Clarification on Homework #1****:**(i) For problem #1 and #3, your compound proposition should only be composed of the three atomic propositions D4, D100 and D400, parentheses as needed, and the logic operators ˄, ˅, and ̚ as needed. Don’t use other logic operators. (ii) For problem #5, please do include 8 rows in the truth table, corresponding to all the 8 possible combinations of truth values for three independent atomic propositions. Do so even though the truth values D4, D100 and D400 are dependent and some of the 8 combinations could not happen.

******************************************************************************************************* **** **

**Week ****2:
Algebraic Laws and Logical Equivalence in Propositional Logic**

- Reading #2, due Thursday,
**Feb. 16****:**(i) Review Sections 1.1 and 1.3 in Discrete*Mathematics and Its Applications*, 7th Ed. again. (ii) Read Section 1.2 and Section 1.4. **Homework #2,**due Thursday,**Feb. 16****: Please click here**to download**propositional logic**.

Showcase: An Eclipse logic program for solving Sudoku puzzles

******************************************************************************************************* **** **

**Week ****3:
Introduction to Predicate Logic. **

- Reading #3, due Thursday,
**Feb. 23****:**Read Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #3**, due Thursday,**March. 2****: Please click here**to download**predicate logic**.

** **** **

**Week ****4:
Predicate Logic, Rules of Inference, and Basics of Proofs****.
**

- Reading #4, due Thursday,
**March. 2****:**(i) Review Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. if you need more exposure to familiar with predicate logic. (ii) Read Sections 1.6-1.8 if you are confident about Sections 1.4 and 1.5.

** **** **

**Week ****5:
Review on Logic. **

- Reading #5, due Thursday,
**March. 9****:**(i) Review Sections 1,1, 1.3, 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed.to prepare for Test #1. (ii) Read Sections 1.6-1.8.

**Test #1** on Logic (in-class
open-book test), Thursday,
**Mar. 9****: **(i)
Cover all the things from Reading #1 Reading #4 on
logic. (ii) Make sure you understand the all the
homework problems and the related concepts very well. (iii) Make sure you
understand the algebraic laws and logic equivalence
depicted in Tables 6, 7, and 8 in Section 1.3
and are capable of using them for determining logic equivalence.

** **** **

**Week 6 and Week 7: Sets, Set
Operations, and Proofs
| Mission Conference
Mar. 15~17**

- Reading
#6, due Thursday, Mar. 16 (extended to Monday May 20)
**:****(i) Required**: Sections 2.1-2.2 in Discrete*Mathematics and Its Applications*, 7th Ed. (ii)**Optional**if you are interested: Sections 12.1-12.3 in Discrete*Mathematics and Its Applications*, 7th Ed.

- Reading #7 due Thursday,
**Mar. 23****:**Review Sections 2.1-2.2 and Sections 1.6-1.8 in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework
#4 due Thursday,
**Mar. 23****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 8: More on Sets, Set Operations, and Proofs | ****Basics of
Counting **

- Reading
#8 due Thursday,
**Mar. 30****:**Read Sections 6.1, 6.3 and 8.5 in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework #5
**Mar. 30 (****submission open till April 6 without penalty)****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 9: Basics of
Counting **

- Reading
#9 due Thursday,
**April 6****: Re-read****Sections 6.1, 6.3 and 8.5 one more time**in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework
#6
**: Please click here**Homework #6 on**counting and derangement,**due Thursday, April 13**(submission open till Tuesday, April 25 without penalty)****.**

**Test #2** on Logic and Sets (in-class
open-book test), Tuesday,
**April 11****: **

·
**Range**: Cover all the things from
Reading #1 to Reading #7 on logic and sets. Make
sure you understand all the problems in Homework#1~Homework#5. There are 43
questions in total, leading to 43 points in total. Getting 33 points would be
considered as 100%.

·
**On predicate logic**: Make sure you review the
concepts of predicate logic needed for doing **Problem#3 in Homework #3**. You need
to understand the algebraic laws and logic equivalence
depicted in Tables 6, 7, and 8 in Section 1.3
and are capable of using them for determining logic equivalence.

·
**On sets**: Make sure you review the
related concepts needed for doing Homework #4 and Problem #1 in Homework #5.
You need to be able to reason about the subset relationship among sets, set
equality, and the use of logic behind them. It would be helpful if you
understand set identities depicted in Table 1 in Section 2.2 and are capable of using them
to reason about the equality of sets.

** **** **

**Weeks 10-11: Binomial
Coefficients + Relations **

- Reading
#10 due Thursday,
**April 27****:**Read**Sections 6.1~6.4**(note that 6.2 & 6.4 are new) in Discrete*Mathematics and Its Applications*, 7th Ed. - Reading
#11 due Thursday,
**May 4****:**Read**Sections 9.1 – 9.3**on relations in Discrete*Mathematics and Its Applications*, 7th Ed.

- Homework
#7
**: Please click here**Homework #7 on**counting,**due Thursday, May 4.

**Week 12:** **Counting and Discrete
Probability.**

- Reading
#12
**:**Read Sections 7.1~7.2, 7.4 in Discrete*Mathematics and Its Applications*, 7th Ed. due Thursday, May 11. - Homework #8
**: Please click here**Homework #8 on**counting and probability,**Thursday, May 18.

**Week 13:** **Big O Notation + Algorithms and Complexity.**

Reading #13**:** due
Thursday, May 18.

- Carefully
read Section 3.2 on the growth of functions and the big O notation in Discrete
*Mathematics and Its Applications*, 7th Ed. - Browse through Section 3.1 on algorithms and Section 3.3 on complexity.

**Week 14:** **More on** **Big O Notation +
Algorithms and Complexity.**

Bonus Reading #14 (for extra bonus points if you
have time)**:** due Friday, May 26.

- Sections 5.1~5.4 on
recursion in Discrete
*Mathematics and Its Applications*, 7th Ed.

Bonus Reading #15 (for extra bonus points if you
have time)**:** due Friday, May 26.

- Sections 8.1~8.3 on
recurrence relation in Discrete
*Mathematics and Its Applications*, 7th Ed.

Homework #9**:** (for extra bonus
points if you have time) due Friday, May 26.

- Read Sections 10.6 on
the shortest path problem, and do the following.
- Consider the same
directed graph depicted
**here**and apply Dijkstra’s Algorithm to find the shortest paths from vertex B to all other vertices.

** **** **

Test #3 (take-home
test)**:** Due: Thursday** **May 26

· **Problem set**: Go to Canvas/Files to find
the problem set there. See the problem set under "Files/FinalTest" to do the test: Total 69 points. Getting
55 points will be counted as 100%. 2017_Test3_Part1.pdf: 50 points, 1
point for each question 2017_Test3_Part2.pdf: 19 points, 1 point for each
question

· **Submission**: Upload your answers in a word document under (under
**Assignments**/**Test 3)**.

· **Integrity rules** for the open-book take-home test: (i) Resources
allowed: The only resources
allowed are the textbook and your class notes, and your earlier homework. (ii) No collaboration:
You should not discuss the
test with others for clues during the test. (iii) Violation of the integrity rules is viewed as
cheating in the test.** **

· **No meeting in the final exam week**.

** **** **

**Power point class notes** available under
**Files** in our Canvas class site.

References: (i) Set operations in Python

** **** **

**TAs: **William Gertsch, Ho Leung**. **

**TA hours in MATH lab (Grove 10): Wednesday 4:30~5:30pm and Thursday 3:00~4:00pm
starting from Wednesday 03/22**

** **** **

**To
the Top of this Page**