Über diesen Kurs
4.6
226 Bewertungen
49 Bewertungen

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Stufe „Anfänger“

Ca. 15 Stunden zum Abschließen

Empfohlen: 5 weeks, 3-5 hours/week ...

Englisch

Untertitel: Englisch

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Stufe „Anfänger“

Ca. 15 Stunden zum Abschließen

Empfohlen: 5 weeks, 3-5 hours/week ...

Englisch

Untertitel: Englisch

Lehrplan - Was Sie in diesem Kurs lernen werden

Woche
1
3 Stunden zum Abschließen

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....
14 Videos (Gesamt 52 min), 5 Lektüren, 5 Quiz
14 Videos
Knight Transposition2m
Seven Bridges of Königsberg4m
What is a Graph?7m
Graph Examples2m
Graph Applications3m
Vertex Degree3m
Paths5m
Connectivity2m
Directed Graphs3m
Weighted Graphs2m
Paths, Cycles and Complete Graphs2m
Trees6m
Bipartite Graphs4m
5 Lektüren
Slides1m
Slides1m
Slides1m
Slides1m
Glossary10m
2 praktische Übungen
Definitions10m
Graph Types10m
Woche
2
5 Stunden zum Abschließen

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! ...
12 Videos (Gesamt 89 min), 4 Lektüren, 6 Quiz
12 Videos
Total Degree5m
Connected Components7m
Guarini Puzzle: Code6m
Lower Bound5m
The Heaviest Stone6m
Directed Acyclic Graphs10m
Strongly Connected Components7m
Eulerian Cycles4m
Eulerian Cycles: Criteria11m
Hamiltonian Cycles4m
Genome Assembly12m
4 Lektüren
Slides1m
Slides1m
Slides1m
Glossary10m
4 praktische Übungen
Computing the Number of Edges10m
Number of Connected Components10m
Number of Strongly Connected Components10m
Eulerian Cycles2m
Woche
3
3 Stunden zum Abschließen

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!...
11 Videos (Gesamt 55 min), 4 Lektüren, 6 Quiz
11 Videos
Trees8m
Minimum Spanning Tree6m
Job Assignment3m
Bipartite Graphs5m
Matchings3m
Hall's Theorem7m
Subway Lines1m
Planar Graphs3m
Euler's Formula4m
Applications of Euler's Formula7m
4 Lektüren
Slides1m
Slides1m
Slides1m
Glossary10m
3 praktische Übungen
Trees10m
Bipartite Graphs10m
Planar Graphs10m
Woche
4
4 Stunden zum Abschließen

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....
14 Videos (Gesamt 52 min), 5 Lektüren, 8 Quiz
14 Videos
Graph Coloring3m
Bounds on the Chromatic Number3m
Applications3m
Graph Cliques3m
Cliques and Independent Sets3m
Connections to Coloring1m
Mantel's Theorem5m
Balanced Graphs2m
Ramsey Numbers2m
Existence of Ramsey Numbers5m
Antivirus System2m
Vertex Covers3m
König's Theorem8m
5 Lektüren
Slides1m
Slides1m
Slides1m
Slides1m
Glossary10m
4 praktische Übungen
Graph Coloring10m
Cliques and Independent Sets10m
Ramsey Numbers10m
Vertex Covers10m
Woche
5
4 Stunden zum Abschließen

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!...
13 Videos (Gesamt 99 min), 6 Lektüren, 4 Quiz
13 Videos
The Framework8m
Ford and Fulkerson: Proof11m
Hall's theorem10m
What Else?8m
Why Stable Matchings?6m
Mathematics and Real Life4m
Basic Examples6m
Looking For a Stable Matching6m
Gale-Shapley Algorithm6m
Correctness Proof6m
Why The Algorithm Is Unfair7m
Why the Algorithm is Very Unfair9m
6 Lektüren
Slides1m
Slides1m
The algorithm and its properties (alternative exposition)10m
Gale-Shapley Algorithm2m
Project Description10m
Glossary10m
4 praktische Übungen
Choose an Augmenting Path Carefully20m
Constant Degree Bipartite Graphs30m
Base Cases10m
Algorithm
4.6
49 BewertungenChevron Right

33%

nahm einen neuen Beruf nach Abschluss dieser Kurse auf

50%

ziehen Sie für Ihren Beruf greifbaren Nutzen aus diesem Kurs

33%

erhalten Sie eine Gehaltserhöhung oder Beförderung

Top-Bewertungen

von SUFeb 28th 2019

Appreciate the structure and the explanations with examples. The practice tool before every lesson not makes it fun to learn but also sets the student in the context and can anticipate the concept.

von RHNov 17th 2017

Was pretty fun and gave a good intro to graph theory. Definitely felt inspired to go deeper and understood the most basic proof ideas. The later lectures can spike in difficulty though. Very nice!

Dozent

Avatar

Alexander S. Kulikov

Visiting Professor
Department of Computer Science and Engineering

Über University of California San Diego

UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory....

Über National Research University Higher School of Economics

National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communicamathematics, engineering, and more. Learn more on www.hse.ru...

Über die Spezialisierung Introduction to Discrete Mathematics for Computer Science

Discrete Math is needed to see mathematical structures in the object you work with, and understand their properties. This ability is important for software engineers, data scientists, security and financial analysts (it is not a coincidence that math puzzles are often used for interviews). We cover the basic notions and results (combinatorics, graphs, probability, number theory) that are universally needed. To deliver techniques and ideas in discrete mathematics to the learner we extensively use interactive puzzles specially created for this specialization. To bring the learners experience closer to IT-applications we incorporate programming examples, problems and projects in our courses....
Introduction to Discrete Mathematics for Computer Science

Häufig gestellte Fragen

  • Sobald Sie sich für ein Zertifikat angemeldet haben, haben Sie Zugriff auf alle Videos, Quizspiele und Programmieraufgaben (falls zutreffend). Aufgaben, die von anderen Kursteilnehmern bewertet werden, können erst dann eingereicht und überprüft werden, wenn Ihr Unterricht begonnen hat. Wenn Sie sich den Kurs anschauen möchten, ohne ihn zu kaufen, können Sie womöglich auf bestimmte Aufgaben nicht zugreifen.

  • Wenn Sie sich für den Kurs anmelden, erhalten Sie Zugriff auf alle Kurse der Spezialisierung und Sie erhalten nach Abschluss aller Arbeiten ein Zertifikat. Ihr elektronisches Zertifikat wird zu Ihrer Seite „Errungenschaften“ hinzugefügt – von dort können Sie Ihr Zertifikat ausdrucken oder es zu Ihrem LinkedIn Profil hinzufügen. Wenn Sie nur lesen und den Inhalt des Kurses anzeigen möchten, können Sie kostenlos als Gast an dem Kurs teilnehmen.

Haben Sie weitere Fragen? Besuchen Sie das Hilfe-Center für Teiln..