Greedy Method

The course changes mode here. The first half was spent on data structures and abstract data types (ADTs) — stack, queue, list, position, heap, binary tree, binary search tree, dictionary, and vector. Those structures do not disappear; we keep using them. But from this point on, the discussion centers on algorithm design techniques — general strategies for designing algorithms that can be applied to many different problems. The first such technique, and the topic of this session in full, is the greedy method.

This session follows the greedy method from its everyday roots to its classic problems. We start by seeing greedy thinking emerge from a bank cashier's coin problem, then formalize it with configurations, objective functions, and the greedy choice property. Real-life examples show where the strategy appears naturally. Then come three classic problems solved greedily: the fractional knapsack, ship loading, and job sequencing with deadlines. A full exam-style problem ties the method together, and the session closes with the textbook's application list plus the exam guidance given at the start of the class.

8.1 Algorithm Design Techniques — the Course Pivot

8.1.1 From Data Structures to Design Techniques

A quick recall exercise opened the session: which ADTs had we already covered? The answers came fast — stack, queue, list, dictionary, position, heap, binary tree, binary search tree, vector. The response to the list was an emphatic "all linear ADTs we discussed," and the tree structures we built on top of them. That was the whole first half of the course in one breath.

The second half starts with a deliberate change of focus. Instead of asking "what data structure fits this problem," we ask "how do we design the algorithm itself." The data structures remain in the toolbox — they get used again here — but the discussion now leads with design.

The distinction shows up in exam questions too: a question that asks "which data structure" and a question that asks "how would you design an algorithm" are different questions, and the course now trains the second one.

8.1.2 What Is an Algorithm Design Technique?

The instructor asked the class to define the term before explaining it. The guesses were telling.

The key idea: a design technique does not name a particular algorithm or a particular data structure. It is a way of thinking about problems, a template that you can apply to problems you have never seen before.

A technique differs from an algorithm the way a cooking style differs from a recipe. "Frying" is a technique: you can fry eggs, fish, vegetables, or cutlets, and each of those is a different recipe. A single recipe — "fried egg, sunny side up" — is a specific algorithm: exact ingredients, exact steps, one dish. The greedy method is a technique; a greedy algorithm for a specific problem is a recipe built from that technique.

8.1.3 The Hand-Tool Analogy

To make the idea concrete, the instructor used carpentry. A furniture workshop has two kinds of tools. There are specialized power tools — say, a machine designed to make sofa parts or table parts. For the one kind of furniture it is built for, that tool produces parts with utmost perfection. But it is not versatile; it cannot do anything else. Then there are general-purpose hand tools — hammer, saw, screwdriver. No hand tool makes a finished piece of furniture by itself, but with the know-how to use them, a carpenter can build any kind of furniture with hand tools.

The specialized power tool is a specific algorithm, good for the problem it was designed for. The hand tool is the algorithm design technique: fundamental, general, and applicable to a wide range of problems once you know how to drive it. The design technique is exactly that kind of tool — not a specialized solution, but a general approach.

Visual intuition — the workshop shelf. Picture a workshop wall. On one side stand special-purpose machines, each bolted down and dedicated to one product line: this one stamps sofa arms, that one cuts table legs. The machines sit idle for anything outside their one job. On the other side hangs a small rack of hand tools — hammer, saw, screwdriver, plane. The hand tools follow the carpenter to every job in the shop. The syllabus for this course is the hand-tool rack: a few techniques, each of which follows you to many problems.

8.2 The Change-Making Problem — Greedy Thinking by Example

The best way to meet the greedy method is through the change-making problem — the one bank cashiers face most of the time. For simplicity, the examples use paise as the unit.

8.2.1 First Example: Change for 32 Paise

The denominations available to the cashier are 25, 10, 5, and 1 paise. The cashier's till holds one 25-paise coin, two 10-paise coins, two 5-paise coins, and five 1-paise coins. The task: give change for 32 paise.

The class produced two answers: 25 + 5 + 1 + 1 (four coins) and 10 + 10 + 5 + 5 + 1 + 1 (six coins).

The greedy reasoning, step by step:

• Look for the largest denomination that does not exceed 32. That is 25. Give the 25-paise coin.
• The remaining problem shrinks to 7 paise. The largest denomination that fits in 7 is 5. Give the 5-paise coin.
• The remaining problem shrinks to 2 paise. Give two 1-paise coins.

So the greedy answer is $32=25+5+1+1$, four coins total. The big problem (32 paise) was reduced to a small one (7 paise) in one step, and then to 2 paise. Each step takes the largest coin that can possibly be given, without thinking about the future.

This answer is also the optimal solution — it uses the fewest possible coins. The objective was to minimize the number of coins, and greedy happened to achieve it here. That is why the instructor called it "one of the most correct answers."

Visual intuition — the shrinking target. Picture the amount as a line of 32 small marks. Each greedy step draws one coin across the largest chunk it can cover: the 25-paise coin wipes out marks 8 to 32, the 5-paise coin covers marks 3 to 7, and two 1-paise coins cover the last two marks. The line empties from the right, always taking the longest single span available. That is the whole strategy in one picture: cover as much as possible now, then look again at what is left.

8.2.2 Second Example: Change for 20 Paise — Greedy Fails

Same kind of problem, different coin set. Available: one 15-paise coin, two 10-paise coins, and five 1-paise coins. Change for 20 paise.

The optimal solution is different: two 10-paise coins — two coins.

Greedy picked 15 first because giving 15 reduces the problem at hand to the maximum. It never asked whether that choice leads to an optimal final answer. It did not. So in this second example, greedy thinking does not give the optimal solution.

This is the moment to be careful: in the first example greedy produced an optimal solution; in the second it did not. Greedy thinking will not guarantee an optimal solution. It will always give you a solution — but that solution may not be optimal. Greedy gives the optimal answer only when the problem has the greedy choice property (next section). This second problem lacks it: the optimal solution to the subproblem "give change for 15 paise" would be a single 15-paise coin, and that 15-paise coin is never part of the optimal solution for 20 paise. The optimal solution of the big problem does not contain the optimal solution of the subproblem.

8.2.3 Student Questions on the Coin Problems

The same question, asked about any amount, gets the same answer — the rule never changes:

Real-world: this is the exact problem a bank cashier or a vending machine solves dozens of times a day. The point of the two examples is that the same strategy that feels natural to a human (take the biggest coin that works, then repeat) is the greedy method — and it has a flaw that only the greedy choice property can patch.

8.3 Greedy Method — Definition and Properties

8.3.1 Configurations and Objective Functions

The formal definition: a greedy method is a general algorithm design paradigm built on two ideas — configurations and an objective function.

For 20 paise with the 15/10/1 till, two configurations exist: one 15-paise coin plus five 1-paise coins (score 6), and two 10-paise coins (score 2). The objective function is the count of coins, and the optimization problem is to find the configuration with the minimum count. If $c$ stands for the number of coins in a configuration, the objective is

$$\min c$$

and the answer is the configuration that reaches that minimum.

The greedy thinking for the coin problem, in one sentence: always return the largest coin you can. For the first example's coins (25, 10, 5, 1), this works optimally. The intuition behind the strategy: each step should eliminate as much of the remaining problem as possible, so pick the biggest denomination that still fits. Greedy never asks whether today's choice is good for the final answer — it only asks what looks best right now.

Here is the casual way to think of the method: it is a design strategy that tries to find the best solution for each subproblem, with the hope that this will yield a good solution for the problem as a whole. When you first meet a problem, you solve the maximum possible from it right away. You do not know whether the path you are on now leads to the best solution — you take whatever looks best at this particular point. The method makes a choice that looks best at the moment without worrying about the effect that choice has in the future. In the 20-paise example, giving the 15-paise coin was the locally best move — it shrank the problem the most — and it was exactly the move that ruined the outcome.

Once a choice is made, it cannot be reversed. That irreversibility is what locks in the suboptimal outcome in the 20-paise example.

To solve a problem with a greedy method, you proceed by a sequence of choices: start from some well-understood starting configuration, then iteratively make the decision that seems best at present, until the problem is solved. This sequence will not always lead to an optimal solution; it works optimally exactly for problems with the greedy choice property.

8.3.2 Greedy Choice Property

The greedy choice property is the property that makes the greedy method trustworthy: a globally optimal solution can be arrived at by making locally optimal choices. When a locally optimal choice can lead to a globally optimal solution, the problem has this property.

It is not easy to look at a problem and know whether it has the property. You cannot tell just by inspection — you have to work it out. The instructor showed this with two coin sets.

The instructor's answer to the earlier question about greedy for arbitrary amounts used this same 40-paise example: greedy gives one 30-paise coin first; the remaining problem is change for 10 paise; greedy gives what fits (described in class as giving 5s), landing on three coins total, while the optimal solution solves the same problem with two coins.

So the check is problem-dependent. You may have to look at the coin values and work out whether the greedy choice stays inside some optimal solution. There is no formula that tells you in advance.

8.3.3 Optimal Substructure

The second property — optimal substructure — was introduced conceptually and flagged as the "second part" of the greedy story, to be developed later in the course. The concept: an optimal solution to a problem contains optimal solutions to its subproblems. The 20-paise problem shows what happens when it fails: the optimal solution to the subproblem "change for 15 paise" is one 15-paise coin, but that coin is not part of the optimal solution for 20 paise. The big optimal solution does not contain the subproblem's optimal solution, so the greedy approach built on that subproblem collapses.

The two properties travel together in every greedy success story. The greedy choice property makes the first move safe; optimal substructure guarantees that the smaller problem left behind is worth solving greedily in turn. Both are needed — the 20-paise coin problem fails on both counts: greedy's first move (15) is not part of any optimum, and the optimal solution of the big problem does not contain the optimal solution of the subproblem.

Hold the greedy choice property firmly in mind: a problem must have it for the greedy strategy to give an optimal answer.

8.3.4 The Three Properties of a Greedy Choice

Every choice the greedy method makes must satisfy three conditions.

1. Feasible — the choice must be possible: it has to satisfy the problem's constraints. You must be able to do it.
2. Locally optimal — the choice must be the best solution you can make at the present step.
3. Irrevocable — once made, the choice cannot be changed in subsequent steps.

That is the whole method: take the best feasible option available, commit to it forever, repeat. It is an easy method to run — you stop worrying about the global optimum and just take the best available step. The difficulty lives entirely in deciding whether the problem deserves a greedy method at all.

8.3.5 Recognizing Greedy Problems

A second question followed naturally — whether the method must be applied by trial and error:

Yes, this sounds awkward: if you must solve first and prove later, what is the use of the method? The answer is that applying greedy is very direct and very easy — the proof work is one-time, per problem family — and that is why greedy still finds use in many places.

8.4 Greedy Method in Real Life

8.4.1 Everyday Examples

Asked for real-life situations where the greedy strategy applies, the class produced a string of good answers.

The exam-preparation example maps onto the greedy pattern cleanly. The configuration is your study plan; the objective function is marks gained per hour; the greedy choice is the highest-yield topic next; and the choice is irrevocable in the sense that the hours spent are gone. The backpack maps the same way: the configuration is the set of packed items, the objective is total value under the weight limit, and greedy packs the item with the best value-per-weight next.

8.4.2 Portfolio Optimization and Cutting Stock

Portfolio optimization is a rich real-world greedy application. A portfolio is the range of investments held by a person or an organization. Portfolio optimization is the process of selecting the best portfolio out of the set of all portfolios being considered, according to some objective — for example, the distribution of investment across sectors. The objective: maximize the factors you want (expected returns) while minimizing the factors you do not (financial risk). "Less risk, max profit" is the everyday phrasing. That is an optimization problem, and greedy is a natural candidate method.

Cutting stock problem comes from hardware factories. You have standard-size pieces of stock material — a paper roll, a sheet of metal — and you must cut them into pieces of specified sizes. The objective is to minimize the material wasted while fulfilling the order. Again: minimize something, so it is an optimization problem, and greedy-style cutting decisions are the standard approach.

Real-world: one more example surfaced from the class — the internet download manager. When you download a file, the data is broken into chunks, and the server packs the chunks according to the maximum size of data that can be retrieved in one go; the greedy algorithm packs the chunks so that the size limit is fully used on every request.

8.5 Fractional Knapsack

8.5.1 Problem Statement

First, the word: a knapsack is a bag or container — historically the bag soldiers carried back with them when they returned home. (Asked for the meaning, the class fell silent and someone went googling; the answer is simply "the bag.")

The problem: given a knapsack of capacity $M$ and $n$ objects with weights $w_1,w_2,\dots ,w_n$ and profits $p_1,p_2,\dots ,p_n$ associated with each object, place objects in the knapsack so that the profit is maximum and the total weight of the chosen objects does not exceed the capacity. The instructor's picture: a thief robbing a bank with a bag, packing objects so that profit is maximized within the bag's weight limit.

The instructor noted that it has already been proved that this family of problems can be solved with the greedy method and yields an optimal solution here.

8.5.2 Mathematical Formulation

Let $x_i$ be the fraction of object $i$ that is added to the knapsack. The aim is to maximize profit:

$$\text{maximize }\sum _{i=1}^n{p}_i{x}_i$$

"Summation of 1 to n, $p_i$ into $x_i$ — this will give me the maximum profit." Here $p_i$ is the profit associated with object $i$, and $x_i$ is the fraction of that object taken.

The constraint: the weight of the chosen objects must not exceed the capacity.

$$\sum _{i=1}^n{w}_i{x}_i\le M$$

"$w_i$ is the weight associated with each object and $x_i$ is a fraction of that object, so summation of 1 to n of $w_i{x}_i$ should be less than or equal to capital $M$, where $M$ is the capacity of the knapsack." Since $x_i$ is a fraction, it is bounded:

$$0\le x_i\le 1$$

Maximize the profit; satisfy the capacity constraint at all times; that is the whole problem.

8.5.3 The Greedy Choice: Value per Unit Weight

The greedy choice: keep taking the item with the highest value. The word value is loaded — it means the profit-to-weight ratio:

$$v_i=\frac{p_i}{w_i}$$

Value is the profit obtainable per unit weight — per kg or per pound, as you prefer. Before applying the algorithm, compute $v_i$ for every object and arrange the objects in decreasing order of value. Then consider objects in that order.

Why does sorting by value make the method work? Because per-unit profit tells you how much profit each unit of weight brings. It is the number that lets you decide, later in the example, that taking all of object 3 is more profitable than taking a fraction of object 1. Without the value computation you could not make that decision.

8.5.4 Worked Example: Three Gold Blocks

Visual intuition — filling a box with gold. Picture the bag as a 40-kg box and each object as a block with its value per kg stamped on it. Greedy is a shopper who reads the stamps and drops the best-value block in first, then the next best, and when the last block does not fit, breaks off exactly the piece that fits. The box ends exactly full — in the fractional version there is always a piece size small enough to finish the job, which is why the final $RC=0$ is a good self-check: the answer should always end at full capacity.

8.5.5 The Algorithm

The instructor emphasized: different textbooks show different versions of this algorithm, but this is the easiest version, and it matches the table above exactly. Keep the notation fixed: $w$ for weight, $p$ for profit, $x$ for the fraction, $RC$ for remaining capacity.

1.  Arrange the objects in decreasing order of p_i / w_i
2.  for i = 1 to n:
3.      x_i = 0                      // fractions array, initialized
4.  RC = M                           // remaining capacity starts at the full capacity
5.  for i = 1 to n:
6.      if w_i > RC: break           // weight exceeds remaining capacity; nothing more fits
7.      x_i = 1                      // take the complete object
8.      RC = RC - w_i                // reduce remaining capacity
9.      P = P + p_i                  // add the full profit
10. if i <= n:                       // a fraction of the current object can still be taken
11.     x_i = RC / w_i
12.     P = P + x_i * p_i            // add the fraction's profit

The logic in English: walk the objects in decreasing value. While the next object's weight fits in the remaining space, take it whole — every kilogram of a full object earns its value. The moment an object weighs more than what is left, stop taking whole objects and take only the fraction $RC/w_i$ that exactly uses up the space, then finish. The break and the final fraction are the only two exits from the packing loop.

Walk through it against the example: the loop takes O3 ($x=1$), then O2 ($x=1$); at O1 the test $w_1=20>RC=5$ triggers the break; the last if computes $x_1=5/20=0.25$ and adds $0.25\times 30=7.5$. Exactly the table.

8.5.6 Time Complexity

The time complexity is $O(n\log n)$ — because of the sorting step. This is the step that everyone misses when computing the complexity. The loops themselves run in $O(n)$, and the if statement is $O(1)$; the sorting is what dominates. The instructor used heap sort in the example because heap-based sorting is the only sorting we have studied so far, but any sorting algorithm works — it is not mandatory to use heap sort. Different sorting algorithms give different overall complexities, so use the sorting algorithm that does the job in the most effective way; several sorting algorithms run in $n\log n$, and more of them appear in the next algorithm design strategy.

8.5.7 Student Questions and Answers

During the table fill, a student doubted whether object 2 could be taken whole:

Another student asked about the supply of each object:

And one more, linking back to the coin problem:

Real-world: fractional knapsack is exactly the model behind cutting stock, portfolio optimization, and download managers — anywhere a divisible resource is packed into a limited container to maximize value. The 0/1 knapsack variant (indivisible objects) comes later under a different technique.

8.6 Ship Loading Problem

8.6.1 Problem Statement

A second optimization problem in the same family: a ship is to be loaded with containers. The aim is to load the ship with the maximum number of containers. Each container $i$ has a weight $w_i$, and the ship has capacity $C$. The variable $x_i$ denotes whether container $i$ is loaded: $x_i=0$ if the container is not loaded, $x_i=1$ if it is.

The constraint is the same shape as knapsack:

$$\sum _{i=1}^n{w}_i{x}_i\le C$$

where $C$ is the capacity of the ship, and the optimization is to maximize the number of containers loaded.

Since the 0/1 knapsack has not been studied yet, treat this as a fractional knapsack problem with the value of $x_i$ restricted to either 0 or 1. When 0/1 knapsack is covered, the instructor said, this problem will be revisited from a different angle.

8.6.2 Greedy Strategy

The greedy algorithm loads the ship in stages — one container per stage — and at each stage selects the container with the least weight. Lightest first maximizes the count of containers, which is the objective here (different from fractional knapsack, where highest value first maximizes profit).

The greedy algorithm itself is cheap to run: sorting the containers by weight costs $O(n\log n)$, and the loading pass visits each container once, so the whole procedure is $O(n\log n)$. What earns the answer credit is the same habit as everywhere in this unit: state the objective, state the greedy criterion (lightest first), and justify why the choice is safe.

8.7 Job Sequencing with Deadlines

Task scheduling is the second category of greedy problems. Two versions appear in the literature; both are discussed — job sequencing with deadlines first, then interval scheduling (next session).

8.7.1 Problem Statement

Given a set of $n$ jobs, where each job $i$ has an integer deadline $d_i$ and a profit $p_i$, find the set of jobs such that all jobs are completed within their deadlines and the profit earned is maximum.

Three constraints define the setting:

1. Only one machine is available for processing the jobs.
2. Only one job can be processed at any point of time.
3. A job is complete when it is processed on the machine for one unit time — every job takes exactly one unit, which is why durations are not mentioned in the data; only deadlines are.

The problem: find the order in which to sequence the jobs so that every scheduled job finishes within its deadline and total profit is maximized. Note that we do not have to schedule all the jobs — the subset that fits the deadlines and maximizes profit is the answer.

8.7.2 The Clock Representation

The instructor's device for solving by hand: draw a clock. Find the maximum deadline in the table — that decides how many slots the clock has. If the maximum deadline is 3, divide the circle into 3 equal slots and think of the time running from 12 noon to 3 pm, with each job needing one hour (one unit of time). A job cannot be paused in the middle.

The rule: for each job, allot the last possible slot before its deadline — never the first available one. A job with deadline 2 could finish by 1 o'clock, but put it in the 1-to-2 slot anyway. The reason appears immediately in the example: an earlier slot may be needed by a job with a tighter deadline, a job that can only go there.

A note of caution the instructor added: the "clock" is not literally a clock — it is a data structure (a slot list); the clock is only an easy picture for understanding.

8.7.3 Worked Example 1

The numbering matters: the instructor pointed out that depending on how you number the rows you must state exactly which numbers you mean; here the original job numbers 1, 3, 5 are the ones picked.

8.7.4 Student Questions and Answers

A hypothetical variant came up next — what if a higher-profit job existed:

The time unit itself was questioned too:

And whether every task must be processed at all:

8.7.5 The Algorithm

If the clock picture is clear, the algorithm is easy — the "clock" is a list (slot array) and the algorithm is exactly what we did by hand.

1.  Arrange the jobs in decreasing order of profit
2.  Initialize the list (the "clock") with zeros: list[1..d_max] = 0
3.  P = 0                                        // total profit starts at zero
4.  for i = 1 to n:
5.      k = d_i                                  // start from the job's deadline position
6.      while k > 0:
7.          if list[k] == 0:                     // this slot is empty
8.              list[k] = i                      // place the job in this slot
9.              P = P + p_i                      // add the profit
10.             break                            // job is placed; move to the next job
11.         k = k - 1                            // slot taken; try the earlier slot

Trace the second sorted job (profit 15, deadline 2) through the loop: $k$ starts at 2, but list[2] is occupied by the first job, so the loop does not place it — it decrements $k$ to 1, finds list[1] empty, and places the job there. Decrementing continues down to 0 if needed; if no slot opens up, the job is simply not scheduled. The list is our clock: the deadline position $k$ indexes the slot, and an empty slot means the position is free.

8.7.6 Time Complexity

The time complexity is $O(n^2)$, and this one needs care. The sorting suggests $n\log n$ — and many students answer exactly that — but sorting is not the dominant term here. The outer loop runs $n$ times, and the inner while loop (over $k$) can also run up to $n$ steps in the worst case: if all jobs have the same (large) deadline, the $k$ loop keeps decrementing through occupied slots. One loop inside the other — the answer is n squared — gives

$$O(n^2)$$

The instructor's rule for this course: a time complexity answer without an explanation gets zero credit. The reason here is the inner $k$ loop — in extreme situations it can go all the way to $n$, so the two loops nest into $n^2$. $n\log n$ is the complexity of the sort alone, and that is not the whole algorithm.

8.8 Exam-Style Problem: Maximizing Bonus Marks

The instructor walked through an exam question from the same family, to show the pattern — and to show how wordy exam statements reduce to one simple demand.

8.8.1 The Question

A set of problems is given; each problem carries 1 mark, plus a bonus if it is submitted within a specified number of days (its deadline). The objective stated in the question is to maximize the bonus marks — the number of problems solved is not the objective.

Reducing the question: "arrange the table in the descending order of bonus." That is the entire task in one line. The instructor's advice for the exam: long paragraphs of question text conclude in maybe one line or half a line of actual demand — do not panic because there are many sentences; reduce and go. A similar practice variant shown alongside had nine jobs and a maximum deadline of seven, needing seven slots.

The exam data (as presented in class): the maximum deadline is 6, so the clock has 6 slots — 1 through 6. Each attempted problem earns its 1 mark plus its bonus when it is submitted within its deadline.

8.8.2 Walkthrough

Arrange the problems in decreasing order of bonus, then place them one by one in their last possible slot.

There is no limit on the number of problems — the question asked for maximum bonus, not for solving fewer problems, so extra problems without bonus are harmless. The instructor noted that you could even attempt all the problems and simply collect bonus only where the timing allows.

8.8.3 The Mistake and the Correction

During the walkthrough the instructor initially skipped problem 7, saying "you will not get any bonus" for it. A student spotted the problem.

The instructor acknowledged the error openly ("my bad, that was my mistake") and included problem 7. Two lessons for students: the last-slot rule is applied even when earlier slots are free (deadline 6 → slot 6, per the algorithm), and errors like this are exactly why the walkthrough should be checked against the table.

8.8.4 Student Questions

The two numbers answer two different questions. Total marks (19) counts every attempted problem's base mark plus its bonus; total bonus (15) counts only the bonus parts. If the question asked for maximum total marks, you would attempt more problems even when they carry no bonus (up to all of them, since slots remain free); if it asks for maximum bonus, you stop once no bonus remains obtainable. Reading which quantity the question names is the first step.

8.9 Applications of the Greedy Method

8.9.1 Classic Applications from the Textbook

The textbook lists a family of problems where greedy is a standard, successful approach:

• Portfolio optimization — selecting the best portfolio by some objective (covered in 8.4).
• Cutting stock problem — cutting standard stock into specified sizes while minimizing waste (covered in 8.4).
• Huffman encoding for text compression — a classic greedy algorithm; the textbook covers it and it is worth reading through. The greedy step is memorable: repeatedly combine the two least-frequent trees, a "merge the cheapest pair" rule that builds an optimal prefix code.
• Web auction optimization — explained in detail later in the textbook; reading it through is expected.
• k-means procedure in clustering — if you have seen data mining or machine learning, you know k-means uses the sum of squared distances: examples with the minimum sum of squared distances to a cluster center are grouped in one cluster, and larger distances push examples into different clusters. Conceptually, partitioning $n$ examples into $k$ clusters so as to minimize the sum of intra-cluster quantities and maximize the sum of inter-cluster quantities is an optimization problem — and it can be viewed as an application of the greedy idea.

The general pattern the instructor repeated: wherever maximize or minimize appears, an optimization problem is present, and greedy should be the first strategy considered — at least as a starting point.

Real-world: portfolio optimization (finance), cutting stock (paper and metal industries), download managers (networking), Huffman encoding (compression in ZIP, image formats), web auctions (e-commerce), and k-means (customer segmentation, image compression, recommendation systems).

Next session: interval scheduling — the second task-scheduling problem — and the remaining algorithm design techniques.

Exam Guidance Summary

Mid-semester feedback (heap sort question). The heap sort question from the regular exam is still being evaluated for some students, and many of you got zero on it.

Evaluation rules. Papers are evaluated by a team to ensure uniformity — the same question is graded by the same person for all students, and the most effective answer fetches the maximum credit; correct-but-less-effective answers get relatively less. All papers are reviewed by the instructor. The heap question that is still pending is being resolved.

Paper design. The regular paper felt very lengthy — that was deliberate. In an online exam, the paper is either made 90% tough or a bit lengthy; those are the only two tactics, so that you are challenged or run out of time to look elsewhere. You can write what you know.

Regular vs makeup. The makeup paper felt easier than the regular one, but the reason is pattern familiarity: after the regular paper you know what to expect. If the makeup had come first, it would have felt the same.

Difficulty and grading. The mid-semester was consciously made a bit tough so that you understand the complexity of the course. With a similar paper now, you would score much better — you know the question types and timing. The first time is always a shock. Grading is relative, and everyone is on the same page, so this helps all of you.

Final exam. The final exam is the full syllabus, with a marks split of 25/75 (as announced at the end of the session).

Time complexity answers. A time complexity answer without an explanation gets zero credit — for job sequencing with deadlines, explain the inner $k$ loop; for fractional knapsack, name the sorting step.

Reading long questions. Long exam statements are how you are tricked — extra words are added to an otherwise simple question ("instead of asking what data structure can be used, I will put some extra words and all of you panic"). Read fully and reduce: many paragraphs conclude in one line, like "arrange in descending order of bonus."

Problem-solving study advice. Problem solving is a gap: concepts are explained in class, but we do not get to learn through problem solving. The plan: one or two problems (maximum three) solved in class; the remaining ones posted as discussion topics on the course forum, where you discuss and solve together, with the instructor joining in when needed. You should also try to solve as many online and textbook questions as possible. The exam problems from greedy method and task scheduling are being uploaded for practice; a nine-job, maximum-deadline-seven variant is a good self-test.

Assignment 1 (greedy part). The second part of the assignment is a greedy design — that is the highlight; you may use any data structure you want, including a heap or a set (set is allowed because it was not explicitly covered in class) and Python's built-in ADTs. The design document must explain which data structure you used, the algorithm, and the time complexity. The input file format will be exactly the same as the example file — same labels, different values — and boundary conditions will be tested, so follow best coding practices: exit gracefully, with a message explaining the reason. The intention of the first part of the assignment is for you to implement the ADT yourself rather than only use a library implementation; you may use libraries if you cannot implement it yourself, but implementing it yourself is the point.

Key Industry Applications

• Bank cashier change-making — the coin problem that opened the session is a daily routine in retail; greedy works when the coin system has the greedy choice property (as with 25, 10, 5, 1). Vending machines and point-of-sale terminals run the same "largest coin first" rule every time they give change.
• Portfolio optimization — selecting the best portfolio (distribution of investment across sectors) to maximize expected returns while minimizing financial risk.
• Cutting stock problem — hardware factories cut standard-size stock material (paper rolls, sheet metal) into specified sizes while minimizing material waste.
• Internet download managers — data is broken into chunks and the server greedily packs chunks to fill the maximum size retrievable in one go.
• Huffman encoding — greedy algorithm for text compression, used in ZIP files and image formats; it repeatedly merges the two least-frequent symbols, packing more frequent symbols into shorter codes.
• Web auction optimization — greedy ideas behind auction mechanics, covered in detail later in the textbook.
• k-means clustering — partition $n$ examples into $k$ clusters minimizing intra-cluster (sum of squared distances) and maximizing inter-cluster separation; used in customer segmentation, image compression, and recommendation systems.
• Vacation backpack packing and night-before-exam study planning — the everyday greedy applications the class itself came up with: pack the highest value-per-weight item first, and study the highest-yield topic first.