Harvard’s Math 152

I’ve enjoyed reading the Math 152 Weblog associated with the Discrete Mathematics course of the same name at Harvard.  Many of the posts should be of interest to Metroplex Math Circle attendees, but two recent posts struck me as being very similar to topics from our Fall 2008 lectures.

Math 152 helps you get jobs…

In this post a student talks about an interview he had with a quantitative trading firm which asked him to do a discrete path problem which was very similar to those Richard Rusczyk shared with us in his Math and Finance lecture.

Reading Project:  Groups, Factoring and Cryptography

This post built upon ideas that were introduced to Math Circle participants by both Dr. Bennette Harris and Alicia Prieto Lagarica in their lectures on cryptography.  It was particularly interesting that this Harvard student was able to apply his understanding of discrete math to the practical applications of RSA encryption just as Dr. Harris taught.

Alicia Prieto Langarica “Cryptography” Recap

Alicia Prieto LAngarica began her talking by taking questions from the audience about her own experience in competitive mathematics and pursuing a Ph.D. in math. Being closer in age to the students than to the parents, she was much better able to connect with them and discuss some of the pressures that work against pursuing a passion for mathematics.

Ms. Langarica’s lecture built on the theoretical foundation set down by Dr. Harris on September 27th.  The presentation began with a review of the history of various coding techniques. With each example, Ms. Langarica challenged the students to describe its strengths and weaknesses.

She then taught the students how to encode a text message into the binary code corresponding to ASCII characters. She then showed how that using the XOR operation (binary addition without carrying) she could encode the message. Students were given the opportunity to quickly decode the message when given the corresponding key.

Finally, Ms. Langarica divided the students into groups of 4-5 and allowed them to use their creativity to develop their own codes. These codes were then shared between groups who used the probability of letter usage to attempt to decode each other’s code. The codes were very complex and diverse and showed that the students had learned a great deal from these two weeks of cryptography.

Ms. Lanagrica has provided her slides from the lecture and answers to the problems. Members of the Metroplex Math Circle e-mail group can download these files from the group site. To join the e-mail group simply click below.

Click to join MetroplexMathCircle

Alicia Prieto Langarica – “Cryptography”

October 4th, we will review the history of cryptography starting with the classic methods, medieval techniques, cryptographic mechanical machines and finishing with contemporary cryptographic methods. We will discuss the advantages and disadvantages of each method and we will try to come up with different cryptographic methods of our own.

Ms. Langarica is a mathematics Phd student at The University of Texas at Arlington. She has a BS in Applied Mathematics from the Univestity of Texas at Dallas and was a contestant in the Mexican Mathematics Olympiads for 5 years where she received one national silver medal and two gold medals. Since then, she has been involved continuously in mathematics Olympiads as a trainer and problem writer.

Dr. Bennette Harris – Problem Set 2

Here is the continuation of Dr. Bennett Harris’ problems to warm us up before his lecture on September 27th. Congratulations to Dominic for being the first to answer the previous set of problems in the comments. Another happy discovery is the fact that WordPress, which hosts this site, supports the use of code!

Problems

A solution for each of the following should either give the correct answer, or a technique for determining the answer in reasonable time with the assistance of a calculator.

6. Crack this secret message: “uifsfaxjmmacfabmnptuaopaqsppgtaupebz”

7. Code the alphabet a=0, b=1, …, z=25, space=26. We will encrypt each letter of the alphabet by mapping it to the letter 3 farther along in the alphabet. Thus, a maps to d, b maps to e, and so forth. The message “a bat is fat” would be encrypted as “dcedwclvciodw” in this scheme. Find a mathematical function f(x) such that y=f(x) gives the correct encryption for every value x = 0,1,2,…,26. Test your function by encrypting “the toy boat floats”.

8. The purpose of these two questions is to provide points of comparison for the questions that follow:
How many particles are there in the known universe?
How many microseconds have elapsed since the beginning of the universe?

9. How long (approximately will do) would it take to calculate at 1,000,000 calculations per second? How many digits does the answer have? If p is 200 digits long, and if q is 200 digits long, about how many digits are there in pq?

10. The number – 1 is known to be prime. Estimate how long it would take a computer to demonstrate this by repeated division, at 1,000,000 divisions per second.

Dr. Bennette Harris – Problem Set 1

This Saturday’s (9/27) Math Circle lecture by Dr. Bennett Harris on “Computer Data Encryption – Decrypted” promises to be a great combination of number theory and applied math. To warm up the students, Dr. Harris forwarded some problems that I will post in two parts. Feel free to offer solutions in the comments or to just work them on your own. Full solutions will be made available at the next Math Circle.

Problems

A solution for each of the following should either give the correct answer, or a technique for determining the answer in reasonable time with the assistance of a calculator.

1. How many prime numbers are there? Prove your answer.

2. What is the largest number you must test to demonstrate that 83 is prime?

3. What is the smallest 5-digit prime? How could you find this number?

4. Is 1234567890 prime? What about 123456789?

5. Assume an alphabet with 26 letters (plus a blank space). A substitution cipher is a one-to-one mapping of this alphabet onto itself. How many such substitution ciphers are there?