http://www.crazyontap.com/topic.php?TopicId=10624#133296

I'd love to see what the undergraduate CS kids are learning these days...  What's this week's assignment?  What are the courses?

I wish I cared enough to look it up.

I'm in comp sci 230, the lowest level one there is.  C programming for people who have never seen a command line before.  Wow.

Yesterday the prof held me after class to tell me that going for a BS was not what I should be doing, that I should be taking this only as a prereq for a Master's program.  I'm considering it.

He's right. It's silly for you to take a 2nd BS.  BS is done once and you put any MS you want - even unrealated - on top of it.  Given that you know how to program a BS in CS is foolish.

I'm really mostly interested in filling in my gaps of knowledge of algorithms - design, analysis, selection.

I know there is some software out there designed to search algorithm-space, and I want something like that which caches results in a database, and use that in a compiler for code optimization.

Aaron, why are you taking such an intro course anyway?  So you really are there to meet women?

I'm not sure a CS class is the way to go.  You should try the nursing program or something.

"I know there is some software out there designed to search algorithm-space, and I want something like that which caches results in a database, and use that in a compiler for code optimization."

Well, then, your next course should be at least data structures or something with algorithms in the title.

I am very interested, myself, in a course that combines mathematics with data structures so that you can create your own.  Like how to apply math theories to data.

to search algorithm-space
caches results in a database
and use that in a compiler for code optimization.

a course that combines mathematics with data structures
so that you can create your own. 

Like how to apply math theories to data.

=========

fasinating, if half-formed, ideas.  Can you elaborate?

I've considered music, english, art...nursing wouldn't be a bad option, as IUPUI seems to be the primary nursing school in the area.  Just walking around, it sure seems like women outnumber men here, too...but perhaps I am just blind to men.

The prereq for algorithms is C++, 240.  I could probably skip this one, but I hope we hit function pointers soon.  If plain old pointers don't damage these kids, that will.

It's funny - you'd think that I'd be perfectly comfortable with algorithms, since that's what I did for my frickin PhD...but the truth of the matter is, I got lucky.  Guess work, trial and error.  Now, once found, it was work testing the hell out of it, but there was no rational process to finding it at all.

I love gode generators/parsers.  You can manipulate the abstract tree to fit any algorithm you choose.  So, if you can search that space - given input X, and desired output Y, find algorithm Z - you could then store the tree.  Once stored, you could emit that code in any language you have a generator for.

Pattern recognition is also on my list.  Given a certain algorithm, find an equivalent algorithm that is more efficient, snip out the old one and replace it with the new.

Optimizing compilers do similar things all the time, but on a smaller scale.  This is more like source code rewriting.

Well if you know the input and it is discrete, and you know that output and it is also discrete, then your simplest algorithm is to lookup the output using the input as a key.

If you don't know the input, eg. numerous or infinite inputs are possible with possibly distinct outputs, then knowing if you've found a good replacement is quite a challenge.

You should go off and look at stuff by John Koza.

http://www.genetic-programming.com/johnkoza.html

Consider for example slide 5 of this

http://www.genetic-programming.com/gecco2004tutorial.pdf

You have input, you have output , the GA picks a program.

Also do you know LISP yet?  You should. Or Scheme.  The source esentially is the abstract syntax tree, so a lot of the representation problems disappear.

I think my brain just had an orgasm.

Thanks!

You see...the optimization algorithm that is my thesis bitch slaps GA soundly.  If GA can be applied to algorithm searching, then I should be able to plug in mine quite nicely.

Too sweet.

Thanks again.

Your algorithm http://www.chem.purdue.edu/kais/ref36.pdf
seems to involve searching the output space of a function for a minimum. 

I'm not sure how to apply it to building an algorithm.

How would you proceed?

The GA has to use some sort of fitness function, ranking algorithms according to some criteria.  Input, output, fitness.

There's no fundamental difference in that aspect.  The tricky part is in variance points and how a Tsallis distribution applies to it.

What are variance points and why do you need this Tsallis distribution?

Sorry, by variance points I mean ways/places to change an algorithm.  The Tsallis distribution is mentioned in the later papers, it's much more efficient than simple exponential cooling or Gaussians.  Narrower spike but longer tail.

In Koza's view any node in the AST can be a variance point.  Mutation point is his term. 

So you generate a bunch of random programs.  inputs, outputs, take the top 100 scoring programs.  Splice together bits at variance points, repeat.

What are we doing with the minima search?  Why is there a minima search (or a maxima search) in our algorithm search?


Does the universe of possible algorithm  form a function that is amenable to search? Are high fitness scoring programs "close" to each other? How is that distance scored? # of variance point changes required?

All of those are excellent questions that I would love to know the answers to, which was why I got excited over the genetic programming page - it appears they've figured all that out, and once I wrap my brain around how they did it, I should be able to use it, too.

Maybe not better, as they have a crapload of experience with it, but at least use it for my own nefarious ends.

I pulled variance point outta my butt, there.  Mutation point is just as good.

Yea, it's pretty neat stuff. I hope you get to relate your stuff to it in some way.

The minima/maxima search is the same as their fitness criteria.  No difference.  They weed out the bad and keep the good.

Thanks - I hope I can make it work, too.

Just not this week.

There's no need to search for the maxima.  Run all the programs on the inputs, get fitness scores. Sort.  You have a maxima. 

As far as I can tell, superficially, we don't have a function that we need to find a maxima in, we just have programs that run and return scores.

Except the search space is astronomical - you simply can't run them all.  So you vary around the best, while still sometimes try the bizarre variations, and repeat.

When it stabilizes, you pretty much have to call it quits.  It's a nondeterministic search.

You see, this is why the taking-a-remedial-CS-class algorithm optimizes neither the girl-going-out-with metric nor the learn-a-lot metric.

It probably doesn't maximize a combination either.

Yeah, but you have start somewhere.  Zero data points to begin with.