Delivering Quality Education

Welcome to CSE 21 Spring 2016
Class time Schedule

Announcements

Homework 1: The first homework is now posted in the updated schedule linked above. It is due Friday, April 1 at 11:59pm (but we are not fooling) and can be completed in a group of 3. Unlike future assignments, the first homework will be graded based solely on good-faith effort to solve problems. However, a grade based on correctness will be included in the comments, for your use only.

Textbook: The required textbook for this course is
Discrete Mathematics and its Applications, Kenneth Rosen, McGraw Hill, 7th edition. 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.

Meeting Time

	Date	Time	Location
Lecture B00 (Jones)	Mon, Wed, Fri	9:00am - 9:50am	PCN 109
Lecture D00 (Russell)	Mon, Wed, Fri	4:00pm - 4:50pm	CENTER 101
Discussion B05	Monday	12:00pm - 12:50pm	CSB 005
Discussion D01	Monday	12:00pm - 12:50pm	WLH 2204
Discussion B01	Monday	1:00pm - 1:50pm	CSB 005
Discussion D02	Monday	1:00pm - 1:50pm	WLH 2204
Discussion B02	Monday	2:00pm - 2:50pm	CSB 005
Discussion D03	Monday	2:00pm - 2:50pm	WLH 2204
Discussion B03	Monday	3:00pm - 3:50pm	CSB 005
Discussion D04	Monday	3:00pm - 3:50pm	WLH 2204
Final Exam B00 Practice Final questions	Wed, June 8	8:00am - 11:00am	Pcynh 109
Final Exam D00 Practice Final questions	Thu, June 9	3:00pm - 6:00pm	Center 101

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 2:30pm on Thursday, December 31.

Top

Instructional Staff and Contact Information

Name Role Office Hours Email

Miles Jones Instructor See calendar above mej016@eng.ucsd.edu

Russell Impagliazzo Instructor See calendar above russell@eng.ucsd.edu

Jiapeng Zhang Teaching Assistant See calendar above jpeng.zhang@gmail.com

Yunli Wang Teaching Assistant See calendar above yuw258@ucsd.edu

Lenord Melvix Teaching Assistant See calendar above lmelvix@eng.ucsd.edu

Tanvi Nabar Teaching Assistant See calendar above tgnabar@eng.ucsd.edu

Yan Shu Teaching Assistant See calendar above yashu@eng.ucsd.edu

Qiushi Wang Teaching Assistant See calendar above qiushi@ucsd.edu

Anwaya Aras Teaching Assistant See calendar above aaras@ucsd.edu

Sid(Side) Li Tutor See calendar above s7li@eng.ucsd.edu

Adam Setters Tutor See calendar above asetters@eng.ucsd.edu

Vyom Shah Tutor See calendar above vyshah@ucsd.edu

Anna Raichev Tutor See calendar above araichev@ucsd.edu

Brian Nguyen Tutor See calendar above btn023@ucsd.edu

We will be communicating with you and making announcements through an online question and answer platform called Piazza. We ask that when you have a question about the class that might be relevant to other students, you post your question on Piazza instead of emailing us. That way, everyone can benefit from the response. You should not post about graded homework questions on Piazza. The best way for us to answer homework questions is in office hours. You can also post private messages to instructors on Piazza, which we prefer to email.

Top

Syllabus

Welcome to CSE21! This course is intended to introduce you to mathematical concepts and problem solving techniques that are used to model and solve problems in every area of computer science, and in particular, in algorithm design. We will learn about sorting and searching, asymptotic notation, recursion, graphs, enumeration, data representation, and discrete probability. Understanding these topics and being able to work out related problems will be essential to your work as a computer scientist.

Course Description:

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

Grading:

Course grades will be computed using the following weights.

Exams 60%

Homework 35%

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. You may not use calculators or other devices 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 30%, First Exam 15%, Second Exam 15%), (Final 45%, 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, 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. That is, each of your seven best homework scores counts for 5% of your grade. Also, note that the first assignment is on background material, and is graded based on good-faith effort rather than correctness. In other words, it is a free perfect grade as long as you make an effort. (A detailed evaluation of correctness will be provided to you as comments).

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. A good balance is if the members of the group rotate the following roles: solution generator, skeptic, scribe, and editor.

Homework solutions should be neatly written or typed and turned in through Gradescope by 11:59pm 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.

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. In particular, do not post about graded homework questions on Piazza. Homework questions are best addressed in office hours. If you accidentally find related material in another source (e.g., you took a related course last year with a similar problem), you must cite the source on your homework and write up your answer without consulting the source. To do otherwise is plagiarism and is subject to incredibly harsh penalties, as well as being damaging to your soul. Remember that no one will care in a few years what your grade in CSE 21 was, but academic dishonesty can ruin your life.

The 5% of the grade awarded for participation will be based on collecting up to 25 participation points, each 1/5 of a per cent. (More than 25 participation points does not improve your grade directly, but the more you participate, the better prepared you will be on homework and exams)

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 one participation point, you should take the quiz at the beginning of section, take notes on your quiz during section, and submit an attendance form to your TA at the end of section. Note that you gain the participation point even if you get all answers incorrect.
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 on TritonEd (formerly Ted). Clicker discussion questions in lecture will be graded for participation only and not correctness of the response. You get a participation point for each lecture where you answer at least 80% of the questions asked that day. You can't answer if you forgot your clicker, so please remember to bring it! Participation points will also be awarded for completing a survey in the middle of the quarter and filling in the CAPE and TA evaluations at the end of the quarter. We are also looking into awarding points for piazza participation.

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-
97	93	89	85	81	77	73	69	65

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 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 three days after they are recorded. All regrade requests must be made through Gradescope. A separate request must be made for each problem you want to be regraded, and each should include an explanation of your reason for requesting a regrade.

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 CSE21:

Do not discuss homework problems with people besides your homework group members and the instructional staff.
Do not post about homework problems on Piazza.
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.

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). If you have an AFA letter, please schedule an appointment with your instructor by the end of week one to ensure that reasonable accommodations can 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.

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.

The texbook'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

Important Websites

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

Use Gradescope to submit homework assignments and view grades on homework and exams.
Use Piazza to get important announcements and post questions and answers. You will need to follow the registration process to sign up for Piazza.
Use TritonEd (formerly Ted) to register your clicker at the beginning of the quarter and view your participation scores.

Top

Current class schedules

NOTE: This schedule is subject to change.

Homework 8 (probability)

Date	Day	Subject	Reference	Due Dates
3/28/16	Mon	Discussion Section. Background	Quiz
3/28/16	Mon	Introduction. Sorting algorithms.	Rosen 3.1 JS 4.3 Slides Guide for understanding proofs and logic
3/30/16	Wed	Sorting algorithms. Counting comparisons. Using loop invariants to prove algorithms correct.	Rosen 3.1, 5.5 JS 4.3 Some extra problems about induction and invariants How to use loop invariants Slides
4/01/16	Fri	Linear and binary search. Counting comparisons. Using loop invariants to prove algorithms correct.	Rosen 3.1 JS 4.1 Slides	Homework 1, background
4/04/16	Mon	Discussion Section. loop invariants	Quiz
4/04/16	Mon	Asymptotic notation. The need for order notation.	Rosen 3.2 Slides
4/06/16	Wed	Time analysis of sorting and searching algorithms.	Rosen 3.3 Slides	Homework 2 (sorting and searching) due April 6
4/08/16	Fri	Time analysis of other algorithms.	Rosen 3.3 Slides
4/11/16	Mon	Discussion Section. Time analysis	Quiz
4/11/16	Mon	Intro to recursion. Correctness of recursive algorithms.	Rosen 5.3 before Thm 1, 5.4, 8.1 JS 2.4.1 Slides Annotated Slides (B) Annotated Slides (D)
4/13/16	Wed	Time analysis of recursive algorithms. Solving recurrences. Merging sorted lists.	Rosen 5.4 Slides Annotated Slides (B) Annotated Slides (D)	HW3 due (asymptotics) Released April 8.
4/15/16	Fri	Divide and conquer, including mergesort and multiplication.	Rosen 5.4, 8.3 before Thm 1 Slides Annotated Slides (B) Annotated Slides (D)
4/18/16	Mon	Discussion Section. Recursion	Quiz
4/18/16	Mon	Introduction to graphs.	Rosen 10.1, 10.2 before Example 14, 10.3 Slides Annotated Slides (B) Annotated Slides (D)
4/20/16	Wed	Graph search algorithms	Rosen 10.5 JS 5.1 Slides
4/22/16	Fri	First exam.	Exam covers content through 4/15/16. Some relevant study guides: Order study guide Proofs study guide Invariants study guide Recursion study guide - Practice problems for Midterm 1. Note: these problems total about two or three exams	First exam today in lecture. Use the following seating charts unless you've cleared switching times with the instructors Seating chart for 9-10 section Seating chart for 4-5 section
4/25/16	Mon	Discussion Section, graphs.	Quiz
4/25/16	Mon	Eulerian tours and Fleury's algorithm.	Rosen 10.5 Slides Annotated Slides (B)
4/27/16	Wed	DAGs and topological orderings.	Slides Annotated Slides (B)	HW4 due (Recursion)
4/29/16	Fri	Trees.	Rosen 10.4 through Thm 1, 11.1, 11.2 through Thm 2 Slides Annotated Slides (B) Annotated Slides (D)
5/02/16	Mon	Discussion Section, graph algorithms.	Quiz (5/03)
5/02/16	Mon	Trees. Intro to counting. Sum and product rules.	Rosen 11.1, 11.2 through Thm 2, 6.1, 6.3 JS 2.3 Slides Annotated Slides (B)
5/04/16	Wed	Counting Strategies: Inclusion-exclusion, Categories.	Rosen 8.5 JS 2.3 Slides Annotated Slides (B)	-HW5 due (graphs, DAGs) Solutions (graphs)
5/06/16	Fri	Binomial coefficients.	Rosen 6.3, 6.4 JS 2.3 Slides Annotated Slides (B)
5/09/16	Mon	Discussion Section: trees, counting.	Quiz
5/09/16	Mon	Encoding and decoding for data compression.	Slides
5/11/16	Wed	Encoding and decoding for fixed density binary strings. Lower bounds for sorting.	Rosen 11.2 through Thm 2 JS 4.4 Slides Annotated Slides (B) Annotated Slides (D)	Homework 6 (Trees and cCounting) due
5/13/16	Fri	Applying counting to graphs and sorting.	Rosen 11.2 through Thm 2 JS 4.4 Slides Annotated Slides (B)
5/16/16	Mon	Discussion Section: counting applications	Quiz
5/16/16	Mon	Introduction to probability. Distributions, conditional probabilities, paradoxes	Rosen 7.1, 7.2 JS 9.1, 9.2 Slides Annotated Slides (B) Annotated Slides (D)
5/18/16	Wed	Expected values.	Rosen 7.4 JS 9.3,9.5 Slides Annotated Slides (B)
5/20/16	Fri	Second midterm	Exam covers graphs, counting	Second midterm in lecture - Practice problems for Midterm 2. Note: these problems total about two exams
5/23/16	Mon	Discussion Section: probability	Quiz
5/23/16	Mon	Randomized algorithms 1: selection	Rosen 7.3, 7.4 Slides Annotated Slides (B)
5/25/16	Wed	Variance and concentration bounds	Slides Annotated Slides (B)
5/27/16	Fri	Randomized algorithms 2: hash functions	Slides Annotated Slides (B)	Homework 7 (counting and probability)
5/30/16	Mon	Discussion	Quiz
6/01/16	Wed	Randomized algorithms 3: streaming algorithms	Slides
6/03/16	Fri	Course Review	Slides (Annotated)
6/8/16	Wed	Final Exam (Section B)	PCYNH 109 8:00AM-11:00AM	Practice Final
6/9/16	Thu	Final Exam (Section D)	CENTR 101 3:00PM-6:00PM	Practice Final

Top

Name	Role	Office Hours	Email
Miles Jones	Instructor	See calendar above	mej016@eng.ucsd.edu
Russell Impagliazzo	Instructor	See calendar above	russell@eng.ucsd.edu
Jiapeng Zhang	Teaching Assistant	See calendar above	jpeng.zhang@gmail.com
Yunli Wang	Teaching Assistant	See calendar above	yuw258@ucsd.edu
Lenord Melvix	Teaching Assistant	See calendar above	lmelvix@eng.ucsd.edu
Tanvi Nabar	Teaching Assistant	See calendar above	tgnabar@eng.ucsd.edu
Yan Shu	Teaching Assistant	See calendar above	yashu@eng.ucsd.edu
Qiushi Wang	Teaching Assistant	See calendar above	qiushi@ucsd.edu
Anwaya Aras	Teaching Assistant	See calendar above	aaras@ucsd.edu
Sid(Side) Li	Tutor	See calendar above	s7li@eng.ucsd.edu
Adam Setters	Tutor	See calendar above	asetters@eng.ucsd.edu
Vyom Shah	Tutor	See calendar above	vyshah@ucsd.edu
Anna Raichev	Tutor	See calendar above	araichev@ucsd.edu
Brian Nguyen	Tutor	See calendar above	btn023@ucsd.edu

Delivering Quality Education

Welcome to CSE 21 Spring 2016