Data Structures and Algorithms (JBP031) – Spring 2019

go directly to the schedule

Course Information


Instructor: Kevin Buchin, k.a.buchin@tue.nl
Please use the tag [JBP031] in the subject of your email when contacting me about the course.

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

  •  arrays, lists, stacks and queues,
  •  searching and sorting algorithms,
  •  search trees,
  •  hash tables,
  •  and basic graph algorithms.
In addition, students will learn how to design simple algorithms using techniques like incremental algorithms and divide&conquer and how to evaluate algorithms and data structures in terms of their efficiency.

Lectures

The sessions will combine lectures and solving and discussing exercises. These take place Wednesdays 8:45-12:30 in MDB 1.09.



Schedule



 
Lecture
Assignments
Week
Date
Topic
Lecture Schedule
Slides
Reading
Python notes
Due
Home work
05
30-01-2019
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

whiteboard: sums (and one induction)
27-02-2019
(06-03-2019
for quiz)
06
06-02-2019
Asymptotic Analysis of Algorithms, Binary Search.

lecture with in-class exercises

[C] Chapter 2 (remaining parts), Chapter 3: only binary search,
[CLRS] Chapter 3
07
13-02-2019
Sorting Algorithms.

2nd half: work on Assignment 1

[CLRS] Chapter 2, 4.3-4.5; also [C] Chapter 3
08
20-02-2019
no lecture
09
27-02-2019
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)
whiteboard: substitution method
27-03-2019
10
06-03-2019
no lecture

11 

13-03-2019
Linear-time Sorting.  
[CLRS]  8.1-8.3, also [C] 4

12 

20-03-2019
Quicksort. 2nd half: work on Assignment 2
[CLRS]  7

13

27-03-2019
Abstract Data Types, Elementary Data Structures. 2nd half: discussion of 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
17-04-2019
14
03-04-2019
Hash Tables. 2nd half: exercises hashing, discussion of Assignment 2 continued + working on Assignment 3
[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
15
10-04-2019
Heaps.

2nd half: exercises + working on Assignment 3

[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
16
17-04-2019
Binary Search Trees. 2nd half: discuss solution to Assignment 3
[CLRS] 12 notes: html, nb partial: nb
practice set (without solutions): html, nb
practice set (with solutions): html, nb(zip)
whiteboard: pdf
08-05-2019
17
24-04-2019
Graph Algorithms. 2nd half: discuss solution to Assignment 3 continued, work on Assignment 4
[CLRS] 22 practice set 1: html, nb
practice set 2 (without solutions): html, nb(zip)
practice set (with solutions): html, nb(zip)
18
01-05-2019
No lecture. Time to work on practice exam (provided on blackboard) and Assignment 4. I will not be present for this.
19
08-05-2019
More Graph Algorithms, Wrap Up. 2nd half: wrap up, discussion of Assignment 4, brief discussion of first practice exam
[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 exam.
20
15-05-2019
Practice Exam. last hour: discussion of practice exam
 
June 5, 2019, 09:00-12:00, Exam
 

July 10, 2019, Resit Exam

 


Assignments and Grading


Grading scheme

The final grade will be based on two items:
  1. 4 homework assignments each counting for 10% of the final grade. (If necessary an additional assignment can be provided. In this case the best 4 out 5 count.)
  2. A written exam (closed book) which counts for the remaining 60% of the final grade.

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.

Homework Assignments

  1. Assignments consist of two parts. The first part is an online quiz consisting of relatively short questions. The second part is homework consisting of longer, more involved questions.
  2. The answers to the online quiz are submitted individually, the solutions to the homework questions of the second part have to be handed in by groups of 3 students. You should find a group in the first weeks of the course. If necessary, ask me for help. In case problems occur in your group, contact me as soon as possible.
  3. For the online quiz oncourse.tue.nl is used. When you have your TU/e account, you need to self-enroll in the corresponding course (direct link). This requires the enrollment key announced on blackboard. At the start of the course, a test quiz (Quiz 0) will be published there, which does not count towards the final grade (but is there for you to test the system). Quiz 1 will be published 12 days before the deadline. All other quizzes and assignments are published shortly after the deadline of the previous assignment. Note: This is the first time I am using OnCourse for this course. Please make sure to report any issues.
  4. Homework solutions to the group assignments have to be written in English.
    You should consider writing your solution as Jupyter Notebook (as soon as you learned about them, see also comment on LaTeX below), since this makes it easy to type mathematical expressions and include python code. Note: LaTeX commands can be used in Jupyter notebook to typeset mathematics, but you don't have the full power of LaTeX in Jupyter Notebook. To format your solution (e.g., setting text in bold, making lists) you can use Markdown, see here for a cheatsheet. You could also consider using LaTeX directly.
  5. Assignments are due before the lecture starts (08:44). You should hand in your solution (two the second part) in pdf-format. A simple way to obtain a pdf from a notebook is to download it as html, and print the html-page to pdf. Next to this you should also hand in the actual Jupyter notebook. Note: Submit your solutions using blackboard.
  6. Academic honesty: Students have to work independently on the quiz, and in their group for the second part of their homework. You are of course allowed to discuss the material presented in class, homework assignments, or general solution strategies with the teachers or your classmates of other groups, but you have to formulate and write up your solutions without outside help. You must not copy from the internet, your friends, or other textbooks. Problem solving is an important component of this course so it is really in your best interest to try and solve all problems by yourself (in your group). If you represent other people's work as your own then that constitutes fraud and will be dealt with accordingly. If your solution significantly builds upon outside resources, in doubt give credit to those resources.



Other Information



LaTeX

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.


Literature

You don't need to buy any of these books. A copy of each is available in Mariënburg. Both Cormen books are available as e-book in the UvT library. More specifically, the book "Algorithms Unlocked" is available for one student at a time. Please download the separate chapters (will stay), instead of “the whole book” (will disappear). This book is also available as e-book at TU/e. The book "Introduction to Algorithms" has unlimited access. But the same advise for downloading chapters applies. See schedule for relevant book chapters.

book cover

T.H. Cormen.
Algorithms Unlocked
MIT Press, 2013. (Referred to as [C] in schedule.)

book cover

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein.
Introduction to Algorithms (3rd edition)
MIT Press, 2009. (Referred to as [CLRS] in schedule.)

book cover

R.D. Necaise.
Data Structures and Algorithms using Python
Wiley, 2011.
(Don't use without the Errata.)

book cover

M.T. Goodrich, R. Tamassia, M.H. Goldwasser.
Data Structures and Algorithms in Python
Wiley, 2013.

Additional resources:

For additional self-study on algorithms there are several excellent online courses/videos. One of these is the course by Tim Roughgarden.