Data Structures and Algorithms

2019-2020
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

Doel vak

The goal of the course is to get acquainted with basic data structures
and the the design and analysis of algorithms.

For the data structures part:
At the end of the course, the student is familiar with data structures
such as stacks, queues, linked lists, binary trees, binary search trees,
balanced binary search trees, heaps, graphs, hash tables, The student is
able to give (in pseudo-code) and analyze querying and updating
operations on the data structures, and to express a data structure using
one or more other data structures.

For the algorithms part:
At the end of the course, the student is familiar with several sorting
algorithms, string matching algorithms, some graph algorithms, with the
paradigms of divide-and-conquer, dynamic programming, and greedy
algorithms, and with several concrete algorithms of every paradigm. The
student is able to give (in pseudo-code) algorithms with an appropriate
data structures,
and to analyze algorithms in terms of worst-case time complexity, and in
some case also with respect to space complexity and correctness.

Inhoud vak

The course is concerned with data structures and the design and analysis
of algorithms. We study several subjects from the book by Cormen et al:
linear data structures such as stacks, queues, linked lists, tree-like
data structures such as binary trees, binary search trees, balanced
binary search trees, heaps, graph-like data structures, and hash tables.
Further we study several sorting algorithms. some graph algorithms.
string matching,
and the programming paradigms divide-and-conquer, dynamic programming,
and greedy algorithms. We consider the worst-case time complexity and in
some cases the correctness of algorithms.

Onderwijsvorm

There are 2 lectures per week and 2 exercise classes per week.

Toetsvorm

There is a non-obligatory written mid-term exam that is concerned with
the material of roughly the first three weeks.

There is a written final exam that is concerned with all material,

If the grade for the mid-term exam is higher than the grade for the
final exam, then the mid-term exam contributes for 25% to the final
grade and the final exam contributes for 75% to the final grade. In the
other cases, the final grade is the grade for the final exam.

Literatuur

Introduction to Algorithms
third edition,
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford
Stein, MIT Press 2009.

Doelgroep

2CS, 2BA, 3IMM, 3LI, 3W, 3Ect

Afwijkende intekenprocedure

The registration procedure is the standard one.

Toelichting Canvas

The schedule, slides for the lectures, and material for the exercise
classes are available via the Canvas page of the course.

Aanbevolen voorkennis

It is helpful to know recursive procedures and arrays such as for
example taught in the course Computer Programming (XB_40011).
It is helpful to know graphs and elementary graph algorithms as for
example taught in the course Networks and Graphs (X_401010).

Algemene informatie

Vakcode X_400614
Studiepunten 6 EC
Periode P1
Vakniveau 200
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator dr. F. van Raamsdonk
Examinator dr. F. van Raamsdonk
Docenten dr. F. van Raamsdonk

Praktische informatie

Voor dit vak moet je zelf intekenen.

Voor dit vak kun je last-minute intekenen.

Werkvormen Werkcollege, Deeltoets extra zaalcapaciteit, Hoorcollege
Doelgroepen

Dit vak is ook toegankelijk als: