Category Archives: computer science

Teaching kids to program

Posted by on 28 February 2012 11:16 2 comments

Benjamin Pollack wrote yesterday about “Learning coding from boredom.” I love his ideas about teaching programming:

Programmers like to program because they can do cool things, or because they can solve problems, or both. It’s both creative and it’s practical. If the goal of a high school course is to get people interested in programming, then the course must build around these two pillars.

I first learned to program in BASIC on the VTech PreComputer Prestige. The things I wrote were simple Fahrenheit-to-Celsius conversions, guess-the-number-I’m-thinking programs, but they were really cool in the mind of an elementary school kid. Once my dad got me a copy of Visual Basic 2 that would run on our real Packard Bell Navigator Windows 3.11 computer, I was in heaven.

My junior high had two great programming classes. We didn’t do much theory, but Mr. Ferrin taught us a good balance of programming practice and Visual Basic GUIs. The high school had one class in the business department that tacked on VB6 for a measly two or three weeks, but like Benjamin, I knew nobody who actually liked programming after taking that class.

A few of my friends had great computer science teachers in high school, but most of them gained their love of programming by solving their own problems outside a formal programming course. Secondary education is ripe for reform in computer science curricula.

I’m lucky right now to be working with Bayside High School in Queens, who’s developing a program for CS students that looks a lot like the above, with introductory classes focusing on tangible results students can play with immediately (web applications, little GUIs, and dumpster-diving through massive datasets) rather than wading knee-deep into theory right from the get-go. But there are many, many high schools out there who have nothing remotely like this, who teach programming the same way they teach math. If the high school in your area’s like that, volunteer to teach something more inspiring. The students will love it, and we’ll get more impassioned developers as a result.

I might just do that.

Musical notation and programming languages

Posted by on 8 September 2010 10:12 2 comments

The most recent assignment for my CS 330 class was to write about how musical notation is similar to a programming language. This is a fascinating idea that I had never considered before.

The professor had an odd grading system for this assignment that, while seeking to reward creativity, penalizes collaboration, even in the mere exchange of ideas. But now that it’s been graded and returned, I have no qualms with sharing it here. You may find it interesting.

Similarities between musical notation and programming languages

Musical notation (in its modern form, at least) is standardized and widely accepted. Any educated performer can look at a piece of music and understand what the notation is intended to convey. This is a fundamental requirement of any programming language as well—the language must have a well-defined structure and syntax to be useful for expressing algorithms.

In addition to being systematic, musical notation is (largely) deterministic. While some structures in music are subject to the performer’s interpretation (rubato is a prime example), most parts of the notation are straightforward and not open to much variation. This is a bit of a rough comparison, however, as programming languages are entirely devoid of human interpretation or variation. Any given piece of code written in a particular language produces the same behavior when properly compiled, regardless of the platform or environment.

A beautiful aspect of music is the fact that the same simple notes and pitches can be combined in infinitely many ways to produce new and interesting melodies. The creators of musical notation could have had no concept of all the types of music that would eventually be written with that notation. In the same way, a programming language can become the vehicle of expression for all sorts of programs that the creator of the language may or may not have envisioned. The predicates, control structures, and definitions can be combined in infinitely many ways to produce new and interesting programs.

Often, there is more than one way to notate a certain musical phrase. For example, one could write a series of 32nd notes of alternating pitches, specifying explicitly how a trill is to be performed. But more efficiently, the composer could write a single note with the symbol “tr” above it, signifying to the performer that she should execute that same series of alternating pitches, even though the composer did not expressly write them. In either case, the music produced is the same, but the latter notation is more concise and easy to understand. Many programming languages give the programmer similar facilities. He can write a function recursively or iteratively, for example. In one case, the recursive structure will be much more easily understood than its iterative analog, and in another case the iterative structure is more intuitive. Obviously, the result will be the same in the end. It is often left to a compiler to decide the most efficient way of actually executing the algorithm, regardless of what notation the programmer chose to express it.

Some notes on the Collatz Conjecture

Posted by on 8 January 2010 22:15 13 comments

Part of my Computational Theory (CS 252) class this semester deals with the proof (or rather the lack thereof) of the Collatz conjecture. We were assigned a group problem to “prove” the conjecture, the point being, of course, that we would examine it and try to find patterns (since the likelihood of a few undergraduate CS students discovering such a proof is rather small). I found the conjecture fascinating and decided to post a few of the observations made by our group and myself.

Here is a flowchart of how the Collatz conjecture works:

One of our group members wrote a short Java program to run the Collatz conjecture on arbitrary input. I ran it on two data sets, one with the natural numbers {1..20} and one with the natural numbers {1..100}. I imported these into a spreadsheet and generated graphs of each of them. Here’s the graph over the {1..20} set:

Collatz graph over the integers {1..20}

Some interesting observations about this data set:

  • {15} maxed out at 160 (max of the whole range)
  • {19} maxed out at 88
  • {7, 9, 11, 14, 17, 18} maxed out at 52
    • All of these integers reduce to 17 somewhere along the line, and 52 is the next iteration after 17

It’s also interesting to note that the even integers {1..20} start going down first on the graph, and the odd numbers go up first. The odd integers usually, but not always, max out higher than the even integers.

This is the graph of the set of integers {1..100}:

Collatz graph over the integers {1..100}

Of the integers in this set, {27, 31, 41, 47, 54, 55, 62, 63, 71, 73, 82, 83, 91, 94, 95, 97} max out at 9232 (which is the max of the entire range).

Another of our group members noticed an interesting pattern in the output for the integers in the set {7, 15, 32, 63}. These integers are related to the number preceding them in the set by the formula 3n + 1. For example, 3 * 7 + 1 = 15. Here is the sequence generated by Collatz for 7:

(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

And for 15:

(15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1)

First of all, you can note that the last 9 elements of both of these sequences are the same. That is, once 7 is reduced to 13, the next element in the sequence is 40, and once 15 is reduced to 80, the next element in the sequence is also 40. Once the two have reached that common point, the rest of their sequences are the same.

But the intriguing observation is the bolded numbers in each sequence. in the 15 sequence, we eventually reach 35, which is one greater than 34 in the 7 sequence. Each sequence then has some arbitrary number, after which the next element of each sequence again differs by one. In the case of 7 and 15, this occurs only twice. The same pattern can be seen in the sequences for 31 and 63, but they are not reproduced here. (See the CSV files below for the data.)

After 63, however, the pattern breaks. 127 does not exhibit this phenomenon. A graph of the sequences for {7, 15, 31, 63, 127} shows this:

Collatz graph over the integers {7, 15, 31, 63, 127}

Here is apparent that 127 reduces fairly quickly, compared to 31 and 63, for example. This shows that 127 fails to carry on the pattern observed for the integers {7, 15, 31, 63}.

In step 13 of the 31 sequence and step 14 of the 63 sequence, both sequences reduce to 364. After this point, they parallel each other (differing by one step) until they reduce to 1. This is easy to spot in the above graph, and it helps explain the clusters of similarly shaped lines for the sequences in, for example, the graph over the integers {1..100}.

The data used for these graphs can be downloaded here ({1..20}), here ({1..100}), and here ({7, 15, 31, 63, 127}). The data series are on the rows and are comma-separated.