Discrete Structures

**To the Bottom of the
Page**

**Instructor**: Dr.
Shieu-Hong Lin Email: ** **

Class Time: Section 1: MW 10:30-11:45am Section 2: MW 12:00-1:15pm at Lim 041

Office Hours: Lim 137 MW 1:30-3:30pm T Th 3:00-5:00pm

**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 Wednesday,**Jan. 23****:**(i) 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**Wednesday,**Jan. 23****: 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.**Notes 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 Wednesday,
**Jan. 30****:**(i) Carefully review the algebraic laws and logic equivalence depicted in Table 6, 7, 8 in Section1.3 so that you can fluently use them in logic reasoning. (ii) Read Section 1.2 and Section 1.4. **Homework #2,**due Wednesday,**Feb. 6****: 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 Wednesday,
**Feb. 6****:**Read Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #3**, due Wednesday**Feb. 13****: Please click here**to download**predicate logic**.

** **** **

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

- Reading #4, Wednesday
**Feb. 13****:**(i) Read Sections 1.6-1.8 if you are confident about Sections 1.4 and 1.5. (ii) Review Sections 1.4 and 1.5 in if you still need more exposure to get familiar with predicate logic.

** **** **

**Week ****5:
More on Rules of Inference and Basics of Proofs + ****Sets.
**

- Reading #5, Wednesday,
**Feb. 20****:**(i) Read Sections 2.1-2.2 on sets and set operations. (ii) Read/Review Sections 1.6-1.8 on rules of inference and proofs. **Homework #4,Wednesday**,**Feb. 27****: Please click here**to download**sets and direct proofs.**

**Test #1** on Logic, Wednesday ~~Feb. 20~~, Feb. 27**:
**

**In-class open-book test**: on the subjects covered by the lectures and**Reading #1**to**Reading #4**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 can fluently use them to reason about logic equivalence.

** **** **

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

- Reading
#6, Wednesday,
**Feb. 27****:****(i) Carefully review**Sections 2.1-2.2, especially the set identities in Table 1 in Section 2.2 in Discrete*Mathematics and Its Applications*, 7th Ed.**(ii)****If you have time, also r****ead**Sections 6.1, 6.3 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #4**Wednesday,**Feb. 27****: Please click here**to download**sets and direct proofs.****Homework #5**Wednesday,**March. 6 (extended to March 13, no penalty)****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 7-8: ****Basics
of Counting | Spring
Break**

- Reading
#7-8, Wednesday,
**March. 13****:****(i)**Read**Sections 6.1~6.4**(note that 6.2 & 6.4 are not part of Reading 6),**(ii) If you have time, also r****ead****Sections 8.5.** **Homework #5,**Wednesday,**March. 6 (extended to March 13, no penalty)****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 9-10: ****More
on Counting + Basics of Probability |
Missions Conference**

- Reading
#9, Wednesday,
**March. 20 (open for submission till March. 27, no penalty)****:****(i)**Review**Sections 6.1~6.4 (ii) R****ead****Sections 8.5.** **Homework #6,**Wednesday,**March. 20 (open for submission till March. 27, no penalty)****: Please click here**to download Homework #6 on**counting and derangement.**

- Reading
#10, Wednesday,
**March. 27****:***Mathematics and Its Applications*, 7th Ed. **Homework #7,**Wednesday,**March. 27****(open for submission till April. 3, no penalty): Please click here**to download Homework #7 on**counting**.

** **** **

**Week 11:** **Basics of
Probability + Recurrence
Relations and Complexity of Algorithms.**

- Reading
#11, Wednesday,
**April 3****:**(i) Review Sections 7.1~7.2, 7.4 as needed. (ii) Browse through Sections 3.2, 8.1, 8.3 - Homework #8, Wednesday,
**April 10****: Please click here**to download**counting and probability**.

** **** **

**Week 12:** **More on** **Basics of Probability + Recursion and Complexity of Algorithms.**

- Reading
#12, Wednesday,
**April 10****:**(i) Review Sections 7.1~7.2, 7.4 as needed. (i) Review Sections 3.2 as needed (ii) Briefly browse Sections 5.1~5.4 if you have time. - Homework #9
**: Please click here (revised 04/16)**to download**big-O notation,**Wednesday,**April 17****(open for submission till****April 24****, no penalty)**.

** **** **

**Weeks 13-14:** **Test 2 + Relations
and Graphs.**

- Reading #13, Wednesday,
**April 17****:**(i) Review Reading #6 to Reading #10 on sets, counting, and probability for Test 2. - Reading #14, Wednesday,
**April 24****:**(i) Read Sections 10.1~10.3 and 10.6 on the basics of graphs.

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

**In-class open-book test**: on the subjects in Reading #6 to Reading #10 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 for determining equality of sets.

** **** **

**Week 15:** **Review + Test 3.**

- Reading #15, Wednesday,
**May 1 (Open for submission till May 6)****:**(i) Read the D-matrix algorithm described in*ShortestPath_D_Matrix_algorithm.pdf*and the F-matrix algorithm (the Floyd-Warshall algorithm) in*ShortestPath_F_Matrix_algorithm.pdf*for solving the all-pairs shortest path problem. Both are available under Canvas | File. (ii) Review the concepts of the big O notation and the growth of functions in Section 3.2 as needed.

**Test #3: **

- 10:00am-12:00
noon
**Mon****day**,**May 6**for those who are in MATH 112-01 (MW 10:30-11:45) - 10:00am-12:00
noon
**Wednesday**,**May 8**for those who are in MATH 112-02 (MW 12:00-13:15) **In-class open-book test**: on all the subjects explored this semester.- Make sure you understand
the
**all the homework problems and the related****concepts**very well.

Homework #10 on the all-pairs
shortest path problem: due **Wednesday**, **May 8.**

**TAs: **Joy Choi,** **Liam Thompson,**
**Peter Young

**TA hours in MATH lab (Lim 143):
**

Tuesday: 4:00 - 5:30 pm (Liam Thompson); Wednesday: 4:00 - 5:30 pm (Joy Cho)

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

** **

**To
the Top of this Page**