ToDo

From Algorithmist

Jump to: navigation, search

1 Site-wide changes
2 Problem Help

[edit] Site-wide changes

[edit] Misc

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.

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)

[edit] other sites devoted to cataloging algorithms

A Meta-Request: A list has been started at http://www.listible.com/list/online-catalogues-of-algorithms (which this site has duly been added to) of sites devoted to cataloguing algorithms. It was started because there seems to be a dearth of good sites that cover the topic. I would like to know if there are any other high-quality, free resources out there that can be linked here and which could be added to the listible list as well. - Andrew Matthews 30 Mar 2006

The news group "algogeeks" http://groups.google.com/group/algogeeks also discusses computer programming algorithms.

[edit] Pseudocode

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)

[edit] Partial Writeups

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)