Archive for March, 2008

David Gale

My favorite math professor has, over the course of two semesters, introduced his classes to many prominent mathematicians through brief stories about their lives. Each recounting reminded us of the importance of the scientist and the frailty of their existence. From mild psychosis to paranoia, from greed to altruism, from lives filled with joy and happiness to those wrecked by tragedy and sadness, we have learned that the perfection of mathematics springs from the imperfection of the human condition. The question is not why, but how.

So, it is to be expected that I am alert for translations to the highest sphere…..

Via the Wall Street Journal:

David Gale (1921 – 2008)

Mathematician Who Loved Games Helped Unknot a Pairing-Up Puzzle

This spring’s medical-school graduates have just completed the nerve-wracking “match day,” in which they rank the hospitals where they would like to do their residencies and bite their fingernails until they find out where they will be placed.

Few realize that the algorithm pairing them with a teaching hospital was developed by a game-loving University of California, Berkeley, mathematics professor, David Gale.

[Gale]
David Gale

Enamored of recreations from sudoku to the roller derby, Mr. Gale, who died March 7 at age 86, was a game-theory specialist often mentioned alongside a onetime collaborator, Nobel laureate John Nash, as a giant in the field.

Mr. Gale’s best-known contribution came as a solution to the “stable-marriage problem,” the question of how best to pair up an equal number of men and women, each of whom has his or her own preferences for a mate.

In a 1962 paper written with University of California, Los Angeles, professor Lloyd Shapley, Mr. Gale proposed a multistage process beginning with each man asking his top choice whether she will have him. Women with multiple offers tell one of the suitors “maybe” and all the others “no.” The rejected men move on to make offers to other women. If a woman gets a new offer from someone she likes better, she gives him a “maybe” and tells the earlier “maybe” that he is now a “no.”

After many rounds, as the rejected men turn to women who didn’t get any offers at first, everyone has paired up. Then each woman turns to her man and says “yes.”

Although offered as an academic solution to a theoretical problem, Mr. Gale’s paper proved a remarkably fertile contribution to real-world cases of “two-sided matching” such as the medical-residency example, where hospitals are choosing students at the same time as students are choosing hospitals. A related algorithm is used by school systems in Boston and New York to allocate slots in high schools.

“David’s work will be remembered for generations to come,” says Alvin E. Roth, a professor of economics at Harvard. Mr. Roth helped design the school-choice systems and has lately been working to apply the theory to the allocation of scarce kidney donations.

Mr. Gale inspired headlines as recently as last year when he challenged studies reporting that men had more lifetime heterosexual partners than women, a situation he labeled a logical impossibility.

Mr. Gale studied math at Princeton, where he was a doctoral candidate alongside Mr. Nash. He was known for devising elegant puzzles and games. Among these was Chomp, in which players take cookies from a board until a final, poison cookie must be removed by the loser. Simple enough for a preschooler to master, the game turns out to have mathematical subtleties that have inspired dozens of academic papers.

At dinner time, says his daughter, Katharine Gale, “he would ask us if we all toasted, how many clinks would there be. He would write matrices all over napkins.”

Once, in a flash of inspiration, “he wrote all over an airplane ticket. The airline refused to honor it and he had to buy a new one,” she says.

“He thought math was beautiful, and he wanted people to understand that,” Ms. Gale says.

–Stephen Miller

 

 

Thank you, Professor Gale.

Advertisements

Turing’d?

Well said……

Over the years I’ve had many opportunities to work with professionals from various fields. In every endeavor, computer technology is utterly transformative. But not every field gets this. Some scientists, licencsed experts, and professionals are allergic to new technology.

I had an epiphany recently on why some varieties of professionals are more welcoming of disruptive technology than others. I realized the types of pros who are most eager to employ the latest technology are those fields which have already been Turing’d.

analyticalengine.jpg

We have this long list of tasks and occupations that we humans believe only humans can do. Used to be things like using tools, language, painting, playing chess. Now, one by one they get Turing’d. A computer beats them. Does it better…

Computer scientists are great to work with, because in general they are completely fearless. They were Turing’d long ago. They grok that many of the tasks they used to do can be done much better by computers. On the other hand, doctors as a rule are loathed to accept new technology because what they do is hard to delegate to computers. Ditto for a lot of biologists.

Within biology there are certain fields that have already been Turing’d. For instance, phylogeny, the study of taxonomic trees, how different species are related to each other. Figuring out phylogenetic trees turns out to be something computers can do better than even the smartest, most learned humans — even though nobody believed this only a little while ago. So phylogenists are Turing’d and very open to new ways of doing things…

Once you are Turing’d it is much easier to believe other occupations which we humans used to do uniquely, can be done by computers. You tend to be open to disruptive technology in all parts of your life.

Have you been Turing’d?

From Kevin Kelly…

Work Math

We haven’t covered this is any of my math classes, yet, but experience teaches that the proof exists and can be easily written:

Simple Math….

The Big-O

Here I am, a man of middle-age, thinking that I know what the Big O is………

Little did I know…..

images3.jpg

In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithm‘s usage of computational resources (usually running time or memory). It is also called Big Oh notation, Landau notation, Bachmann-Landau notation, and asymptotic notation. Big O notation is also used in many other scientific and mathematical fields to provide similar estimations.

Silence The Thoughts

In calculus class today, while the professor was explaining yet another step in the process of understanding L’Hospital’s Rule and indeterminate forms, she suddenly stopped and looked out over the class. “Silence the thoughts, and just work the problem in front of you, one step at a time. Don’t let your mind get too carried away……”

Silence the thoughts……….

The Spy Among Us

Everybody (at least those about my age) can remember stories of espionage that involved some daredevil using a variety of skills to gain access to important information held by the enemy. Cary Grant in Monaco, in a palace, at night……dodging nefarious enemies to steal information for the good guys.

So, today in class, comes a student that I thought had dropped. Hasn’t been around for the last week.

images2.jpg

First thing I notice is that he has a digital camera. As the class fills, but before the professor arrives, he turns around and asks the girl sitting behind him if he can look at her notes for the last week. She assents, hands over her notebook, and he proceeds to take pictures of every page. Unbelievable……….

He’s gonna go home, download to his laptop, and save the notes. Then he’s gonna print some hard copies (or not).

How cool is that……….

Cash Register

Another very tough week on the programming front. With the assistance of the ever patient and helpful graduate assistant, P$(@$(&k, I managed to cobble together some workable code. Below is the driver for the assignment (Coin and CashRegister classes used, not displayed here…why further embarass myself?):

public class CashRegisterDriver
{
public static void main(String[] args)
{
//Create coin set by integer value and type name
Coin penny = new Coin(1, “penny”);
Coin nickel = new Coin(5, “nickel”);
Coin dime = new Coin(10, “dime”);
Coin quarter = new Coin(25, “quarter”);

Scanner in = new Scanner(System.in);

CashRegister register = new CashRegister();

//Input a purchase price amount for class CashRegister
//Input via Scanner
System.out.print(“Enter price: “);
int price = in.nextInt();
register.recordPurchase(price);

//Input payment amount for class CashRegister
//Create variable names for each coin type for payment method
System.out.print(“Please enter your payment as requested: \n”);
System.out.print(“Enter # of quarters: “);
int quarters = in.nextInt();
register.enterPayment(quarters, quarter);
System.out.print(“Enter # of dimes: “);
int dimes = in.nextInt();
register.enterPayment(dimes, dime);
System.out.print(“Enter # of nickels: “);
int nickels = in.nextInt();
register.enterPayment(nickels, nickel);
System.out.print(“Enter # of pennies: “);
int pennies = in.nextInt();
register.enterPayment(pennies, penny);

//Alert user to transaction values
System.out.print(“The price is: ” + register.purchase + “\n”);
System.out.print(“You have paid a total of: ” + register.payment + “\n”);
System.out.print(“Your change due is: ” + (register.payment – register.purchase) + “\n”);

//Create variable name for change method for each coin type created above
int q = register.giveChange(quarter);
register.giveChange(quarter);
System.out.print(“Quarters returned: ” + q + “\n”);
int d = register.giveChange(dime);
register.giveChange(dime);
System.out.print(“Dimes returned: ” + d + “\n”);
int n = register.giveChange(nickel);
register.giveChange(nickel);
System.out.print(“Nickels returned: ” + n + “\n”);
int p = register.giveChange(penny);
register.giveChange(penny);
System.out.print(“Pennies returned: ” + p + “\n”);

}
}

Any programmer that reads this will note that all monies and transactions are integer type…..I can’t figure out how to express an integer value in double format, nor can I figure out how to cast a double to an integer. If you are in my class, please don’t get us both in trouble by copying/using this doggerel.


“Life’s hard, son. It’s harder when you’re stupid.” — The Duke.

Education is a companion which no misfortune can depress, no crime can destroy, no enemy can alienate,no despotism can enslave. At home, a friend, abroad, an introduction, in solitude a solace and in society an ornament.It chastens vice, it guides virtue, it gives at once grace and government to genius. Without it, what is man? A splendid slave, a reasoning savage. - Joseph Addison
The term informavore (also spelled informivore) characterizes an organism that consumes information. It is meant to be a description of human behavior in modern information society, in comparison to omnivore, as a description of humans consuming food. George A. Miller [1] coined the term in 1983 as an analogy to how organisms survive by consuming negative entropy (as suggested by Erwin Schrödinger [2]). Miller states, "Just as the body survives by ingesting negative entropy, so the mind survives by ingesting information. In a very general sense, all higher organisms are informavores." - Wikipedia

Blog Stats

  • 30,521 hits