Algorithms, advanced course

The course can be part of the following programmes:

1. Computer Science, Master's Programme (N2COS)
2. Applied Data Science Master's Programme (N2ADS)
3. Computer Science, Bachelor's Programme (N1COS)

The course is a also a single-subject course at Gothenburg University.

The requirement for the course is to have successfully completed courses corresponding to 120 creditswithin the subject Computer Science or equivalent, including successful completion of DIT093 Algorithms, 7.5 credits(or equivalent).

Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.

The course covers the following topics;

• approximation algorithms and approximation schemes for NP-complete problems, and their analysis,
• use of linear programming, in particular for approximation,
• network flow with some complex applications,
• randomized algorithms and their analysis by appropriate random variables,
• helpful input structures like tree structures and input parameters.

After completing the course the student is expected to be able to:

Knowledge and understanding

• apply important design and analysis techniques for algorithms, in particular, ways to approach NP-complete problems,
• describe current research on algorithms,

Competence and skills

• apply design and analysis techniques to solve new problems that may arise in various applications,
• explain complex algorithms and their proofs in written form,

Judgement and approach

• find connections between algorithmic problems and turn them into formal reductions,
• perform more complex analysis of algorithms, in particular, analyze the worst case and expected time complexities and error probabilities for randomized algorithms.

Lectures, exercises, feedback and consultations.

Language of instruction: English

The course is examined by hand-in exercises and a final take-home exam.

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

Sub-courses

1. Assignment, 7.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)

The grading scale comprises: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U).

To pass the course, all mandatory components must be passed. To earn a higher grade than Pass, a higher weighted average from the grades of the components is required.

The course is evaluated through meetings both during and after the course between teachers and student representatives. Further, an anonymous questionnaire is used to ensure written information. The outcome of the evaluations serves to improve the course by indication which parts could be added, improved, changed or removed.

The course replaces DIT280 Algorithms advanced course 7,5 hp. The course cannot be included in a degree which contains DIT280. Neither can the course be included in a degree which is based on another degree in which the course DIT280 is included.

The course is a joint course together with Chalmers.