And you're being one of those accursed objectivists. Safety is hardly ever free. There is always some cost. A seatbelt can be uncomfortable but I wear one for safety. I could cook a steak to be well-done [but tough] but I prefer to take the risk and eat it rare [and juicy].
Eigenfaces research from the early nineties showed how part of the face can even be missing and it will still pick up the principal components of the face.
Also, there exists research that synthesizes faces in a vector space. For example, making a face look older or more feminine. If the police suspected you would grow/lose facial hair, they could synthesize what you might look like and put those images into the computer.
Newton's Method is slick, but remember that it does not guarantee convergence at all, especially in the presence of zero second derivatives. For 1-D, you can couple Newton with Regula Falsi. For higher dimensions, Levenberg-Marquardt works surprisingly well given that it heuristically chooses whether to behave more like Newton or more like gradient descent.
Finite elements are really more of a modeling technique. The interesting algorithms are then how to solve the differential equations over the finite elements.
To address some of your points: Hell yeah, recursion adds overhead. If it cannot be readily optimized into iteration (such as tail recursion), you need to maintain stack frames, allocate new local variables, etc. For tree recursions, such as quick sort (pick a pivot and resursively screw with each side), it is very hard to make the algorithm iterative without implicitly mimicing recursion or a stack.
Yes, I was not thinking perfectly when I claimed that a good quick sort implementation would use bubble sort when the chunks got small enough. They may use some other quadratic sort. But I am still willing to bet, that when tuned properly, using the bubble sort then is more efficient than using quicksort all the way down. I don't want to make any claims about performance on various architectures because it all boils down to freakly things such as cache hits. When I try to explain things for the layman, sometimes some details slip by, just waiting for the tight-assed dork to jump on.
By 2.blah, I was actually referring to the better results, rather than the boring divide-and-conquer method you cited. I recall results as good as n^2.23 or so, and I believe it is still unproven if matrix multiplication can be quadratic.
the quadratic algorithm for solving the Stable Marriage problem... I've been wanting to run it on a bunch of friends to see what bizarre matches came up... (run it twice, to be both male-optimistic and female-optimistic).
Sweepline algorithm for Voronoi diagrams. The sweepline (directrix) creates parabolas around the points (foci). If illustrated right, these look like breats and make for a humorous lecture.
Re:In place swap of two variables
on
Deep Algorithms?
·
· Score: 1
And most processors these days have a single machine instruction to do a swap for you. Of course their main motivation is atomicity for concurrency. But these days it may be better just to code swaps the old-fashioned way (with the temp variable). Besides having it being easier to read, the compiler would have a better chance figuring out exactly what you are doing and optimizing it for you. The compiler is your friend and you should not try to outsmart it.
There are many common randomized algorithms that have an expected running time that is linear but could potentially run forever. A simple example is the rejection method.
For example, suppose I had two coins and had to pick a random number from {1,2,3}. I could do the following scheme: Flip the two coins. If I got: HH I picked 1. HT I picked 2. TH I picked 3. TT Flip again.
We all know that Bubble Sort is O(n^2) while Quick Sort is O(n log n) average case [and O(n^2) worst case].
But remember that Big-O is for asymptotic behavior. When you have to swap small amounts of elements, bubble sort is by far faster. Why? For one, Quick Sort is recursive. In fact, a good quick sort implementation will do quick sort until the chunks get small enough and then do bubble sort on those.
There are also algorithms that do matrix multiplication in O(n^2.blah) time. The naive method is cubic. How come no one uses these fancy methods? Because they are a pain to implement and require n to be so large before they actually start performing better than the naive implementation.
discrete fast fourier transform
on
Deep Algorithms?
·
· Score: 2
Anything from Photoshop to cellphones benefits from fast signal processing. A little complex analysis turns an O(n^2) algorithm to O(n log n).
Oh, give me a break. The original poster wanted a 3-d map of the universe. By your argument, we don't even have true maps of Earth.
A map with "approximate" positions of the stars/galaxies would be plenty good. Oh no, the sun is off its true center by the diameter of an apple? I am wetting my pants! I can even see the difference of the sun's placement on my super-duper 1e10x1e10 resolution monitor (that provides the ultimate resolution for viewing porn: not only do I see all her parts, I see all the parts of the gonorrhea bacteria that she has).
The real interesting question is how does one navigate [in a user interface] around such a sparse map?
On that note, I heard Jim Gray give a talk the other day (5th Turing Award winner I've heard talk) on the database/scalability aspects of SSDS. Cool stuff.
I guess it may be tricky to analyze multiple wavelengths via CCDs... my guess is they would need some sort of splitter to guarantee that pixel (37,52) on the near-infrared CCD corresponds to the same light as pixel (37,52) on the far-infrared CCD. A quick google search seems to indicate
that some Australian dudes did some work with this stuff: news story
Steel crampons should work just fine on pavement, especially because pavement is still slightly textured. You'll still have to be good at flat-footing and balancing (put foot out, transfer center of mass to new foot, then stand on it). If you just step out without transfering your center of mass first, you'll wipe out.
Slashdot Mirror
And you're being one of those accursed objectivists. Safety is hardly ever free. There is always some cost. A seatbelt can be uncomfortable but I wear one for safety. I could cook a steak to be well-done [but tough] but I prefer to take the risk and eat it rare [and juicy].
The essence of life is taking calculated risks.
Is your kid the friggin' Bubbleboy?
I wouldn't be surprised that if kids' lives were severely restricted/controlled, they would be more inclined to commit suicide.
Thousands of kids die every year in car accidents. If we locked them up in their respective houses, they would not die in car accidents.
I'd give a thousand dead children a year to protect the basic liberties of the other hundred million.
Eigenfaces research from the early nineties showed how part of the face can even be missing and it will still pick up the principal components of the face.
Also, there exists research that synthesizes faces in a vector space. For example, making a face look older or more feminine. If the police suspected you would grow/lose facial hair, they could synthesize what you might look like and put those images into the computer.
ummm, most crypto involves taking gcds at some point or another.
But in this case you can place an upper bound on the number of steps. The next prime number after p (p>2) is guaranteed to occur before p!.
Newton's Method is slick, but remember that it does not guarantee convergence at all, especially in the presence of zero second derivatives. For 1-D, you can couple Newton with Regula Falsi. For higher dimensions, Levenberg-Marquardt works surprisingly well given that it heuristically chooses whether to behave more like Newton or more like gradient descent.
Finite elements are really more of a modeling technique. The interesting algorithms are then how to solve the differential equations over the finite elements.
That's the definition I go by. Basically the Church-Turing Thesis. Algorithm == Turing Machine.
To address some of your points:
Hell yeah, recursion adds overhead. If it cannot be readily optimized into iteration (such as tail recursion), you need to maintain stack frames, allocate new local variables, etc. For tree recursions, such as quick sort (pick a pivot and resursively screw with each side), it is very hard to make the algorithm iterative without implicitly mimicing recursion or a stack.
Yes, I was not thinking perfectly when I claimed that a good quick sort implementation would use bubble sort when the chunks got small enough. They may use some other quadratic sort. But I am still willing to bet, that when tuned properly, using the bubble sort then is more efficient than using quicksort all the way down. I don't want to make any claims about performance on various architectures because it all boils down to freakly things such as cache hits. When I try to explain things for the layman, sometimes some details slip by, just waiting for the tight-assed dork to jump on.
By 2.blah, I was actually referring to the better results, rather than the boring divide-and-conquer method you cited. I recall results as good as n^2.23 or so, and I believe it is still unproven if matrix multiplication can be quadratic.
the quadratic algorithm for solving the Stable Marriage problem... I've been wanting to run it on a bunch of friends to see what bizarre matches came up... (run it twice, to be both male-optimistic and female-optimistic).
Sweepline algorithm for Voronoi diagrams.
The sweepline (directrix) creates parabolas around the points (foci). If illustrated right, these look like breats and make for a humorous lecture.
And most processors these days have a single machine instruction to do a swap for you. Of course their main motivation is atomicity for concurrency. But these days it may be better just to code swaps the old-fashioned way (with the temp variable). Besides having it being easier to read, the compiler would have a better chance figuring out exactly what you are doing and optimizing it for you. The compiler is your friend and you should not try to outsmart it.
Actually Dijkstra's Algorithm is O(E log V) or O(V^2), depending on implementation. E is the number of edges and V is the number of vertices.
There are many common randomized algorithms that have an expected running time that is linear but could potentially run forever. A simple example is the rejection method.
For example, suppose I had two coins and had to pick a random number from {1,2,3}. I could do the following scheme:
Flip the two coins. If I got:
HH I picked 1.
HT I picked 2.
TH I picked 3.
TT Flip again.
If all algorithms, by definition, terminate, then the Halting Problem is easily decidable.
We all know that Bubble Sort is O(n^2) while Quick Sort is O(n log n) average case [and O(n^2) worst case].
But remember that Big-O is for asymptotic behavior. When you have to swap small amounts of elements, bubble sort is by far faster. Why? For one, Quick Sort is recursive. In fact, a good quick sort implementation will do quick sort until the chunks get small enough and then do bubble sort on those.
There are also algorithms that do matrix multiplication in O(n^2.blah) time. The naive method is cubic. How come no one uses these fancy methods? Because they are a pain to implement and require n to be so large before they actually start performing better than the naive implementation.
Anything from Photoshop to cellphones benefits from fast signal processing. A little complex analysis turns an O(n^2) algorithm to O(n log n).
It is so far-reaching.
linear programming, minimax game searches, network flow, primal-dual techniques for approximation algorithms......
Oh, give me a break. The original poster wanted a 3-d map of the universe. By your argument, we don't even have true maps of Earth.
A map with "approximate" positions of the stars/galaxies would be plenty good. Oh no, the sun is off its true center by the diameter of an apple? I am wetting my pants! I can even see the difference of the sun's placement on my super-duper 1e10x1e10 resolution monitor (that provides the ultimate resolution for viewing porn: not only do I see all her parts, I see all the parts of the gonorrhea bacteria that she has).
The real interesting question is how does one navigate [in a user interface] around such a sparse map?
On that note, I heard Jim Gray give a talk the other day (5th Turing Award winner I've heard talk) on the database/scalability aspects of SSDS. Cool stuff.
I guess it may be tricky to analyze multiple wavelengths via CCDs... my guess is they would need some sort of splitter to guarantee that pixel (37,52) on the near-infrared CCD corresponds to the same light as pixel (37,52) on the far-infrared CCD. A quick google search seems to indicate that some Australian dudes did some work with this stuff: news story
Steel crampons should work just fine on pavement, especially because pavement is still slightly textured. You'll still have to be good at flat-footing and balancing (put foot out, transfer center of mass to new foot, then stand on it). If you just step out without transfering your center of mass first, you'll wipe out.
i assume you've looked at Outdoor Research's
gloves and mitts? They have some that fold
back, have open fingertps, etc.
heh, i know some climbers that are too
embarrassed to take brand-new clothes/boots
to the mountains that they muddy them first.
What about chemical hand warmers? They seem
to be pretty popular.
I've never used them though -- my hands stay
pretty warm. Often, thin polypro liners are
all that I need when out in the mountains
in the winter.