This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization

4.5
stars
911 ratings

Alexander S. Kulikov

45,065 already enrolled

Offered By

Introduction to Discrete Mathematics for Computer Science SpecializationUniversity of California San Diego

About this Course

66,232 recent views

We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. 
In this online 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.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Course 3 of 5 in the

Introduction to Discrete Mathematics for Computer Science Specialization

Beginner Level

Approx. 20 hours to complete

English

Flexible deadlines

Reset deadlines in accordance to your schedule.

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Course 3 of 5 in the

Introduction to Discrete Mathematics for Computer Science Specialization

Beginner Level

Approx. 20 hours to complete

English

Instructor

Instructor rating

4.19/5 (128 Ratings)

Alexander S. Kulikov

Professor

Department of Mathematics and Computer Science

707,439 Learners

13 Courses

Offered by

University of California San Diego

Syllabus - What you will learn from this course

Content Rating88%(5,516 ratings)

Week1

Week 1

3 hours to complete

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.

3 hours to complete

14 videos (Total 52 min), 6 readings, 5 quizzes

14 videos

Airlines Graph1mKnight Transposition2mSeven Bridges of Königsberg4mWhat is a Graph?7mGraph Examples2mGraph Applications3mVertex Degree3mPaths5mConnectivity2mDirected Graphs3mWeighted Graphs2mPaths, Cycles and Complete Graphs2mTrees6mBipartite Graphs4m

6 readings

Slides1mSlides1mSlides1mSlides1mGlossary10mHint for Guarini's Puzzle10m

5 practice exercises

Puzzle: Guarini's Puzzle30mPuzzle: Bridges of Königsberg30mDefinitions10mPuzzle: Make a tree30mGraph Types10m

Week2

Week 2

6 hours to complete

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!

6 hours to complete

12 videos (Total 89 min), 4 readings, 7 quizzes

12 videos

Handshaking Lemma7mTotal Degree5mConnected Components7mGuarini Puzzle: Code6mLower Bound5mThe Heaviest Stone6mDirected Acyclic Graphs10mStrongly Connected Components7mEulerian Cycles4mEulerian Cycles: Criteria11mHamiltonian Cycles4mGenome Assembly12m

4 readings

Slides1mSlides1mSlides1mGlossary10m

7 practice exercises

Puzzle: Connect Points by Segments30mComputing the Number of Edges10mNumber of Connected Components10mNumber of Strongly Connected Components10mEulerian Cycles30mPuzzle: Plow Truck30mPuzzle: Hamiltonian Cycle30m

Week3

Week 3

3 hours to complete

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!

3 hours to complete

11 videos (Total 55 min), 4 readings, 6 quizzes

Week4

Week 4

4 hours to complete

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.

4 hours to complete

14 videos (Total 52 min), 5 readings, 8 quizzes

14 videos

Map Coloring3mGraph Coloring3mBounds on the Chromatic Number3mApplications3mGraph Cliques3mCliques and Independent Sets3mConnections to Coloring1mMantel's Theorem5mBalanced Graphs2mRamsey Numbers2mExistence of Ramsey Numbers5mAntivirus System2mVertex Covers3mKönig's Theorem8m

5 readings

Slides1mSlides1mSlides1mSlides1mGlossary10m

8 practice exercises

Puzzle: Map Coloring30mGraph Coloring10mPuzzle: Graph Cliques30mCliques and Independent Sets10mPuzzle: Balanced Graphs30mRamsey Numbers10mPuzzle: Antivirus System30mVertex Covers10m

Reviews

4.5

205 reviews

5 stars
66.52%
4 stars
23.16%
3 stars
6.91%
2 stars
2.19%
1 star
1.20%

TOP REVIEWS FROM INTRODUCTION TO GRAPH THEORY

by AAMay 2, 2019

Very friendly and applied course.

A well-balanced approach, even layman can understand the concept with exceptional ease.

by ATNov 24, 2017

This course is really good. If someone has interest in graph theory or he wants to learn it, then this course is definitely a good start.

by YZDec 31, 2017

This course is interesting, and it is a good introduction. I like the first four weeks' courses, while I feel the last week's course is not clear presented, which changes the instructor.

by PMMay 22, 2020

This course introduces us to a broad range of topics in graph theory. A number of classical problems were solved in graph theory were explained.

View all reviews

About the Introduction to Discrete Mathematics for Computer Science Specialization

Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun try-this-before-we-explain-everything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to IT-applications, we incorporate programming examples, problems, and projects in the specialization.

Frequently Asked Questions

When will I have access to the lectures and assignments?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
What will I get if I subscribe to this Specialization?
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
Is financial aid available?
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

More questions? Visit the Learner Help Center.

Introduction to Graph Theory

About this Course