School of Engineering \ Computer Engineering
Course Credit
ECTS Credit
Course Type
Instructional Language
Programs that can take the course
Computer Engineering
Artificial Intelligence Engineering
This course aims to introduce the students with mathematical foundations of computer science. It provides a philosophical and technical introduction to deductive reasoning via formal proving techniques to propositional and predicate logic sequents. Students are trained in recursive thinking, solving exact recurrences and evaluating sums. A brief introduction to theory of computation and algorithm analysis is provided.
Textbook and / or References
Logic in Computer Science Modelling and Reasoning About Systems. By Michael R A Huth and Mark D Ryan. Cambridge University Press.
Concrete Mathematics a Foundation for Computer Science. By Graham, Knuth and Patashnik. Addison-Wesley Publishing Company.
Introduction to Algorithms. Third Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. McGraw-Hill.
Formal reasoning in propositional and predicate logic
Recursive thinking and being able to make mathematical induction proofs
Learning a variety of recurrence solving and summation evaluation techniques
Designing easy algorithms, being able to make time and space complexity analysis and correctness proofs
1. Proving propositional logic sequents by using natural deduction rules
2. Proving predicate logic sequents by using natural deduction rules
3. Formulating and solving recurrence relations
4. Formulating and solving summations
5. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms
6. Solve problems that involve sorting and searching
Week 1: Propositional logic
Week 2: Propositional logic
Week 3: Propositional logic
Week 4: Predicate logic
Week 5: Predicate logic
Week 6: Introduction to algorithms and time complexity analysis
Week 7: Asymptotic analysis, solving asymptotic recurrence relations
Week 8: Sorting and searching, heap algorithms
Week 9: Discrete mathematics: Solving recurrences
Week 10: Solving recurrences
Week 11: Solving summations
Week 12: Solving summations
Tentative Assesment Methods
Midterm 40%
Final 40%
Quiz 10%
Homework 10%
|
Program Outcome
*
|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Course Outcome
|
|---|
| 1 |
A, C
|
|
|
|
|
C
|
|
|
|
|
|
| 2 |
A, C
|
|
|
|
|
C
|
|
|
|
|
|
| 3 |
A, C, D
|
|
|
|
|
C
|
|
|
|
|
|
| 4 |
A, C
|
|
|
|
|
C
|
|
|
|
|
|
| 5 |
C
|
|
|
|
|
C
|
|
|
|
|
|
| 6 |
C
|
|
|
|
|
C
|
|
|
|
|
|