BME VIK - Algoritmusok és adatstruktúrák

A tantárgy neve magyarul / Name of the subject in Hungarian: Algoritmusok és adatstruktúrák

3. Course coordinator and department Dr. Csima Judit,

Web page of the course www.cs.bme.hu/....

4. Instructors

Name	Position	Department
Katalin FRIEDL	Assoc. professor	Department of Computer Science and Information Theory
Tamás FLEINER	Assoc. professor	Department of Computer Science and Information Theory
Judit CSIMA	Assoc. professor	Department of Computer Science and Information Theory
Ildikó SCHLOTTER	Assistant lecturer	Department of Computer Science and Information Theory
Gábor WIENER	Assoc. professor	Department of Computer Science and Information Theory

5. Required knowledge None

7. Objectives, learning outcomes and obtained knowledge

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.

8. Synopsis

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

9. Method of instruction

Lectures and recitations

10. Assessment The grades will be determined based on homework assignments (50%) and a final exam (50%).

12. Consultations

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

13. References, textbooks and resources T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 2003 or

J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006

14. Required learning hours and assignment

Number of contact hours	56
Preparation to the classes
Preparation to the tests
Homework	34
Assigned reading
Preparation to the exam	30
Total	120

15. Syllabus prepared by

Katalin FRIEDL

Assoc. professor

Department of Computer Science and Information Theory