11
Oct

Efficient Algorithms – Intro to Algorithms

Through this course, we looked at a number of different algorithms that we were trying to solve and for each of them, we worked out what their running time was so for finding the connectivity between two nodes in an undirected, unweighted graph, the running time is the number of nodes plus the number of edges. Finding the shortest path in a weighted, undirected connected graph took time m times the logarithm of n. Removing the minimum value of a heap is log n. For the problem of finding the shortest path between all pairs of nodes in a weighted graph is taking n続 times of at one of the algorithms. Okay, so you have a sense that these are considered to be pretty good algorithms. In fact, there’s some cases very good algorithms and you see that they’re all polynomially bounded, so there’s some polynomial in n and m that actually is larger asymptotically than all of these. And by large the algorithms for which–that we can actually solve in a reasonable amount of time, all seem to be in this category of having a polynomial bound. And that is lead theoreticians at least to find efficient in one particular way sometimes and that is that an algorithm is efficient if it has a polynomial bound on its running time. And a problem can be efficiently solved obviously if it has an efficient algorithm– that’s a reasonable question to ask–well, do our problems have efficient algorithms.