Course Description: The main objective of this course is to learn basic skills and knowledge to design efficient algorithms and data structures and to analyze their complexity. Students will learn about basic algorithms and data structures, and how to select an algorithm or data structure for a given task. These include
The sessions will intertwine lectures and solving and discussing exercises. These take place Tuesdays 13:45-17:30 in MDB 0.30.
Lecture |
Assignments |
|||||||
Week |
Date |
Topic |
Lecture Schedule |
Slides |
Reading |
Python notes |
Due |
Home work |
35 |
28-08-2018 |
Linear Search, Proving Correctness. | lecture with in-class exercises | [C] Chapter 1, Chapter 2 (parts) |
notes: intro/linear search: html, nb, loop invariants: html, nb, (with index shift: html, nb) induction: html, nb, maths background: html, nb, recursion: html, nb, practice set 1 (without solution): html, nb, practice set 2 (proofs, without solution): html, nb, practice set 2 (proofs, with solution): html, nb, practice set 3 (growth rate, asymptotics, without solution): html, nb, practice set 3 (growth rate, asymptotics, with solution): html, nb, practice set 4 (loops, loop invariants, without solution): html, nb, practice set 4 (loops, loop invariants, with solution): html, nb, weather data: csv, info, nb, count in interval (1d range counting): html, nb, proving f(n)=O(g(n)): html, nb |
25-09-2018 | ||
36 |
04-09-2018 |
Asymptotic Analysis of Algorithms, Binary Search. | lecture with in-class exercises |
|
[C] Chapter 2 (remaining parts), Chapter 3: only binary search, [CLRS] Chapter 3 |
|||
37 |
11-09-2018 |
no lecture
|
||||||
38 |
18-09-2018 |
Sorting Algorithms. | 2nd half: work on Assignment 1 |
|
[CLRS] Chapter 2, 4.3-4.5; also [C] Chapter 3 | |||
39 |
25-09-2018 |
Recurrences. | 2nd half: discussion of Assignment 1 | notes: sorting: html, nb Master theorem: html, nb practice set 1: html, nb practice set 2 (recurrences, without solutions): html, nb practice set 2 (recurrences, with solutions): html, nb(zip) |
16-10-2018 | |||
40 |
02-10-2018 |
Linear-time Sorting. Quicksort |
|
[CLRS] 8.1-8.3, also [C] 4 | ||||
41 |
09-10-2018 |
Abstract Data Types, Elementary Data Structures. | 2nd half: work on Assignment 2 |
|
[CLRS] 10.1-10.2 |
notes: html, nb
whiteboard: main, more practice set (without solutions): html, nb practice set (with solutions): html, nb |
||
42 |
16-10-2018 |
Hash Tables. | 2nd half: exercises hashing, discussion of Assignment 2 |
|
[CLRS] 11.1-11.4 |
practice set 1:
html,
nb
practice set 2 (without solutions): html, nb practice set 2 (with solutions): html, nb(zip) whiteboard: main, more |
06-11-2018 | |
43 |
23-10-2018 |
Heaps. | 2nd half: exercises + continued discussion of Assignment 2 |
|
[CLRS] 6 | notes: html, nb
practice set 1: html, nb practice set 2 (without solutions): html, nb practice set 2 (with solutions): html, nb(zip) whiteboard: pdf |
||
44 |
30-10-2018 |
Binary Search Trees. | 2nd half: work on Assignment 3 |
|
[CLRS] 12 | notes: html, nb partial: nb
practice set (without solutions): html, nb practice set (with solutions): html, nb(zip) whiteboard: pdf |
||
45 |
06-11-2018 |
Graph Algorithms. | 2nd half: discuss solution to Assignment 3 |
|
[CLRS] 22 |
practice set 1:
html,
nb
practice set 2 (without solutions): html, nb(zip) practice set (with solutions): html, nb(zip) |
27-11-2018 | |
46 |
13-11-2018 |
More Tree/Graph Algorithms. | last hour: work on Assignment 4 |
|
[C] parts of 6 (Dijkstra's algorithm) and parts of 10 (NP-hard problems). |
practice set (without solutions):
html,
nb
practice set (with solutions): html, nb(zip) note: NP-hardness will not be part of assignments/exam. |
||
47 |
20-11-2018 |
kD-trees, Wrap Up. | 2nd half: wrap up, work on Assignment 4 |
|
Not covered by the books. If you are interested, ask me for further reading material. | note: kD-trees will not be part of assignments/exam. | ||
48 |
27-11-2018 |
Practice Exam. | last hour: discussion of practice exam, brief discussion of Assignment 4 |
|
|
|||
11-12-2018, 13:30-16:30, Exam | ||||||||
15-01-2019, Second chance Exam |
Important: If you reach less than 50% of the possible points on the homework assignments or if you reach less than 50% of the points on the exam, then you will fail the course, regardless of the total number of points you collected; in this case your grade will be the minimum of 5 and the grade you achieved.
A great feature of Jupyter Notebook is that it is simple to typeset mathematics using LaTeX commands. LaTeX is a document typesetting software package that is widely used by mathematicians, (computer) scientists, and many others that need to typeset technical writing. This article on Wikipedia gives you some background and history.
For more background on LaTeX you can also read the "Not so short introduction ..." or check out this Wikibook.
You don't need to buy any of these books. A copy of each is available in Mariƫnburg.
![]() |
T.H. Cormen. |
![]() |
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein. |
![]() |
R.D. Necaise. |
![]() |
M.T. Goodrich, R. Tamassia, M.H. Goldwasser. |