ITB8832 -- Mathematics for Computer Science
Autumn semester 2024
Index
Acquiring competence in areas of mathematics that are especially
relevant to computer science and have applications in various
fields, from programming to analysis of algorithms to network
design.
At the end of the course, the successful student:
-
Applies the principles and techniques of rigorous reasoning.
-
Employs recursive data structures and algorithms to problem
solving, game theory, and software testing.
-
Recognizes the intrinsic limitations of computers’
capabilities.
-
Employs notions and methods from the mathematical foundations
of modern cryptography.
-
Applies the concepts and techniques of graph theory to
scheduling and resource management.
Autumn semester 2023, 16 weeks, 2 days per week, 2 hours per
day.
-
Lectures: Mondays from 10:00 to 11:30 in Room ICO-219
(IT College).
-
Exercises: Wednesdays from 12:00 to 13:30 in Room
U06A-204.
The course "Mathematics for Computer Science" follows
the lines of the course of the same name taught at Massachusetts
Institute of Technology. It is aimed at Master students of the
School of Information Technology.
The course covers a series of topics from logic, set theory,
discrete mathematics, and theory of computation, chosen from the
first half of the textbook. Among these:
-
Proofs. The axiomatic method. Proofs by cases. Proofs by
contradiction. Well ordering principle. Propositional logic
in computer programs. Propositional algebra. Induction.
Application: satisfiability.
-
Mathematical data types. Sets and sequences. Functions and
finitary relations. Recursive data types. Recursive
functions. Application: games as a recursive data type.
-
State machines. Invariants. The stable marriage problem.
The halting problem. Application: program verification.
-
Number theory. Divisibility. Prime numbers. Modular
arithmetic. Application: the RSA public key encryption
algorithm.
-
Directed and undirected graphs. Partial orders.
Connectivity. Planar graphs. Application: scheduling.
The language of the course is English.
The course gives 6 ECTS credits.
Students who have the course in their study plan must declare it
in ÕIS (Õppeinfosüsteem, Student Information
System) by the deadlines set in the academic calendar.
Calculus, algebra, and programming at the level of the first
year of a BSc in Computer Science. Basic combinatorics and
probability are a useful addition.
Some introductory textbooks are:
-
Richard Hamming. Methods of Mathematics Applied to
Calculus, Probability, and Statistics. Dover, 2004.
A good introductory text to most undergraduate mathematics.
-
Ivan Niven. Mathematics of Choice. Mathematical
Association of America, 1965.
A nice introduction to combinatorics, although the notation
may appear surpassed nowadays.
-
Raymond M. Smullyan. A Beginner’s Guide to Mathematical
Logic. Dover, 2014.
An accessible academic textbook by a famous inventor of
logical puzzles.
-
Brian S. Thomson, Judith B. Bruckner and Andrew
M. Bruckner. Elementary Real Analysis. Second Edition,
2008.
A very good compendium, available from
THIS LINK.
Unfortunately, it follows the habit of Calculus manuals to
call "natural numbers" the positive, instead
of nonnegative, integers.
-
Mati Abel and &Uumkl;lo
Kääsik. Matemaatikasõnaraamat. TEA 2002.
A dictionary of mathematical terminology, with words in
English, Estonian, Finnish, and Russian. Unfortunately out of
print.
Each week will include:
- Two hours of classroom lectures.
- Two hours of classroom exercises.
At the end of each week, a self-evaluation test will be uploaded
on Moodle. These tests are not graded and are meant to let the
students estimate their understanding of the discussed topics.
For each classroom hour the students must take into account at
least one and a half hour of personal study. Ideally, the
students will, in this order:
-
Attend the lecture on Monday.
-
Study from the textbook the topics discussed in the lecture.
-
Attempt the exercises related to those topics.
-
Participate in the exercise session on Wednesday.
-
Review the topics and the exercises before the next week's
lectures.
-
Take the self-evaluation test.
The students are warmly encouraged to take handwritten notes
during the lectures and the exercise sessions.
Lecture slides and solutions to exercises will be uploaded on
the course web page by noon of the following day.
The first editions of the course had classroom assignments,
where only handwritten notes were allowed.
However, there was no restriction on the contents of said notes:
they could, for example, include solutions of exercises.
The policy was then that, if one of the test exercises had
already been solved (for example, at home) then the student was
allowed to copy their solution from the notes to the test paper.
However, copying the solution to a wrong exercise gave zero
points for the task.
Textbook:
The continuous assessment consists of two parts:
-
Three midterm tests, which will take place on the fifth,
ninth, and thirteenth week of the course, and determine
access to the final exam.
-
Non-mandatory group work, which gives extra credit.
Each midterm test is worth 15 points. As the final exam is
worth 60 points, an outstanding performance at the midterms
gives a little extra credit for the final score.
To be admitted to the final exam, a student must have obtained a
minimum of 21 points during the midterm tests, with a minimum of
6 points for each test.
The group work is entirely voluntary, and worth up to 10 points
of extra credit.
-
The students will solve exercises including, but not limited
to, problem solving and multiple choice questions.
-
The test is given online. It will remain available for a
limited time; a single attempt is allowed, which ends a fixed
time after its start.
-
Students caught cheating at a test will receive 0 points for
the test, be deferred to the disciplinary department, and get
a 10 points penalty on their score for the final exam.
-
The students will present their solution of a more complex
problem than those discussed in the midterm tests.
-
Groups can consist of a number of members variable from 1 to
4. The contribution of each member must be acknowledged and
listed in the returned assignment.
-
The work can be started between the tenth and the fourteenth
week of the course. The subject can be chosen between those
discussed from the sixth week of the course until the one when
the work starts. For example, a group starting on the twelfth
week can discuss topics from chapter 6, 7, 8, 9, and 10.
-
The deadline for submission is after fourteen days from the
assignment of the problem.
-
Students caught cheating at the group work will receive 0
points for the test, be deferred to the disciplinary
department, and get a 10 points penalty on their score for the
final exam.
The final exam will take place at the end of the semester and
count for up to 60 points of the final score. Three dates will
be arranged. Tentatively:
-
The last day of the course.
-
The first Wednesday after New Year.
-
The last Monday of the autumn semester at TalTech.
To be admitted to the final exam, a student must have obtained
at least 7 points at each one of the three tests.
Students are allowed one retake. In this case, the last returned
assignment will determine the final grade.
Taking the final exam is required for the final grade. Students
who obtain 51 or more points from the midterm tests and the
group work but don’t take the final exam, will receive a
"no show" grade. See also the section "Final
grade".
-
The students will solve exercises including, but not limited
to, problem solving and multiple choice questions.
-
The exam is given online. It will remain available for a
limited time; a single attempt per session is allowed, which
ends a fixed time after its start.
-
The students can retake the exam once; in this case, the final
grade is determined by the last assignment returned.
-
Students caught cheating at the final exam will receive a
final grade of 0 for the course and will be deferred to the
disciplinary department.
From 5 (maximum) down to 0 (minimum).
The total score from the midterm tests, final exam, and
voluntary group work is converted into the final grade according
to the following conversion table:
| Grade |
Judgement |
Score |
Interpretation |
| 5 |
Excellent |
91% or more |
The student commands the subject. |
| 4 |
Very good |
81%-90% |
The student has a good grasp on the subject, with some small
mistakes or imprecisions.
|
| 3 |
Good |
71%-80% |
The student understands most of the subject, but there are
some evident major issues.
|
| 2 |
Satisfactory |
61%-70% |
The student manages the bulk of the subject, but also shows
serious lacks or misunderstandings.
|
| 1 |
Poor |
51%-60% |
The student achieved the bare minimum. Maybe the approach to
the course was flawed.
|
| 0 |
Fail |
50% or less |
At the end of the course the student did not display an
appreciable knowledge of the subject.
|
Back to course home page
Last update: 4 June 2024.