akrish

I’m continuing to learn Haskell in my free time and as I like to learn by doing, I’ve been implementing common algorithms in the language. Last week I tackled depth first search and found it to be surprisingly challenging and consequently really educational. Today, I decided to try my hand at dynamic programming. I chose dynamic programming because these algorithms hinge on memoization, and I wanted to figure out how to do that in a purely functional way. Also, I thought that I could do some performance analysis, as implementing recursive, un-memoized algorithms to solve these problems seemed to be quite easy.

The first algorithm I tried to implement was the standard edit distance algorithm. It’s a classic DP algorithm and although no longer used much in practice, it is the basis for several modern techniques used in sequence alignment, so I figured it would be an interesting exercise. I spent an hour or so thinking about how to approach this and even started programming a solution, but I quickly got bogged down in maintaining a matrix of subproblem solutions. I found implementing all of these matrix operations to be quite mundane and decided to start with something a bit less tedious.

So I chose another classic DP problem, Longest Increasing Subsequence. Briefly, the problem formulation is: Given a list of (lets say) positive, unique integers, find the length of the longest subsequence such that the subsequence is strictly increasing. For example, given [1, 4, 2, 3, 9], the longest increasing subsequence would be [1, 2, 3, 9]. Read the wikipedia article for more details. I chose this problem because you don’t have to maintain a matrix of subproblem solutions, but rather a list, and the problem is quite a bit simpler, allowing me to focus on the algorithmic elements.

So, I started out by implementing a naive un-memoized algorithm, then went on to implement the dynamic programming algorithm that’s based on the one on the wikipedia page, but in Haskell it doesn’t really look the same at all. I implemented both so that I could do run some performance metrics which I’ll discuss about after presenting my code. First some auxiliary stuff:

[code lang="lisp"]
-- return the item in the list indexed by i --
listGet :: [Int] -> Int -> Int
listGet lst i =
if i == 0
then (head lst)
else
listGet (tail lst) (i-1)

-- return the index of item i in the list --
getIndex :: [Int] -> Int -> Int
getIndex lst i =
if (head lst) == i
then 0
else
1 + (getIndex (tail lst) i)

-- given a list of integers, return the largest value in the list --
listMax :: [Int] -> Int
listMax [] = 0
listMax lst =
if (length lst)==1
then (head lst)
else max (head lst) (listMax (tail lst))
[/code]

I admit I should have used arrays for this but I kind of started using lists before having to implement these and was too lazy to change it. I would change it now but I’m worried about breaking things right before posting and since I’m probably (read definitely) never going to look at this again it really doesn’t matter to me.

Anyway, so we have three functions that are all pretty straightforward. One essentially treats a list as an array and gets the i-th element from the array. Another does the reverse, it gets the index of an item in the array. Finally the third computes the max over a list.

My first algorithm is a naive approach that is just recursive with no memoization:

[code lang="lisp"]
-- compute the longest increasing subsequence starting from each index in the list --
longestIncreasingSubsequence :: [Int] -> Int -> [Int]
longestIncreasingSubsequence [] _ = []
longestIncreasingSubsequence lst i =
if (length lst) == i+1
then [1]
else
[(1+(listMax
(map (\x -> head (longestIncreasingSubsequence lst (getIndex lst x)))
(filter (\x -> (listGet lst i) < x)
(filter (\x -> (getIndex lst x) > i) lst)))))]
++ (longestIncreasingSubsequence lst (i+1))

-- compute the longest increasing subsequence of the list --
lis2 :: [Int] -> Int
lis2 lst =
listMax (longestIncreasingSubsequence lst 0)
[/code]

Ok so longestIncreasingSubsequence is a bit confusing and the comment is kind of inaccurate. If you call it with i == 0, then it’ll return a list where each j-th element is the value of the longest increasing subsequence that starts from and contains the jth item of lst. It basically computes the solution to all of the subproblems, but it doesn’t compute them by memoization. It’s similar if you start with i != 0 but the list only has a suffix of the subproblems. It computes these results by following the standard recursive formula: look at each j>i such that l[i]

This was a good exercise but not really what I wanted to do. So I tested that a bit and made sure it was correct, and proceeded to think about the dynamic programming algorithm. I found it a bit difficult to actually memoize the solutions, but here's what I came up with:

[code lang="lisp"]
-- given an array of subproblem, find the largest increasing subsequence starting at i --
dplis :: [Int] -> Int -> Array Int Int -> Int
dplis lst int arr =
listMax
((map (\x -> 1 + arr ! (getIndex lst x))
(filter (\x -> (listGet lst int) < x)
(filter (\x -> (getIndex lst x) > int) lst))) ++ [1])

– compute largest increasing subsequence starting at int –
getDPScores :: [Int] -> Int -> Array Int Int
getDPScores lst int =
if (length lst) == int+1
then array (0, ((length lst)-1)) ([(i, 0) | i <- [0..((length lst)-2)]]++[(((length lst)-1), 1)])
else
let arr = getDPScores lst (int+1) in
arr // [(int, dplis lst int arr)]

– compute largest increasing subsequence of list –
lis :: [Int] -> Int
lis lst =
listMax (elems (getDPScores lst 0))
[/code]

So I hope the functions make sense. dplis just does lookups in the array parameter to compute the longest increasing subsequence starting at and including i. getDPScores builds the array of subproblem solutions, starting from the smallest subproblems and relying on dplis. Finally lis is just a wrapper for calling getDPScores with the right parameters.

One noteworthy thing is the flow of the program. It's tail recursive. So the first thing we do is get to the bottom of the recursion of getDPScores, then we really do our computation as we work our way out of that recursion stack. Each call to getDPScores after returning from recursion still has to call dplis. Of course there are a lot of tail recursive algorithm, but I didn't really expect dynamic programming to naturally flow like this. Typically dynamic programming is done iteratively, but I suppose we can't do that here.

So those are my two implementation, now on to performance stuff. I decided to experiment with this just to see how amazing dynamic programming really is. If you notice the first algorithm I implemented is definitely exponential (in the worst case, imagine a ascending list of length n, then each call has to spawn O(n) smaller calls). I think it's O(n^n) but I haven't thought too much about it so please correct me if I'm wrong. Anyway, the second algorithm is O(n^2), you just recurse straight down and pop all the way back up. At each recursive call you may have to look at O(n) neighbors and there are only n recursive calls.

Given the asymptotic running times, I expect the second algorithm to be far superior to the first in actual running time. Just for fun I decided to run this experiment and plot my results. I generated random lists of sizes ranging from 5 to 70 in increments of 5 and ran each algorithm on the same lists. Here are the results:

exponential vs quadratic times

They are pretty much what I expected. Notice that the y axis is log-scaled, so that for input length 70, the exponential algorithm took around 10 minutes (600 seconds) where the dynamic programming one takes well under a second. Really amazing how dynamic programming helps that much. I had originally intended to run on larger input sizes but I simply couldn't as the exponential algorithm wouldn't terminate.

As I did in my last Haskell post, I did a quick search for other people who had looked at dynamic programming in Haskell. I found this article which walks through an implementation of the knapsack algorithm and it appears to be much more elegant than mine. Of course you should remember that this I'm still a Haskell newbie so I don't have mastery over most of the features and I really don't expect myself to be able to implement elegant solutions. However, he does mention that dynamic programming is quite natural in functional languages and that you can take advantage of lazy evaluation, which I can understand. Also the knapsack algorithm uses a matrix of subproblems, so it's slightly different and more interesting.

I also found this article that implements the Needleman/Wunsch algorithm for global sequence alignment, another classic dynamic programming algorithm. This was also an interesting read, and he used some language features that I haven't used and barely knew existed so it was definitely educational. Also, this algorithm also uses a matrix of subproblem solutions so I'm thinking that my next experiment will be with more one of these dynamic programming algorithms.

So, In conclusion, I'm feeling more confident in my functional thinking and my Haskell programming. In my previous post, Jedai commented that I shouldn't consider arrays as cheating, and so I have adopted them into my repertoire here. Further, as proof of the importance of algorithm design and asymptotic efficiency, I generated some performance numbers to show how essential it is to have efficient algorithms.

Anyway... there's a leak in my ceiling and water is dripping all over the place so, until next time!

It’s been awhile since I wrote about Israel and what I’m up to so here goes…

If you read my last post about Israel, you’d know that I played in an ultimate tournament, met a bunch of people through ultimate and have been having a generally good time. So that was two weeks ago (the week of June 14-18th) and yeah that week was pretty awesome. I hung out a lot with people I had met through ultimate and had a lot of stuff to do.

That wednesday, I hung out with my friend Steve, and in part of our hanging out we went to a Falafel stand in town. Now this is ordinarily uneventful news, except on Thursday night, I went to play ultimate with a local team and got dropped off pretty close to my house, but I was so weak that I could barely make it up to my room. Fortunately, the next day was Friday (the weekend), so I spent that day pretty much sleeping. I think I slept like 18+ hours on Friday alone.

Turns out I got food poisoning. I’m pretty sure it was from the falafel, because that was the only out-of-the-ordinary thing I had eaten that whole week. So Friday I was really miserable but managed to sleep a lot and I felt quite a bit better by the next day. On Saturday, a family that I know here offered to pick me up and let me get better at their house. They called a doctor who, although he barely spoke english, managed to diagnose me and prescribed me some antibiotics. I spent the day and night at my friends’ house and they really took good care of me.

I took Sunday off, but I was feeling much better and moved back to my room. I decided to go to work on Monday. From then on the week was fairly uneventful, work had its share of ups and downs; there were times when I didn’t really have anything to do, and there were times when there was tons of interesting work to do. This coming week, Igor (the grad student who I am working with) and Professor Shamir will be away at a conference, so they gave me a bunch of stuff to do that should keep me busy.

Other than that, during the week, I really didn’t do much. I was still a bit shaken up from being sick and didn’t want to push myself and get worse. I pretty much hung out in my dormitory and kept myself busy.

Yesterday though, I went into town with Jake, my neighbor who is pretty much doing the same thing as I am in Israel. We wandered around for awhile and found a place to eat when my friend Jesse (from ultimate) called and said he was having a barbeque and invited us to stop by. It turned out the place we were eating was directly under his apartment so we ate and headed up to his place. The barbeque was awesome, I met a bunch of naturally english speaking med students, ate some really good food, and had a great time hanging out on Jesse’s roof.

And today, I went into Jaffo with two of my friends, went to an amazing hummus place, wandered around the flea market and then went to the beach. The beach was relaxing and I’m disappointed that I haven’t been spending more time there. I guess it wouldn’t be as much fun if you go by yourself, but now that I have friends to hang out with, I think I will be taking advantage of the beach that’s 10 minutes away!

So the last couple of days have been pretty jam-packed and fun, but the week preceding was horrible. And of course things are exaggerated because I was sick, but I think I’m going to have my ups and downs here. There’ll be times when I have a bunch of stuff to do and will barely realize I’m away from home, and there’ll be times when I’m just dying to fly back to the states. There seems to be an inverse correlation between how social I am and how much I want to go home. When I was sick and couldn’t hang out with people, I really just wanted summer to end and to go home. But these past couple of days, I’ve been kind of sad that I only have a couple of weeks left here.

And that’s the last couple of weeks. Up next, I’m working tomorrow so that I can take Wednesday off and go travel to the the Sea of Galilee. And I’m also planning a trip to Petra in Jordan, which is supposed to be amazing. Stay tuned!

A couple of months ago, I suddenly had this desire to learn Haskell. I was working on my compilers project (obviously) and randomly thought it would be cool to know and use a purely functional language for whatever reason. Plus, I’ve been reading about Haskell a bit on blogs and stuff and one of my friends uses it pretty regularly so I figured I’d give it a shot.

Why learn Haskell? I’m not sure if I’d ever really need to use it, but of course I may have a job where I program in a purely functional language and then it would certainly help. But more importantly, I wanted to challenging myself to thinking in a new way, and of course it’s good to have another tool in our tool belt. For more general reasons to learn Haskell, check this out.

Anyway, about 2 months ago, I went to the Haskell website, downloaded GHC and started reading this as a tutorial. I knew some of the basic stuff, like that Haskell is purely functional and whatnot but that’s a good document to read to learn about some of the design decisions and of course it serves as a tutorial. I didn’t get very far in the tutorial due to school and other responsibilities

That was 2 months ago. Last night, I decided to re-start my foray into Haskell and went through several chapters of the tutorial. I’m not done with it, but I hate learning by reading and decided that I’d learn by doing. So I set out to implement some “simple” algorithms in Haskell and see how/why they are different from the traditional implementations. Now of course my code isn’t the best written Haskell (because I’ve been writing for less than a day), and I’m pretty sure there are better ways to implement these algorithms, but it was definitely a good learning experience.

Note: I didn’t want to use some of the more advanced Haskell features like monads largely because I don’t really understand them yet, and also because I wanted to keep my algorithms really pure and functional. I don’t yet buy that monads are within the rules of haskell’s purely functional-ness, but I’m sure I’ll understand that later on.

One of the algorithms I especially struggled with was Depth First Graph Search. At first, I didn’t expect it to be very challenging because DFS is naturally recursive and that’s pretty much the common way to write algorithms in Haskell anyway. So I started out with some data type definitions and some functions to manipulate the data.

[code lang="c"]
---- a Node is an index and an adjacency list ----
data Node = Node Integer [Integer]

makeNode :: Integer -> [(Integer, Integer)] -> Node
makeNode ind eList = Node ind
((map (\x -> snd x) (filter (\x -> (fst x)==ind) eList))
++ (map (\x -> fst x) (filter (\x -> (snd x)==ind) eList)))

getAdjList (Node _ b) = b

getId (Node a _) = a

instance Show Node where
show (Node a b) = "Node " ++ show a ++ " " ++ show b

---- a Graph is a list of nodes ----
data Graph = Graph [Node]

instance Show Graph where
show (Graph x) = foldl (++) "" (map (\y -> show y ++ ['\n']) x)

makeGraph :: Integer -> [(Integer, Integer)] -> Graph
makeGraph numNodes edges = Graph (map (\x -> makeNode x edges) (enumerateList numNodes))
[/code]

So hopefully that is relatively straightforward. My basic graph structure is a list of Nodes, and each Node is a just a tuple containing an index and a list of neighboring node indices. And how concise is that makeNode function… I love it! There’s also a function to make a graph out of a list of edges, and it basically just calls makeNode a bunch of times.

Ok then my first approach was to try and implement a standard DFS. It looked something like this:
[code lang="c"]
---- just the type signature of getNode. Implementation is too long and boring ----
getNode :: Graph -> Integer -> Maybe Node

---- run depthFirstSearch starting from ind, return the list of reachable nodes ----
depthFirstSearch :: Graph -> Integer -> [Node]
depthFirstSearch g ind = foldr (++) [fromJust (getNode g ind)]
(map (\x -> depthFirstSearch g (getId x))
(map (\x -> fromJust (getNode g x)) (getAdjList (fromJust (getNode g ind)))))

[/code]

So yes this is unnecessarily complicated, (you don’t need the last map because depthFirstSearch takes integers anyway. It’s like applying a function, then applying the inverse right away.) However, the whole routine is wrong and I introduced the complication as I thought about how to fix it. It’s wrong because in a nested call to depthFirstSearch you have no idea what nodes you’ve visited. And using this approach, at best you can know the nodes that are on the path from the current node to the root, but you cannot know about the other nodes that you’ve already visited.

For example, supposed I have edges = (1, 2), (1, 3), (2, 3) and I call depthFirstSearch (makeGraph 3 edges) 1. What happens? Well, we “visit” node one, and then call depthFirstSearch (makeGraph 3 edges) 2. This obviously calls depthFirstSearch (makeGraph 3 edges) 1 and so on ad infinitum.

Ok so we can quickly fix this infinite recursion problem. By removing the current node from the graph before we recurse. But this still doesn’t fix all of our problems. Now while visiting node 2, we recurse to node 3, then we back up to node 1 and visit node 3 again. At the top level, we have know way of knowing that we already visited node 3 earlier.

So if we’re doing tree search, the above algorithm (with the “remove current node” adjustment) should work. Actually there are some minor adjustments: Here’s my final Depth First Search for Tree Search:

[code lang="c"]
---- run depthFirstSearch starting from ind, return the list of reachable nodes ----
depthFirstSearch :: Graph -> Integer -> [Node]
depthFirstSearch g ind = foldl (++) [fromJust (getNode g ind)]
(map (\x -> depthFirstSearch (removeNode g ind) (getId x))
(map
(\x -> fromJust (getNode g x))
(filter
(\x -> isJust (getNode (removeNode g ind) x))
(getAdjList (fromJust (getNode g ind))))))
[/code]

So a good detour but not really what I was after. Figuring out how to get DFS graph-search to work wasn’t trivial for me. After a couple of hours here’s what I came up with:
[code lang="c"]
dfsIterateOverNeighbors :: Graph -> [Integer] -> [Node]
dfsIterateOverNeighbors g toVisit =
if length toVisit == 0
then []
else
let firstNode = fromJust (getNode g (head toVisit))
newG = removeNode g (getId firstNode)
neighbors = (filter (\x -> isJust (getNode newG x)) (getAdjList firstNode))
in [firstNode] ++
(dfsIterateOverNeighbors
newG
(neighbors ++ (filter (\x -> (not (contains x neighbors))) (tail toVisit))))

depthFirstSearch g ind =
dfsIterateOverNeighbors g [getId (fromJust (getNode g ind))]
[/code]

So, let’s look quickly at how this works. Basically, depthFirstSearch immediately calls dfsIterateOverNeighbors (which is probably not well named but whatever) and this function does some magic. Actually, all it really does is maintain a stack of nodes to visit, and visit them in stack order. Each time you visit a node, you also remove it from the graph for subsequent “iterations” to know that you’ve visited the node. Finally, I’m careful about what nodes get put on the stack, not allowing nodes that I’ve visited already and cleaning up the backside of the stack with nodes that I figured out I’ll visit sooner than I had previously thought.

So, in thinking about this. I realize this is basically an iterative DFS algorithm. A lot of “state” is maintained as function arguments, and the whole thing works tail-recursively. You do a bunch of work, then tell the next guy to do some stuff, which seems a lot like imperative programming. But it is pretty interesting that to make a “simple” recursive algorithm work in a functional setting, I essentially made it more imperative.

So I was relatively happy with this solution and decided to check my answers. I looked at what other people have done online and found a couple of interesting things. Most notable was this paper that uses mutable Arrays to implement Depth First Search in linear time. However, immutable arrays are “cheating” by my standard so these guys don’t have a solution to my problem.

I also ran across this thread that is loosely related. Actually I only really found the first two posts related but essentially it seems that it is quite challenging to implement DFS in linear time without using some mutable state. In looking at my algorithm, I’m pretty sure it’s quadratic (O(|V| calls to dfsIterateOverNeighbors and in each call you have to walk across toVisit which is also O(|V|)). However, I could not find a “better” way to implement Depth First Search under my somewhat arbitrary restrictions.

In conclusion, my first experience with Haskell was kind of cool, I had to think really hard about something that is usually pretty trivial but I did come up with a decent solution and learned a bunch of language features along the way. I think I will keep trying to implement various algorithms in Haskell whenever I get free time and maybe I’ll write about it too.

With my senior year of college looming forbodingly on the horizon, I realized that I’m almost at that point where I have to make one of the biggest decisions of my life: I need to decide what I’m going to do after I graduate.

If I were Israeli this wouldn’t be a problem yet. I’d just be getting out the army, I’d go travel for a year or two, then I’d have to make the decision as I prepare to start college. Of course I only know this because I’m here, and
everyone around me is starting their undergrad at the ripe, young age of 22. I wish I could procrastinate it for at least a year longer.

Alas, this is probably not possible. I’ve procrastinated for too long already. However, this is not a lost cause. I’ve made huge strides in deciding that I want to pursue a Ph.D. in computer science, which I guess I decided sometime during this last school year. To read about why I want to pursue research, read this. There are still many questions to be answered, the most important of which is: What area of computer science do I want to devote the next 4-6 years (and possibly the rest) of my life to?

For some people this isn’t a challenge at all. Some people take a class, love it, start research in that area and that’s it. Sometimes, I wish I were like those people, but things didn’t work like that for me. I’ve really enjoyed almost all of the computer science class I’ve taken, and although I’ve only done research in a couple of areas, I can see myself doing research on a variety of different topics. I really enjoy reading about the research being conducted in areas as broad as operating systems, distributed computing, databases, programming languages, algorithms, theory of computation, security, network security, artificial intelligence, machine learning, and computational biology.

Aside: Actually, I’ve know about this problem for a long time. Whenever some asks me what I’m interested in I generally say “almost everything.” Most people think this is a good thing and I for the most part agree. It’s only if you plan on devoting yourself to one specific area, that it becomes “bad.”

That by the way is a list of candidate fields that I’m considering. There are two observations from this list: the first is that many of the areas are quite related. Like operating systems, distributed computing, and databases are “similar” in that they are often lumped together under the term “systems.” Same with algorithms and theory of computation and of course AI, ML, and Bioinformatics are very closely related. The second observation is that I could work on two of these things. For example, one of my current research projects would probably be classified under programming language security. This is a definite possibility, and something that I currently feel will probably end up happening.

On sort of another related side note: It doesn’t really matter what decision I have to make soon, it’s more of the fact that I HAVE to make a decision soon. Seriously, I’m not even 21 yet. How am I supposed to know what I want to do with my life? This is one of the things that really scares me about graduating (and there are many, many more, but living on my own in Israel is really preparing me to face some of them, and making things a lot less scary in general).

So how do I deal with it? How do I decide what to do in grad school, in my limited time frame of say 3 months?

My research experience has been largely in security, and I’ve been working in bioinformatics for 3 weeks now (oh my god only six more weeks in israel!). I really like both areas, so even between these two it’s very hard to decide. It’s
not something I can directly compare because my experience in each area has been very different. Even with experience, I can’t tell which one I like better, so who’s to say that I won’t like some other area that I haven’t tried equally or more? I don’t have time to get a feel for research in every thing I’m interested in.

So I’ve been stressing out about this for the past week or so, since my parents kindly reminded me that I need to start thinking about grad school. In my opinion, the next best thing to actually conducting research is to read about research, so I’ve compiled lists of papers for each area that I plan to read over the next couple of weeks. It’s going to be a lot of reading but from what I’ve already done I think it will really help me make this decision.

I wanted to write about israel about once a week, but this past weekend was really busy (read on for why) so I didn’t get around to it. Plus my weeks have been pretty uneventful (until now…) so there wasn’t much to write about.

So last week (week 2 of work) was, as mentioned, pretty uneventful. I’ve gotten used to going to work in the morning, spending most of my day there, coming home and working, watching tv, or otherwise passing time at night. In my previous post, I commented that the dormitory isn’t a very social place and that definitely still holds. In fact, now that I’ve stopped trying to be social, it’s become even more so. Thus, I typically come home, make some dinner, and head to the lounge where I do work, watch tv (online), or otherwise waste time on my computer. So usually life is just that.

Last Tuesday, I went to play ultimate with the Holy Landers, one of the few teams in Israel. We “practiced” in a town called Rishon, a bit South of Tel Aviv, so I got a ride from one of the players. Practice was really fun, it was good to get back into playing again. I also met a bunch of people from the states, who have been playing ultimate for years and are quite good.

I’ll get back to what I did on Friday, but on Saturday I participated in a Hat Tournament at the nearby Hayarkon Park. The tournament was very different from the tournaments I’d been to, in that teams were created on the spot (I guess that’s how hat tournaments work) and the games were very relaxed. There were two “divisions,” a youth division and an everyone else division. I was amazed that the youth division had like 25 people and the adult division had around 50. People came from all over Israel, but I definitely did not expect to see such a good turnout. There were 5 teams in my division and consequently I got to play 4 games.

Apart from the ultimate, which was pretty awesome, the tournament was a great chance for me to meet a lot of different people here. I met some of the kids, some other natives, and a lot of people who are originally from the states or other english speaking places like Canada and New Zealand. Since the tournament, I’ve been hanging out with many of these people, and I think they will be my core group of friends during my stay.

Even at school, ultimate was my way to meet people and branch out from my existing group and I felt that this year was a lot more interesting because of ultimate. Now in Israel, ultimate is again a really great social tool. Since I’m not really in a happening place, and since my living environment isn’t that social, I’m relying on ultimate to kick-start my social life and so far it’s working. How ironic is it that I just met someone from the states in my dorm, and he seems pretty cool.

So this week, I was supposed to play ultimate yesterday, today, and tomorrow, and practices got cancelled so I went to throw with a couple of the people that live “close” to me. And it’s definitely good to get out of the dorm and to go around town and stuff. Tomorrow, hopefully I’m going to go into Tel Aviv to hang out with someone else from ultimate. So life is good this week. I’m actually pretty busy and unable to deal with the minor crisis of choosing what I want to study in grad school.

In other news, on Friday I went to Haifa to see the Baha’i Garden. The gardens were amazing and Haifa seems like a really cool town. I only wish I could have spent more time there, but it was Friday, and everything stops/closes early to prepare for Shabbat, including the trains. I took a bunch of pictures but I don’t have any more space in my Flickr account until August. As soon as I get space, I’ll upload them.

Work is also going pretty well. I’m still working on the same project, but basically we are happy with how fast things are running and are now looking at improving “correctness” of the results. By correctness I really mean, massaging our algorithms to spit out solutions that are biologically significant. We are also trying to make the algorithms find similar quality solutions. So this week I’m mostly generating a bunch of statistics and analyzing them so we can figure out how to move forward.

I mentioned this mid-life crisis I’m having and it’s pretty serious. I plan to apply for graduate schools in the fall, but I don’t really know what area I want to focus in. I’ve been doing a lot of thinking, and researching about it and I think it merits its own post (I’ve noticed myself saying this a lot recently…).

Finally, some food related things: croissants here are really good, I’ve been eating a lot of them. I also went to a really good hummus place with some ultimate players after the hat tournament. It was a small place, near the harbor, and unfortunately I don’t remember the name, but their hummus was excellent. In haifa, I ate at a really good cafe near the entrance to the Baha’i Garden, where I got a mozzarella, pesto sandwich and a salad. The sandwich was one of the better ones of that kind that I’ve had.

In summary, things have really picked up here. I’m really glad that I play ultimate, and that it’s a pretty big thing here too.