Syllabus for Algorithms and Data Structures I
Algoritmer och datastrukturer I
A revised version of the syllabus is available.
Syllabus
- 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: 2017-05-02
- Revised by: The Faculty Board of Science and Technology
- Applies from: Autumn 2017
-
Entry requirements:
10 credits in computer programming (Program Design, Programming Techniques II, or equivalent) and 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.
- choose appropriate algorithms and data structures for storing data, searching and sorting, as well as implement those algorithms.
- use and implement basic graph algorithms.
Content
Mathematical foundations: asymptotic notation, summations, recurrence relations.
Data structures: trees, FIFO queue, stack, priority queues, heaps.
Searching: binary search trees, balanced search trees, hash tables.
Sorting: insertion sort, merge sort, quick sort, heap sort.
Graph algorithms: depth first and breadth first search, topological sort and (strongly) connected components.
Design techniques: divide-and-conquer.
Implementation of algorithms and data structures.
Instruction
Lectures, laboratory work, lessons, and mandatory assignments.
Assessment
Written exam (4 p). Assignments (1 p).
Other directives
The unit cannot be included in a degree with Program Design II (1IT022), nor with Data Structures (1DL009, 1TD191, 1MB026).
Syllabus Revisions
Reading list
Reading list
Applies from: Autumn 2017
Some titles may be available electronically through the University library.
-
Cormen, Thomas H.
Introduction to algorithms
3. ed.: Cambridge, Mass.: MIT Press, cop 2009
Mandatory