# Finding Lane Lines on the Road

Wrote my first Medium article about “Finding Lane Lines on the Road”. All the code can be found at this github link. The stacks I used are python, OpenCV, and computer vision algorithms. For example, edge detection via Canny algorithm, line detection via Hough Transformation.

The lane detection snapshot of a video.

White lane:

Yellow lane:

# sort list via selection sort

```struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:

head->next = NULL; // set up the termination condition
while (cur){
ListNode *nxt = cur->next;

if (cur->val < brk->val) {
cur->next = brk;
}
else {
while (brk && brk->next && brk->next->val <= cur->val){
brk = brk->next;
}
cur->next = brk->next; // propagate the NULL, a smart move!
brk->next = cur;
}
cur = nxt;
}
}
};
```

# What innovations in CS theory from the last 10 years have had an impact outside of academia?

Well, let’s see.

• Bloom filters are a clever technique that gives practical solutions for a wide variety of problems. The basic idea was first invented in 1970 and saw practical application throughout the decades since then, but theorists picked it up again around 2000 and have devised a long line of variations that have made Bloom filters useful (and in fact used) for many more diverse tasks. See [1] for a survey.
• Streaming algorithms is an area of CS theory that has produced a large number of novel algorithms that make analysis of large datasets tractable. The name was coined about 15 years ago in a paper of Alon, Matias, and Szegedy; much of the work was done in the past decade. Network routers and other devices processing giant streams of data use these algorithms by necessity. See the Wikipedia article [2] for an overview and many links.
• Lattice-based cryptography and post-quantum cryptography generally — this is an area whose major real-world impact has not yet happened, but it’s unusual in that we can be pretty confident it will happen. Quantum computers are coming within the next few decades. When they do, they will make it easy to factor numbers and to compute discrete logarithms, destroying the security of many of the most widely-used cryptosystems that protect the Internet. The last decade has seen a great deal of work on other families of cryptosystems, with a focus on bringing them all the way to practice so that as quantum computing develops we’ll be ready to use them. See http://pqcrypto.org/ and in particular [3]. As a bonus, some of these cryptosystems have practical application today, even without the threat of quantum computers.
• Distributed hash tables, as Nelson pointed out, are another good example. Rather than duplicate his description, I’ll just add a pair of links: the Wikipedia article [4] for lack of a better survey, and one of the early papers [5].

These are just some examples that I happen to know about because of the people I know and the things I was interested in when I was in academia; someone who’s really followed the field well could doubtless produce a much longer list.

So, turning to your follow-up questions, does theoretical computer science matter? Yes, some of it definitely does. Some machine learning research matters too.

Should you go into it as a career? If you’re interested in practical impact, probably not. The incentives in academia don’t reward practical impact, and you have to constantly move against the grain if you want to work toward such impact. I’ve observed this not only in theory but in systems, where grad students do things like write operating systems from scratch in C and assembly, and which might seem as far from theory as it’s possible to get. So I doubt it’s any different in machine learning either.

Instead, if your goal is to have a big impact, you should probably just head for Silicon Valley. Here it’s all about the practical impact, there are plenty of people ambitious to change an industry or the world, and some of them do.

[1] Andrei Broder and Michael Mitzenmacher. “Network Applications of Bloom Filters: A Survey” (2005). http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf
[2] http://en.wikipedia.org/wiki/Streaming_algorithm
[4] http://en.wikipedia.org/wiki/Distributed_hash_table
[5] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications” (2001). http://pdos.csail.mit.edu/papers/chord:sigcomm01/

What innovations in CS theory from the last 10 years have had an impact outside of academia?

# Faster, I say! The race for the fastest SDD linear system solver – STOC 2014 Recaps (Part 9)

Look forward to seeing the results on the simulation solver. The connections between SDD solver to matrix exponential.

Not so Great Ideas in Theoretical Computer Science

In the next post in our series of STOC 2014 recaps, Adrian Vladu tells us about some of the latest and greatest in Laplacian and SDD linear system solvers. There’s been a flurry of exciting results in this line of work, so we hope this gets you up to speed.

The Monday morning session was dominated by a nowadays popular topic, symmetric diagonally dominant (SDD) linear system solvers. Richard Peng started by presenting his work with Dan Spielman, the first parallel solver with near linear work and poly-logarithmic depth! This is exciting, since parallel algorithms are used for large scale problems in scientific computing, so this is a result with great practical applications.

The second talk was given by Jakub Pachocki and Shen Chen Xu from CMU, which was a result of merging two papers. The first result is a new type of trees that can be used as…

View original post 1,858 more words