Archive

Posts Tagged ‘mathematics’

DaMN book now on Softpedia

21 June 2011 Leave a comment

My book-in-progress Algorithmic Graph Theory, co-authored with David Joyner and Nathann Cohen, is now listed on Softpedia. These days I rather refer to the book as the DaMN book. The name is taken from the first letter of the first name of each author.

Advertisements

Bubbles and gullibility

18 June 2011 Leave a comment

Odlyzko [1] proposed a measure of gullibility, called the gullibility index, as a quantitative tool for developing realistic economic models. He argued that gullibility and innumeracy are strongly correlated, where innumeracy is understood to mean “the inability to reason with numbers and other mathematical concepts”. For example, answer the following question. What weighs more: a tonne of bricks or a tonne of feathers? Answer: both are of the same weight since each is a tonne. That we are comparing bricks with feathers is irrelevant. Innumeracy is almost universal in the sense that even people with higher degrees such as PhDs and MBAs do show signs of innumeracy. Furthermore, people who exhibit high degrees of numeracy could also fall prey to suspiciously false quantitative stories. A case in point is John Allen Paulos who related in [2] his falling victim to the Internet bubble of the early 2000s.

References

[1] A. Odlyzko. Bubbles, gullibility, and other challenges for economics, psychology, sociology, and information sciences. First Monday, 15(9), 2010.

[2] J. A. Paulos. A Mathematician Plays the Stock Market. Basic Books, 2003.

Version 0.7 of book “Algorithmic Graph Theory” released

24 February 2011 4 comments

Here is version 0.7 of the book Algorithmic Graph Theory. The relevant download options are:

Version 0.7 fleshes out the chapter “Random Graphs”. Here is the content of the chapter in brief:

  1. Network statistics
  2. Binomial random graph model
  3. Erdos-Renyi model
  4. Small-world networks
  5. Scale-free networks

Version 0.6 of book “Algorithmic Graph Theory” released

6 January 2011 Leave a comment

Happy new year, folks! As a new year’s gift to you, here is version 0.6 of the book Algorithmic Graph Theory. The relevant download options are:

Version 0.6 adds the new chapter “Tree Data Structures” that discusses priority queues and various efficient implementations of priority queues, including binary heaps and binomial heaps. Here is the content of the new chapter in brief:

  1. Priority queues
  2. Binary heaps
  3. Binomial heaps
  4. Binary search trees

Challenge your cryptology skills

25 December 2010 Leave a comment

In science, mathematics, and informatics there are various problem solving competitions aimed at challenging and expanding the talents of high school students. In the biological science, we have the International Biology Olympiad, in mathematics the International Mathematical Olympiad, and in informatics the International Olympiad in Informatics and the Internet Problem Solving Contest.

But cryptology is very much at the intersection of mathematics and informatics. There are some famous competitions in cryptology such as the National Institute of Standards and Technology (NIST) call in 1997 for a new encryption standard, a challenge that was met in late 2001 with the adoption of the Rijndael cipher as the Advanced Encryption Standard (AES) to replace the aging Data Encryption Standard (DES). The latest cryptology competition from NIST is a call for a new hash algorithm, called the Cryptographic Hash Algorithm Competition. As of this writing, the competition is in its third round of selection of a new hash algorithm.

The latter two competitions are oddly out of place for high school students. What comes close to a cryptology challenge for high school students is a competition I very recently learned about: the Crypto Challenge Contest. The contest is not really designed exclusively for high school students. You can find cryptology challenges suitable for high school students and up to cryptology researchers. However, many of the problems in Level I of the Crypto Challenge Contest are suitable for high school students. For those students who love a programming challenge, you might want to have a go at the problems in Level II. Happy problem solving.

QED symbol for end of proof

24 November 2010 Leave a comment

The amssymb \LaTeX package defines a default Halmos symbol that automatically appears when you use the proof environment. That default Halmos symbol is \Box. But if you want that to be filled with black, you could redefine the Halmos symbol. Put the following in your preamble:

\renewcommand{\qed}{\hfill \mbox{\raggedright \rule{0.1in}{0.1in}}}

Better still, you could customize what symbol you want to use as your QED symbol. Just replace the macro \rule{0.1in}{0.1in} with the the symbol of your choice.

Converting from binary to integer

26 October 2010 1 comment

The following is an updated and edited version of my posts to this sage-support thread.

Problem

You have a bitstring as output by

sage.crypto.stream.blum_blum_shub

and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.

Solution

Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.

sage: version()
'Sage Version 4.5.3, Release Date: 2010-09-04'
sage: from sage.crypto.stream import blum_blum_shub
sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b
100110
sage: type(b)
<class 'sage.monoids.string_monoid_element.StringMonoidElement'>
sage: # read in little-endian order
sage: # conversion using Python's built-in int()
sage: int(str(b), base=2)
38
sage: # conversion using Sage's built-in Integer()
sage: Integer(str(b), base=2)
38

Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.

sage: # reversing a string
sage: str(b)
'100110'
sage: str(b)[::-1]
'011001'
sage: # read in big-endian order
sage: int(str(b)[::-1], base=2)
25
sage: Integer(str(b)[::-1], base=2)
25

Or you can do as follows:

sage: b = "100110"
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b))
25
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1]))
38

Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.

sage: def horner(A, x0):
...       # Evaluate the polynomial P(x) at x = x_0.
...       #
...       # INPUT
...       #
...       # - A -- list of coefficients of P where A[i] is the coefficient of
...       #   x_i.
...       # - x0 -- the value x_0 at which to evaluate P(x).
...       #
...       # OUTPUT
...       #
...       # An evaluation of P(x) using Horner's method.
...       i = len(A) - 1
...       b = A[i]
...       i -= 1
...       while i >= 0:
...           b = b*x0 + A[i]
...           i -= 1
...       return b
sage: A = [1, 0, 0, 1, 1, 0]
sage: horner(A, 2)
25

As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.