The Hebrew University Logo
Syllabus DISCRETE MATHEMATICS - 80181
עברית
Print
 
PDF version
Last update 29-10-2019
HU Credits: 5

Degree/Cycle: 1st degree (Bachelor)

Responsible Department: Mathematics

Semester: 1st and/or 2nd Semester

Teaching Languages: Hebrew

Campus: E. Safra

Course/Module Coordinator: Dr. A Gurevich

Coordinator Email: gurevich@math.huji.ac.il

Coordinator Office Hours: Tue, 13-14

Teaching Staff:
Dr. Orit Raz
Dr. Boris Begun
Mr.
Mr. Moshe White
Ms. Zilberman Chaya
Ms. Noy Sofer
Dr. Alex Gourevich
Mr. Uri Brezner
Mr. Michael Simkin

Course/Module description:

1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, functions
3. Relations - equivalence and order relations, partially ordered sets
4. Counting problems – counting with and without order importance, set partitions
5. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
6. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
7. Reflection method - Catalan numbers
8. Pigeonhole principle – Erdos-Szekeres theorem
9. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers, solving recurrence relations
10. Limiting behavior – big O and Theta notations, estimation of growth rates
11. Graphs – paths, connectivity, cycles, trees, bipartite graphs, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, the marriage theorem, colored graphs, Ramsey theory


Course/Module aims:
Providing basic notions of Discrete Math and developing the ability to solve problems.

Learning outcomes - On successful completion of this module, students should be able to:
solve elementary problems in set theory, combinatorics, and graph theory.

Attendance requirements(%):
none

Teaching arrangement and method of instruction: Lecture + exercise

Course/Module Content:

1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, functions
3. Relations - equivalence and order relations, partially ordered sets
4. Counting problems – counting with and without order importance, set partitions
5. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
6. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
7. Reflection method - Catalan numbers
8. Pigeonhole principle – Erdos-Szekeres theorem
9. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers, solving recurrence relations
10. Limiting behavior – big O and Theta notations, estimation of growth rates
11. Graphs – paths, connectivity, cycles, trees, bipartite graphs, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, the marriage theorem, colored graphs, Ramsey theory


Required Reading:
none

Additional Reading Material:
Nati Liniel, Michal Parnas,
Discrete Mathematics (Hebrew)

Course/Module evaluation:
End of year written/oral examination 90 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 10 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %

Additional information:
none
 
Students needing academic accommodations based on a disability should contact the Center for Diagnosis and Support of Students with Learning Disabilities, or the Office for Students with Disabilities, as early as possible, to discuss and coordinate accommodations, based on relevant documentation.
For further information, please visit the site of the Dean of Students Office.
Print