Algorithms

The course can be part of the following programmes:

1. Computer Science, Bachelor's Programme (N1COS)
2. Computer Science, Master's Programme (N2COS)
3. Applied Data Science Master's Programme (N2ADS)
4. Mathematical Sciences, Master's Programme (N2MAT)
5. Bachelor's Programme in Mathematics (N1MAT)

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

One requirement is to have a bachelor's degree of 180 hec in computer science (or equivalent), or alternatively to have successfully completed courses corresponding to 120 hec in computer science or mathematics. The following requirements must also be satisfied:

• 7.5 hec in discrete mathematics (DIT980 Discrete Mathematics for Computer Scientists, or the sub-course Introductory Algebra of MMG200 Mathematics I, or equivalent),
• additionally 10 hec in mathematics,
• 15 hec in programming, and
• 7.5 hec in data structures (this requirement can be satisfied by the course DIT375 Python for Data Scientists).

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 topics are as follows:

• What is an efficient algorithm?
• Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls.
• Solving recurrence relations.
• Data structures and algorithms. Review of basic data structures.
• Graph algorithms.
• Greedy algorithms.
• Divide-and-conquer.
• Dynamic programming.
• Exhaustive search.
• Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. Coping with hard problems.
• Combine different design techniques and data structures.
• Short orientation about other design techniques: e.g. randomized algorithms,
  preprocessing, and others.

On successful completion of the course the student will be able to:

Knowledge and understanding

• describe algorithms and their qualities: explain algorithms in writing, so that others can understand how they work, why they are correct and fast, and where they are useful;
• recognize and formalize non-trivial computational problems that appear in various real-world computer applications and which need to be solved by algorithms;
• intractability: recognize intractable problems and other classes of problems like P,NP, NPC;
• prove the correctness of algorithms.

Competence and skills

• design: apply the main design techniques for efficient algorithms (for instance greedy, dynamic programming, divide-and-conquer) to problems which are similar to the textbook examples but new;
• perform in simple cases the whole development cycle of algorithms: problem analysis, choosing, modifying and combining suitable techniques and data structures, analysis of correctness and complexity, looking for possible improvements, etc;
• perform simple reductions between problems, explain NP completeness, recognize various computationally hard problems which tend to appear over and over again in different applications,

Judgement and approach

• critically assess algorithmic ideas and demonstrate the ability to see through obvious and seemingly plausible algorithms that often turn out to be incorrect;
• analyse: explain why the time efficiency of algorithms is crucial, express the time complexity in a rigorous and scientifically sound manner, analyze the time complexity of algorithms (sum up operations in nested loops, solve standard recurrences, etc.) i.e. perform an objective evaluation of the performance and be able to compare it to other algorithms performance.

The course is given as lectures, combined with exercise sessions for problem solving related to the course and and a number of assignments intended to develop the skill of analyzing and designing algorithms.

Language of instruction: English

The course is examined by an individual written hall-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. Written hall examination, 7.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)

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 is a joint course together with Chalmers.

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