@aditya.bhargava: Thank you for your amazing book. Could you help us with this?
1. In the radio stations problem time table (Page 152). I'm confused, similar to OP and the user above me, as to
why use O(2^n) and not n! to calculate the Exact Algorithm's time. As shown in
Table Page 152. Thank you!
UPDATE: I believe the Big O should be 2^n as explained in page 165. Please correct me if I'm wrong
For anyone interested. For "Set-Covering" problems, the Set containing all possible subsets/permutations (including the empty set and the whole Set itself) is called the
Power Set as the books says.
Now, the number of all possible subset is calculated using
2^n where n is the number of elements in the Set.
At first, I didn't get that
this is a given formula you have to trust, mathematicians came up with this.
In this case,
n is the number or Radio Stations. Eg. For 3 Radio Stations, there are 8 subsets (or 8 different arrangements of the Radio Stations).
Take a look at
Power Set(wikipedia). In the "Example" section, the exercise of a Set with 3 elements {x, y, z} = 8 subsets.
For many other NP-Complete problems, the Big O is O(n!) or factorial, as explained in the traveling-salesperson problem in page 157.
See attached image for a proposed fix in the table 9.17.
UPDATE: YOU COULD IGNORE THIS QUESTION.
2. Is "Simple Search" a Greedy Algorithm?
I say that because it has to check ALL possible solutions... same as with Breadth-First Search.
What makes me doubt if it is Greedy is that Simple Search is O(n) which is kind of fast... or at least it is not as slow as O(n log n) or O (n^2)[
UPDATE FOR ANYONE INTERESTED:
I thought Simple Search was a Greedy Algorithm bc it had to check all possible solutions. But actually, a Greedy Algorithm is one that "approximates the answer" (which could be wrong or not the best), and not one that checks EVERY possible solution.
Simple Search checks all the solutions, but IT IS NOT APPROXIMATING THE ANSWER. It always gets the correct answer.
Another thought: BFS and Dijkstra are Greedy. Why? could it be because they get a Local Optimal to reach a Global Optimal. Thereby, shortening the steps needed to reach a solution. BEAR IN MIND that these 2 algorithms, they get the CORRECT ANSWER, THEY DON'T GET AN APPROXIMATION OF THE ANSWER LIKE OTHER GREEDY ALGORITHMS.
Here's a slightly different definition of "Greedy Algorithm" that involves no-backtracking:
Last Edit: Mar 29, 2017 @ 10:43 PM
Last Edit: April 11, 2017 - Added definition Stack Exchange's definition of Greedy Algorithm.