Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Basic techniques and data structures will be presented in the first half of the course (introduction to algorithms, dynamic programming, search in unordered lists - worst case and average case, search trees, sorting algorithms, lower bound on number of comparisons)

The second half of the course will focus on graph algorithms and geometric algorithms. Among the graph algorithms special emphasis will be given to BFS and its applications (connected components, shortest paths, recognizing bipartite graphs, finding maximum matching in bipartite graphs), DFS and its applications (strongly connected components, directed acyclic graphs, shortest and longest paths in directed acyclic graphs), shortest paths in weighted graphs and minimum spanning trees. The geometry part will include geometric problems in the plane, intersection of line segments, closest pair of points and determining the convex hull of points.

First half-semester – Basic techniques and data structures
1. Introduction to algorithms
    Recursion
    Divide and conquer
    Analyzing algorithms
2. Dynamic programming
    Longest common superstring
    Edit distance of strings
    String matching
3. Graph algorithms
BFS and its applications
    Connected components
    Shortest paths
    Recognizing bipartite graphs
    Finding maximum matching in bipartite graphs
4. DFS and its applications
    Strongly connected components
    Directed acyclic graphs
    Shortest and longest path in directed acyclic graphs
5. Shortest path in weighted graphs
    Bellman-Ford algorithm
    Floyd's algorithm
    Dijkstra's algorithm
6. Minimum spanning trees
    Basic properties
    Greedy algorithms (Jarnik-Prim, Kruskal)

Second half-semester – Graph algorithms and geometric algorithms

7. Search in unordered list: worst case and average case
    Finding the smallest and the largest element in a list
    Finding the median in linear time in ordered list
8. Search trees
    B-tree
    Hashing
9. Sorting algorithms:
    Bubble sort
    Insertion sort
    Merge sort
    Quicksort
10. Lower bound on number of comparisons
    Binsort and radix sort11. Union-find data structure
    Geometric problems in the plane
    Intersection of line segments
12. Closest pair of points
    Determining the convex hull of points

Lectures and recitations

You can reach the instructors at the following e-mail address for consultation:
Katalin FRIEDL: friedl@cs.bme.hu