LC 207 Mathematical Experiments in Computer Science

An Integrative Learning Community Seminar - Joining

CSC 201 (Discrete Mathematics I) and CSC 212 (Data Structures)

Ralph Bravaco     304 Stanger     (508) 565-1077

Shai Simonson    306 Stanger     (508) 565-1008


Meetings:  Wednesday  2:30 - 5:00,            Room 308 Stanger.

Description: Computers provide us with tools to explore mathematics in deeper ways than ever before.  They allow empirical testing of mathematical conjectures with elusive proofs.  Computers enable us to experimentally analyze algorithms whose performance defies theoretical analysis.  Mathematics provides a structure and formalism that turns the study of computers and their applications into a science and not just an engineering discipline.  This learning community focuses on the delicate balance between theory and practice in computer science, revealing the dual and sometimes contradictory nature of computer science as both an engineering and a mathematical discipline.

Goals:  To appreciate the symbiotic relationship between mathematics and computer science.  To understand how mathematics is used to formalize computer science, and how computer science can be used as a tool to explore mathematics.

Labs and Expectations:  The semester is divided up into approximately five different self-contained labs as time allows.  Each lab is divided up into three parts:

Sample Lab Topic - Cryptography, Number Theory, and the Internet
Here is an example of one of our labs and its three parts.
This lab studies the abstract mathematics of Greece and the Renaissance and how it relates to modern cryptography.  Before the first meeting the students read and study a brief history of cryptography from ancient times to the present.

During the first two meetings, the students write programs to cement their understanding and implement various cryptographic methods.  They simultaneously write solutions to problem sets on number theory, to make sure their understanding of the foundations is clear.

During the third meeting, the programs are used to encrypt and decrypt various information.  A contest to see who can crack whose codes will commence.  Experiments as to the practicality of breaking codes and the safety of e-commerce will be performed.  Discussions of the future of the internet and its dependence on results in this area will complete the day.

Enrichment for this lab might discuss the life and times of Alan Turing, a famous pioneer computer scientist and mathematician who worked in England during World War II helping to crack German codes.  Turing is also famous for being an outspoken homosexual, who was tormented by his own country (for his sexual preferences) despite his heroic contributions to science and the war.  He eventually committed suicide at young age.  There is an excellent PBS video on Alan Turing and his life, as well as an acclaimed biography, and a Broadway play based on the biography.  Another possible area of discussion is the issue of government control over encrypted information, regulation versus freedom.

Lab Report Format: 

For each lab, every group will demonstrate that all programs execute correctly and are designed properly.  In addition a lab report should be submitted with three parts:
Grading:   

Altogether each group will have four to five lab report grades.  Final grades will consist of two parts:  75% is an even weighting of the lab report grades and 25% for participation, attendance, and interaction throughout the semester.


Useful Links: Mathworld  Cut-the-Knot Math in CS

Labs

    An exploration into complex numbers, the scientific theory of chaos, and computer graphics, through the award winning Tom Stoppard play Arcadia.

    (If you want to do this lab using C++, you should  also download directions for using the CMU graphics package.  If you are using Java, you do not need any special graphics package).

 An exploration into the world of abstract number theory and its application to the modern world of e-commerce.

    An exploration of the techniques used to send information in compressed formats.  Applications to the online music sharing craze.  (Here is the lab as a Word document with better layout -- Lab 3 ).

An exploration of a proof with a computer.  The proof implies an algorithm that defies analysis.

Comparing an algorithm to human performance in SameGame.

    A computational exploration of a trick where mathematical analysis falls short of a complete solution.