Search found 16 matches

by Horsman
Wed Sep 03, 2008 11:10 am UTC
Forum: Computer Science
Topic: Majoring in Comp Sci: Do I have a shot at this?
Replies: 42
Views: 8682

Re: Majoring in Comp Sci: Do I have a shot at this?

I didn't write a line of code until my first CS class. I'm now in my final semester at Dalhousie and have done two NSERC research awards, two Research assistant jobs, and have a two year GPA of 4.0 and 4 year GPA of 3.6. Among the top say 5 students to go through my school with me, only 1 of them pr...
by Horsman
Sun Mar 30, 2008 2:55 am UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

I too am currently working on the TSP, your algorithm is actually quite similar to "Simulated Annealing" which is the method I am using. The main difference is that in simulated annealing if the new distance is longer than the old distance then it does not necessary switch back, their is ...
by Horsman
Thu Mar 27, 2008 11:31 pm UTC
Forum: Computer Science
Topic: AI and checkers
Replies: 18
Views: 6338

Re: AI and checkers

The solved checkers was done by genetic optimization if I'm not mistaken, so the chances of a brute force beating it are slim to none.
by Horsman
Thu Mar 27, 2008 11:14 pm UTC
Forum: Computer Science
Topic: On relations between context-free languages
Replies: 3
Views: 2324

Re: On relations between context-free languages

Basically you want to translate both into Pushdown automata and then try subgraph-isomorphism algorithms. There should be some moderately good solutions floating around to solve for reasonable sizes. Edit: Ullman's algorithm seams to be the goto guy http://portal.acm.org/citation.cfm?doid=321921.321...
by Horsman
Thu Mar 27, 2008 11:07 pm UTC
Forum: Computer Science
Topic: Ternary C extensions
Replies: 20
Views: 4051

Re: Ternary C extensions

Cool, I ran into your emulator on freshmeat earlier today. Good luck.
by Horsman
Tue Mar 25, 2008 1:21 pm UTC
Forum: Computer Science
Topic: AP CS AB: java Collections Framework.. what need I know?
Replies: 22
Views: 3069

Re: AP CS AB: java Collections Framework.. what need I know?

Actually this is a perfect example of something I'm pretty sure Java generics can't do. Generics can't take primitive types, so you would have to use the boxed types. But no superclass of the boxed types have an add function. Also right. I never really used generics much (Should use them more actua...
by Horsman
Sun Mar 23, 2008 3:34 pm UTC
Forum: Computer Science
Topic: Non-deterministic Turing machine
Replies: 13
Views: 4180

Re: Non-deterministic Turing machine

Really it does not matter at all why or why not a turing machine halts. What matters is that you give a problem input on a particular turing machine, and it either returns TRUE, FALSE, or continues churning. Thats all there is to it.
by Horsman
Sun Mar 23, 2008 3:24 pm UTC
Forum: Computer Science
Topic: College Majors and Courses
Replies: 32
Views: 4965

Re: College Majors and Courses

I'd like some help in deciding a college. I've been accepted by University of Washington in St. Louis and Texas A & M, and I'm waiting to hear back from Stanford, Yale, and Rice University. I'm pretty sure I am going to do something with computer science--but I'm more interested in abstract stu...
by Horsman
Sun Mar 23, 2008 3:15 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

jareds wrote:Whoosh. The joke is that it is in fact easy to factor large prime numbers, in constant-time even. That was a widely mocked quote with the same error.
I otherwise agree with you.


whoosh indeed. I'm having a good laugh now. Excuse the holier-than-thou please.
by Horsman
Sun Mar 23, 2008 3:15 am UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

As another sidenote (I think touched on elsewhere): If anyone were able to actually find a polynomial time algorithm, and release it widely to the world, there would be a scrambling period where all encryption schemes fall apart. Most modern encryption (RSA and others) is based on the assumption th...
by Horsman
Sat Mar 22, 2008 5:48 pm UTC
Forum: Computer Science
Topic: Resources for learning the Math and Science behind computing
Replies: 45
Views: 98890

Re: Resources for learning the Math and Science behind computing

Different Things you'd probably want to look for: Data Structures (About how to represent data in programs, in good and efficient ways) Algorithms (how to efficiently compute results for problems and design problem solutions) Discrete Math (Formal proofs, number theory, probability, combinatorics, g...
by Horsman
Sat Mar 22, 2008 5:48 am UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

As another sidenote (I think touched on elsewhere): If anyone were able to actually find a polynomial time algorithm, and release it widely to the world, there would be a scrambling period where all encryption schemes fall apart. Most modern encryption (RSA and others) is based on the assumption th...
by Horsman
Fri Mar 21, 2008 7:02 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

quintopia wrote:A local beam search is always superior to a genetic algorithm.


I'm interested to look this up (Does beam search outperform ILP?). Thanks!

Edit: looks like another pruning technique.
by Horsman
Fri Mar 21, 2008 6:31 pm UTC
Forum: Computer Science
Topic: similarity between documents
Replies: 7
Views: 2225

Re: similarity between documents

Basically you want to represent each document as a bag (multiset) of words (the words, unordered). Then use normal bag comparison techniques. You can also cull non-important words (for instance, everything but nouns and verbs). Keep a linked copy of the full text, and you can also have each word in ...
by Horsman
Fri Mar 21, 2008 6:19 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

As for the best cutting plane ILP methods: ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formu...
by Horsman
Fri Mar 21, 2008 5:57 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 0399: "Travelling Salesman Problem"
Replies: 115
Views: 28712

Re: "Travelling Salesman Problem" Discussion

As for the best cutting plane ILP methods: ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formul...

Go to advanced search