This course is no longer offered

20273 Graph Algorithms 1

Credits: 3 intermediate credits in Computer Science

Prerequisites: none

Required: Introduction to Computer Science Using Java 2

Recommended: Discrete Mathematics3 (or Mathematics for Students of Social Sciences), Probability for Computer Science Students (or Introduction to Statistics and Probability for Science Students), Data Structures and Introduction to Algorithms (or Data Structures)

The course is based on videotaped lectures by Prof. Shimon Even.

The course acquaints students with the basic principles and methods for developing algorithms in graph theory. Criteria for determining algorithm efficiency and for selecting the best-suited algorithmic approach to a given problem are discussed.

Topics: Graphs, paths, Euler circuits, the shortest path problem, minimum spanning tree, depth-first search (DFS), breadth-first search (BFS), network flow, matching.