Programming & Computer Science
Algorithmic Thinking
Design an algorithm step by step: schedule meetings, describe a strategy, test it, find counterexamples, and prove when a greedy choice is the best one.
THE SYLLABUS
I
0 / 7
▶
The Scheduling Problem
Build schedules for a music room by hand: no two accepted bookings may overlap, and each schedule must also meet its own criteria - how many to accept, how many to leave out, a closing time, or as many as possible.
Start
🔒
Solving Instances
A problem is its criteria; an instance is one particular set of requests. Solve instances of the scheduling problem for a pottery wheel, and pick out instances whose solutions accept 3, 1, 2 or all of the requests.
Premium
🔒
Describing Algorithms
Describe a method that solves any instance: take the telescope bookings one by one in the order they were requested, accept each one that conflicts with nothing accepted so far - a greedy algorithm - and write it as code.
Premium
🔒
Multiple Solutions
One instance can have several solutions: count them for the ferry dock, then trace which single one the greedy algorithm finds when it takes the bookings in the order they were requested.
Premium
🔒
Identifying Invariants
Tracing a few instances proves nothing; logic does. Find the invariants of the greedy loop - the accepted bookings never conflict, and every rejected booking conflicts with an accepted one - and the lines that keep them true.
Premium
🔒
Finding Counterexamples
One instance where a claim fails is enough to disprove it: find counterexamples showing the greedy schedule for the climbing wall doesn't always accept the most bookings, the shortest one, the most time or the earliest start.
Premium
🔒
Level Review
Nine questions on the scheduling problem: valid schedules built by hand, the greedy algorithm written and traced, instances with several solutions, the loop's invariant, and counterexamples.
Premium