Informationen für
Logo VIS

« Zurück

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

  • NO LECTURE
    On January 20th, there will be no lecture.
  • COURSE MANAGEMENT VIA ILIAS SYSTEM
    The course will be managed via the ILIAS system. Lecture notes and important information can be found there. The current web-page will only be used for backup purposes.
  • FIRST LECTURE
    The first lecture will be on Tuesday, October 21th.

 

 

Lecture Notes:

  • Lecture 00   (21.10.2014)   Introduction (PowerPoint)
  • Lecture 01 X (21.10.2014) X Lists - Searching (PowerPoint)
  • Lecture 02   (28.10.2014)   Lists - Sorting I (PowerPoint)
(Stack, Queue, Iterators, Collections, Selection Sort, Insertion Sort)
  • Lecture 03   (04.11.2014)   Lists - Sorting II (PowerPoint)
(Generics, Bubble Sort, Merge Sort, Quick Sort)
  • Exercise 00
  (06.11.2014)    
  • Lecture 04   (11.11.2014)  

Complexity (PowerPoint)
(Asymptotic Analysis, Landau Notation, Complexitly Classes)

  • Lecture 05   (11.11.2014)   Trees - Data Structures (PowerPoint)
(Types of Trees, Binarization, Traversal, Insertion, Deletion)
  • Lecture 06   (18.11.2014)   Trees - Binary Trees (PowerPoint)
(Traversal with Iterator, Searching, Insertion, Deletion, Balanced Trees)
  • Exercise 01
  (20.11.2014)    
  • Lecture 07   (25.11.2014)
(02.12.2014)
  Trees - Balanced Trees (PowerPoint)
(AVL Trees, 2-3-4-Trees, B-Trees, Searching, Insertion, Deletion)
  • Lecture 08  

(02.12.2014)
(09.12.2014)

  Trees - Tries, Heaps, Sets (PowerPoint)
(Tries, Patricia Trees, Prefix Trees, Heaps, Sets, Heap Sport)
  • Exercise 02
  (04.12.2014)    
  • Lecture 09   (09.12.2014)
(16.12.2014)
  Graphs - Data Structures (PowerPoint)
(Graph Types, Edge List, Node List, Adjacency Matrix, Adjacency List)
  • Exercise 03
  (18.12.2014)    
  • Lecture 10
 

(13.01.2015)

  Graphs - Algorithms I (PowerPoint)
(Breadth First Search, Depth First Search, Topological Sorting,
Shortest Path: Dijkstra's Algorithm, Bellman-Ford Algorithm)
  • Exercise 04
  (15.01.2015)    
  • Lecture 12   (20.01.2015)   No lecture
  • Lecture 11   (27.01.2015)
(03.02.2015)
  Graphs - Graph Algorithms II (PowerPoint)
(Minimum Spanning Tree: Kruskal's Algorithm,
Max Flow: Ford-Fulkerson Algorithm)
  • Exercise 05
  (29.01.2015)    
  • Lecture 12   (03.02.2015)   Hashing (PowerPoint)
(Hash Functions, Collision Resolution, Open/Closed Hashing,
Rehashing, Dynamic Hashing)
  • Exercise 06
  (12.02.2015)    

 


 

Assignments:

Files for the Programming Assignments

X • Assignment 00 X (issued 21.10.2014, submission 30.10.2014) X  
  • Assignment 01   (issued 04.11.2014, submission 13.11.2014)    
  • Assignment 02
  (issued 18.11.2014, submission 27.11.2014)    
  Assignment 03   (issued 02.12.2014, submission 11.12.2014)    
  Assignment 04   (issued 16.12.2014, submission 08.01.2015)    
  Assignment 05   (issued 13.01.2015, submission 22.01.2015)    
  Assignment 06   (issued 27.01.2015, submission 05.02.2015)    

 

Solutions

X • Assignment 00 X (issued 06.11.2014) X  
  • Assignment 01   (issued 20.11.2014)    
  • Assignment 02
  (issued 04.12.2014)    
  Assignment 03   (issued 18.12.2014)    
  Assignment 04   (issued 15.01.2015)    
  Assignment 05   (issued 29.01.2015)    
  Assignment 06   (issued 12.02.2015)    

 

Self Test Problem:

       

 

 

 

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