Design and Analysis of Algorithms finished!

Well, I've wrapped up the work for Design and Analysis of Algorithms. I hope and plan to watch some of the remaining optional videos that I didn't get around to seeing, but that's the end of the work. I got full marks on the last homework and problem set, but on the final exam I got 25.75/30, which is a little lower than I'd like. Particularly annoying is that I lost two points on the final question, which I should have been able to get but I just didn't read my notes well enough. Ah, well. I certainly could have done better, but on the other hand, considering where I'm at, I can't be too upset by it. I'll await my final score - which unfortunately will be lower than it should, due to that brain-fart of not knowing about the existence of the programming questions. I could calculate it now, but eh.

On the class itself - interesting!! Wow, algorithms are really cool. I can see what Tim meant when he said they're addictive to think about. Although so far I don't seem to have any particular spark for algorithm design - all of the solutions offered are like "gee whiz" to me - I can understand everything well enough, and the ideas are cool enough, that I could see myself in some parallel universe studying this stuff. At the very least, it's very useful.

So with that, let's look at where I've come since the last post:

Progress:

• Algorithms: completed the course.
• I've all but given up on finding the answer to the second programming question. It's infuriating because the code sorts the list just fine - but the problem doesn't ask you to sort; it asks you to count the number of comparisons made. And for some reason, my code just doesn't count it right. Since it was late, and since I already got one of the three problems right, remaining is only a question of one or two more points. So, for the sake of my sanity, I'm going to pass.
• Programming Abstractions: watched through the 11th lecture video. Finished problem set 3.
• On the last problem of the set, I used an iterative solution rather than a recursive. They didn't say which one to use, but I'm guessing they wanted the recursive solution. Once I had the "updateVector" function built, it would of course be easy to implement a recursive rather than iterative solution, but I don't think the algorithm really would gain anything from it. Also, there might have been able to do a problem like this without vectors, but that's the answer I got and I'm sticking to it. Worthy to note is that some of the lectures coming up will be covering similar ground to the algorithms class I just finished up, so I anticipate skipping through a couple of those.
• Linear Algebra: watched through the 8th lecture video.
• The plodding pace of this class continues. I hope I can keep up a pace of at least 2 lecture videos a week; even at that I'm running behind the pace of the real class but at least it's not so slow that I'll lose track of the class.
• Programming Languages: watched through the end of unit 1.
• A really cool class. I like the content and I like the professor. I'm really looking forward to this one.
• Robotic car: watched through the end of unit 1.
• I remain optimistic about this course. Oh what an understatement, I'm totally psyched by this course! The material is a bit challenging, sometimes from a conceptual point of view and other times practical. But, if I can get a good grasp on this stuff, it will really be amazing. Especially combined with the Machine Learning and Computer Vision classes.

And coming right around the corner are Machine Learning and Computer Vision courses from coursera! They will be live on the website starting tomorrow or maybe late tonight. W00t!

Modelling The Monty Hall Problem with python

So I've always found the Monty Hall problem interesting, because it's so counter-intuitive. Basically, you're given three doors, with a car behind one and a goat behind the other two. You pick one door and then the host opens one of the doors you haven't picked to reveal a goat, and then asks you if you want to switch. Intuitively, you'd think that you'd gain no advantage from switching, because either way you have a 1 in 3 chance of getting it right... right? But no, as vos Savant first showed, the actual probability of a hit is higher if you choose to switch. Significantly higher. I'd heard this of course, and seen the Bayes math to show it's true. But nonetheless, it's just so counter-intuitive that it's hard to believe.

Enter computer science! Python, as with many things, makes it a snap to whip up a Monty Hall simulation. Then run it a hundred thousand times and voila, we have our answer: and sure enough, 2/3 of the time, switching gave us the car, while only 1/3 of the time did staying with our first pick result in a hit. It's still hard to understand why... but the sim is pretty solid.

Here's the code:
http://pastebin.com/2KueJkf4

Here's a rendering of the pseudocode inside the montyPick function, the only non-trivial part of the simulation.
Given a randomized list of three doors:
Pick the first door
- if you chose the car, Monty opens one of the other two doors (both goats).
- if you chose a goat, Monty opens the other goat.
- set remainingDoor to be the one you haven't picked and Monty hasn't opened.
- if your initial choice was a hit, add 1 to the count of hits from staying. (this step could be done earlier if wanted)
- if the remainingDoor is a hit, add 1 to the count of hits from switching.

The outer loop just iterates this and shuffles the list, so each time you're getting a randomized list. I had initially randomized both the list itself and the pick, but I realized that was unneccessary and added unneeded code complexity as well as extending the runtime (though perhaps I could have eliminated this with some optimization).

And the results speak for themselves:

Out of 100000 trials run:
Trials won by switching: 66575 percent of total: 66.575
Trials won by staying: 33425 percent of total: 33.425


Tough to argue with! : )

All hands on deck! We're heading into the squall...

So, the ball is definitely starting to roll now and I scarcely have time for anything these days besides working, eating, sleeping and of course, studying. But that's good - productivity is a good thing, right? This is what gives me raison d'etre. Of course, my girlfriend is not quite as excited by my obsession. But this isn't my diary, so let's stay focused and update ye olde blog.

Notice that the number of classes in the list has suddenly gone way up! And next week it will go up again...

Progress:

• Programming Abstractions: finished 5 out of 8 problems on the third problem set.
• Despite a week dedicated to recursion in the lectures, there's only a bit of recursion included on this problem set (of the 5 problems I've done), so either the last three problems here are recursion-heavy, or the next problem set is, which would mean that I'm a bit behind in problem sets compared to where I am in the lectures. Which isn't that big of a deal. Anywho, I'm getting more comfortable in C++ but at the same time there are so many myriad things that Python seems to make so much easier. Not only are the data types much more opaque in C++, but, it's worth mentioning, more limited too - for example the "map" type provided by the CS106B library can only accept strings as keys, while the equivalent "dictionary" type in python can take anything. Also, while accessing substrings from either direction is a snap in python, it's a hassle and a half in C++. The iterator is also a big PITA in C++. It's amazing how much I'd been taking for granted in python. I suppose the tradeoff of that is a reduction in computation speed, but so far that's not an issue for me. Anyway, I certainly don't regret getting some practice with C++, and compared to other languages I'm sure C++ is as easy as python anyway.
• Algorithms, Linear Algebra: no progress since the last update :(
• Udacity CS212: Design of Computer Programs: watched through part 14 of unit 1.
• I'm excited by this course, but I'm a bit miffed by the somewhat ill-defined nature a bit of the programs have taken. The lecturer has a bit of a loosey-goosey way of doing things when he's explaining, and I wish he'd be a bit more precise. That said, I think there's a lot to get out of this class. I expect to see lots of the same kind of stuff that I encountered on my own when programming my FreeCell implementation, but handled in a more thorough and structured way - plus all of the peripheral knowledge that will come with it.
• Udacity CS253: Web Application Engineering: watched all of unit 1.
• I expect this course to teach me a lot about what up until now I've mostly taken for granted about how the internet, specifically the client-server interaction, works. I expect it to complement the skills learned in CS262 very well. Thus far, there hasn't been too much new information since I already know the (very) basics of HTML. But there's some good info regarding the kind of information that servers use, etc.
• Udacity CS262: Programming Languages
• While the backbone of this course deals with building a web browser (which is incredibly interesting and exciting), it also so far has been spending a lot of time talking about more theoretical topics like regular expressions and finite-state machines. I find this theoretical stuff to be just as fascinating and I'm glad the course has a bit more of an academic feel to it than the other two, which seem to be more like practical (engineering) courses. But of course, time will tell.
• Udacity CS387: Programming a Robotic Car
• Along with Computer Vision and Machine Learning that are starting next week, this will be one of the three AI-courses I'll be taking this "term." How exciting!! The course thus far has been decently challenging, but I must say I'm not without complaints. Sometimes I feel he doesn't spend enough time on the math or the theory and the knowledge doesn't seem as deep because of it. I wonder if he's not trying to "sweeten" the course by removing rigorous mathematical discussion, which would be a shame in my opinion. On the other hand, sometimes the class is difficult but for the wrong reason - to wit, he tends to give a quiz right after he explains something. Instead of doing several examples to explain the concept, he hits the student with a quiz right after he's explained the theory, so in effect you're being asked to do the example yourself. This is fine in some cases, but really, in my opinion quizzes should be made after a thorough explanation and some examples have been given. This will help the student understand the material and see the thought processes to make, and it will avoid discouraging the student by giving them a problem they don't understand well and thus can't solve, and making them feel stupid for not being able to do so. As far as the actual course content goes, there's lots of interesting stuff. It seems that probability is absolutely central to the idea of AI, which isn't surprising. With that as a framework, localization and motion can be wrought up as probabilistic functions, with measurements and attempts at motion updating probability. It's neat. I hope and expect that if I have a good understanding of this class, the Computer Vision class and the Machine Learning class, and fill in whatever significant cracks are left (for example, by looking at the Introduction to Robotics lectures on the SEE site), then I'll have some really solid knowledge of AI. I'm very excited.

Right as I add a host of courses to my plate, I also find myself about to start my job full-time (next week, to be precise). As exciting as all of this is, I'm not a little worried as to how I'm going to fit everything in. I suppose we'll see.

Curses! Algorithms fail.

Well, so for the last couple of days I've been focusing on algorithms, not the least because it's the hardest subject I'm taking but also because I'm finding it quite interesting. Despite my lapse of giving up 2 points on the 3rd problem set, I bounced back to complete the 4th problem set with a perfect score, and in general I've been feeling pretty good up about the course.

Then suddenly, a link on the course webpage caught my eye - "Programming Questions." Huh? What's this?

Dun. It's 3 weeks of graded homework assignments that I hadn't been doing - plus a fourth one for this week. Urgh. I guess for some reason I had tunnel vision for the word "problem set" and didn't think there could be other graded work. Well, lesson learned and no sense crying about it. Besides doing the programming question for this week, I also have attempted to finish the other three I hadn't done, and now I've finished two of them and I'm inches away on the third.

As one might expect, these problems involve the actual implementation of some of the algorithms taught in the course, which is indeed nice to have the experience of. As I've learned, it's one thing to learn a high-level description of an algorithm in class, and quite another to translate that into working code. Oftentimes little things like how best to represent your data are big issues. Another is how that data changes - what should you change at the nuts-and-bolts level when you make a change like collapsing one node into another that's easy to understand at the high level? Anyway, it's interesting, but not a little frustrating. Anyway, here's the code for two that I've finished. I got full credit on problems 1, 3, and 4, but because 1 and 3 (and 2 when I finish it) are late, they only get half-credit. :(

Problem 1 - counting inversions
Problem 3 - calculating mincuts

OK, so a full update on progress. It wasn't all algorithms; I also got some Linear Algebra done.

Progress:

• Programming Abstractions: watched through lecture 10.
• The recursion topic, though not really new to me anymore, is still easily one of the most difficult for me to grasp intuitively. This is mostly true on the practical front - writing working code - but also on the conceptual front. So, I don't feel my time is wasting watching these lectures. But I'm still kind of skipping through them, as there is a lot of repeated information.
• Algorithms: watched the remainder of section IX and all of section X. Completed problem set 4 and programming questions 1,3, and 4
• In addition to the lengthy description above, I'll note that graph search is somewhat difficult in concept but is also very interesting. It seems like there must be loads of cool stuff to learn in graph theory.
• Linear Algebra: completed problem set 2.
• This is definitely the slowest-progressing class of the three. I hope to improve that and would say I aim to, but at the same time, there's a lot on the horizon and I'm not sure how much my available time for this class might wane as the new slew of courses begins.

Coming up:

Coming up is actually a lot! It's April 16th now, so all of the Udacity courses are going to start. And then on April 23rd, a new list of Coursera classes begins. There's hardly a course in those two lists that doesn't seem incredibly interesting. I hope to take most of them, and I hope I succeed therein. A lot of these are "periphery" classes when considered in the framework of a CS major, but are hardly periphery to the core of computer science. To wit, the planned course list is:

• Udacity:
• CS212: Design of Computer Programs
• Looks like it focuses on some key ideas in structuring larger-scale programs. Awesome
• CS253: Web Application Engineering
• Learning how to design web apps like a blog, and the associated stuff like user accounts. This one could be huge for any sort of business ideas or who knows what. Awesome awesome.
• CS262: Programming Languages
• I'm not sure how far it will go into the theoretical aspects of programming languages, but at the very least it teaches you how to build a web browser - wow! This knowledge seems to tie well into both of the above courses in that a central idea of programming is tying together disparate sources of information like HTML vs JavaScript, etc. Awesome awesome awesome.
• CS373: Programming a Robotic Car
• I was enrolled for the previous edition of this course but due to time demands and doubts about my level, I didn't actually do any of the class. Now once again I might skip this one, but I should be covering it either way through the machine learning class I hope to take at coursera. I'll start with both of them and pick the one that seems better - who knows, it might be both.
• CS387: Applied Cryptography
• This one seems very cool and I'd certainly like to learn cryptography, not only for practical purposes but it seems like a really neat aspect of mathematics. However, I must admit that if one course were to be knocked off, it would probably have to be this one because it's the least "essential" as in, what I feel I really need to know. I was going to say I'd try it out, but on second thought it seems clear that the time would be better spend elsewhere..
• Coursera
• Computer Vision
• What to say - this is what I'm the most interested in! At a very abstract level, I find this topic fascinating, and I would posit it's what I'm the most interested in studying. But, I really don't know the first thing about it. So, enter this course - I hope it's a good one.
• Machine Learning
• The natural component to computer vision, all under the AI umbrella. I'm definitely looking forward to this one. I'm not sure how much this one, computer vision, and the self-driving car class will overlap. If it's a lot, one of them might be forgone. Otherwise, it'll be a crash course in AI - hope it lives up to the hype.
• Lots of courses that I wish I could take!!
• Cryptography, probabilistic graph models, automata, natural language processing, logic... all in good time, I hope.

Looking over this list, it seems almost certain that I won't be able to handle all of this. This plus abstractions and linear algebra would make more classes than days in the week. I have to work out what my priorities are. One option is really focusing on the AI courses - vision, robotic car and machine learning - and letting the other ones go, or at least myself be lazy with them. Cryptography is probably gonna get the axe. Looks super cool, but it can wait. Plus, there's a coursera version that seems like it might be a little more rigorous.

Excited - but nervous - for what's coming up!

Updates 4/11/12

After a bit of unproductivity, I hope I can get back into the swing of things.

Progress:

• Programming Abstractions: watched lecture 8, finished problem set 2.
• They began the topic of recursion in lecture 7, which I was surprised to see as I would have thought it would have been introduced in the first term. Lecture 8 dealt entirely with recursion and pretty much covered stuff I knew already, so I just skimmed it. There was a nifty recursive counting (nCk) algorithm they showed that was interesting, but mostly I had seen all of it. The problem set was, like the first one, pretty basic and seemed mostly geared towards just getting students used to the basics of C++, particularly the data types that they use. The last problem was a lot of busy work IMO, with a bunch of if statements. Though, perhaps there was an easier way to implement it; in Python I could have used a few try/except blocks instead of explicitly writing out all the if statements. Here is my code: http://pastebin.com/6dL3FDqW
• Algorithms: watched second video of VII, first two videos of VIII, and all but the fourth video of IX. Did problem set 2, albeit with a mistake that cost me two points.
• I ended up having a lot of things come up that cost me valuable time, so I was unable to give the problem set the time it deserved or even to watch all of the videos I wanted to. All that to come.
• Linear Algebra: watched through lecture 7.
• Thus far, I'm still finding the idea of subspaces quite understandable, and I'm finding that bit by bit my intuition for matrices is building. It's still not at the level I'd like yet, but it's encouraging. Next up is to do problem set 2, which I may or may not be behind on schedule-wise.

I've gotta run so I'll skip the to-do section. Mostly it's pretty obvious. One thing that I definitely have to do - what a chore - is GRE study. Also I need to register for the test.

Updates 4/8/2012

Unfortunately this has not been the most productive week as of yet. My long vacation finally ended and my new job started up, albeit in a still somewhat restricted capacity. It seems that this job will allow me a fairly large amount of free time so it should still be possible to maintain a very productive schedule - but nonetheless, the job and certain other exigencies prevented me from getting much work done Thursday, Friday or Saturday. I got some quality study time in today, however. Well, let's see where we are now.

Progress:

• Programming Abstractions: Watched through lecture 7.
• Lots of interesting new data types being introduced. It's largely stuff that's part of the course-specific libraries, but nonetheless a lot of it looks interesting. Basically I'm seeing counterparts to a lot of the fundamental data types that are included in python like  lists ("vectors" in this class) and dictionaries ("maps"), and some new data types like the LIFO-vector type "stack" and the FIFO-vector "queue", as well as a fast-access unstructured array called the "set." The lecturer gives good examples of all of them, and I wonder if I might at some point find C++ as easy or easier for certain things than python.
• Algorithms: Watched through the third video of section 9.
• More operations on arrays, namely selection algorithms (such as the canonical "find the ith smallest member of a set") and graph theory (minimum cut problem) that both make use of randomized algorithms, much like the QuickSort algorithm.
• Linear Algebra: Watched lecture 6.
• With the somewhat tedious subject of manipulating matrices seemingly covered, it seems we're ready to dive into the more theoretical concepts in linear algebra. He started talking about subspaces of a space, which is an interesting topic and one that is perhaps ironically much easier for me to grasp than figuring out how one matrix will multiply another - although I'm getting better at that too.
• Udacity 101: Watched final 2 units of the course. Took the final exam, minus the starred problems.
• The final part, which was an explanation of Google's PageRank algorithm, left me somewhat confused. I feel like the explanation of the derivation of the terms in the algorithm was presented very quickly and without adequate time spent on saying what each term was doing and why the equation had the composition that it did in the end. I might rewatch them to see if I get a better idea upon second (more like third) viewing. Otherwise, the class was lots of fun and I'm glad I took it. I felt that the final exam was pretty easy, although I haven't tried the starred (bonus) problems. The first starred problem on the final exam looks quite a bit like some of the graph theory we're being introduced to in algo. I might give those problems a try, though time constraints might prevent me.
• GRE study: began some practice problems in the vocabulary and reading comp sections. 
• The reading comp problems are really unnecessarily weasely in my opinion. They're worded like riddles and that seems to be their primary value (although, for riddles, they're hardly amusing). I suppose a law student would be expected to ace that kind of thing, as the sort of subtle differences it's asking you to identify is the kind of thing that in my opinion would really only be relevant if you're looking for loopholes in legal language or some other kind of quibbly pursuit.

To do next:

1. Programming Abstractions: at least get started on problem set 2.
2. Algorithms: problem set 3 is due tomorrow, and there are also a few lectures I still need to watch to cover the proper material.
3. Linear Algebra: get started on problem set 2, read appropriate sections of the book
4. GRE: more practice problems. Try writing some of the essays. Get registered for the real thing next month.
5. Figure out what course is going to take the place of the Udacity course. It's somewhat of a moot point as there will be a whole host of new classes starting around April 16th, but nonetheless. Perhaps the discrete math would be a good fit for this, or I could simply decide to use the time towards existing classes.
6. Finish the FreeCell game, at least up to the point of a text-based implementation.

Progress on a FreeCell game!

I'd been thinking about if for a while but at last I got around to something a little fun: a freecell game. I was going to do it in C++, but... Python is so frickin EASY! Plus, the class inheritance system is a really nice advantage with this kind of thing. Here's what I have so far.

http://pastebin.com/NiH02qE9

The mechanics of freecell are really quite simple and almost trivial to write, so it didn't really take me long to write the move functions (no longer than it took me to write out all of those card name variables, etc...). All that really remains, besides bug testing, is fleshing out how it's all displayed. In the beginning, unfortunately, it'll be all text-based... but hopefully I can get something that's decent. I doubt it'll be a real blast but, hey like they always say, food tastes better if you cook it yourself. If I can get something working, I'll be happy. And then, maybe I can work on some solving algorithms. :D

Class progress updates:
Linear algebra: Watched first half of lecture 5.
Udacity 101: finished unit 6 and completed the final exam. I'm essentially finished here, but I might do the final exam bonus questions, and watch the videos in the last segment. I'm still a little fuzzy on exactly what PageRank does. I'll have to figure it out.

Updates 4/2/2012

(Sorry that my titles are getting repetitive. It's hard to be creative in this regard.)

Yesterday turned out to be a very productive day. As I noted in my previous entry, I had watched a lot of lectures from the algorithms class and completed the 2nd problem set. I also finished lecture 4 of Linear Algebra and before I went to sleep, I powered through the first problem set of the class. I was somewhat lazy on the problem set and didn't exactly nail all of the questions, but I was able to at least feel like I understand the material at some level. (It's still not my cup of tea, that's for sure). After waking up today, I got through unit 5 of the udacity 101 class (which mostly dealt with hash tables), and I'm now on unit 6, which seems to focus on recursion - my old nemesis. Although judging from the difficulty level of the class so far, I don't think it's going to challenge me as much as, say, the dynamic programming assignment from MIT 6.00 did (I think the stress of that problem set probably aged me a year or two - shiver).

Progress:
Introduction to Computer Science: 19 lectures, 10 problem sets
Programming Abstractions: 5 lectures, 1 problem set
Algorithms: 6.5 lecture sections, 2 problem sets
Linear Algebra: 4 lectures, 1 problem set
Udacity 101: 5+ units
Discrete Math: 1 lecture

My rough plan for the day is to try to finish or at least make significant headway on unit 6 of the udacity class, to play around a bit in C++ (perhaps do some preliminary work on a FreeCell implementation), and to watch another lecture from the discrete math class. If I have time, maybe I can squeeze in another Linear Algebra lecture.

Updates...

So it's been a few days... productive in many ways, though still perhaps not as productive as I would have liked.

Progress:
Watched through lecture 5 of Programming Abstractions. Completed first problem set but skipped last problem, which dealt with a memory diagram (Note: to address this deficiency in my knowledge, namely stack vs heap memory allocation, I watched lecture 14 of Stanford's Programming Methodology course. It was very informative. I might watch some more videos in this series to shore up whatever gaps exist in my basic programming knowledge. Side-side note: Java looks pretty interesting. I like that everything is an instance of an object. Python is similar of course, but maybe wears it a bit less on its sleeve. Well, like I said before, I'm sure I'll get around to Java sooner or later.)
Watched through section VI of Design and Analysis of Algorithms, and the first part of section VII. Completed second problem set. Once again I was able to get all answers correct. Yay. (Note: I'm worried I'll run out of space in the notebook for this class. Many notes have been taken.)


Unfortunately, this is the extent of my progress since the last update. It's not shameful but I'd like to be doing more. I still have yet to finish lecture 4 of Linear Algebra or complete the first problem set in that class. I hope to do at least one of those and ideally both before I go to sleep today. I also would like to get back to the udacity class before (a) I get too far out of the loop or (b) the class ends without me having completed it.

Next on the to-do for the next two days:

1. Linear Algebra lecture 4 and problem set 1. Watch lecture 4.
2. Finish unit 5 of Udacity's 101 class. If motivated, also watch unit 6 and maybe even 7.
3. Review basic combinatorics, probability and distributions. Watch second video of section VII of Algorithms.
4. (maybe?) start planning or thinking about a computer implementation of FreeCell, possibly in C++ (Python would be easier, but I could use the practice. Also I can try out new data types like the Queue or Stack in C++).

Aside: I'm becoming a total Stanford fanboy. The quality of lectures is overall amazing, the research is exciting, and they have the further positive of really having embraced the online-lecture paradigm, perhaps more so than any other major institution besides MIT. I can say with high certainty that Stanford would be my #1 pick for graduate school were I to get that opportunity, whether for a master's or a PhD.