Discrete Structures
Instructor | Rudiger Urbanke |
Office | INR 116 |
Phone | +4121 6937692 |
rudiger.urbanke@epfl.ch | |
Office Hours | By appointment |
Teaching Assistant | Marco Mondelli |
Phone | +4121 693 7514 |
Office | INR 038 |
marco.mondelli@epfl.ch | |
Office Hours | Tuesday, 10:15 - 12:15 (or by appointment) |
Teaching Assistant | Mani Bastani Parizi |
Phone | +4121 693 7539 |
Office | INR 033 |
mani.bastaniparizi@epfl.ch | |
Office Hours | (or by appointment) |
Lectures: | Tuesday | 8:15 - 10:00 | Room: xxx | |
Friday | 8:15 - 10:00 | Room: CO1 | ||
Exercise: | Friday | 10:15 - 12:00 | Room: xxx |
Student assistants: tba
Language: English Coefficient/Crédits: 6
Link to the official course description.
Course Description
The basics of mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking and applications and modeling.
Content. A wide variety of practical relevant mathematical problems is studied and solved, thereby teaching students to think mathematically.
The mathematical common sense taught in this course is not only fun, it will also prove to be a valuable resource irrespective of the students' future specialization.
Textbook
We will be using the book “Discrete mathematics and its applications / Kenneth H. Rosen”. Year:2007. ISBN:0-07-331271-1
Grading
Grading. If you do not hand in your final exam your overall grade will be “NA”. Otherwise, your grade will be determined according to the following weighted average:
max( (0.1 H+0.3 M+0.6 F) , F)
Here H is your average homework percentage (out of 100), M is the percentage (out of 100) for your midterm exam, and F is the percentage (out of 100) for your final exam.
This means that the grade is determined by either your final exam only, or the weighted average of the homework, midterm, and final, picking the best result.
If you miss the midterm, only your final exam will be considered.
Homeworks. We will have weekly homeworks. Out of those, 4-6 of will be graded. You can collaborate on the homework by discussing with your colleagues how to solve it. But each of you has to write down his solution in his own words. If you collaborated on a homework, write down the name of your collaborators on top of the first page. No points will be deducted for collaborations. If we find similarities in solutions beyond the listed collaborations we will consider it as cheating.
Midterm and final exams. There will be a midterm exam on xx/11/2014 and a final exam (date to be announced). All information relevant for the exams will be listed on this web page.
– Both exams will be made available in English and in French; your solutions may be given in English, French, or German.
– Both exams are written, in class, closed book; you are not allowed to use a laptop, cellphone, smart-watch, digital assistant, calculator, or any other similar device.
– The midterm exam will take place on Day November xx, 00:00-00:00, in room.
– The date and location of the final exam will be announced as soon as SAC has informed us.
Cheating and plagiarism. If cheating or plagiarism is detected for any homework assignment or during any of the exams, we have to report this to SAC. Note that EPFL has a very strict policy with respect to cheating and any such case is reported to the President of EPFL. See deontology and ethics
Slides
You will find slides for the various lectures posted on this web page. These slides are courtesy Prof. Arjen Lenstra who taught this course for the past 5 years. I would like to thank Prof. Lenstra for making these slides available.
Special Announcements
tba
Detailed Schedule
Date | Topic | Assignment | Due Date/Solutions Posted | Remarks |
---|
17/9 | rules and aim of the course, propositional logic | |||
20/9 | predicates and quantifiers | Homework 1 | ||
27/9 | inference | |||
27/9 | proofs and proof techniques | Graded Homework 2 | ||
01/10 | sets | |||
04/10 | functions | Homework 3 | ||
08/10 | cardinalities | |||
11/10 | sequences | Graded Homework 4 | ||
15/10 | algorithms | |||
18/10 | big O notation | Homework 5 | ||
22/10 | modular arithmetic | |||
25/10 | more on modular arithmetic, groups, applications, prime numbers | Graded Homework 6 | ||
29/10 | induction | |||
01/11 | induction | Homework 7 | ||
05/11 | recursions | |||
08/11 | recursions, review | Special Homework 8 | Preparation for the Midterm | |
12/11 | Midterm | Midterm Version A | ||
15/11 | basic counting: sum and product rule | Homework 9 | ||
19/11 | combinations, permutations, cards | |||
22/11 | combinatorial versus algebraic proofs, pascal's identity, binomial theorem, vandermonde identity | Graded Homework 10 | ||
26/11 | counting via recurrences | |||
29/11 | generating functions | Homework 11 | ||
03/12 | advanced usage of generating functions | |||
06/12 | basic probability; motivating examples; sample space, outcomes, events, distribution function, axioms of probability | Graded Homework 12 | ||
10/12 | conditional probability, bayes, independence | |||
13/12 | Homework 13 | |||
17/12 | ||||
20/12 | Special Homework 14 | Preparation for the Final Exam |