Tuesday, March 22, 2011

The story of Sissa and Moore

NP-complete problems
(Chapter 8 by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani )

Source: Algorithms (2007 McGraw-Hill Higher Education) by
Sanjoy Dasgupta, University of California - San Diego
Christos Papadimitriou, University of California at Berkeley
Umesh Vazirani, University of California at Berkeley

Note: This book evolved over the past ten years from a set of lecture notes developed while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego.

- http://cseweb.ucsd.edu/~dasgupta/book/index.html
- http://highered.mcgraw-hill.com/sites/0073523402/

The story of Sissa and Moore

Ref.: www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf

"According to the legend, the game of chess was invented by the Brahmin Sissa to amuse and teach his king. Asked by the grateful monarch what he wanted in return, the wise man requested that the king place one grain of rice in the rst square of the chessboard, two in the second, four in the third, and so on, doubling the amount of rice up to the 64th square. The king agreed on the spot, and as a result he was the rst person to learn the valuable-albeit humbling-lesson of exponential growth. Sissa's request amounted to
264-1 = 18,446,744,073,709,551,615 grains of rice, enough rice to pave all of India several times over!
All over nature, from colonies of bacteria to cells in a fetus, we see systems that grow exponentiall-for a while. In 1798, the British philosopher T. Robert Malthus published an essay in which he predicted that the exponential growth (he called it "geometric growth") of the human population would soon deplete linearly growing resources, an argument that in uenced Charles Darwin deeply. Malthus knew the fundamental fact that an exponential sooner or later takes over any polynomial.

In 1965, computer chip pioneer Gordon E. Moore noticed that transistor density in chips had doubled every year in the early 1960s, and he predicted that this trend would continue. This prediction, moderated to a doubling every 18 months and extended to computer speed, is known as Moore's law. It has held remarkably well for 40 years. And these are the two root causes of the explosion of information technology in the past decades: Moore's law and efficient algorithms.

It would appear that Moore's law provides a disincentive for developing polynomial algorithms. After all, if an algorithm is exponential, why not wait it out until Moore's law makes it feasible? But in reality the exact opposite happens: Moore's law is a huge incentive for developing ef cient algorithms, because such algorithms are needed in order to take advantage of the exponential increase in computer speed.

Here is why. If, for example, an O(2n) algorithm for Boolean satis ability (SAT) were given an hour to run, it would have solved instances with 25 variables back in 1975, 31 variables on the faster computers available in 1985, 38 variables in 1995, and about 45 variables with today's machines. Quite a bit of progress-except that each extra variable requires a year and a half's wait, while the appetite of applications (many of which are, ironically, related to computer design) grows much faster. In contrast, the size of the instances solved by an O(n) or O(n log n) algorithm would be multiplied by a factor of about 100 each decade. In the case of an O(n2) algorithm, the instance size solvable in a fxed time would be multiplied by about 10 each decade. Even an O(n6) algorithm, polynomial yet unappetizing, would more than double the size of the instances solved each decade. When it comes to the growth of the size of problems we can attack with an algorithm, we have a reversal: exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast! For Moore's law to be refected in the world we need efficient algorithms.

As Sissa and Malthus knew very well, exponential expansion cannot be sustained indefinitely in our nite world. Bacterial colonies run out of food; chips hit the atomic scale. Moore's law will stop doubling the speed of our computers within a decade or two. And then progress will depend on algorithmic ingenuity-or otherwise perhaps on novel ideas such as quantum computation, explored in Chapter 10.

New: S. Dasgupta, Two faces of active learning, Theoretical Computer Science, 412(19): 1767-1781, 2011
- http://cseweb.ucsd.edu/~dasgupta/papers/twoface.pdf

Algorithmic Thinking
"Algorithms are the engines of a great majority of systems, natural and artificial alike. This course introduces algorithmic thinking as a discipline for reasoning about systems, taming their complexities, and elucidating their properties. Algorithmic techniques, along with their correctness and efficiency, will be taught through reasoning about systems of interactions, such as markets, that are ubiquitous in our highly connected world."
(Luay Nakhleh, Course: Algorithmic Thinking, COMP 182, www.clear.rice.edu/comp182/)

Laboratory activities are essential to learning activities. Teachers are required to combine computer more effectively as teaching classes with laboratory classes which actually ends a cycle to solve computer problems: the problem --> the mathematical model --> the algorithm --> the program --> computer --> solutions -->check the resulting. There are equivalent Algorithm-Program-Computer System and operations carried out by the algorithm in cyberspace (virtual), that made the Computer System operations by executing the corresponding algorithm program. Algorithm to simulate all operations will be triggered by launching the appropriate program execution algorithm (Vlada, 2004): Abordarea modernă a conceptului de algoritm, CNIV-2004, Noi tehnologii de E-Learning, Conferinţa Naţională de Învăţământ Virtual, Software Educaţional, Ediţia a II-a, [online], Facultatea de Matematică şi Informatică, Universitatea din Bucureşti , Editura Universităţii din Bucureşti,
Ref.: http://fmi.unibuc.ro/ro/pdf/2004/cniv/gandirealgoritmica.pdf

Monday, March 21, 2011

Professor Emeritus Donald E. Knuth

Ph.D. Donald E. Knuth, Professor Emeritus of The Art of Computer Programming at Stanford University

The Art of Computer Programming

"At the end of 1999, these books were named among the best twelve physical-science monographs of the century by American Scientist, along with: Dirac on quantum mechanics, Einstein on relativity, Mandelbrot on fractals, Pauling on the chemical bond, Russell and Whitehead on foundations of mathematics, von Neumann and Morgenstern on game theory, Wiener on cybernetics, Woodward and Hoffmann on orbital symmetry, Feynman on quantum electrodynamics, Smith on the search for structure, and Einstein's collected papers."
- Ref.: 100 or so Books that shaped a Century of Science by Phylis Morrison, www.americanscientist.org/

-Information and Communication Technologies 2010, The BBVA Foundation Frontiers of Knowledge Award: Donald E. Knuth

- Books in Print by Donald E. Knuth: www-cs-staff.stanford.edu/~knuth/books.html
1. Volume 1: Fundamental Algorithms, Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)
2. Volume 2: Seminumerical Algorithms, Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)
3. Volume 3: Sorting and Searching, Second Edition (Reading, Massachusetts: Addison-Wesley, 1998)
4. Volume 4A: Combinatorial Algorithms, Part 1 (Upper Saddle River, New Jersey: Addison-Wesley, 2011)
5. Volume 5: Syntactic Algorithms, in preparation.
* 9. Lexical scanning (includes also string search and data compression)
* 10. Parsing techniques
Estimated to be ready in 2020.

Note 1: Translations of previous editions:
Romanian translation by Adrian Davidoviciu, Adrian Petrescu, Smaranda Dimitriu, and Paul Zamfirescu, Tratat de programarea calculatoarelor, V. 1: Algoritmi fundamentali (Bucharest: Editura tehnica, 1974), 676pp.

- www-cs-staff.stanford.edu/~knuth/
- www-cs-staff.stanford.edu/~knuth/taocp.html
- MMIXware: A RISC Computer for the Third Millennium, by Donald E. Knuth (Heidelberg: Springer-Verlag, 1999)
- The TeXbook, by Donald E. Knuth (Reading, Massachusetts: Addison-Wesley, 1984
- Computers & Typesetting (A-F), (Reading, Massachusetts: Addison-Wesley, 1984)
- Obs.: TeX is a trademark of the American Mathematical Society.
METAFONT is a trademark of Addison-Wesley Publishing Company, Inc.

.... The Art of Computer Programming (TAOCP) ...

Professor John McCarthy

Ph.D. John McCarthy (1927-2001), Professor Emeritus of Computer Science at Stanford University.

John McCarthyis an American computer scientist and cognitive scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence (AI). He was responsible for the coining of the term "Artificial Intelligence" in his 1955 proposal for the 1956 Dartmouth Conference and is the inventor of the Lisp programming language.

- http://www-formal.stanford.edu/jmc/
"It is reasonable to hope that the relationship between computation and mathematical logic will be as fruitful in the next century as that between analysis and physics in the last. The development of this relationship demands a concern for both applications and mathematical elegance." (John McCarthy, 1963).

- Patrick J. Hayes and Leora Morgenstern, On John McCarthy’s 80th Birthday, in Honor of His Contributions, AI Magazine Volume 28 Number 4 (2007); http://www.aaai.org
- Actions and Other Events in Situation Calculus, by John McCarthy, 2002. Published in the Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-02). San Francisco: Morgan Kaufmann Publishers. This paper extends the original McCarthy-Hayes situation calculus in several significant ways, in order to handle natural events, concurrency, and combined linear and branching time.
- History - AI and CS, www-formal.stanford.edu/jmc/history/

Professor Zohar Manna

Ph.D. Zohar Manna
Professor of Computer Science at Stanford University

- www.cs.stanford.edu/~zm/
The STeP (Stanford Temporal Prover) system supports the computer-aided formal verification of reactive, real-time and hybrid systems based on their temporal specification.

- Aaron R. Bradley and Zohar Manna. The Calculus of Computation: Decision Procedures with Applications to Verification. Springer, 2007.

- Zohar Manna, On-line papers (in reverse chronological order):

- Manna and Calogero G. Zarba, Combining Decision Procedures Zohar, Stanford University, [online], www.infsec.ethz.ch/education/ws0506/decproc/combining.pdf

- Zohar Manna's Doctoral Descendents and Ancestors: www.cs.tau.ac.il/~nachumd/Ztree.html

- Zohar Manna's Doctoral Descendents: http://theory.stanford.edu/~srirams/Zohar/Ztree.html

Thank the professor that in 1977 sent me a package post. The package containing the book published in 1974 and several scientific articles.We used the book to the development paper license. Thank you very much sir!

Trebuie sa-i multumesc si astazi domnului profesor Manna pentru ca in anul 1977 mi-a trimis prin colet postal cartea sa "Mathematical theory of computation. McGraw Hill, 1974" publicata in anul 1974. Eram student si am folosit tot ce mi-a trimis la elaborarea lucrarii mele de licenta. Trebuie sa recunosc ca am fost foarte mirat de amabilitatea sa, tinand seama ca Romania este despartita de U.S.A printr-un ocean foarte mare.

Saturday, March 5, 2011

Walter Zorn's Famous Web Scripts

Walter Zorn, Munich, Germany
Update: A Developer I Admire — Walter Zorn, http://www.useragentman.com/blog/2012/

Walter Zorn has developed a JavaScript Vector Graphics Library (wz_jsgraphics.js), Javascript DHTML API, Walter Zorn's ToolTip Library (Tooltips 1.4.11), WZGrapher Function Grapher (wzgrapher_e.zip, 2006). [Copyright (c) 2002-2009 Walter Zorn]

1. About Walter Zorn
2. JavaScript vector-draw library
3. Advanced DHTML, JavaScript (gualtierozorni.altervista.org)
4. Class WalterZornTips (http://www.jarvana.com)

1. About Walter Zorn

"I recently stumbled across a site that contains a small treasure trove of incredibly useful code for Web applications. The site is walterzorn.com, the home of (as you might guess) one Walter Zorn, a software developer and recumbent bicycle enthusiast from Munich, Germany. I found Walter’s site because I was looking for a tool tip system written in JavaScript for my wife’s apparel company Web site and I found Walter’s cross-browser JavaScript library (to see how I used it go here and click on the “Why” link). This is one of the nicest tool tip libraries I’ve seen. It runs under Gecko Browsers (Firefox, Mozilla, Netscape 6+, Galeon and others), IE 5+, Opera 7+, Konqueror, and Safari, and features automatic bubble width, inclusion of any HTML content including formatting, images, breaks, tables, links, etc., and it supports extensions." Web Applications Alert By Mark Gibbs, Network World, September 12, 2007

Walter also offers some other excellent tools that I have yet to use “in anger”. These include an amazing DHTML JavaScript library that implements Drag & Drop for Images and Layers, a JavaScript VectorGraphics library, and a JavaScript Online Function Grapher that can do some impressive math is under development.

Ref.: A Tribute to Walter Zorn and His Famous Web Scripts,

- https://sites.google.com/a/balancegames.org/zorn/


• Roland says:
Sorry, but it’s true. Walter Zorn is dead. He died in may or april 2009.

Posted on July 19th, 2009 at 2:17 pm
• Norbert says:
I am an old friend of Walter, but left for Australia 7 years ago. Walter and I spend weeks discussing recumbents before he built the Kreuzotter. I failed to contact him. Is it true he died? I am devastated. Can you email to me please, have you got details?

Posted on November 5th, 2009 at 4:14 pm
Source: www.recumbentblog.com/2009/06/29/sometimes-you-just-want-to-know-more/

Walter Zorn Sites (www.walterzorn.com)

• walterzorn.com (Archive) http://web.archive.org/web/20080109034423/http://www.walterzorn.com/
• kreuzotter.de (Archive)
Javascript DHTML API by Walter Zorn, http://www.walterzorn.com, Copyright (c) 2002-2003 Walter Zorn
- Walter Zorn Tooltips extension

Walter Zorn's website no longer exists. Word has reached us that he is deceased. We are deeply in his debt!
Source: http://www.virtlab.com/

2. JavaScript vector-draw library

Courtesy of Walter Zorn, you can now use JavaScript to draw objects on your web pages. Fire up your JavaScript Editor, follow the instructions below and you will be drawing shapes on your web pages in no time. (http://www.c-point.com)

Walter Zorn - wz_jsgraphics.js (JavaScript Vector Graphics Library)
- www.facebook.com/topic.php?uid=59195345575&topic=14294

Source: Kevin Crosby (www.c-point.com)

3. Advanced DHTML, JavaScript (gualtierozorni.altervista.org)

"WZGrapher is an easy-to-use and small-footprinted Function Graphing and Calculation Program written in C language, with capabilities to plot both cartesian and polar functions. WZGrapher can also be used to graph numerical solution curves of integrals, to solve numerically and to graph ordinary differential equations up to the fifth order, and to calculate value tables (also of ODEs) including the first derivative values." Developer: Walter Zorn , 2007

WZGrapher Function Grapher
- http://gualtierozorni.altervista.org/grapher/grapher_app.htm
DHTML, JavaScript | VectorGraphics-Library
- http://gualtierozorni.altervista.org/jsgraphics/jsgraphics_e.htm
- http://gualtierozorni.altervista.org/dragdrop/dragdrop_e.htm

JavaScript, DHTML Tooltips
- http://linuxnotes.us/lostpages/walterzorn.de/tooltip_old/tooltip_e.htm
Rotate Image
- http://gualtierozorni.altervista.org/rotate_img/rotate_img.htm
Online Function Grapher
- http://gualtierozorni.altervista.org/grapher/grapher_e.htm

- http://web.archive.org/ (Walter Zorn, Munich, 2007)

4023976 visitors on www.walterzorn.com since 27. 12. 2002

4. Class WalterZornTips (http://www.jarvana.com)

Class WalterZornTips
All Implemented Interfaces:
java.io.Serializable, org.apache.wicket.behavior.IBehavior, org.apache.wicket.IClusterable, org.apache.wicket.markup.html.IHeaderContributor
walterzorn - Static variable in class org.wicketstuff.jwicket.tooltip.WalterZornTips

WalterZornTips - Class in org.wicketstuff.jwicket.tooltip
This class is a wrapper around Walter Zorn's ToolTip library.
WalterZornTips(String) - Constructor for class org.wicketstuff.jwicket.tooltip.WalterZornTips

Maven-Focused Java Class and Archive Search Engine
- Jarvana searches the central maven repository and provides maven dependency information for classes and artifacts.

1. cniv-sigla.htm (http://www.icvl.eu, M. Vlada)

2. Terry Brooks: tabrooks AT u.washington.edu (INFO 343 Web Technologies - Autumn 2010)

JavaScript Vector Graphics Library (Walter Zorn)

3. mapper.netzgesta.de © 2011 by Christian Effenberger

Demonstration .
mapper.js 2.4 allows you to add automatic area highlighting to image maps on your webpages (inc. export to SVG). It works in all the major browsers - Mozilla Firefox 1.5+, Opera 9+, Safari and IE6+. On older browsers, it can use "jsgraphics" from Walter Zorn (if installed), else it'll degrade and your visitors won't notice a thing.
Source: http://www.netzgesta.de/mapper

4. Pure Javascript Martin Browser Fractals By Peter Bromberg (2007)

"I've always had a fascination with fractal geometry. Its funny because I was so disinterested in mathematics that I almost failed 9th grade algebra. But once through college and with the advent of computers and graphics, math took on a whole new light for me. At home we have a coffee-table copy of Benoit Mandelbrot's book on Fractals (Mandelbrot could be considered the "father" of fractals, the Mandelbrot Set is named after him) ... Recently I came across Walter Zorn's Javascript graphics library and was impressed. Essentially he is drawing colored div tags into the browser, each absolutely positioned. No VML, no SVG - it's 100% pure client script, and it works with virtually every browser. The single .JS file is only about 19K, and if you compress it as I did, you can get it down to about 11K - not bad at all. So, I turned my attention back to my Martin Fractals article and decided to adapt the functions to use Zorn's library. ."

Source: http://www.eggheadcafe.com