AA / course home
Week 01 · Phase 1 · Thinking in steps

What Is an Algorithm?

Trace a method. Draw what changes. Count the work.

How can we get the right answer with less work?

Lesson

1.1One problem. A precise method.

Find the largest number. Start with a non-empty list.

Input7, 2, 9, 4
MethodKeep the largest so far
Output9

Algorithm: precise instructions that finish and produce the required output for every allowed input.

Trace — the remembered value after each card
7294
7799

Read the first card. Then replace the remembered value only when a larger card appears.

Cards readT(n) = n
Comparisons after the first cardn − 1
Remembered values1

n means the number of cards. Here: 4 reads, 3 comparisons, 1 remembered value.

Why must we read every card?

An unread card could be larger than every card seen so far. We cannot guarantee the maximum without reading it.

1.2Use order to skip work

Different problem: find 7 in this sorted list. Check the lower middle card; if it is not 7, keep only the side that could contain 7.

Three checks to find 7
1
247912162025

9 > 7 → keep the left side.

2
247912162025

4 < 7 → keep 7.

3
247912162025

7 = 7 → stop.

Read one by one

Works with any order.

Worst case: n checks.

Check the middle

Requires sorted input.

Each failed check leaves at most half the candidates.

On a shuffled list: a middle value cannot tell us which side contains the target.

1.3Count work before measuring time

One check means inspecting one candidate and deciding “found”, “left” or “right”.

One-by-one search, worst caseT(n) = n
Middle search: largest size covered in k checksn = 2k − 1
Items, nOne by one: maximum checksMiddle search: maximum checks
773
15154
31315
1,0001,00010

29 − 1 = 511 < 1,000 ≤ 1,023 = 210 − 1
So 10 middle checks suffice in the worst case.

Where does 2ᵏ − 1 come from?

One check handles the middle item, then either a left or right subproblem.

Capacity: 1 → 2 × 1 + 1 = 3 → 2 × 3 + 1 = 7 → 15 → 31

After k checks the capacity is 2k − 1. We count checks, including the final candidate; simply halving a size down to one is a different count.

Optional preview · other growth patterns

Compare the displayed counts as n increases. The names are introduced later in the course.

Counts depend on the method and input. Seconds also depend on the machine. We will measure seconds later.

1.4Three checks for your instructions

Clear?

“Warm it a bit” → “Heat to 60 °C.”

Will it finish?

“Draw enough cards” → “Draw 5 cards from a pile with at least 5.”

Assumptions stated?

“Search the middle” → “Search the middle of a sorted list.”

Judge a method in this order: correct answer → readable instructions → work and memory used.

1.5Run your first cell

  1. Open Google Colab and create a notebook.
  2. Enter the code below. Press Shift + Enter.
  3. Name the notebook AA_Week01.ipynb.
Python — arithmetic only; no loop syntax yet
print("Hello, algorithms!")
print(2 ** 10 - 1)
Hello, algorithms! 1023

** means “to the power of”. Change 10 to 3; predict the result before running.

If the cell shows an error

Read the last line of the error message. Check that the quotes and parentheses match the 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.

Story 2 · Movie-star scheduling

One actor receives fixed film offers. Accept the largest number of non-overlapping roles; every role has equal value. A role ending at time 3 can be followed by one starting at 3: we use intervals [start, finish).

Blue = accepted; a crossed-out bar = rejected; an orange outline marks the offer currently being checked. Equal priority uses alphabetical order.

Compare all three rules on these offers

    Why earliest finish is correct

    1. Take an optimal schedule and call its first film O. Let E be the offered film that finishes earliest.
    2. E finishes no later than O. Replace O with E: every later film in that schedule still starts after E finishes, so the number of roles is unchanged.
    3. Repeat on the offers starting at or after E’s finish. This gives an optimal schedule that begins with each greedy choice.

    Know the boundary. This proof maximises the number of roles for one actor with fixed, positive-duration intervals and no changeover time. Different fees, travel times or multiple actors change the problem.

    Practice

    Practice questions

    10 test questions · 7 written questions · 17 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 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

    A method says “repeat until the answer looks good.” What is missing?

    1. a particular programming language
    2. a precise stopping condition
    3. a faster computer
    4. a longer name

    Answer: option B. “Looks good” gives no test that another person or a computer can apply consistently. State a measurable condition for stopping.

    Question 6 · easy · course question

    Scan the cards 6, 2, 8, 3, remembering the largest seen so far. What are the remembered values after each card?

    1. 6, 6, 8, 8
    2. 6, 2, 8, 3
    3. 2, 2, 3, 3
    4. 8, 8, 8, 8

    Answer: option A. Start with 6. The 2 does not replace it; 8 does; 3 does not replace 8.

    Question 7 · easy · course question

    Which input would disprove the rule “the first item is the maximum” for every nonempty list?

    1. [9]
    2. [9, 2]
    3. [9, 9]
    4. [2, 9]

    Answer: option D. The rule returns 2 for [2, 9], although the maximum is 9. One legal failing input disproves a universal correctness claim.

    Question 8 · easy · course question

    A search checks the middle value and discards one side. What must be known to justify the discarded side?

    1. the computer brand
    2. the list length is even
    3. the values are sorted in the stated order
    4. the target appears exactly once

    Answer: option C. Sorted order tells us which side may contain smaller or larger values. Without it, a middle value does not justify discarding either side.

    Question 9 · easy · course question

    Two methods both return the required result on every legal input. What is a useful next comparison?

    1. only the number of characters in their names
    2. work and memory needed as input size grows
    3. which method was invented first
    4. whether both were written on the same day

    Answer: option B. Once correctness is established, compare resource use under the same assumptions and input sizes. Short-looking code can still do much work.

    Question 10 · hard

    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

    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 13 · 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 14 · 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 15 · 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 16 · hard

    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 17 · hard

    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.

    1.6Try it yourself

    1 · Trace

    For 6, 3, 8, 2, 5, write the largest-so-far after each card. Count reads and comparisons separately.

    Animate it — after you have tried by hand
    Check your trace

    6 → 6 → 8 → 8 → 8. 5 reads, 4 comparisons. For n cards: n reads and n − 1 comparisons.

    2 · Calculate

    Guess a secret from 1–100 using the middle each time. For secret 73, record each guess. Compare with counting up from 1.

    Animate it — race the two strategies
    Check your counts

    50 → 75 → 62 → 68 → 71 → 73: 6 guesses. Counting up takes 73. The worst case over all secrets is 7 middle guesses because 26 − 1 < 100 ≤ 27 − 1.

    3 · Change one thing

    Shuffle the cards. Can a middle check still justify discarding half? Show one arrangement where it discards the target.

    Animate it — watch the halving trick break
    Check your explanation

    Searching for 2 in [9, 4, 2]: the middle is 4. Keeping only the left side discards 2. Sorted order is necessary for this rule.

    Optional challenges · sorting, large inputs, precise instructions
    Put letters in order

    Sort A, C, E, B, D using only comparisons and swaps. Specify when to stop.

    Animate it — or be the machine yourself
    Reduce to one candidate

    Repeatedly halve 1,000,000, rounding up. How many reductions leave one candidate? Repeat for 1,000,000,000.

    Animate it — check your estimate
    Check

    20 and 30 reductions. These count reductions to one candidate, not checks of that candidate.

    Repair an instruction

    Identify the missing precision, stopping rule or assumption, then repair the instruction.

    Animate it — hand the instructions to a literal robot

    Check your understanding

    1.7Self-check

    Find the maximum of 10 unsorted cards, remembering the first card before comparing the rest. How much work?

    Read every card; compare each of the nine later cards with the largest so far.

    What lets a middle check safely discard one side?

    Order tells us that all values on one side are too small or too large.

    Middle search covers at most 2ᵏ − 1 items in k checks. How many checks cover 31 items?

    2⁵ − 1 = 31. This is the worst-case bound; some targets are found sooner.

    Ready for Week 2: explain your trace, name the sorted-input assumption, and run the Colab cell.

    1.8Words from this week

    Six terms to keep
    Algorithm
    Precise instructions that finish with the required output.
    Input / output
    What the method receives / produces.
    n
    The input size: here, the number of items.
    Trace
    The states produced while following a method step by step.
    Worst case
    The largest cost among allowed inputs of the same size.
    Memory
    The information stored while the method runs.
    Extra material & reference
    Optional depth · correctness and counterexamples

    From the beginner notes · Lecture 1

    Test a robot route with a small example

    A robot visits solder points on a circuit board and returns to its start. “Choose the nearest unvisited point” sounds sensible, but a shorter move now can force a longer move later. Before writing code, say which inputs are allowed, how distance is measured and whether the route must return home.

    On a line, any closed route visiting both extremes travels at least twice their separation. That gives a lower bound: a distance no valid route can beat. A sweep from one extreme to the other and back can reach it. Compare the nearest-neighbour trace in the investigation with that bound. One failing example (a counterexample) disproves the claim that the rule always gives the best route. Many successful tests do not prove that claim.

    Engineering use. If an AI proposes a routing rule, ask what it tries to minimise, how it chooses between equal options, and whether a small example can show it fails.

    Learning goals & class plan
    This week

    Describe a method, trace it, count its work, and run one Python cell.

    Three-hour interactive studio

    00:00–01:00: launch, predict–run–explain cycle, questions  ·  01:00–01:10: break  ·  01:10–02:00: worked variation, peer instruction, questions  ·  02:00–02:10: break  ·  02:10–03:00: core mechatronics practice, exam bridge, and exit ticket.

    Ask at any point. Weekly self-checks stay private; optional extensions are not collected.

    Need a longer explanation? Open the English + Türkçe reference guide.

    Where this leads

    You reasoned about steps on paper. Next week the computer does the counting for you — your first lines of Python.