In this course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible!

By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics.

As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Course 3 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization

### Syllabus

**WEEK 1**

What is a Graph?

What are graphs? What do we need them for? This week we'll see that a graph is a simple pictorial way to represent almost any relations between objects. We'll see that we use graph applications daily! We'll learn what graphs are, when and how to use them, how to draw graphs, and we'll also see the most important graph classes. We start off with two interactive puzzles. While they may be hard, they demonstrate the power of graph theory very well! If you don't find these puzzles easy, please see the videos and reading materials after them.

Graded: Puzzle: Guarini's Puzzle

Graded: Puzzle: Bridges of Königsberg

Graded: Definitions

Graded: Puzzle: Make a Tree

Graded: Graph Types

**WEEK 2**

CYCLES

We’ll consider connected components of a graph and how they can be used to implement a simple program for solving the Guarini puzzle and for proving optimality of a certain protocol. We’ll see how to find a valid ordering of a to-do list or project dependency graph. Finally, we’ll figure out the dramatic difference between seemingly similar Eulerian cycles and Hamiltonian cycles, and we’ll see how they are used in genome assembly!

Graded: Computing the Number of Edges

Graded: Number of Connected Components

Graded: Number of Strongly Connected Components

Graded: Eulerian Cycles

Graded: Puzzle: Hamiltonian Cycle

**WEEK 3**

Graph Classes

This week we will study three main graph classes: trees, bipartite graphs, and planar graphs. We'll define minimum spanning trees, and then develop an algorithm which finds the cheapest way to connect arbitrary cities. We'll study matchings in bipartite graphs, and see when a set of jobs can be filled by applicants. We'll also learn what planar graphs are, and see when subway stations can be connected without intersections. Stay tuned for more interactive puzzles!

Graded: Puzzle: Road Repair

Graded: Trees

Graded: Puzzle: Job Assignment

Graded: Bipartite Graphs

Graded: Puzzle: Subway Lines

Graded: Planar Graphs

**WEEK 4**

Graph Parameters

We'll focus on the graph parameters and related problems. First, we'll define graph colorings, and see why political maps can be colored in just four colors. Then we will see how cliques and independent sets are related in graphs. Using these notions, we'll prove Ramsey Theorem which states that in a large system, complete disorder is impossible! Finally, we'll study vertex covers, and learn how to find the minimum number of computers which control all network connections.

Graded: Puzzle: Map Coloring

Graded: Graph Coloring

Graded: Puzzle: Graph Cliques

Graded: Cliques and Independent Sets

Graded: Puzzle: Balanced Graphs

Graded: Ramsey Numbers

Graded: Puzzle: Antivirus System

Graded: Vertex Covers

**WEEK 5**

Flows and Matchings

This week we'll develop an algorithm that finds the maximum amount of water which can be routed in a given water supply network. This algorithm is also used in practice for optimization of road traffic and airline scheduling. We'll see how flows in networks are related to matchings in bipartite graphs. We'll then develop an algorithm which finds stable matchings in bipartite graphs. This algorithm solves the problem of matching students with schools, doctors with hospitals, and organ donors with patients. By the end of this week, we'll implement an algorithm which won the Nobel Prize in Economics!

Graded: Choose an Augmenting Path Carefully

Graded: Base Cases

Graded: Algorithm