# 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

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

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.

 T.H. Cormen. Algorithms Unlocked MIT Press, 2013. (Referred to as [C] in schedule.) 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.) R.D. Necaise. Wiley, 2011. (Don't use without the Errata.) M.T. Goodrich, R. Tamassia, M.H. Goldwasser. Data Structures and Algorithms in Python Wiley, 2013.