Informationen für
Logo VIS

« Zurück

Data Structures and Algorithms (auf Englisch)
Typ: Master-Studiengang Information Technology
Semester: WS 2015/2016
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:

  • RULES OF SUBMISSION
    There is a sheet with further instructions regarding the submission of your exercise solutions below.
  • NO LECTURES
    On December 22nd and January 7th, there will be no lecture.
  • FIRST LECTURE
    The first lecture will be on Tuesday, October 20th.

 

 

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   (20.10.2015)   Introduction (PowerPoint)
  • Lecture 01 X (20.10.2015) X Lists - Searching (PowerPoint)
  • Lecture 02   (27.10.2015)   Lists - Sorting I (PowerPoint)
(Stack, Queue, Iterators, Collections, Selection Sort, Insertion Sort)
  • Lecture 03   (03.11.2015)   Lists - Sorting II (PowerPoint)
(Generics, Bubble Sort, Merge Sort, Quick Sort)
  • Exercise 00
  (05.11.2015)    
  • Lecture 04   (10.11.2015)   Complexity (PowerPoint)
(Asymptotic Analysis, Landau Notation, Complexity Classes)
  • Lecture 05   (10.11.2015)   Trees - Data Structures (PowerPoint)
(Types of Trees, Binarization, Traversal)
  • Lecture 06   (17.11.2015)   Trees - Binary Trees (Power Point)
(Traversal with Iterator, Searching, Insertion, Deletion, Balanced Trees)
  • Exercise 01
  (19.11.2015)    
  • Lecture 07   (24.11.2015)
(01.12.2015)
  Trees - Balanced Trees
(AVL Trees, 2-3-4-Trees, B-Trees, Searching, Insertion, Deletion)
  • Lecture 08  

(01.12.2015)
(08.12.2015)

  Trees - Tries, Heaps, Sets
(Tries, Patricia Trees, Prefix Trees, Heaps, Sets, Heap Sport)
  • Exercise 02
  (03.12.2015)    
  • Lecture 09   (08.12.2015)
(15.12.2015)
  Graphs - Data Structures
(Graph Types, Edge List, Node List, Adjacency Matrix, Adjacency List)
  • Exercise 03
  (17.12.2015)    
  • No Lecture   (22.12.2015)   cancelled
  • No Lecture   (24.12.2015)   Christmas Holidays
  • No Lecture   (29.12.2015)   Christmas Holidays
  • No Lecture   (31.12.2015)   Christmas Holidays
  • No Lecture   (05.01.2016)   Christmas Holidays
  • No Lecture   (07.01.2016)   cancelled
  • Lecture 10
 

(12.01.2016)

  Graphs - Algorithms I
(Breadth First Search, Depth First Search, Topological Sorting,
Shortest Path: Dijkstra's Algorithm, Bellman-Ford Algorithm)
  • Exercise 04
  (14.01.2016)    
  • Lecture 11   (19.01.2016)
(26.01.2016)
  Graphs - Graph Algorithms II
(Minimum Spanning Tree: Kruskal's Algorithm,
Max Flow: Ford-Fulkerson Algorithm)
  • Exercise 05
  (28.01.2016)    
  • Lecture 12   (02.02.2016)   Hashing
(Hash Functions, Collision Resolution, Open/Closed Hashing,
Rehashing, Dynamic Hashing)
  • Exercise 06
  (04.02.2016)    

 

Assignments

Rules of submission

X • Assignment 00 X (issued 20.10.2015, submission 29.10.2015)  

Assignment Sheet, Programming Source

Example Solution

  • Assignment 01   (issued 03.11.2015, submission 12.11.2015)   Assignment Sheet, Programming Source
  • Assignment 02
  (issued 17.11.2015, submission 26.11.2015)    
  Assignment 03   (issued 01.12.2015, submission 10.12.2015)    
  Assignment 04   (issued 15.12.2015, submission 07.01.2016)    
  Assignment 05   (issued 12.01.2016, submission 21.01.2016)    
  Assignment 06   (issued 21.01.2016, submission 28.01.2016)    

 

Self Test Problem

X • Assignment Sheet X (issued before exam)

 

 

REMARKS:

  • t.b.a.

 


Link zum LSF Online Portal:

Data Struture and Algorithms

Exercises Data Structures and Algorithms

 


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