Swedish name: Effektiva algoritmer
This syllabus is valid: 2023-06-26 and until further notice
Course code: 5DV182
Credit points: 7.5
Education level: Second cycle
Main Field of Study and progress level:
Computing Science: Second cycle, has only first-cycle course/s as entry requirements
Grading scale: TH teknisk betygsskala
Responsible department: Department of Computing Science
Established by: Faculty Board of Science and Technology, 2017-08-04
Revised by: Faculty Board of Science and Technology, 2023-03-07
The course covers techniques for constructing effective algorithms and typical data structures used in these. Special consideration is given to the fact that efficiency depends not only on the inherent asymptotic behavior of the algorithms but also on the specific problem instances on which it is applied. Standard algorithms and data structures need therefore often be chosen and adapted to solve the problem as effectively as possible.
Part 1, Algorithmic techniques and data structures, 3 credits, deals with effective algorithmic techniques (divide-and-conquer, greedy, dynamic programming), their usages, pros, and cons, illustrating these techniques using central algorithms, and discussing examples of effective data types (Eg heaps, red-black trees, union-find) and their implementation.
Part 2, Problem solving and algorithm analysis, 4.5 credits,
consists of the student, both theoretically and empirically, examining variants of a known algorithm with respect to efficiency and writing a report on this. The entire chain from initial, usually unclear specified research questions to the completed algorithmic solution and its theoretical and empirical analysis are included. The part trains the student's ability to go from an unclearly formulated problem specification to an exact formulation, develop an appropriate algorithmic solution, if possible improve it by adapting it to the problem's particularities, as well as analyzing and discussing its effectiveness.
Knowledge and understanding
After completing the course, the student should be able to
Competence and skills
After completing the course, the student should be able to
Judgement and approach
After completing the course, the student should be able to
At least 90 ECTS, including 60 ECTS Computing Science, or at least 120 ECTS within a study programme. At least 7.5 ECTS programming; 7.5 ECTS data structures and algorithms; 7.5 ECTS discrete mathematics; and 7.5 ECTS formal languages. Proficiency in English equivalent to the level required for basic eligibility for higher studies.
Teaching consists of three different elements: Teacher-led lessons, tutorial meetings where problem statements and the suggested solutions or identified problems are discussed, as well as feedback on draft reports submitted at predefined times. In addition to scheduled activities, individual work with the material is also required. It is the student's responsibility to get into the material in time and to prepare any questions to get appropriate feedback.
Part 1 is examined though an oral exam. The grades given are Fail (U) or Pass (G)
Part 2 is examined by a written report submitted by the student at the end of the course. The grading scheme is Fail (U), Pass (3) or Pass with Merit (4), or Pass with Distinction (5).
The grading scheme on the course as a whole is Fail (U), Pass (3) or Pass with Merit (4), or Pass with Distinction (5). The grade is determined by the grade on Part 2.
Adapted examination
The examiner can decide to deviate from the specified forms of examination. Individual adaptation of the examination shall be considered based on the needs of the student. The examination is adapted within the constraints of the expected learning outcomes. A student that needs adapted examination shall no later than 10 days before the examination request adaptation from the Department of Computing Science. The examiner makes a decision of adapted examination and the student is notified.
This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If in
doubt, consult the student counselors at the Department of Computing Science and / or the program director of your
program. In particular, this course can not, in whole or in part, be used in a degree together with 5DV170 Efficient algorithms.
If the syllabus has expired or the course has been discontinued, a student who at some point registered for the course is guaranteed at least three examinations (including the regular examination) according to this syllabus for a maximum period of two years from the syllabus expiring or the course being discontinued.
Introduction to algorithms
Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford
Fourth edition : Cambridge, Mass. : MIT Press : [2022] : xx, 1291 pages :
ISBN: 9780262046305
Mandatory
Search the University Library catalogue
Linz Peter
Introduction to formal languages and automata
Jones And Bartlett Publishers : 2016 : 450 sidor :
ISBN: 9781284077247
Search the University Library catalogue
Cormen Thomas H.
Introduction to algorithms
3. ed. : Cambridge, Mass. : MIT Press : cop 2009 : xix, 1292 s. :
ISBN: 9780262033848 (inb.)
Mandatory
Search the University Library catalogue
Linz Peter
Introduction to formal languages and automata
Jones And Bartlett Publishers : 2016 : 450 sidor :
ISBN: 9781284077247
Search the University Library catalogue