Apps
Contact
Seminars
RSS FeedAugust 11th, 2011
School of Life (or, Life in School at 18)
Had an excellent meeting yesterday with a tech superstar (let us call him Dave). Dave has worked in (and sold) many companies, designed a real time operating system, developed a programming language currently in use, designed uber cool software components still being used by a big name ERP software provider. When I asked him about his educational background, Dave casually mentioned that he didn’t have much. Really, no big surprise there – some very big names in software have come from all kinds of schools, and some very big names have been dropouts etc, and some never stepped inside school to begin with. The value of school of life is well understood.
Also well understood is that there are many aspects of formal education which helps many people have a better grasp of their work. Some concepts are easier learnt in a structured program (at least for many people), than in a work environment.
In a certain respect, direct high school -> college -> graduate school -> job route can be considered to be a bottom up approach. Students have a structured path of learning, and they learn all the base steps and continue to build on those blocks, and are then ready for a super job. (Does this approach look similar to Dynamic Programming to you?) Along the path, students may question the relevance of certain classes, and can get a bit frustrated if neither the professor’s lucid explanations and war stories, nor the associate dean’s topological sort dependency diagram of classes are readily available.
The alternate route, high school -> job -> undergraduate -> job -> graduate route can be considered to be a top down, or greedy approach. Students start by learning what they can at their job, figure out what more they need to learn, go back to school to get their undergrad. Some go for masters after they have been working for a while, and benefit from what they learn. They have learnt the processes at work, are aware (somewhat) of the gaps that they have in their knowledge, and are now interested in filling those gaps.
[Umm, and there is also the slight issue of expectations. A person with the title of a senior developer with a graduate degree under his belt walks into his new job and everyone is aghast to find out that he doesn't even know how to use subversion - "Holy BSD!!" There aren't many graduate schools in the world that are going to teach someone how to use version control, and that is also not something that hard to learn, but you do have to learn it. A kid out of high school walks in, and everyone is happy to help him check it out.]
The alternate route is the part where I have picked some of my own arguments with the rest of the academic community. Everyone learns differently, and thus either of these routes may be the right path for someone. The kids shouldn’t just go to college by default when they finish the high school. In my opinion, the freshmen are generally thinking along these lines:
I could be flipping burgers at the King
Touring the Amazon, the pyramids and the sphinx
Working a bit, saving a bit
Climbing the mountains and walking along the Ganges.Instead, I am in this classroom
The professor knows nothing, the college feels like a hoax
The PhD Dude can’t even remember my name
But at least I am four hours away from my folks.
Currently, “living by yourself” has become a very significant portion of the college life, so much so, that everyone says - “Of course, that is a part of the college experience.” That may be the case, but if we can change a situation a bit, the kids can learn to live on their own, as well as, use the college for the kind of education experience that it was meant to provide. Kids can work a bit after high school, travel a bit, study a bit. Maybe go for an Associates degree. Then, when they are 21 or so, maybe then they feel like extending that Associates into a complete Baccalaureate, perhaps graduating when they are 23/24. That is 2 years behind the norm now, but by that time, they would have gotten some work experience, have smaller student loans and have wider perspectives on life and the world – what’s not to like about that?
——————————————
Do you have an opinion on this matter?
Loading ...
July 10th, 2011
CS 6212 (Summer 2011) – Final Grade Distribution
Here is the final grade distribution for my CS 6212 (Design and Analysis of Algorithms) class at GWU.
July 6th, 2011
3-colorability versus 3-clique
In CS6212, we study some challenging problems like graph coloring and finding large cliques. Both these problems are NP-complete. However, consider the following decision problems:
(Problem 1 – Graph Coloring) Does the given graph G have a valid 3-coloring?
(Problem 2 – Clique) Does the given graph G have a clique of size 3?
We know that the clique problem is NP-complete. Still, problem 2 as defined above, has a simple brute force O(n^3) solution, that simply checks every 3 vertex combination to see whether or not it is a clique. That is, it has a polynomial time algorithm. However, generally speaking, the brute force algorithm to clique problem is exponential, because the clique size (k) is given as an input, and then, the brute force algorithm becomes O(n^k), that is exponential in terms of the input. [An NP-completeness proof can be built by using a reduction from SAT to Clique.]
There is no analogous O(n^3) algorithm for identifying a 3-coloring on a graph. In fact, every known algorithm is exponential time, like O(2^n).
One way to reconcile this apparent confusion is to remember that a graph coloring works on the entire graph. A valid 3-coloring of the graph, for example, is a labeling that labels EVERY vertex of the graph using one of the 3 labels (or 3 colors). A 3-clique on the other hand is a localized structure, that we can identify by traversing all “neighborhoods” of the graph one by one.
June 3rd, 2011
Quiz 1 – Asymptotic Notation – Solutions
#cs6212gwu
Asymptotic Notation – Quiz Solutions
May 3rd, 2011
Rose is a Rose (but name is important in software and algorithms)
Ms. Juliet Capulet: “What’s in a name? That which we call a rose, By any other name would smell as sweet.” Sure, but Juliet was not an algorithm designer, or a software engineer, or a color guesser!
Apparently, naming is HUGELY import
ant when it comes to those non-romantic fields. John McWhorter’s The Story Of Human Language, presents a fascinating example: people of a certain culture have names for colors red, green, yellow etc, but do not have a name for color blue. Let us call them NoBluez, and let us call ourselves NoCluez for the time being. The NoBluez people see colors just fine, just like you and me, but they don’t have a ready name for the color we call blue. On the other hand, they do have two different names for two shades of yellow, that we normally call just yellow. Let us suppose that their names for the yellows are yellow (the light one) and izaga (the dark one). An experiment is conducted when colors are flashed quickly, and the people are asked to name the color. Although the NoBluez people and the NoCluez people are able to name the colors correctly in all cases (they are all home sapiens after all), still, the NoBluez people have a certain delay in finding and calling out the color blue. NoCluez people, on the other hand, show a delay in calling out the color izaga. Merely, the naming of the colors, has an impact on how quickly we can recognize it.
Nothing in algorithms, or in software engineering could be a more appropriate lesson. If you are going to have a fruitful communication with your team mates, and you are going to make sure that everyone understands and uses the newly written method called “processIt(boolean b)”, then good luck to you! While you may be able to tell everyone today what the method does, the chances of your method standing the test of a few weeks time, are basically zero. Someone will write a worse mouse trap, but name it better (for example, “synchronizeCalendars (boolean inclPastEvents)”), and that is the method that everyone will eventually use.
But that is not all of it. It doesn’t merely affect the usability and recognition of the method. Using a good name helps the person writing the code or the algorithm as well as you think through the logic and the various components and subsystems. Especially more so, when you have a system that is bigger than a few lines. For example, consider the attached MapReduce flowchart (courtesy Lukas). Naming each of those steps appropriately: “split”, “schedule”, “combine” is helpful in going through the motions of designing.