Programming Contest

[Sidoh]

Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.

Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.

Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).

Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.

[nslay]

Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.

Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.

I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).

Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.

Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.

Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.

[Sidoh]

Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.

Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.

I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).

Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.

Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.

Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.

A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.

I'm not implying that any of these are trivial; I'm suggesting that they're feasible.  Automated theorem proving is difficult, and I wouldn't expect anyone to do half as well as prolog, but it's still not impossibly challenging.

I don't think that's true.  If you're given a reasonable sampling of what the captchas look like, I don't think it takes much more than a bit of background in graphics and probably some knowledge in OCR to solve them.  Making a generalized solver would be difficult, but again, this is not what I'm suggesting.

[nslay]

Sudoku solvers are not difficult to write.  Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.

Soduku is an NP-complete problem.  The people who derive algorithms to efficiently solve them publish their results in papers.

Automated theorem proving isn't very difficult either.  It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.

I don't know what automated theorem proving entails, but it sure reminds me of computer algebra systems which are a product of symbolic computing.  This does not seem trivial.

Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics.  I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).

Captcha classifications requires background in computer vision and machine learning to even begin to approach the problem.

Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary.  I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.

Writing algorithms to solve soduku puzzles or classes of soduko puzzles efficiently is publishable material (which is worthy of a thesis). Captcha classification is not trivial either...a very accurate captcha classifier would be publishable material.

A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.

Well, I don't know or solve sodoku puzzles.  I only saw it mentioned in some journal so I misunderstood.

I'm not implying that any of these are trivial; I'm suggesting that they're feasible.  Automated theorem proving is difficult, and I wouldn't expect anyone to do half as well as prolog, but it's still not impossibly challenging.

I don't think that's true.  If you're given a reasonable sampling of what the captchas look like, I don't think it takes much more than a bit of background in graphics and probably some knowledge in OCR to solve them.  Making a generalized solver would be difficult, but again, this is not what I'm suggesting.

As with face detection, I imagine you would employ machine learning algorithms to classify captchas.  Train the algorithm on annotated captchas, then use the trained algorithm to classify unseen captchas.  If the captcha is simple, you might be able to do something else.

[Sidoh]

Yeah, on captchas, I don't expect we'd try anything more than really simple ones.

Actually, I'm very interested by machine learning.  I understand very little beyond the general concept, but I do plan to take a course in it before I graduate.  I'm taking the non-machine learning AI courses first.  They're not prerequisites, but they're offered before machine learning in the cycle.

Anyway!  Is anyone else interested?  I think it'd be ideal if we could get ~5+ people.

[Camel]

http://csis.pace.edu/~bergin/karel.html

Did some projects with this years ago in middle school - various mathematical operations.

[iago]

A few years ago I solved a moderate CAPTCHA with no fore knowledge. The easiest part was that it was numerical-only.

I used an AI type of solution by dividing the image into regions and checking what percentage of each region was black (that was after filtering out the noise). It got about 15% accuracy, which was pretty good.

[Chavo]

15%? That's barely better than randomly guessing a digit ;)

[Sidoh]

15%? That's barely better than randomly guessing a digit ;)

Not considering it was almost certainly more than one digit.  If he was randomly guessing, it'd be (.1)^n, yes?

[iago]

It was 5 digits, so we brought it from 1/10,000 to 1500/10,000. Just a bit better..

[Chavo]

I was joking, clown.

[MyndFyre]

A reasonable brute force algorithm (ie, one without bugs) solves a sudoku in O(1) time.  It's a fixed size grid (9x9).  It's not an interesting problem in an academic circle (save for an exercise).  Generalized sudoku (which is not sudoku) is nxn, which is NP-complete.  I'd hope it's obvious that this is not what I'm proposing.

I don't believe that the algorithm solves a 9x9 grid in O(1)....  Unless you're meaning to say that it will do it in at most constant time, with the 1 being ALL of the possible combinations of numbers on the board....

[Sidoh]

It's pretty clearly O(1).  Given any algorithm that solves a sudoku, you can do amortized analysis on it.  Since the size of the input is bounded, the worst you can do is based on how the algorithm approaches it.  If it's backtracking, you could probably end up doing something like 65^5, which is still O(1).

I wrote a backtracking solver a few months ago.  I did nothing in the way of heuristics (it's a CSP, so it'd be easy to implement most constrained variable / least constraining value), and it still solves 12-hint puzzles in less than 5 seconds.  I suspect implementing meaningful heuristics would down that to less than 1 second pretty easily.

[Sidoh]

I was joking, clown.

lol. 

Well, I'm probably going to try doing one of these things over the break to stay productive.  Blaze, you want to work on one as well?  If so, which one?

[zorm]

Why not spend your time doing the 30 day challenge or something like that?