CSE 20: Discrete Math for CS -- WINTER 2021 ARCHIVED SITE: DEPRECATED

Textbook and supplies

The required textbook for this course is

Discrete Mathematics and its Applications, Kenneth Rosen, McGraw Hill, 7th edition.

This book is on reserve in the library and is also available in hardcopy at the UCSD Bookstore or many online retailers. An eBook is available as a purchasing option for this course. You can access this eBook by clicking the RedShelf tool within Canvas. If you opt-in to this eBook by clicking the Opt-in Now button your student account will be charged directly. You will also receive an email with the exact amount of this charge. Within the add/drop period you may also opt-out of this option if you decide you’d rather use an alternate format. There are not many differences between the 7th edition and other recent editions, so you may be able to save some money by purchasing an older edition of the textbook. All posted reading assignments refer to the chapter and section numbers of the 7th edition. This guide lists the corresponding sections in the 5th and 6th editions.

Online Self Assessments and Extra Examples from the book are here.

Typesetting (LaTeX) Resources

All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.

If you have never used LaTeX, we recommend cloud resources (e.g. Overleaf) that don't require you to download and install LaTeX on your local machine. In particular, Overleaf has great collaboration functionality if you choose to work with a group.

An open source LaTeX reference is here, and you can Google for many templates and examples to get you started.

Grading and academic integrity

Grades in this class are designed to reflect your work and to document evidence of your learning this core material. They are also designed to accommodate the emergency remote learning context we're continuing to face in light of the current pandemic. By working together to explore the CSE 20 material with integrity, we can each help ensure a fair and interesting quarter of building the foundations needed for your continued development in Computer Science. Please reach out to me (minnes@eng.ucsd.edu) if you have extenuating circumstances that you think will impede your ability to participate in the planned CSE 20 activities; I'd like to work out a solution together.

The graded components for CSE 20 will be Homework, Review quizzes, Project, Final exam. Your overall grade for CSE 20 will be computed using the weights

• Homework: 30% of overall score. You will need to achieve a passing grade (70%) with integrity on the homework component of this class to pass this course.
• Review quizzes: 30% of overall score. You will need to achieve a passing grade (70%) with integrity on the review quiz component of this class to pass this course.
• Project: 30% of overall score. You will need to achieve a passing grade (70%) with integrity on the project component of this class to pass this course.
• Final: 10% of overall score.
• Extra credit: This class is participating in a research project on academic integrity. You will receive 1% extra credit for accessing two surveys and answering two comprehension questions. Check your @ucsd.edu email for instructions during the quarter from integrity@ucsd.edu .

More details about each graded component:

Review quizzes

Why? To focus your attention on key ideas in the videos and give you immediate feedback.
How? Review quizzes based on class videos are due each week on Friday. They can be submitted as many times (with no penalty) as you'd like any time until Sunday night. The lowest two quiz scores will not be included in your overall review quiz average.

Homework

Why? To give you practice with the main concepts and techniques of the course, while getting to know and learn from your classmates.
How? Weekly homework may be done individually or in groups of up to 4 students. You may switch HW partners for different HW assignments. The lowest HW score will not be included in your overall HW average. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission. If working in a group, submit only one submission per group: one partner uploads the submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission by selecting their name(s) in the "Add Group Members" dialog box. You will need to re-add your group member(s) every time you resubmit a new version of your assignment. Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness.

• HW1 Definitions and Notation (due Tuesday January 12)
• HW2 Numbers (due Tuesday January 19)
• HW3 Circuits and Logic (due Tuesday January 26)
• HW4 Propositional and Predicate Logic (due Tuesday February 9)
• HW5 Proofs and Sets (due Tuesday February 16)
• HW6 Induction (due Tuesday February 23)
• HW7 Proofs and Numbers and Cardinality (due Tuesday March 9)

All assignment files can be accessed at this Google Drive folder.
In light of the many difficult circumstances surrounding this quarter, we are building in the following flexibility into our CSE 20 HW policy.

1. The late submission (with no penalty) on HW will be extended until 8am (San Diego time) the morning after each HW deadline.
2. The lowest HW score will not be included in your overall HW average.
3. Since the goal of HW in CSE 20 is to give you practice with the main concepts and techniques of the course, we want you to engage with it even if you don't have time to complete it before the deadline. We will open a Gradescope assignment where you can turn in your work for any one HW assignment (e.g. one that you did not submit or one that you want to revisit). You will complete this assignment individually, even if you worked on the HW with others. Prepare a screencast video where you explain your work for each question of your chosen HW assignment, and/or explain the posted solutions we have provided. During your solution presentation, for each HW question in this assignment, point out at least one potential mistake that someone solving a similar question should avoid (this could be a mistake you made while thinking about this problem or something you anticipate a classmate might struggle with); explain why the mistake is wrong and how to fix it. Include your face and your student ID for a few seconds at the beginning, and introduce yourself audibly while on screen. You don't have to be on camera the whole time, though it's fine if you are. We are looking for a brief confirmation that it's you creating the video/doing the work attached to the work. Upload your video file for this assignment directly into the Gradescope online assignment. Successful completion of this video will earn back up to 75% of the missed points in your HW assignment. We will grade these assignments at the end of the quarter, so that you have time to choose which HW you would like to work on.

Project

Why? To go deeper and extend your work on assignments and to explore an application of your choosing.
How? This project replaces the in-class exams we would have during an in-person quarter. The main thing that in-person, on-paper exams let us do is easily verify that it is in fact you, the student, completing a major assessment. Many students have told us that they are concerned that cheating will be frequent in all-remote courses. Incorporating some video assessement and some open-ended personalized projects help ensure fairness in that we are giving credit and grades to the people who earned them. Hopefully, you will also find them interesting and valuable activities in their own right. The project description is available at this Google doc. The project consists of four parts.

• Part 1 of Project (due Friday of Week 3, January 22)
• Part 2 of Project (due Friday of Week 5, February 5)
• Part 3 of Project (due Friday of Week 9, March 5)
• Part 4 of Project (due Friday of Week 10, March 12)

Final exam

Why? To review the entire quarter and solidify your understanding of this foundational material.
How? Cumulative quiz on class content during exam week of Spring quarter. This will be an online assignment on Gradescope available for 24 hours including the scheduled final exam time. Once you begin the exam, you will have 2.5 hours to complete it. The exam is designed to require approximately 1 hour; the extra time is available to help those in our community that are struggling to focus in these times and to allow for slow internet connections. The exam must reflect your own independent effort. The exam may have a combination of True/False, multiple choice, select-all-that-apply, and free-response questions. To be fair to those in other time zones who may be taking the exam while I am asleep and therefore can't answer questions, I (and the TAs/tutors) will not answer any questions about the exam during the exam period. If any bugs are found in the exam after the exam period, the affected question(s) will be removed. To take the exam, ensure you are located somewhere with reliable internet for the duration of your exam. If you will have trouble with this requirement contact me ASAP so we can work something out.
The exam will be open-book: you may use your notes for CSE 20, along with all provided CSE 20 class material this quarter. No collaboration or help-seeking / help-giving will be allowed. No online resources other than those provided for this quarter's CSE 20 offering are allowed.

The UC San Diego Academic Integrity pledge is here. Academic integrity violations will be taken seriously and reported to the campus-wide Academic Integrity Office. Key facts about academic integrity related to CSE 20:

• Use only resources explicitly allowed for each assignment. Resources not affiliated with this quarter's version of the class may use inconsistent notation or definitions. If you need help, please reach out to the instructor, TAs, and tutors.
• Do not share written solutions or partial solutions for homework with other students in the class who are not in your group. Doing so would dilute their learning experience and detract from their success in the class.
• Before and during taking any individual assessment, do not attempt to obtain information about the contents of the exam from students who have already taken it or from any nonauthorized source.
• You may not ask for help from anyone while taking individual assessments since they are intended to reflect your own mastery of the material. In particular, you may not collaborate on exam questions with other students in the class and you may not post any portion of the exam on forums where others may assist you.
• After taking an exam or quiz, do not discuss its contents with anyone in the class who has not yet taken it. Do not post information about it or share information about it with others who haven't taken it.

Policies

Regrades

Regrades need to be requested within three days of announcement of grades. The regrade window will be set in Gradescope. In the regrade request, include a brief but detailed explanation of why you think there was an error in the grading. A regrade request may lead to us reviewing the entire assignment and may lead to the score being adjusted up or down depending on any errors found in the original grading. All regrades will be considered once the regrade window closes; thank you in advance for your patience while we carefully look through them.

Accommodations for students with disabilities

Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) which is located in University Center 202 behind Center Hall. Please use the OSD Student Portal as early in the quarter as possible to facilitate timely accommodations. For more information, see here.

Class material and intellectual property

My lectures and course materials, including videos, assignments, and similar materials, are protected by U.S. copyright law and by University policy. I am the exclusive owner of the copyright in those materials I create. You may take notes and make copies of course materials for your own use. You may also share those materials with another student who is enrolled in or auditing this course. You may not reproduce, distribute or display (post/upload) lecture notes or recordings or course materials in any other way — whether or not a fee is charged — without my express prior written consent. You also may not allow others to do so. If you do so, you may be subject to student conduct proceedings under the UC San Diego Student Code of Conduct.

Similarly, you own the copyright in your original work. If I am interested in posting your answers or papers on the course web site, I will ask for your written permission.

Educational Research

This class is participating in research to understand an array of specific classroom and learning experience that students have in response to the pedagogical and curricular decisions instructors make and to address the following research questions:

• What pedagogies lead to better learning outcomes, and for which students?
• What educational practices increase the persistence and success of students, particularly those from underrepresented groups?
• What student practices lead to increased learning and success in real-world settings?

Answers to these questions will inform teaching practice at UC San Diego, and also have the potential to contribute to the global knowledge base of how to improve student learning in a large university setting.

Specifically for this quarter, CSE 20 is participating in a project on academic integrity and in a project analyzing different types of assignments.

Details about the academic integrity project will be sent to your @ucsd.edu email from integrity@ucsd.edu .

Details on the project studying different types of assignments are in this document. In particular, if you consent to participate in this study, no action is needed. If you DO NOT consent to participate in this study, or you choose to opt-out at any time during the quarter, please submit this form online. Your instructor will not have access to the list of students who opted out until after grades are posted. Note that you must separately opt-out of the study for each course involved in this study.

Learning goals

Upon successful completion of this course, you will be able to:

• Describe and trace simple algorithms using English and pseudocode.
• Define and use classical algorithms and algorithmic paradigms e.g. Euclidean algorithm, greedy optimization.
• Use multiple representations of numbers to illustrate properties of the numbers and develop algorithms.
• Understand the logical structure and meaning of a sentence expressing a property, fact, or specification.
• Reason about the truth or falsity of complicated statements using Boolean connectives, quantifiers, and basic definitions.
• Relate boolean operations to applications, e.g. set operations and combinatorial circuits.
• Prove propositional equivalences and use normal forms.
• Apply proof techniques, including direct proofs and proofs by contradiction.
• Distinguish valid from invalid arguments.
• Craft proofs and arguments at different levels of formality, including prose and symbolic notation as appropriate.
• Reason about modular arithmetic.
• Use mathematical induction to prove statements about mathematical identities and inequalities.
• Apply structural induction to prove statements about recursively defined objects, e.g. strings and trees.
• Identify and be able to prove basic properties of sets, functions, and relations.
• Distinguish between finite, countable, and uncountable sets.