Dave Smith's Blog

Taking a break from computer science and model aviation for the moment, I want to make sure my readership (both of you, not counting my mother) is aware that my company is currently hiring software developers. I know that many developers in the Salt Lake City area have recently found themselves on the job market. I also know that new job opportunities have slowed significantly. Although I take a more optimistic view than most, I readily admit that times are harder today for developers than they were one year ago. Despite the current state of the economy, my company is doing extraordinarily well. If you are looking for work, and you would enjoy working on a small team of engineers solving problems of national and global importance, then this may be the job for you.

At my company, we build the world’s most advanced signal processing systems. Developers here tend to get intimately involved in projects from the early idea stage all the way through delivery. You won’t be an insignificant cog in a massive corporate machine. Although we tend to have a small company feel, we have big company stability and benefits. Our Salt Lake City office of 60 people is actually a satellite office of our California-based headquarters, so we have all the best medical benefits afforded to larger companies, and yet we still maintain that small company feel: no office politics, no bureaucracy, no pigeon-holing, just pure engineering at its best. We have been very fortunate for the past couple years, and now we have more revenue coming in than we’ve ever had before.

As for experience and requirements, I won’t mention the specific technologies we work with since the only real job requirement is that you are smart and get things done. You’ll pick up the job-specific knowledge you need once you start working.

If this sounds good to you, feel free to email me your resume: dave@thesmithfam.org

I look forward to hearing from you.

I came across a graph theory problem at work this week, and decided to blog about it to help me sort it out. At first I didn’t think of it as a graph problem, but that’s how these problems often go, shrouded in disguise and all. But I digress.

The problem is this. Considering the following directed graph, which nodes are the most senior ancestors (speaking in tree terms, of course)?

The answer is that nodes A and B are the most senior, meaning they have the most number of descendants in their sub-trees. This becomes obvious if we draw the same graph this way:

I’m trying to discover an algorithm to identify the senior most nodes given any directed graph. The graph is given as an edge list, like this:

• A -> B
• A -> F
• A -> E
• E -> H
• E -> G
• B -> A (notice the cycle here back to A)
• B -> D
• B -> C
• H -> I

So there’s the problem. I’m looking for an algorithm that will find the top-most nodes given any directed graph. In the case where there is only a single top-most node, it’s easy, but that’s just one case, and I want a general solution. Also, the graph need not be fully reachable from any node. It could be two or more non-connected graphs.

If you have an idea for an elegant solution, please post it in the comments below. I’ll post my own solution next week.

Happy graphing!

Edit:

After thinking about the problem a bit more, I thought I’d add another example with some corner cases that my solution will need to consider. If you look below, you’ll see a graph with a more complicated cycle and a non-contiguous section. The nodes I expect the algorithm to discover are shown in green:

Here are the edge pairs:

• A -> B
• A -> E
• A -> F
• E -> H
• E -> G
• B -> A
• B -> C
• C -> B
• C -> D
• I -> J
• I -> K
• H -> L