# Data Structures and Algorithms (archived version)

The course page is now on canvas. Some materials from previous iterations (-2018) of course can be found below.

### Course Information

Instructor: Kevin Buchin, k.a.buchin@tue.nl
Please use the tag [JBP030] 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 intertwine lectures and solving and discussing exercises. These take place Tuesdays 13:45-17:30 in MDB 0.30.

### Schedule

 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

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. Assignment 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.
2. Homework 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.
3. Assignments are due before the lecture starts (13:44). You should hand in your solution 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. In case of a Jupyter Notebook also hand in the actual notebook. Note: Submit your solutions using blackboard.

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