Cs70 Homework Solutions
CS 70, Fall 2003
Discrete Mathematics for Computer Science
Instructor:
David Wagner (daw@cs, 765 Soda Hall, 6422758)
TA:
Amir Kamil (kamil@cs, 566 Soda Hall)
Lectures:
TuTh, 3:305:00, 3106 Etcheverry
Sections:
101. F 9:0010:00, 310 Soda
102. F 10:0011:00, 310 Soda
Section notes are available.
Office Hours:
Wagner: Mon 4:005:00, Tue 1:002:00 in 765 Soda.
Kamil: Mon 3:004:00, Wed 2:304:30, at 751 Soda (alcove).
Announcements
Course Overview
The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Computer Science. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them.Broadly speaking the material is similar to that in Math 55; however, Math 55 covers a wider range of topics in less depth and with fewer applications , and is less closely tailored to Computer Science. You should take this course as an alternative to Math 55 if you are intending to major in Computer Science and if you found the more conceptual parts of CS 61A enjoyable and relatively straightforward.
List of course topics:
 Propositions and Proofs
 Mathematical Induction and Recursion
 Propositional Logic: automated proof and problemsolving
 Arithmetic Algorithms: gcd, primality testing, the RSA cryptosystem
 Polynomials and their Applications: errorcorrecting codes, secret sharing
 Probability and Probabilistic Algorithms: load balancing, probabilistic constructions, conditional probability, Bayesian inference
 Diagonalization and Uncomputability
Assignments and Exams
All homeworks are due on Thursday at 3:30 p.m. in the drop box labeled "CS 70" in 283 Soda. Deadlines will be enforced strictly. Late homework will be accepted only in extraordinary circumstances, and may in any case be penalized. The lowest homework grade will be dropped.Exams:
Old exams from previous semesters are available.
Lectures
The following schedule is tentative and subject to change.
Topic  Readings  
1  August 26  Overview; intro to logic  Notes [ps][pdf]. [Rosen 1.1, 1.2] 
2  August 28  Propositional logic; quantifiers  [Rosen 1.31.5] 
3  September 2  Induction  Notes [ps][pdf]. [Rosen 3.3] 
4  September 4  Strong induction  Notes [ps][pdf]. [Rosen 3.3] 
5  September 9  Structural induction  Notes [ps][pdf]. [Rosen 3.4] 
6  September 11  Proofs about algorithms  Notes [ps][pdf]. [Rosen 3.5] 
7  September 16  Stable marriages  External notes 
8  September 18  Cake cutting  Notes (in outline form): [txt]. 
9  September 23  Algebraic algorithms  Notes [ps][pdf]. [Rosen 2.1] 
10  September 25  Number theory  (continuing from same notes as last time). [Rosen 2.4,2.5] 
11  September 30  Midterm review  Notes (in outline form): [txt]. 
October 2  Midterm 1  
12  October 7  Primality testing  Notes [ps][pdf]. [Rosen 2.6] 
13  October 9  RSA  Notes [ps][pdf]. Also [ps][pdf](revised 10/9). [Rosen 2.6] 
14  October 14  Fingerprints, ECC, Secret Sharing  Notes [ps][pdf]. 
15  October 16  Basics of counting  Notes [txt]. [Rosen 4.14.4] 
16  October 21  Basic probability  Notes [ps][pdf]. [Rosen 5.1, 5.2] 
17  October 23  Conditional probability  Notes [ps][pdf]. [Rosen 5.1, 5.2] 
18  October 28  Midterm review  
October 30  Midterm 2  
19  November 4  How to lie with statisics  
20  November 6  Hashing  Notes [ps][pdf]. 
November 11  No class!  
21  November 13  Random variables, expected values  Notes [ps][pdf]. [Rosen 5.3] 
22  November 18  Variance  Notes [ps][pdf]. [Rosen 5.3] 
23  November 20  Polling  Notes [ps][pdf]. 
24  November 25  "Bits on forehead"  
November 27  No class!  Have a great Thanksgivings Day holiday!  
25  December 2  Countability, diagonalization, computability  
26  December 4  Halting problem, Godel's theorem, P vs. NP  A relevant essay [ps][pdf] 
Extra optional reading:
Textbooks
Unfortunately, there is no book that adequately covers all the material in this course at the right level. We will provide lecture notes for most of the lectures. The book Discrete Mathematics and its Applications, 5th Edition (Kenneth H. Rosen, McGrawHill, Inc., New York, 2003) is recommended.Note that you should not view the availability of lecture notes as a substitute for attending class: our discussion in class may deviate somewhat from the written material, and you should take your own notes as well.
Prerequisites
You must have taken CS 61A, Math 1A and Math 1B (or equivalents). If you struggled with any of these courses, you should probably take Math 55 instead of CS 70 as CS 70 is likely to be more conceptual in nature. If you are in any doubt about your preparation for the class, please come and talk to any one of us as soon as possible.Grading Summary
Grading will be on an absolute scale. (However, the instructor reserves the right to add extra points to your grade at the end of the class, in extreme cases.) 30% for the homeworks.
 20% for Midterm I (Thu, Oct 2, held in class).
 20% for Midterm II (Thu, Oct 30, held in class).
 30% for the Final Exam (Wednesday, December 17, 12:303:30pm).
The grading standard is available and has been fixed at the beginning of the course.
The homeworks will be graded by the course reader; depending on the time available, we reserve the right to grade some of the problems in more detail than others, and to award correspondingly more credit for them. Thus, if you turn in incomplete homeworks you are gambling on your grade.
Collaboration
Collaboration on homeworks is welcome and warmly encouraged. You may work in groups of at most three people; however, you must always write up the solutions on your own. Similarly, you may use references to help solve homework problems, but you must write up the solution on your own and cite your sources. You may not share written work or programs with anyone else. You may not receive help on homework assignments from students who have taken the course in previous years, and you may not review homework solutions from previous years.
You will be asked to acknowledge all help you received from others. This will not be used to penalize you, nor will it affect your grade in any way. Rather, is intended only for your own protection.
In writing up your homework you are allowed to consult any book, paper, or published material. If you do so, you are required to cite your source(s). Simply copying a proof is not sufficient; you are expected to write it up in your own words, and you must be able to explain it if you are asked to do so. Your proofs may refer to course material and to homeworks from earlier in the semester. Except for this, all results you use must be proved explicitly.
Copying solutions or code, in whole or in part, from other students or any other source without acknowledgment constitutes cheating. Any student found to be cheating in this class will automatically receive an F grade and will also be referred to the Office of Student Conduct.
We believe that most students can distinguish between helping other students and cheating. Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group is an interaction that we encourage. On the other hand, you should never read another student's solution or partial solution, nor have it in your possession, either electronically or on paper. You should write your homework solution strictly by yourself. You must explicitly acknowledge everyone who you have worked with or who has given you any significant ideas about the homework. Not only is this good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.
Presenting another person's work as your own constitutes cheating, whether that person is a friend, an unknown student in this class or a previous semester's class, a solution set from a previous semester of this course, or an anonymous person on the Web who happens to have solved the problem you've been asked to solve. Everything you turn in must be your own doing, and it is your responsibility to make it clear to the graders that it really is your own work. The following activities are specifically forbidden in all graded course work:
 Possession (or theft) of another student's solution or partial solution in any form (electronic, handwritten, or printed).
 Giving a solution or partial solution to another student, even with the explicit understanding that it will not be copied.
 Working together with anyone outside your homework group to develop a solution that is subsequently turned in (either by you or by the other person).
 Looking up solution sets from previous semesters and presenting that solution, or any part of it, as your own.
In our experience, nobody begins the semester with the intention of cheating. Students who cheat do so because they fall behind gradually and then panic. Some students get into this situation because they are afraid of an unpleasant conversation with a professor if they admit to not understanding something. We would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Remember that the other students in the class are working under similar constraintsthey are taking multiple classes and are often holding down outside employment. Don't hesitate to ask us for helphelping you learn the material is what we're paid to do, after all!
Contact information
If you have a question, your best option is to post a message to the newsgroup. The staff (instructor and TAs) will check the newsgroup regularly, and if you use the newsgroup, other students will be able to help you too. When using the newsgroup, please do not post answers to homework questions before the homework is due.
If your question is personal or not of interest to other students, you may send email to . Email to cs70@cory is forwarded to the instructor and all TAs. We prefer that you use the cs70@cory address, rather than emailing directly the instructor and/or your TA. If you wish to talk with one of us individually, you are welcome to come to our office hours. If the office hours are not convenient, you may make an appointment with any of us by email. There are about 50 of you to every one of us, so please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the newsgroup.
The instructor and TAs will post announcements, clarifications, hints, etc. to this website and to the class newsgroup. Hence you should read the newsgroup regularly whether you post questions to it or not. If you've never done this before, there is online information about how to access UCB newsgroups (see also here for more).
We always welcome any feedback on what we could be doing better. If you would like to send anonymous comments or criticisms, please feel free to use an anonymous remailer to send us email without revealing your identity, like this one.
Accounts and grading software
Some of you may already have named accounts for the lab machines from Instructional Facilities. Lab machines may be found in 2nd floor Soda. If you do not already have an instructional account, go to a Unix machine in 273 Soda and login as 'newacct' (password: 'newacct'). You should receive a 'named' account. You can also read the online instructions.
After you have obtained your account, you will need to register with our grading software. See these instructions.
Miscellaneous
In addition to office hours for the class instructors, HKN (the Eta Kappa Nu honor society) offers free dropin tutoring every weekday 10am4pm in 345 Soda. Contact them for more information.Mail inquiries to.
CS 70 Discrete Mathematics for Computer Science Prof. Luca Trevisan Spring 2007 

 [ News ]  [ Course information ]  [ Homework ]  [ Lecture notes ]  [ Vahab's sections ]  [ Alex's section ] 
News
5/18  The final exam is today, Friday 5/18, 12:30pm3:30pm. The exam is at 105 Northgate. Here's how to get from Soda to 105 Northgate directly: Follow the green arrow. The green X marks the location of the room; the red zone is the CITRIS construction site: 
5/12  An extra review session will be held on Thursday, May 17th, 36pm. This is specifically designed for those who can not come to the Sunday's review session or have last minute questions. Location: 306 Soda Hall. 
5/11  Final review problems have been posted ([ PS ] [ PDF ]). The review session will work best if you attempt to solve each of them before the review session. These problems are not exhaustive — a particular topic not getting covered here does not mean that it will be completely absent from the final. 
5/11  All homework solutions (112) are now posted below. 
Sun 05/06  Mon 05/07  Tue 05/08  Wed 05/09  Thu 05/10  Fri 05/11  Sat 05/12 

12p  Vahab's regular OH, 511 Soda 34p  Alex's regular OH, 511 Soda  3:30p5p  Last lecture, 2 LeConte  5p  HW12 due, 283 Soda 4:30p7:30p  Last supplementary section, 320 Soda  
Sun 05/13  Mon 05/14  Tue 05/15  Wed 05/16  Thu 05/17  Fri 05/18  Sat 05/19 
58p  Final exam review session, 306 Soda; Review problems  [ PS ] [ PDF ]  2p4p  Luca's extra OH, 679 Soda 3p6p  Extra review session (Vahab). Location: 306 Soda 8:30p10p  Alex's extra OH, Cafe Milano  12:30p3:30p  FINAL EXAM in 105 Northgate; you may use up to three handwritten 8.5"x11" pages of notes  summer 
5/7  Homework 12 has been updated to clarify the wording of problem 1(b). The deadline for homework 12 has been extended to Wednesday 05/09, at 5pm. 
5/3  Homework 12 (the last homework!) has been posted, and will be due on Tuesday 05/08. 
5/3  Notes for Lecture 27. Corrected typo in Notes for Lecture 24 
5/3  Notes for Lecture 26 
4/28  Homework 11 posted. It will be due on Thursday, May 3rd. You can use the normal c.d.f. calculator for some of the problems. 
4/24  No class and no office hours on Thursday April 26 because of the faculty retreat 
4/24  For the rest of the semester, I (Alex) will run an extra, nonrequired "supplementary section" on Wednesdays, 4:30pm6pm. The first one will be tomorrow, Wed 04/25, in 320 Soda. I will not prepare a specific plan for the sections, so bring your own questions. One rule — no questions about the current homework. Anything else goes. 
4/19  Notes for lectures 23 and 24 are posted Homework 10 posted. 
4/12  Homework 9 posted. 
4/10  Midterm 2 is today, inclass. You may use 2 pages of notes. The midterm will cover all of the material through last Tuesday's lecture (variance), with an emphasis on material presented after the the first midterm. 
4/9  Quick solutions to the midterm review problems have been posted: [PDF] 
4/6  Some midterm review problems have been posted: [PDF]; more might be posted later. 
4/4  Homework 7 and 8 solutions have been posted. 
4/3  Reminder: Midterm 2 will be in class next Tuesday, 4/10. There will be a review session on Monday, 4/9, 4pm6pm, 306 Soda. Review problems will be posted shortly. 
3/22  Homework 8 posted (will be due after spring break) 
3/21  Notes for lectures 18 and 19 posted 
3/15  HW7 is posted. 
3/13  Posted notes for lecture 16 
3/12  Posted notes for lecture 15 
3/8  Posted HW6 below; note that, for this week only, it will be due on Wednesday, March 14, at 2:30pm 
3/7  Posted notes for lecture 14 
3/5  HW5 has been graded and may be picked up from the box outside 581 Soda (along with other homeworks that weren't picked up in section) 
3/4  Vahab's office hour is moved from Monday 12 pm to Tuesday 11am12pm for the last minute questions. Location: 511 Soda. 
3/3  Additional office hours before the midterm: Prof. Trevisan  Monday (03/05), 4:30pm5:30pm, 679 Soda. Alex  Monday (03/05), 10am11:30am, 611 Soda. 
3/2  Solutions to all of the homeworks up to now are now posted below 
3/2  More midterm review problems are now available. Please look through all the problems in parts 1 and 2 of the review handout, try to solve the ones that you feel you need review on the most, and bring all your questions to the midterm review session tonight. Midterm review, part 2: [PS] [PDF] Midterm review, part 1: [PS] [PDF] (fixed bugs in problem 2) A recap of topics we've covered thus far: [PS] [PDF] 
3/1  Reminder: Midterm 1 will be inclass on Tuesday 3/6. The midterm will be closedlecturenotes, but you may bring a 8.5"x11" sheet of notes (singlesided). 
3/1  There'll be a midterm review session tomorrow (Friday, 03/02) in 306 Soda from 5pm until 7pm (we may stay around until 8pm if there's enough demand) 
2/28  Some midterm review problems have been posted: [PS] [PDF]; more will be posted later 
2/27  If you still don't have enough people in your group for the secret sharing exercise on HW5, you may use the shares for "Alice", "Bob", and "Charlie" (SIDs 10000001, 10000002, and 10000003, respectively). 
2/22  Graded homeworks get passed out in discussion sections. If you don't pick yours up in section, it will be in a box outside Alex's office (581 Soda). 
2/22  
2/22  Notes for lectures 9 and 11 reposted with betterquality pictures. Notes for lecture 12 posted 
2/20  Posted notes for lecture 11 
2/16  Alex's office hours for Monday 02/19 (President's Day) will be 10pm11pm at Cafe Milano (on Bancroft across from Sproul Hall) instead of the usual 34pm slot in Soda. 
2/14  Posted Homework 4 
2/8  Midterm dates posted below 
Information
 Course overview: prerequisites, grading, etc
 Instructor: Luca Trevisan. Email: luca@eecs. Office hours: Thursday 23pm, 679 Soda
 TAs
 Exams:
 Midterm 1: Tuesday, March 6, in class. (20% of grade)
 Midterm 2: Tuesday, April 10, in class. (20% of grade)
 Final exam: Exam Group 20  Friday, May 18, 1230330P, 105 Northgate (25% of grade)
 Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGrawHill, Inc., New York. You do not need to buy the latest edition.
Homework
Homeworks are due in the CS70 drop box in 283 Soda at 2:30pm on Tuesdays. Graded homeworks are returned in section; homeworks not picked up in section will be in a box outside 581 Soda. Homework 1 [PS] [PDF] / Out: Jan 23, Due: Jan 30 / Solution: [PS] [PDF]
 Homework 2 [PS] [PDF] / Out: Jan 30, Updated: Feb 4, Due: Feb 6 / Solution: [PS] [PDF]
 Homework 3 [PS] [PDF] / Out: Feb 7, Due: Feb 13 / Solution: [PS] [PDF]
 Homework 4 [PS] [PDF] / Out: Feb 14, Due: Feb 20 / Solution: [PS] [PDF]
 Homework 5 [PS] [PDF] / Out: Feb 22, Due: Feb 27 / Solution: [PS] [PDF]
 Homework 6 [PS] [PDF] / Out: Mar 8, Due: Mar 14 / Solution: [PS] [PDF]
 Homework 7 [PS] [PDF] / Out: Mar 15, Due: Mar 20 / Solution: [PS] [PDF]
 Homework 8 [PS] [PDF] / Out: Mar 22, Due: Apr 3 / Solution: [PS] [PDF]
 Homework 9 [PS] [PDF] / Out: Apr 12, Due: Apr 17 / Solution: [PS] [PDF]
 Homework 10 [PS] [PDF] / Out: Apr 19, Due: Apr 24 / Solution: [PS] [PDF]
 Homework 11 [PS] [PDF] / Out: Apr 28, Due: May 3 / Solution: [PS] [PDF]
 Homework 12 [PS] [PDF] / Out: May 3, Updated: May 6, Due: May 9 / Solution: [PS] [PDF]
Lectures
 Jan 16, Lecture 1. Contents of the course. Boolean operations. [notes]. Rosen 1.1
 Jan 18, Lecture 2. Proof techniques (contrapositive, contradiction, cases). [notes]. Rosen 1.21.7
 Jan 23. Lecture 3. Mathematical induction. [notes]
 Jan 25. Lecture 4. Strong induction. [notes]
 Jan 30. Lecture 5. The stable matching problem. [notes]
 Feb 1. Lecture 6. More on the stable matching algorithms. Modular arithmetic. [notes]
 Feb 6. Lecture 7. Euclid's GCD algorithm. [notes  same as for lecture 6]
 Feb 8. Lecture 8. Finding inverses — the extended GCD algorithm. [notes  same as for lecture 6]
 Feb 13. Lecture 9. Polynomials. [notes]
 Feb 15 Lecture 10. Secret Sharing. [notes  same as for lecture 9]
 Feb 20. Lecture 11. Errorcorrecting codes. [notes]
 Feb 22. Lecture 12. Introduction to graphs. [notes]
 Feb 27. Lecture 13. Necessary and sufficient conditions for a graph to have an Eulerian tour or path. [notes  same as for lecture 12]
 Mar 1. Lecture 14. The hypercube. Hamiltonian cycles and paths. [notes]
Mar 6. Midterm 1  Mar 8. Lecture 15. Introduction to counting. [notes]
 Mar 13. Lecture 16. Inclusionexclusion formula. Introduction to probability. [notes]
 Mar 15 Lecture 17. The Monty Hall problem. Conditional probabilities and independence. [notes  see notes for previous class and next class]
 Mar 20. Lecture 18. Mutual independence. Computing the probability of the union and intersection of events. [notes]
 Mar 22. Lecture 19. Random variables and expectation. [notes]
 Apr 3. Lecture 20. Independence of random variables, variance, standard deviation, concentration around the expectation. [notes]
 Apr 5. Lecture 21. The binomial distribution and the Poisson distribution. [Notes]
Apr 10. Midterm 2  Apr 12. Lecture 22. The geometric distribution and the coupon collector's problem. [Notes]
 Apr 17. Lecture 23. I.i.d. random variables and the law of large numbers. [notes]
 Apr 19. Lecture 24. Continuous random variables and the Normal distribution. [notes]
 Apr 24. Lecture 25. The central limit theorem. [same notes as lecture 24]
Apr 26 No lecture  May 1. Lecture 26. The Chernoff bound. Lying with statistics. [notes]
 May 3. Lecture 27. Infinity and diagonalization. [notes]
tentative schedule
Lectures 1517 (March 815): counting and basic probability
Lectures 1819 (March 2022): conditional probability
Lectures 2022 (April 312): expectation, linearity of expectation, variance, concentration of probability
April 10: Midterm 2. Syllabus: lectures 120
Lectures 2325 (April 1724): IID random variables, Chernoff bounds, and applications
Lectures 2629 (April 26May 8): infinity, diagonalization and halting problem
One thought on “Cs70 Homework Solutions”