This repository is for class materials for Discrete Structures, Fall 2018, taught by Prof. Fasy.
Course Catalog Description: This course covers logic, discrete probability, recurrence relations, Boolean algebra, sets, relations, counting, functions, maps, Big-O notation, proof techniques including induction, and proof by contradiction.
The folders in this repository contain all materials for this class.
- lec_notes: Copies of lecture notes and board photos.
- assignments: week-by-week practice problems and homework assignments, as well as a LaTex template for your submissions.
The schedule is at the bottom of this Markdown file. If you want to learn more about Markdown, check out this tutorial.
When? MWF 16:10 - 17:00
Where? Reid 105
The preferred method to ask questions relating to this class is a public post on Piazza. Please use this link to sign up for the course in Piazza.
- Link to Piazza course page - use this link once you are signed up for the class.
- You can direct message Prof. Fasy and the TAs in Piazza, but if you would prefer to email Prof. Fasy, please use: brittany.fasy@montana.edu.
Office hours:
- Prof. Fasy: M,W 17:10 - 18:30, and by appointment.
- Sam Micka: T,Th 13:10-14:00
- Rostik Mertz: M 8:00 - 9:00.
- Kirby Overman: W,F 15:10 - 16:00.
The repository is set as public, so you can access all course materials easily. I suggest creating a fork, so that you can use your fork to maintain your own materials for this class. See the resources below for forking directions.
To clone this repo:
$ git clone https://bitbucket.org/msu-cs/csci-246-fall2018.git
Group discussions, questions, and announcements will be through Piazza.
By the end of this course, a student will:
- 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.
Your grade for this class will be determined by:
- 5% Attendance
- 30% Homework (top 10 counted)
- 10% Online Quizzes (top 10 counted)
- 20% Midterm I
- 20% Midterm II
- 15% Final
A grade above an 90 will earn at least an A-, above a 80 will earn at least a B-, above 70 will earn at leat a C-, and above 60 will earn at least D-.
Class attendance and participation is required. Attendance will be randomly taken throughout the semester. Class Attendance grade is all-or-nothing, and you must attend 75% of the classes where attendance is taken.
All assignments must be submitted by 23:59 on the due date. Late assignments will not be accepted.
Throughout this semester, we will have 12 homework assignments. The best 10 grades will count towards the homework grade.
For descriptive assignments and reports, the submission should be typeset (preferably in LaTex), and submitted as a PDF both in D2L and Gradescope. Each problem should be started on a fresh page.
- Code to sign up for Gradescope: M8NJY5
For code assignments, well organized source code with clear comments should be submitted.
Collaboration is encouraged on all aspects of the class, except where explicitly forbidden. Note:
- All collaboration (who and what) must be clearly indicated in writing on anything turned in.
- Homework may be solved collaboratively except as explicitly forbidden, but solutions must be written up independently. This is best done by writing your solutions when not in a group setting. Groups should be small enough that each member plays a significant role.
The integrity of the academic process requires that credit be given where credit is due. Accordingly, it is academic misconduct to present the ideas or works of another as one's own work, or to permit another to present one's work without customary and proper acknowledgment of authorship. Students may collaborate with other students only as expressly permitted by the instructor. Students are responsible for the honest completion and representation of their work, the appropriate citation of sources and the respect and recognition of others' academic endeavors.
Plagiarism will not be tolerated in this course. According to the Meriam-Webster dictionary, plagiarism is `the act of using another person's words or ideas without giving credit to that person.' Proper credit means describing all outside resources (conversations, websites, etc.), and explaining the extent to which the resource was used. Penalties for plagiarism at MSU include (but are not limited to) failing the assignment, failing the class, or having your degree revoked. This is serious, so do not plagiarize. Even inadvertent or unintentional misuse or appropriation of another's work (such as relying heavily on source material that is not expressly acknowledged) is considered plagiarism.
By participating in this class, you agree to abide by the Student Code of Conduct. This includes the following academic expectations:
- be prompt and regular in attending classes;
- be well-prepared for classes;
- submit required assignments in a timely manner;
- take exams when scheduled, unless rescheduled under 310.01;
- act in a respectful manner toward other students and the instructor and in a way that does not detract from the learning experience; and
- make and keep appointments when necessary to meet with the instructor.
Except for note taking and group work requiring a computer, please keep electronic devices off during class, as they can be distractions to other students. Disruptions to the class will result in being asked to leave the lecture, and one half-point will be deducted from the attendance grade.
After 20 October 2018, I will only support requests to withdraw from this course with a ``W" grade if extraordinary personal circumstances exist. If you are considering withdrawing from this class, discussing this with me as early as possible is advised. Since this class involves a project, the decision to withdraw must be discussed with me, and with your group.
If you have a documented disability for which you are or may be requesting an accommodation(s), please contact me and Disabled Student Services within the first two weeks of class.
- Git Udacity Course
- Forking in Git
- Markdown
- More Markdown
- Inkscape Can Tutorial
- Plagiarism Tutorial]
- Ott's 10 Tips
- Epp: Epp, Discrete Mathematics, Brief Edition
- EF: Lecture notes by Edelsbrunner and Fasy
- 4CT: Wilson, Four Colors Suffice
- Topics: Introduction, What is proof?, Sets, Lists
- Reading: Epp 1.2-3, 4.1-2; EF Lecture 1
- Online Quiz 1: due Friday (31 August 2018)
- Sept. 3 is Labor day. Enjoy the holiday!
- Topics: Binomial Coefficients, Permutations, Combinations, Counterexamples
- Reading: Epp 4.3-4, 9.2, 9.6; EF Lecture 2
- Homework-01: due Tuesday (4 September 2018)
- Online Quiz 2: due Wednesday (5 September 2018)
- Topics: Equivalence Relations, Boolean Algebra
- Reading: Epp Ch. 2, 4.5-4.6, 8.1-8.3 EF Lectures 3, 8; 4CT Preface
- Homework-02: due Tuesday (11 September 2018)
- Online Quiz 3: due Wednesday (12 September 2018)
- Topics: Quantifiers, Predicates, and Big-O Notation
- Reading: Epp Ch. 3.1-3.4 EF Lecture 9; 4CT Ch 1
- Homework-03: due Tuesday (18 September 2018)
- Online Quiz 4: due Wednesday (19 September 2018)
- Exam: Monday the 24th of September
- Topics: Inference
- Reading: EF Lecture 10; 4CT Ch 2
- Online Quiz 5: due Wednesday (26 September 2018)
- Topics: Mathematical Induction, Sequences, Summations, Recursion
- Reading: Epp Ch. 5.1-5.4; EF Lectures 11, 12; 4CT Ch 3
- Homework-04: due Tuesday (2 October 2018)
- Online Quiz 6: due Wednesday (3 September 2018)
- Topics: Growth Rates, Solving Recurrence Relations, Divide and Conquer
- Reading: Epp Ch. 5.5-5.6; EF Lectures 13, 14; 4CT Ch 4
- Homework-05: due Tuesday (9 October 2018)
- Online Quiz 7: due Wednesday (10 September 2018)
- Topics: Modular Arithmetic, Inverses, Proof by Contradiction)
- Reading: Epp Ch. 8.4; EF Lectures 4, 5; 4CT Ch 5
- Homework-06: due Tuesday (16 October 2018)
- Online Quiz 8: due Wednesday (17 September 2018)
- Topics: Introduction to Algorithms, Euclid's Algorithm, RSA Cryptograph
- Reading: Epp Ch. 8.5; EF Lectures 6, 7; 4CT Ch 6
- Homework-07: due Tuesday (23 October 2018)
- Online Quiz 9: due Wednesday (24 September 2018)
- Exam: Monday the 29th of October
- Topics: Inclusion-Exclusion
- Reading: Epp Ch. 9.1-9.3; EF Lecture 15; 4CT Ch 7
- Online Quiz 10: due Wednesday (29 September 2018)
- Topics: Conditional Probability, Random Variables, Expected Values
- Reading: EF Lecture 16, 17; CT Ch 8
- Homework-08: due Tuesday (6 November 2018)
- Online Quiz 11: due Thursday (8 November 2018)
- Nov. 12 is Veterans day. Enjoy the holiday!
- Topics: Probability in Hashing
- Reading: EF Lecture 18; CT Ch 9
- Homework-09: due Tuesday (13 November 2018)
- Online Quiz 12: due Thursday (15 November 2018)
- Nov. 21 and 23 are part of Thanksgiving Break. Enjoy the holidays!
- Reading: EF Lecture 19
- Homework-10: due Tuesday (20 November 2018)
- Topics: probability distributions, variance
- Topics: Trees, Tours
- Reading: Epp. 10.1-10.3; EF Lectures 20, 21; 4CT Ch 10
- Homework-11: due Wednesday (28 November 2018)
- Online Quiz 13: due Thursday (29 November 2018)
- Topics: Graphs, Matching, Bipartite Graphs, Pigeonhole Principle
- Reading: Epp. 9.4; - Reading: EF Lectures 22, 23; 4CT Ch 11
- Homework-12: due Tuesday (4 December 2018)
- Online Quiz 14: due Thursday (6 December 2018)
- Cumulative Final Exam: 4:00-5:50pm Dec. 10 (Fall 2018 finals schedule)
This syllabus was created, using wording from previous courses that I have taught, as well as David Millman's Spring 2018 Graphics course. Thanks, Dr. Millman!