BBM 205 - Introduction to Discrete Mathematics (Fall 2024)

Lectures: Monday 9am-12:40pm

---

Instructor:

Burkay Genç bgenc[at]cs.hacettepe.edu.tr Room 122

Gülden Olgun guldenolgun[at]cs.hacettepe.edu.tr Room 102

Lale Özkahya ozkahya[at]cs.hacettepe.edu.tr Room 218

---

Communication:

Piazza: It is mandatory that you enroll to the course on Piazza by following the link here, since all course-related communications will be carried out through Piazza.
Office hour: There will not be any prescheduled office hours, but feel free to set an an appointment by emailing the instructors for any questions for course-related questions or issues.

---

Grading

Midterm exams	60%
Final exam	40%

Reference Books

• Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition, Ralph P. Grimaldi.
• Discrete Mathematics and Its Applications, 7th Edition, Kenneth H. Rosen.
• Mathematics for Computer Science, Eric Lehman, Tom Leighton, and Albert Meyer 2018 (available online)
• A Course in Discrete Structures, Rafael Pass and Wei-Lung Dustin Tseng (available online)
• Building Blocks for Theoretical Computer Science, Margaret M. Fleck (available online)

More Resources for Interested Readers

• Foundations of Computer Science, Al Aho and Jeff Ullman (available online)
• Lists, Decisions and Graphs is a Google Book, Creative Commons License CC0 (available online)

Similar Courses

• MIT Open Courseware: Mathematics for Computer Science
• CS70 at EECS, Berkeley Uni.
• 21-127, Carnegie Mellon Uni.
• CPS102 at CS, Duke Uni.
• Discrete Mathematics and Mathematical Reasoning, Informatics, Uni. of Edinburgh
• Ma/CS 6a at CS, Cal.Tech.

Sample Exams and Questions

Below are some exams from previous years.
Besides the solutions, unanswered exams are provided as well, so that you can test yourself on these samples before reading their solutions.
Fall 2023: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam (Soln).
Fall 2022: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam (Soln).
Fall 2021: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam (Soln).
Fall 2020: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam, (Soln).
Fall 2019: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam, (Soln).
Fall 2018: Midterm 1 (Soln), Final Exam, (Soln).
Fall 2017: Midterm 1 (Soln), Midterm 2 (Soln), Final Exam (Soln),
Fall 2016: Midterm 1 (Soln), , Midterm 2 (Soln), Final Exam (Soln),
Spring 2015: Midterm 1 (Soln), , Midterm 2 (Soln), Midterm 3 (Soln), Final Exam (Soln), Butunleme (Soln).
Fall 2015: Midterm (Soln), Final (Soln). Butunleme (Soln).

Schedule (Tentative)

Week	Topic and Slides	Reading (Lehman, Leighton and Meyer (LLM), and Rosen)
1	Propositional Logic [slides: 1, 2 ]	Logic Sheet, Chapter 3 (LLM), Chapter 1.1-1.3 (Rosen) Reading for fun
2	Predicate Logic [Slides]	Chapter 1.4 - 1.5 (Rosen)
3	Rules of Inference [Slides]	Chapter 1.6 (Rosen)
4	Proofs [ Slides]	Chapter 1.7-1.8 (Rosen), Chapter 1 (LLM) Top ten proof techniques not allowed in BBM205 (from LL)
5	Basic structures: Sets, Relations, Functions [slides: 1, 2]	Chapter 2.1-2.4 (Rosen)
6	Sequences, Sums, Cardinality of Sets [slides: 1, 2]	Chapter 9.1, 9.5 (Rosen)
7	Midterm Exam I
8	Induction and Recursion [ Slides]	Chapter 5.1-5.2 (Rosen), Chapter 5 (LLM) Chapter 8.1-8.2 (Rosen), Chapter 22.1 (LLM) Reading for fun
9	Graph Terminology, Special Graphs, Graph Isomorphism [Slides: 1, 2]	Chapter 10.1-10.3 (Rosen), Chapter 12 (LLM) Reading for fun
10	Basics of Counting, Pigeonhole principle [Slides: 1, 2]	Chapter 6.1-6.2 (Rosen), Chapter 15.5-8 (LLM)
11	Combinations, Permutations, Binomial Coefficients [Slides: 1, 2, 3, 4]	Chapter 6.3-6.5 (Rosen), Chapter 15.5-8 (LLM)
12	Midterm Exam II
13	Introduction to Discrete Probability, Conditional Probability [Slides:1, 2, 3]	Chapter 7.1-7.3 (Rosen), Chapter 17, 18 (LLM) An alternative summary
14	Random Variables and Expectation [slides 1, 2, 3]	Chapter 7.4 (Rosen), Chapter 19 (LLM) Two nice applications of discrete probability

---

© 2024 Hacettepe University