Credits: 5

Schedule: 11.09.2019 - 13.12.2019

Contact information for the course (applies in this implementation): 

Responsible Professor: 

Parinya Chalermsook 

Teaching Assistants: 

  • Ameet Gadekar 
  • Nidia Obscura Acosta 
  • Ly Orgo 
  • Sorrachai Yingcharoenthawornchai 

Teaching Period (valid 01.08.2018-31.07.2020): 

I - II (Autumn)

Learning Outcomes (valid 01.08.2018-31.07.2020): 

At this course you will become familiar with a number of fundamental structures and principles underlying the design of efficient algorithms, and will learn to approach new algorithmic problems using these generic paradigms. You will also come to appreciate the possibilities and limitations of theoretical a priori analysis of algorithm efficiency, and learn to perform such analyses in simple cases.

Content (valid 01.08.2018-31.07.2020): 

Fundamental algorithm design paradigms: divide-and-conquer, greedy algorithms, dynamic programming. More advanced philosophy of algorithms design: Randomization, duality, and algebraic techniques. 

Details on the course content (applies in this implementation): 

In Autumn 2019, we will be following Erickson's book:

We will cover chapters 1 - 12 and some additional topics. 

Assessment Methods and Criteria (valid 01.08.2018-31.07.2020): 

Exercise sessions, programming assignments, and exam. 

Elaboration of the evaluation criteria and methods, and acquainting students with the evaluation (applies in this implementation): There will be no exam.

Ideally (but not necessarily), you are expected to attend:

A) 8 lectures: Each lecture is 2-hour long. Check the schedules for detail. The purpose of the lectures is NOT to provide a detailed account of course materials but rather to introduce students to the topics so as to facilitate student's independent studies.

B) 8 Excercises: Submit class exercises and get feedbacks on your work. Check the schedules for detail.

C) Final project report: A final report & 15-minute interview with teaching staffs is required if you want to get grade 5. A final report should be 5-page and can be:

(C.1) [THEORY] writing a detailed proof on 3 "hard" exercises, or
(C.2) [IMPLEMENTATION] an implementation and/or visualization of algorithms.

Workload (valid 01.08.2018-31.07.2020): 

Lectures. Exercise sessions. Exam. Independent work. 

Details on calculating the workload (applies in this implementation): Here is an example of how you could spend your time:

- Attending lectures 2x8 = 16 hours.
- Independent study 3x8 = 24 hours.
- Exercises 40 to 80 hours, depending on your background and expected grades
- Final project 0 to 30 hours.

Study Material (valid 01.08.2018-31.07.2020): 

S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorithms. McGraw-Hill 2008.

Details on the course materials (applies in this implementation): In Autumn 2019, we will be following Erickson's book:

Substitutes for Courses (valid 01.08.2018-31.07.2020): 

Replaces the courses T-79.4202 Principles of Algorithmic Techniques and T-106.4100 Design and Analysis of Algorithms.

Prerequisites (valid 01.08.2018-31.07.2020): 

First year engineering mathematics, together with an introduction to probability theory (e.g. MS-A05XX), and programming skills (e.g. CS-A111X). Familiarity with basic data structures (e.g. CS-A114X) an asset.

Grading Scale (valid 01.08.2018-31.07.2020): 


Details on the schedule (applies in this implementation): 

There will be 8 lectures. Tentative dates are: 

- September 20, 2019. 16:15 - 18:00  

- September 27, 2019. 16:15 - 18:00  

- October 4 (or 11), 2019. 16:15 - 18:00  

- October 11 (or 18), 2019. 16:15 - 18:00 

- November 1, 2019. 16:15 - 18:00 

- November 8, 2019. 16:15 - 18:00 

- November 22, 2019. 16:15 - 18:00 

- November 29, 2019. 16:15 - 18:00 


Registration and further information