CSE20

The BIG questions

How do we decide (and prove) what's true?
About algorithms and games and strategies / databases / cryptographic systems / compilers / operating systems / circuits...
How do we exploit these properties to build new systems?
Use integer representations to build ALU, use strings to build error-correcting codes, use logic to optimize database queries...
What's impossible? And what can we say about it?
Logical paradoxes, different sizes of infinity

Top

Instructional team

Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/winter2017/cse20): use public posts to ask questions that might interest other students in the class and private posts (visible to the instructional team) for questions specific to you. Our office hours and locations 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.

Course Description:

Please click here for a course description as given in the undergraduate course listing.

Learning Goals:

In answering the three BIG questions above about truth, provability, and possibility, 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.
• 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.

Grading:

Course grades will be computed using the following weights.

Grading
Exams	65%
Homework	30%
Participation	5%

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 a standard sized index card. 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.

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

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

Homework solutions should be neatly written or typed and turned in through Gradescope by 11:59am right before noon!! (you won't need to pull late nights!) on the due date. No late homeworks will be accepted for any reason. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible (neatly written and not too faint) or your homework may not be graded. Submit only one submission per group. One representative group member can upload the submission through their gradescope account and then add the other group member(s) to the Gradescope submission: make sure to select their names when you "Add Group Members" to the submission; it's not enough to just list their names on the page. For step-by-step instructions on scanning and uploading your homework, see this handout.

For homework help, consult your textbook, class notes and podcast, lecture slides, instructors, TAs, and tutors. It is considered a violation of the policy on academic integrity to:

• look or ask for answers to homework problems in other texts or sources, including the internet, or to
• discuss the homework problems with anyone outside your group (unless you are in office hours with someone from the instructional team).

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.

Participation: 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 and will help you start out on the homework. 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.

When you enrolled in the class, you signed up for a specific discussion section. If you would like to switch section during the quarter, please post a private note on Piazza with your name, PID, current Discussion Section, and requested new section. Also let us know if you'd like this to be a permanent switch for the rest of the quarter. Please wait for confirmation from us before attending your new section, since we will need to make sure that there is enough space.



• iClicker Participation: There will be frequent opportunities for structured active participation during lecture and discussion section (solving problems, responding with clickers, group discussion), in which everyone is expected to participate. Additionally, alerting the instructor, TAs, and tutors when you are confused, lost, didn't hear something, or otherwise in need of additional explanation is strongly encouraged. You must register your iClicker here. We will start recording clicker points on the second day of class, so please register your clicker right away. Clicker discussion questions in lecture will be graded for participation only and not correctness of the response. Full credit for clicker points for a given day will be awarded for clicking in at least 80% of the time that day. Your two lowest lecture participation days (one week's worth of excused absences) will be automatically dropped before your average iClicker participation score is computed. Forgetting your clicker counts as missing a class, so please remember to bring it!

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-90	89.9-80	79.9-65	Below 65

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:

Your assignments in this class will be evaluated not only on the correctness of your answers, but also 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.

Regrades:

Please be prompt (less than three days) in reporting any errors in the grading of your work, or in the recording of your grade. All grades become permanent one week after they are recorded. All regrade requests must be made in person in Prof. Minnes' office hours (see calendar for times; CSE 4206).

Academic Integrity:

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 index card 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 on reserve in the library and is also 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. 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.

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. Access the companion website here.

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

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

Top