AA / course home

Week 01 · Lecture 1

Algorithms and correctness

Specify the answer, trace a method, and challenge a tempting rule. Robot tours and interval scheduling show why correctness needs an argument.

Can a locally attractive choice give a globally bad answer?

Jobs A=[0,3], B=[2,4], C=[3,5]. Choose the largest compatible set; touching endpoints are allowed.

ABC012345
Compatible intervals A and C touch at time 3; B overlaps both.
Step 1

Sort by finish time: A, B, C.

Step 2

Accept A, ending at 3. Reject B because it starts at 2.

Step 3

Accept C because it starts at 3. Result: two jobs.

Step 4

The earliest finish leaves at least as much room as any competing first choice. Repeating this exchange establishes optimality for equal-value fixed intervals.

Change the case. If jobs have different fees, maximising their count may not maximise income. We return to this distinction in dynamic programming.

Explore the animations

Each demonstration states its own input and code. Check its loop bounds before comparing counts with the worked example.

Story 1 · The robot tour

A soldering robot must visit every point and return home. The goal is the shortest total distance, not the shortest next move. Choose a case, then step through the decisions.

What each rule does. Nearest neighbour moves from the robot’s current point. Closest pair builds connections anywhere, while preventing branches and early loops. Exhaustive search evaluates every visit order.

Why 64 is optimal on the line. The extremes are −21 and 11, a span of 32. A closed tour must cover that span in both directions: at least 2 × 32 = 64. The order 0 → −1 → −5 → −21 → 1 → 3 → 11 → 0 achieves it.

Correct can still be expensive. Testing all n! orders gives 3,628,800 for n = 10 and approximately 2.43 × 1018 for n = 20. Fixing the start removes duplicate rotations, but the remaining factorial growth is still severe. These counts describe this exhaustive method; they are not a proof that every exact algorithm must test every ordering.

Questions and answers are together. Hard questions are optional; some tests revisit earlier ideas.

Practice with answers

10 test questions · 9 written questions · 19 total

Each question is followed by its answer and explanation. Hard questions also include a starting hint and smaller reasoning steps.

Test questions

Choose one option. Cost questions state their model and whether the bound is tight, expected or worst-case. Here lg means log₂, and heap positions start at 1.

Question 1 · easy

For a problem that requires a terminating answer on every legal input, an algorithm is best described as:

  1. a program written in a particular language
  2. a precise, finite procedure that returns the required answer on every legal input
  3. any computation that eventually stops
  4. a rule that works on most inputs

Answer: option B. The idea is independent of the language, and it must handle every legal instance.

Question 2 · easy

A sorting algorithm counts as correct only if it also handles:

  1. random inputs only
  2. inputs with no repeated values only
  3. already-sorted inputs and inputs with repeated values
  4. inputs of at most 1,000 items

Answer: option C. Every legal instance, including the awkward ones, must give the right output.

Question 3 · easy

The nearest-neighbour rule for the robot tour is:

  1. always optimal
  2. a heuristic that can be far from optimal
  3. exponential in running time
  4. undefined when points tie

Answer: option B. It is a heuristic: a plausible rule with no general optimality guarantee. With the stated tie rule in written source exercise 4, its closed tour has length 84, while a tour of length 64 exists.

Question 4 · easy

For fixed-time jobs of equal value, choose as many nonoverlapping jobs as possible (a job may start when another finishes). Which greedy rule is optimal?

  1. earliest start first
  2. shortest job first
  3. earliest finish first
  4. longest job first

Answer: option C. Taking the job that finishes soonest frees the most time afterwards.

Question 5 · easy · course question

Why can one counterexample refute a claim of correctness?

  1. The claim concerns every legal input.
  2. It tests every input.
  3. It proves all alternatives correct.
  4. It measures the worst running time.

Answer: option A. A universal claim fails if even one legal instance produces an incorrect result.

Question 6 · easy · course question

Before comparing two algorithms, what must agree?

  1. Their programming language.
  2. Their input and required-output contract.
  3. Their variable names.
  4. Their measured runtime.

Answer: option B. Two methods may be compared as solutions only if they solve the same specified problem.

Question 7 · easy · course question

For equal-value fixed intervals, earliest-finish scheduling leaves what advantage?

  1. The most remaining time for compatible jobs.
  2. The highest guaranteed income for weighted jobs.
  3. The fewest jobs.
  4. The longest first job.

Answer: option A. Choosing a first job that finishes no later than another feasible first job cannot reduce the remaining scheduling window.

Question 8 · easy · course question

Many successful tests establish which conclusion?

  1. Correctness for every input.
  2. Evidence on the tested instances.
  3. A proof of optimality.
  4. Constant running time.

Answer: option B. Testing checks particular instances. A universal claim needs an argument covering every legal case.

Question 9 · easy · course question

Which is a precise tour objective?

  1. Find the nicest tour.
  2. Find the most sensible tour.
  3. Minimise total distance while visiting all specified points and returning to the start.
  4. Use an elegant method.

Answer: option C. The objective and legal routes must be defined before optimality has a meaning.

Question 10 · hard · optional challenge

A robot must visit points at −10, −3, 0, 4 and 9 on a line, starting and ending at 0. The length of the shortest closed tour is:

  1. 19
  2. 26
  3. 38
  4. 45

In simpler words: Find the full left-to-right spread and count a return trip.

Starting hint: A closed route must cross the spread in both directions.

Answer: option C. Any closed tour must travel from the leftmost to the rightmost point and back, so 2 × (9 − (−10)) = 38, and walking left then right achieves it.

Step by step
  1. The spread is 9−(−10)=19.
  2. The lower bound is 2·19=38. Route 0→−10→9→0 reaches it.

Written questions

Read each question together with its explanation, trace or proof. Numbering continues from the test questions.

Question 11 · easy

What are the two things we demand of every algorithm, and what does each one mean?

Answer & reasoning

correctness (it gives the required output on every legal instance) and efficiency (its running time grows slowly enough with the input size to be usable on large inputs).

Question 12 · easy

State the sorting problem precisely, as an input and a required output.

Answer & reasoning

input, a sequence of n numbers a₁, …, aₙ; output, a rearrangement of the same numbers so that a₁ ≤ a₂ ≤ … ≤ aₙ.

Question 13 · easy

Why can there be a provably correct algorithm for “find the shortest tour” but not for “find the best tour”?

Answer & reasoning

“Shortest” supplies an objective: minimise total length among legal tours. That lets us state and prove a correctness claim. “Best” needs a defined objective first. Checking a tour’s length is easy; proving that no shorter tour exists is a different and potentially difficult task.

Question 14 · easy

Use nearest neighbour from 0 and, at a distance tie, choose the smaller absolute coordinate. The points are −21, −5, −1, 0, 1, 3, 11. At the initial tie choose +1. Trace the tour, find its length, and compare it with the shortest closed tour.

Answer & reasoning

The specified ties give 0 → 1 → −1 → 3 → −5 → 11 → −21 → 0. Length: 1 + 2 + 4 + 8 + 16 + 32 + 21 = 84. A monotone sweep from one extreme to the other and back has length 2 × (11 − (−21)) = 64. The sweep visits intermediate points on the way. A nearest-neighbour trace needs a tie rule; this is a counterexample for the stated rule.

Question 15 · easy

For fixed-time jobs with equal value, maximise the number of nonoverlapping jobs (adjacent jobs may share a finish/start boundary). Which rule is optimal: earliest start, shortest job, or earliest finish?

Answer & reasoning

earliest finish first, repeatedly accepting the job that ends soonest and discarding whatever overlaps it.

Question 16 · easy

Name the three parts of a proof by induction.

Answer & reasoning

the base case (it holds for the smallest size), the assumption or induction hypothesis (it holds for sizes up to n − 1), and the general case (using the assumption, it holds for size n).

Question 17 · medium

Build a three-job instance where “shortest job first” accepts only one job although two compatible jobs exist.

Answer & reasoning

A = [1, 5], B = [4, 6], C = [5.5, 9]. B is shortest (length 2) but overlaps both A and C, so the rule takes B alone; A and C do not overlap each other, so two jobs were possible.

Question 18 · hard · optional challenge

The robot starts at one of n points on a line and visits any point it passes. Prove that the shortest closed route has length 2 × (rightmost − leftmost), and find that route description in O(n).

In simpler words: Find the least travel needed to visit both ends of a line and return.

Starting hint: Draw the two extreme points. A closed trip has to cross their separation in both directions.

Answer & reasoning
Step by step
  1. Let L be the leftmost point, R the rightmost, and S the start, with L ≤ S ≤ R.
  2. Any closed trip includes a part from L to R and another from R to L. Each part costs at least R − L.
  3. The route S → L → R → S costs (S−L)+(R−L)+(R−S)=2(R−L). One scan finds L and R.

Any closed route reaching both extremes contains a journey from the left extreme to the right extreme and a return journey, costing at least twice their separation. Moving from the start to the left extreme, then to the right extreme, then home achieves this bound and passes every point. One scan finds both extremes, so the route described by these turning points takes O(n) time to find. Producing all points in sorted visitation order would be a separate sorting task.

Question 19 · hard · optional challenge

Change the movie-star problem so that each job pays a fee and the goal is to maximise the total fee earned. Show by example that earliest-finish-first is no longer optimal.

In simpler words: Show why choosing the earliest finish can lose money.

Starting hint: Try two overlapping jobs: one short and cheap, one long and valuable.

Answer & reasoning
Step by step
  1. Give A the interval [1,2) and fee 1; give B [1,10) and fee 100.
  2. Earliest finish selects A and must reject B because they overlap.
  3. The better solution selects B alone. One counterexample disproves the rule for fees; it does not disprove every greedy method.

Job A = [1, 2) pays 1 and job B = [1, 10) pays 100. Earliest finish first takes A, which blocks B, earning 1 instead of 100. This disproves that greedy rule for unequal fees. Weighted interval scheduling can be solved by dynamic programming; this example does not rule out every possible fee-aware greedy rule by itself.

Document reading · Lecture 1
  • Lecture 1: Introduction to Algorithms
    What an algorithm is; Correctness; How algorithms are written down; Story 1: the robot tour (why “obvious” is not “correct”); Story 2: movie star scheduling (a problem where a simple rule is correct); How to show an algorithm is wrong: counterexamples; How to show an algorithm is right: induction.

Download the complete bilingual document

Python explained for this lesson

Variables name values; assignment stores a result. An algorithm can be explained before any Python is written.

jobs = [(0, 3), (2, 4), (3, 5)]
end = float("-inf")
chosen = []
for start, finish in sorted(jobs, key=lambda job: job[1]):
    if start >= end:
        chosen.append((start, finish))
        end = finish
print(chosen)  # [(0, 3), (3, 5)]

Predict the result, then run the demonstration. No prior Python fluency is required for the paper trace.

English–Turkish explanations
Lecture 1 · What an algorithm is

Algoritma nedir?

An algorithm is the idea behind a program. The same algorithm can be written in Python on a phone or in assembly language on a supercomputer; the idea stays the same. Only the idea is studied in this course.

Algoritma, bir programın arkasındaki fikirdir. Aynı algoritma, bir telefonda Python ile veya bir süperbilgisayarda assembly dilinde yazılabilir; fikir değişmez. Bu derste yalnızca bu fikir incelenir.

To be interesting, an algorithm has to solve a general problem, not one particular input. A problem is specified by two things:

Bir algoritmanın incelenmeye değer olması için tek bir özel girdiyi değil, genel bir problemi çözmesi gerekir. Bir problem iki unsurla tanımlanır:

The set of instances it must work on (every legal input).

Üzerinde çalışması gereken problem örnekleri kümesi (geçerli girdilerin tümü).

The properties the output must have (what counts as a right answer).

Çıktının sahip olması gereken özellikler (hangi yanıtın doğru sayılacağı).

Example, the sorting problem:

Örneğin, sıralama problemi:

Input: a list of n numbers a1, a2, …, an.

Girdi: a₁, a₂, …, aₙ biçiminde n sayıdan oluşan bir liste.

Output: the same numbers rearranged so that a1 ≤ a2 ≤ … ≤ an.

Çıktı: a₁ ≤ a₂ ≤ … ≤ aₙ olacak biçimde yeniden düzenlenmiş aynı sayılar.

Notice that the problem statement never says how to sort. That is the algorithm’s job. Many different algorithms solve the same problem, and the course is largely about choosing between them.

Problem tanımının sıralamanın nasıl yapılacağını hiçbir zaman söylemediğine dikkat edin. Bu, algoritmanın işidir. Aynı problemi birçok farklı algoritma çözer; bu ders büyük ölçüde bu algoritmalar arasında seçim yapmayı konu alır.

Lecture 1 · Correctness

Doğruluk

An algorithm is correct only if it produces the desired output for every legal instance. For sorting that includes awkward inputs: a list that is already sorted, a list with repeated values, a list with one element, an empty list. An algorithm that works on “typical” inputs but fails on one odd case is simply wrong.

Bir algoritma ancak her geçerli problem örneği için istenen çıktıyı üretiyorsa doğrudur. Sıralamada buna alışılmadık girdiler de dahildir: zaten sıralı bir liste, tekrarlanan değerler içeren bir liste, tek elemanlı bir liste ve boş bir liste. “Tipik” girdilerde çalışan, fakat tek bir sıra dışı durumda başarısız olan algoritma yanlıştır.

Correctness needs a carefully worded problem. “Find the shortest tour” is precise enough to have a provably correct algorithm. “Find the best tour” is not, because “best” has no definition to check against.

Doğruluk, dikkatle ifade edilmiş bir problem gerektirir. “En kısa turu bul” ifadesi, doğruluğu ispatlanabilir bir algoritmaya sahip olacak kadar kesindir. “En iyi turu bul” ise değildir; çünkü “en iyi” için denetlenebilecek bir tanım yoktur.

Lecture 1 · How algorithms are written down

Algoritmalar nasıl ifade edilir?

There are three levels of precision, and the more precise the description, the harder it is to write and read:

Üç kesinlik düzeyi vardır. Tanım ne kadar kesinleşirse yazılması ve okunması o kadar zorlaşır:

Plain English (easiest to write, least precise).

Sade İngilizce (yazması en kolay, kesinliği en düşük).

Pseudocode: structured, program-like English with loops and conditions, but without the fussy details of a real language.

Sözde kod: döngüler ve koşullar içeren, yapılandırılmış ve programı andıran; ancak gerçek bir dilin ayrıntılı kurallarını içermeyen İngilizce.

A real programming language (most precise, hardest to read).

Gerçek bir programlama dili (kesinliği en yüksek, okunması en zor).

Skiena’s habit, followed in these notes, is to explain the idea in English and switch to pseudocode only when a detail is genuinely tricky.

Bu notlarda da izlenen Skiena yaklaşımı, fikri doğal dille açıklamak ve yalnızca bir ayrıntı gerçekten zorlaştığında sözde koda geçmektir.

Lecture 1 · Story 1: the robot tour (why “obvious” is not “correct”)

Öykü 1: robot turu (“apaçık” neden “doğru” demek değildir?)

A robot arm must solder a set of points on a circuit board. We choose the order in which it visits the points, and we want the order that minimises the total travel distance. (The arm returns to its starting point at the end.) This is the famous travelling salesman problem.

Bir robot kolunun, devre kartı üzerindeki bir dizi noktayı lehimlemesi gerekir. Noktaları hangi sırayla ziyaret edeceğini biz seçeriz ve toplam hareket mesafesini en aza indiren sırayı isteriz. (Kol, sonunda başlangıç noktasına döner.) Bu, ünlü gezgin satıcı problemidir (travelling salesman problem).

Attempt 1: nearest neighbour. Start anywhere. Repeatedly go to the closest point you have not visited yet. When all are visited, return to the start.

Deneme 1: en yakın komşu. Herhangi bir noktadan başlayın. Henüz ziyaret etmediğiniz en yakın noktaya tekrar tekrar gidin. Hepsi ziyaret edildiğinde başlangıca dönün.

It sounds sensible, and it is easy to program. It is wrong. Put the points on a straight line at positions −21, −5, −1, 0, 1, 3, 11 and start at 0. The nearest unvisited point is always just across the start, so the robot zig-zags: 0 → 1 → −1 → 3 → −5 → 11 → −21, then back to 0. Every hop roughly doubles the previous one, so the total is 1 + 2 + 4 + 8 + 16 + 32 + 21 = 84. Simply walking left to −21, then right to 11, then home costs 21 + 32 + 11 = 64. Starting from the leftmost point does not rescue the idea; other point sets break that too.

Kulağa mantıklı gelir ve programlaması kolaydır. Ama yanlıştır. Noktaları bir doğru üzerinde −21, −5, −1, 0, 1, 3, 11 konumlarına yerleştirin ve 0’dan başlayın. Ziyaret edilmemiş en yakın nokta her defasında başlangıcın karşı tarafındadır; bu yüzden robot zikzak çizer: 0 → 1 → −1 → 3 → −5 → 11 → −21, ardından yeniden 0. Her sıçrama yaklaşık olarak bir öncekinin iki katıdır; toplam mesafe 1 + 2 + 4 + 8 + 16 + 32 + 21 = 84 olur. Oysa sola −21’e, ardından sağa 11’e gidip başlangıca dönmek yalnızca 21 + 32 + 11 = 64 tutar. En soldaki noktadan başlamak da fikri kurtarmaz; başka nokta kümeleri bu seçimi de başarısız kılar.

Attempt 2: closest pair. Repeatedly join the two closest endpoints of the partial paths built so far, as long as joining them creates neither a loop nor a three-way junction. When one path contains every point, join its two ends.

Deneme 2: en yakın çift. Şimdiye kadar oluşturulmuş kısmi yolların birbirine en yakın iki uç noktasını, bir döngü veya üç kollu bir kavşak oluşturmadığı sürece tekrar tekrar birleştirin. Tek bir yol tüm noktaları içerdiğinde iki ucunu birleştirin.

This fixes the line example, but it is also wrong. Picture two horizontal rows of points, where the vertical gap between the rows is slightly less than the horizontal gap between neighbours in a row. The rule greedily links each vertical pair first, and is then forced to stitch those short vertical links together with long connections. The resulting tour is longer than the obvious loop around the outside of the rectangle.

Bu yaklaşım doğru üzerindeki örneği düzeltir, ancak o da yanlıştır. İki yatay nokta sırası düşünün; sıralar arasındaki düşey uzaklık, aynı sıradaki komşuların yatay uzaklığından biraz küçük olsun. Kural, açgözlü biçimde önce her düşey çifti birleştirir; ardından bu kısa düşey bağlantıları uzun bağlantılarla birbirine eklemek zorunda kalır. Ortaya çıkan tur, dikdörtgenin dışından dolaşan bariz turdan uzundur.

Attempt 3: exhaustive search. Try every possible ordering of the points, compute each tour’s length, and keep the shortest.

Deneme 3: tüm olasılıkları tarama. Noktaların olası bütün sıralanışlarını deneyin, her turun uzunluğunu hesaplayın ve en kısasını saklayın.

This one is finally correct, because it looks at every possibility. But the number of orderings of n points is n! (“n factorial”: n × (n−1) × … × 2 × 1). For 10 points that is 3,628,800; for 20 points it is about 2.4 × 10^18. Exhaustive search is hopeless beyond 10 to 20 points. Nobody knows an algorithm that is both correct and fast for this problem, and Lecture 19 onward explains why we believe none exists.

Bu yöntem sonunda doğrudur; çünkü her olasılığı inceler. Ancak n noktanın sıralanış sayısı n!’dir (“n faktöriyel”: n × (n−1) × … × 2 × 1). Bu sayı 10 nokta için 3,628,800; 20 nokta için yaklaşık 2.4 × 10^18’dir. Tüm olasılıkları tarama, 10–20 noktanın ötesinde uygulanamaz hâle gelir. Bu problem için hem doğru hem hızlı bir algoritma bilinmemektedir; Ders 19 ve sonrasında, böyle bir algoritmanın bulunmadığına neden inanıldığını açıklayacağız.

The lesson: a rule that feels right is only a heuristic until it is proven. Being correct on a few examples proves nothing.

Çıkarılacak ders: doğru hissettiren bir kural, ispatlanana kadar yalnızca bir sezgisel yöntemdir (heuristic). Birkaç örnekte doğru sonuç vermesi hiçbir şeyi ispatlamaz.

Lecture 1 · Story 2: movie star scheduling (a problem where a simple rule is correct)

Öykü 2: film yıldızının işlerini çizelgeleme (basit bir kuralın doğru olduğu bir problem)

A movie star is offered n film roles, each occupying a fixed interval of time. She wants to accept as many roles as possible with no two overlapping.

Bir film yıldızına, her biri sabit bir zaman aralığını kaplayan n film rolü teklif edilir. Yıldız, hiçbir ikisi çakışmayacak biçimde olabildiğince çok rol kabul etmek ister.

Input: a set I of n intervals on a line.

Girdi: bir doğru üzerinde n zaman aralığından oluşan I kümesi.

Output: the largest subset of intervals from I such that no two overlap.

Çıktı: I içinden seçilen, hiçbir iki aralığı çakışmayan en büyük aralık alt kümesi.

Attempt 1: earliest start first. Always accept the job that starts soonest and does not clash with jobs already accepted. Wrong: a single very long job (“War and Peace”) that starts first blocks everything else. With jobs A = [1, 10], B = [2, 3], C = [4, 5], the rule takes A alone, while B and C together would be two jobs.

Deneme 1: önce en erken başlayan iş. Her zaman en erken başlayan ve kabul edilmiş işlerle çakışmayan işi kabul edin. Yanlış: ilk başlayan tek bir çok uzun iş (“Savaş ve Barış”) diğer her şeyi engeller. A = [1, 10], B = [2, 3], C = [4, 5] işleri için kural yalnızca A’yı seçer; oysa B ve C birlikte iki iş eder.

Attempt 2: shortest job first. Always accept the shortest remaining job, then delete everything it overlaps. Wrong: a short job that sits across the boundary between two longer jobs knocks out both. With A = [1, 5], B = [4, 6], C = [5.5, 9], the rule takes B (length 2) and loses A and C, which are compatible with each other.

Deneme 2: önce en kısa iş. Her zaman kalan en kısa işi kabul edin, ardından onunla çakışan her şeyi silin. Yanlış: iki uzun işin sınırını aşan kısa bir iş, ikisini de devre dışı bırakır. A = [1, 5], B = [4, 6], C = [5.5, 9] için kural B’yi (uzunluk 2) seçer ve birbirleriyle uyumlu olan A ile C’yi kaybeder.

Attempt 3: earliest finish first. Always accept the job that finishes soonest, delete everything it overlaps, repeat. This one is correct.

Deneme 3: önce en erken biten iş. Her zaman en erken biten işi kabul edin, onunla çakışan her şeyi silin ve tekrarlayın. Bu yöntem doğrudur.

Why it works, in plain words: let x be the job that finishes first. Any job that conflicts with x must overlap the period around x’s finish time, so all of those conflicting jobs overlap each other too, and at most one of them can ever be chosen. Choosing x instead of any of them can only free up more time afterwards, never less. Repeating the argument after x is accepted gives an optimal schedule.

Neden işe yaradığını sade bir dille açıklayalım: en erken biten iş x olsun. x ile çakışan her iş, x’in bitiş zamanı çevresindeki dönemi kapsamak zorundadır; dolayısıyla bu çakışan işlerin tümü birbirleriyle de çakışır ve bunlardan en fazla biri seçilebilir. Bunlardan herhangi biri yerine x’i seçmek, sonrasında yalnızca daha fazla boş zaman bırakabilir; daha az değil. x kabul edildikten sonra aynı argümanı tekrarlamak optimal bir çizelge verir.

This is a first example of a greedy algorithm (make the locally best choice and never look back) that is actually correct. Most greedy rules are not; this one is because the proof exists.

Bu, gerçekten doğru olan bir açgözlü algoritmanın (yerel olarak en iyi seçimi yap ve bir daha geriye bakma) ilk örneğidir. Açgözlü kuralların çoğu doğru değildir; bunun doğru olmasının nedeni bir ispatının bulunmasıdır.

Lecture 1 · How to show an algorithm is wrong: counterexamples

Bir algoritmanın yanlışlığı nasıl gösterilir? Karşı örnekler

Hunting for a counterexample is the fastest way to kill a bad heuristic. Three places to look:

Karşı örnek aramak, kötü bir sezgisel yöntemi çürütmenin en hızlı yoludur. Bakılacak üç yer vardır:

Small examples. Try every input with 2, 3 or 4 items. Most broken rules break on tiny inputs.

Küçük örnekler. 2, 3 veya 4 elemanlı tüm girdileri deneyin. Hatalı kuralların çoğu çok küçük girdilerde bozulur.

Ties. If the rule says “pick the nearest”, build an input where two things are equally near and see whether either choice leads to disaster.

Eşitlik durumları. Kural “en yakını seç” diyorsa, iki nesnenin eşit uzaklıkta olduğu bir girdi oluşturun ve seçimlerden birinin felakete yol açıp açmadığına bakın.

Extremes. Mix very large and very small values, very long and very short intervals, points very close and very far apart.

Uç durumlar. Çok büyük ve çok küçük değerleri, çok uzun ve çok kısa aralıkları, birbirine çok yakın ve çok uzak noktaları birlikte kullanın.

Lecture 1 · How to show an algorithm is right: induction

Bir algoritmanın doğruluğu nasıl gösterilir? Tümevarım

Not finding a counterexample is not a proof. “It’s obvious” is not a proof either. The standard tool for proving that a recursive or step-by-step algorithm is correct is mathematical induction, which has three parts:

Karşı örnek bulamamak ispat değildir. “Apaçık ortada” demek de ispat değildir. Özyinelemeli veya adım adım ilerleyen bir algoritmanın doğruluğunu ispatlamak için kullanılan standart araç, üç bölümden oluşan matematiksel tümevarımdır:

Base case. Show it works for the smallest input (say, n = 1).

Temel durum. En küçük girdi için çalıştığını gösterin (örneğin n = 1).

Assumption (induction hypothesis). Assume it works for all inputs up to size n − 1.

Varsayım (tümevarım hipotezi). Boyutu n − 1’e kadar olan bütün girdiler için çalıştığını varsayın.

General case. Using that assumption, show it works for size n.

Genel durum. Bu varsayımdan yararlanarak n boyutu için çalıştığını gösterin.

Recursion (an algorithm that calls itself on a smaller input) is the same idea seen from the programmer’s side, which is why induction is the natural way to prove recursive algorithms correct.

Özyineleme (bir algoritmanın daha küçük bir girdi üzerinde kendisini çağırması), aynı fikrin programcı açısından görünümüdür. Bu nedenle tümevarım, özyinelemeli algoritmaların doğruluğunu ispatlamanın doğal yoludur.

The classic warm-up is the formula for adding the numbers from 1 to n:

Klasik hazırlık örneği, 1’den n’ye kadar sayıların toplamını veren formüldür:

Base case: for n = 1 both sides equal 1. Assumption: the formula holds for n − 1, so 1 + … + (n−1) = (n−1)n/2. General case: add n to both sides, and (n−1)n/2 + n simplifies to n(n+1)/2. Done. This particular sum will come back in Lecture 3 when we count the steps of selection sort.

Temel durum: n = 1 için iki taraf da 1’dir. Varsayım: formül n − 1 için geçerlidir; dolayısıyla 1 + … + (n−1) = (n−1)n/2. Genel durum: iki tarafa n ekleyin; (n−1)n/2 + n ifadesi n(n+1)/2’ye sadeleşir. İşlem tamamdır. Bu toplam, Ders 3’te seçmeli sıralamanın adımlarını sayarken yeniden karşımıza çıkacaktır.