Algorithms and Data Structures FSS12
 

Lectures

 

Please join the ILIAS page of the class!

 Lecture:

  • Instructor: Mathias Niepert
  • Time and date: Wednesdays 15:30-17:00 (first lecture will be on Fabruary 15th)
  • Place: B6, A3.02

    Note: You are required to register for the class through the "Studierendenportal"!

 Recitation:

  • Instructor: Marina Maznikova
  • Time and date: Tuesdays 13:45-15:00
  • Place: B6, A2.06

Organisation

The class will provide a comprehensive introduction to the modern study of computer algorithms tailored to the needs of business informatics students. The class is for international students who have to pass the "Algorithms and Data Structures" requirement.

Textbook: Introduction to Algorithms (Third Edition) Cormen, Leiserson, Rivest, Stein; The Mit Press. (The second edition works as well.)


Practice Problems


Practice Exam

The practice exam


Agenda

Please note that the covered material consists of the book chapters and the class notes. If you were unable to attend class you have to obtain the notes from a fellow student.

  • Foundations and Sorting Algorithms
    • Getting started (chapter 1)
    • Insertion sort, Divide and Conquer, Merge sort (Chapter 2)
    • Growth of Functions (Chapter 3; only worst-case analysis)
    • Quicksort (Chapter 7.1 and 7.2)
  • Algorithms on Graphs
    • Elementary Graph Algorithms (Chapters 22.1-3, 22.5)
    • Minimum Spanning Trees (Chapter 23)
    • Singe-Source Shortest Path (Chapters 24.1-3)
    • Maximum Flow (Chapters 26.1-2)
  • Advanced Design Techniques
    • Dynamic Programming (Chapters 15.1, 15.3, and 15.4)
    • Greedy Algorithms (Chapters 16.1-2)
  • Data Structures
    • Elementary Data Structures (Chapters 10.1 and 10.2)
    • Hash Tables (Chapters 11.1-4)
    • Binary Search Trees (Chapters 12.1)
  • Advanced Topics/Practice
    • Binary Search Trees (Chapters 12.2 and Chapter 12.3)
    • Dynamic Programming Exercises
    • Greedy Algorithm Exercises
    • Exam preparation

Topics

  • Mathematical Foundations
    • Growth and Functions
    • Recurrence
    • Graphs & Trees
  • Sorting Algorithms
    • Heapsort
    • Mergesort
    • Quicksort
  • Elementary Data Structure
    • Hash tables
    • Binary search trees
  • Elementary Problem Solving Strategies
    • Divide and Conquer
    • Dynamic Programming
    • Greedy Algorithms

  • Algorithms on Sets

  • Algorithms on Graphs
    • Minnimum Spanning Tree
    • Single-Source Shortest Paths
    • Maximum Flow

  • Advances Algorithms (if time permits)
  • Matrix Operations
  • String Matching
  • Linear Programming