Course Information

●   Prerequisites:

○   C- or better in Calculus 1

○   C- or better in CSCI 1200, 1300, or 1320

○   ability (or willingness to learn) to program in Python 3

●   Office Hours:

○   Rachel Cox: Day and Time listed on Canvas

○   TAs, CAs: Calendar

Why Discrete Structures?

The course covers fundamental ideas from discrete mathematics, especially for computer science students. It focuses on topics that will be foundational for future courses including algorithms, artificial intelligence, programming languages, automata theory, computer systems, cryptography, networks, computer/network security, databases, and compilers.

Computer Science is all about solving interesting problems efficiently and cheaply, using computers!

Here are some real problems that keep many computer scientists awake at night:

●   Route a packet reliably from one server to another on the internet (faster than existing protocols? even when routers can fail on us?)

●   Search for web pages (better than Google, Bing or your favorite search engine??)

●   Find the biggest clique on Facebook. How many people are in this clique? Who are they?

●   Understand how to sequence the human genome.

●   Write a program to play go (and play better than the best human champion?).

●   Write a program to check if a program is “correct” (keeps your instructor awake at night!).

Some of these problems are really hard to solve using a computer. No one knows if there are easy solutions to these problems and it would be nice to see efficient solutions in this century. In this course, we will cover the mathematical foundations that will help us formulate solutions to some of the real problems above. Specifically, we will learn

●   How to abstract using mathematical objects such as sets, relations, functions, trees and graphs.

●   How to count really well.

●   How to reason like a pro: obtain succinct water-tight proofs to guarantee that your solutions are correct, better than a competing solution and all that.

●   We will learn these cool mathematical facts, so that in the course of your education as a computer scientist, you will write cool programs to solve interesting problems involving automated reasoning, games, fractals, social networks and the human genome.

Topics Covered

Roughly, we will cover the following topics (some of them may be skipped depending on the time available).

●   Logic: Propositional and First Order Logic, Boolean Algebra.

●   Proofs: Primer on writing proofs, inductions, proof by contradiction.

●   Sets, Relations and Functions: Basic properties. Paradoxes in naive set theory. Infinite sets.

●   Recursion: Recursive functions and recursively defined structures.

●   Combinatorics: Counting, binomial theorem, counting with recursion.

●   Discrete Probability: Basic facts, Bayes' Rule

●   Graphs: Definitions and properties of graphs.

●   Trees: Definitions and properties of trees.

●   Number Theory: Modular Arithmetic, Pascal’s Little Theorem

●   Example Applications: Artificial Intelligence (automated reasoning, game playing), Graphics (drawing fractals) and Networks (social network analysis).

Textbook

We will use Discrete Mathematics and Its Applications, 7th ed. by Kenneth H. Rosen.

We realize the book is pricey, but it's pretty well-written and includes lots of cool computer science applications. Earlier/international editions are fine, but you'll be responsible for figuring out the section number map between editions for the daily reading.

Course Web Page

This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the graders, the course assistants, and the instructor. Rather than emailing me questions, I request that you post your questions on Piazza. If your question is of a private nature, Piazza allows you to send private messages to the instructor. It is your responsibility to check the web page on a regular basis. Additionally, check our Canvas page regularly. Here you will find detailed information such as news, homework assignments and solutions, and instructor office hours.

Coursework

Weekly Homework: Homework will be assigned weekly throughout the course. There will be 12 assigned homeworks. There will be two types of homework assignments: online homework through Canvas which may include matching, multiple choice, numerical, or programming questions, and written homework which may include by-hand computations, puzzles, and proofs. You are expected to write up your written solutions neatly, with full explanations and justifications. You may discuss problems with your classmates, but all work must be your own. See the Collaboration Policy below for more details.

Copying solutions from Chegg or other online "resources" constitutes Academic Dishonesty (that work is NOT your own).

Homework is due by 5 PM on the listed due date for full credit (typically Fridays).

Late policy: You may turn in the homework by 5pm the following day for 90% credit. You may turn in the homework by 5pm two days late for 80% credit. Homework is not accepted past 48 hours late.

Because of Covid-19, I recognize that personal emergencies may arise. You have 3 emergency dropped assignments available to you throughout the semester if you need them. I will automatically drop up to three 0’s in the gradebook at the end of the semester. If you need to use a drop during the semester, you are not required to let me know. You may simply not turn that assignment in. Note that regardless of the reason that you do not turn up to 3 assignments in, 3 dropped assignments is the hard cutoff. If you feel you may need to miss more coursework than that, you may want to consider dropping the course. 3 missed assignments represents 25% of the work for the semester. If you end up not needing to drop any scores, I will compute your homework grade out of your best 9 scores.

You must submit your written homework to Gradescope (https://www.gradescope.com/) by 5 PM. I do NOT accept emailed homework under any circumstances.

Exams: There will be two midterms on February 15-16, 2021 and March 31-April 1, 2021 and a cumulative final exam given during the university-scheduled final examination time. Note that due to university regulations, final exams can only be rescheduled due to official university excused absences. Please plan your travel accordingly.

You must obtain an average exam score of at least 55% in order to pass the course with a C- or better.

Quizlets: Weekly I will post a short exercise - a "quizlet" - on Canvas. Your lowest three quizlet scores will be dropped.

Grade Determination

The overall grades will be based on a cumulative score computed from

●   The weekly homework (30% of the grade)

●   The quizlets (10% of the grade)

●   Two midterm exams (20% of the grade each)

●   The final exam (20% of the grade)

Unless adjustments are necessary, letter grades will be assigned using the standard grading scale:

Letter	A	A-	B+	B	B-	C+	C	C-	D+	D	D-	F
Raw Average	93-100	90-92	87-89	83-86	80-82	77-79	73-76	70-72	67-69	63-66	60-62	00-59

Collaboration Policy

The collaboration policy is simple:

●   Inspiration is free: you may discuss homework assignments with anyone. You are especially encouraged to discuss solutions with your instructor and your classmates.

●   Plagiarism is forbidden: the assignments and code that you turn in should be written entirely on your own. While writing the assignment you are not allowed to consult any source other than textbooks, your own class notes or the posted lecture slides. Copying/consulting from the solution of another classmate constitutes a violation of the course's collaboration policy and the honor code and will result in an F in the course and a trip to the honor council.

●   Do not search/ask for a solution on-line: You may not actively search for a solution to the problem from the internet. This includes posting to sources like StackExchange, Reddit, Chegg, etc.

●   When in doubt, ask: If you have doubts about this policy or would like to discuss specific cases, please ask the instructor.

Standard Course Policies

Behavior

Both students and faculty are responsible for maintaining an appropriate learning environment in all instructional settings, whether in person, remote or online. Those who fail to adhere to such behavioral standards may be subject to discipline. Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with race, color, national origin, sex, pregnancy, age, disability, creed, religion, sexual orientation, gender identity, gender expression, veteran status, political affiliation or political philosophy. For more information, see the policies on classroom behavior and the Student Code of Conduct.

Requirements for COVID-19

As a matter of public health and safety due to the pandemic, all members of the CU Boulder community and all visitors to campus must follow university, department and building requirements, and public health orders in place to reduce the risk of spreading infectious disease. Required safety measures at CU Boulder relevant to the classroom setting include:

●   maintain 6-foot distancing when possible,

●   wear a face covering in public indoor spaces and outdoors while on campus consistent with state and county health orders,

●   clean local work area,

●   practice hand hygiene,

●   follow public health orders, and

●   if sick and you live off campus, do not come onto campus (unless instructed by a CU Healthcare professional), or if you live on-campus, please alert CU Boulder Medical Services.

Students who fail to adhere to these requirements will be asked to leave class, and students who do not leave class when asked or who refuse to comply with these requirements will be referred to Student Conduct and Conflict Resolution. For more information, see the policies on COVID-19 Health and Safety and classroom behavior and the Student Code of Conduct. If you require accommodation because a disability prevents you from fulfilling these safety measures, please see the “Accommodation for Disabilities” statement on this syllabus.

All students who are new to campus must complete the COVID-19 Student Health and Expectations Course. Before coming to campus each day, all students are required to complete the Buff Pass. 

Students who have tested positive for COVID-19, have symptoms of COVID-19, or have had close contact with someone who has tested positive for or had symptoms of COVID-19 must stay home. In this class, if you are sick or quarantined, send me an email within 24 hours of the onset of sickness; [email protected], if you know your sickness will impact your ability to participate in the class.

Accommodation for Disabilities

If you qualify for accommodations because of a disability, please submit your accommodation letter from Disability Services to your faculty member in a timely manner so that your needs can be addressed. Disability Services determines accommodations based on documented disabilities in the academic environment. Information on requesting accommodations is located on the Disability Services website. Contact Disability Services at 303-492-8671 or [email protected] for further assistance. If you have a temporary medical condition, see Temporary Medical Conditions on the Disability Services website.

Preferred Student Names and Pronouns

CU Boulder recognizes that students' legal information doesn't always align with how they identify. Students may update their preferred names and pronouns via the student portal; those preferred names and pronouns are listed on instructors' class rosters. In the absence of such updates, the name that appears on the class roster is the student's legal name.

Honor Code

All students enrolled in a University of Colorado Boulder course are responsible for knowing and adhering to the Honor Code. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access to academic materials, clicker fraud, submitting the same or similar work in more than one course without permission from all course instructors involved, and aiding academic dishonesty. All incidents of academic misconduct will be reported to the Honor Code ([email protected]); 303-492-5550). Students found responsible for violating the academic integrity policy will be subject to nonacademic sanctions from the Honor Code as well as academic sanctions from the faculty member. Additional information regarding the Honor Code academic integrity policy can be found at the Honor Code Office website.

Sexual Misconduct, Discrimination, Harassment and/or Related Retaliation

The University of Colorado Boulder (CU Boulder) is committed to fostering an inclusive and welcoming learning, working, and living environment. CU Boulder will not tolerate acts of sexual misconduct (harassment, exploitation, and assault), intimate partner violence (dating or domestic violence), stalking, or protected-class discrimination or harassment by members of our community. Individuals who believe they have been subject to misconduct or retaliatory actions for reporting a concern should contact the Office of Institutional Equity and Compliance (OIEC) at 303-492-2127 or [email protected]. Information about the OIEC, university policies, anonymous reporting, and the campus resources can be found on the OIEC website.

Please know that faculty and graduate instructors have a responsibility to inform OIEC when made aware of incidents of sexual misconduct, dating and domestic violence, stalking, discrimination, harassment and/or related retaliation, to ensure that individuals impacted receive information about options for reporting and support resources.

Religious Holidays 

Campus policy regarding religious observances requires that faculty make every effort to deal reasonably and fairly with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, review the course schedule. Let the instructor know of any religious holiday conflict two weeks prior to any exams or due dates. 

See the campus policy regarding religious observances for full details.