# CSE20

## Discrete Mathematics for Computer Science

### Instructional Staff and Contact Information

 Name Role Mia Minnes Instructor Srinivas Avireddy Teaching Assistant Justin Lazarow Teaching Assistant Shaida Masoumi Teaching Assistant Candice Yang Teaching Assistant Angel Zhang Teaching Assistant Asha Camper Singh Tutor Rachel Keirouz Tutor Benjamin Levin Tutor Timothy Nguyen Tutor Jenny Nguyen Tutor Maya Nyayapati Tutor Diana Zhou Tutor Jimmy Ye Tutor Oscar Song Tutor Xingda Jiang Tutor Su Jin Heo Tutor

Our office hours can be found in the calendar above.

Top

### Welcome Message

Welcome to CSE20! If you ever wondered "What sort of mathematics do I need for computer science?", this course will provide some of the answers. In particular, you will have the opportunity to learn basic concepts about algorithms, computer arithmetic, number systems, Boolean algebras, logic, proofs, program correctness, loop invariants, modular arithmetic, linear and partial orders, recurrences, and induction, among other things. These are some of the essential ingredients in the toolkit of every computer scientist.

#### Learning Goals:

CSE 20 will teach you the basic tools for representing, analyzing, solving, and reasoning about computational problems. Specifically, on successful completion of this course, you will be able to:
• Describe and trace simple algorithms using English and pseudocode.
• Identify and prove (or informally justify) termination and correctness of some algorithms.
• 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. logic puzzles, set operations, combinatorial circuits.
• Prove propositional equivalences.
• Apply proof techniques, including direct proofs and proofs by contradiction.
• Distinguish valid from invalid arguments.
• Prove program correctness using loop invariants and pre-conditions /post-conditions.
• Use mathematical induction to prove statements about mathematical identities and inequalities.
• Apply structural induction to prove statements about recursively defined objects.
• Identify and be able to prove basic properties of sets, functions, and relations.
• Distinguish between finite, countable, and uncountable sets.

Course grades will be computed using the following weights.

 Grading Exams 65% Homework and participation 35%

Exams: There will be two midterm exams and one final exam. The midterms will be given during the usual lecture time and place and you must attend the lecture for which you are registered. No makeup tests will be given. The exams will test all material covered up to the day of the exam. In particular, the final exam will be cumulative and will cover all material from the whole term. You may not use calculators on any exams but you may use a double-sided sheet of handwritten notes on 8.5x11 inch paper. The weighting of the exam scores will be

MAX ( (Final 35%, First Exam 15%, Second Exam 15%), (Final 50%, Best Exam 15%)).

You must have a passing score on the final exam (50%) in order to pass the course.

The weighting of the homework and participation will be
MAX ( (Homework 30%, Participation 5%), Homework 35 %)

Homework: There will be eight homework assignments. Working through them which will be crucial to helping you gain mastery of the techniques we will study. When computing the homework portion of the course grade, the lowest of your eight homework scores will be dropped and the average computed using the remaining seven assignments.

Homework should be done in groups of one to three people. You are free to change group members at any time throughout the quarter. Problems should be solved together, not divided up between partners.

Students should consult their textbook, class notes, lecture slides, instructors, TAs, and tutors when they need help with homework. Students should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don't understand what the question is asking you to do. Other questions are best addressed in office hours.

The 5% of the grade that may be earned through participation will consist of the higher score between the following two options:

• Discussion section quizzes: Each week, short quizzes will be given in discussion section. These short quizzes will be based on the readings in the textbook sections for the week. To receive credit, you should take the quiz at the beginning of section, take notes on your quiz during section, and show your quiz to your TA at the end of section. You will get 100% on the quiz by doing these things. We will drop your lowest quiz score (one week excused absence), then compute the average score of the remaining quizzes.

After your weighted average is calculated, letter grades will be assigned based on the following curved grading scale:

 A+, A, A- B+, B, B- C+, C, C- D, F 100-88 87-75 74-60 Below 60

The boundaries for +/- designations within each letter grades will be determined based on the grade distribution of the class. In addition, you must pass the final exam with at least a 50% in order to pass the course.

#### Standards for evaluation:

The Jacobs School of Engineering code of Academic Integrity is here. You should make yourself aware of what is and is not acceptable by reading this document. Academic integrity violations will be taken seriously and reported immediately. Ignorance of the rules will not excuse you from any violations. Key facts about academic integrity related to CSE20:
• Do not discuss homework problems with people besides your homework group members and the instructional staff.
• Do not share written solutions or partial solutions with other groups.
• Prepare your final written solution without consulting any written material except class notes and the class text.
• Do not use any external resources (other than the allowed one sheet of notes) during the in-class exams.
• Before taking an exam, do not attempt to obtain information about the contents of the exam from students who have already taken in. After taking an exam, do not discuss its contents with anyone in the class who has not yet taken it.

#### Accommodations:

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. Students are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance (by the end of week 2, if possible) so that accommodations may be arranged. For more information, see here.

Top

### Textbook

The required textbook for this course is

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

This book is available in hardcopy at the UCSD Bookstore or many online retailers. You are also able to purchase an online copy of the book through McGraw Hill Connect.

We acknowledge that 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 will refer to the chapter and section numbers of the 7th edition, but we have put together this guide so that you can easily find the corresponding sections in the 5th and 6th editions. Please be aware that while this textbook does not vary too much from edition to edition, the content of the older books might not be exactly the same as the 7th edition.

You may also wish to look at the following textbook as a supplementary resource.

Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, Jenkyns and Stephenson

Top

### Important Websites

In addition to this course website, we will be using these external websites for various purposes throughout the quarter:

• Use Gradescope to view grades and submit homework assignments. You should already be enrolled in this class with your @ucsd.edu email address. If you have trouble accessing the Gradescope site, post a private Piazza message to the instructors with your name, PID, UCSD email, and lecture section in this class (A00 or B00).
• Use Piazza to get important announcements and post questions and answers.
• Register your clicker at the beginning of the quarter here. Once this is done, you will not need to access this website.
• Visit podcast.ucsd.edu for a video podcast of the lectures.

Top

### Class Meetings

 Date Time Location Lecture A00 Tu, Th 11:00am - 12:20pm WLH 2001 Lecture B00 Tu, Th 12:30pm - 1:50pm PCYNH 106 Discussion A01 Monday 1:00pm - 1:50pm WLH 2205 Discussion A02 Monday 2:00pm - 2:50pm WLH 2205 Discussion A03 Monday 3:00pm - 3:50pm WLH 2205 Discussion A04 Monday 4:00pm - 4:50pm WLH 2205 Discussion A05 Monday 7:00pm - 7:50pm WLH 2205 Discussion B01 Monday 1:00pm - 1:50pm CENTR 222 Discussion B02 Monday 2:00pm - 2:50pm CENTR 222 Discussion B03 Monday 3:00pm - 3:50pm CENTR 222 Discussion B04 Monday 4:00pm - 4:50pm CENTR 222 First Midterm Exam Tues Jan 26 In lecture In lecture Second Midterm Exam Tues Feb 23 In lecture In lecture Final Exam A00 Thursday Mar 17 11:30am - 2:30pm TBA Final Exam B00 Tuesday Mar 15 11:30am - 2:30pm TBA

Discussion section signups will be done through UCSD's Sections Tool on a first-come, first-served basis. You can sign up for any discussion section that still has room, regardless of which lecture you are enrolled in. Signups open at 3pm on Tuesday, January 5, the first day of class.

Top

### Schedule

NOTE: This schedule is subject to change.

 Date Day Subject Reference Due Dates 1/5/16 Tues Algorithms: pseudocode and tracing Rosen 3.1 + Appendix 3 JS 1.1 Slides (revised after class) Extra worked examples from Rosen 1/7/16 Thur Number systems: representations and algorithms Rosen 4.2 (+ 4.1) JS 1.2, 1.3 Slides (revised after class to fix error in one clicker question) Extra worked examples from Rosen 1/8/16 Fri HW 1 due. 1/11/16 Mon Discussion Section. Rosen 4.2 # 13,14,21,22,23,24 1/12/16 Tues Number systems: conversions and logical operations Rosen 4.2 + 1.1 JS 1.2, 1.3 Slides (revised after class) 1/14/16 Thur Propositional Logic: the connectives Rosen 1.1 JS 3.2 Slides (typos fixed after class) 1/15/16 Fri HW 2 due. (File updated 1/12.) 1/18/16 Mon No Discussion Section. Rosen 4.2 #14, 1.1 #49 In observance of MLK day. 1/19/16 Tues Propositional logic: equivalences Rosen 1.2 + 1.3 JS 3.2 Slides (typos fixed after class) 1/21/16 Thur Predicates and quantifiers. Rosen 1.4 JS 3.3 Slides 1/22/16 Fri HW 3 due. 1/25/16 Mon Discussion Section. Review for first exam. 1/26/16 Tues First exam. Exam today, covers everything before predicates (through Jan 19). 1/28/16 Thur Nested quantifiers Rosen 1.5 JS 3.3 Slides 2/1/16 Mon Discussion Section. Rosen 1.4 #19,29 2/2/16 Tues Proof strategies Rosen 1.7+1.8JS 3.4 + 3.5 Slides (filled in after class) 2/4/16 Thur Sets Rosen 2.1 + 2.2 JS 2.1 Slides (filled in after class) 2/5/16 Fri HW 4 due. 2/8/16 Mon Discussion Section. Rosen 2.1 #9, 17 2/9/16 Tues Sets Rosen 2.1 + 2.2 Slides 2/11/16 Thur Induction, inequalities and constructions Rosen 5.1 + 5.2 JS 3.6 + 3.7 Slides (updated after class) 2/12/16 Fri HW 5 due. 2/15/16 Mon No discussion Section. Rosen 2.2 #47, 5.1 #19 In observance of Presidents' Day 2/16/16 Tues Recursive definitions and structural induction Rosen 5.3JS 2.2 Slides 2/18/16 Thur Structural and strong induction Rosen 2.3 JS 2.1.2 Slides (updated after class to fix Fibonacci bound) 2/19/16 Fri HW 6 due. 2/22/16 Mon Discussion Section. Practice exam + HW review 2/23/16 Tues Second exam. Exam today, covers through Feb 16. 2/25/16 Thur Functions and cardinality of sets Rosen 2.3, 2.5 Slides 2/29/16 Mon Discussion Section. Rosen 5.2 # 3, 5.3 #32. 3/1/16 Tues Cardinality of sets and relations Rosen 2.5, 9.1 Slides 3/2/16 Wed HW 7 due. 3/3/16 Thur Relations: equivalence relations and posets Rosen Ch 9 JS Ch 6 Slides 3/7/16 Mon Discussion Section. Rosen 9.1 #49, 9.6 #23a, 9.5 #1b,3a 3/8/16 Tues Modular arithmetic Rosen 4.1, 9.4 Slides 3/10/16 Thursday (note change!) HW 8 due. 3/10/16 Thur Review day. Slides 3/15/16 Tues Lec B00 Final exam. Final exam today at 11:30. 3/17/16 Thurs Lec A00 Final exam. Final exam today at 11:30.

Top