7 votes

Why do greedy coloring algorithms mess up?

I like @HallaSurvivor's intuition that coloring isn't a local property. From an Algorithms perspective, there are two properties to consider for when the greedy algorithm works. The first property is ...
user avatar
  • 13.5k
4 votes

Why do greedy coloring algorithms mess up?

The first thing to note is that everything depends on the heuristic you use to order the vertices. On the one hand, if you knew an optimal coloring, you could get the greedy algorithm to produce it: ...
user avatar
3 votes

Can we find the sum of a sorted array in O(logn) time?

The clear answer in the general case (sorted, but otherwise arbitrary) is "no." You must visit each list value in order to compute the sum (the sorting does not help). Thus it is an ${\cal ...
user avatar
3 votes

No Dijkstra and no BFS? What else is there?

Unfortunately, you are dealing with an $\mathsf{NP}$-hard problem, which is called the Traveling Salesman Problem. This means there is no efficient way to solve your problem. Thankfully, the graph is ...
user avatar
  • 878
1 vote

The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

The key idea is basically to use rules of exponents and the binary expansion of $b$ to speed things up. Consider $a^{b}$. Now write $b$ in binary. So: $$b = \sum_{i=0}^{\ell} a_{i}2^{i},$$ where $\ell ...
user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible