 français
 English
Coursebooks 20172018
Advanced information, computation, communication I
CS101
Lecturer(s) :
Lenstra ArjenLanguage:
English
Remarque
This course focuses on the foundational, discrete mathematics core of advanced computation.Summary
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.Content
I. Mathematical reasoning: propositional logic, propositional functions, quantifiers, rules of inference; this includes very basic logic circuits.
II. Sets and counting: cardinalities, inclusion/exclusion principle, sequences and summations.
III. Algorithms and complexity: basic algorithms, computational complexity, bigO notation and variants, countability.
IV. Number representations such as binary and hexadecimal and (postponed to 2nd semester) basic number theory: modular arithmetic, integer division, prime numbers, hash functions, pseudorandom number generation; applications.
V. Induction and recursion: mathematical induction, recursive definitions and algorithms.
VI. Basic combinatorial analysis: permutations, binomial theorem, basic generating functions.
VII. Basic probability: events, independence, random variables, Bayes' theorem.
VIII. Structure of sets: relations, equivalence relations, power set.
IX. (time permitting) Elementary graph theory: graphs, Euler and Hamilton paths, Dijkstra's algorithm, spanning trees.
Keywords
Propositional logic, counting, complexity, bigO, number representations, sets, matrices, modular arithmetic, induction, basic probabilities, Bayes theorem, combinatorial analysis, recurrences, generating functions, countability, graph theory.
Learning Outcomes
By the end of the course, the student must be able to: Recognize if there is a mistake in a (simple) proof
 Apply general problemsolving techniques
 Recognize the mathematical structures present in applications
 Apply simple recursion and use it to design recursive algorithms
 Apply the tools studied in class to solve problems
 Demonstrate familiarity with mathematical reasoning
 Solve linear recurrences and use generating functions
 Argue about (un)countability
 Formulate complete, clear mathematical proofs
Transversal skills
 Assess one's own level of skill acquisition, and plan their ongoing learning goals.
 Continue to work through difficulties or initial failure to find optimal solutions.
 Demonstrate the capacity for critical thinking
Teaching methods
Ex cathedra (blackboard) lectures
Expected student activities
Studying the book, test your understanding by making the exercises, ask questions
Assessment methods
Midterm exam (30%) and final exam (70%), both mostly (and possibly exclusively) multiple choice
Supervision
Office hours  No 
Assistants  Yes 
Forum  No 
Others 
A list of students assistants and their contact data will be made available on the moodle page for this course, along with an assignment of each registered student to one of the student assistants. If you have a question, first contact the student assistant assigned to you. If that does not help, contact one of the teaching assistants (Marguerite Delcourt, Dusan Kostic and Benjamin Wesolowski). Furthermore, you are always welcome to stop by at my office (INJ330, no office hours, I'm available when I'm there) for any type of question related to this course or your study at EPFL. Never hesitate to ask questions before, during or after the lectures!

Resources
Bibliography
"Discrete Mathematics and Its Applications", Kenneth H. Rosen, 7th ed, McGrawHill 2012. (You should be able to find the pdf on the web.)
Ressources en bibliothèque
Websites
Moodle Link
In the programs
 SemesterFall
 Exam formWritten
 Coefficient
7  Subject examined
Advanced information, computation, communication I  Lecture
4 Hour(s) per week x 14 weeks  Exercises
2 Hour(s) per week x 14 weeks
 Semester
 SemesterFall
 Exam formWritten
 Coefficient
7  Subject examined
Advanced information, computation, communication I  Lecture
4 Hour(s) per week x 14 weeks  Exercises
2 Hour(s) per week x 14 weeks
 Semester
 SemesterFall
 Exam formWritten
 Coefficient
7  Subject examined
Advanced information, computation, communication I  Lecture
4 Hour(s) per week x 14 weeks  Exercises
2 Hour(s) per week x 14 weeks
 Semester
Reference week
Mo  Tu  We  Th  Fr  

89  
910  
1011  
1112  
1213  
1314  
1415  
1516  
1617  
1718  
1819  
1920  
2021  
2122 
legend
 Autumn semester
 Winter sessions
 Spring semester
 Summer sessions
 Lecture in French
 Lecture in English
 Lecture in German