CSE 20 Discrete Mathematics Spring 2012

University of California, San Diego

Course Information

• Objective of this course is to introduce discrete mathematics for computer system designs.

Instructor

• CK Cheng, CSE2130, ckcheng+20@ucsd.edu, 858 534-6184

Schedule

• Outlines (Use index to locate the sections in textbooks)
• Lectures: TTh3:30-4:50PM, Pepper Canyon 109.
• Discussion: A. M2:00-2:50PM, Center 109, B. F10-10:50AM, CSE2154. First discussion session on 4/9.
• Office hours: 2:00-3:00PM Tu; 11:00-12:00PM Th, CSE 2130.

Annoucement

• Last discussion (Friday 8): will go through this problem from the exercises: Frogs problem (Recursive Functions) .
  (Answer to a frequently asked question about the form of the solution in Question 2:
  the third term has a 'n' because the (-1) solution is multiple, that is recurrent:
  at each iteration you add one more term so you can express it that way)
  
• June 4 -
  CK has extra office hours Friday (06/08) 11-12PM Friday and Saturday (06/09) 11-12PM. Lucia's office hours tomorrow is rescheduled to 12:30PM-2:30PM (B260A).
  Rossana will have extra office hours this Friday (06/08) 11AM-12AM.
  Lucia will have extra office hours this Saturday (06/09) 3PM-5PM (B260A).
  Yixin and Jingwei will have extra office hours this Friday 6PM-8PM (B260A).
  Jingwei will have final review session this Sunday 2PM-4PM (CSB 001).
  
• Discussions of May 25 (uploaded because Monday 28th is a holiday): pdf .
  
• Discussions of May 18 and 21 will consist of going over the solutions of midterm 2 .
  
• May 16 - Midterm 2 solution & grading policy is posted (see link below).
  
• May 15 - Homework 3 solution to problem 2.12 is corrected (v3).
  
• May 12 -
  Homework 3 solution is updated (v2).
  Comments to the solution of problem 6 of Midterm 2, Winter 2010 have been added (see below).
  
• May 10 -
  Homework 3 solution is posted (see pdf link below)
  Midterm 2 coverage: residual number systems, cryptography, logic (Boolean algebra, AND, OR, NOT gates, theorems, multivalued logic, Boolean transform).
  For midterm 2, calculators but not cell phones, scratch papers (empty), clarification of the exam in the first 15 minutes.
• May 08 -
  CK Cheng will have extra office hours this Friday 1:00PM-3:00PM (CSE 2130)
  Rossana will extend her office hours this Friday to 1:00PM (11:00AM-1:00PM).
  Yixin will have extra office hours this Friday 3:00PM-5:00PM (TBA)
  Lucia will have extra office hours this Saturday 6:00PM-8:00PM (B260A)
  Jingwei will have question-based midterm-2 review session this Sunday (05/13) 2:00PM-4:00PM at Center Hall 105. Students please prepare with questions.
  
• Apr. 29 - Jingwei's office hours of next Monday (04/30) will be changed to next Thursday (06:00PM-08:00PM at CSE B260A).
• Apr. 25 - Lucia's office hours today (11:00AM-01:00PM) is cancelled due to her health issue.
• Apr. 23 - Register and check your iCliker points at Ted.
  
• Apr. 19 - CK Cheng has extra office hrs 1:30-3:00PM Friday 4/20.
  
• Apr. 17 -
  Rossana will hold office hours this Friday 11:00AM-1:00PM (Discussion-related questions).
  Yixin will be out of town between 04/19 and 04/25.
  Lucia will have extra office hours this Saturday at 2:00PM-4:00PM, CSE B260A.
  Jingwei will have extra question-based midterm review session this Sunday (04/22) 2:00PM-4:00PM Pepper Caynon 109, attendees please prepare with questions.
  Homework 1 and 2 solutions are posted (see pdf link below)
  
• Apr. 16 - Classroom changes from Center Hall 214 to Pepper Canyon Building #109.
• Apr. 12 - Midterm 1 has been rescheduled to the class on Tuesday, 04/24.
• Apr. 4   - Yixin's office hours have been rescheduled to Th11:30AM-1:30PM.
• Apr. 2   - Register your iClicker at http://iclicker.com ASAP.

Teaching Assistants and Tutors

• TA: Jingwei Lu, 20hrs/week
  • E-mail: jlu@cs.ucsd.edu
  • Office Hours: M6-8PM & W6-8PM, CSE B260A
• TA: Rossana Motta, 20hrs/week
  • E-mail: rmotta@eng.ucsd.edu
  • Office Hours: for Discussions-related questions only, send email for appointment
• Tutor: Yixin Zhu
  • E-mail: y4zhu@ucsd.edu
  • Office Hours: Th11:30AM-1:30PM, CSE B260A
• Tutor: Lucia Wang
  • E-mail: xiw041@ucsd.edu
  • Office Hours: W11:00AM-1:00PM, CSE B260A

Textbooks

• Chapters from A Short Course in Discrete Mathematics by Edward A. Bender and S. Gill Williamson A hardcopy is published by Dover in 2004.
• Discrete Mathematics, by Seymour Lipschutz and Marc Lipson, Schaum's Outline Series, Third Edition, McGraw Hill, 2009

Lecture Notes

• Lecture 1. Number Systems: Introduction. (ppt, pdf)
  Text: pages BF9-20, Section 2: Number Systems and Computer Arithmetic.
  Exercise: problems 2.8-11 on pages BF22, solution (pdf)
• Lecture 2. Number Systems: Binary and Gray Codes. (ppt, pdf)
• Lectures 3 & 4. Number Systems: Negative Numbers and Subtraction. (ppt, pdf)
  Exercise: problems 2.12-18 on pages BF22, and problems 10-12 on pages BF24-25, solution (pdf)
• Lecture 5. Number Systems: Residual Number Systems. (ppt, pdf)
  Text: NT Section 1.
  Exercise: Shaum's Chapter 11 Problems 11.14-15, 11.17-18 on pages 285-287.
• Midterm 1, Spring 2011, solution
• Midterm 1: Solutions (.doc format and .pdf format.)
• Lecture 6. Number Systems: Residual Number Systems and Cryptography. (ppt, pdf)
  Text: NT Section 2.
  Exercise of cyptography: NT Section 2 Problems 2.12-15 on page NT-25, solution (pdf)
  Exercise of residual numbers: Shaum's Chapter 11 Problems 11.56-60, 11.123 on pages 296-301.
• Lecture 7. Boolean Algebra: Introduction and Definition (ppt, pdf)
  Text: Shaum's Chapter 15
• Lecture 8. Boolean Algebra: Definition and Theorems (ppt, pdf)
• Lecture 9. Boolean Algebra: Theorems and Transformations (ppt, pdf)
• Midterm 2, Spring 2011 (Problems 7 & 8 will be covered in Part III: Functions), and Solution.
• Midterm 2, Winter 2010, and Solution.
  Notice: page 4, step 6 of problem 6's solution can also be ad+a'+d'+b=d+a'+d'+b
  
• Midterm 2: Solutions & Grading Policy (pdf).
  
• Lecture 10. Boolean Algebra: Theorems and Transformations (ppt, pdf)
  Exercise: Schaum's Chaptger 15 Problems 15.1, 15.5-15, 15.22-26, 15.30-33, 15.43, 15.60, 15.67-68 on pages 389-405.
• Lecture 11. Function: Recursion (ppt, pdf)
  Text: DT Section 2: Recursive Algorithms
  Exercise: DT Section 2: Problems 2.1-2.4 pages DT-26,27, and Problems 10-16 pages DT-54.55, solutions are here (page 24-26).
• Lecture 12. Function: Induction (ppt, pdf)
  Exercise: Schaum's Problems 11.8-13, 11.70-76.
• Lecture 13. Function: Analysis of Recursive Functions (ppt, pdf)
  Exercise: Schaum's Examples 6.7-13 pages 111-117, Problems 6.11-12, 31-35.
• More exercises before the final, solution.
  
• Survey and Response, Summary of the Class.
  
• Final exam (pdf), solution (pdf).

Grading

• iClicker (a ramp function saturates at 80% clicks): 7%
• Discussion Session Attendace: 3% (at least 3 attendances for full credit)
• CK Cheng Office-Hr Visits: 2%
• Midterm 1: 25% (Th 4/19) (Tu 4/24)
  Stats at http://www.gradesource.com/reports/4124/22510/420443.html
• Midterm 2: 25% (Th 5/10) (Tu 5/15)
• Final Exam: 40% (3:00-5:59PM, M 6/11)