Sound of Sorting: 15 sorting algorithms in 6minutes

Dictionary of Algorithms and Data Structures

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions. Algorithms include common functions, such as Ackermann’s function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area and by type. The two-level index has a total download 1/20 as big as this page.

Check it out on http://xlinux.nist.gov/dads/ 

SoundWave: Using the Doppler Effect to Sense Gestures

Do Kinect-like things on your computer, but without the Kinect: the technique uses your speakers and microphone to sense what gesture you are making.
(quote Bramus!)


(via)

Gesture is becoming an increasingly popular means of interacting with computers. However, it is still relatively costly to deploy robust gesture recognition sensors in existing mobile platforms. We present SoundWave, a technique that leverages the speaker and microphone already embedded in most commodity devices to sense in-air gestures around the device. To do this, we generate an inaudible tone, which gets frequency-shifted when it reflects off moving objects like the hand. We measure this shift with the microphone to infer various gestures. In this note, we describe the phenomena and detection algorithm, demonstrate a variety of gestures, and present an informal evaluation on the robustness of this approach across different devices and people.

Find out more on: http://research.microsoft.com/en-us/um/redmond/groups/cue/soundwave/

Josephus problem

At school we started with a basic algorithm called the Josephus problem.

A short explanation from Wikipedia:

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

Here is my short C++ version. The benchmarking was just a test and should actually replaced with something else 😛

/*
 * File:   main.cpp
 * Author: Teusje
 *
 *
 */

#include <stdlib.h>
#include <iostream>
#include <list>
#include <time.h>
using namespace std;

int josephus1(int n, int k) {
    list<int> myList;
    list<int>::iterator it;
    list<int>::iterator itNext;

    // filling myList with values
    for (int i = 1; i <= n; i++) {
        myList.push_back(i);
    }

	// do untill n == 1, n-- every iteration
    for (it = myList.begin(); n-- != 1; it = itNext) {

		// times to skip
        for (int i = 1; i < k; i++) {
            ++it;
			// reset if we are at the end
            if (it == myList.end()) {
                it = myList.begin();
            }
        }
        itNext = it;
		// placing the iterator at the right position otherwise we have problems when we remove
        ++itNext;

		// removing the value
        myList.erase(it);

		// reset the iterator if we are at the end
        if ( itNext == myList.end()) {
            itNext = myList.begin();
        }
    }
    // return value
    return *it;
}

/*
 *
 */
int main(int argc, char** argv) {
    // Benchmark (very basic and undetailed)
    // http://www.cplusplus.com/reference/clibrary/ctime/difftime/
    time_t start,end;
    double dif;
    time (&start);
    //--Benchmark

    int result = josephus1(10, 2);

    //Benchmark
    time(&end);
    dif = difftime(end, start);
    //--Benchmark

    cout << endl << "Result: " << result << endl;
    printf("\nTime needed: %.21f \n", dif);

    return (EXIT_SUCCESS);
}

Got a better solution? (and yes there are better solutions ;)) Feel free to post it.

/*
* File:   main.cpp
* Author: Wouter
*
* Created on 10 februari 2010, 21:05
*/

#include <stdlib.h>
#include <iostream>
#include <list>
#include <time.h>
using namespace std;

int josephus1(int n, int k) {
list<int> lijst;
list<int>::iterator it;
list<int>::iterator volgende;

// lijst opvullen met waarden
for (int i = 1; i <= n; i++) {
lijst.push_back(i);
}

// doen tot n == 1 is, n telkens met 1 verminderen
for (it = lijst.begin(); n– != 1; it = volgende) {

// aantal keer doorschuiven
for (int i = 1; i < k; i++) {
++it;
// resetten als we op het einde zijn
if (it == lijst.end()) {
it = lijst.begin();
}
}
volgende = it;
// iterator al goedzetten, anders probleem bij verwijderen
++volgende;

// verwijderen
lijst.erase(it);

// resetten als we op het einde zijn
if ( volgende == lijst.end()) {
volgende = lijst.begin();
}
}
// waarde terug geven
return *it;
}

/*
*
*/
int main(int argc, char** argv) {
//Benchmark
// http://www.cplusplus.com/reference/clibrary/ctime/difftime/
time_t start,end;
double dif;
time (&start);
//–Benchmark

int result = josephus1(10, 2);

//Bencmark
time(&end);
dif = difftime(end, start);
//–Benchmark

cout << endl << “Resultaat: ” << result << endl;
printf(“\nTijd nodig: %.21f \n”, dif);

return (EXIT_SUCCESS);
}