BME Course

Introduction to Computing 2

Combinatorics, graph theory, matchings, flows, and algorithms — all in one place

Continue Learning Start from Week 1

0/13

Weeks

Topics

Videos

Quizzes

Course Blocks

Block 1

Foundations

0/3 weeks

W1: Permutations, Combinations & Binomial Theorem W2: Graphs, Isomorphism & Connectivity W3: Trees & BFS

Block 2

Graph Structures

0/3 weeks

W4: Euler Circuits & Hamilton Cycles W5: Bipartite Graphs & Coloring W6: Planarity & Euler's Formula

Block 3

Covers & Matchings

0/3 weeks

W7: Covers, Independent Sets & Kruskal W8: Matchings & Hall's Theorem W9: Edge Coloring, König & Max Flow

Block 4

Flows & Algorithms

0/4 weeks

W10: Max Flow-Min Cut & Ford-Fulkerson W11: Vertex & Edge Connectivity W12: Dijkstra & Bellman-Ford W13: DFS & Topological Ordering

Midterm Prep

Real exam questions from zh15–zh24, mapped to topics with key insights and difficulty ratings

All Weeks

Week 1

Permutations, Combinations & Binomial Theorem

This week introduces the fundamental counting principles that underpin combinatorics and discrete mathematics. We cover ordered and unordered selections with and without replacement, **binomial coefficients**, the **Binomial Theorem**, and **Pascal's triangle**. These tools are essential for counting arguments that appear throughout graph theory.

2 topics1 videos1 quiz

Week 2

Graphs, Isomorphism & Connectivity

We formally define **graphs**, their basic properties (degree, subgraphs, complement), and the crucial concept of **graph isomorphism**. The **Handshake Theorem** connects vertex degrees to edge counts. We also introduce **connectivity**, **components**, and **directed graphs** (digraphs).

4 topics1 videos1 quiz

Week 3

Trees & BFS

Trees are the simplest connected graphs — connected with no cycles. We prove their key properties, introduce **spanning trees**, and learn **Breadth-First Search (BFS)** as a systematic way to explore graphs and find shortest paths in unweighted graphs.

2 topics0 videos1 quiz

Week 4

Euler Circuits & Hamilton Cycles

Two classic problems: Can we traverse every **edge** exactly once (Euler)? Can we visit every **vertex** exactly once (Hamilton)? Euler's problem has a complete characterization. Hamilton's problem is much harder — we have sufficient conditions (Dirac, Ore) but no complete characterization.

2 topics0 videos1 quiz

Week 5

Bipartite Graphs & Coloring

We study **bipartite graphs** (no odd cycles) and **graph coloring** — assigning colors to vertices so no two adjacent vertices share a color. The **chromatic number** $\chi(G)$ is the minimum number of colors needed. We connect these to **interval graphs** and the **greedy coloring** algorithm.

3 topics0 videos1 quiz

Week 6

Planarity & Euler's Formula

A graph is **planar** if it can be drawn in the plane without edge crossings. **Euler's formula** $v - e + f = 2$ relates vertices, edges, and faces. We derive edge bounds and learn **Kuratowski's theorem**: a graph is planar iff it has no subdivision of $K_5$ or $K_{3,3}$.

3 topics0 videos1 quiz

Week 7

Covers, Independent Sets & Kruskal

We introduce the four fundamental graph parameters: **vertex cover** $\tau(G)$, **matching number** $\nu(G)$, **independence number** $\alpha(G)$, and **edge cover** $\rho(G)$. **Gallai's theorems** connect these. We also learn **Kruskal's algorithm** for minimum spanning trees.

3 topics0 videos1 quiz

Week 8

Matchings & Hall's Theorem

We dive deep into **matchings** — sets of pairwise non-adjacent edges. The key algorithmic idea is **augmenting paths**: if one exists, the matching isn't maximum. **Hall's theorem** characterizes when a bipartite graph has a perfect matching. **Frobenius' theorem** extends this to general matchings.

2 topics0 videos1 quiz

Week 9

Edge Coloring, König & Max Flow

We study **edge coloring** (the **chromatic index** $\chi'(G)$), **Vizing's theorem**, and **König's theorem** connecting matchings and vertex covers in bipartite graphs. We then introduce **network flows** — the concept of max flow in a directed network.

4 topics0 videos1 quiz

Week 10

Max Flow-Min Cut & Ford-Fulkerson

The **Max Flow-Min Cut theorem** states that the maximum flow equals the minimum cut capacity. The **Ford-Fulkerson algorithm** computes max flow using augmenting paths in the residual graph. We also cover the **Integrality Lemma** and three standard **flow modifications**. This is the last topic covered on the midterm.

3 topics0 videos1 quiz

Week 11

Vertex & Edge Connectivity

We formalize **connectivity** with two measures: **vertex connectivity** $\kappa(G)$ and **edge connectivity** $\lambda(G)$. **Menger's theorem** beautifully connects these to disjoint paths, and **Whitney's inequality** relates $\kappa$, $\lambda$, and $\delta$.

2 topics0 videos1 quiz

Week 12

Dijkstra & Bellman-Ford

We study shortest path algorithms for weighted graphs. **Dijkstra's algorithm** finds shortest paths from a single source in graphs with non-negative weights. **Bellman-Ford** handles negative weights and detects negative cycles.

2 topics0 videos1 quiz

Week 13

DFS & Topological Ordering

We conclude with **Depth-First Search (DFS)** and its applications. DFS discovers the structure of a graph: **back edges** reveal cycles, **DFS timestamps** enable topological ordering of DAGs, and DFS forests reveal connected components.

2 topics0 videos1 quiz

Overall Progress

Progress0%

Start your journey! Click on any week to begin learning.