CSCI 246: Discrete Structures

Course schedule

Schedule subject to change.

Catalog description

3 Credits. PREREQUISITE: M 171Q or M 165Q. COREQUISITE: CSCI 132. 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.

Course Info

This course meets for lectures on Mondays, Wednesdays, and Fridays from 2:10pm-3pm in Romney Hall 008. Lectures will be recorded and available on the day’s lecture page (see schedule above) if you would like to rewatch them. We will use Discord as the primary method of course communication, and all course information will be posted on this website or on the Discord server; D2L will be used only for grading.

In an ideal world, your participation in this course would look like this:

• Before lecture, skim the recommended reading (about 15 minutes per lecture).
• Attend lecture, taking notes and asking questions as you have them (about 50 minutes per lecture).
• Do the drills on D2L each week to get independent practice with vocabulary, notation, and high-level concepts (20-60 minutes per week).
• Complete the homework assignments to get independent practice developing proofs and writing them up clearly (4-15 hours each, about every two weeks).
• Reference the textbook, lecture notes, and lecture videos, and attend instructor office hours, use tutoring services, or visit the CS Success center as needed.

Course Resources

Textbook

Connecting Discrete Mathematics and Computer Science by David Liben-Nowell. A free PDF version of the book is available here. The physical book is about $80 and is available in the bookstore if you prefer that.

Problem solving tips

Check out this document for tips on how to come up with your proofs, specific tips for homework assignments in this class, and strategies for getting the homework assignments done. This document is a work in progress and may be updated throughout the semester.

Lecture extra notes

We may go over some notation and definitions quickly during lecture. If you’re feeling rusty on your math notation, check out the lecture extras document. It’ll be updated throughout the course with notes for the day’s lecture, and if I get a lot of questions about something from a day’s lecture, I’ll put more notes in about that, too.

Course assistants

We have two course assistants for this course: Adiesha Liyanage and Jasmine Vang. Jasmine will be available in the CS Student Success Center (Barnard 259) from 9am-11am Mondays and Adiesha will be available 9am-11am Fridays.

Lecture videos

Lectures are recorded and available to watch after class. However, if there are technical difficulties recording a lecture, it will not be re-recorded, so come to class when you can to make sure that you do not miss course content or announcements. Videos are linked in the schedule above, or you can access them through the Panopto folder.

Instructor office hours

My office hours are Thursdays and Fridays, 3-4:30 in the CS Success Center (Barnard 259). You can also contact me on Discord to set up a different meeting time, or drop by my office (Barnard 359) if my door is open. You can find office hours for all CS faculty here.

Computer Science Success Center

There are free tutors available in Barnard 259. More information here.

Discord server

All course communication will be through our course Discord server. See D2L announcement for link. Please change your nickname to your full name (first and last). Additionally, I suggest managing your notification settings. Check out Discord’s Notification Settings 101 page to get started. You may also need to manage the application notification settings on your device.

Course outcomes

By engaging with this course through attending lectures and completing assignments, at the end of this course, students should:

• be comfortable reading and using mathematical terminology around sets, functions, propositional and predicate logic, asymptotic notation, recursion, and graphs;
• be comfortable reading and writing mathematical proofs using the following methods: direct proofs, proofs by counterexample, proofs by construction, proofs by contradiction, proofs by contrapositive, and proofs by induction;
• have improved their problem solving and critical thinking skills, such as:
  • using examples, counter-examples, diagrams, simpler cases, similar problems, etc., to better understand a mathematical statement,
  • recognizing a broken proof or a false start and using them to find a new result or approach,
  • thinking critically about which proof paradigm is most appropriate.

Grading

You will be graded on the following:

• 12 weekly drills (lowest three dropped): 8%
• 7 problem sets (lowest two dropped): 62%
• 3 quizzes (including final): 30%

After any curving, your grade will be determined by your total score as follows: 93+: A; 90+: A-; 87+: B+; 83+: B; 80+: B-; 77+: C+; 73+: C; 70+: C-; 67+: D+; 63: D; 60: D-.

Bonus

There are three ways to earn bonus points in this class.

Catch errors in course materials

If you find an error in any of the course materials (typo, incorrect statement, etc.), post in the #errors-in-course-material channel on Discord. I will decide whether it’s truly an error and not a duplicate. If it is really an error, you get a quarter of a point. Only the first person to post about an error gets the points. You can earn a max of 1 total point toward your 100 for the course (for four errors).

Additional work throughout the semester

Since two problem sets and three drills are dropped, if you do additional problem sets and drills beyond those that count, they may be counted as a bonus. There may be additional problems that you can complete for bonus as well. The maximum bonus you may earn from this is 3 points out of 100 for the semester.

Here’s how this bonus category will be computed. First, recall that you can only earn three points total, even if you got more than three total. The following things sum up for your bonus score:

• 1 point: any extra (more than 5) problem set turned in with a score of 50% or more;
• 1/2 point: any in-class bonus activity or bonus question on a homework completed correctly (these are all marked in D2L grades under the “bonus” category)
• 1/4 point: any extra (more than 10) drill completed with a score of 50% or more.

Course survey and evaluation

If 75% or more of the class completes the mid-semester course survey (through D2L), whole class gets 1 bonus point. Same goes for the course evaluation (through the university system).

Late assignment policies

To run a course of this size we cannot accommodate individual requests for extensions on assignments; therefore, we have strict rules for when assignments are due, but have some leeway built in. Please read the bullet points below carefully, respect the policy, and get help early if you are having any problems. We want you to succeed!

• You are responsible for any announcements about assignments made in class, on Discord, on D2L, and here on the course website.
• All assignments are due on their due date by the Anywhere on Earth (AoE) timezone, which is 6 hours behind Bozeman (Actually, it’s only 5 hours behind during standard time, but we’ll go with 6 hours behind at all times). This means that the real due date is 6am the following day. If you submit labs and programs within 24 hours of the due date, you get 25% off of whatever score you earn. If you submit within two days of the due date you get 50% off. Otherwise, no points are possible.
• You can submit as many times as you would like; only your last submission will be graded.
• Drills cannot be submitted late.

Missed quiz policy

Any conflicts with a quiz must be discussed with me prior to missing the quiz. I follow University policy on makeups, which allows that serious illness or a serious family emergency are valid reasons requiring an accommodation. Most other reasons (employment conflict, travel plans) are not valid.

Collaboration policy

On all assignments, you may:

• Discuss problems and approaches with your peers.

You may not:

• Copy your peers’ proofs or write-ups of solutions to homework problems, even if you worked together to develop solutions.
• Use the internet to search for or solicit approaches or ideas.
• Post the assignments or quizzes for this course on the internet.

Academic misconduct

In line with the MSU student code of conduct, if I or the teaching assistants suspect that you have committed academic misconduct, we will schedule a meeting with you to discuss. If, after the meeting, we believe that you did commit academic misconduct, you will receive a 0 on the assignment and I will submit a report to the Dean of Students. It’s just not worth it to cheat in this course.

Important dates

The last day to drop the course online (with no instructor or advisor approval) is January 31st. The last day to drop without a W grade (instructor or advisor approval required) is February 7th. The last day to drop with a W grade (instructor and advisor approval required) is April 19th. See the full add/drop schedule for more information.

Diversity statement

Montana State University’s campuses are committed to providing an environment that emphasizes the dignity and worth of every member of its community and that is free from harassment and discrimination based upon race, color, religion, national origin, creed, service in the uniformed services (as defined in state and federal law), veteran’s status, sex, age, political ideas, marital or family status, pregnancy, physical or mental disability, genetic information, gender identity, gender expression, or sexual orientation. Such an environment is necessary to a healthy learning, working, and living atmosphere because discrimination and harassment undermine human dignity and the positive connection among all people at our University. Acts of discrimination, harassment, sexual misconduct, dating violence, domestic violence, stalking, and retaliation will be addressed consistent with this policy.

Accommodations

If you have a documented disability for which you are or may be requesting an accommodation(s), please contact me and the Office of Disability Services as soon as possible.

How to succeed in this class

What you can do:

• Keep up with the course by attending class, checking Discord, being aware of the course schedule, and doing all assignments on time.
• Be an active participant in class. This means asking and answering questions in class and on Discord, seeking help when needed, and contacting the instructor or the course assistants using Discord if you have any questions outside of class time.
• Be respectful of your classmates, your instructor, and the course assistants.
• Do your own work.

What I can do:

• Grade promptly (exact guarantees TBD).
• Post assignments well in advance (at least one week in advance for drills and at least two weeks in advance for homeworks).
• Respond to all Discord messages within one business day.
• Create a course atmosphere conducive to learning by respecting all of my students and being enthusiastic about course material and my role in helping you learn.

Copyright statement

This syllabus, course lectures and presentations, and any course materials provided throughout this term are protected by U.S. copyright laws. Students enrolled in the course may use them for their own research and educational purposes. However, reproducing, selling or otherwise distributing these materials without written permission of the copyright owner is expressly prohibited, including providing materials to commercial platforms such as Chegg or CourseHero. Doing so may constitute a violation of U.S. copyright law as well as MSU’s Code of Student Conduct.

Instructors are welcome to use this content in their courses without permission.