Week 01 — What Is an Algorithm?

The big question

If two people both get the right answer, why would we prefer one method?

This week begins with instructions, numbered cards and a guessing game. You need no programming experience. Explain exactly what somebody should do, then count the work required. Python begins in Week 2.

By the end, you should be able to identify an input and an output, write an unambiguous stopping rule, follow a method without inventing missing steps, and compare two methods using one clearly defined unit of work. You should also be able to name an assumption that makes a faster method valid. Speed is useful only when the method still solves the intended problem.

Retrieve the ideas you already have

These are analysis questions: distinguish a claim from its evidence and identify missing information. To visualize halving, draw sixteen marks and cross out half at each stage.

Türkçe açıklama: Algoritma analizi için önce karmaşık formüller değil, açık bir soru gerekir. “En büyüğü buldum” demekle “görmediğim kart daha büyük olamaz” demek farklıdır. İkinci cümle, cevabın neden güvenilir olduğunu açıklamaya başlar.

1. A method needs a contract

An algorithm is a procedure with definite steps that finishes and produces the required result for its allowed inputs. A short description should answer four questions: What do we start with? What operations are allowed? When do we stop? What do we report?

For example, “find the largest card” is a problem, not yet a procedure. We can make the contract precise: the input is a nonempty row of number cards; reading and comparing cards are allowed; the output is the largest value. We do not promise to find a largest value in an empty row, because there is no value to return. We can instead report “no cards.” Stating that case is part of being precise.

“Finite” concerns execution, not merely the number of written sentences. “Keep repeating step one forever” is a very short description, but it never finishes. A useful stopping rule must be checkable, and the procedure must make progress toward it. “Stop after inspecting the final card” works because the row is finite and each inspection advances to the next card.

Türkçe açıklama: Girdi koşulu bir mazeret değildir; çözmek istediğimiz problemin sınırını belirtir. Boş bir listedeki en büyük sayıyı istemek, içinde hiç kart olmayan bir kutudan kart seçmek gibidir. Bu durumu açıkça ayırınca hem çözüm hem hata davranışı anlaşılır olur.

2. Instructions must not depend on guessing

The lesson uses recipes and directions because they expose hidden assumptions. “Add some water” leaves the amount unspecified. “Walk toward the building” leaves the building unspecified. “Use the middle card to choose a half” leaves the ordering assumption unspecified.

A precise version says, “Read the next card from the left; compare its number with the largest number remembered so far.” Another person can follow this literally.

We need not describe every physical movement. We can agree that “read one card” is an available operation. Later, a Python command will be an agreed operation, whose internal work we may examine separately.

3. Worked example: a largest-value scan

Use the cards 8, 3, 11, 6. We will count two things separately: a look reads one card, and a comparison compares a later card with the remembered largest value.

The procedure is: read the first card and remember it; move right; replace the remembered value only if the new card is larger; stop after the last card; report the remembered value.

The answer is 11. Four cards required four looks but only three comparisons. For n nonempty cards, the same procedure uses n looks and n − 1 comparisons. Here n means the number of cards, not the largest number printed on them. Replacing 11 with 11 million does not add another card.

Why can we trust the answer? After each row, the remembered value is the largest among the cards already inspected. A larger newcomer replaces it; a smaller newcomer cannot invalidate it. After the last row, “already inspected” means the whole input.

Türkçe açıklama: “Dört adım” demeden önce neyi saydığını söyle. Kartı okumak ile iki değeri karşılaştırmak aynı olay değildir. İlk kart başlangıç değerini sağlar; onu önceki bir şampiyonla karşılaştırmadığımız için karşılaştırma sayısı bir eksiktir.

4. Worked example: keeping only the possible half

A friend chooses 13 from the whole numbers 1 through 16. After each guess they truthfully answer higher, lower or correct. Guess the middle of the remaining interval, rounding a midpoint down when necessary.

Notice the boundary changes. After “higher than 8,” 8 is no longer possible, so the new lower boundary is 9. After “lower than 14,” the upper boundary becomes 13. Keeping the rejected midpoint would create unnecessary work and can prevent progress in a careless implementation.

This secret took four guesses. That is not a guarantee that every secret takes four: with this convention, 16 follows 8, 12, 14, 15, 16 and takes five. Distinguish the guesses for one input from the maximum over every allowed input.

Türkçe açıklama: Her tahminden sonra cevabın bulunabileceği aralığı koruyoruz. “Daha büyük” cevabı yalnızca yön söylemez; tahmin edilen sayıyı ve altındaki bütün sayıları eler. Son kalan sayıyı gerçekten kontrol etmek de bir tahmindir; aralığı küçültmek ile cevabı kontrol etmek aynı sayım değildir.

5. Why structure can buy speed

A dictionary is alphabetically ordered. Looking near its middle tells us which side can contain a requested word. A shuffled pile provides no such information: a small middle value does not imply that every value to its left is small. Throwing away that half could throw away the answer.

For roughly 1,000 possibilities, repeated halving needs about ten decisions; for a million, about twenty; for a billion, about thirty. These are growth comparisons, not promises about the exact execution of every search. Increasing the size from 1,000 to a million is a thousandfold increase, while the approximate count rises by ten. From 1,000 to a billion is a millionfold increase, and the count rises by about twenty.

A complete scan behaves differently: doubling the number of cards doubles the looks. Comparing every card with every other card grows faster still. Today you need the pictures: one fixed action, one pass through the data, repeated halving, and many pair comparisons. Formal growth notation comes later.

Türkçe açıklama: Hız kazancı boşluktan gelmez; sıralılık gibi kullanılabilir bilgiden gelir. Bir yöntemi seçerken “kaç işlem?” kadar “hangi koşul altında doğru?” sorusunu da sor. Sırasız veriye sıralı veri yöntemini uygulamak, daha hızlı bir yanlış cevap üretebilir.

6. Graduated practice

Practice 1 — specify a complete task

Rewrite “take enough cards and find the biggest” for a supplied row of exactly three cards: 4, 9, 2. State input, stopping rule, result and look count.

Solution 1 — replace vague words with checkable steps

The input is the three-card row 4, 9, 2. Read 4 and remember it. Read 9; because 9 > 4, remember 9. Read 2; because 2 < 9, keep 9. Stop because all three cards have been inspected. Output 9. The count is three looks and two comparisons. “Enough” has been replaced by “all three supplied cards.”

Practice 2 — trace a search

The secret is 6 in the interval 1–8. Use the same midpoint rule as the worked example. Compare with guessing 1, 2, 3 and so on.

Solution 2 — write every remaining interval

First midpoint: (1 + 8) / 2 = 4.5, rounded down to 4. “Higher” leaves 5–8. Next midpoint: (5 + 8) / 2 = 6.5, rounded down to 6. “Correct” stops the method after two guesses. Counting upward makes six guesses. On this input the first method saves 6 − 2 = 4 guesses. That does not mean it saves exactly four on every input.

Practice 3 — challenge a speed claim

Someone inspects only three cards in an unsorted row of ten and claims to know the largest. Explain why this cannot guarantee a correct result. What changes if the cards are sorted in increasing order and that fact is trusted?

Solution 3 — use an unseen counterexample

Keep the inspected cards unchanged. Put a larger number on one of the seven unseen cards. The observer received exactly the same information but would now give a wrong answer. Therefore, without extra information, a guaranteed maximum needs ten looks. If the row is already known to be sorted increasingly, its last card is the largest; one look suffices. That shortcut relies on the trusted ordering, whose creation or verification may itself cost work.

7. Misconceptions and useful corrections

8. Glossary, readiness and the bridge

You are ready when you can explain why four cards needed three comparisons, why the halving trace changed 9–16 to 13–16, and why a shuffled pile breaks the shortcut. The answers are initialization, rejection of values at or below 12, and absence of usable ordering. If one explanation is unclear, redo that table with physical cards before adding symbols.

Bridge to Week 2: A remembered largest value will become a variable; “report the answer” will become an output command. The reasoning remains the same. You can also use the original lesson's optional Colab setup to prepare the workspace, without treating programming knowledge as a prerequisite for this week.

Why the answer is correct

An algorithm is a set of steps for solving a problem. First say what data it accepts and what answer it must give. Getting one example right does not show that it works for every allowed input. Explain why each step keeps the answer on track.

Draw or trace. Lay out cards 8, 3, 11, 6. After each card, write the largest value among the cards inspected so far. Cover the uninspected cards.

Predict before checking. Can you stop after seeing 11 because it looks large? How many comparisons are needed if the first card supplies the initial maximum?

Worked reasoning

The largest values remembered are 8, 8, 11, 11. Replace the remembered value only when the next card is larger. This keeps the largest value seen so far. After checking every card, it is the largest value in the whole list. Four cards need three comparisons because the first card gives the starting value. You cannot stop at 11: an unseen card could be 100.

Change one thing. Use all-negative cards, then no cards. Keep the same rule for negative values and explicitly define the empty-input result. Do this on paper; Python is not a prerequisite this week.

Türkçe: Doğru görünen örnek bütün girdiler için kanıt değildir. Her adımda korunan anlamı ve ne zaman bütün girdiyi kapsadığını açıkla.

Additional analysis laboratory

Use this extra laboratory after the Week 1 core trace. It turns the informal idea of a method into the first analysis habit: never compare methods until the allowed information is clear.

Extra exam-style prompt: A student says, "I checked the first and last cards, so I know the largest." Give a counterexample for an unsorted row of six cards and explain what changes if the row is trusted to be increasing.

Solution: Keep the first and last cards the same, then place a larger hidden value in the middle. The student has identical evidence but would be wrong. If the row is known to be increasing, the last card is sufficient; the ordering assumption supplies information that was absent before.

Turkce: Bu haftanin asil dersi sudur: hizli bir yolun dogru olmasi icin kullandigi bilgi belirtilmelidir. Siralama, bir varsayimdir; yoksa yarilama ya da son karta bakma guvenilir olmaz.