Course Overview

The course provides an introduction to elementary concepts of mathematics for computer science. Topics include: formal logic notation, induction, sets and relations, permutations and combinations, counting principles, discrete probability.

Learning Achievement

The goal of this course is to provide the student with a wide groundwork of mathematical concepts. This course focus on mathematical topics that are useful to understand computer science theory. In particular, this course focus on teaching techniques for proving theorems in different mathematical fields that are related to computer sciences. This course is fully in English.

Competence

・汎用コンピテンス
1. コミュニケーション能力
・専門コンピテンス
1. 情報科学を支える基礎知識
5. グローバルな視野とコミュニケーション能力

Course prerequisites

Grading Philosophy

Every week the student has to submit an exercise sheet in English on manaba. The deadline is one week. The final examination covers the entire course. The final grade is composed of the average grade of the exercise sheets (60%) and the final exam (40%).

Course schedule

What is a proof? Proof Methods (Proof by Contradiction, Proof by Cases). The well ordering principle. Propositions, Logic and Quantifiers.
Sets and Proofs. Induction. Relations and Functions. State Machines.
Number Theory. GCD. Primality. Euler's Theorem. RSA Algorithm.
Graphs. Walks and Paths. Directed Graphs and Scheduling. Partial Orders and equivalences.
Graphs. Degrees and Isomorphism. Trees. Coloring and Connectivity. Stable Matching.
Sums and Products. Asymptotic. Computational Complexity.
Counting. Bijection Rules, Rules for counting set components (cards, dice, etc). Division Rule, Binomial Theorem. Bookkeeper Principle, Pigeonhole Principle.
Probability. Discrete Probability: Probability and Counting. Probability Spaces. Infinite Probability Spaces. Conditional Probability. Bayes' Theorem.
Probability. Independence and Causality. Random Variables and Random Walks. Expectation and Mean Time to Failure.
Advanced topics: Probability Graphs, Google Pagerank Algorithm. Sampling and Confidence. Final Exam Practice.

Course type

Lectures and Class Exercises

Online Course Requirement

Instructor

Aranha, Claus,Ye Xiucai

Other information

This course covers topics that are similar to "Programming Challenges" (GB21802) from a more theoretical point of view.

Site for Inquiry