Computer Science
Tel-Aviv University

0368.1118.10
Discrete Mathematics

Fall 2005


Announcements


Homeworks and Solutions


Exams


Some Information

Lectures

Sunday 12:00-14:00, Shenkar 9
Monday 17:00-19:00, Dach 5
Instructor

Oded Regev | Schreiber 220 | 5379 | Office hours: Monday 19:00-20:00 or by appointment
Tutorials

Wednesday 13:00-15:00 Orenstein 102 (Tamir)
Wednesday 15:00-17:00 Dan David 106 (Tamir)
Thursday 15:00-17:00 Schreiber 8 (Itai)
Thursday 16:00-18:00 Dan David 202 (Dan)
Teaching Assistants

Itai Leshem
Tamir Tuller
Dan Hefez
Textbooks

Introduction to Discrete Math, A. Avron (available from Sifrut Zola and online),
Discrete Mathematics, S. Dar and S. Gueron (out of print),
Discrete Mathematics, N. Linial and M. Parnas,
Discrete Math for Computer Science Students, Bogart, Drysdale, and Stein, entire book from a Discrete Math course given in Dartmouth College.
Lecture notes by László Lovász and Kati Vesztergombi
Other Resources Videos of lectures by Prof. Tarsi
Doron Chen's homepage with exams and excercises
Previous exams (exams are free)
Work
One homework per class, due at the start of next class.
Links
Last year's course
And the one before that
Fibonacci numbers in nature
Encyclopedia of integer sequences
(try typing 1,1,2,3,5,8,13,21)
A great collection of puzzles
(some require things we learned; others are unrelated but still fun)

Schedule

Date Class Topic Some Links
Oct 30 הצרנה, פסוק, קשרים, שקילויות לוגיות, איך מוכיחים On De Morgan and other mathematicians.
Oct 31 קבוצת קשרים שלמה, כמתים, שקילויות לוגיות עם כמתים, שלילת פסוקים On some mathematical symbols
Nov 6 סימון יוטה, סימון קיים יחיד, על שימוש במשתנים, כלל אלפא, קבוצות,שייכות בקבוצות
Nov 7 הכלה בין בקבוצות, פרדוקס ראסל, פעולות על קבוצות Berry's paradox
Nov 13 תכונות בסיסיות של הפעולות
Nov 14 קבוצת החזקה, זוגות סדורים ומכפלה קרטזית, פונקציות, תחום, טווח Power set axiom and others
Nov 20 תמונה, סימון למדא
Nov 21 פונקציה כקבוצה,סימון יוטה, צמצום פונקציה, הרכבת פונקציות, חד חד ערכיות, על How to prove a function is one-to-one and onto
Nov 27 פונקציה הפיכה והפונקציה ההופכית
Nov 28 פונקציית קארי
Dec 4 יחסים, תכונות של יחסים
Dec 5 יחס סדר, יחס סדר מלא, יחס שקילות, מחלקות שקילות, קבוצת מנה Hasse diagrams
Dec 11 על חלוקות ויחסי שקילות, עוצמות Cardinal numbers
Dec 12 סופיות, אינסופיות, שיטת האלכסון Hilbert's Hotel
Dec 18 איפיון קבוצות אינסופיות, סדר על עוצמות
Dec 19 משפט קנטור ברנשטיין ועקרון הסנדוויץ, משפט קנטור, פעולות על עוצמות Continuum hypothesis
Dec 25 חוקי הפעולות ושימושים
Dec 26 קומבינטוריקה, בחירת אברים Lecture notes by Rudich (look under Counting I/II/III)
Jan 1 חנוכה
Jan 2 מקדמים בינומיים, מספרי קטלן
Jan 8 עקרון שובך היונים Two examples
Jan 9 עקרון ההכלה וההדחה
Jan 15 תמורות ללא נקודת שבת, נוסחאות נסיגה Derangements, Fibonacci
Jan 16 פתרון נוסחאות נסיגה הומוגניות ולא הומוגניות Solving recurrence relations
Jan 22 פונקציות יוצרות, פתרון נוסחאות נסיגה בעזרתן
Jan 23 תורת הגרפים, מסלולים וטיולים, קשירות Graphs of the Internet and of protein interactions
Jan 29 עצים ויערות, קצת על הלמה של שפרנר Sperner's lemma
Jan 30 נוסחת קיילי