Week 1: On the Importance of Efficient Algorithm Design – Will

Since my last blogpost I have completed the first two problem sets of the twelve this course entails. Week 0 entailed making a simple game in a visual programming language called Scratch where programs are created by dragging and dropping puzzle blocks into place more like LEGO then programming. Week 1 was the course’s first introduction to the C programming language and tasked us to write three programs.


 

water.c

The first of the trio tasked us to put the water wasted into showering into tangible terms by converting minutes spent in a shower to bottles of water. While technically this was a relatively easy challenge – it brought to light the interdisciplinary nature of computer science. CS does not exist in a vacuum nor does the problems it solves, and often its most important applications lay outside of the field itself. Computer Science allows us to contextualize and organize huge data sets and draw connections we might have never seen without it.

Screen Shot 2015-09-20 at 8.00.03 PM


 

mario.c

Image from Nintendo.com

Image from Nintendo.com

Our second task was a more traditional programming challenge. It tasked us with taking an integer of size [0,23] and to generate a Mario style pyramid of that height with # characters. While this didn’t directly have real world implications like water.c did; it did reach many valuable skills. The most important lesson from this problem was that of input sanitation; or making sure what the user inputs is both valid and not malignant. While this seems like something easy, forgetting to satanize inputs has lead to serious real world security breaches.

via XKCD

via XKCD


greedy.c

Screen Shot 2015-09-20 at 7.57.02 PM

The final problem of our problem set was the first time we had to consider and implement our very first algorithm. In short; an algorithm in many ways is just a set of instructions. It is just the procedure the computer follows to solve a problem. However almost all of the study of computer science is that of designing and optimizing algorithms. Even the field’s most notorious unsolved mystery, that equivalency (or probable lack there of) of P and NP complete problems, is an algorithmic mystery.

While greedy.c lacked the global implications that P vs. NP does, it tasked us on implementing our very first algorithm. As the same suggests we were implementing what is known as a greedy algorithm; or more simply an algorithm that always makes the optimal choice. In a fun play of words our greedy algorithm had to figure out how to give change using the least amount of change. While this isn’t a particularly difficult algorithm to implement, the lesson it teaches is invaluable.


Postmortem

While we are often taught the best way to become a better writer is just to put a pen to paper and write as much as possible – this is not true of computer science. It is always beneficial to focus on an elegant and efficient algorithm before you begin trying to implement it. The hardest part of computer science is not writing the code, it is designing it. You will never save time by starting to write before sketching an algorithm out, never. greedy.c is syntactically an extremely easy problem to solve; there is no pointer arithmetic, nor any other advanced programming concepts, just a bunch of while loops.. The challenge comes with designing an efficient algorithm to get to this point.

If you dive into this problem head first and just start writing you will not achieve an optimal result. If you dive in without planning you’ll many hours fighting edge cases and floating point impression and loose most of your sanity in the process. The algorithm I built in just forty lines, which I believe to be the most concise possible, would have been totally impossible to stumble upon if I had not spent significant time planning. I’d estimate that only 10% of the time I spent on this week’s assignment was actually writing code; the rest was quality time with a whiteboard trying out algorithms by hand.

This coming week we move onto Problem Set 2 which deals with cryptography, teaching string manipulation, one of my favorite topics. I suspect the vast majority of my blogging as this course continues will take this format, explaining the work done in this weeks problem set followed by some lessons learned. Hopefully these will serve as a nontechnical introduction into some of the course’s material.

Looking forward to seeing you all next week.

2 thoughts on “Week 1: On the Importance of Efficient Algorithm Design – Will

  1. realrowo

    Just like what you replied on my posts, I also want to thank you for opening up a new world for me. I have never been someone who is interested in computer science and coding (I don’t know if it is the right word because I basically know nothing about it). However, it is great seeing someone doing such cool stuff. Your explanation through the Super Mario game is very attractive. I have always been a fan of gaming, and I think it is really cool as you are digging into the backstage of the creation of the games. I look forward to reading more posts by you in the near future.

    Reply
  2. randyhimself

    I think you have a really good vision of the subject. You know what it means to program and can see the significance of even the simplest programming tasks. And that’s the most important thing. You can only master a skill when you truly understand everything that happens with it.
    I will probably start learning programming in spring, maybe you can teach me a thing or two then. Continue with your good work!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s