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.

week 36-42: Thursday 11.00-12.45

teacher: Femke van Raamsdonk

see also the course schedule.

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

The book is also available via STORM.

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 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.

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.

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) |

Last change October 20, 2016.