Data Structures and Algorithms 2016-2017

Contents

Data Structures and Algorithms (course code 400614) is a course of 6 ECTS which is taught in period 1.

Contents concerning data structures:
Linear data structures: stacks, queues, linked lists. Tree-like data structures: binary trees, binary search trees, heaps, red-black trees or AVL-trees. Graphs-like data structures. Hash tables.
Contents concerning algorithms:
sorting algorithms, the divide-and-conquer programming paradigm, dynamic programming, greedy algorithms, graph algorithms, string matching.
Contents concerning complexity analysis:
big-Oh notation, worst-case time complexity, amortized analysis.
See also the study guide.

Lectures

week 36-42: Monday 13.30-15.15
week 36-42: Thursday 11.00-12.45
teacher: Femke van Raamsdonk
see also the course schedule.

Exercise classes

week 36-42: Tuesday 15.30-17.15
week 36-42: Friday 09.00-10.45
teachers: Ellen Maassen (email: e.m.maassen@vu.nl) and Petar Vukmirovic (email: p2.vukmirovic@student.vu.nl)
see also the course schedule

Book

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms MIT Press 2009.
The book is also available via STORM.

Written exams

There is a mid-term exam (not obligatory) in week 39. The material for the mid-term exam is everything up to and included lecture and exercise class 7.

There is an exam at the end of the course in week 43. The material for the exam is everything discussed in the lectures and exercise classes.

A summary of the material discussed in the 2016-2017 course.

There is a resit of the exam scheduled in week 2 (of 2017).

Mid-term exam of 2014-2015.
Exam of 2014-2015.
Mid-term exam of 2015-2016.
Exam of 2015-2016.
Mid-term exam of 2016-2107.
Exam of 2016-2017.

Programming assignments

The deadline for programming assignment 1 is Thursday September 22, 2016.
Programming assignment 1 is concerned with insertion sort, merge sort, and heap sort.
The files containing for example the skeleton of your program are available via this link.
The pdf file with the programming assignment.

The deadline for programming assignment 2 is Monday October 17, 2016.
Programming assignment 2 is concerned with the algorithms for rod cutting and max-sub-array.
A pdf-file (version October 6) describing programming assignment 2.
The skeleton for programming assignment 2 is available via this link.

Final mark

If it is in your advantage, the mark for the mid-term exam contributes for 30% to the exam-mark, and the mark for the (global) exam contributes for 70% to the exam-mark. Otherwise, the exam-mark equals the mark for the (global) exam.

The first assignment contributes for 40% to the practical-mark, and the second assignment contributes for 60% to the practical-mark. The exam-mark contributes for 80% to the final mark.
The practical-mark contributes for 20% to the final mark.
Both the mid-term exam and the practical work are only valid in 2016-2017.
Both the exam-mark and the practical-mark has to be at least 5,5 in order to pass the course.

Links to additional information (not necessary for the exam)

Schedule per lecture 2016-2017 (preliminary):

Please see below for the slides and the sheets for the exercise classes.
week we do
36 lecture 1
introduction, model, insertion sort
book 1, 2
slides 4-up slides 1-up
exercise class 1
exercise sheet 1 homework: exercises 1, 2, 3, 7, 9; and some answers
lecture 2
selection sort, bubble sort, merge sort, divide-and-conquer, asymptotic notations
book 2, 4.3, 4.4 (3.1), (part of 3.2 is background material)
slides 4-up slides 1-up
exercise class 2
exercise sheet 2 homework: exercises 1 and 3 and some answers
37 lecture 3
heaps, heap sort
book 3.1, 6.1-6.4
slides 4-up slides 1-up
exercise class 3
exercise sheet 3 homework: 4, 6, 16, 17 and some answers
lecture 4
more about heapsort, priority queues, quicksort
book parts of 6.1-6.4, 6.5, 7.1
slides 4-up slides 1-up
exercise class 4
exercise sheet 4 homework: 1 and some answers
38 lecture 5
more about quicksort, lowerbound, linear sorting, stacks
book 7.2, 7.3, (7.4), 8, 10.1
slides 4-up slides 1-up
exercise class 5
exercise sheet 5 homework: 1-3 and some answers
DEADLINE PRACTICAL WORK 1
lecture 6
linked lists, hash tables
book 10.2, 11 (not 11.3.3, not 11.5)
slides 4-up slides 1-up
exercise class 6
exercise sheet 6 and some answers
39 lecture 7
tree traversals, binary search trees
book 12.1, 12.2, 12.3
preliminary version: slides 4-up slides 1-up
exercise class 7
exercise sheet 7 and some answers
lecture 8
short question hour
no new material from the book; discussion of old midterm exam
no new slides
MID-TERM EXAM
no exercise class 8
40 lecture 9
AVL-trees, amortized complexity
notes and book 17.1, 17.2, 17.4
preliminary slides: slides 4-up slides 1-up
exercise class 9
exercise sheet 9 homework: 1, 2, 9 and some answers
lecture 10
dynamic programming: make change, max-sub-array, rod cutting, knapsack01
book 4.1, 15.1, 15.3
slides 4-up slides 1-up
exercise class 10
exercise sheet 10 homework: 1, 3, 4 and some answers
41 lecture 11
dynamic programming: Fibonacci, knapsack01, LCS; graph representations, all pairs shortest paths
book 15.3, 15.4, 22.1, 25.2
slides 4-up slides 1-up
exercise class 11
exercise sheet 11 homework: 3, 5 and some answers
lecture 12
greedy algorithms: activity selection, fractional knapsack, Huffman codes
book 16.1, 16.2, 16.3
slides 4-up slides 1-up
exercise class 12
exercise sheet 12 homework: 7, 3, 12 and some answers
42 DEADLINE PRACTICAL WORK 2
lecture 13
Dijkstra's shortest path algorithm, brute force and Knuth-Morris-Pratt string matching algorithms
book 24.3, 32.1, 32.4
slides 4-up slides 1-up
exercise class 13
exercise sheet 13 homework:1, 2, 3, 8 and some answers
lecture 14
question hour
change: extra exercise class only in M655
43 EXAM (check official schedule)

Questions ?

Send an email to f.van.raamsdonk at vu.nl.
Last change October 20, 2016.