Comp Sci Algorithms

Could a moderator please move this thread to the General Programming forum? I think I might get more replies. Thank you.

I don't think this belongs in General Programming.

Here's a good practice site: acm.uva.es.

Also www.topcoder.com has some very good tutorials on Dynamic Programming.

Just out of interest, is your goal to go to the International Olympiad of Informatics?

the vallidolid problem set is very extensive, but most of the problem statements could use a little work.

topcoder is by far the best.

Quote:

Original post by Tron3k I don't think this belongs in General Programming. Here's a good practice site: acm.uva.es. Also www.topcoder.com has some very good tutorials on Dynamic Programming. Just out of interest, is your goal to go to the International Olympiad of Informatics?

Yes. I think I can do it too. I am a sophomore this year, so incase i don't make it, i have another chance, but i still want to go this year. I am in US, so USACO.

I don't know names of a lot of algorithms, though I can do some pretty awesome shit with pointer manipulation, etc. I want to learn these algorithms.

Yeah I was like you once. But let me tell you, algorithms are everything. Programming skill is good but not the primary thing. But basically, from my experience, you can probably get up to speed on algorithms pretty fast, like I did.

Did you do perform in IOI? If so, is it hard? As in, is it programming skill, or more of algorithm skill?

Quote:

Original post by Tron3k Yeah I was like you once. But let me tell you, algorithms are everything. Programming skill is good but not the primary thing. But basically, from my experience, you can probably get up to speed on algorithms pretty fast, like I did.

I got one week.

I like Bruce Reissi's book Data Structures and Algorithms. Unfortunately, it is not in pdf form, so I have hard time printing it. I will be away from computer for next couple days, so if someone could suggest a pdf book thing for this stuff, I would greatly appreciate it.

Just some random thoughts


disjoint sets with unions has been coming up a lot lately for some reason.

algebra, geometry, linear algebra, discrete math, and trig are always a plus, especially the geometry and discrete. Calculus is rare, very rare. Actually, good integration of linear algebra, discrete mathematics, and geometry have helped me solve tons of problems very quickly and efficiently.

dynamic programming is good when you need speed.

trees and tree traversals are very important, always some problem that uses them.

know the STL inside out, especially vector and map (oooh, map, how thou hast saved me). Know what all the useful purposes of a stack are (reversing lists, converting algebraic equations from infix to postfix notation (very, very handy)).

use typedefs, they save a lot of typing. For example, do you want to "type vector<string>::iterator iter = list.begin()" every time you need to loop through a list of strings (some times you have to do a lot of looping), are would you rather type "typedef vector<string>::iterator vsi" once and then "vsi iter = list.begin()" multiple times?

use c++ i/o. It's harder to screw up.

Try to avoid allocating memory explicitly. Just use scope levels to create and destroy variables/objects.

if you can't come up with a nice way to break out of many loops, it's okay to use a goto. Just as long as you promise to use "hell" as the label to which to jump.

try to right your code as neatly as possible. However, don't stick rigidily to a coding style, sometimes you just have to type really fast and get a quick fix in (hence why a goto is sometimes allowed).

yell really loud when you solve a problem, something like "SPOOON". It intimidates your opponents. Wear a hat like the one I'm wearing in my avatar pic, people will call you the coding cowboy. (this is to say, have fun).

Quote:

Original post by Sagar_Indurkhya Did you do perform in IOI? If so, is it hard? As in, is it programming skill, or more of algorithm skill?

I did go to the IOI. First of all, everybody there will be as good a programmer as you, and many will be better. And all of them will know all the standard algorithms, and some will know a whole lot more. It's very hard. [grin]

Not that I want to ruin your fun, but I don't see the point of those competitions. They encourage you to know algorithms by heart, and they work with a short time limit, encouraging people to hack their code to death.

What's actually needed in the real world is 80% of careful, planned programming, and perhaps 20% of virtuosity, but not the opposite. I haven't been programming for that long, and I've already done a good few things which I consider to be pretty awesome. Yet, I probably wouldn't do that good in any of those competitions. Why? Because I'm not a math freak, I don't know algorithms by heart (I look them up when I need them), and I don't like to hack code up. I program as fast as I want, and I don't like the idea of being time limited.

Whats your motivation, the prize?

I'll take a programming team member on my projects any day. I can teach a person how to write neat code quite easily. I can't teach them how to code from scratch with the same ease (I can do it, it just pisses me off).

Programming team is primarily fun, and mostly an exercise in mathematics and science, not programming. In fact, most of your "programming" will be in the I/O department, which you should have already had worked out with your team and memorized by now.

But of all the CS students at my school, the only ones that are really worth a damn are the programming team member (we actually have a fairly large programming team, with about 12-15 active members and a number of members that show up from time to time).

But atleast they know where a brace goes, or what an array is. I am so sick and tired of working on projects with students in 3rd and 4th year programming and software engineering classes and having to tell them "that is in no way consistent with the language syntax, in fact, a bald monkey can see that". (I'm not that blunt).

Of course the best site available for USACO practice is, well, from USACO (and it's quite good):

http://ace.delos.com/usacogate

The site gradually introduces you to new algorithms and provides (sometimes incomplete imo) descriptions/implementation details of each.

Yeah, basically the "Gold" medal motivates me. I did do a lot of stuff on the USACO website, but the problem is that I end up creating my own algorithms for such stuff. I guess tomorrow I will go through that Bruce Reisse guy's e-book, and print it out.

Max_Payne: I agree with you. Problem is, I got to prove that I am not a dumb ass using basic or something. It look's really good on transcript for high school. Also, I am no math genius, so I don't win all those big shot competitions, but this is one thing I know I can do good on.

So Tron_3K, any good algorithms to memorize or learn about?