Today I am continuing on with my review of a book on programming algorithms. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 7 I covered the knapsack problem. Today I cover the set covering problem, a look at efficient ways to identify the smallest number of entities required to cover a given set.

I decided to make this article different from the previous articles by focusing on the use of LLMs in coding. As we move into 2025 and beyond, programmers are going to be using LLMs more often to handle more tasks, so it begs the question why we should learn and understand algorithms, among other things. I would argue that, rather than memorizing specific algorithms, you should understand what algorithms exist, how they are used, and how to work with them. I will also use the solutions I have to highlight the problems with generating and using code you don’t understand.

Bhargava uses the example of listing a set of radio stations that cover the US, with some stations covering more than one state, and then writing an algorithm that uses greedy algorithms to find something close to an optimal solution without resorting to the time required to find the actual optimal solution. As part of the exercise, I asked several different LLMs to come up with both a list of states and a list of stations that cover all states, with some stations covering more than one state to give us some good data for the set covering problem. None of the LLMs managed to produce a set of radio stations that covered all the states, despite multiple prompts to do so. Here is a sample of what they produced that is broadly representitive of the whole:

const states = [
  "AL", "AK", "AZ", "AR", "CA", "CO", "CT", "DE", "FL", "GA",
  "HI", "ID", "IL", "IN", "IA", "KS", "KY", "LA", "ME", "MD",
  "MA", "MI", "MN", "MS", "MO", "MT", "NE", "NV", "NH", "NJ",
  "NM", "NY", "NC", "ND", "OH", "OK", "OR", "PA", "RI", "SC",
  "SD", "TN", "TX", "UT", "VT", "VA", "WA", "WV", "WI"
];

const stations = {
  KGO: ["CA"],
  KVCR: ["CA", "AZ"],
  KXLA: ["CA"],
  KYQ: ["AZ", "NV"],
  KMVT: ["AK"],
  KSLC: ["UT"],
  KJAZ: ["KS", "CO"],
  KFJC: ["KY", "TN"],
  KTKA: ["TN", "AR"],
  KFMB: ["OH", "IN"],
  KEZK: ["NE", "SD"],
  KRSC: ["MI", "IL"],
  KSPN: ["IL"],
  KABC: ["CA"],
  KYE: ["NY", "PA"],
  KQED: ["CA"],
  KCUR: ["KS"],
  KBRA: ["TX", "OK"],
  KXAS: ["TX"],
  KAMC: ["AZ"],
  KGEM: ["NV"],
  KXOL: ["AZ"],
  KOZK: ["CO"],
  KELO: ["UT"],
  KVLY: ["VA"],
  KQCD: ["MD"],
  KBAL: ["TX"],
  KFAN: ["IA", "IL"],
  KWTV: ["OK", "KS"],
  KXFL: ["FL"],
  KFOG: ["NV"],
  KMCC: ["AZ"],
  KRLA: ["TX"],
  KABC: ["CA"],
  KCAS: ["CO"],
  KEZI: ["IL"],
  KFTX: ["MN"],
  KWOW: ["IA", "NE"],
  KFTC: ["NE"],
  KHOK: ["MI", "OH"],
  KMOT: ["OH"],
  KNBC: ["NY"],
  KVCR: ["CA"],
  KBEL: ["TX"],
  KFBN: ["FL"],
  KQDX: ["NV"],
  KYWJ: ["AZ", "CO"],
  KFOR: ["IL"],
  KEZE: ["MI", "OH"],
  KFTX: ["MN"]
};

A nice looking list, but it doesn’t cover anywhere near all of the states. Remember the strawberry question, where LLMs can’t tell you how many r’s there are in the sord strawberry? This is the same kind of problem, and we know LLMs struggle with this sort of task. It also didn’t understand that radio station call signs in the eastern half of the US start with W, not K, but I didn’t try to correct that with a prompt.

Let’s look at algorithms that solve the set covering problem.

Here is the solution that Microsoft’s phi4 model generated. Note that I had to prompt it to use abbreviations for states, and it used Set() in JavaScript for the stations, but it also failed to generate sample data for stations that covered all fifty states. Like the qwen.25-coder model, phi4 wrote an algorithm that results in an error if all fifty states are not covered in the data. I had to prompt it to fix the error, which it did.

Here is the algorithm that Grok generated. It handled the potential error condition of not covering all the states without prompting, but when it hit that condition it failed to produce any data. Note that unlike the other algorithms, it doesn’t return anything, just displays the data.

Here is the algorithm that Qwen 7B produced. It needed prompting to fix errors. Ultimately I stopped trying to get it to produce a better version, as it got worse over a few attempts.

There are several takeaways from this exercise that I would like to highlight. The first is that LLMs are not perfect or uniform in their operation. There are many ways to solve the set covering problem, and you can see variation in the solutions these models produced.

The second takeaway is that you need to be able to read the code models produce so you can understand what they are doing, what they are not doing, and potentially find bugs they might have in the code. For instance, whenever I see a while loop, I immediately check to see if there could be a case where the while condition is always true, because then the code is likely to produce either an infinite loop or some other error condition.

The third takeaway is that just because an algorithm solves your problem in some way doesn’t mean it represents an optimal solution for your needs. In the case of the Grok solution, it didn’t return anything from the function, and in all likelihood in a production environment, I want that function to return the data in a useful format. In fact, I probably want it to return several things, not just the list of stations in the solution.

And that’s the fourth takeaway. You can, of course, prompt the model to revise its solution, but at a certain point you may find that modifying the code it produced by hand is faster than asking it to change it for you. In the case of the Qwen solution, I manually added the console.log statement to note if it failed to find a bestStation on a loop iteration, because that means it failed to cover all of the states.

But what about the solutions themselves? The basic idea in a greedy algorithm is that you find the best solution at each iteration of the loop, and you find an approximate solution using that strategy. Looping over the stations and selecting the station that covers the most uncovered states for each iteration of the while loop gets you close to an optimal solution, if you the optimal solution.