I've now taken three Coursera courses: Functional Programming Principles in Scala, Social Network Analysis, and Coding the Matrix: Linear Algebra Through Computer Science Applications. I also tried to take Calculus: Single Variable, but found that the workload was higher than I could manage with home and work obligations. I had varying degrees of experience with these subjects before beginning the courses; Functional Programming was largely review for me, Social Network Analysis was mostly new to me, and Linear Algebra was somewhere in between.

First, I found all three courses to be an effective way for me to learn the material presented. This is mostly because all three professors did an excellent job of selecting the exercises to complete for the course. Most of what I learned in all three courses came from completing the exercises. The quality of the lectures and the availability of written materials for offline study varied from course to course. But it's hard to be too critical considering that the courses are free. For someone like me who cares much more about increasing my knowledge than receiving credit or some sort of official certificate, it almost seems foolish not to take at least one course at any given time.

Completing the courses gave me a chance to practice with some programming languages I don't use in my professional work right now, like Scala, Python 3, and R.

Perhaps surprisingly, given that all three courses use Coursera's services, the means of submitting assignments was wildly different from class to class.

For the Scala course, assignments were submitted via sbt, and graded by unit tests on the server. These tests were occasionally fallible; when the server was especially loaded, it could decide that a submission was experiencing infinite recursion (a real hazard in functional programming) when, in fact, it was simply executing the code slowly. At most other times, however, the tests were accurate and the feedback was pretty reasonable.

For the Social Network Analysis course, the programming assignments were an optional add-on. You had to attach the homework via Coursera's site, and it would be graded somehow. It's not clear to me what the mechanism was, but it always accepted my submissions. The final programming assignment was graded using a peer review system where three other students would rate your submission, and you would evaluate the submissions of three more students. I really appreciated the feedback I got on this; it seems that the other students put real effort into their feedback.

In the Linear Algebra course, the programming assignments were all in Python. You submit them using a custom Python script which analyzes your code using regular expressions and unit tests on the client and server. This system was the buggiest of the three; the client and server code were occasionally out of sync, and frequently rejected correct code. These issues were fixed as the course went on, but it made for some very frustrating hours.

The use of instructor-supplied unit testing varied from class to class, as well. Unit tests were always included in the Scala class assignments, although the grader would run additional tests on your code. The Linear Algebra class assignments occasionally included unit tests, but mostly did not. The grader always ran unit tests, but they were not usable by the students. This deficit was made up for by other students who would post reasonable unit tests to the class forum. The Social Network Analysis class never included any unit tests in the assignments at all.

My biggest disappointment with all of these courses, however, is non-technical. Coursera, like nearly everyone in academia, has an honor code which forbids sharing work. This stands in stark contrast to most other collaborative systems for learning programming, like Exercism, Project Euler, 4Clojure (and arguably GitHub) where you are expected to first solve a problem yourself, and then work with other developers to refine your solution into the best possible implementation. You learn how to do the work well, not just how to make tests pass.

With Coursera (with the sole exception of the Social Network Analysis final problem), you just can't do that at all. There are forums, where you are allowed to opaquely discuss the assignment and your approach to it, but you cannot show any actual code for the assignment itself. In a real college course, you could review your work privately with a TA, so you'd at least get some feedback beyond pass/fail. There is no such option at Coursera. For me, this is the biggest barrier to real learning in Coursera, and it seems unnecessary, given that "cheating" on a zero-credit course you take for fun robs only yourself.

There are other areas in which I think Coursera could profit by deviating from the way things are done in college. It's not clear to me why a fixed schedule is required for these classes. Why not give students the option of "auditing" a course on their own time? Since the lectures are pre-recorded and the assignments are, for the most part, graded mechanically, it seems like this should be possible. Having a more flexible schedule would allow students who cannot commit the roughly 6 through 16 hours per week that most of the classes seem to require.

These criticisms aside, however, the big picture is that all of the classes I have taken so far have been good because the professors did an excellent job of designing the courses. As long as Coursera continues to recruit such qualified teachers, I think their classes will be a good investment of my time.

Read more]]>

You can find the puzzle and the solution on the Strange Loop wiki.

Read more]]>

There is more and more FireMonkey resources available online, including new "FireMonkey blog", FireMonkey Info page, FireMonkey quickstart tutorials and many more. Some of the best FireMonkey code pieces can be found at Anders Ohlsson blog. I especially like his EDN article on "Visualizing 3D mathematical functions using FireMonkey" that explains how to programmatically create mesh data for visualization using "TMesh" FireMonkey component. The source code for this demo is available at the Code Central.

Two decades ago I have been studying computer graphics at the Warsaw Institute of Technology and I still have some of my Turbo Pascal 5.5 source code with graphics applications for DOS. One of the projects for the labs on programming digitally controlled devices was to visualize a bicubic surface also known a "Bezier Surface". Using DosBox I was able to run my original, compiled DOS application inside my Windows 7 64-bit virtual machine.

The whole program is just one file with Turbo Pascal 5.5 code ("puns5.pas") and is using BGI for displaying graphics on the SVGA-compatible graphics card. It would not be possible to reuse the actual painting code, however I was able to extract three procedures, and some constants and variables from the the original Turbo Pascal code responsible for generating the 2-dimensional 11x11 matrix of 3D points that make up the wireframe. Bezier surface is a special case of NURBS surface that is very commonly used in 3D modeling. The shape of the surface is controlled by a 4x4 matrix of 3D control points as illustrated on wikipedia:

Below is the source code responsible for generating the 4x4 matrix of control points ("CreateBicubicMatrix2") and the resulting 11x11 matrix that approximates the bezier surface ("CountBicu" and "CreateNet").

**const**

nx = 10;

ny = 10;

**type**

p3 = **array**[0..2] **of** single;

Net = **array**[0..nx,0..ny] **of** p3;

BicubicMatrix = **array**[0..3, 0..3] **of** p3;

**procedure** CreateBicubicMatrix2 (**var** G : BicubicMatrix) ;

**var** x,y,z : real; i,j : byte;

**begin**

y:=-150;

**for** i:=0 **to** 3 **do**

**begin**

x:=-150;

**for** j:=0 **to** 3 **do**

**begin**

G[i,j,0]:=x;

G[i,j,1]:=y;

G[i,j,2]:=0;

x:=x+100;

**end**;

y:=y+100

**end**;

G[0,0,2]:=250;

G[3,0,2]:=50;

G[0,3,2]:=50;

G[3,3,2]:=-200;

G[3,2,2]:=-200;

G[2,3,2]:=-200;

**end**;

**function** CountBicu( wsp : integer; u,v: real; G : BicubicMatrix) : real;

**var** c,vb,u2,u3,t,t2,t3,v2,v3,k,k2,k3: real; j : byte;

**begin**

c:=0;

u2:=sqr(u);

u3:=u*u2;

t:=1-u;

t2:=sqr(t);

t3:=t*t2;

v2:=sqr(v);

v3:=v*v2;

k:=1-v;

k2:=sqr(k);

k3:=k*k2;

**for** j:=0 **to** 3 **do**

**begin**

**case** j **of**

0: vb:=k3;

1: vb:=3*k2*v;

2: vb:=3*k*v2;

3: vb:=v3

**end**;

c:= c + vb * (G[j,0,wsp]*t3 + G[j,1,wsp]*3*t2*u + G[j,2,wsp]*3*t*u2 + G[j,3,wsp]*u3 )

**end**;

Result:=c;

**end**;

**procedure** CreateNet(**var** N : Net; G : BicubicMatrix);

**var** u,v: real; i,e,f: integer;

**begin**

**for** e:=0 **to** nx **do**

**for** f:=0 **to** ny **do**

**begin**

u:=e/nx;

v:=f/ny;

**for** i:=0 **to** 2 **do**

N[e,f,i]:=CountBicu(i,u,v,G); *{ i - coord id: x, y or z }*

**end**;

**end**;

I have started from the original Anders Ohlsson source code for 3D mathematical function visualizations with FireMonkey and did some refactoring. There is a new button added for selecting "Bicubic Surface" and scroll bars for rotating the mesh in X, Y and Z dimensions.

Below is the actual source code for filling in "TMesh" component passed as the parameter with vertices, indices and material information. Below is the code responsible for creating the bezier surface programmatically using the original Anders' texture.

**const**

s = 0.1; *// scale factor for display*

**function** ScaleCol(c: single): single;

**begin**

*// scale color value "c" from "-25..25" to "0..1"*

c := c + 25;

Result := c / 50;

**end**;

**procedure** GenerateBicuMesh(**const** AMesh: TMesh);

**var** G: BicubicMatrix; N: Net; bmp: TBitmap;

i,j: integer; p: TPoint3D;

sizeN: integer; vertid, ixid: integer;

verts : **array** [0..3] **of** TPoint3D;

**begin**

CreateBicubicMatrix2(G);

CreateNet(N,G);

bmp := TBitmap.Create(1,360);

**for** i := 0 **to** 359 **do**

bmp.Pixels[0,i] := CorrectColor(HSLtoRGB(i/360,0.75,0.5));

AMesh.Material.Texture := bmp;

sizeN := (nx+1) * (ny+1);

AMesh.Data.VertexBuffer.Length := 4 * sizeN;

AMesh.Data.IndexBuffer.Length := 6 * sizeN;

**for** i := 0 **to** nx-1 **do**

**for** j := 0 **to** ny-1 **do**

**begin**

vertid := (i*(ny+1) + j) * 4;

ixid := (i*(ny+1) + j) * 6;

verts[0] := Point3D( N[i,j,0]*s, N[i,j,1]*s, N[i,j,2]*s);

verts[1] := Point3D( N[i+1,j,0]*s, N[i+1,j,1]*s, N[i+1,j,2]*s);

verts[2] := Point3D( N[i,j+1,0]*s, N[i,j+1,1]*s, N[i,j+1,2]*s);

verts[3] := Point3D( N[i+1,j+1,0]*s, N[i+1,j+1,1]*s, N[i+1,j+1,2]*s);

**with** AMesh.Data **do** **begin**

**with** VertexBuffer **do** **begin**

Vertices[vertid] := verts[0];

Vertices[vertid+1] := verts[1];;

Vertices[vertid+2] := verts[2];;

Vertices[vertid+3] := verts[3];;

**end**;

**with** VertexBuffer **do** **begin**

TexCoord0[vertid] := PointF(0, ScaleCol(verts[0].Z));

TexCoord0[vertid+1] := PointF(0, ScaleCol(verts[1].Z));

TexCoord0[vertid+2] := PointF(0, ScaleCol(verts[2].Z));

TexCoord0[vertid+3] := PointF(0, ScaleCol(verts[3].Z));

**end**;

IndexBuffer[ixid] := vertid;

IndexBuffer[ixid+1] := vertid+1;

IndexBuffer[ixid+2] := vertid+2;

IndexBuffer[ixid+3] := vertid+2;

IndexBuffer[ixid+4] := vertid+1;

IndexBuffer[ixid+5] := vertid+3;

**end**;

**end**;

**end**;

Below is the screenshot from the "Bezier Surface" visualization in Delphi FireMonkey 3D application.

The full source code of the "Bezier Surface" demo can be found at the Embarcadero Code Central.

Read more]]>

Perhaps surprisingly, it's actually very simple. (I say "surprisingly" because much of the math and technical papers on encryption is decidedly not simple, including that of Gentry's first fully homomorphic scheme, which was based on ideal lattices.)

This scheme created by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan, however, uses basic arithmetic operations like division, with a few uncommon, but easy to understand, variations.

The nature of homomorphic encryption also dictates a programming style which will seem unfamiliar to users of most high-level languages, but very familiar to anyone who has ever taken a digital circuits class.

What is the integer quotient of 10 / 6? Most people would probably say "1, remainder 4." But the exact answer, in the domain of real numbers, is 1.666666 (repeating), which is closer to 2 than the previous answer of 1. So another way we could answer this question is "2, remainder -2." This quotient is closer to the exact answer, and, correspondingly, has a smaller remainder.

So which answer is correct? Arguably, both of them. As long as the following rule holds:

`dividend = divisor * quotient + remainder `

(the division rule)

...then we have a valid answer.

Which method should you use?

In fact, there are at least five different, valid algorithms for selecting a quotient and remainder for a given integer division problem.

The homomorphic encryption scheme used in the van Dijk, et. al. paper and in Gentry's CACM article uses "R-division":

- Compute the real quotient
`Q`

._{R} - Compute the integer quotient
`Q`

by rounding_{Z}`Q`

to the closest integer._{R} - Compute the remainder
`R = Dividend - Divisor * Q`

_{Z}

This is probably different than the method you learned in elementary school, but both are valid. Importantly, it's probably different than what the integer division and remainder operators in your favorite programming language do.

If you've ever seen a 12 hour, analog clock, then you've worked with modular arithmetic. The time of 10:00 today is the same position on the clock as 10:00 p.m/22:00. Another way to say this is:

`10 ≡ 22 mod 12`

This reads: "10 is congruent to 22 modulo 12." In other words, we just ignore the "extra" 12 hours in the measurement of 22:00, because it's the same clock dial position as 22:00, only with a circle around the dial.

Naturally, we can perform arithmetic operations like addition and subtraction and compare the congruence of the result. I can say "10:00 + 5 hours means that the hour hand will point to 3 on the clock," or:

`10 + 5 ≡ 3 mod 12`

You can use any number as the modulus. When we make analog clocks, we use 12. A modulus which is particularly interesting in computer programming is 2. Arithmetic operations mod 2 correspond to binary operations, e.g.:

`0 + 0 ≡ 0 mod 2`

0 + 1 ≡ 1 mod 2

1 + 0 ≡ 1 mod 2

1 + 1 ≡ 0 mod 2

From this example, you can see that addition modulo 2 is the same as the binary operation

`XOR`

. It turns out that subtraction is exactly the same thing (for mod 2 only!):`0 - 0 ≡ 0 mod 2`

0 - 1 ≡ 1 mod 2

1 - 0 ≡ 1 mod 2

1 - 1 ≡ 0 mod 2

Multiplication modulo 2, on the other hand, corresponds to the binary operation

`AND`

:`0 * 0 ≡ 0 mod 2`

0 * 1 ≡ 0 mod 2

1 * 0 ≡ 0 mod 2

1 * 1 ≡ 1 mod 2

This is all very simple. However, a word of caution is in order here for anyone who has used a high-level programming language. Most languages have an operator like

`mod`

(in Delphi) or `%`

(in C#, which is commonly pronounced "mod"). However, this operator is not strictly modular congruence. It is more like a remainder, although, as we've seen, different people and different programming languages might choose to compute a remainder in different (but hopefully valid) ways.Remainders and congruence are often the same. In fact, the congruence relationship and the integer division remainder for the examples above are

`10 ≡ 22 mod 12`

22 / 12 = 1 R 10

However, it's easy to show examples where this is not true:

`22 ≡ 34 mod 12 (1)`

34 / 12 = 2 R 10 (2)

-22 ≡ 2 mod 12 (3)

-22 / 12 = -1 R -10 (4)

(1) is probably not the most common choice; 10 would be a more common answer, as with (2). (1) is nevertheless correct as a statement of congruence. Now compare (3) with (4). The most common way to compute a modulus is to pick the smallest positive number. But the most common way to perform integer division is so-called "T-division", where you select the quotient closest to zero and then calculate the remainder, resulting in a negative remainder when either the dividend or the divisor is negative.

A homomorphic encryption scheme, in addition to the usual

`Encrypt`

and `Decrypt`

and `KeyGen`

functions, has an `Evaluate`

function which performs operations on the ciphertext, resulting in the ciphertext of the result of the function.Obviously, this necessitates a different style of programming than that afforded by the typical programming language. In particular, code like this:

boola = b ? c : d

...(where

`a`

, `b`

, `c`

, and `d`

are all `bool`

s) is impossible, because the value of `b`

is encrypted, so the program cannot know what to assign to `a`

. If, however, we can perform binary operations on the ciphertext of `b`

, then we can rewrite the statement above as:

boola = (b & c) | ((!b) & d)

...or its homomorphic encryption equivalent:

CypherTexta = (b h_and c) h_or (h_not(b) h_and d)

...where the

`h_*`

operators are the homomorphic equivalents of the usual Boolean operations and `a`

, `b`

, `c`

, and `d`

are now of type `CypherText`

.Note that the version with the ternary operator and the version with the

`AND`

and `OR`

operators are not strictly the same, although their results are; the ternary operator is lazy, whereas the `AND`

and `OR`

version uses complete evaluation. This is necessary when the values are encrypted. It also means that the function may be inefficient.Intuitively, it's easy to see that any referentially transparent function can be reduced to such operations; this is what compilers and operating systems do under the hood anyway. I'm not going to go into any detail on how this is done; get an introduction to digital circuits book if you are interested in the particulars.

Gentry's article notes that other changes in programming style are necessary when performing operations within a homomorphic encryption scheme. For example, the size of the output of a function must be set in advance. Even if the plaintext is variable-length, the ciphertext must be of a known length, which corresponds to the number of "wires" in the circuit. The plaintext, therefore, would have "whitespace" at the end or be truncated, depending upon its size.

In my first post on homomorphic encryption, I mentioned that Gentry's encryption schemes can be considered fully homomorphic because they support two homomorphic operations, corresponding to Boolean

`AND`

and `XOR`

. I'd like to go into a little bit more detail as to why that is true.Many combinations of Boolean operations are equivalent. Perhaps the most famous are De Morgan's laws. There are a variety of techniques for converting one function using Boolean operations into an equivalent function with different operations. This is often done in order to produce a simpler or more efficient function, but can also be done in order to use a specific type of Boolean gate.

It is possible to use combinations of

`NAND`

or `NOR`

gates, for example, to produce circuits which perform a Boolean AND, OR, NOT, etc. Hence, a cryptosystem which supported a homomorphic `NAND`

operation could be considered "fully homomorphic."Similarly, having both

`AND`

and `XOR`

gates available allows you to produce the same outputs as all other Boolean gates, as, for example, `NOT p`

is the same as `p XOR 1`

and we can see by De Morgan's laws that with `NOT`

and `AND`

we can implement `OR`

.Therefore, we can see that a cryptosystem can be considered fully homomorphic if it supports enough homomorphic operations to perform any logical Boolean operation. In particular, a cryptosystem which supports any of the following homomorphic operations would qualify:

- Just
`NAND`

- Just
`NOR`

- Both
`XOR`

and`AND`

If you understand the math above, you should now be able to follow along as I implement Gentry's algorithm for "somewhat homomorphic" encryption. As you'll see, the "somewhat homomorphic" encryption will be the first step towards a fully homomorphic cryptosystem.

Read more]]>

On the other hand,I have not found. Quite the opposite, in fact. This does depend heavily on what kind of code you're writing, but the vast bulk of code thatin practicethat programmers need to be mathematically inclined to become great software developersI'veseen consists mostly of the "balancing your checkbook" sort of math, nothing remotely like what you'd find in the average college calculus textbook, even.

{

i = j++ / (x + v);

}

Not exactly the stuff mathletes are made of.

Arithmetic is one kind of math. It is relatively common in elementary math classes, and

On the other hand, I do see a good bit of:

- Relational database queries (relational algebra)
- LINQ (functors)
- Composition of lambda expressions (lambda calculus, of course)
- Set operations and logical operators (set theory)
- Etc.

That's by no means a comprehensive list. For example, every general-purpose programming language I've ever used would not exist without the Church-Turing thesis. But I didn't include that, since most people don't do programming language design.

All programmers work with mathematical systems day in and day out, whether we recognize them or not. Perhaps the ability to recognize math when we see it will help us better evaluate the importance of understanding it.

Read more]]>