finding "good work" in CS

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

finding "good work" in CS

Dennis Raddle
It's me again, guy aged 45 thinking about doing graduate work in CS.

I read this ebook about a guy's CS PhD, "The PhD Grind":
It was enlightening. I used to think that software in the C.S. academic world must be well-written, seeing as it was written by computer scientists. (I didn't like the poorly organized and simple-minded code involved in my last job at NASA.) Turns out that academic code can be very poor indeed, sometimes just a hacked prototype meant to demonstrate an idea to get it published. It may be the youngest PhD students who are assigned the job of cranking out such prototypes.

So what do I want to do for my life's work, once I can overcome this illness and get back to work full-time?

I hope I can work with beauty in some form. I find Haskell to be beautiful, for instance. I like ideas, but I also like the process of implementing ideas in a quality way. I may not be suited to the academic world because I need to spend at least some of my time as a craftsman of code, doing something well.

Is there an area with CS academia that is more about elegance, less about hacking up prototypes? The study of languages?

Second, what if I thought of PhD not as a way to enter academia, but as a way to qualify me for the more interesting and creative C.S. jobs out there? What kinds of C.S. jobs involve real creative control, an opportunity to do things in an elegant way?

I know that's a very broad question, so maybe those reading could mention single examples or things they've run into. No need to cover everything.

Thanks,
Dennis

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: finding "good work" in CS

Carter Schonwald
the best way to get cool work is to create opportunities! Do great work and make it visible, reach out to businesses. etc

while theres many people on haskell cafe who are happy to try to give advice, i think we're the wrong group to give advice.

1) reach out to your universities alumni network, there'll be many folks in many organizations who may be willing to help / give you advice

2) email organizations that are hiring that you're excited by and where you have some basic fluency in the the skills they need.   The fact of the matter is that for jumpstarting/resuming a career thats been on hiatus, taking a junior role is the best way to get it started.  One good listing that happens every month is the hacker news who's hiring thread, and they list many remote ok jobs too!

best of luck
_Carter


On Sat, Dec 7, 2013 at 6:54 PM, Dennis Raddle <[hidden email]> wrote:
It's me again, guy aged 45 thinking about doing graduate work in CS.

I read this ebook about a guy's CS PhD, "The PhD Grind":
It was enlightening. I used to think that software in the C.S. academic world must be well-written, seeing as it was written by computer scientists. (I didn't like the poorly organized and simple-minded code involved in my last job at NASA.) Turns out that academic code can be very poor indeed, sometimes just a hacked prototype meant to demonstrate an idea to get it published. It may be the youngest PhD students who are assigned the job of cranking out such prototypes.

So what do I want to do for my life's work, once I can overcome this illness and get back to work full-time?

I hope I can work with beauty in some form. I find Haskell to be beautiful, for instance. I like ideas, but I also like the process of implementing ideas in a quality way. I may not be suited to the academic world because I need to spend at least some of my time as a craftsman of code, doing something well.

Is there an area with CS academia that is more about elegance, less about hacking up prototypes? The study of languages?

Second, what if I thought of PhD not as a way to enter academia, but as a way to qualify me for the more interesting and creative C.S. jobs out there? What kinds of C.S. jobs involve real creative control, an opportunity to do things in an elegant way?

I know that's a very broad question, so maybe those reading could mention single examples or things they've run into. No need to cover everything.

Thanks,
Dennis

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: finding "good work" in CS

Richard A. O'Keefe
In reply to this post by Dennis Raddle

On 8/12/2013, at 12:54 PM, Dennis Raddle wrote:

> It's me again, guy aged 45 thinking about doing graduate work in CS.
>
> I read this ebook about a guy's CS PhD, "The PhD Grind":
>
> <http://www.pgbovine.net/PhD-memoir.htm>
>
> It was enlightening. I used to think that software in the C.S. academic world must be well-written, seeing as it was written by computer scientists.

There is a huge difference between *computer science* and
*programming*.  I remember two excellent computer scientists
I used to know, neither of whom had any idea of indentation.
(Seriously, one of them began each function on a new line,
and pressed the RETURN key only at the very end of it.)

Come to think of it, I met another computer scientist who was
writing a library for an exotic flavour of priority queue --
which he understood to a depth I shall never reach -- and was
interested in comparing it against some other priority queue
implementations, and asked me for some advice about the
coding.  I suggested including the classic binary-heap-in-an-
array as a baseline.  It beat the pants off _all_ the other
priority queue implementations.

Here's a piece of computer science that I would like some help
with.  I call it the Indirect Cycle Detection problem.

Given:  Domains P and E,
        functions f : P -> Maybe P
                  g : P -> E

Define  to_list :: Maybe P -> [E]
        to_list Nothing = []
        to_list (Just p) = g p : to_list (f p)

Given:  That f is cyclic starting at p0.

Find:   The shortest alpha, beta such that
        to_list p0    is   alpha ++ cycle beta
        and do so *efficiently*.

Now, I can use tortoise-and-hare to find a cycle in f
and then use brute force to find a shortest prefix and
cycle of to_list ... The stuff I've checked so far
about periods in strings has nothing to say about
periods that begin _after_ a non-empty prefix.  

The point here is that this is a computer science question
which can be answered by someone who has no knowledge of
any programming language.  Indeed, I don't see any reason
to expect that programming skill would help.

> (I didn't like the poorly organized and simple-minded code involved in my last job at NASA.)

And yet we hear amazing things about NASA code quality.

> Turns out that academic code can be very poor indeed, sometimes just a hacked prototype meant to demonstrate an idea to get it published.

Since the declared *aim* of Universities is *published* research,
it is *rational* for code quality to be no higher than is required
to get that job done.

Basically, Sturgeon's Revelation
-- see http://http://en.wikipedia.org/wiki/Sturgeon's_Law --
is a universal truth.

I remember a certain company whose compilers and operating system
were gems of care and readability, yet provided a statistics package
whose code was _nightmarish_, pointlessly bulky, and would
happily invert a singular matrix and keep running.

Had you considered building software checking tools as a topic?

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: finding "good work" in CS

Rustom Mody
In reply to this post by Dennis Raddle
On Sun, Dec 8, 2013 at 5:24 AM, Dennis Raddle <[hidden email]> wrote:
It's me again, guy aged 45 thinking about doing graduate work in CS.


Is there an area with CS academia that is more about elegance, less about hacking up prototypes? The study of languages?

about beauty in mathematical proofs
[And in case you wonder what that has to do with CS -- the guide was E W Dijkstra]



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: finding "good work" in CS

Jefferson Carpenter
In reply to this post by Dennis Raddle
On Sat, Dec 7, 2013 at 5:54 PM, Dennis Raddle <[hidden email]> wrote:
Turns out that academic code can be very poor indeed, sometimes just a hacked prototype meant to demonstrate an idea to get it published.

In that case, it can be helpful to use the right license: http://matt.might.net/articles/crapl/CRAPL-LICENSE.txt 

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: finding "good work" in CS

Kim-Ee Yeoh
Administrator
In reply to this post by Dennis Raddle

On Sun, Dec 8, 2013 at 6:54 AM, Dennis Raddle <[hidden email]> wrote:
So what do I want to do for my life's work, once I can overcome this illness and get back to work full-time?

I hope I can work with beauty in some form.

Beauty is very much in the eye of the beholder.

Have you looked at "Land the Tech Job You Love" by the Pragmatic label? Chapter 1 might be free and well worth the read, approx 10 pages.

Something that strikes me about your emails is that you're focused on your wants and needs. Which is important. But a job is ultimately a trade: you give up X in return for Y.

Grad school these days is no different; admissions DO actively look for that X, even if that X is different from that of a commercial setting.

Think about what those X's might be -- as in, what does the other party want. Feel free to continue the convo on this list!

-- Kim-Ee

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Indirect Cycle Detection problem [was: finding "good work" in CS]

Thomas Horstmeyer
In reply to this post by Richard A. O'Keefe
Hi Richard,

Am 09.12.2013 04:00, schrieb Richard A. O'Keefe:
>
 > [...]

> Here's a piece of computer science that I would like some help
> with.  I call it the Indirect Cycle Detection problem.
>
> Given:  Domains P and E,
>          functions f : P -> Maybe P
>                    g : P -> E
>
> Define  to_list :: Maybe P -> [E]
>          to_list Nothing = []
>          to_list (Just p) = g p : to_list (f p)
>
> Given:  That f is cyclic starting at p0.
>
> Find:   The shortest alpha, beta such that
> to_list p0    is   alpha ++ cycle beta
>          and do so *efficiently*.
>
> Now, I can use tortoise-and-hare to find a cycle in f
> and then use brute force to find a shortest prefix and
> cycle of to_list ... The stuff I've checked so far
> about periods in strings has nothing to say about
> periods that begin _after_ a non-empty prefix.
>

I am not sure if you're really looking for help here or just wanted to
present an example. I assume the former.

Also, I can not see where this "non-empty prefix" notion comes from.
Perhaps you have a different definition for cyclic?

For me: "f is cyclic starting at p0" means there exist an N>0 such that
f^N p0 == p0. Let's assume n to be the smallest number that fulfills
this condition and call it the period length of f_p0.

f_p0 defines a periodic list ps with the same period length n.

ps = map fromJust $ iterate (>>= f) (Just p0)


Your (to_list p0), which I'd like to call es could now be written as:
es = map g ps


We know that es has a period of length n, but if g is not injective, its
smallest period of length k may be smaller than n.

period_n = take n es

To find k, we search for the second occurrence of period_n in (period_n
++ period_n), knowing that it will be at position n, if it is not found
at positions [1..n-1]. We might use the fact that it can only be in
positions that divide n. On the other hand, we could just use any of the
well known string-search-methods.


Efficiency:

- If computation of f is done in constant time, finding n takes Theta(n)
time. Just apply f until you reach p0 again.

- Searching a pattern of size n in a text of size 2n can be done in O(n)
using the Knuth-Morris-Pratt-algorithm.

In total you have a linear algorithm for finding your result:
alpha = []
beta = take k es
      = take k period_n

*****

Of course, I guess now you're going to tell me that your "non-empty
prefix" means that the period of f is not starting at p0 but at some pi
that is reached by applying f i times to p0. You can adapt to that, but
you have to pay for it ;-)

In this case, ps has the form (prefix ++ (cycle p_period_n)) and to find
this structure, you need to find the first element of ps that occurs
twice. (Before, you knew this would be p0.) For that, you need a set
implementation for elements of P that gives you efficient adding of one
element and lookup. Since we know nothing about P's elements, we use the
list itself and get a runtime of Theta((i+n)^2).

Finding the (smallest) period k in es is exactly the same as before,
i.e. we look for the second occurrence of period_n in (period_n ++
period_n) with
period_n = map g p_period_n

The prefix does not bother us here, because we know that we are looking
at the periodic part.

Now that we know the period length k, we still have to find where it
starts. For that we start at position i and go backwards until we find a
difference to the found out period. That is, we find the position of the
first mismatch between (reverse $ take i es) and (cycle (reverse $ take
k period_n)).
The index tells us the length of alpha and the rotation needed to get
beta from (take k period_n).
The cost for that is O(i).

So, the total cost in this case would be O((i+n)^2 + n + i).


I could have implemented this in Haskell, but since the point in the
original discussion was about not needing programmer skills, but CS
skills, I refrained from it. Haskell is only used to clarify points, in
a language which both he recipient and the recipient know. :-)

Thomas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Indirect Cycle Detection problem [was: finding "good work" in CS]

Bertram Felgenhauer-2
Hi Thomas and Richard,

> > [...]
> >Here's a piece of computer science that I would like some help
> >with.  I call it the Indirect Cycle Detection problem.
> >
> >Given:  Domains P and E,
> >         functions f : P -> Maybe P
> >                   g : P -> E
> >
> >Define  to_list :: Maybe P -> [E]
> >         to_list Nothing = []
> >         to_list (Just p) = g p : to_list (f p)
> >
> >Given:  That f is cyclic starting at p0.
> >
> >Find:   The shortest alpha, beta such that
> > to_list p0    is   alpha ++ cycle beta
> >         and do so *efficiently*.
> >
> >Now, I can use tortoise-and-hare to find a cycle in f
> >and then use brute force to find a shortest prefix and
> >cycle of to_list ... The stuff I've checked so far
> >about periods in strings has nothing to say about
> >periods that begin _after_ a non-empty prefix.
As Thomas explained, that's sufficient. The tortoise-and-hare algorithm
will identify a tail of the sequence that is known to be periodic, and
then we can find the smallest period using an algorithm that operates on
a finite string. Once the actual cycle length is known, identifying the
prefix is easy.

> Also, I can not see where this "non-empty prefix" notion comes from.
> Perhaps you have a different definition for cyclic?

See http://en.wikipedia.org/wiki/Cycle_detection .

> In this case, ps has the form (prefix ++ (cycle p_period_n)) and to
> find this structure, you need to find the first element of ps that
> occurs twice. (Before, you knew this would be p0.) For that, you
> need a set implementation for elements of P that gives you efficient
> adding of one element and lookup. Since we know nothing about P's
> elements, we use the list itself and get a runtime of
> Theta((i+n)^2).

The tortoise-and-hare algorithm does this in O(i+n) time.
 
I'm attaching some code. For simplicity, it works with functions
@f :: a -> a@, @g :: a -> b@, which define the sequence
@xs = map g (iterate f x)@. I'm using Brent's algorithm [1] for cycle
detection, which finds the period and a periodic suffix of @iterate f x@,
followed by Duval's algorithm [2] to identify the actual cycle length
of @xs@. (The main advantage of Duval's algorithm over Knuth-Morris-Pratt
is that less space is required. One disadvantage is that we need a total
order on @b@.) The total running time is linear in the cycle length and
initial prefix length of @iterate f x@, i.e. O(i+n).

There are two entry points of interest in the code.

- factor f g x
  Find prefix and repeated segment of @map g (iterate f x)@.
- factor' f g x
  Find prefix and repeated segment of @to_list x@.
  The repeated segment will be empty if @to_list x@ is a finite list.

Cheers,

Bertram

[1] http://en.wikipedia.org/wiki/Cycle_detection
[2] http://stackoverflow.com/questions/3459509/minimal-cyclic-shift-algorithm-explanation

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

duval.hs (1K) Download Attachment