akrish

I’m going to continue again from the last post, but as I mentioned here, I skipped several weeks that I promise to get back to. I’ll try to get to writing about the middle bit of my trip over the next couple of weeks.

I’m at home now. I got back two days ago and have been pretty busy or sleeping since then so I haven’t really had time to write anything. It’s really great to be home, I’ve got to spend time with some of my friends and my family and I’ve been playing a lot of guitar because I really missed it in Tel Aviv.

My departure from Israel was sad, but also very characteristic of my trip. The day before I left, Jake and I went to Yafo in the morning (yup we took off the morning) and got hummus at Abu Hassan for breakfast. This was my third trip to Abu Hassan and every time I go there it is simply amazing. One of things I will miss the most about Israel is all of the delicious foods.

That evening I went out for dinner with my lab at this cafe on the pier and that was really great. I had some really good shakshuka. Maybe you can tell that food was a defining factor of my trip… That night I hung out with Jake and some of my friends and unfortunately had to say goodbye to them.

The day of my departure was pretty uneventful. I went to work, didn’t really have too much to do (it was my last day after all) but I showed Igor some of the results of my work and they looked okay. After work, I finished packing, said goodbye to Jake, and Mukul helped me take my stuff downstairs and catch a taxi.

As usual, I started chatting with the taxi driver and he was really cool. We talked for the entire trip to the airport about India, Bulgaria (his country of origin), Israel, traveling, girls, college, languages and everything in between. He was one of the best cabbies of my trip, and it was a great way to end the trip.

After the tedium of airport security I finally boarded the plane from Tel Aviv to Atlanta, Georgia. I sat next to an Israeli-American woman from Palo Alto, and we talked for a decent amount of the plane ride about a hodgepodge of topics ranging from Israeli supermarkets in the south bay to computer science. This was another really pleasant encounter with a stranger, which I really enjoy (see this for why). So the flight went okay and Atlanta was pretty uneventful. The second flight from Atlanta to California was a little depressing because I stopped hearing Hebrew and English had definitely become the default language.

I landed in California, got my bags and my mom was waiting for me outside of the terminal. We drove home and that’s the end of this story!

As I mentioned I do plan on writing more about Israel, especially the middle part that I’ve completely left out, and I’m starting to think I’ll also write something about my parting thoughts on the summer. I’m leaving for Bali tonight and I don’t plan on spending time at a computer there, so this will be my last post for two weeks or so.

So we’re going to skip forward quite a bit in my israel trip to today. I promise to go back and write about the rest of my trip, which was arguably the best part. But now, lets jump to today…

I have 7 days left (by now it’s more like 6). I generally have very mixed feelings about leaving Israel. Part of me really likes everything about being here, except for my dormitory. I have a solid group of friends, I have a great, stimulating job, I get to play ultimate, go to the beach, eat amazing food, you name it. This part of me is really sad to leave.

The other part of me is really excited to go home. I haven’t seen my parents for almost 9 weeks and I haven’t seen my brother for even longer (I think I last saw him in January… ridiculous). Of course I also miss a lot of my friends from home and from college and I’m excited to see everyone. My parents would love to hear me admit this, but I actually miss home-made indian food, though I’m sure I’ll still complain about it when I get home.

So last night I took part in a ultimate game between the two teams in Tel Aviv. In my time here, I’ve gotten to know many players from both teams pretty well, and yesterday I had to say goodbye to many of them, because I’m not sure if I’ll be able to play ultimate again before I leave. And it made me pretty sad. I really liked a lot of the people who I played ultimate with, and unless I come back to Israel or they come to the US, it’s very unlikely that we’ll see each other again.

Fortunately, I did get contact information for many of them, and I plan to keep in touch, but it’s definitely not the same as hanging out or playing ultimate together. I do have a reason to come back though.

And as my time here quickly runs out, I’ll have to say more and more goodbyes to some really great people. I really wish I could spend more time with them before we have to part ways…

Ok wow this post and the previous one were probably really depressing. Don’t get me wrong, I’m not moping around and wasting my last days, I’m “living it up”: doing as much as I can, eating great food, hanging out with my friends and making sure I take advantage of being here. But I do think about the depressing stuff every once in awhile.

Oh yeah, one more reason I’m excited to go home. I’m going almost directly to Bali for a solid week and a half of vacation!

I started reading the news recently (yes I used to not read the news or really care what was going on in the world) and it’s making me really depressed. I subscribed to the New York Times’ RSS feed and here’s what I read about today.

• 16 Dead in Afghan Helicopter Crash – Last week there was the Iranian plane crash that killed over 100 people and now this. The middle east is still as depressing as ever.
• Explosion Kills 9 in Afghanistan – These I.E.Ds are still littering afghani streets and pretty much just wreaking havoc. not good.
• Chinese Question Police Absence in Ethnic Riots – First of all there were massive ethnic riots in China between Uighurs and the Han, and second of all, the police really didn’t do a good job of stopping the initial riots of the Uighurs and the ensuing retaliation of the Han.
• Explosions at 2 Hotels in Indonesia Kill at least 9 – Yup, and I’ll be in Bali in just a couple of days…
• 5 Officers Shot and 2 Suspects Killed in N.J. Melee – And even at home things aren’t pretty. This one is a pretty violent gunfight.

I guess there is some light in all of this but it doesn’t seem like much consolation

• Mauritians See Chance to Break Cycle of Coups – After years of living under military regimes, the Mauritians appear to be having a legitimate election. Of course, the current ruler is a pretty strong favorite to win, and he first came to power via a coup, so while this is good, it’s not all that amazing.
• Signs of Hope Emerge in West Bank – The Palestians, no longer under Hamas, is experience some economic growth and some form of peace. There has been a lot less violence between Israel and Palestine over the last year or so and I personally am pretty hopeful for some sort of peace agreement.

And while most of the world is as chaotic as ever, Israel seems to be relatively peaceful. Of course it’s a pretty precarious peace here, but there haven’t been any commotion since I’ve been here, so that’s pretty good.

I think this is partly why I don’t like to read the news. I guess it’s good to know what’s going on in the world, but when the world is as messed up as it is, it just makes me depressed.

Wow so I wanted to write about my adventures in Israel every week but that totally has not happened. I’m thinking that this is probably a good thing, because it means I’ve been too busy to find time to write in the past couple of weeks. So, what exactly have I been up to? Unfortunately, since I’ve been up to a lot, this post will only cover really one experience.

When we left off I had just recovered from being sick and miserable, and was starting to have a good time with the friends that I’ve made here. I was planning a trip to the Sea of Galilee and I was really excited to see more of Israel.

I didn’t end up going to the Sea of Galilee, but instead went north to Rosh Hanikra and Akko. Rosh Hanikra is a kind of “natural wonder” right on the border between Israel and Lebanon. The Mediterranean Sea has carved these grottos into the cliff wall and you can walk into them and explore these really cool caves (check out some of my pictures pictures). Akko is also a pretty interesting place; it’s a town at the across the bay from Haifa that was used as a kind of fortress during the crusader period. It was also occupied by the Ottomans, so there are a bunch of artifacts from that period too (pictures).

I took a day off of work, because it’s much easier to travel on weekdays than on weekends here, and took a train from Tel Aviv University to Naharriya, one of the northern-most coastal towns. From here I needed to take a bus to Rosh Hanikra, which is about 10km north of Naharriya. Naturally, I didn’t really know how to do this, so I asked a couple of people and they told me to wait at this bus stop. I waited and waited, and buses passed by, but none of them were going to Rosh Hanikra. Eventually, this taxi stopped and asked me where I was going and said he’d take me to Rosh Hanikra. The taxi, although it looked like a normal taxi, was some kind of shared-taxi. He stopped at all of the bus stops and picked up one or two people, and dropped them wherever they wanted to go. I guess it was good because it was much cheaper than a regular taxi.

Anyway, he dropped me at Rosh Hanikra and I went to go ask about admission tickets (It’s kind of a touristy place so of course you have to pay to see the grottos). You take this cable car down from the top of the cliff to where the grottos are and on the cable car I met a bunch of South African high schoolers, who were on some sort of summer trip through Israel. Their “chaperone” was a college student so I hung out with him and his group for a bit before parting ways and wandering around on my own through the grottos. Of course the grottos were really impressive, but it’s hard to capture that in words, so check out my pictures instead.

After wandering around, I took the cable car back up to the top of the cliff and asked about how to get back to Naharriya. Everyone I asked didn’t really seem to know how, so I kind of started freaking out, but one person told me to go wait at the bus stop and a bus would eventually show up. This was still pretty worrisome as I wanted to get to Akko in time for lunch, and it was already approaching noon. There were around 20 army girls waiting at the bus station, apparently also going back to Naharriya, so I started talking to them asking about how they were getting into town. They had called a sherut (a different kind of shared taxi) and invited me to come along with them. Long story short, I met a bunch of army girls and made it to Akko in time for lunch.

Akko was pretty interesting, but not as incredible as I imagined it would be. On the plus side, the markets were really cool, and there were some interesting artifacts from the crusader and ottoman times. I had heard that there was this amazing hummus place in the Akko market so that was my first stop for lunch. These hummus places are funny, because if your party doesn’t fill up a table, they’ll sit other people with you. I was by myself, so I was seated with a German girl and a Mexican guy, who are studying in England. So we ate lunch together and it was pretty fun, they were both interesting people and had some good stories. In retrospect I really like the policy of sitting you with other people because it makes you’re meal a lot more social. And of course, lunch was amazing; seriously it was probably the best hummus I’ve ever eaten, on par (or better than) Abu Hassan in Yafo.

After lunch, I wandered around the old city, saw the harbor, some of the mosques, the sea wall, and many of the tourist attractions. I also wandered around the market a bit and got to see all of the colorful spice stands and experience some amazing smells from food stands. Afterwards, I wanted to go see the Knight’s Hall (where the Templar’s lived during the Crusades) and ran into this French guy who was literally motorcycling the mediterranean (from Algeria back to France). We hung out together and saw the Knight’s Hall and walked through the market again and then parted ways but he was a really cool guy. As for all of the things I saw, just check out my pictures.

As I was leaving, I walked through the market one last time and met an Arab-Israeli who was trying to buy some fish. He also was really friendly and I walked with him and watched him bargain for fish (which was really entertaining). He invited me to lunch, but as I was still really full from my earlier meal and politely declined. Finally, on my way out I ran into the South African kids again and walked with them for a bit. Then I got on a train from Akko back to Tel Aviv University, took the bus back to my dorm and pretty much just passed out. It was a long, busy day, but totally worth it.

One thing I really liked about this day in particular (and most of my time in Israel) is that you meet a lot of random people and all of them are really interesting. Maybe it’s partly me becoming more engaging with strangers, but I find that here I interact with “strangers” a lot more and consequently get to see new perspectives and learn about cool places and things to do. Like on this trip, I met and hung out with the South Africans, shared a taxi with some Israeli soldiers, had lunch with the Mexican and German, explored Akko with the French guy, and wandered the market with an Arab-Israeli. I cannot imagine meeting such a diverse group of people at school, and this is definitely something I’m going to miss about being here.

Definitely this wouldn’t have happened had I been with a big group, which is part of why I really like being here by myself. I’ve made a completely new group of friends, and we’re a small enough group that we still interact with new people. I think if I were here with a bunch of friends then I wouldn’t have met a lot of the people that I did, and consequently I would have missed out on a bunch of great stories and experiences.

So despite planning to spend the day by myself, I met some great people and had good company throughout my trip. I ate good food, saw some pretty spectacular things, met interesting people, and of course, skipped a day of work!

So I took this day-trip the week after I wrote my last post. A lot of time has passed since then so I still owe you many more stories. Work has been keeping me pretty busy but I’ll see if I can find some time to write more during this coming week.

My algorithms professor used to tell his students (including me) this story to motivate studying NP-complete problems and reductions. The story goes something like this: say you’re working as a software developer and your boss gives you this project where you need to come up with a efficient way to do some computation. You go to your desk and think about for awhile and then suspect that there is no efficient way to do the computation. So you can’t just go back to your boss and say, “I think this problem is NP-Hard, so I give up,” you need to show your boss that it’s NP-Hard and this motivates the studying of reductions. It further motivates the study of approximation algorithms and other techniques to cope with NP-Completeness.

I’ve heard this story a couple of times from my professor, but I never really felt like this is something that would happen. How often is it that you are given a problem that doesn’t look intractable immediately, and how much convincing will your boss really need? For that matter how often, in a typical job, do you encounter intractable problems? Like how often does this really happen at a typically development job? Now I haven’t spent too much time in industry and really in my time I never ran into NP-Hard problems so I don’t really know. Although the story was motivational for an algorithms course, the situation used to seem implausible to me. That is until I was challenged to do this myself

This summer, I’m working in a computational genomics lab refining some algorithms for analyzing gene expression data. The core problem we are working on is NP-Hard, but in my refinements, I ran into another NP-Hard problem that I did not immediately see as intractable. I guess this story may be a little bit skewed because I am basically doing algorithms research but I still thought it was pretty cool.

My work deals with finding connected components in a large gene network (an undirected graph). To simplify things, we have a scoring function and want to find connected components with good scores and because of the scoring function this turns out to be NP-Hard, read this for the exact problem and why it’s NP-Hard (The exact problem is a generalization of set cover). Anyway, the basic way we do this is to pick a vertex with a “good” score (called the “seed”) and then expand the module from that node.

In our experimentation, we decided to see what would happen if we allowed seeds to be multiple disconnected nodes and grew our modules from these multi-node seeds. Basically, here you choose k nodes to be your seed and you grow the module out from these seeds, but it is not a requirement that the result is a connected component, in this case it is ok if the resulting module consists of k connected components. The motivation was that from a biological perspective, a disease may affect two or more gene pathways and we wanted our algorithms to be able to account for that, hence allowing multiple connected components.

I set out to implement this feature and was thinking about ways to create these multi-node seeds. I started out by filtering away all of the “bad” vertices and was left with a set of 30-50 good vertices but it was (and still is) not clear what’s a good way to combine these single seeds into multi-node seeds.

My first approach was to simply enumerate all of the combinations and then choose the ones where the individual vertices had good scores. This approach besides having exponential time complexity was bad in that the seeds we selected were all very similar. This was because the individual nodes that were very good were in all of the multi-node seeds we selected. Thus this approach was not satisfactory. Another problem with this approach was that we typically did not see disjoint connected components in the resulting solutions.

To remedy the last problem, we decided on a new approach where we select multi-node seeds where each individual vertex is far from the rest. We compute this by looking at the neighborhoods (typically only 1 level of breadth first search) around each seed and computing the intersection of these neighborhoods. So this seemed like a good approach and we were hopeful this would produce disjoint connected components in the results so I set out to implement this.

Lets restate the problem: Given a set of vertices in a graph, where each vertex has an associated set of elements from some universe U. The goal is to find k vertices that minimizes the intersection of the sets, or such that the intersection of these sets is the empty set.

I thought about this problem for awhile and was quite confident that it was intractable. Before talking to the grad student I’m working with about it, I wanted to have at least a sketch of a reduction in mind. My first reaction was that I should be able to reduce set cover to this problem, possibly by “negating” all of the sets or something. I messed with this for awhile and I didn’t really get anywhere.

I mentioned this problem to some other people in my lab and we all thought about it for awhile. Eventually one guy found that he could reduce independent set to this problem quite easily. If you instead go back to the gene network graph and consider each of the “elements of the universe” as neighbors of the vertices in the graph, then you immediately see that this is the independent set problem. If you treat each neighborhood as a node in a graph, and there is a edge between two neighborhoods if they share an element in common, then you can solve this problem by running an independent set solver on this graph. Conversely, given a graph, you can define a universe of elements and a set to each vertex such that vertices that are not connected share no elements and vertices that are connected share some elements. Then you can look for multi-node seeds and solve independent set. The way I explained the problem above, and the way that I thought about it made it difficult to see that it was independent set, but if you go back to the original problem, it’s easier to see.

Now that I new the problem was NP-Hard, I started thinking about ways to get good enough multi-node seeds and eventually settled on a greedy algorithm that grows the seed sets by adding the node with minimal intersection. The resulting seeds are decent and we did start seeing solutions with multiple disjoint components which is exactly what we were looking for. Despite being faced with a “challenging” problem, we did end up finding a good working solution that gave us the results that we wanted.

This little anecdote, although quite silly in retrospect (because the reduction was pretty straightforward), really showed me that what I learned about reductions and NP-Completeness is important from a practical perspective. It also showed me that my professors story was actually quite plausible. Plus it was another situation where I got to apply things that I learned, and I always find that really cool.