Algorithms and Data Structures
 

Instructor


Organisation

  • Please note that this is not a course page any longer but a page that can be used for preparation purposes!

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

  • Week 1: 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)
  • Week 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)
  • Week 3: Advanced Design Techniques
    • Dynamic Programming (Chapters 15.1, 15.3, and 15.4)
    • Greedy Algorithms (Chapters 16.1-2)
  • Week 4: Data Structures
    • Elementary Data Structures (Chapters 10.1 and 10.2)
    • Hash Tables (Chapters 11.1-4)
    • Binary Search Trees (Chapters 12.1)
  • Week 5: 
    • 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