===== Discrete Structures ===== \\ |Instructor|**Rudiger Urbanke**| |Office|[[http://plan.epfl.ch/?room=INR116|INR 116]]| |Phone|**+4121 6937692**| |Email|**rudiger.urbanke@epfl.ch**| |Office Hours|**Just stop by... if you dare ! **|{{:en:courses:img-20141031-wa0003.jpg?400|}}| \\ |Teaching Assistant|**Marco Mondelli**| |Phone|**+4121 693 7514**| |Office|[[http://plan.epfl.ch/?room=INR038|INR 038]]| |Email|**marco.mondelli@epfl.ch**| |Office Hours|**Just stop by**| \\ |Teaching Assistant|**Mani Bastani Parizi**| |Phone|**+4121 693 7539**| |Office|[[http://plan.epfl.ch/?room=INR033|INR 033]]| |Email|**mani.bastaniparizi@epfl.ch**| |Office Hours|**Just stop by**| \\ |**Lectures:** | |Tuesday|8:15 - 10:00|Room: CO1| | | |Friday |8:15 - 10:00|Room: CO1| |**Exercise:** | |Friday|10:15 - 12:00|Room: CO2, CM012, CO122, CO123, CO124, INJ218, INM200, INM010| \\ ---- Student assistants: \\ | **Alfonso Peterssen** | **alfonso.peterssen@epfl.ch** | | **Mohamed Ben Arbia** | **mohamed.benarbia@epfl.ch** | | **Valentin Bonneaud** | **valentin.bonneaud@gmail.com** | | **Sébastien Chevalley** | **sebastien.chevalley@epfl.ch** | | **Theophile De Cazenove** | **theophile.decazenove@epfl.ch** | | **Matthieu Devaux** | **matthieu.devaux@epfl.ch** | | **John Ery** | **john.ery@epfl.ch** | | **Natalija Gucevska** | **natalija.gucevska@epfl.ch** | | **Zhivka Gucevska** | **zhivka.gucevska@epfl.ch** | | **Maxime Hulliger** | **maxime.hulliger@epfl.ch** | | **Marc Ilunga** | **marc.ilungatshibumbumukendi@epfl.ch** | | **Aimée Montero ** | **aimee.montero@epfl.ch** | | **Khalil Mrini** | **khalil.mrini@epfl.ch** | | **Florian Poma** | **florian.poma@epfl.ch** | | **Kevin Serrano **| **kevin.serrano@epfl.ch** | | **Robin Solignac** | **robin.solignac@epfl.ch** | | **Pius VonDäniken** | **pius.vondaeniken@epfl.ch** | \\ ---- **Language:** English **Coefficient/Crédits:** 6 \\ \\ [[http://isa.epfl.ch/imoniteur_ISAP/!itffichecours.htm?ww_i_matiere=47848061&ww_x_anneeAcad=2013-2014&ww_i_section=946228&ww_i_niveau=6683111&ww_c_langue=en|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. The bookstore has some copies pre-ordered. We highly recommend that you buy a copy or perhaps borrow a copy from a student who previously took this course. \\ ---- ==== 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. Indeed, we encourage you to collaborate. But, 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 **11/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 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. [[http://jahia-prod.epfl.ch/site/polylex/ethics|(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 until 2012. I would like to thank Prof. Lenstra for making these slides available. \\ ---- ==== Special Announcements ==== **A small write-up on partial fraction expansion as well as a link to some lecture notes from MIT on generating functions was added (see details below).** \\ Each graded homework is due by 10am on the due date written in the homework sheet. There will be a box in the lecture room and you need to return the homework by the end of the lecture (before exercise session starts). As concerns **graded homework 2**, the grading tasks were divided as follows: | Exercise 1: | Kevin Serrano | | Exercise 2: | Khalil Mrini | | Exercise 3: | Matthieu Devaux | | Exercise 4: | Florian Poma | | Exercise 5: | Valentin Bonneaud | | Exercise 6: | Zhivka Gucevska | | Adding points: | Robin Solignac | As concerns **graded homework 4**, the grading tasks were divided as follows: | Exercise 1: | Sebastien Chevalley | | Exercise 2: | Natalija Gucevska | | Exercise 3: | Alfonso Peterssen | | Exercise 4: | Kevin Serrano | | Exercise 5: | Valentin Bonneaud | | Exercise 6: | Zhivka Gucevska | | Adding points: | Robin Solignac | As concerns **graded homework 6**, the grading tasks were divided as follows: | Exercise 1: | Zhivka Gucevska | | Exercise 2: | Kevin Serrano| | Exercise 3: | Valentin Bonneaud | | Exercise 4: | Kevin Serrano | | Exercise 5: | Alfonso Peterssen | | Exercise 6: | Khalil Mrini | | Adding points: | Matthieu Devaux | As concerns **graded homework 11**, the grading tasks were divided as follows: | Exercise 1: | Zhivka Gucevska | | Exercise 2: | Khalil Mrini | | Exercise 3: | Zhivka Gucevska | | Exercise 4: | Valentin Bonneaud | | Exercise 5: | Alfonso Peterssen | | Exercise 6: | Matthieu Devaux | | Adding points: | Aimee Montero | If you have any questions, please refer to the corresponding assistant by sending him/her an email. \\ ===== Final Exam - Wednesday January 14, 2015 - Swiss Tech Center - from 14:00 till 17:00 ===== The final exam will take place in the Swiss Tech center. The "garden" entry door is located on the **ground floor** on the west side of the building. After walking under the tunnel (under the M1 tracks), go straight ahead and walk along the building on the left side. You can also climb steps in direction of Tekoe and walk along the building on the upperfloor, you will then step down to the ground floor again in front of the West-garden entry door. {{:en:courses:2014-2015:stcc_west_door.pdf|how to reach STCC west door?}} Doors will be open at 13:45 and the exam is starting at 14:00 sharp! Be on time and **make sure to leave all your stuff in the space located in front of your feet behind the student in front of you. Keep your pencil and your CAMIPRO card on your desk. ** The exam is written, closed book; you are not allowed to use a laptop, cellphone, smart-watch, digital assistant, calculator, or any other similar device. Click here to see the map and the list of the seating plan {{:en:courses:2014-2015:final_seats_ds_12jan15.pdf|Name list & seat number}} {{:en:courses:2014-2015:1240-stcc-map.pdf|STCC map}} L'examen final aura lieu au Swiss Tech Center le mercredi 14 janvier de 14:00 à 17:00. La porte d'entrée appelée "garden" est située à l'ouest du bâtiment à l'étage inférieur (rez). Après être passé sous les rails du M1, continuer tout droit et longer le bâtiment sur votre gauche (il y a déjà un chemin marqué dans le gazon par les gens qui ont pris un raccourci)au bout du bâtiment, tournez à droite et l'entrée est là. Vous pouvez aussi après le tunnel grimper les escaliers au niveau CAMPUS, longer le bâtiment sur la gauche et redescendre au niveau garden, vous vous retrouvez vers l'entrée. Les portes seront ouvertes à 13:45 et l'examen débute à 14:00, soyez ponctuel !! Déposez toutes vos affaires dans l'espace situé devant vous (derrière l'étudiant qui vous précède). Ne gardez que votre crayon et votre carte CAMIPRO sur votre bureau. L'examen se déroule à livres fermés, vous n'êtes pas autorisé d'utiliser un laptop, natel, smart-watch, assistant numérique, calculatrice ou d'autres moyens similaires. Cliquer sur les liens ci-dessus, pour obtenir votre numéro de siège et le plan de salle. ===== === **We will have a Q&A session for all of your last-minute questions in SG1 on Wednesday January 7th from 10-12am.** === ===== ==== Detailed Schedule ==== \\ ^ Date ^ Topic ^ Assignment ^ Due Date/Solutions Posted ^ Remarks ^ | 16/9 | rules and aim of the course, propositional logic | | | | | 19/9 | predicates and quantifiers |{{:en:courses:lthc:ds2014-hwk-01.pdf| Homework 1}} | {{:en:courses:lthc:ds2014-hsol-01.pdf| Solution 1}}| | 23/9 | inference and proof techniques| | |{{:en:courses:2014-2015:lenstra_chapter_1.pdf|Chapter 1 Notes}} | | 26/9 | sets, subset, power set, set identities |{{:en:courses:lthc:DS2014_hw2bis.pdf| Homework 2 (graded)}} | | {{:en:courses:2014-2015:ds2014_sol2.pdf|Solution 2}}| | | 30/9| inclusion and exclusion principle, functions | | | | | 03/10| injectivity, surjectivity, bijectivity, when do two sets have equal cardinality? | {{:en:courses:lthc:ds2014-hwk-03.pdf| Homework 3}}| | {{:en:courses:2014-2015:ds2014-hsol-03.pdf|Solution 3}}| | 07/10| countability of rationals, reals are uncountable, some special functions, sequences, arithmetic and geometric progression | | |{{:en:courses:2014-2015:lenstra_chapter_2.pdf|Chapter 2 Notes}} | | 10/10| when is one set bigger than another, pigeonhole principle, algorithms | {{:en:courses:2014-2015:ds2014_hw4.pdf|Homework 4 (graded)}} | {{:en:courses:2014-2015:ds2014_sol4_v2.pdf|Solution 4}}| | | 14/10| big O, Omega, Theta, little o| | | | | 17/10| more on big O etc, how to bound sums by integrals, modular arithmetic -- basic facts | {{:en:courses:2014-2015:ds2014-hwk-05.pdf|Homework 5}}|{{:en:courses:2014-2015:ds2014-hsol-05.pdf|Solution 5}} | | | 21/10| more on modular arithmetic, applications, Horner's rule, how to exponentiate quickly, primes | | | | | 24/10| prime number distribution, how to generate large random prime numbers, Fermat's little theorem, multiplicity inverse of a number modulo a prime | {{:en:courses:2014-2015:ds2014-hwk-06.pdf|Homework 6 (graded)}}| {{:en:courses:2014-2015:ds2014-sol-06.pdf|Solution 6}}| {{:en:courses:2014-2015:lenstra_chapter_3.pdf|Chapter 3 Notes}}| | 28/10| Euclidean algorithm and the extended Euclidean algorithm, proof of Euclid's Lemma, multiplicative inverse modulo m revisited | | | | | 31/10| {{:en:courses:courge.jpg|}} induction | {{:en:courses:2014-2015:ds2014-hwk-07_v2.pdf|Homework 7}}|{{:en:courses:2014-2015:ds2014-hsol-07.pdf|Solution 7}} | We have clarified the text of Problem 4 | | 04/11| recursions | | | {{:en:courses:2014-2015:lenstra_chapter_5.pdf|Chapter 5 Notes}}| | 07/11| mock midterm and review | {{:en:courses:2014-2015:ds2014-hwk-08.pdf|Special Homework 8}}|{{:en:courses:2014-2015:ds2014-hsol-08.pdf|Solution 8}} | the median for this midterm was 64 points, i.e., half the people had more and half had less than 64 points| | 11/11| **Midterm** | {{:en:courses:2014-2015:awithsols.pdf| Midterm (Text + Solutions)}} | | {{:en:courses:2014-2015:histo_midterm.pdf|histogram.pdf}} {{:en:courses:2014-2015:hist-all-ver.pdf|detailedhistogram.pdf}}| | 14/11| basic counting: sum and product rule |{{:en:courses:2014-2015:ds2014-hwk-09.pdf| Homework 9}} |{{:en:courses:2014-2015:ds2014-hsol-09.pdf|Solution 9}} | {{:en:courses:2014-2015:lenstra_chapter_6.pdf|Chapter 6 Notes}}| | 18/11| combinations, permutations, combinatorial versus algebraic proofs, pascal's identity, binomial theorem, vandermonde identity | | | | | 21/11| cards, generating functions approach to solving the Fibonacci sequence | {{:en:courses:2014-2015:ds2014-hwk-10.pdf|Homework 10}}|{{:en:courses:2014-2015:ds2014-hsol-10.pdf|Solution 10}} | | | 25/11| formal power sums | | | | | 28/11| partial fractions |{{:en:courses:2014-2015:ds2014-hwk-11.pdf|Homework 11 (graded)}} |{{:en:courses:2014-2015:ds2014-hsol-11.pdf|Solution 11}} || | | 02/12| advanced usage of generating functions | | |{{:en:courses:2014-2015:lenstra_chapter_8.pdf| Chapter 8 Notes}} {{:en:courses:2014-2015:partial_fractions.pdf|Partial Fraction Expansion.pdf}} - [[http://courses.csail.mit.edu/6.042/fall05/ln11.pdf|Lecture Notes from MIT on generating functions]] | | 05/12| basic probability; motivating examples; sample space, outcomes, events, distribution function, axioms of probability |{{:en:courses:2014-2015:ds2014-hwk-12.pdf| Homework 12}} | {{:en:courses:2014-2015:ds2014-hsol-12.pdf|Solution 12}}| {{:en:courses:2014-2015:lenstra_chapter_7.pdf|Chapter 7 Notes}}| | 9/12| conditional probability, bayes, independence | | | | | 12/12| notion of random variable, distribution of random variable, expected value, linearity of expectation, Binomial distribution, | {{:en:courses:2014-2015:ds2014-hwk-13.pdf|Homework 13}}|{{:en:courses:2014-2015:ds2014-hsol-13bis.pdf|Solution 13}} || | 16/12| Markov inequality, second moment, variance, Cheyshev inequality, birthday paradox | | | | | 19/12| mock final exam | {{:en:courses:2014-2015:ds2014-hwk-14_withsol.pdf| Special Homework 14 (Text + Solutions)}} | | |07/01|Q & A| in SG1 from 10:00 am till 12:00 noon| | 14/01| **Final Exam 14:00 -- 17:00**|{{:en:courses:2014-2015:a.pdf|Final (Text + Solutions}} | |