Content Calendar

 

CSE 20 SPRING 2021

Introduction to Discrete Mathematics

About the Course

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, amongst other things. These are some of the essential ingredients in the toolkit of every computer scientist.

Prerequisites

There are no strict prerequisites but students should have a basic understanding of elementary computer programming, mathematics (algebra, geometry, trigonometry and calculus.)

Learning Outcomes

• Describe and trace simple algorithms using English and pseudocode.
• Identify and prove (or informally justify) the 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.
• Reason about modular arithmetic.
• 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 Logistics

Instructor and Course Staff

Name Role email Office hours Zoom link Miles Jones Instructor mej016@ucsd.edu Mon 9:30-11am Wed 12-1:30pm https://ucsd.zoom.us/j/91801672777   Megan Chu TA mec043@ucsd.edu Mon 1-2pm Wed 10-11am https://ucsd.zoom.us/j/3136709354 Yuanjun Huang TA yuh036@ucsd.edu Mon 8-9am Wed 8-9am https://ucsd.zoom.us/j/96799660410 Alexander Mai TA amai@ucsd.edu Wed 2-3pm, 6-7pm https://ucsd.zoom.us/j/97149949916     Sachin Deshpande TA scdeshpa@ucsd.edu Wed 4-5pm Thurs 2-3pm https://ucsd.zoom.us/j/7550170649?pwd=Y2tvVTVqMGxQcGw3UHNQMC9iVGVzZz09      Albert Li Tutor ajl015@ucsd.edu Thurs 2-3pm Fri 4-5pm https://ucsd.zoom.us/j/93356506531  Brian Nguyen Tutor brnguyen@ucsd.edu Mon 11-12 Tues 12-1pm https://ucsd.zoom.us/j/7665621310 Pankita Tibrewala Tutor ptibrewa@ucsd.edu Tue 2-3pm Fri 12-1pm https://ucsd.zoom.us/j/7943304614 Minh Vo Tutor m9vo@ucsd.edu Mon 2-3pm Tue 10-11am https://ucsd.zoom.us/j/7451905610 Jack Yang Tutor g2yang@ucsd.edu Mon 5-6pm Wed 5-6pm (Final Week Tue 9 - 10am Wed 9 - 10am) https://ucsd.zoom.us/j/97042199061 Ramin Atrian Tutor ratrian@ucsd.edu Tue 11-12 Thu 11-12 https://ucsd.zoom.us/j/97031127294 Ethan Lan Tutor etlan@ucsd.edu Sat 3-5pm https://ucsd.zoom.us/j/6180079839?pwd=Zi9Ham1uK3VNeDk4UzhyTWV3TnBRdz09

Office Hours Schedule

 

Course Resources

The textbook for this course is

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

The textbook's companion website has extra practice problems and resources. In particular, the Self Assessments and the Extra Examples for each chapter are great practice materials. Acess the companion website here.  Earlier editions contain almost all of the material we will reference, and can be bought used often quite reasonably.  Just be sure to double-check page numbers, because we will use the page numbers for 7th edition.  

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

Jenkyns, Stephenson   Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer
The full pdf of this book is available for free download from a UCSD internet connection at:

http://link.springer.com/book/10.1007%2F978-1-4471-4069-6

Another helpful book is:  Daniel Solow's
How to Read and Do Proofs: An Introduction to Mathematical Thought Processes
While primarily for mathematics majors, it also is a general reference that can be used by anyone reading or doing proofs.

Time and Location

Date	Day	Time
Lecture	Tu/Th	8:00-9:20 (A00 Miles Jones)	Meeting ID: 918 0167 2777 https://ucsd.zoom.us/j/91801672777
Discussion Section	Fridays (no discussion during exam weeks)	2:00-2:50 (A01) 3:00-3:50 (A02) 4:00-4:50 (A03)	https://ucsd.zoom.us/j/96339247246  https://ucsd.zoom.us/j/98970923313  https://ucsd.zoom.us/j/97600094784
Final Exam	Thursday June 10	Scheduled for 8am-10:59am In reality we will give you 3 hours to complete during a 24 hour window starting 8am June 10 and ending 8am June 11.

Lectures:

•  via Zoom during the scheduled times (TuTh 8:00-9:20) (PT)

•  The lecture slides will be posted before class on the calendar tab of the canvas site.

•  You may interrupt lecture to ask questions, make comments or express doubts (you can use text or audio.)

•  All lectures will be recorded and posted for students to watch when they want.

•  You are not required to have a webcam, but microphones are encouraged, especially when we open the lecture to comments and discussion.

•  There will be a short review quiz given via canvas due on the following Sunday at 11:59pm.

Coursework and Grades

Assignments/Coursework

Your grade will be based on the following:

• Homework
• 2 Midterms
• Review Quizzes
• Final Exam

Homeworks

Homeworks can be downloaded from the content calendar.

Homework should be done in groups of 1-4 people. So you may do them on your own if you prefer not to work in a group. You are free to change group member at any time throughout the quarter. Problems should be solved together, not divided up between partners.

We will drop the lowest homework score.

Homework solutions should be typed (NOT HANDWRITTEN) and turned in through Gradescope by 11:59pm on the due date. No late homeworks will be accepted. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible or your homework may not be graded. You may resubmit updated versions of your homework up until the deadline. Only your most recent Gradescope submission will be graded.

Standards for evaluation

Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. This means that unless it says: "no justification necessary" then we expect a written justification.

Collaboration Guidelines for Homework

Students are encouraged to collaborate on homework assignments. You may work in groups of up to four students. Your group will submit one assignment and Gradescope will give you the opportunity to add all of your group members to the assignment. Groups do not have to be the same people for every assignment. You can change group members at any time.

If you are discussing problems with students outside of your group, please only share hints and basic techniques. DO NOT share your answers or allow other students to copy your written work. The bottom line is to submit YOUR OWN work. If we find that your work is too similar to another group's then you may be suspected of an academic integrity violation.

You may not collaborate with anyone outside of the class. (You are not permitted to ask homework questions to message boards or websites such as chegg.)

Review Quizzes

There will be a review quiz for every lecture.

This adds up to 20 total review quizzes.

You will have until the following Sunday to complete the review quizzes of the preceding week.

You will have unlimited attempts on each quiz.

Each review quiz is worth 1 point. You will get whatever fraction of 1 based on how well you did on the review quiz.

In order to get the full 5% points for review quizzes, you must earn 16 points.

Each point less than 16, the percentage will go down by 1 percent:

16+:   5%

15:     4%

14:     3%

13:     2%

12:     1%

11-:    0%

Midterms

Midterm 1 is a canvas quiz. It is administered on Friday of week4. You have a 24 hour window to take the exam (12:01am to 11:59pm PT). The exam is timed for 90 minutes.

Midterm 2 is a gradescope online assignment. It is administered Friday of week 8 May 21st.

Due to concerns about academic integrity, we will be holding two 3-hour windows for you to take the 90 minute timed exam.

• Window 1 is from 2-5pm (Friday May 21) Pacific Time.
• Window 2 is from 8-11pm (Friday May 21) Pacific Time.

If you are unable to take the exam during these windows then please contact us at your earliest convenience and we will do our best to accommodate your situation.

Grading

Course Policies

Academic Integrity

In this course we expect students to adhere to the UC San Diego Integrity of Scholarship Policy.   This means that you will complete your work honestly, with integrity, and support and environment of integrity within the class for which you are tutoring.  Some examples of specific ways this policy applies to CSE 20 include:

• Do not discuss solutions to homework problems with people besides your homework partner (except during office hours, with the instructional team).
• Do not share written solutions with other groups.
• Do not collaborate or copy exams.
• Follow the golden rule for AI:  Always give credit for any outside help on any assignment, except for those whose job it is to help you (Instructors, TAs, tutors, the textbook, and class handouts)
• You should not attempt to search for homework solutions or exam solutions online or in sources outside of the course content. (Example: you should not consult content from CSE 20 of past quarters.) If you accidentally stumble upon a homework solution in such an outside source you should cite it in your homework solution. If your solution proves to be too similar to the cited one, you may lose credit on the problem, however failure to cite the other solution will be treated as academic dishonesty.

 

Collaboration Policy

For homework collaboration policy, see the paragraph above.

For the exams, you are not permitted to collaborate with anyone else (including people from outside of the class like message boards or chegg.)  We will give you the opportunity to ask questions to the teaching staff during exams.

Regrade Policy

Please be prompt (three days) in reporting to your TA any errors in the grading of your work, or in the recording of your grade. All grades become permanent three days after they are recorded. Regrade requests for homework assignments must be made on Gradescope. Please note that by requesting a regrade for a problem, it will be completely regraded and your grade may go up or down.

Late or Missed Assignments/Missed Exam Policy

We will drop your lowest homework and give you the option of dropping your lowest exam. Other than extenuating circumstances, there is no credit for late or missed assignments.

Technology Policy

For homework assignments and for exams, you are permitted to use calculators, online calculators such as wolfram alpha and programming languages to help you with your answers.

Outside Tutoring

Individuals are not permitted to approach students to offer services of any kind in exchange for pay,  including tutoring services.  This is considered solicitation for business and is strictly prohibited by University policy.

Resources for Students

Getting Help

We provide many office hours and 1-1 sessions. Please use them. This class can be challenging if you don't engage with the teaching staff. The office hours are TBD.

 

The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all.  The Center offers a variety of programs, listed in the IDEA Center Facebook page at http://www.facebook.com/ucsdidea/ (you are welcome to Like this page!) and the Center web site at http://idea.ucsd.edu/.  The IDEA Center programs support both undergraduate students and graduate students.

Diversity and Inclusion

We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.).  Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive. 

 

Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course.  If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door.  Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input. 

 

We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community (https://ucsd.edu/about/principles.html).  Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.

If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible.   If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.  

Students with Disabilities

We aim to create an environment in which all students can succeed in this course.  If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away.  We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD.  You 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 so that accommodations may be arranged.

Basic Needs/Food Insecurities

If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry.  Please visit http://thehub.ucsd.edu/ for more information.