General
The purpose of this course is to introduce students to various techniques in Algorithms Design.
Algorithms is a key engine of modern computer science. This course will give you important algorithmic and mathematical tools for handling modern challenges in computing. We will start with basic principles and will delve into advanced algorithmic tools where you will get to learn, for instance, how to deal with intractability, uncertainty, and (time permitting) big data.
We will focus on rigorous analysis of algorithms, i.e., we will try to understand mathematically why certain algorithms work (and sometimes why certain approaches will never work.)
The course is suitable for computer science students at all levels (bachelor, master and doctoral students) who seek to enhance their algorithmic, mathematical and analytical toolboxes in computer science.
Lectures: Tuesday & Thursday (8:30 to 10:00), Room T1 (CS building). First class is on September 11. Solution sessions will also be held in some of the lecture time slots.
Small group tutorials: There are four possible schedules.
- Session A: Room T3 (CS building). Wednesday 14:15 - 16:00
- Session B: Room T5 (CS building). Thursday 10:15 - 12:00
- Session C: Room TU3 (Maarintie 8).Thursday 14:15 - 16:00
- Session D: Room T3 (CS building). Friday 12:15 - 14:00
Responsible Professor: Parinya Chalermsook
Teaching Assistants (TA):
 Ameet Gadekar |
 Wanchote Jiamjitrak |
|---|---|
 Nidia Obscura |
 Ly Orgo |
SCHEDULE (updated on 13 Nov 2018)
GRADING
There will be three components of the grades.
1) Exams (EX)
There will be two exams. The grading of the exams is only pass/fail. You need to pass both exams to pass the course.
The exam dates are as follows:
- First exam: October 30, 2018 at 8:30 (Room T1)
- Second exam: December 4, 2018 at 8:30 (Room T1)
2) Conceptual Exercises (CE)
There will be exercises that test your conceptual understanding of algorithms design and analysis. The total achievable score for CE is (approximately) 100. There are various components that contribute towards the CE scores:
Home Assignments (HA): There will be 4 home assignments. Each such assignment carries 20 CE points. All HA assignments must be submitted through MyCourses. There is a soft deadline for submitting your HA work: If you submit it before the soft deadline, you have a possibility to get full points. If you submit it after the soft deadline, you can earn at most 30% of the total points.
The soft deadlines for home assignments are as follows:
- Assignment 1:
October 1, 2018October 2, 2018 at 23:55 [extended] - Assignment 2:
October 22, 2018 at 23:55October 23, 2018 at 23:55 [extended] - Assignment 3: November 19, 2018 at 23:55
- Assignment 4: December 18, 2018 at 23:55
The hard deadlines for all assignments are December 31, 2018 at 23:55. After this deadline, no submission will be accepted.
Short Quizzes (SQ): There will be at least 9 short quizzes to be done during the solution sessions and "small group" tutorials. Each quiz carries 2 CE point. There is a hard deadline for submitting your SQ work, i.e. it will be handed out at the beginning of the session and due at the end of each session.
Late submission for SQ is not accepted in any circumstances.
Hardworking Bonus (HB): There will be various opportunities for getting bonus points by, for instance, pointing out important mistakes made by the instructor or the TAs, or by contributing to the online discussions in a way that helps your classmates. Another way to earn such bonus is by solving "algorithmic challenges" to be posted regularly on MyCourses. In total, there will be at least 8 bonus points.
The total CE points = HA + SQ + HB3) [Optional] Programming Exercises (PE)
There will also be programming exercises that test your ability to turn concepts into actual codes. These exercises are optional. The maximum achievable score for PE is 15 (100% of the exercises).
There is a hard deadline for PE assignments. There will be 2 separate deadlines:
- PE deadline 1: October 31
- PE deadline 2: November 30
| Grades | Criteria | |
|---|---|---|
| 5 | Pass EX & | CE + Min(PE,10) >= 70 |
| 4 | Pass EX & | CE + Min(PE,15) >= 60 |
| 3 | Pass EX & | CE + Min(PE,15) >= 50 |
| 2 | Pass EX & | CE + Min(PE,15) >= 40 |
| 1 | Pass EX |
Warning: This is a 5 ECTS credit course, which means roughly 130 study hours. And this course is an example where, if you have no prior background in Algorithms, such hours are actually necessary to pass the course. If you believe you can only commit substantially less than this number, please consider taking the course later (the course is offered every Autumn).
COURSE TEXTBOOK
The main textbooks are
- Dasgupta, Papadimitriou, Vazirani, “Algorithms”, McGraw-Hill 2008. PDF version is available on the internet.
- Erickson "Algorithms, Etc", link
There will occasionally be handouts from the lecturer.
INTENDED LEARNING OUTCOMES
- Analysis: Students are able to formally (or mathematically) argue about the efficiency and correctness of an algorithm.
- Design: Students are able to design algorithms using basic algorithmic paradigms.
- Modelling: Students are able to model real-world problems formally as computational problems.
CLASS SESSIONS AND EXPECTATIONS
Ideally (but not necessarily), you are expected to attend
- 16 lectures: The instructor will explain the digested concepts ignoring certain technicalities. If you feel that reading the book is hard, please try to attend the lectures.
- 4 solution sessions: The TA will explain the solutions to the HA exercises.
- 5 "small group" tutorials: The TA will conduct small group tutorials where students are split into classes of size around 40. In these sessions, some concepts will be explained more in detail. Students will be sent a poll to vote for which tutorial sessions they want to attend.
HONOR CODES
Students are strongly encouraged to discuss exercise problems with classmates. But write or type your own solutions. Clearly acknowledge help from other students, e.g. "I got ideas from Student X" or "I found the solution on website YYY".
A failure to acknowledge properly the sources of your solutions will be regarded as plagiarism, which would be severely punished.