Aalto courses in Algorithms and Discrete Methods

[Pekka Orponen]

Aalto courses in Algorithms and Discrete Methods, 2013-2014

Dear all,

please be informed of the following courses in the areas of algorithms,
cryptology and supporting mathematical methods offered at the Aalto
Department of Information and Computer Science in the academic year
2013-2014. (For further courses in e.g. computational logic and
distributed computation, see "http://ics.aalto.fi/en/studies/courselist/".)

------------------------------------------------------------------

T-79.4202 Principles of Algorithmic Techniques (5 cr), Autumn 2013
Lecturer: Prof. Pekka Orponen

General: Efficient algorithms are a core element of modern computational
technology, and also fascinating objects of mathematical study.
Designing efficient algorithms requires knowledge, insight and skill,
and the choice of algorithm for a challenging computational task can
make a difference of several orders of magnitude in eventual system
performance. This course introduces a number of common "design
paradigms" that occur repeatedly as underlying principles of efficient
algorithms, and presents important examples of the use of each paradigm.
These paradigms provide also helpful conceptual tools for approaching
new algorithm design tasks.

Contents: Fundamental algorithm design paradigms: divide-and-conquer,
greedy algorithms, dynamic programming. Randomised algorithms.
Introduction to the analysis of algorithms and the theory of
NP-completeness.

Prerequisites: First year engineering mathematics, together with an
introduction to probability theory (e.g. Mat-1.2600), and programming
skills (e.g. T-106.1200). Familiarity with basic data structures (e.g.
T-106.1220) an asset.

Lectures: Tue 12:15-14:00 C (Otakaari 1), Thu 10:15-12:00 T1 (CS building)
Exercises: weekly, 2 groups; 3 small programming assignments

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.4202/"

------------------------------------------------------------------

T-79.4502 Cryptography and Data Security (5 cr), Autumn 2013
Lecturer: Prof. Kaisa Nyberg

General: Cryptography consists of the mathematical methods for modern
information and communication security systems. This course gives
introduction to the commonly used mathematical building blocks of
cryptographic primitives, and to the basic principles of cryptographic
security, authentication, confidentiality, and integrity of data. The
most common generic attacks such as meet-in-the-middle,
man-in-the-middle, and collision attacks, are presented, and their
impact to the fundamental limits of cryptographic security defined in
terms of parameter lengths is explained. By programming of some modern
cryptosystem the students will learn how cryptosystems work in practice.

Prerequisites: Programming skills in C are required. Some background in
discrete mathematics is useful but not necessary.

Lectures: Mon 12:15-14:00 AS2 (TUAS building)
Exercises: biweekly, 3 groups; programming assignments

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.4502/"

------------------------------------------------------------------

T-79.7003 Random Graphs and Complex Networks (8 cr), Autumn 2013
Lecturer: Dr. Charalampos E. Tsourakakis

General: Network science has emerged over the last years as an
interdisciplinary area spanning traditional domains including
mathematics, computer science, sociology, biology and economics. Since
complexity in social, biological and economical systems, and more
generally in complex systems, arises through pairwise interactions there
exists a surging interest in understanding networks. The goal of this
class is to introduce the audience to a set of important problems, ideas
and mathematical tools frequently used in the analysis of random graphs
and complex networks.

Prerequisites: Familiarity with undergraduate material in probability,
linear algebra and discrete mathematics.

Lectures: Fri 14:15-17:00 T5 (CS building)
Exercises: homework assignments, project work

Course pages: "https://noppa.aalto.fi/noppa/kurssi/t-79.7003/",
"http://randomgraphsaalto.wordpress.com/"

------------------------------------------------------------------

T-79.5103 Computational Complexity Theory P (5 cr), Spring 2013
Lecturer: Prof. Pekka Orponen

General: Computational complexity theory is the fundamental framework
for understanding the intrinsic nature of computation. Over its 50-year
history this research field has produced a continuous flow of deep work
in characterising the power and limitations of computational models,
classifying the inherent complexity of computational problems, and
introducing new approaches to computation. Part of the fascination of
the area derives from the cunning richness of the space of possible
computations, where even the most simple and "obvious" statements can
lead to impossibly difficult mathematical considerations.

Contents: NP-completeness. Randomised algorithms. Cryptography.
Approximation algorithms. Parallel algorithms. Polynomial hierarchy.
PSPACE-completeness.

Prerequisites: Basic theory of computation (e.g. T-79.1001).

Lectures: Mon 12:15-14:00, Wed 10:15-12:00 B353 (CS building)
Exercises: homework assignments

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.5103/"

------------------------------------------------------------------

T-79.5205 Combinatorics P (5 cr), Spring 2013
Lecturers: Prof. Petteri Kaski, Dr. Eugen Czeizler

Contents: An introduction to combinatorics. Basic combinatorial objects
(e.g. graphs, set systems, posets, permutations, set and integer
partitions, designs, codes), their properties and relationships.
Existence and enumeration. Extremal, probabilistic, and algebraic
techniques.

Prerequisites: First- and second-year engineering mathematics, together
with an introduction to discrete mathematics (e.g. Mat-1.2991) and
probability theory (e.g. Mat-1.2600).

Lectures: Tue 12:15-14:00, Wed 12:15-14:00 B353 (CS building)
Exercises: weekly, 1 group

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.5205/"

------------------------------------------------------------------

T-79.5207 Advanced Course in Algorithms P (5 cr), Spring 2014
Lecturer: Prof. Petteri Kaski

Contents: Advanced algorithm design techniques such as randomization,
approximation, parameterisation, parallelisation, and algebrisation.
Examples of contemporary advanced algorithms and supporting data
structures. Computational resources such as space, time, and
communication. Tradeoffs between resources. The course consists of a
fixed core part and a varying part covering topics of current interest.

Prerequisites: Fundamentals of algorithm design and analysis (e.g.
T-79.4202 or T-106.4100), good programming skills. First year
engineering mathematics, together with an introduction to probability
theory (e.g. Mat-1.2600). Familiarity with discrete algebraic techniques
(e.g. linear programming) an asset.

Lectures: Tue 10:15-12:00, Thu 12:15-14:00 T5 (CS building)
Exercises: weekly, 1 group; programming assignment

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.5207/"

------------------------------------------------------------------

T-79.5501 Cryptology P (5 cr), Spring 2014
Lecturer: Prof. Kaisa Nyberg

General: This course gives an introduction to the computational
techniques in modern symmetric-key and public-key cryptography. Starting
from Shannon's information theoretic principles the course will proceed
to exploration of nonlinearity properties of Boolean functions and
linear complexity profiles of sequences. The principles of statistical
cryptanalysis of symmetric-key ciphers is explained with the main focus
on differential and linear cryptanalysis. The latter part of the course
concentrates on algorithms for analysing public-key cryptosystems based
on the integer factorisation problem or the discrete logarithm problem
in a finite field or on an elliptic curve.

Prerequisites: Background in finite fields and elementary number theory
is recommended.

Lectures: Thu 12:15-14:00 B353
Exercises: weekly, 1 group

Course page: "https://noppa.aalto.fi/noppa/kurssi/t-79.5501/"