##### Informationen für

« Zurück

Data Structures and Algorithms (auf Englisch)
Typ: Master-Studiengang Information Technology
Semester: WS 2016/2017
Umfang: 2V+1Ü
Studiengang: InfoTech
Dozent: Prof. Dr.-Ing. Andrés Bruhn
Beschreibung:

This class deals with the design and implementation of the most important algorithms together with their appropriate data structures. In particular, it will provide appropriate solutions to common problems and realize them in terms of a concrete  programming language. The contents of the class include

• Strategies to develop and implement algorithms
• Selection of data structures: lists, trees, graphs, their definitions, their data structures
• Complexity and efficiency of algorithms, Landau notation
• Lists Concepts
(e.g. array, linked lists, doubly-linked lists, queue, stack)
• Tree Concepts
(e.g. binary trees, balanced trees, AVL-trees, 2-3-4 trees, B-trees, heaps, sets)
• Search algorithms
(e.g. linear search, binary search)
• Sorting algorithms
(e.g. selection sort insertion sort, bubble sort, merge sort, quick sort, heap sort)
• Graph algorithms
(e.g. DFS, BFS, topological sorting, minimum spanning trees, shortest path)
• Hashing algorithms
(e.g. internal/external hashing, linear and quadratic probing, rehashing, dynamic hashing)

After attending the class the students should have

• Knowledge of the properties of elementary and frequently used algorithms
• Understanding of the impact of complexity in theory and practice
• Competence in the design and understanding of algorithms and their underlying data structures

This course has programming and mathematics as prerequisites. Every student must be comfortable with the following topics:

• Java 6 programming (and clean coding)
(basic OO programming, inheritance, recursive functions, fundamental data structures)
• Basic mathematics for Computer Science
(random variables, limits, series)

Lectures will be in English. In the section on literature some reference are provided. If you are unsure whether you have the prerequisites, please contact us and we will help you decide whether this course is appropriate for you.

### Literature:

Textbooks:

• Data structures and Algorithm Analysis, Clifford A. Shaffer.
(Available online at: http://goo.gl/ePwnqR)
• Introduction to Algorithms, Thomas H. Cormen - goo.gl/HKCIY

On Java programming:

On mathematics:

NEWS:

• EXERCISE CANCELLED
The exercise on Thursday, January 12th is cancelled.
Exercise Sheet 03 will be discussed on January 19th.

• EXERCISE SHEET 04 CANCELLED
Exercise Sheet 04 will not be issued. Merry Christmas!

• FIRST LECTURE
The first lecture will be on Tuesday, October 25th.

• CAMPUS SYSTEM:
Please rely exclusively on the schedule on this we page.
The schedule in the CAMPUS system might not be correct.

• RULES OF SUBMISSION
There is a sheet with further instructions regarding the submission of your exercise solutions below.

Lecture Notes:

All course material (lecture notes, assignments, code, example solutions) are available in the ILIAS system.

As long as the lecture notes and the assignment sheets cannot be accessed by all students via the ILIAS system, they will as well be provided here. Both, username and password are identical. They correspond to the registration password of the ILIAS system.

Lectures

 • Lecture 00 (25.10.2016) • Lecture 01 X (25.10.2016) X • No Lecture (01.11.2016) Public Holiday (All Saints) • Lecture 02 (08.11.2016) Lists - Sorting I (PowerPoint)(Stack, Queue, Iterators, Collections, Selection Sort, Insertion Sort) • Lecture 03 (15.11.2016) Lists - Sorting II (PowerPoint)(Generics, Bubble Sort, Merge Sort, Quick Sort) • Exercise 00 (17.11.2016) • Lecture 04 (22.11.2016) Complexity (PowerPoint)(Asymptotic Analysis, Landau Notation, Complexity Classes) • Lecture 05 (22.11.2016) Trees - Data Structures (PowerPoint)(Types of Trees, Binarization, Traversal) • Lecture 06 (29.11.2016) Trees - Binary Trees (Power Point)(Traversal with Iterator, Searching, Insertion, Deletion, Balanced Trees) • Exercise 01 (01.12.2016) • Lecture 07 (06.12.2016)(13.12.2016) Trees - Balanced Trees(AVL Trees, 2-3-4-Trees, B-Trees, Searching, Insertion, Deletion) • Lecture 08 (13.12.2016)(20.12.2016) Trees - Tries, Heaps, Sets(Tries, Patricia Trees, Prefix Trees, Heaps, Sets, Heap Sport) • Exercise 02 (15.12.2016) • No Lecture (27.12.2016) Christmas Holidays • No Lecture (29.12.2016) Christmas Holidays • No Lecture (03.01.2017) Christmas Holidays • No Lecture (05.01.2017) Christmas Holidays • Lecture 09 (20.12.2016)(10.01.2017) Graphs - Data Structures(Graph Types, Edge List, Node List, Adjacency Matrix, Adjacency List) • No Exercise (12.01.2017) cancelled • Lecture 10 (17.01.2017) Graphs - Algorithms I(Breadth First Search, Depth First Search, Topological Sorting, Shortest Path: Dijkstra's Algorithm, Bellman-Ford Algorithm) • Exercise 03 (19.01.2017) • Lecture 11 (24.01.2017)(31.01.2017) Graphs - Graph Algorithms II(Minimum Spanning Tree: Kruskal's Algorithm, Max Flow: Ford-Fulkerson Algorithm) • Exercise 05 (02.02.2017) • Lecture 12 (07.02.2017) Hashing(Hash Functions, Collision Resolution, Open/Closed Hashing, Rehashing, Dynamic Hashing) • Exercise 06 (09.02.2017)

Assignments

Rules of submission

 X • Exercise 00 X (issued 25.10.2016, submission 10.11.2016) Sheet Source • Exercise 01 (issued 15.11.2016, submission 24.11.2016) Sheet Source • Exercise 02 (issued 29.11.2016, submission 08.12.2016) • Exercise 03 (issued 13.12.2016, submission 05.01.2017) • Exercise 04 (issued 20.12.2017, submission 12.01.2017) cancelled • Exercise 05 (issued 17.01.2017, submission 26.01.2017) • Exercise 06 (issued 24.01.2017, submission 02.02.2017)

Self Test Problem

 X • Assignment Sheet X (issued before exam)

REMARKS:

• t.b.a.

## Link to the CAMPUS Online Portal:(schedule might not be correct)

Bilder:
Internet-Seite:
Termine: Dienstag, 14:00 - 15:30 Uhr in V38.03
Übungen: Donnerstag, 14:00 - 15:30 Uhr (14-tägig) in V38.02
Tutor: Prof. Dr.-Ing. Andrés Bruhn
Michael Stoll M.Sc. M.Sc. B.Sc.

« Zurück