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 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
|