CSE21

Discrete Mathematics for Computer Science


Top



Office Hours and Contact Information

NameRoleEmailOffice Hours and Study Sessions
Miles Jones Instructormej016 (at) eng.ucsd.eduMon, Wed 11-12, CSE 4208
Sahil Agarwal Teaching Assistantsaa034 (at) eng.ucsd.eduSee Calendar Above
Julia Kapich Tutor and Mentor juc033 (at) ucsd.eduSee Calendar Above
Soheil Karimi Tutor and Mentorskarimik (at) ucsd.eduSee Calendar Above
Tommy H Nguyen Tutor and Mentorthn055 (at) ucsd.eduSee Calendar Above
Anna Raichev Tutor and Mentoraraichev (at) ucsd.eduSee Calendar Above
Jiali (Scarlet) Xie Tutor and Mentorjlxie (at) ucsd.eduSee Calendar Above

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.

Top


Welcome Message

Welcome to CSE21! This course is intended to introduce you to the broad field of algorithms and give you the mathematical tools needed to study algorithms and their efficiency. We will learn about sorting and searching, asymptotics, 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.

Grading
Exams70%
Homework30%

Exams: There will be two midterm exams and one final exam. Exams will be given in class, with no make-ups allowed. You may not use calculators or notes. The weighting of the exam scores will be

MAX ( (Final 40%, First Exam 15%, Second Exam 15%), (Final 55%, Best Exam 15%)).

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


Homework: There will be seven 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 seven homework scores will be dropped and the average computed using the remaining six assignments. That is, each of your six best homework scores counts for 5% of your grade.

Homework should be done individually or in pairs. You are free to change partners at any time. Problems should be solved together, not divided up between partners. Homework solutions should be neatly written or typed and turned in through Gradescope.

Students should consult their textbook, class notes, lecture slides, Piazza forum, instructor, TA, 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.


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-
96 92 88 84 80 76 72 68 64

In addition, you must pass the final exam with at least a 60% 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 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. For exams, requests for regrades should be made immediatley by returning your exam on the day you get it back, before ever leaving the room with your exam.


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:

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 within the first three days of class to ensure that reasonable accommodations can be arranged. For more information, see here.

Top


Textbook

The textbook for this course is

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


All textbooks and course materials will be provided to the students free of charge on the opening day (August 2, 2015).


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.

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:

Top


Class Meetings

DateTimeLocation
Lecture Mon, Tu, Th, Fri8:30am - 9:50amCSE 4258 (first week), CSE 4140 (remaining weeks)
Discussion Section Mon, Th10:00am - 10:50amCSE 4258 (first week), CSE 4140 (remaining weeks)
Problem Solving Sessions Tu, Fr10:00am - 10:50amCSE 4258 (first week), CSE 4140 (remaining weeks)
Optional Study Sessions with Tutors See Calendar7 - 9pmCSE 4258 (first week), CSE 4140 (remaining weeks)

Top


Schedule

NOTE: This schedule is subject to change.

DateDaySubjectReferenceLecture slides, HW and Due Dates
8/1/16 Mon Sorting algorithms. Counting comparisons. Using loop invariants to prove algorithms correct. Rosen 1.9, 3.1,
JS 4.3
Lecture 1
HW 1
HW 1 solutions
8/2/16 Tues Linear and binary search. Counting comparisons. Using loop invariants to prove algorithms correct. Rosen 1.9, 3.1,
JS 4.1
Lecture 2
HW 1 due
HW 2
HW 2 solutions
8/4/16 Thur Asymptotic notation. The need for order notation. Rosen 3.2 Lecture 3
HW 3
HW 3 solutions
8/5/16 Fri Time analysis of sorting and searching algorithms. Rosen 3.3 Lecture 4
HW 2 due (sorting, searching, loop invariants).
8/8/16 Mon Intro to recursion. Correctness and time analysis of recursive algorithms. Rosen 4.3, 6.1,
JS 2.4.1
Lecture 5
8/9/16 Tues Divide and conquer, including mergesort and multiplication. Rosen 4.4, 6.3 before Thm 1
JS 7.1, 7.2
Lecture 6
HW 3 due (asymptotic notation, algorithm analysis).
8/11/16 Thur Solving puzzles with graphs. Rosen 8.1, JS 5.1 Lecture 7
8/12/16 Fri First exam. Exam today, covers everything before graphs.
Practice midterm
Solutions
8/15/16 Mon Euler and Hamilton tours. Rosen 8.2, 8.3, 8.5 through Ex. 7
JS 5.2
Lecture 8
HW 4
HW 4 solutions
8/16/16 Tues DAGs and topological orderings. Graph search and reachability. Rosen 8.4 through Thm 1 HW 4 due (graphs).
Lecture 9
HW 5
HW 5 solutions
8/18/16 Thur Trees. Rosen 9.1, 9.2 though Thm 2
JS 5.5.1
Lecture 10
8/19/16 Fri Intro to counting. Sum and product rules. Inclusion-exclusion. Rosen 5.1, 5.3, 6.5
JS 2.3
HW 5 due
Lecture 11
8/22/16 Mon Binomial coefficients. Encoding and decoding. Rosen 5.4, 5.5 Lecture 12
HW 6
HW 6 solutions
8/23/16 Tues Fixed density binary strings. HW 6 due
Lecture 13
8/25/16 Thur Applying counting to graphs and sorting. JS 4.4 Lecture 14
8/26/16 Fri Second exam. Exam today, covers graphs and counting.
Practice midterm
Solutions
8/29/16 Mon Intro to probability. Expected value. Lecture 15
HW 7
8/30/16 Tues Variance and concentration. Lecture 16
HW 7 due
9/1/16 Thur Randomized algorithms. Lecture 17 (review)
9/2/16 Fri Final exam. Practice final
Solutions

Top