Discrete Structures

**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin

Class Time: **T TH at** **Lim 041**

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

· M T Th 9:00-10:30am 1:30-3:00pm.

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 Tuesday,
**Jan. 16****:**(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,**Tuesday,**Jan. 16****: 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 Tuesday,
**Jan. 23****:**(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 Tuesday,**Jan. 23****: 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 Tuesday,
**Jan. 30****:**Read Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #3**, due Tuesday**Jan. 30**, extended to**Feb. 6****: Please click here**to download**predicate logic**.

** **** **

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

- Reading #4, due Tuesday,
**Feb. 6****:**(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 + Basics of Sets. **

- Reading #5, due Tuesday,
**Feb. 13****:**(i) Read Sections 1.6-1.8. (ii) Review Sections 1,1, 1.3, 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed.to prepare for Test #1. (iii) Optional: Read Sections 2.1-2.2 if you have time.

** **** **

**Week 6: Sets, Set Operations,
and Proofs **

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

**Test #1** on Logic, Thursday, **Feb. 22****: **

**In-class open-book test**: on the subjects in Reading #1 to Reading #5 on logic.- Make sure you understand
the
**all the homework problems and the related**concepts very well. - 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 7: ****More
on Sets, Set
Operations, and Proofs | ****Basics of
Counting **

- Reading
#7, due Thursday,
**March. 8****:****Read**Sections 6.1, 6.3 and 8.5 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #5**due Thursday,**March. 8****: Please click here**to download**sets and direct proofs.**

** **** **

**Weeks 8 and 9: More on Basics
of Counting **

- Reading
#8 + #9 due
Thursday,
**March. 22****:**Read**Sections 6.1~6.4**and**8.5**(note that 6.2 & 6.4 are new) in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework
#6
**: Please click here**Homework #6 on**counting and derangement,**due Thursday,**March. 22**.

** **** **

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

- Reading
#10
**:**Read Sections 7.1~7.2, 7.4 in Discrete*Mathematics and Its Applications*, 7th Ed., due Thursday,**March. 29**. - Homework
#7
**: Please click here**Homework #7 on**counting,**due Thursday,**March. 29**.

** **** **

**Week 11:** **Counting: Recurrence
Relations and Complexity of Algorithms.**

- Reading
#11
**:**(i) Review Sections 7.1~7.2, 7.4 as needed. (ii) Browse through Sections 3.2, 8.1, 8.3, due Thursday,**April 5**. - Homework #8
**: Please click here**Homework #8 on**counting and probability,**Thursday,**April 5**.

** **** **

**Week 12:** **Recursion, Recurrence
Relations, and Mathematical Induction.**

- Reading
#12
**:**(i) Review Sections 3.2, 8.1, 8.3 (ii) Briefly browse Sections 5.1~5.4, due Thursday,**April 12**. No penalty if submitted by April 19.

** **** **

**Week 13:** **Mathematical Induction | Relations and
Graphs.**

- Reading
#13
**:**(i) Review Sections 5.1~5.4, (ii) Browse Sections 10.1~10.3 and 10.6 on the basics of graphs, due Thursday,**April 19**. - Homework #9
**: Please click here**Homework #9 on**big-O notation,**Thursday,**April 19**. (No Penalty until Thursday April 26.)

**Test #2: ** Tuesday, **April 17**

**In-class open-book test**: on the subjects in Reading #6 to Reading #11 on sets, counting, and probability.- Make sure you understand
the
**all the homework problems and the related**concepts very well. - Make sure you understand
the
**set identities**about sets and set operations depicted in**Table 1**in Section 2.2 and are capable of using them for determining logic equivalence.

** **** **

**Week 14:** **Graphs.**

- Reading #14
**:**(i) Read Sections 10.1~10.3 and 10.6 in Discrete*Mathematics and Its Applications*. (ii) Read the D-matrix algorithm described in the first handout and the F-matrix algorithm (the Floyd-Warshall algorithm) in the second handout for solving the all-pairs shortest path problem, due Thursday,**April 26**.

** **** **

**Test #3: ** Due - May 3 (No meeting in the final exam week)

**Take-home open-book test**: No collaboration with other people allowed. You can only refer to textbook and your own notes as resources to work out the answers.**Preparation**: Carefully review Test 1, Test 2, and all the homework assignments.**Problem set**: Already posted on Canvas.**Submission**: Upload your answers in a file (a text file or WORD file) due by 11:55pm Thursday May 3.

Optional Homework #10 for extra bonus points: due by 11:55pm Thursday May 3.

** **** **

**TAs: **Liam Thompson,** **Peter Young**. **

**TA
hours in MATH lab (Lim 143): **Wednesday Liam Thompson: **10:30-11:30am****;** Peter Young: **3:00-4:00pm**

** **** **

**To
the Top of this Page**