Ragib Hasan's Computer Science Blog

What algorithms should new CS students learn first?

2010-07-05T22:24:00.002-05:00

Back in my college days, I tutored a lot. I actually paid my way through college by teaching computer programming to many students. At last count, I think I have taught C, C++, and Java to almost 150 students in total. And along the way, I taught them the basic algorithms they could test out.

Which brings on the question: what algorithms should newbies learn first?

From my experience, I think first-timers ought to start learning simple things (such as finding the maximum of three numbers), then progress towards slightly complex versions of these problems (such as finding the maximum of n numbers). Then they should focus on things such as finding the GCD using Euclid's method; Binary search, etc. Sorting can come next, and I started teaching my students Bubble sort (yes, I know, it's the worst performance algorithm, but easy for people to grasp, compared with Quicksort!!).

Once the students master searching, sorting, max-mins etc., I then taught them recursion. It was quite fun to teach them recursion using the analogy of a staircase ... you go down the stairs, doing something in each step as you go down and then return (or doing something in each step on your way up).

Bernhard Koutschan recently posted a list of the most important algorithms. (thanks to Daniel Lemire for pointing it out). Among my favorites for first-timers, only 2 made that list (Euclid's GCD, binary search). The rest of the algorithms in that list are a bit complex for the newbie CS students to grasp in their first semester ... at least that's what I felt during my tutoring days.

Lemire has also posted a shorter list of the 5 most important algorithms, along with a poll, in his blog. It will be interesting to see what shortlist people come up with.

Matthew Caesar's talk on Trustworthy Internet Infrastructure

2009-03-23T03:31:00.007-05:00

On 11th March, 2009, I attended UIUC CS Assistant Prof. Matthew Caesar's talk on trustworthy Internet Infrastructure. This was part of the ITI/UIUC TSS Seminar Series.

Matt talked about how to make the Internet routing system trustworthy. Internet infrastructure is very complex. Some people consider it as the most complex thing ever designed. And modeling internet operation is difficult ...

Because of the enormous cost of changing the way the Internet operates, traditional approaches have been to focus on incremental workarounds. Any radical redesign would be useless as it is not practical to deploy.

However, the quick hacks are not clearly working, as we face many problems.

Matt pondered, what if we could start over? Start from scratch and focus on a clean slate approach? He argued that any redesign is not going to happen because of the enormous task of changing routers. So, the best we can do is to work with the existing schemes and make them trustworthy.

Caesar talked about 3 schemes towards trustworthy Internet. The first is easier network monitoring, second, making making network operations/debugging/monitoring simpler to design. and third, making network more available and resilient, with high uptimes.

Among these, Matt talked about Bug tolerant networks.

Building bug tolerant networks with bug tolerant routers

Today's routers have a lot of complex software running on them. Because of the complexity, bugs abound, causing a string of high profile vulnerabilities, outages. Like any complex software , complexity is the cause of bugs, which cause serious issues, that propagate , ISPs often run routers in a way that errors are cascaded.

A recent example was Misconfiguration at AS 47868, Supronet, that started as a BGP error. BGP routing updates, has path vectors, A particular isp supronet misconfigured their routers , a typo, they were running a mikrotik router, this vendor has a bug in router, and cisco also has a bug in their OS, long AS path would trigger buffer overflow. FEb 16, 2009, 1/3 of internet was slow.

Challenges of router bugs

Bugs are different from traditional failures. fail stop failures cause routers to stop working. Bugs cause misbehavior, violate protocol, need vendor repair, exploitable by attackers.

Vikram Adve asked what code was the problem -- can a malicious guy write bad code to run in the router. Caesar replied that's not the main issue they are concerned with. Carl Gunter asked how similar this is to active networking, it seems like a similar concept. Caesar said this is similar to active networks.

Solving the bug problem

Caesar's main research here focuses on how to run multiple copies of router software on the router. A single copy/implementation may have bugs, but with voting among multiple different implementations, bugs can be filtered out.

So, he and his team built a router that had 3 routing software daemons (Quaga, zorp, etc.) running in parallel. These run on top of a hypervisor. After these run, a voting tool decides the final result. The hypervisor gives the illusion of a single routing daemon.

Nitin Vaidya asked, does Caesar assume that similar specs used by all the implementations? Has Caesar thought if two BGP implementations can have different results? Caesar replied that yes, because there are some non-determinism, so results may vary between implementations.

Bill Sanders asked, there are lots of work in voting issues in faut tolerant computing, . Caesar said, the non-determinism is disabled by ISP operators. because for traffic engineering, they need to make things deterministic.

Majoz (?) asked what you do when you have a buggy daemon ... do you remove it? Caesar said they haven't thought of it, but you can patch/update a daemon, or give weights.

Someone asked how much overhead is there? Caesar said update has some additional latency, they implemented it, overheads are 10s of milliseconds to process. But that's OK, because routers only exchange updates every several seconds.

Carl Gunter remarked that most problems are caused by misconfiguration, so what if someone misconfigured all 3 of the daemons. Caesars said that, configuration issues are orthogonal to their research.

Someone asked about the overhead with additional instances of daemons. Caesar replied that each daemons can be run on a separate core in multicore proc (routers have desktop like processors).

Bill Sanders asked if Matt knew about papers or reports that document quantifiably how diverse different copies of software are to produce the same things. Caesar commented it is similar to Knight-Levenson experiment, but Sanders said that was a 1985 experiment done with a few group of students. He then pondered, how much diversity do you need here?

Anecdotal evidence by Bill Sanders - they had a big DARPA projects, two different operating systems, turned off all unneeded service. and then looked how many advisories are common to both operating systems. the answer was 60%. Is it good or bad number? They don't know.

Carl Gunter said that there is a much better chance of replicating the knight experiment because the code size is small. Sanders commented what fraction of error will be caught by the small piece of errors doing voting.

Vikram Adve said: if you are running 3 copies of code, then isn't performance reduced by a factor of 3. Caesar said the bottleneck is in the hardware in data plane.

When sending updates to neighbors, the router also uses voting to choose the update to advertise.

Finally, Matt presented the research questions.

how to do voting?
nature o routing bugs?
how to achieve diversity?

They also looked into different voting strategies:

Wait for consensus: output majority. Downside = wait for consensus to happen, that slows down updates.

Master slave - always output master's answer, but switch to slave on buggy behavior.

Another aspect Matt had little time to talk about was the Study of nature of router bugs. They looked at Bugzilla bug db, and characterized bugs, most are from se fault/crash/freeze.

Wrong behavior (Bugs) = 43%, router crash = 57%.

There was a big diversity across virtual routers, different techniques, code bases, software versions, configurations,

And then he ran out of time.

My take: Interesting idea. But the problem is, often all different implementations of a particular algorithm or routing scheme reuse some components (e.g. random number generator? Some existing common library?). Often, security vulnerabilities are in the common library code, rather than in any particular implementation. How much dependability do you get by using 3 different copies? I'll be very interested in looking into more numbers. I hope Matt's paper on this has more experimental results.

My take2: And obviously, I'm interested to know how secure provenance can solve the malicious router update problem. It seems that by considering provenance of an update, it may be possible to filter out bad/tampered update info.

On Secure Provenance and the logic behind the threat model

2009-03-08T20:57:00.005-05:00

In our USENIX FAST 2009 paper (the "Picasso" paper), we discussed a scheme for providing integrity and confidentiality assurances to provenance of files. While this is a good first step towards securing provenance, I think there are many more issues we need to resolve.

These days, I see many security related papers advocating this or that scheme to secure objects. However, I really don't buy anything that claims to solve problems by having access control or policies. Here is why: access control works fine if the system is centralized, or the sysadmin of the system is incorruptible. However, when you have a distributed system with no control over other principals/their systems, OR when even sysadmins may become an attacker, there is no guarantee that access control constraints will be honored.

So, in the "REAL World", we can't claim to have a system that will prevent attacks from happening. With enough money, even trusted hardware devices can be breached (my co-advisor Radu Sion likes to stress on this point ... nothing is invincible). So, what can we do? We can't prevent someone from lying about themselves, or from deleting / changing things in their possession. What we CAN do is to prevent people from lying about others (i.e. "honest" others). This is exactly what guarantee we provide in our Secure Provenance work ... we prevent people from undetectably "invent" history involving other honest people.

To give a real life analogy, suppose a forger has painted a fake Picasso painting. The forger benefits here by taking his fake Picasso, and then inventing a fake history / provenance record involving his painting. He must have some honest buyers / art galleries listed in the provenance, otherwise, if the provenance only lists his cronies, it won't be believed.

The forger will NEVER do the opposite thing, i.e. take a real Picasso, and then remove its provenance and claim it to be painted by him. :)

The analogy applies to many scenarios involving data. I won't claim that it applies to all cases ... there are scenarios where the adversary might want to claim something as his own. An example would be the case of copyright disputes ... imagine two scientists bickering over who discovered something. But in most cases, the forger's goal with data is just like real life objects ... the forger wants to pass off something as what it's not ... so he needs a fake history, and that fake history must involve "honest" principals.

There are tons of issues to solve in order to have secure provenance ... but I'll write more about them later.

BTW, the painting shown above is a "real" Picasso, it is the painting titled "Dora Maar au Chat" (Dora Maar with cat). It is one of the most expensive paintings in the world; it was auctioned off in 2004 for $95 million!! Now, that has got to be the costliest painting of a cat!!

Ouri Wolfson's talk on using IT for Intelligent Transportation

2009-03-05T19:42:00.005-06:00

This afternoon, I listened to Prof. Ouri Wolfson of UIC talk at the DAIS seminar about using IT in managing transportation in an intelligent manner. The talk title was Information Technology and Intelligent Transportation - A Marriage Made in Heaven.

Prof. Wolfson presented some futuristic ideas ... if vehicles could talk to each other, if things such as vehicle speed, road congestion, brake malfunction etc. could be exchanged between adjacent vehicles, and then propagated to a larger area, what things can we do? Wolfson argued that we could do a LOT. For example, if a road is congested, and our car learned that, we can take an alternate route. If suddenly a vehicle in front of a my car lost control, my car could take proactive steps to avoid an accident.

There are of course sensors showing traffic congestion, but those are usually deployed at main highways. Wolfson's vision is to create a vehicular p2p system that will work for arterial roads as well. There are of course many issues such as how cars exchange and propagate the info.

Prof. Wolfson showed a small box-device that can collect vehicle movement/location info, and then transmit that to other such devices. The vision is to have these devices deployed on a large number of cars, and then beam the aggregated system state to all of these devices. The device can then show a map, and provide situational awareness to the entire set of vehicles.

The work is part of the IGERT initiative, for intelligent transportation.

My take: As a security researcher, the first thing that comes into my mind is how we would handle security issues. Thinking like an attacker, I see a lot of ways to subvert the system. For example, how do we know that the boxes are not lying and feeding fake data? If I want other vehicles to erroneously believe a side road is congestion free, move over there, and hence clear the road ahead of me, shouldn't I (or a lot of people) be tempted to do that?

Besides lying for personal benefits, there may be more sinister reasons to cheat/subvert the system. Attackers can also cause congestion, and jam critical highways. Attackers can also feed fake "accident" information to cause nearby vehicles take emergency evasive action, which itself can cause more problems.

When we take information from a mass of potentially untrusted sources, we have to be careful from the outset. Unless we can ensure the provenance of information, and also verify trustworthiness of things we get fed from others, it is better not to look at the info.

People don't even have to be malicious ... a vehicular sensor unit can malfunction ... how do we ensure it won't cause a ripple effect and mess up the entire system?

---
I won't even touch on the "Privacy" issues i.e. Big brother like monitoring of cars ... though this is a big concern as well.

Of course, the networking and data propagation issues are quite interesting by their own right, and that's where Ouri Wolfson focused on the talk. Quite interesting.

Funny news report

2007-10-15T14:42:00.001-05:00

I was reading BDNews24.com's coverage of some shoplifting at a Dhaka store. The item was titled "Three arrested on shoplifting charges".

The news was typical: two women and a man were arrested for shoplifting at ETC, a Dhaka MegaStore at Dhanmondi. What amused me was the way the reporter quoted the Police Inspector. Apparently, the alleged shoplifters picked up two Punjabis and a Fatua worth about 60,000 takas. The Police wanted to seize the Punjabis and Fatua as evidence. But, it being the top of the Eid shopping season, the ETC store staff didn't want to give away the expensive clothes.

But the Police Inspector had the upper hand:

A move was underway to file a case against the three as two salespersons for ETC accompanied the police to their station as "part of the legal procedure".

The ETC staff urged the police officer not to take the clothes to the police station, but he did not listen to them and insisted: "They are required for filing a case."

Arriving on the second floor of the shop, the Police officer told the ETC staff: "Hey, I didn't get any commission (discount) on a punjabi and a belt I bought from you guys."

"Now look, some clothes are with me," he said jokingly, grabbing the stolen items as he sat on the sofa.

Very funny, and that it made into the report was even funnier.

Dolls from Aarong

2007-01-30T11:43:00.001-06:00

Jamindar_Ginni_Dolls
Originally uploaded by Ragib Hasan.

These are the Jamindar Ginni Dolls from Aarong. My wife Jaria likes to decorate our living room with a lot of handicrafts. So, when she came to the US about 2.5 years ago, she had a whole suitcase full of Bangladeshi handicrafts. These two dolls arrived at that time :)

The workmanship is great ... note the details in the clothing. Alas, I went looking for more of these dolls during my recent visit to Bangladesh, but wasn't able to find such good quality ones. Perhaps the next time, I'd go to the main branch of Aarong.

Note: These dolls are from Aarong, the handicrafts branch of BRAC. These are made by the village artisans, mostly women, from rural Bangladesh.

Tagore Festival 2006

2007-01-30T09:35:00.002-06:00

Tagore Festival is an annual program held in the Tagore Center, Channing-Murray Foundation, Urbana. Actually, the nobel-laureate poet Rabindranath Tagore stayed here for quite some time in 1912 to visit his son Rathindranath, who was a student at University of Illinois.

Every year, Tagore Festival is held to commemorate the poet.

In 2006, the two main guests were the poet/novelist Sunil Gangopadhyay and the Dramatist/novelist Momtazuddin Ahmed.

Sunil was born in Faridpur, Bangladesh, but migrated to India following the 1947 partition. Ironically, Momtazuddin was born in Maldaha,West Bengal, but migrated to Bangladesh (then East Bengal) following the 1947 partition.

Jaria and I enjoyed the program a lot ... it included a cultural program with a lot of Tagore/Baul songs, and speeches by the two main guests. Momtazuddin Ahmed knew Jaria and her family since she was a baby, so he was quite pleased to see her again.

There was also a great Bengali-style feast after the cultural events.

Minus 12 Celcius in Urbana

2007-01-28T15:37:00.001-06:00

100_0020
Originally uploaded by Ragib Hasan.

This is how the outside looks from my window today. Can you guess the temperature? It's -12Celcius, during Daytime!!!

I'm never a big fan of winter, and this is why. Outside, its kind of sunny-but-cloudy, and it looks quite tempting. But the temperature is actually -12C, cold enough to freeze me in seconds!!

Don't get misled by the absence of snow. Actually, the temperature goes up when it snows!!

This is a far cry from the tropical winter in Dhaka, Bangladesh. I wish I'd be back there again ... :(

View of the Sky at 34000 feet

2007-01-28T15:33:00.001-06:00

101_0101
Originally uploaded by Ragib Hasan.

Ok, this isn't an awesome photo, but I liked the blueness of the sky. This was taken during my trip over the Atlantic ocean, through the window. Apparently, it was a very cloudy day, but we were going above the clould levels.

First snow of the year

2006-12-01T07:07:00.000-06:00

So I was up all night, not for anything particular. It was a rainy night .... but the morning brought the first snow of the year, in the guise of a snow storm. I realized that I didn't manage, in my last 3 winters here, to actually watch a snowstorm.

It looks strangely beautiful, and horrible at the same time. I remember watching those old movies where there will be snow blowing into the actors faces ... this one looks as bad as those.

I am sort of horrified to think what my car will look like after this storm is over. The prediction is for 3 inches of snow, but what I see outside the window looks way deeper than that. I hate to dig my car out of snow, and scrape the ice off the car's body.

Of course, living in midwestern US, we are probably luckier than those living in the east coast, or in the Dakotas.

:)

Looking into the Past

2006-09-06T12:13:00.000-05:00

Sometimes, I think about, say, 20 or 30 years in the past, and try to imagine how they worked without computers. Then again, I think the people 20 years from now will look into us and our gas-guzzling environment-polluting cars and put on a huge sigh.

But, upon watching an episode of Futurama, I think I'll change my perspective. It was the episode where Fry goes to a museum in the year 3000, and one exhibit is the 20th century factory assembly line. The museum commentator says, they don't know exactly how the 20th century people worked, but their best guess is like this: a bunch of robots, with primitive looking clubs, chanting "Buga Buga Buga!!!".

When it comes to looking into the past, we often do the same. Archaelogists tend to create elaborate theories about the origin of things. I wonder what people 50 years from now would think of us, the modern techologies we cherish, and so on.

Buga buga buga? That's how we are achieving this? Who knows!!

PS: My profound(!!) thoughts come from watching Futurama and Family guy. Yeah, I'm very shallow ... :(

50 years of Hard disks!

2006-07-31T00:30:00.000-05:00

NewsWeek reports that, next September 13th would be the 50th anniversary of the first hard disk drive.

Steven Levy writes,

"On Sept. 13, 1956, IBM shipped the first unit of the RAMAC (Random Access Method of Accounting and Control) and set in motion a process that would change the way we live."

Change indeed! Today, we have 120 GB or more hard drives sitting on our desks, with some geeks sporting terabyte storage systems for storing their infinite collection of Star Trek trivia and Klingon love songs.

So, what was the spec for the first disk drive? Let's see what Steven Levy writes:

"The drive weighed a full ton, and to lease it you'd pay about $250,000 a year in today's dollars. Since it required a separate air compressor to protect the two moving "heads" that read and wrote information, it was noisy. The total amount of information stored on its 50 spinning iron-oxide-coated disks—each of them a pizza-size 24 inches—was 5 megabytes."

Don't laugh. Your own drive will become obsolete in your lifetime, and you'd be telling your kids that "in 2006, I had a 120GB hard disk drive". I can visualize the smirk on your grandchild's face :)

I think in future, everything will become static, flash based or some other kind of chip based memory. Hard disks are good, have a lot of capacity for a dime, but still, they consist of moving parts, and that's why they are so much prone to failure.

Anyway, I still have my first 2nd disk drive. Though it sort of sings a serenade when I try to read something off it. Perhaps it's almost time I buried it in a time capsule for an archaeologist to discover in the year 2525 ...

Culture shock - 1

2006-06-26T10:36:00.000-05:00

Today, I'm going to list some cultural changes I encountered when I first came to the USA

a. I landed in Chicago and cleared immigration at around 9 pm. I've been hearing that Chicago O'Hare airport is the 2nd busiest in the world, or something like that. So, I expected a huge airport terminal, with thousands of people (at least comparable to Dubai's lavish airport).

Well, not so!! As I went into the terminal lounge, I found out that I was the ONLY person there. Not even a guard, janitor or cleaner! At 9 pm!! I was extremely hungry after my 30 hour flight, but found not a single restaurant or coffee shop open. The whole terminal looked like a ghost town.

I had to spend the night at the terminal as I didn't have transportation arrangements, so I slept or rather napped on a bench, while tightly grabbing my luggage.

Compared to O'Hare, other airports of similar size would be almost always full of people at almost all hours. I later figured out why this happened ... O'Hare has a small number of international flights, all leaving from terminal 5, and there were no flights after 9pm. So, the stores all closed, and everyone left. I guess the other terminals, mostly handling domestic traffic would be a bit busier.

b. On my very first day, I went to meet a professor in the department. It was the high point of a ferocious mid-west summer ... with temperatures reaching 32+ c (90+F). When I met the prof, I found him wearing a pair of shorts, and a t-shirt. In Bangladesh, where hot weather is a daily occurrance 80% time of the year, a professor of high stature would almost always wear Suits, rather than comfortable clothing. So, meeting a bigshot professor wearing shorts. I thought it made him more down to earth and approachable.

c. On the 2nd week, a member of the group proposed that we go to lunch to welcome the three new students (including myself). Now, when someone in Bangladesh asks someone else to go to a restaurant, this means the person who proposes is footing the bill. So, imagine my surprise when I figured out, right out there in the restaurant, that I am to pay for myself! Not that there is anything wrong with that, but obviously, I misunderstood "Let's have lunch!".

Of course, this is not necessarily true in all cases.

Anyway, that's all for today ... I'll write more later.

My BBC Interview

2006-05-05T20:39:00.000-05:00

I recently have started promoting the Bangla wikipedia. Unlike the English one, there are still too few articles in bn-wiki. However, with some very energetic people in BD joining the effort, I believe we'd be able to achieve a great, balanced encyclopedia pretty soon.

What I like about wikipedia is its ability to combine the little bits of information into a vast continuum of knowledge. It reminds me of the saying, "if you spend money, it's gone. But if you donate knowledge, it grows".

Anyway, recently, The Daily Prothom Alo did an article on Wikipedia. The article, which can be found here, was by Munir Hasan, and it helped launch interest in bn-wiki ... to a great extent.

Somehow, BBC Bengali learnt about the movement, and became interested. So, this week, on May 1, they called me and took a 10 minute interview on what Wikipedia is, and how
the Bangla wiki is being developed. I spoke about the progress, and how we can advance the bits and pieces of information into a large repository of knowledge.

The interview was broadcast worldwide on May 2 evening. I felt so great!! After all, I grew up listening to BBC every evening in our old radio set. It is great to be myself a part of that. Luma was so happy!! And so were my parents and Luma's parents!

I hope we'd at least get up to 8,000 articles and at least 2000 good articles in bn-wiki by the end of the year.

India beats China

2006-03-10T23:32:00.000-06:00

A recent list of billionaires published by Forbes shows that, there are more Indian US Dollar Billionaires than Chinese ones. Among the 793 US Dollar Billionaires of the world, 23 are Indian compared to 8 Chinese ones.

I looked through the list with quite an interest. As predicted, Lakshikant Mittal, the steel king, is the top Indian billionaire. But he's followed by Azim Premji of Wipro, the software company. Then there is the usual march of Ambanis, Birlas etc.

I was quite impressed to see Anurag Dikshit , a 33 year old IIT Delhi Grad. Apparently, he's the co-founder of PartyPoker.com , which makes his net worth at US $ 3.3 billion!! Who says coding doesn't pay!!!

Squirrels love M&M!!!

2006-03-02T13:22:00.000-06:00

As anyone living in the midwestern USA (I guess any where in USA) knows, Squirrels are quite pervasive here. They'd hang from trees, climb down to pick a nut, and occassionally fight among themselves, mess around with trash etc. I have often seen people feed them nuts.

Well, the other day, I found out that Squirrels do have a knack for sweet things as well. This is what happened:

I was coming out of the Illini Union, the student center at UIUC. I happened to have a pack of M & M's with me (if you haven't seen one, it's a kind of a chocolate). While I was unlocking my bike, I took one M&M out, and was planning to nibble on one. Suddenly, 2 squirrels came down from the tree next to my bike, and they sized me and the M&M out with interest. After a few seconds, they decided that I was a gullible one, and they can extort the sweet-smelling-nut-type-thing from me. So, literally, they stood up, and started waving to me. REally!!!! I wish I had my camera with me at that point, the scene was so funny, two squirrels standing up on their hind legs, and extending their hands!! Reminded me of how beggars in Bangladesh used to extort coins!

Anyway, I was so surprised and amused at the scene and their attempt to bully me into giving up the M&M, I spoke out in Bangla, (automatically) telling them "Dicchi baba dicchi" (wait please, I'll give you the nuts!!) (which reminded me again of my friend Suman's dialog in a similar situation on a train, India, in 2000)

So, I picked out 3/4 M&Ms, and gave them to the squirrels. They grabbed the chocolates, and finished them in 5 to 10 seconds. The way they devoured them, it looks like they really liked the M&Ms.

Ultimately, they managed to get 10-12 M&Ms from me that day. Next time, I'm taking my camera there, and will either get some stills or a video to show their "bullying tactics".

Pining for snow!

2006-01-29T20:07:00.000-06:00

Usually, I'd be gloomy all through the midwest winter. Until I came to Illinois 3 years ago, the only ice I'd ever see was inside the freezer. The last to harsh winters had me wishing a relief from the snow for months.

But this year, things are different.

It only snowed for a day or two in December. That snowfall was quite heavy. But after that, there hasn't been any snow even as we reach the end of January.

Is this the global warming effect people have been dreading for long? I watched the movie "The Day after Tomorrow" recently, and the movie now seems more and more realistic.

Anyway, as a result 0f the snow-less winter, I'm kind of missing the flurries and powdery snows, and the funny way of walking on the snow. Strange!!!

My Linux History article

2006-01-17T15:40:00.000-06:00

In this post, I'm going to look back at my article on the History of Linux. (also available from here ).

Ok, let me start with how it began. Back in 1999, I had just installed Linux, and was one of the first members of Bangladesh Linux Users Group (BDLUG). Back in those days, I had a rickety 19.2 kbps dial up connection, at cut-throat price ... taka 3 per minute. Yet, I spent probably a week looking for the History of Linux. Those were the days before Google became such a hot thing for search, so I think I probably used Yahoo! search. After learning the interesting History of Linux, and with the zeal of a newbie, I wrote a small article on the history of Linux.

First, I posted it in my free web host, hypermart.net. It was also mirrored at the BDLug site. It remained there, and I almost forgot about it, until I started getting mails from complete strangers regarding permission to use the article. Many of them wanted to use it for a course, or a LUG meeting, but several of the people wanted to use it for inclusion in a book. After thinking about the whole thing, I decided to release the article free for all non-commercial use.

Next, in 2000, I published the article in a local news paper, The Daily Star. I'd have to check to see if they kept an archive back to 2000, but I may have the copy of the news paper.

By this time, I got several requests from people, who wanted to translate it to other languages. The first one is probably from a Japanese guy, who translated it, and put it in his website. Following that, the article has been translated into 5 or 6 more languages. Here is a list of the different languages.

[Hebrew] | [Bulgarian] [Japanese] [Chinese] [Romanian] [Portuguese]

I recently released version 2.2.0. I wrote about Tanenbaum, Richard Stallman, and other people who were influential in providing the whole basis of Linux.

I keep expanding and enhancing the article on a regular basis. What makes me happy is that the article has proven to be useful to a lot of people, and also many instructors (at least 5 I know of) have used it for their university level courses.

Year-ending Group Lunch

2005-12-29T16:52:00.000-06:00

Rishi proposed that we should have a group lunch to celebrate the end of the year. So, Prof. Winslett and our whole group went to El Toro for a group lunch on Saturday, December 17. I was interested in meeting Arash, another student of Prof. Winslett, whom I am yet to meet. However he didn't show up. Lars was also missing.

Anyway, the lunch was good. I was surprised though, because I thought El Toro would be a costlier restaurant. It turns out that El Toro is a chain restaurant, and this is one of the two branches in Champaign.

We had a nice chat during the lunch. Everyone recounted where we have travelled, the different anecdotes from the travel experiences, and also where we want to go. I haven't travelled to too many countries. The only two I've been to are India and USA. But if I get the chance, I want to visit Europe and South America. My cherished place is the Inca ruins of Machu Picchu. I also want to visit the Pacific Islands like the Easter Island, Tahiti etc. I've read so much about them since I was a kid.

It was great to have such a nice gathering. It enhances the interaction among the students of our group (although already we have a lot of interaction going on).

M.S. Conferral Ceremony

2005-12-29T16:43:00.000-06:00

I got my Masters Degree on December 18th, 2005. This was my first commencement ceremony. I had missed my undergraduate convocation (that's what the ceremony is called in Bangladesh). That was a great loss ... as the ceremony was a grand one ... with the Prime Minister of Bangladesh giving out the certificates. I got 2 gold medals for my undergraduate results (passing Summa Cum Laude). My wife, Jaria, attended that ceremony and got the awards on my behalf. Anyway, that's why my MS graduation ceremony was so important to me.

I took Jaria and some of my friends to the ceremony. I was impressed ... the ceremony was smooth and flawless. We didn't get the actual certificates, those will be mailed in about 2 months. But to attend the ceremony with the cermonial gowns and the orderly procession was a great feeling.

After the ceremony, we celebrated at our local Indian fast food restaurant.

I put more photos in my website's album pages.

My poster at the ITI Dependability Workshop

2005-12-06T17:19:00.000-06:00

This is my poster from the ITI dependability workshop at UIUC on December 6, 2005. Basically, this shows my Master's thesis work. The system is still a work in progress, so not all bits and pieces of information are there, and not every sort of details figured out, but still it was a nice experience to work on the poster and also to build the system.

My Thesis: (Finally)

2005-11-23T13:09:00.000-06:00

I've been putting off writing my Masters Thesis for a long time, but this fall, I decided to do it. I'll be building a framework for policy driven information exchange between entities. For example, in a disaster/emergency situation, a control room could gain access from resources that otherwise don't allow access.

Prof. Winslett gave me this idea last summer. I'm coding like crazy right now to finish it within this week, so that I can start writing it up.

If it's implemented, it will probably be included in the City of Champaign's control room.

ACM StorageSS 2005 in George Mason University

2005-11-12T23:12:00.000-06:00

I'm just back from a trip to ACM StorageSS 2005, co-located with ACM CCS, in George Mason University, Fairfax, Virginia. I had 2 papers published in this conference. The first one, was on Storage Service Providers, and the second one was on Storage Threat Models.

3 members of our StorageSS group: Bill, Suvda and I went to the conference. Bill was also the program chair. The experience of attending the conference was a good one ... I met a lot of people in the Storage field. For example, I met Kevin Fu, the MIT guy. designed of SFS, now an assistant prof at U Mass. Amherst. Yongdae Kim from UMN was there, and so was Ethan Miller from UC Santa Cruz. I also met other grad students from StonyBrook, UMN, and UCSC.

Many of the talks were insightful. Since I work in the area, I knew about most of the topics, and had discussions/chats with the bigwigs during the lunch and coffee breaks.

Mine was the first presentation of the day. I had practised extensively, so everything went smoothly. Bill (Yurcik) was happy with the talk.

Prof. Winslett, my advisor, came to the talk. She also introduced me to Will Winsborough (Prof. at UT San Antonio) , Prof. Ning Yu (from Purdue), and some Italian researchers (Bonatti, Samarati).

George Mason University is one of those traditional east-coast schools, about 30 miles away from Downtown Washington D.C. Not too big, but the campus was nice.

AnHai Doan's Academic job hunting talk

2005-11-07T23:04:00.000-06:00

Today, AnHai Doan gave a talk on Academic job hunting. Now, I've taken AnHai's class, and he is a very good speaker. At first, he doesn't seem impressive ... but as soon as he starts to talk, he just has everyone listening. He is very very funny, and even makes jokes at his own expense.

Anyway, AnHai talked about how we should proceed when looking for an Academic job in a talk school. Lately, UIUC is lagging behind other schools in academic job placement of its graduates. AnHai says the key is to get into the habit of "people watching", network with people, and know who to impress. Interestingly, AnHai says that paper count is NOT the main thing ... rather the quality of paper and how it's closely related to research area is important.

Another thing is to generate "buzz" and have a presence. Academic recruiters look for people they can hire, and a good word from a high-placed person can mean a lot.

I was impressed by AnHai's talk ... I hope I'd be able to incorporate some of that into my own life.

How to write an SOP/Get a Reco

2005-10-30T22:48:00.000-06:00

Nope, I won't give tips, but here's something people from admission committee, and professors tell me. Basically, they don't really rely on recommendation from unknown professors. Also, most of the recommendations from South Asia are likely to be written by the applicants themselves, this is a known fact. Besides, it makes a recommender's credibility very low when every student s/he recommends is "My favorite student".

The best way to improve chances of admission is to write a great Statement of Purpose (SOP). Don't make it sound like you are bragging. The admission committee have no idea who you are ... grades don't reveal a lot about a person. So the Statement of Purpose is the best way of presenting/selling yourself ... you get to show off.

More on this in my personal website article that I'm working on now.....

My favorite Science Fiction Movies

2005-10-25T22:55:00.000-05:00

I like Sci-Fi movies, and there are some which I like more than others. Here is a list of my favorites:

1. Close Encounters of the 3rd Kind
2. Artificial Intelligence
3. 2001: A Space Odyssey
4. Gattaca
5. Star Trek (most of the original series)
6. E.T.
7. Back to the Future
8. Total Recall

Well, there are some others, I just can't remember right now.

Photo from Matt Bishop's visit to UIUC

2005-10-25T16:08:00.000-05:00

Ok, this is a photo from October 24, 2005, as I have mentioned in an earlier post. I've finally got off the procrastination mode and managed to get the photos dloaded from my camera.

Matt Bishop is at the center of the photo, with other people from our NCSA Security Research Group. I'm standing to the left of Bishop.

Matt Bishop's visit

2005-10-25T15:53:00.000-05:00

Matt Bishop from UCDavis came to UIUC yesterday. For those who doesn't know him, Bishop is the author of the book, "Computer Security: Art and Science". This is one of the encyclopedic works on computer security theory. Of course the book is highly mathematical, and not one on the practical implementations. Anyway, for any serious security researcher, this is a must-have book.

Prof. Bishop came to our NCSA security research lab last afternoon. He is one of those jolly, friendly professors ... was quite free with us, and affable. I had been studying for the Security midterm since the weekend ... I told him to wish me good luck as he signed my copy of his book. :D. I also have a picture taken at the lab...

By the way, the midterm was quite tough!!

Star Trek

2005-10-23T20:20:00.000-05:00

I like watching Star Trek, but I'm not sure which series I like: Star Trek Original Series or the Next Generation.

One thing is that I've seen more of Star Trek TNG than TOS. The TNG is in syndication now, so I watch at least 5-8 episodes per week. Although there are about 63 episodes in the original series, I've seen only the first season.

Of course, I like Captain Kirk more than captain Picard. Somehow I find Kirk more heroic. Picard sometimes look too much pompous to me, too much diplomatic.

Anyway, the characters I don't like would be Worf and Troy.

By the way, among the movies, definitely I like the ones from the original series (Star Trek 1-6). The newer movies are aweful.

And, I definitely don't like the newer serieses, like Star Trek:Voyager, Star Trek:Deep Space 9, and Star Trek:Enterprise.

Crazy weather in Champaign-Urbana

2005-10-21T23:32:00.000-05:00

The weather in Champaign-Urbana is totally crazy. Today started with a lot of rain/cloud etc, and remained cloudy. But right when I thought it would end up as one of those cold-rainy-windy days, it became sunny in the afternoon. This reminds me how I was duped last year by the sunny sky, which turned into torrential rains within 10 minutes, and left me all soaked up in my best outfit.

IBM Day at UIUC

2005-10-20T23:50:00.000-05:00

Today was IBM day at UIUC CS department. A Whole day of talks, demos and other fun activities. I attended some of the talks, which dealt with some projects at IBM, and some others at UIUC.

At noon, there was the Pizza session, with Pizza from Papa-dels. A lot of people came, I guess for the pizza. Anyway, there was a poster session too. Adam Lee and I were planning to take our posters, but they didn't have room for it. I looked into some posters that interested me. Joe Tucek had a poster on the paper that's being published at SOSP. I also looked at Qingbo's poster, and some other one that used Game theory for Network security.

Fall in C-U

2005-10-18T12:00:00.000-05:00

Fall is in full bloom in Champaign-Urbana. It's fun to see the trees changing the color almost overnight. The weather is surprisingly warm for this time of the year. Of course, there are predictions that it would remain so throughout this winter.

Tagore festival in Urbana

2005-10-15T22:22:00.000-05:00

Today, we attended the Tagore Festival at the Tagore Center, Channing-Murray Foundation, Urbana. Rabindranath Tagore came to the University of Illinois in 1911-12, to visit his son, who was studying Agriculture here. Each year, a festival is held in mid-October to commemorate his stay. Interestingly, it was during his stay in Urbana that Tagore learnt about his Nobel Prize for Literature.

The program was great : we didn't attend the session at noon, but others told us that the violin session was great. We reached there at the start of the afternoon session, when local artists were singing Tagore songs. Also there were several dance presentations. It was a well-planned, and well-rehearsed program. Also, it was great to see so many Bengalis gathered together for such a nice cultural program.

Qual Lunch at Mandarin Wok

2005-03-11T14:34:00.000-06:00

Our Group at NCSA went for a lunch at Mandarin Wok on Green Street. Bill is definitely one of the most enthusiastic persons I've ever met ... he was even more enthusastic about the 3 of us taking quals (me, Joe and Adam). Well, we all passed ... unlike last year (when some didn't). I met 2 new people from Prof. Han's group, Chao Liu was the one who also took quals this year.

Always good to meet new people ....

:)

PS: The food at Mandarin Wok sucks.

Passing Qual makes me feel like a King!!

2005-03-10T16:15:00.000-06:00

No more taking 3 crappy courses. No more going to prof. for a progress report. I am free....

And now I can start my very own research work ...

Cool.

Passed Qual!!!!

2005-03-04T13:24:00.000-06:00

I passed my qual!!!!! So officially, I'm a full PhD student now!!!!!

Hurray...... I am finally getting a PhD for sure......

Qual

2005-03-03T18:35:00.000-06:00

I am still waiting for my quals. It is really frustrating to take it on the 14th Feb, and wait till 3 weeks!! The results were printed today, but wouldn't be posted due to the silly fact that the person who has to carry it from CS Office to Mail room is not there. !!!!!

I know I did ok, but still the wait is too bad.

Google suggest

2004-12-13T15:56:00.000-06:00

Google suggest is awesome!!!!!!!!! I wonder how they can make it so fast and work in real time!!

Snowflakes

2004-12-13T15:43:00.000-06:00

It is snowing in Champaign-Urbana. Well, not snow, but more of an endless torrent of flurries. I checked some snowflakes to see if the saying "No two snowflakes are alike" is true or not.

The temperature outside is about -4 c (21F). Too chilly for me!!