Discrete Mathematics
opinarer@gsu.edu.tr
Content
Objective
The aim of this course is to provide students with the fundamental concepts of discrete mathematics that form the basis of computer science and computer engineering, and to develop their logical reasoning, mathematical modeling, problem-solving, and proof-writing skills. Students will learn to relate concepts such as sets, relations, combinatorics, number theory, graph theory, algebraic structures, algorithms, and computability to problems in computer science.
Course Content
Propositional logic and truth tables; predicates, quantifiers, and proof techniques; set theory and power sets; partially ordered sets; relations, closures, and equivalence relations; number theory, modular arithmetic, and cryptography; combinatorics and counting principles; inclusion-exclusion and generating functions; recurrence relations and algorithm analysis; fundamental concepts of graph theory and graph isomorphism; trees, traversals, and Huffman coding; graph algorithms, paths, and spanning trees; algebraic structures for computer science; finite-state automata and computability theory.
Course Learning Outcomes
Upon successful completion of the course, students will be able to:
1. Analyze logical propositions and construct truth tables.
2. Formulate mathematical statements using predicates and quantifiers.
3. Apply fundamental proof techniques, including direct proof, proof by contradiction, contrapositive proof, and mathematical induction.
4. Define and analyze sets, relations, and equivalence relations.
5. Describe and analyze partially ordered sets and their fundamental properties.
6. Apply concepts from number theory and modular arithmetic to problems in computer science and cryptography.
7. Apply fundamental counting techniques and the inclusion-exclusion principle to combinatorial problems.
8. Solve recurrence relations and perform basic complexity analyses of algorithms.
9. Model problems using graphs and trees and apply fundamental graph traversal techniques.
10. Explain and apply concepts and algorithms related to paths, spanning trees, and Huffman coding.
11. Describe fundamental algebraic structures used in computer science and analyze their properties.
12. Explain the basic principles of finite-state automata and the concept of computability.
13. Apply discrete mathematics concepts to the modeling, analysis, and solution of computer engineering problems.
Teaching and Learning Methods
* Lectures and interactive classroom sessions
* Conceptual explanations using board work and/or digital presentations
* Mathematical problem-solving
* Proofs and worked examples
* Question-and-answer sessions and classroom discussions
* Examples from computer science and computer engineering
* Practical exercises involving algorithms and graph problems
* Individual problem-solving and homework assignments
References
Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
Weekly Contents
| Week | Weekly Contents |
|---|---|
| 1 | Propositional Logic and Truth Tables |
| 2 | Predicates, Quantifiers, and Proof Techniques |
| 3 | Set Theory, Power Sets, and Partially Ordered Sets |
| 4 | Relations, Closures, and Equivalence Relations |
| 5 | Number Theory, Modular Arithmetic, and Cryptography |
| 6 | Combinatorics I: Fundamental Principles and Counting |
| 7 | Combinatorics II: Inclusion-Exclusion and Generating Functions |
| 8 | Mid term exam |
| 9 | Recurrence Relations and Algorithm Analysis |
| 10 | Graph Theory I: Fundamental Concepts and Isomorphism |
| 11 | Trees, Graph Traversals, and Huffman Coding |
| 12 | Graph Algorithms: Paths and Spanning Trees |
| 13 | Algebraic Structures for Computer Science |
| 14 | Finite-State Automata and Computability Theory |
Assessment System
| Activities | Number | Contribution |
|---|---|---|
| Contribution of in-term studies to overall grade | 1 | 50 |
| Contribution of final exam to overall grade | 1 | 50 |
| Total | 2 | 100 |
| Activities | Number | Contribution |
|---|---|---|
| Assignments | 0 | 0 |
| Presentation | 0 | 0 |
| Midterm Examinations (including preparation) | 1 | 50 |
| Project | 0 | 0 |
| Laboratory | 0 | 0 |
| Other Applications | 0 | 0 |
| Quiz | 0 | 0 |
| Term Paper/ Project | 0 | 0 |
| Portfolio Study | 0 | 0 |
| Reports | 0 | 0 |
| Learning Diary | 0 | 0 |
| Thesis/ Project | 0 | 0 |
| Seminar | 0 | 0 |
| Other | 0 | 0 |
| Make-up | 0 | 0 |
| Total | 1 | 50 |
Relation of Proficiency
| No | Program Learning Outcomes | Contribution | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | Matematik, fizik ve mühendislik bilimlerine özgü konularda yeterli bilgi birikimi; bu alanlardaki kuramsal ve uygulamalı bilgileri, mühendislik problemlerinin modellenmesi ve çözümünde kullanabilme becerisi. | X | ||||
| 2 | Karmaşık bilgisayar mühendisliği problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analiz ve modelleme yöntemlerini seçme ve uygulama becerisi. | X | ||||
| 3 | Yazılımsal veya donanımsal karmaşık bir sistemi, süreci veya donanımı gerçekçi kısıtlar ve koşullar altında, belirli gereksinimleri karşılayacak şekilde tasarlama becerisi; bu amaçla modern tasarım yöntemlerini uygulama becerisi. | |||||
| 4 | Mühendislik uygulamalarında karşılaşılan karmaşık problemlerin analizi ve çözümü için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin bir şekilde kullanma becerisi. | X | ||||
| 5 | Analitik düşünce ile bir sistemi, sistem bileşenini ya da süreci analiz etme, modelleme, deney tasarlama ve yapma, veri toplama, çözüm algoritmaları üretebilme, uygulamaya alma ve geliştirme becerileri. | X | ||||
| 6 | Disiplin içi ve çok disiplinli takımlarda etkin biçimde çalışabilme becerisi; bireysel çalışma becerisi. | |||||
| 7 | Türkçe sözlü ve yazılı etkin iletişim kurma becerisi; en az iki yabancı dil bilgisi; etkin rapor yazma ve yazılı raporları anlama, yazılım ve donanım tasarımını, gerekirse teknik resim metotları kullanarak raporlayabilme, etkin sunum yapabilme becerisi. | X | ||||
| 8 | Bilgiye erişebilme ve bu amaçla kaynak araştırması yapabilme, veri tabanları ve diğer bilgi kaynaklarını kullanabilme becerisi | |||||
| 9 | Yaşam boyu öğrenmenin gerekliliği bilinci; kendini sürekli yenileme becerisi. | |||||
| 10 | Mesleki etik ilkelerine uygun davranma, mesleki sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi. | X | ||||
| 11 | Proje yönetimi, risk yönetimi ve değişiklik yönetimi gibi, iş hayatındaki uygulamalar hakkında bilgi; girişimcilik, yenilikçilik hakkında farkındalık; sürdürülebilir kalkınma hakkında bilgi. | |||||
| 12 | Mühendislik uygulamalarının evrensel ve toplumsal boyutlarda sağlık, çevre ve güvenlik üzerindeki etkileri ve çağın mühendislik alanına yansıyan sorunları hakkında bilgi. | |||||
| 13 | Bilgisayar mühendisliği uygulamalarının hukuki ve etik boyutları konusunda farkındalık. | |||||
ECTS
| Activities | Number | Period | Total Workload |
|---|---|---|---|
| Class Hours | 14 | 3 | 42 |
| Working Hours out of Class | 14 | 2 | 28 |
| Midterm Examinations (including preparation) | 1 | 10 | 10 |
| Final Examinations (including preparation) | 1 | 17 | 17 |
| Total Workload | 97 | ||
| Total Workload / 25 | 3.88 | ||
| Credits ECTS | 4 | ||