Syllabus for Algorithms and Data Structures I

Algoritmer och datastrukturer I

A revised version of the syllabus is available.

  • 5 credits
  • Course code: 1DL210
  • Education cycle: First cycle
  • Main field(s) of study and in-depth level: Computer Science G1F, Technology G1F
  • Grading system: Fail (U), Pass (3), Pass with credit (4), Pass with distinction (5)
  • Established: 2007-03-19
  • Established by: The Faculty Board of Science and Technology
  • Revised: 2008-11-03
  • Revised by: The Faculty Board of Science and Technology
  • Applies from: week 27, 2009
  • Entry requirements: 10 credits in programming (Program Design 1DL200, Programming techniques II or equivalent) 10 credits in mathematics, including basic algebra.
  • Responsible department: Department of Information Technology

Learning outcomes

In order to pass, the student must be able to


  • analyse the runtime performance of a (simple) algorithm/program in terms of the size of its inputs, and this in the average, best, and worst cases.

  • answer evaluation questions such as the following: If the inputs double in size, will the runtime be the same, doubled, quadrupled, squared, or what? Which algorithm/program should one choose among several alternatives for the same specification? Which data structure should one choose when implementing an algorithm, considering its basic operations (add, modify, delete, find, order) on its data? Does it make a difference in runtime (for large inputs) if one replaces a part of an algorithm/program by a faster alternative?

  • state in a precise way the assumptions underlying such a runtime performance analysis.

  • know (and analyse) the runtime performance of the basic operations (add, modify, delete, find, order) for some of the most common (simple) data structures (lists, arrays, first-in first-out queues, priority queues, stacks, trees, heaps).

  • explain the trade-off of using a so-called greedy algorithm (that makes opportunistic choices without any sense of regret) for an optimisation problem where the expected runtime performance is very bad for the typically occurring size of the inputs.

Content

Mathematical foundations: asymptotic notation, summations, recurrence relations.
Data structures: stacks, first-in first-out queues, trees, heaps, priority queues.
Searching: binary search trees, balanced search trees, hash tables.
Sorting.
Graph algorithms (simple ones).
Greedy algorithms.
Implementation in a functional programming languageof algorithms and data structures.

Instruction

Lectures, laboratory work, lessons, and mandatory assignments.

Assessment

Written exam (4 p). Assignments (1 p).

Reading list

The reading list is missing. For further information, please contact the responsible department.