LP: CS51 – Wrapping Up, Cows and Finals

That’s it! CS51’s end is on the horizon, and I am again one step closer to completing my Harvard Challenge.

Problem Set 7 served to culminate most of the concepts introduced in the class, while also serving to expand events and objects. The last problem set involves programming a pseudo-simulation of cows in their natural habitat, or so I’ve described. A video of it in action, plus the specification, is available in the official page here.

The problem set is divided into 6 parts (along with a table of contents even!) so you know its going to be loads of work. There wasn’t really any pset that used objects before this one, so most of the concepts like Inheritance were introduced here. Coding a movable class to which bees and other moving objects inherited from meant a lot of code re use.

Movable Object Diagram

 

Perhaps the only thing I was uncomfortable with in the whole program was the fact that World Steps were events, and object adds an event listener for it, instead of having a world object that calls the ‘update’ method of it’s children. Of course, it may be just because of the fact that the pset aims to introduce the students to events, so it’s fair enough.

Finals

I took my finals today, and it went smoother than I expected. I was able to ‘steal’ a flash card reviewer for the final exams’ course, which I can only assume was the work of a previous harvard student or a TF. All in all it took me about an hour to complete the exam, including formatting the questions to make it look at least look easy enough for the eyes.

I nabbed a 95/100 for the exam, which you can view here. Of course, it was self assessed,, but most of the questions had concrete objective answers (definitions, true or false, code). There were a handful subjective answers, but I decided to grade them brutally (perhaps too brutally even!) I am even surprised myself that I was able to get such a high mark, though I can only imagine that the problem sets, which were the real meat of the course and involved lots of thinking and code, were the real barometer for the grade (or maybe Harvard is just that effective in teaching!)

The last question on the finals “What is the super secret bonus answer?” which was worth 1 point. I guessed “Cows” but I was unfortunately wrong. (The answer was 43)

Wrapping Up

Alright! I’ve finished CS51, completing the systems requirement of Harvard’s Computer Science Curriculum. I learned a lot in this course, being it functional programming and the beauty of abstractions (and laziness!) The syllabus states that the goal of the course is:

CS51 is a course that will teach you more rigorous methods of developing and
analyzing software. You will learn to write code that is reliable, efficient, readable,
testable, provable, maintainable… beautiful!

Which I think I was able to accomplish.

LP: CS51 – Laziness and Infinite Data Structures; also Music!

CS51 just keeps on with the surprises. I guess not CS51, but Ocaml and functional programming in general, but you get the point.

Lecture 8 was about infinite data structures. Consider:

type ‘a stream = Cons of ‘a * (‘a stream)

Finished reading it? So basically, we are recursively defining our type using the type itself, making it cyclic and therefore infinite. It was a pretty cool concept and it has an almost mysterious aura about it due to the fact that it’s something that by logic would be impossible – we are representing infinite data on finite memory! Of course, there is floating point numbers which are also infinite, but I digress.

As the end nears I see the more familiar paradigms I have become comfortable with. The next lectures tackled objects and events, showing that we do in fact, sometimes need to introduce side effects to our code.

Problem set 6 was quite challenging but a lot of fun, using infinite data structures to represent music as a stream of events. It was strangely satisfying to be able to produce music through code, and I had to admit I couldn’t move on from the problem set without playing a song in it first.

LP: CS51- Midterm, Moogle, and a three-day hiatus

Midterms

I survived my midterms for CS51!

CS51’s midterm was a closed book, no computer exam which was in stark contrast to CS50x‘ open book exams. The midterm was actually pretty easy: the beginning was mostly a matter of syntax (though still quite tricky!) while the latter parts did prove quite a challenge.

Since I’m only taking CS51 through the available online courseware, the midterm was provided in a pdf file. While I could have just dropped annotations for my answer, I figured that we could be a little bit more savvier than that and actually made myself an examination webpage! Strapped with time, I only bundled together the page with a WYSIWYG editor and while it won’t compete with Edx’ exams anytime soon, it gets the job done, and it’s quite pretty too!

You can view my midterm here!

Moogle

Told you Prof. Greg loves cows.

Problem Set 5 of CS51 is Moogle, a search engine a la Google. It really does show the power of Modules; we define a 2-3 Tree module once and have it be used in not only the dictionary and sets, but also in the graphs. We also have to implement the crawler for Moogle, among other things.

Hiatus

I had a bit of a cold these past days that I had a bit of a hiatus and wasn’t really able to continue the class. It’s an understatement that it’s quite a bit of a schedule slip.

LP: CS51 – Modules: Binary Tree, Heap, and Queue

Binary Heap Diagram

Visualizing binary heaps made it easier for me to code it.

Problem set 4 aimed to reinforce the idea of modules, which are cool little things that packages related definitions into one.

To really hammer the point about abstractions, the pset involves writing a Stack using a Binary Search Tree and lists, while making a Priority Queue using a Tree and a Binary Heap. The cool thing about all of these is they only have a single signature, meaning that the client can be using our module and not be afraid of having the code be broken as we increase the sophistication of our algorithms, which was really the case as we moved to the binary heap (that had O(log n) running time).

It took me quite some time to code all of these, and the binary heap was particularly tricky. The diagram I have is actually quite imperative, and the steps and branches int it are actually made as I moved through the coding process. It was basically a snap shot of white-boarding  the problem set.

Next up on my CS51 course is the mid term! Hope I’ll pass 🙂

LP: CS51 – RSA, Bignum, and the Substitution Model

The third problem set involves something BIG

The third problem set involves something BIG

Lecture 4 was about the Substitution model of evaluation, which started out pretty uninteresting (the concept was a bit obvious). Nonetheless it strengthened my knowledge, particularly the bit towards the end which translated how ocaml handled values to code. It involved a meta-circular interpreter, and even intuitively showed how a let statement is turned to a function call.

The problem set was a HUGE problem set; it was HUGE not only in the datatype we need to implemented but also a HUGE pain in the ass.

Anyway, the first part of the problem set was implementing the bignum datatype, a type which can hold an arbitrary amount of integers (as opposed to the standard 2^31 give or take of a standard int). Basically, we translate an int like:

123,456,789

into:

{neg=false;coeffs=[123;456;789]}

In base 1000. Of course, the beauty of this is we can input a crazily HUGE integer like 123,453,126,358,127,854,342,733,193,420 without getting integer overflows, which is necessary for RSA algorithms, the second problem set.

Wait What!

Yup, the second part of Problem Set 3 is implementing the RSA algorithm. Let me just quote the problem spec:

 Not bad for your third CS51 problem set!

Not bad Indeed. So here I am, armed with 5 CS51 programming lectures and emacs (now I try to save everything with C+x C+s, doh!), to implement the RSA algorithm to prevent baddies from stealing important info. Oh, and with a pretty tight schedule of like one hour. Secret Agent 101.

As always, you can view my code on this github link: HERE

LP: CS51– Polymorphism and Higher-Order Functions

When you’re completing a whole 4 year course in one year, the difference between completing a course in 10 days vs 7 days can be quite astonishing. And I feel like I’m lagging a bit.

Right now I’m at Lecture 4 of CS51, while also completing the third Problem set.

Problem Set 2 (which is the third one because of zero-indexing) is divided into two parts, the first part involving writing Higher Order Functions.

Finishing it was a lot of fun! (Which was literally my commit message in github).  Robert Fischer once said that “Ocaml” will warp your mind, and my mind had successfully been. Implementing Higher Order Functions- in which we were not allowed to touch signatures mind you, have opened my thinking to a very different programming paradigm. It was surprisingly exciting to use function composition and list mapping to what otherwise could be solved by a simple for loop, and function currying was both yummy and useful. The level of abstraction that feels always within reach is a very deep one, and I feel I understand recursion in a much more meaningful way.

However, there was an ominous message in the very beginning that seem to warn of a challenge coming in the horizon:

(* TIME ADVICE:
* Part 2 of this problem set (expression.ml) can be difficult, so be careful
* with your time. *)

Part 1 was fun! It was intuitive! It was great! Until I reached part 2.

The second part involved writing a freaking Language for Symbolic Differentiation!
Now, now, with all the things I learned up top, I should be able to do it right? However that doesn’t change the fact that it is both time-consuming AND challenging. I just discovered Scott Young, my big senpai in taking this course, took some of the programming assignments in parallel to other courses, which makes a butt-load of sense really. As stated in the very start of this particular learning project (that is, CS51), I was still deciding whether or not I take another course in parallel, and this option is appealing a bit more to me right now.

DerivRules

The Calculus. Be afraid of the Calculus!

LP: CS51– Function signature and Tuple fun!

I’m chugging along just fine in this CS51 class, but man, does Prof. Greg, not kid when he said he’ll make you feel uncomfortable by pulling out the rug. Functional Programming is very different. It’s not really hard per se, but it forces you to think in a different way than an imperative programming language does.

I spent a lot of time working back and front on the lecture slides and the official course reading (which is the official OCaml Reference) to understand this quirky language. I’ve just worked on the  problem set 1 (zero-index) tasked with writing functions that work with tuples, functions, and types. It was brain melting.

And it was damn fun. Weird return types? No loops? Weird syntax that bites beginners? It’s lovable! Function currying and pattern matching is what I used most in the assignments, but I can already see the elegance of functional programming.

Because of the nature of the course, and the language in general, I cannot be objective in giving a fair estimate of my code by just checking if it works. Imagine my joy when I discovered Code Review, which was part of the Stack Exchange family. Now I’ll even have a group of people who could review my code, and see if it’s good, readable, and smooth!

Not much to show visually, but emacs has a lot going for it that makes it's following understandable.

Not much to show visually, but emacs has a lot going for it that makes it’s strong following understandable.

Another thing that’s trippy is the editor itself. While I’ve heard of emacs before and its reputation for having a cult-y following, this course was the perfect excuse for me to try it out. Most of the key bindings are esoteric, i.e., saving involves pressing Crtl+x Crtl+s, while copy-pasting involves Alt+w, Crtl+y, respectively.

With regards to the problem set itself, the first few ones are easy enough (relatively easy, still a bit challenging) while the latter ones involve writing functions themselves. Here’s a list of them (non-exhaustive):

  • reversed – checks if an int list is in descending order.
  • merged – merges an int list. (involves currying)
  • unzip – unzip a list of int tuples. (okay, ‘unzip’)
  • variance – checks variances within a float list.
  • … and many more.

My favorite among them (the ones that made my head hurt the most) was the last two, which was writing a Run-length encoding algorithm, and a function that computes all the permutations of a list.

The course also teaches you practical programming practices! It is required to write assertions for your functions to make sure it actually works. Now it’s not just about making sure it compiles, but having a sharp eye on different test-cases!

All in all I’m really digging the course, not in the same way as 50, but in a different, much more “down the rabbit hole” way.