- Discrete Math Problems And Answers
- Discrete Math Midterm
- Discrete Math Midterm
- Discrete Math Midterm Exam
- Discrete Math Midterm Study Guide
- Discrete Math Midterm Solutions
- Discrete Math Midterm Exam
Discrete Mathematics Midterm. Professor Callahan. Name: NYU NetID: Multiple Choice. How many possibilities are there for the first, second, third and fourth positions in a car race with 12 cars if all orders of finish are possible? View Discrete Mathematics - MQ1 to Midterm Exam.docx from IT at ACLC - Naga (AMA Computer Learning Center). Question 1 Not yet answered Marked out of 1.00 Question text ¬(P ∨ Q) is. Start studying Discrete Math Midterm. Learn vocabulary, terms, and more with flashcards, games, and other study tools.
Instructors:
Mike Clancy(779 Soda Hall,642-7017)
David Wagner(629 Soda Hall,642-2758)
CPS102 DISCRETE MATHEMATICS Practice Final Exam In contrast to the homework, no collaborations are allowed. You can use all your notes, calcu-lator, and any books you think are useful. Write legibly and formulate each answer concisely, using only the space provided on this handout. Your name: credit max Question 1 10 Question 2 10 Question 3 10. During my sophomore year at Dartmouth I took a course in discrete mathematics. The tests were not calibrated to any standard scale, so it was difficult to judge how well you were doing. On the midterm, for example, scores around 50 to 60 out of 100 were at the top of the class, whereas for the final those would be failing.
TA:
Eric Kuo(ekuo@cs)
Addresses:
Contact address:cs70@cory.eecs
Web page:http://www-inst.eecs.berkeley.edu/~cs70/
Lectures:
TuTh, 3:30-5:00, 247 Cory
Sections:
101. M 9:00-10:00, 105 Latimer
102. M 10:00-11:00, 105 Latimer
Office Hours:
Clancy: Mon 1:15-2pm, Tue 5:15-6:30pm, Wed 1:15-3pm in 779 Soda.
Wagner: Mon 3:15-4:30pm in 629 Soda.
Kuo: Wed 10am-noon in 511 Soda, Fri 2-3pm in 711 Soda.
Announcements
- Final exam solutions:[ps],[pdf].
- Final exam: Friday, 5/20, 12:30-3:30pm, 141 McCone.
- Final exam review: Thursday, May 19 from 5-7 pm in 310 Soda Hall.
- Office hours exam week:
Clancy:Tue 5/17 3:30-6:30pm in 779 Soda.Wed 5/18 10-12,1-4pm and Thu 5/17 10-12,1-4pmin Self-Paced Center (room C10 Hearst Field Annex).
Wagner: Mon 5/16 4-6pm, 629 Soda.
Kuo: Wed 5/18 4-6pm, 711 Soda. - Please check the course newsgroup,ucb.class.cs70, for announcementsand many clarifications about potentially confusing subjects.
Course Overview
The goal of this course is to introduce students to ideas and techniquesfrom discrete mathematics that are widely used in Computer Science. Thecourse aims to present these ideas 'in action'; each one will be gearedtowards a specific significant application. Thus, students will see thepurpose 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 withfewer applications,and is less closely tailored to Computer Science. You should take thiscourse as an alternative to Math 55 if you are intending to major in ComputerScience and if you found the more conceptual parts of CS 61A enjoyableand relatively straightforward.
List of course topics:
- Propositions and Proofs
- Mathematical Induction and Recursion
- Propositional Logic: automated proof and problem-solving
- Arithmetic Algorithms: gcd, primality testing, the RSA cryptosystem
- Polynomials and their Applications: error-correcting codes, secret sharing
- Probability and Probabilistic Algorithms: load balancing, probabilisticconstructions, conditional probability, Bayesian inference
- Diagonalization and Uncomputability
Assignments, Quizzes, and Exams
All homeworks, except the first one, are due on Thursday at 3:30pm.The deadlines will be enforced strictly. Latehomework will be accepted only in extraordinary circumstances, and mayin any case be penalized. The lowest homework grade will be dropped.Homeworks will be submitted online (no paper submissions accepted).We require PDF or text submissions. We recommend using LaTeX to compose yourhomeworks. (We do not accept raw Microsoft Word .doc files;if you must use Word, please convert to PDF and then submit the PDF file.)
Homeworks:
- Homework 1[ps][pdf] (due Tuesday January 25, 3:30pm);latex template [tex];solutions[ps][pdf].
- Homework 2[ps][pdf] (due Thursday February 3, 3:30pm);latex template [tex];solutions[ps][pdf].
- Homework 3[ps][pdf] (due Thursday February 10, 3:30pm);latex template [tex];solutions[ps][pdf].
- Homework 4[ps][pdf] (due 2/17, 3:30pm);latex template [tex];solutions[ps][pdf].
- Homework 5[ps][pdf] (due 2/24);latex template [tex];solutions[ps][pdf].
- Homework 6[ps][pdf] (due 3/10);latex template [tex];solutions[ps][pdf].
- Homework 7[ps][pdf] (due 3/19);latex template [tex];solutions[ps][pdf].
Sample solns to Q1:[Java code],[Scheme code]. - Homework 8[ps][pdf] (due 3/31);latex template [tex];solutions[ps][pdf].
- Homework 9[ps][pdf] (due 4/7);latex template [tex];solutions[ps][pdf].
- Homework 10[ps][pdf] (due 4/14);latex template [tex];solutions[ps][pdf].
- Homework 11[ps][pdf] (due 4/21);latex template [tex];solutions[ps][pdf].
- Homework 12[ps][pdf] (due 4/28);latex template [tex];solutions[ps][pdf].
- Homework 13[ps][pdf] (due Tuesday, 5/10);latex template [tex];solutions[ps][pdf].
See also: normal tables/calculators.
Quizzes must be completed online twice a week:before 1pm on each Thursday where we have in-class lecture,and before midnight on the Sunday before each section.The quizzes will check your progress so far, so you should be doingthe reading for the Tuesday lecture in advance of the Thursday quiz,and the reading for the Thursday lecture in advance of the Sunday quiz.Quizzes must be done on your own (no collaboration, and no discussion ofthe questions or your answers with others).
Quizzes:
- Quiz #1(due Thu 1/20 1:00pm),solution.
- Quiz #2(due Sun 1/23 11:59pm),solution.
- Quiz #3(due Thu 1/27 1:00pm),solution.
- Quiz #4(due Sun 1/30 11:59pm),solution.
- Quiz #5(due Thu 2/3 1:00pm),solution.
- Quiz #6(due Sun 2/6 11:59pm),solution.
- Quiz #7(due Thu 2/10 1:00pm),solution.
- Quiz #8(due Sun 2/13 11:59pm),solution.
- Quiz #9(due Thu 2/17 1:00pm),solution.
- Quiz #10(due Sun 2/20 11:59pm),solution.
- Quiz #11(due Thu 2/24 1:00pm),solution.
- Quiz #12(due Sun 2/27 11:59pm),solution.
- No Quiz for Thu 3/3.
- No quiz due 3/6, due to problems with the instructional server.
- Quiz #13(due Thu 3/10 1:00pm),solution.
- Quiz #14(due Sun 3/13 11:59pm),solution.
- Quiz #15(due Thu 3/17 1:00pm),solution.
- Quiz #16(due Thu 3/31 1:00pm),solution.
- Quiz #17(due Thu 4/7 1:00pm),solution.
- Quiz #18(due Sun 4/10 11:59pm),solution.
- Quiz #19(due Thu 4/14 1:00pm),solution.
- Quiz #20(due Sun 4/17 11:59pm),solution.
- Quiz #21(due Thu 4/21 1:00pm),solution.
- Quiz #22(due Sun 4/24 11:59pm),solution.
- Quiz #23(due Thu 4/28 1:00pm),solution.
- Quiz #24(due Sun 5/1 11:59pm),solution.
- Quiz #25(due Thu 5/4 1:00pm),solution.
Exams:
- Midterm 1[ps][pdf];solutions[ps][pdf].
- Midterm 2[ps][pdf];solutions[ps][pdf].
- Final[ps][pdf],solutions[ps][pdf].
Old exams from previous semesters are available.
Lectures
The following schedule is tentative and subject to change.Readings in Rosen are optional, in case you want extra backgroundon the subject or a different presentation from a second point of view.
| Topic | Readings | ||
| 1 | Jan 18 | Overview; intro to logic | Notes [ps][pdf]. [Rosen 1.1, 1.2] |
| 2 | Jan 20 | Propositional logic; quantifiers | [Rosen 1.3-1.5] |
| 3 | Jan 25 | Induction | Notes [ps][pdf]. [Rosen 3.3] |
| 4 | Jan 27 | Strong induction | Notes [ps][pdf]. [Rosen 3.3] |
| 5 | Feb 1 | Structural induction | Notes [ps][pdf]. [Rosen 3.4] |
| 6 | Feb 3 | Proofs about algorithms | Notes [ps][pdf]. [Rosen 3.5] |
| 7 | Feb 8 | Minesweeper I | Notes [ps][pdf]. |
| 8 | Feb 10 | Minesweeper II | Notes [ps][pdf]. More notes [ps][pdf]. |
| 9 | Feb 15 | Stable marriages | External notes |
| 10 | Feb 17 | Cake cutting | Notes[txt][ps][pdf]. |
| 11 | Feb 22 | Algebraic algorithms | Notes [ps][pdf]. [Rosen 2.1] |
| 12 | Feb 24 | Number theory | (continuing from same notes as last time). [Rosen 2.4,2.5] |
| 13 | Mar 1 | Primality testing | Notes [ps][pdf]. [Rosen 2.6] |
| Mar 3 | Midterm 1 | ||
| 14 | Mar 8 | RSA | Notes [ps][pdf].Also [ps][pdf]. [Rosen 2.6] |
| 15 | Mar 10 | RSA, Fingerprints | Notes[pdf](updated 3/13). |
| 16 | Mar 15 | Number theory applications | |
| 17 | Mar 17 | Basics of counting | Notes [txt][ps][pdf]. [Rosen 4.1-4.4] |
| Mar 22 | No class! Enjoy Spring break. | ||
| Mar 24 | No class! Enjoy Spring break. | ||
| 18 | Mar 29 | Basic probability | Notes [ps][pdf]. [Rosen 5.1, 5.2] |
| 19 | Mar 31 | Conditional probability | Notes [ps][pdf]. [Rosen 5.1, 5.2] |
| Apr 5 | Midterm 2 | ||
| 20 | Apr 7 | How to lie with statisics | |
| 21 | Apr 12 | Hashing, Load balancing | Notes [ps][pdf]. |
| 22 | Apr 14 | Random variables, expected values | Notes [ps][pdf]. [Rosen 5.3] |
| 23 | Apr 19 | Linearity of expectation, variance | Notes [ps][pdf]. [Rosen 5.3] |
| 24 | Apr 21 | Variance, tail bounds | (Continuing from same notes as last time) |
| 25 | Apr 26 | Polling | Notes [ps][pdf]. |
| 26 | Apr 28 | Minesweeper III | Notes [ps][pdf]. |
| 27 | May 2 | Countability, diagonalization, computability | Notes [txt]. |
| 28 | May 4 | Halting problem, Godel's theorem | Optional: A relevant essay[ps][pdf] Optional: Connections to Scheme eval,Abelman & Sussman, Section 4.1.5,[html] Optional: Time Magazine on Goedel[html] |
| 29 | May 9 | P vs. NP |
Extra optional reading:
- Notes on distributions[ps][pdf]
- Lenstra's notes on probability[ps][pdf].
- For fun: The Infinite Hotel.
Textbooks
Unfortunately, there is no book that adequately covers all the materialin this course at the right level. We will provide lecture notes for mostof the lectures. The book Discrete Mathematics and its Applications,5th Edition (Kenneth H. Rosen, McGraw-Hill, Inc., New York, 2003) isrecommended but not required.Note that you should not view the availability of lecture notesas a substitute for attending class: our discussion in class may deviatesomewhat from the written material, and you should take your own notesas well.
Course readers are available attheNorthside Copy Central as of approximately Thursday, Jan 20.
Prerequisites
You must have taken CS 61A, Math 1A and Math 1B (or equivalents). If youstruggled with any of these courses, you should probably take Math 55 insteadof CS 70 as CS 70 is likely to be more conceptual in nature. If you arein any doubt about your preparation for the class, please come and talkto any one of us as soon as possible.Grading Summary
Grading will be on an absolute scale.Your final grade will be in the range 0-200 and will be computed as thesum from five categories:- 50 points: Homeworks (average of all but your lowest hw score, withthe average capped at 50 pts).
- 10 points: Quizzes (average of your quiz scores, times 1.666, capped at 10 pts).
- 40 points: Midterm I (March 3, held in class).
- 40 points: Midterm II (April 5, held in class).
- 60 points: Final Exam (May 20, 12:30-3:30pm, 141 McCone).
The grading standard is availableand has been fixed at the beginning of the course:The instructors reserve the right to add extra points toyour grade at the end of the class (for instance, if the final examwas unexpectedly harder than intended).
The homeworks will be graded by the course reader;depending on the time available, we reserve the right to grade some ofthe problems in more detail than others, and to award correspondingly morecredit for them. Thus, if you turn in incomplete homeworks you are gamblingon 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 onyour own. Similarly, you may use references to help solve homework problems,but youmust write up the solution on your own and cite your sources.You may not share written work or programs with anyone else. You may notreceive help on homework assignments from students who have taken the coursein previous years, and you may not review homework solutions from previousyears.
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 inany way. Rather, this is intended only for your ownprotection.
If you work in a group, you'll be required to change group partnersafter the first midterm.
In writing up your homework you are allowed to consult any book,paper, or published material. If you do so, you are required to citeyour source(s). Simply copying aproof is not sufficient; you are expected to write it up in your ownwords, and you must be able to explain it if you are asked to do so.Your proofs may refer to course material and tohomeworks from earlier in the semester.Except for this, all results you use must be provedexplicitly.
Copying solutions or code, in whole or in part, from other studentsor any other source without acknowledgment constitutes cheating. Any studentfound to be cheating in this class will automatically receive an F gradeand will also be referred to the Office of Student Conduct.
We believe that most students can distinguish between helping otherstudents and cheating.Explaining the meaning of a question, discussing a way of approaching asolution, or collaboratively exploring how to solve a problem withinyour group is an interaction that we encourage.On the other hand, youshould never read another student's solution or partialsolution, nor have it in your possession, either electronically or onpaper. You should write your homework solution strictly by yourself. Xampp mobile. You mustexplicitly acknowledge everyone who you have worked with or who hasgiven you any significant ideas about the homework. Not only is this goodscholarly conduct, it also protects you from accusations of theft ofyour 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 aprevious semester's class, a solution set from a previous semester ofthis course, or an anonymous person on the Web whohappens to have solved the problem you've been asked tosolve. Everything you turn in must be your own doing, and it is yourresponsibility to make it clear to the graders that it really is yourown work. The following activities are specifically forbidden in allgraded course work:
- Possession (or theft) of another student's solution or partial solutionin any form (electronic, handwritten, or printed).
- Giving a solution or partial solution to another student, even with theexplicit understanding that it will not be copied.
- Working together with anyone outside your homework group to develop a solutionthat is subsequently turned in (either by you or by the other person).
- Looking up solution sets from previous semesters and presentingthat solution, or any part of it, as your own.
In our experience, nobody begins the semester with the intention ofcheating. Students who cheat do so because they fall behind graduallyand then panic. Some students get into this situation because they areafraid of an unpleasant conversation with a professor if they admit tonot understanding something. We would much rather deal with yourmisunderstanding early than deal with its consequences later. Even ifyou are convinced that you are the only person in the class thatdoesn't understand the material, and that it is entirely your faultfor having fallen behind, please overcome your feeling of guilt andask for help as soon as you need it. Remember that the other studentsin the class are working under similar constraints--they are takingmultiple classes and are often holding down outside employment.Don't hesitate to ask us for help--helping you learn thematerial 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 theucb.class.cs70 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 homeworkquestions before the homework is due.
If your question is personal or not of interest to other students,you may send email to cs70@cory.eecs.berkeley.edu.Email to cs70@cory is forwarded to the instructor and all TAs. We prefer that you use the cs70@cory address, rather thanemailing directly the instructor and/or your TA.If you wish to talk with one of us individually, you are welcometo come to our office hours.If the office hours are not convenient,you may make an appointment with any of us by email.
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 abouthow toaccess UCB newsgroups (see alsoherefor 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 emailwithout revealing your identity,like this one.
Accounts and grading software
We will use 'class' accounts this semester.We will account forms in class.Lab machines may be found in 2nd floor Soda.Further information ishere.
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 drop-in tutoring.Contact them for more information.Mail inquiries tocs70@cory.eecs.berkeley.edu.
Discrete Math Problems And Answers
Instructor: Reza ZadehWinter 2017
Time: Tue, Thu 10:30 AM - 11:50 AM
Room: Bishop Auditorium
Topics Covered
- Basic Algebraic Graph Theory
- Minimum Spanning Trees and Matroids
- Maximum Flow and Submodularity
- NP-Hardness
- Approximation Algorithms
- Randomized Algorithms
- The Probabilistic Method
- Spectral Sparsification
Course Description
This course is targeting doctorate students with strong foundations in mathematics who wish to become more familiar with the design and analysis of discrete algorithms. An undergraduate course in algorithms is not a prerequisite, only familiarity with basic notions in linear algebra and discrete mathematics.
Required textbook:
Algorithm Design by Kleinberg and Tardos [KT]
Optional textbooks:
Graph Theory by Reinhard Diestel [D]
Approximation Algorithms by Vijay Vazirani [V]
Randomized Algorithms by Rajeev Motwani and Prabakhar Raghavan [MR]
The Probabilistic Method by Noga Alon and Joel Spencer [AS]
Midterm: Thursday, Feb 16th
Final: 03/22/2017, 12:15 - 3:15 P.M. at STLC 114 (science teaching & learning center)
Assignments
- Assignment 1 [pdf] [tex], Due at the beginning of class Thursday 01/26. [Solutions]
- Assignment 2 [pdf] [tex], Due at the beginning of class Thursday 02/09. [Solutions]
- Assignment 3 [pdf] [tex], Due at the beginning of class Thursday 03/02 [Solutions]
- Assignment 4 [pdf] [tex], Due at the beginning of class Thursday 03/16 [Solutions]
References
Note that these references are not intended to be any substitute for the material covered during lectures.- Tu 1/10: Lecture 1 'The min-cut is small' (Intro to Graph Theory, Karger's Global Min-Cut): D 1.1-1.6; Notes; A New Approach to the Minimum Cut Problem (Karger and Stein)
- Th 1/12: Lecture 2 'Pigeons and eagles' (s-t Min-Cut, Max-Flow, Ford-Fulkerson): KT 7: Notes
- Tu 1/17: Lecture 3 (Applications of Max-Flow, Probabilistic Method): Notes; MR 5; AS 1
- Th 1/19: Lecture 4 (Minimum Spanning Trees): Notes
- Tu 1/24: Lecture 5 (Ramsey Numbers and Probabilistic Method):MST Alg with Inverse-Ackerman Complexity ; , Exhausting a Graph, Resistance of a Graph and Cover Time; Notes; MR 6
- Th 1/26: Lecture 6 (Cover Times): 'Random Walks on Graphs: A Survey'
- Tu 1/31: Lecture 7 (Markov Inequality; Tighter Bounds for Cover Times)
- Th 2/02: Lecture 8 (2-SAT, 3-SAT, Intro to Problem Classes): Notes; The NP Compendium; KT 8
- Tu 2/07: Lecture 9 (Problem Classes, Reductions): Notes; The NP Compendium; KT 8
- Th 2/09: Lecture 10 (Approximation Algorithms) Notes; KT 11
- Tu 2/14: Lecture 11 (Midterm Review)
- Th 2/16: Midterm Solutions
- Tu 2/21: Lecture 13 (Approximation Algorithms - vertex cover, bin-packing) Notes; KT 11
- Th 2/23: Lecture 14 (TSP). Paths, Trees, and Flowers.
- Tu 2/28: Lecture 15 (Dynamic Programing): KT 6
- Th 3/02: Lecture 16 (Asymmetric TSP, Max Cut): V 26; An O(log n/log log n)-approximation Algorithm for ATSP (Asadpour et al.) (Goemans-Williamson Max-Cut): CMU Max-Cut Notes; Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (Goemans and Williamson)
- Tu 3/07: Lecture 17 (Graph Sparsification) Notes; Graph Sparsification by Effective Resistances (Spielman and Srivastava)
- Th 3/09: Lecture 18 (Machine Learning): Impossibility Theorem; Uniqueness theorem; KMeans++
- Tu 3/14: Lecture 19 (Matroids): MIT Matroid Notes
Practice Exams
Spring 2012 Qual pdf.
Fall 2012 Qual pdf.
Spring 2013 Qual pdf.
Discrete Math Midterm
2016 Midterm pdf, Solutions pdf
2015 Midterm pdf, Solutions pdf
2014 Midterm and Solutions pdf,
2011 Midterm pdf, Solutions pdf.
2010 Midterm pdf, Solutions pdf.
Practice Midterm 1 (In-Class) pdf, Solutions pdf.
Practice Midterm 2 (In-Class) pdf, Solutions pdf.
Problem Sessions
Discrete Math Midterm
Problem Session 3/20/17, 2 Solutions Problem Session 2/15/17 SolutionsDiscrete Math Midterm Exam
Problem Session 2/11/15 and Solutions
Problem Session 2/10/15 and Solutions
Problem Session 2/10/14 and Solutions
Discrete Math Midterm Study Guide
Problem Session 2/20/14 and Solutions
Previous years
Winter 2016: Class website
Discrete Math Midterm Solutions
Winter 2015: Class website
Discrete Math Midterm Exam
Quizzes must be completed online twice a week:before 1pm on each Thursday where we have in-class lecture,and before midnight on the Sunday before each section.The quizzes will check your progress so far, so you should be doingthe reading for the Tuesday lecture in advance of the Thursday quiz,and the reading for the Thursday lecture in advance of the Sunday quiz.Quizzes must be done on your own (no collaboration, and no discussion ofthe questions or your answers with others).
Quizzes:
- Quiz #1(due Thu 1/20 1:00pm),solution.
- Quiz #2(due Sun 1/23 11:59pm),solution.
- Quiz #3(due Thu 1/27 1:00pm),solution.
- Quiz #4(due Sun 1/30 11:59pm),solution.
- Quiz #5(due Thu 2/3 1:00pm),solution.
- Quiz #6(due Sun 2/6 11:59pm),solution.
- Quiz #7(due Thu 2/10 1:00pm),solution.
- Quiz #8(due Sun 2/13 11:59pm),solution.
- Quiz #9(due Thu 2/17 1:00pm),solution.
- Quiz #10(due Sun 2/20 11:59pm),solution.
- Quiz #11(due Thu 2/24 1:00pm),solution.
- Quiz #12(due Sun 2/27 11:59pm),solution.
- No Quiz for Thu 3/3.
- No quiz due 3/6, due to problems with the instructional server.
- Quiz #13(due Thu 3/10 1:00pm),solution.
- Quiz #14(due Sun 3/13 11:59pm),solution.
- Quiz #15(due Thu 3/17 1:00pm),solution.
- Quiz #16(due Thu 3/31 1:00pm),solution.
- Quiz #17(due Thu 4/7 1:00pm),solution.
- Quiz #18(due Sun 4/10 11:59pm),solution.
- Quiz #19(due Thu 4/14 1:00pm),solution.
- Quiz #20(due Sun 4/17 11:59pm),solution.
- Quiz #21(due Thu 4/21 1:00pm),solution.
- Quiz #22(due Sun 4/24 11:59pm),solution.
- Quiz #23(due Thu 4/28 1:00pm),solution.
- Quiz #24(due Sun 5/1 11:59pm),solution.
- Quiz #25(due Thu 5/4 1:00pm),solution.
Exams:
- Midterm 1[ps][pdf];solutions[ps][pdf].
- Midterm 2[ps][pdf];solutions[ps][pdf].
- Final[ps][pdf],solutions[ps][pdf].
Old exams from previous semesters are available.
Lectures
The following schedule is tentative and subject to change.Readings in Rosen are optional, in case you want extra backgroundon the subject or a different presentation from a second point of view.
| Topic | Readings | ||
| 1 | Jan 18 | Overview; intro to logic | Notes [ps][pdf]. [Rosen 1.1, 1.2] |
| 2 | Jan 20 | Propositional logic; quantifiers | [Rosen 1.3-1.5] |
| 3 | Jan 25 | Induction | Notes [ps][pdf]. [Rosen 3.3] |
| 4 | Jan 27 | Strong induction | Notes [ps][pdf]. [Rosen 3.3] |
| 5 | Feb 1 | Structural induction | Notes [ps][pdf]. [Rosen 3.4] |
| 6 | Feb 3 | Proofs about algorithms | Notes [ps][pdf]. [Rosen 3.5] |
| 7 | Feb 8 | Minesweeper I | Notes [ps][pdf]. |
| 8 | Feb 10 | Minesweeper II | Notes [ps][pdf]. More notes [ps][pdf]. |
| 9 | Feb 15 | Stable marriages | External notes |
| 10 | Feb 17 | Cake cutting | Notes[txt][ps][pdf]. |
| 11 | Feb 22 | Algebraic algorithms | Notes [ps][pdf]. [Rosen 2.1] |
| 12 | Feb 24 | Number theory | (continuing from same notes as last time). [Rosen 2.4,2.5] |
| 13 | Mar 1 | Primality testing | Notes [ps][pdf]. [Rosen 2.6] |
| Mar 3 | Midterm 1 | ||
| 14 | Mar 8 | RSA | Notes [ps][pdf].Also [ps][pdf]. [Rosen 2.6] |
| 15 | Mar 10 | RSA, Fingerprints | Notes[pdf](updated 3/13). |
| 16 | Mar 15 | Number theory applications | |
| 17 | Mar 17 | Basics of counting | Notes [txt][ps][pdf]. [Rosen 4.1-4.4] |
| Mar 22 | No class! Enjoy Spring break. | ||
| Mar 24 | No class! Enjoy Spring break. | ||
| 18 | Mar 29 | Basic probability | Notes [ps][pdf]. [Rosen 5.1, 5.2] |
| 19 | Mar 31 | Conditional probability | Notes [ps][pdf]. [Rosen 5.1, 5.2] |
| Apr 5 | Midterm 2 | ||
| 20 | Apr 7 | How to lie with statisics | |
| 21 | Apr 12 | Hashing, Load balancing | Notes [ps][pdf]. |
| 22 | Apr 14 | Random variables, expected values | Notes [ps][pdf]. [Rosen 5.3] |
| 23 | Apr 19 | Linearity of expectation, variance | Notes [ps][pdf]. [Rosen 5.3] |
| 24 | Apr 21 | Variance, tail bounds | (Continuing from same notes as last time) |
| 25 | Apr 26 | Polling | Notes [ps][pdf]. |
| 26 | Apr 28 | Minesweeper III | Notes [ps][pdf]. |
| 27 | May 2 | Countability, diagonalization, computability | Notes [txt]. |
| 28 | May 4 | Halting problem, Godel's theorem | Optional: A relevant essay[ps][pdf] Optional: Connections to Scheme eval,Abelman & Sussman, Section 4.1.5,[html] Optional: Time Magazine on Goedel[html] |
| 29 | May 9 | P vs. NP |
Extra optional reading:
- Notes on distributions[ps][pdf]
- Lenstra's notes on probability[ps][pdf].
- For fun: The Infinite Hotel.
Textbooks
Unfortunately, there is no book that adequately covers all the materialin this course at the right level. We will provide lecture notes for mostof the lectures. The book Discrete Mathematics and its Applications,5th Edition (Kenneth H. Rosen, McGraw-Hill, Inc., New York, 2003) isrecommended but not required.Note that you should not view the availability of lecture notesas a substitute for attending class: our discussion in class may deviatesomewhat from the written material, and you should take your own notesas well.
Course readers are available attheNorthside Copy Central as of approximately Thursday, Jan 20.
Prerequisites
You must have taken CS 61A, Math 1A and Math 1B (or equivalents). If youstruggled with any of these courses, you should probably take Math 55 insteadof CS 70 as CS 70 is likely to be more conceptual in nature. If you arein any doubt about your preparation for the class, please come and talkto any one of us as soon as possible.Grading Summary
Grading will be on an absolute scale.Your final grade will be in the range 0-200 and will be computed as thesum from five categories:- 50 points: Homeworks (average of all but your lowest hw score, withthe average capped at 50 pts).
- 10 points: Quizzes (average of your quiz scores, times 1.666, capped at 10 pts).
- 40 points: Midterm I (March 3, held in class).
- 40 points: Midterm II (April 5, held in class).
- 60 points: Final Exam (May 20, 12:30-3:30pm, 141 McCone).
The grading standard is availableand has been fixed at the beginning of the course:The instructors reserve the right to add extra points toyour grade at the end of the class (for instance, if the final examwas unexpectedly harder than intended).
The homeworks will be graded by the course reader;depending on the time available, we reserve the right to grade some ofthe problems in more detail than others, and to award correspondingly morecredit for them. Thus, if you turn in incomplete homeworks you are gamblingon 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 onyour own. Similarly, you may use references to help solve homework problems,but youmust write up the solution on your own and cite your sources.You may not share written work or programs with anyone else. You may notreceive help on homework assignments from students who have taken the coursein previous years, and you may not review homework solutions from previousyears.
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 inany way. Rather, this is intended only for your ownprotection.
If you work in a group, you'll be required to change group partnersafter the first midterm.
In writing up your homework you are allowed to consult any book,paper, or published material. If you do so, you are required to citeyour source(s). Simply copying aproof is not sufficient; you are expected to write it up in your ownwords, and you must be able to explain it if you are asked to do so.Your proofs may refer to course material and tohomeworks from earlier in the semester.Except for this, all results you use must be provedexplicitly.
Copying solutions or code, in whole or in part, from other studentsor any other source without acknowledgment constitutes cheating. Any studentfound to be cheating in this class will automatically receive an F gradeand will also be referred to the Office of Student Conduct.
We believe that most students can distinguish between helping otherstudents and cheating.Explaining the meaning of a question, discussing a way of approaching asolution, or collaboratively exploring how to solve a problem withinyour group is an interaction that we encourage.On the other hand, youshould never read another student's solution or partialsolution, nor have it in your possession, either electronically or onpaper. You should write your homework solution strictly by yourself. Xampp mobile. You mustexplicitly acknowledge everyone who you have worked with or who hasgiven you any significant ideas about the homework. Not only is this goodscholarly conduct, it also protects you from accusations of theft ofyour 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 aprevious semester's class, a solution set from a previous semester ofthis course, or an anonymous person on the Web whohappens to have solved the problem you've been asked tosolve. Everything you turn in must be your own doing, and it is yourresponsibility to make it clear to the graders that it really is yourown work. The following activities are specifically forbidden in allgraded course work:
- Possession (or theft) of another student's solution or partial solutionin any form (electronic, handwritten, or printed).
- Giving a solution or partial solution to another student, even with theexplicit understanding that it will not be copied.
- Working together with anyone outside your homework group to develop a solutionthat is subsequently turned in (either by you or by the other person).
- Looking up solution sets from previous semesters and presentingthat solution, or any part of it, as your own.
In our experience, nobody begins the semester with the intention ofcheating. Students who cheat do so because they fall behind graduallyand then panic. Some students get into this situation because they areafraid of an unpleasant conversation with a professor if they admit tonot understanding something. We would much rather deal with yourmisunderstanding early than deal with its consequences later. Even ifyou are convinced that you are the only person in the class thatdoesn't understand the material, and that it is entirely your faultfor having fallen behind, please overcome your feeling of guilt andask for help as soon as you need it. Remember that the other studentsin the class are working under similar constraints--they are takingmultiple classes and are often holding down outside employment.Don't hesitate to ask us for help--helping you learn thematerial 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 theucb.class.cs70 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 homeworkquestions before the homework is due.
If your question is personal or not of interest to other students,you may send email to cs70@cory.eecs.berkeley.edu.Email to cs70@cory is forwarded to the instructor and all TAs. We prefer that you use the cs70@cory address, rather thanemailing directly the instructor and/or your TA.If you wish to talk with one of us individually, you are welcometo come to our office hours.If the office hours are not convenient,you may make an appointment with any of us by email.
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 abouthow toaccess UCB newsgroups (see alsoherefor 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 emailwithout revealing your identity,like this one.
Accounts and grading software
We will use 'class' accounts this semester.We will account forms in class.Lab machines may be found in 2nd floor Soda.Further information ishere.
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 drop-in tutoring.Contact them for more information.Mail inquiries tocs70@cory.eecs.berkeley.edu.
Discrete Math Problems And Answers
Instructor: Reza ZadehWinter 2017
Time: Tue, Thu 10:30 AM - 11:50 AM
Room: Bishop Auditorium
Topics Covered
- Basic Algebraic Graph Theory
- Minimum Spanning Trees and Matroids
- Maximum Flow and Submodularity
- NP-Hardness
- Approximation Algorithms
- Randomized Algorithms
- The Probabilistic Method
- Spectral Sparsification
Course Description
This course is targeting doctorate students with strong foundations in mathematics who wish to become more familiar with the design and analysis of discrete algorithms. An undergraduate course in algorithms is not a prerequisite, only familiarity with basic notions in linear algebra and discrete mathematics.
Required textbook:
Algorithm Design by Kleinberg and Tardos [KT]
Optional textbooks:
Graph Theory by Reinhard Diestel [D]
Approximation Algorithms by Vijay Vazirani [V]
Randomized Algorithms by Rajeev Motwani and Prabakhar Raghavan [MR]
The Probabilistic Method by Noga Alon and Joel Spencer [AS]
Midterm: Thursday, Feb 16th
Final: 03/22/2017, 12:15 - 3:15 P.M. at STLC 114 (science teaching & learning center)
Assignments
- Assignment 1 [pdf] [tex], Due at the beginning of class Thursday 01/26. [Solutions]
- Assignment 2 [pdf] [tex], Due at the beginning of class Thursday 02/09. [Solutions]
- Assignment 3 [pdf] [tex], Due at the beginning of class Thursday 03/02 [Solutions]
- Assignment 4 [pdf] [tex], Due at the beginning of class Thursday 03/16 [Solutions]
References
Note that these references are not intended to be any substitute for the material covered during lectures.- Tu 1/10: Lecture 1 'The min-cut is small' (Intro to Graph Theory, Karger's Global Min-Cut): D 1.1-1.6; Notes; A New Approach to the Minimum Cut Problem (Karger and Stein)
- Th 1/12: Lecture 2 'Pigeons and eagles' (s-t Min-Cut, Max-Flow, Ford-Fulkerson): KT 7: Notes
- Tu 1/17: Lecture 3 (Applications of Max-Flow, Probabilistic Method): Notes; MR 5; AS 1
- Th 1/19: Lecture 4 (Minimum Spanning Trees): Notes
- Tu 1/24: Lecture 5 (Ramsey Numbers and Probabilistic Method):MST Alg with Inverse-Ackerman Complexity ; , Exhausting a Graph, Resistance of a Graph and Cover Time; Notes; MR 6
- Th 1/26: Lecture 6 (Cover Times): 'Random Walks on Graphs: A Survey'
- Tu 1/31: Lecture 7 (Markov Inequality; Tighter Bounds for Cover Times)
- Th 2/02: Lecture 8 (2-SAT, 3-SAT, Intro to Problem Classes): Notes; The NP Compendium; KT 8
- Tu 2/07: Lecture 9 (Problem Classes, Reductions): Notes; The NP Compendium; KT 8
- Th 2/09: Lecture 10 (Approximation Algorithms) Notes; KT 11
- Tu 2/14: Lecture 11 (Midterm Review)
- Th 2/16: Midterm Solutions
- Tu 2/21: Lecture 13 (Approximation Algorithms - vertex cover, bin-packing) Notes; KT 11
- Th 2/23: Lecture 14 (TSP). Paths, Trees, and Flowers.
- Tu 2/28: Lecture 15 (Dynamic Programing): KT 6
- Th 3/02: Lecture 16 (Asymmetric TSP, Max Cut): V 26; An O(log n/log log n)-approximation Algorithm for ATSP (Asadpour et al.) (Goemans-Williamson Max-Cut): CMU Max-Cut Notes; Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (Goemans and Williamson)
- Tu 3/07: Lecture 17 (Graph Sparsification) Notes; Graph Sparsification by Effective Resistances (Spielman and Srivastava)
- Th 3/09: Lecture 18 (Machine Learning): Impossibility Theorem; Uniqueness theorem; KMeans++
- Tu 3/14: Lecture 19 (Matroids): MIT Matroid Notes
Practice Exams
Spring 2012 Qual pdf.
Fall 2012 Qual pdf.
Spring 2013 Qual pdf.
Discrete Math Midterm
2016 Midterm pdf, Solutions pdf
2015 Midterm pdf, Solutions pdf
2014 Midterm and Solutions pdf,
2011 Midterm pdf, Solutions pdf.
2010 Midterm pdf, Solutions pdf.
Practice Midterm 1 (In-Class) pdf, Solutions pdf.
Practice Midterm 2 (In-Class) pdf, Solutions pdf.
Problem Sessions
Discrete Math Midterm
Problem Session 3/20/17, 2 Solutions Problem Session 2/15/17 SolutionsDiscrete Math Midterm Exam
Problem Session 2/11/15 and Solutions
Problem Session 2/10/15 and Solutions
Problem Session 2/10/14 and Solutions
Discrete Math Midterm Study Guide
Problem Session 2/20/14 and Solutions
Previous years
Winter 2016: Class website
Discrete Math Midterm Solutions
Winter 2015: Class website
Discrete Math Midterm Exam
Winter 2014: Class website
