From Algorithmist
Jump to navigation Jump to search

Site-wide changes[edit]

Site cleanup[edit]

Site seems to be last updated only in 2007. Make sure that the site is free of broken links.


Larry needs to update the index to match the new UVa archive.. Larry 10:30, 19 October 2007 (EDT)

Obviously fill in more of the problems.

Larry needs to finish up Convex Hull and Sorting. - Larry 10:51, 3 Jan 2005 (EST)

Fill Breadth-First Search, Dijkstra's Algorithm and Floyd-Warshall's Algorithm.

Someone requested information about Segmented Trees.

I'd like contributions and someone who has english as native language to correct my text or express better some ideas on Ad Hoc and Simulation categories definitions - Jemerson 28 Dec 2005

The Diff algorithm is an elegant algorithm that has a huge range of applications - it would be of general value to the community. Huffman Encoding and Decision Tries find implementations in many areas as well. I understand that these are based around constructing data structures, but they have a significant broadly valuable algorithmic compnent that renders them of interest. - Andrew Matthews 30 Mar 2006

Diff uses the Longest Common Subsequence algorithm. We also have a little information on using diff in useful shell commands. Data structures are part of what the Algorithmist covers, too. See Linked List, Stack, Hash Table, and so on. Welcome to the wiki! :) Sartak 19:58, 29 Mar 2006 (EST)

And I would like someone to write different ways to write Dynamic Programming and its general way to identify the recurrence and the state space apart from normal tasks and also the usage of bit masking in DP.

I don't think there's a magic technique - you just need to able to convert a problem into a structure which solves a subproblem - with benefits if they overlap. As for using bitmasks, it's mostly used for the 0-1 type DP problems, where in that case, it's the same as using an array of bools, just represented differently..

Larry 14:04, 11 Apr 2007 (EDT)

Other sites devoted to cataloging algorithms[edit]

This section has been moved to Links


We should adopt a uniform set of pseudocode conventions. As it stands right now, just about every article uses its own slightly different flavor of pseudocode. Sartak 16:30, 8 Feb 2006 (EST)

It's true, I agree with you. Larry 01:38, 9 Feb 2006 (EST)

I agree even more! But is consensus possible? For example, I'm personally opposed to using the "var n As Integer" syntax -- I think "is" would be a better word than "As", and "As" makes no sense, except to VB coders who are simply used to it. But I guess some people think the "as" syntax is good. Minor example, I know... Other minor examples -- should the code blocks be enclosed in pre tags, or should we just use spaces before each line? The former makes it more clear that it is a code block, but the latter allows more markup within the code, and that's probably why Wikipedia uses it... At any rate, some common things can be agreed on -- for loops should say for i from 1 to n and not for(i=0;i<n;i++), etc. --Aboyner 03:23, 9 Feb 2006 (EST)
Who said anything about a consensus? :) Have Larry (I assume he runs this wiki) come up with some conventions. If people don't like them, they can suggest new ones. If people don't want to follow the conventions, they'll suffer the wrath of those who update their articles. I'm a libertarian, but I don't always act it. ;) Sartak 03:26, 9 Feb 2006 (EST)
Traditionally-speaking pseudo-code shouldn't have any as integer, is integer, etc... nonsense in it at all. The context should be enough to determine what the variable is. Personally I prefer Python-esque pseudo-code (Python is afterall executable pseudo-code). This means proper indentation is a pre-requisite, there are no {} characters marking scope, and all variables are untyped and are declared on-the-fly where they're needed. Context should be enough to tell the user what the variable is.
If someone writes x=True it's quite obvious that x is a boolean variable. Likewise n=1 n is a numerical variable. The differences between floats, doubles, integers, etc... don't matter when it comes to pseudo-code. It's a number, and based on context you can determine anything else you might need to know about it. For example: if you're indexing an array or list, clearly you're not going to be using a float. If you're doing mathematical calculations on averages one can assume you're using floats. If for some reason you need to be explicitely clear you can use pseudo-code functions like int() and float() to make sure the reader knows exactly what you're doing.
As for loop syntax the c/++ version is hopeless as far as pseudo-code goes. I support either for i=(start) to (end), or for i in (mathematical range). By mathematical range I mean syntax like: [0,k], (1,3], (-10,10), or [0,array.length), where a square bracket indicates inclusivity, and a rounded parenthesis indicates exclusivity. It's a standard mathematical notation, and as such should generally be accepted and/or understood.
Furthermore, whenever possible, using a for each loop would be just as good. If you're looping through an array why bother defining an extra pseudo-code variable? For each node (V,E) in graph G... is quite clear, as opposed to for i=0 to k-1: node=G[i]...., which is needlessly verbose.
Generally for pseudo-code as long as the code is actually pseudo-code, and not a copy-and-paste of your latest C project we should be fine. Make sure you've simplified the operations, streamlined the code, eliminated unnecessary variables, and indent properly. Throwing in a comment here and there wouldn't hurt either if you feel it's necessary. (Comments of course should start with # or //.)
--ve4cib 13:41, 7 Dec 2006 (EST)

Partial Writeups[edit]

How does editing work here? I would like to write the Exhaustive_Search page for example. That would probably take me about two weeks. Can I post a "working" sign and start editing it? --Rgrig

Yeah, posting partial writeups and rough drafts is very welcome. Once you have a piece of crap on the web with your name on it, you have lots of incentive to polish it ;). Also, you might get useful feedback. --Rrenaud 17:25, 6 Mar 2006 (EST)

Problem Help[edit]

Previous: UVa_10591, UVa_10139

Hi can i request for the explanation of the Apriori Algorithm? Thankx! =)

Here, let me google that for you:


What is "The AVT simulation algorithm" ? There's a brief mention in a paper I'm reading about asynchronous processors ... but Google doesn't seem to give much detail. --DavidCary 04:38, 24 May 2009 (UTC)

Heuristic instead of Greedy[edit]

I took the liberty of changing the table of contents to place greedy under heuristics could you propagate the change to the main page?--Graeme E. Smith 07:28, 1 September 2009 (UTC)

What do you prefer to go there? It's setup as it would be in a textbook, as greedy is one of the first things to learn.. Larry 15:29, 1 September 2009 (UTC)

code tags[edit]

The <code> tags seem to be rendering incorrectly for some reason. In some cases, it works, but in others, it leaves the second tag unclosed and breaks the rendering of the page itself. --Sigma 7 13:54, 1 April 2010 (UTC)

Any particular links? It might be that it now expects the lang attribute, after the syntax highlighting plugin. Larry 14:07, 1 April 2010 (UTC)
Turns out there wasn't haskell support for some reason. I'm not sure it's correct right now, but I did hack it in. Let me know if you see anything out of the ordinary. Larry 14:15, 1 April 2010 (UTC)

I think it has to do with the default lang attribute. For example: <code lang="c++"> int main() { printf("Hello World\n"); return 0; } </syntaxhighlight> results in:

int main() 
  printf("Hello World\n"); 
  return 0; 

I think it might be better to grab - instead of acting wierd on an incorrect/invalid lang attribute, it will bring up a bright red box telling users that they need to use "cpp" or some other recognized language. The current one doesn't do this, and instead causes the strange behaviour. (It also won't strip out the <pre> tags, causing a weird layout.) --Sigma 7 23:40, 1 April 2010 (UTC)

Finding Algorithms[edit]

I'm working on a particular problem within string parsing.

"There should be some directory that I could find or place this problem in, to learn more about approaches people take with it, and to share what I find as I research."

Problem: Mapping from a practical problem to a solution through "CS" language[edit]

Most of the categorization on this site is based in a "Computer Science" perspective -- within this CS perspective, algorithms are categorized and named in a particular way.

But I come from an "I'm just a coder, coding this thing" perspective.

That is, the road from "I'm programming and wondering how to code this particular thing," and "Here's what you're looking for," requires a detour through this complex computer science land that I don't understand or have time to figure out.

Example: String Grouping[edit]

The particulars of my problem: I'd like a very simple algorithm that reveals nesting structures. For example, if I have a string "here (are some) elements (of a string)", I want to get back ["here", "(are some)", "elements", "(of a string)"].

Now, how do I find an algorithm for this kind of thing?

Someone with domain knowledge says, "Well, obviously, this is a context-free" (or whatever) "grammar, so you just need to choose an LL parser" (or whatever) "problem solved, no big deal."

OK -- but I'm not a Computer Science parsing expert. LL parsers and all that Chomsky hierarchy stuff is pretty complicated, and most tutorials start in such an abstract space, that I have to dedicate months to decomposing it all, sorting it out in my head, in order to get what I'm looking for, and then I forget it all 2 months later anyways. How expensive!

Whereas -- I can brute-force a solution pretty easily. Won't be very elegant, and it'll bleed a lot of resources unnecessarily, but after 2-4 hours of coding and testing, it should do 95% of what I need, and the waste should be something that I can cope with.

But I'd like the nice algorithm.

Question: How to categorize lay problems?[edit]

So my open question is: "How can we categorize situations that can make use of algorithms?" How can we categorize the problems? And for example, how can I categorize my problem?

An example, imagined:


   Formal Grammars
   Ad Hoc
     Grouping  <- my problem is here, or around here