Discrete Math Midterm

MW 4-5:30pm, or by appointment. Course description and goals This course is an introduction to those areas of Mathematics which deal with discrete variables, logical or numerical, deterministic or random. It covers some basic elements of Logic, Set Theory, Algorithms, Mathematical Reasoning, Combinatorics, Probability, Graph Theory.

Instructor: Reza ZadehDiscrete Math Midterm
  1. Discrete Mathematics: Midterm Test with Answers Professor Callahan, section (A or B): Name: NetID: 30 multiple choice, 3 points each.
  2. Mathematics for Computer Science (Discrete math) midterm test need help at 9:30AM EST. You will be paid per question. Show me your knowledgeable in this field of mathematics, 'Trust me bro' will not work. Post your discord.

Winter 2017

EECS 203: Discrete Mathematics Spring 2016. Home / announcements Course overview Staff and hours: References / Notes / Handouts Homework Schedule. Math 55: Discrete Mathematics, Spring 2012 Professor Bernd Sturmfels Office hours: Monday 9:00-11:00, Wednesday 11:00-12:00. Office: 925 Evans Hall email. [email protected] Our class meets Tuesdays and Thursdays, 8:00-9:30am in 10 Evans.

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

MidtermQuestions

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]

Grade breakdown: 50% final, 30% midterm, 20% assignments (4 of them). The midterm and final will be good practice for the ICME qualifying exam.

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 mathematics exam questions

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.

Discrete Math Problems And Answers

Practice Midterm 2 (In-Class) pdf, Solutions pdf.

Problem Sessions

Problem Session 3/20/17, 2 Solutions Problem Session 2/15/17 Solutions

Problem Session 2/11/15 and Solutions

Problem Session 2/10/15 and Solutions

Problem Session 2/10/14 and Solutions

Problem Session 2/20/14 and Solutions

Previous years

Winter 2016: Class website

Winter 2015: Class website

Winter 2014: Class website

Contents of this page

News
Professor and section instructors
Lectures, discussion sections and resources
About the class
Textbook
Exams
Homework
Grading policy
Schedule of lectures, reading and homework

News

(May 3) I'll hold Zoom office hours on Wed May 5, 10-11am, Thurs May 6 5-6pm, and Mon May 10 10-11am.

Spring tool suite 4 download. (May 2) Posted some previous years' final exams and a Midterm 3 for practice.

(Apr 20) Changed PS 14 to be due Sunday, May 2 at 11:59pm.

(Apr 13) Fixed a mistake in 6.5 #36 on PS 11 solutions as initially posted.

(Apr 10) Midterm 2 grades have been released. Regrade requests will be open on Gradescope until 11pm PDT Sunday April 18.

(Apr 6) Fixed a mistake in 6.3 #34(c) on PS 10 solutions as initially posted.

(Apr 6) Midterm 2 clarifications:
On Question 4, the standard deck has 52 cards, with 13 cards (2through 10, Jack, Queen, King, Ace) in each of four suits (Spades,Hearts, Diamonds, Clubs). There are no jokers. A bridge hand is any13 cards from the deck. In the 4-4-3-2 distribution it is notspecified in advance which suits are to have 4, 3 or 2 cards.
On Question 5, 'permutation' means that each of the 26 letters is usedonce.

(Mar 30) Posted previous years' Midterm 2 exams for practice under Exams, below.

(Mar 15) First group of problems on PS 9 is from Ch. 5.2, not 5.1 as originally posted.

(Mar 9) On PS 8, changed Ch.4 Supplementary Ex. 24 to 4.3 #6, which is the one I meant to assign.

(Feb 25) Today's Q&A for Lecture 11 started late and didn't get recorded because of computer problems. Only the blackboard slides are available on bCourses. I'll try to be sure this doesn't happen again.

(Feb 24) Midterm 1 questions and solutions are posted under Exams, below.

(Feb 22) Fixed a mistake on PS 6, which should say 4.4 12(c) (there is no 12(f)).

(Feb 18) Posted some Midterm 1 exams from previous years for practice, see Exams, below.

Math

(Jan 26) Posted Problem Set 1 solutionson bCourses.See the end of the solutions for which problems will be graded.

(Jan 21) I moved problems 1.6: 10(e), 16(a,b) from Problem Set 1 to 2, since they involve quantifiers.

(Jan 19) Problem Sets 1 and 2 are now posted below. I'll generally try to stay more than a week ahead posting problem sets.

(Jan 17) Prerecorded lectures for the first week and a half are now posted in the bCourses Media Gallery. View segments 1-1 and 1-2 for the first class, 2-1, 2-2, and 2-3 for the second, and so on.

(Jan 4) Welcome to Math 55! The course will be held online this semester—see below for details. Please check here occasionally for updates and announcements.

Professor and section instructors

Professor: Mark Haiman, .I am not holding fixed office hours. Instead, I will be available forquestions during a portion of the lecture time, and will monitor thePiazza discussion. If you have individual concerns that you need todiscuss, you can contact me by email.

Prof. Haiman Zoom office hours during RRR and finals week:Wed May 5, 10-11am, Thurs May 6 5-6pm, Mon May 10 10-11am.

Section instructors

  • Ovidiu Avadanei
  • Calvin McPhail-Snyder
  • Eduardo Oregon-Reyes
  • Benjamin Siskind
  • Robert Wang

Lectures, discussion sections and resources

Links:bCourses,Piazza.

This class is online. Theclass bCoursessite provides recorded lecture videos, Zoom links, exams, solutions toexams and homework, and access to Gradescope for submitting work.

Lectures will consist of pre-recorded talks on course topics plus alive Q&A session when you can ask questions about the pre-recordedlectures.

The Q&A session will take place on Tuesdays and Thursdays in thelast 30 minutes of the scheduled lecture time, 1:30-2:00pm (actualstart time 1:30, not 'Berkeley time'). The pre-recorded portion willtotal 50 minutes for each scheduled 80 minute lecture period. I willtry to post the pre-recorded portions ahead of the scheduled time.

Discussion sections will be live on Zoom at the scheduled time.Enrollment is via CalCentral. The professor and GSI's have no controlover enrollment. Because GSI's already face a heavy workload, youmay not attend a discussion section that you are not registered for.

Exams will be given with a 24 hour window for completion. Classparticipation will not be a basis for grading. This means that it ispossible to take this class asynchronously or with time conflicts, ifyou accept that you might not be able to take full advantage ofdiscussion sections or the Q&A portion of the lecture.

Jointhe Piazzadiscussion board to get help from classmates, the GSI's, and me. Iencourage you to post questions on Piazza rather than emailing them tothe teaching staff.

The Student LearningCenter offers online drop-in tutoring and may be organizing studygroups for this class.

About the class

We will cover the basic principles of logic, mathematical induction, sets, relations, and functions, and provide an introduction to graph theory, elementary number theory, combinatorics, algebraic structures, and discrete probability theory.

One of the main purposes of this class is to learn how to construct and write mathematical proofs. If a problem says 'prove' or 'show that' or a similar phrase, it means you are to give a logically correct and coherent argument, written in complete sentences. This requires time and careful thought. It will not always be apparent right away how to approach a problem. The process of working out how to prove or disprove a mathematical statement is a creative one, not as mechanical as solving the more computational problems that you may be used to. Often you will have to try several things, and spend some time being stuck, before you find an idea that works.

This means it is extra important not to wait until the last day to do homework and to do assigned reading ahead of the lectures. If you are confused about anything in the reading, hopefully the lectures and Q&A sessions will help clarify it.

Prerequisites

This course does not have an official prerequisite, but you will need general mathematical maturity appropriate to a sophomore level class. Math 55 and CS 70 cannot both be taken for credit.

Textbook

Kenneth H. Rosen, Discrete Mathematics and its Applications,8th Edition, McGraw-Hill (2019). TheCal StudentStore has a reduced price paperback UC Berkeley custom edition.

We will cover material from the following sections of the book (not necessarily in order)

  • Chapter 1, all sections
  • Chapter 2, sections 2.1-2.5
  • Chapter 4, sections 4.1-4.4 and 4.6
  • Chapter 5, sections 5.1-5.3
  • Chapter 6, sections 6.1-6.5
  • Chapter 7, all sections
  • Chapter 8, 8.5-8.6
  • Chapter 10, sections 10.1-10.4 and 10.7-10.8

Exams

There will be two midterm exams and final exam. They are meant to be completed within the regularly scheduled time (see Ground Rules, below), but will be available to complete at any time within a 24 hour window. Posting on Piazza will be inactive during this window.

Exams will be available to download from Gradescope after 8:00pm California time on the day before the exam day. Answers are to be uploaded to Gradescope by 8:00pm on the exam day. Late submissions will lose points. Gradescope will stop accepting submissions after 11:59pm. Gradescope will not enforce the time limit, but you are expected to do your best to honor it—see Academic Honesty, below.

Missed midterms will be overridden by your final exam grade. There are no make-ups for the final exam.

There is no lecture on the dates of the midterm exams.

  • Midterm 1, 80 minutes official time, released 8:00pm Mon, Feb 22, due 8:00pm Tues, Feb 23.
    Covers Lectures 1-10, Problem Sets 1-5. Subject matter is whatever has been covered on homework problems. Exam problems will be generally similar in difficulty to homework problems, excluding those that would not be reasonable to do in a limited time.
    Questionsand Solutions
  • Midterm 2, 80 minutes official time, released 8:00pm Mon, Apr 5, due 8:00pm Tues, Apr 6
    Covers Lectures 11-19, Problem Sets 6-10, and may rely on earlier material as needed. As before, subject matter is what has been covered on homework problems.
    Questionsand Solutions
  • Final Exam, 3 hours official time, released 8:00pm Wed, May 12, due 8:00pm Thurs, May 13
    Covers all course material with some extra emphasis on Lectures 20-26, Problem Sets 11-14. Subject matter is whatever has been covered on homework problems.

Ground rules

Exams are open book. You may consult your own notes, the textbook, and any other books or general information web resources. You may not receive assistance from other people or from web resources that provide answers to specific questions.

Exams will be of an appropriate length so that students should be able to complete them within the scheduled time of 80 minutes for each midterm, 3 hours for the final. This time limit will not be enforced, but you should make your best effort to honor it. Students who have accommodations from DSP allowing extended time on exams may adjust their time limit accordingly.

Academic honesty

Receiving assistance on exams from another person or from a web resource that provides answers to questions interactively is not allowed, and constitutes cheating. Giving assistance to others is also cheating.

I don't consider it cheating to exceed the official time for the exam by a small amount. However, I strongly encourage you to do your best to observe the time limits. I will try to keep the exams short enough so that exceeding the time limit shouldn't help much.

This class is not graded on a curve. I will set grade cutoffs based on my judgment about the degree of mastery shown by various kinds of answers to exam questions. It is theoretically possible (although unlikely in practice) for everyone to get an A on an exam, or for everyone to get an F!

Evidence of cheating, such as clearly copied answers, will result in a score of zero on the affected exam and possible referral for other disciplinary action.

Since it is impractical to proctor online exams, the ground rules are intended to minimize the incentive to cheat, and to make sure that any cheating that does occur will not adversely affect the grades of students who adhere to the rules.

For practice

Your best study strategy for exams will be to review the homeworkproblems and do other similar problems from the book for practice (oddnumbered problems have answers in the book).

Here are some Math 55 exams from previous years. The timing ofexams varies, so Midterm 1 from past years may sometimes cover thingswe haven't covered yet on our Midterm 1.

Midterm 1Ribet Spring 2019(with answers),Haiman Fall 2018 with answers,Williams Spring 2018 practice exam(with answers),Srivastava Spring 2016 practice exam(with answers),Srivastava Spring 2016 real exam(with answers)

Past year midterm exams posted here were mostly a bit later in thesemester than our midterms this year, so you will find relevantpractice questions for our Midterm 2 on both the old midterm 1 examsabove, and the midterm 2 exams below. Most of the later past yearmidterms also have questions on topics that we haven't covered yet onour Midterm 2.

Midterm 2Ribet Spring 2019 (withanswers),Haiman Fall 2018 with answers,Williams Spring 2018 practice exam (withanswers),Srivastava Spring 2016 practice exam (withanswers),Srivastava Spring 2016 real exam (withanswers)Ribet Spring 2015 with answers

Here are past year final exams and a Midterm 3.

Final ExamRibet Spring 2019 (withanswers),Haiman Fall 2018 Midterm 3 with answers,Haiman Fall 2018 Final with answers,Srivastava Spring 2016 practice exam (with answers)Srivastava Spring 2016 real exam with answers

Homework

Homework assignments will be due each week, usually on Monday, at 8:00pm Califonia time on the due date.

You will need to scan your homework solutions in PDF format and upload them on Gradescope.

Each homework set will typically have 10-20 problems, of which oneor two (announced when solutions are posted) will be selected forcareful grading. The remaining problems will just be checked quickly.

Discrete Math Midterm Review

Exam questions will cover material that has been previouslyassigned on homework. Your best preparation for exams is to do allthe homework problems carefully.

Ground rules

Discrete Math Midterm

You may discuss ideas for solving the homework problems with other students. If you do work in groups on homework, you must list the students you worked with and write up your solutions independently. This last point is extremely important, because it is the only way to learn to write complete and correct mathematical arguments.

Homework answers copied from any source will receive a grade of zero, with possible referral for other disciplinary action in case of repeat offenses.

Grading policy

Homework 15%, two midterms 20% each, Final Exam 45%.

Your final exam grade, after conversion to letter grade points,overrides any missed midterms or lower midterm grades (except scores of zero given for cheating). There will be no makeup exams.

All homework assignments count towards your grade, none aredropped.

Incomplete grades are rarely given, and only in cases where astudent has missed the final exam due to a serious, documented illnessor emergency, and has at least a grade of C on other work.

Schedule of lectures, reading and homework

DatePrerecorded lecture topicsReadingHomework
1/191-1 Welcome, 1-2 Logical propositions1.1.1-5, 1.2.1-2Problem Set 1, due Mon 1/25
1.1: 12(c,d,f), 14(b,f), 22(a,d), 30(b), 34(d), 42;1.2: 2;1.3: 8(c), 12(b), 14 for 12(b), 36, 44;1.6: 2.
→1.6: Moved 10(e), 16(a,b) to PS 2
Solutions
1/212-1 More on logical propositions, 2-2 Logical equivalence, 2-3 Rules of inference1.3.1-4, 1.6.1-6
1/263-1 Puzzles, 3-2 Predicates and quantifiers1.2.5, 1.4.1-8Problem Set 2, due Mon 2/1
1.2: 40;1.4: 10(b,c,e), 12(a-g), 36(b,c), 52, 54(b,c,d);1.5: 10(d,h,j), 20(c), 24(d), 28(e) and explain, 30(c), 40(b), 44;1.6: 10(e), 16(a,b), 24, 26
Solutions
1/284-1 Negation and order of quantifiers, 4-2 Uniqueness quantifier, 4-3 Inferences with quantifiers1.4.9-10, 1.4.12, 1.5 (all), 1.6.7-8
2/25-1 Ideas about proofs, 5-2 Rational and irrational numbers1.7 (all)Problem Set 3, due Mon 2/8
1.7: 8, 12;1.8: 6, 16, 22, 28;2.1: 10, 12, 20, 46(a,b);2.2: 22, 32 (and explain your answers), 34 (either as suggested or by any logically correct method).
Solutions
2/46-1 More ideas about proofs, 6-2 Sets1.8 (all), 2.1.1-4, 2.1.7-8, 2.2.1-3
2/97-1 More on sets, 7-2 Functions2.1.5-6, 2.3 (all)Problem Set 4, due Wed 2/17
2.1: 24, 26, 32, 36(a); 2.2 36(b); 2.3 2, 6(a), 20, 34(b) 72; 2.5:4(a), 10.
Solutions
2/118-1 Cardinality, 8-2 Uncountable sets2.5 (all)
2/169-1 Divisibility, quotients and remainders, 9-2 Modular arithmetic4.1.1-4Problem Set 5, due Mon 2/22
4.1: 4, 8, 14(c), 18(f)(try to do it efficiently, and show work), 42, 46;4.3: 4(c,d,e), 12, 16(a,b), 28, 32(c)(show work), 50, 54
Solutions
2/1810-1 Remainder arithmetic, 10-2 Prime numbers, 10-3 GCD and LCM4.1.5, 4.3.1-7
Midterm 1 Tues 2/23
More info under Exams, above
2/2511-1 Solving congruences, 11-2 Bezout's Theorem and extended GCD4.3.8, 4.4.1-2Problem Set 6, Due Mon 3/1
4.3: 22, 40(f); 4.4: 6(d), 12(c), 14
Solutions
3/212-1 Chinese remainder theorem, 12-2 Fermat theorem4.2.1-2, 4.2.4, 4.4.3, 4.4.5Problem Set 7, Due Mon 3/8
4.2: 26 (and explain what the answer says about whether 645 is prime), 32;4.4: 8, 20, 22, 34, 36, 65 (explain how to get the answer in the book using Chinese remainder theorem);4.6: 26, 32
Solutions
3/413-1 A Carmichael number, 13-2 Cryptography, 13-3 RSA public key encryption4.6.1-7
3/914-1 RSA computer demo, 14-2 Unique factorization, 14-3 Proof of Fermat theorem4.6.8 on digital signatures, 4.3.8 on unique factorization, Exercise 4.4.19Problem Set 8, Due Mon 3/15
4.3: 6 (assignment changed!);Ch. 4 Supplementary Exercises (page 326): 40;5.1: 10, 18(b,e), 50, 60
Solutions
3/1115-1 Mathematical induction, 15-2 More induction examples5.1 (all)
3/1616-1 Strong induction, 16-2 More strong induction examples5.2 (all)Problem Set 9, Due Mon 3/29
5.2: 8, 10, 16, 30;5.3: 6(b,c,d), 8(b), 12;6.1: 16, 22(a,b,c,g), 40, 48
→5.2 was posted as 5.1 by mistake
Solutions
3/1817-1 Recursive definitions, 17-2 How to count5.3 (all), 6.1 (all)
Spring recess 3/22-3/26
3/3018-1 Permutations and combinations, 18-2 Pascal's triangle6.3 (all), 6.4.2Problem Set 10, Due Mon 4/5
6.3: 26, 28, 34;6.4: 8, 18, 28, 32
Solutions
4/119-1 The binomial theorem, 19-2 Binomial coefficient identities6.4.1, 6.4.3
Midterm 2 Tues 4/6
More info under Exams, above
4/820-1 Permutations of multisets, 20-2 Permutations and combinations with repetition6.5.1-4Problem Set 11, Due Mon 4/12
6.5: 10(a,c,d,f), 14, 20, 22, 32, 34, 36, 44
Solutions
4/1321-1 The pigeonhole principle, 21-2 Ramsey's theorem6.2 (all)Problem Set 12, Due Mon 4/19
6.2: 6, 16, 36, 42;7.1: 8, 20, 30, 36;7.2: 8, 12, 16
Solutions
4/1522-1 Intro to discrete probability, 22-2 Conditional probability and independence7.1.1-3, 7.2.1-5
4/2023-1 Birthday problem, 23-2 Monty Hall problem, 23-3 Bayes theorem7.1.4, 7.2.8, 7.3 (all)Problem Set 13, Due Mon 4/26
7.1: 42(b,c), 44;7.2: 14, 18, 24, 34;7.3: 4;7.4: 6, 8, 12, 48
Solutions
4/2224-1 Bernoulli trials and random variables, 24-2 Expected values7.2.6-7, 7.4.1-3, 7.4.5
4/2725-1 Independent random variables, 25-2 Variance, 25-3 Chebyshev's theorem7.4.6-8Problem Set 14, Due Sun 5/2 at 11:59pm PDT
7.4: 16, 26, 28, 36, 38;10.2: 18;10.5: 4, 14, 26(a)
Solutions
4/2926-1 Probabilistic constructions, 26-2 Konigsberg bridge problem7.2.10, 10.1 (all), 10.2.1-2, 10.4.1-3, 10.5.1-2
RRR week, 5/3-5/7
Final Exam Thursday, 5/13
More info under Exams, above

Back to top Prof. Haiman's home page

Discrete Mathematics Problems And Solutions