CSCI 246: Discrete Structures

Fall 2020 (this is a snapshot, most of the detailed contents will be on D2L)

Date	Lecture Topic	Text	Assignment/Test	Exercises
17 Aug 19 Aug 21 Aug	Course Overview, Latex Assignment Template, Variables Basics on Sets Set operations and elementary proof methods	Ch 1.1 Ch 1.2 Ch 6.1	Assignment 1 (.pdf) Assignment 1 (.tex) Due: Aug 31	Exercise-01 Exercise-02 Exercise-03
24 Aug 26 Aug 28 Aug	Relations and Functions on Sets Functions on General Sets Logical Statements and Equivalence	Ch 1.3 Ch 7.1 Ch 2.1		Exercise-04 Exercise-05 Exercise-06
31 Aug 02 Sep 04 Sep	Conditional Statements Valid/Invalid Arguments Valid/Invalid Arguments	Ch 2.2 Ch 2.3 Ch 2.3	Assignment 2 (.pdf) Assignment 2 (.tex) Due: Sep 14	Exercise-07 Exercise-08 Exercise-09
07 Sep 09 Sep 11 Sep	Labor Day, no class Predicates and Quantified Statements I Predicates and Quantified Statements II	Ch 3.1 Ch 3.2		Exercise-10 Exercise-11
14 Sep 16 Sep 18 Sep	Statements with Multiple Quantifiers Arguments with Quantified Statements Direct Proof & Counterexample I	Ch 3.3 Ch 3.4 Ch 4.1		Exercise-12 Exercise-13 Exercise-14
21 Sep	Test 1, Sep 21, 4:00-5:15pm; on-line (I will be in Reid 105 in case some people wants to do it there with hard copy tests.)		Contents: Everything covered until (and inclusive of) Sep 16, a practice Test 1 will be posted on D2L under "On-line Tests and Exam" by the evening of Sep 14.
21 Sep 23 Sep 25 Sep	Test 1 Direct Proof & Counterexample II, III Direct Proof & Counterexample III, IV	Ch 4.2, 4.3 Ch 4.3, 4.4	Assignment 3 (.pdf) Assignment 3 (.tex) Due: Oct 1	Exercise-15 Exercise-16, Exercise-17
28 Sep 30 Sep 02 Oct	Indirect Arg: Contradiction & Contrapositon Indirect Arg: Two Famous Theorems Sequences	Ch 4.7 Ch 4.8 Ch 5.1	Assignment 4 (.pdf) Assignment 4 (.tex) Due: Oct 12	Exercise-18 Exercise-19 Exercise-20
05 Oct 07 Oct 09 Oct	Induction Induction Strong induction	Ch 5.2 Ch 5.3 Ch 5.4		Exercise-21 Exercise-22 Exercise-23
12 Oct 14 Oct 16 Oct	Solving recurrence relations Solving recurrence relations Real and integer valued functions	Ch 5.7 Ch 5.7 Ch 11.1	Assignment 5 (.pdf) Assignment 5 (.tex) Due: Oct 22	Exercise-24 Exercise-25 Exercise-26
19 Oct 21 Oct 23 Oct	Time complexity, 2 Time complexity, 3 Review for Test 2	Ch 11.2 Ch 11.3	Assignment 6 (.pdf) Assignment 6 (.tex) Due: Oct 30	Exercise-27 Exercise-28 Practice Test 2
26 Oct	Test 2, Oct 26, 4:05-5:25pm; on-line (I will be in Reid 105 in case some people wants to do it there with hard copy tests.)		Contents: Everything covered since Sep 18 until (and inclusive of) Oct 14. The best way to prepare is to study the questions in Assignments 3-5.
26 Oct 28 Oct 30 Oct	Test 2 Time complexity, 4 Introduction to probability, 1,2	Ch 11.4 Ch 9.1, 9.2		Exercise-29 Exercise-30, Exercise-31
02 Nov 04 Nov 06 Nov	Introduction to probability, 3,4 Introduction to probability, 5,8 Introduction to probability, 9	Ch 9.3,9.4 Ch 9.5,9.8 Ch 9.9	Assignment 7 (.pdf) Assignment 7 (.tex) Due: Nov 6	Exercise-32, Exercise-33 Exercise-34 , Exercise-35 Exercise-36
09 Nov 11 Nov 13 Nov	Graph-1 Graph-2 Graph-3	Ch 10.1, 10.2 Ch 10.2, 10.3 Ch 10.4, 10.5	Assignment 8 (.pdf) Assignment 8 (.tex), Fig 1 (.pdf), Due: Nov 12	Exercise-37 Exercise-38, Exercise-39 Exercise-40
16 Nov	Test 3, Nov 16, 4:05-5:35pm; on-line (I will be in Reid 105 in case some people wants to do it there with hard copy tests.)		Contents: Everything covered since Oct 16 until (and inclusive of) Nov 13. The best way to prepare is to study the questions in Assignments 6-8, as well as Exercise 26-40.	Practice Test 3
18 Nov	Review for the optional final.
23 Nov	OPTIONAL FINAL, Nov 23, 4:10-6:00pm; on-line		Contents: Everything covered in this course, though the weight will be a bit more on the second half (proofs, time complexity, probability, graphs). Note that if you are happy with your 3 test scores, you don't have to take it.

Schedule, assignments and grade weights subject to change.

Meeting Times

On-line Lecture: videos will be posted on D2L about 24 hours before the scheduled lecture.
Face-to-face question answering: Monday, Wednesday and Friday 4:10 - 5:00 pm in Reid 105.
Face-to-face question answering could be done on-line after the first week trial.

Instructor

Dr. Binhai Zhu.
- E-mail: bhz@montana.edu
- Phone: (406) 994-4836
- Office Hours: Monday & Wednesday & Friday, 3:00 pm - 3:50 pm, or by appointment.
- Office Hours will be done on-line: Virtual Location

TA Information

Tina Yin.
- E-mail: yalanyin@foxmail.com
- Office Hours: Monday 5-6pm, Thursday 6-7pm.
- Physical Location: Barnard 259/249, the student help center.

Other Help

CS Department Tutoring Center. Free help from upper division undergraduate and graduate students.
For some topics, additional links and reading materials will be posted later.

Course Description

This course is to introduce students to the basic concepts, proofs and techniques in discrete mathematics. The syllabus/outcomes includes the following:

Be able to use formal proof techniques, including mathematical induction and proof by contradiction.
Understand algorithmic complexity and be able to use it to compare different program designs for a problem.
Solve problems that use logic, sets, and functions.
Solve problems using Boolean algebra.
Solve problems that use permutations and combinations.
Solve problems that use discrete probability.
Solve problems that use basic graph theory.

Textbook

Discrete Mathematics with Applications, Susanna S. Epp, Fifth Edition.

Grading

This a course on discrete mathematics. You can't learn mathematics by listening and reading alone (though they are important!). So you will have to do a lot of exercises (not graded, though the solutions will be posted on D2L to help you to learn). However, the majority of your grade comes from assignments, tests and a final. All the tests and the optional final will be conducted on-line through D2L.
    8 Assignments (the worst dropped, the best counted twice)     ================> 48%
    3 In-class Tests (announced at least one week ahead)    ======================> 30%
    Final (optional, could be replaced with the average of 3 tests)      ==============> 18%
    Best Exam Grade (best of the 3 tests and the final)    =======================> 4%

Each of the 2 in-class tests will be announced at least one week ahead.

The final cannot be taken early. The Best Exam Grade is counted for the best of your 3 tests and the final; for instance, the scores of your 3 tests and the final are 60%, 80%, 80%, and 65% respectively, then you get 80% of these 4 points, which is 3.2.

At the end of the semester, final grades will be determined based on your overall performance on assignments, tests and the final exam.

Late Policy

Assignments will be submitted in .pdf format through D2L, and no late assignment is accepted. Exception will only be given to extreme cases, like a student being seriously sick. It is strongly recommended that you use Latex to generate .pdf files for your assignments; in fact, for Assignment 1, it is mandatory that you use Latex to finish it. In the first lecture, I will show a quick demo on how to use the template to generate a .pdf file.

Latex Downloads/Usage

With an esus.cs.montana.edu account,

you can download and install MobaXterm, which is free; after you login, simply run "pdflatex HW-XX.tex" to generate the pdf file named "HW-XX.pdf".
as I did in class, you can also download and install PuTTY, which is also free; after you login, simply run "pdflatex HW-XX.tex" to generate the pdf file named "HW-XX.pdf".

If you want to use Latex without using the esus.cs.montana.edu account,

you can create an account on Overleaf, which is free (as long as you share your project to at most one collaborator).

Collaboration Policy

You have to finish your assignment alone, unless it is said clearly that the corresponding assignment could be a group assignment (i.e., a group of at most 3 students submit a solution, and all the 3 get the same grade for that assignment).

Even for a non-group assignment, you still may (unless otherwise noted)

Discuss your ideas with other people (including on D2L), but still have to write your solution by yourself.
Use Internet resources, provided that a reference is given.

Failure to abide by these rules will result in everyone involved being reported to the Dean of Students and receiving an F for the course.