This is the talk page for discussing improvements to the WikiProject Computer science page.
Put new text under old text. Click here to start a new topic. Please sign and date your posts by typing four tildes (~~~~). New to Wikipedia? Welcome! Ask questions, get answers.	Be polite Assume good faith Avoid personal attacks Be welcoming
Archives: 1, 2, 3, 4, 5, 6, 7, 8

WikiProject Computer science	(Rated Project-Class)	Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
Computer science portal v • d • e This page is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.  Project  This page does not require a rating on the project's quality scale. Things you can help WikiProject Computer science with: edit · history · watch · purge Get pictures for these bios: Robert Tomasulo (note - he died in April 2008 - contacting him is now a non-option) Living Turing award winners whose biographies lack pictures: Robert Tarjan - Andrew Yao - Richard Stearns (computer scientist) - Raj Reddy - Michael O. Rabin - Butler Lampson - Robin Milner - William Kahan - Edward Feigenbaum - Leonard Adleman - Manuel Blum - Charles Bachman - Edmund M. Clarke Living Eckert–Mauchly Award whose biographies lack pictures: Robert S. Barton - Ken Batcher - David Kuck - Yale Patt - Josh Fisher - James H. Pomerene Extend Artificial life possibly merging the list pages that are included, and using the History of artificial life as context for what should be fleshed out from the various lists. It would be nice to have a paragraph for each list word saying how and why it is part of Artificial life.

edit · history · watch · refresh  To-do list for Wikipedia:WikiProject Computer science:

Get pictures for these bios: Robert Tomasulo (note - he died in April 2008 - contacting him is now a non-option) Living Turing award winners whose biographies lack pictures: Robert Tarjan - Andrew Yao - Richard Stearns (computer scientist) - Raj Reddy - Michael O. Rabin - Butler Lampson - Robin Milner - William Kahan - Edward Feigenbaum - Leonard Adleman - Manuel Blum - Charles Bachman - Edmund M. Clarke Living Eckert–Mauchly Award whose biographies lack pictures: Robert S. Barton - Ken Batcher - David Kuck - Yale Patt - Josh Fisher - James H. Pomerene Extend Artificial life possibly merging the list pages that are included, and using the History of artificial life as context for what should be fleshed out from the various lists. It would be nice to have a paragraph for each list word saying how and why it is part of Artificial life.

Archives
Archive 1 (to 16 December 2005) Archive 2 (to 11 June 2006) Archive 3 (to 26 October 2006) Archive 4 (to 10 March 2007) Archive 5 (to 22 June 2007) Archive 6 (to 28 October 2007) Archive 7 (to 6 May 2008) Archive 8 (to 17 April 2009)

Contents 1 Feige's inequality on the sum of independent random variables 2 Breadth-first search implementation at AfD 3 Participate in discussion 4 GA Sweeps invitation 5 Kernighan-Lin algorithm 6 First-order logic 7 Consensus Please 8 Use of 'source lang="foo"' (Syntax highlighting) 9 Sys-Con 10 Class names in bold 11 The Compiler article 12 Lambda calculus 13 Near Root Algorithm 14 Reorganize the Computability articles 15 Category:Data types and Category:Type theory - crossref from WPMATH 16 Template categories 16.1 Asking permission to create stubs 17 A lot of articles are wrongly categorized in Category:Formal methods 18 AfD input sought 19 Category:Computer language stubs nominated for deletion 20 Computational complexity and analysis of algorithms and program optimization vs. algorithmic efficiency 20.1 Concrete complexity 21 In depth discussion whether programming language =?= computer language 22 Symbolic analysis for deletion 23 Use of primary sources in the history section of Math/TCS articles 24 Some shades of WP:OR at Algorithm#Classification 25 Church-Turing thesis as "unsolved problem" 26 Boolean algebra (dab) 27 Transaction mechanism 28 Java WikiProject 29 Popular pages 30 Leadership? 31 Many overlapping analysis of algorithms articles 32 Can someone take a look at this? 33 dANN and Johnson's algorithm 34 CfD nomination of Category:Probabilistic_complexity_classes 35 Pageview stats 36 Request for article: Frame 37 Merging "X problem" to "X" 37.1 X Problem versus Computing X or Algorithms for X 37.2 Status 38 List of computer science conferences 39 Time complexity 40 Theory of Computing (journal)

[edit] Feige's inequality on the sum of independent random variables

Hi, I would like to write a small article on Feige's inequality but have a few concerns. It will be a more educational extension of my Open Problem Garden entry. The inequality simply says that for non-negative independent random variables with expectation bounded by μ, and it has furthermore been conjectured that 1/13=0.0769... may be replaced with 1/e = 0.367... In comparison to other known probabilistic inequalities (e.g. Markov's inequality), the above RHS does not go to 0 as n goes to infinity. The original paper can be found at http://portal.acm.org/citation.cfm?id=1007352.1007443 .

1. Is the theorem and conjecture notable? The author is a well-respected researcher in complexity theory and the original article was presented at STOC 2004. The inequality is however not well-used. Google Schoolar reports 17 citations: http://scholar.google.com/scholar?cites=11347979119245205986 . Out of these, one probability theory paper improves the inequality (showing 1/8 instead of 1/13 when δ=1, implying a general bound of 1/8 instead of 1/13). However, the entire paper is not devoted to this derivation. Two mention the inequality, proves a special case, and also reflect on a generalization of the inequality. Three extend the work but do not apply the inequality themselves. Three papers reference the work in passing. One cites but does not mention. Seven do not in fact cite the paper. Two references were duplicates. Only 50% +-25% of the papers were devoted to complexity theory.

2. How should the Wikipedia article be named? Feige simply calls it "an inequality on the sum of (nonnegative) (independent) random variables with unbounded variance". Other works do not refer to the inequality with any particular name (preferring references such as "the following inequality" or "Feige showed that"). May I simply call it Feige's inequality? If someone were to solve the conjecture or make significant work on it, one could rename the article appropriately.

—C. lorenz (talk) 21:32, 30 April 2009 (UTC)

[edit] Breadth-first search implementation at AfD

See Wikipedia:Articles for deletion/Breadth-first search implementation. As usual for AfD discussions, please leave a detailed comment explaining your opinion rather than just a keep or delete without an explanation. —David Eppstein (talk) 21:59, 12 May 2009 (UTC)

[edit] Participate in discussion

I'd like to have some more input on the discussion here. The subject is the proposed deletion of a second set of user templates connected with JavaScript. Thank you. Debresser (talk) 18:28, 19 May 2009 (UTC)

[edit] GA Sweeps invitation

This message is being sent to WikiProjects with GAs under their scope. Since August 2007, WikiProject Good Articles has been participating in GA sweeps. The process helps to ensure that articles that have passed a nomination before that date meet the GA criteria. After nearly two years, the running total has just passed the 50% mark. In order to expediate the reviewing, several changes have been made to the process. A new worklist has been created, detailing which articles are left to review. Instead of reviewing by topic, editors can consider picking and choosing whichever articles they are interested in.

We are always looking for new members to assist with reviewing the remaining articles, and since this project has GAs under its scope, it would be beneficial if any of its members could review a few articles (perhaps your project's articles). Your project's members are likely to be more knowledgeable about your topic GAs then an outside reviewer. As a result, reviewing your project's articles would improve the quality of the review in ensuring that the article meets your project's concerns on sourcing, content, and guidelines. However, members can also review any other article in the worklist to ensure it meets the GA criteria.

If any members are interested, please visit the GA sweeps page for further details and instructions in initiating a review. If you'd like to join the process, please add your name to the running total page. In addition, for every member that reviews 100 articles from the worklist or has a significant impact on the process, s/he will get an award when they reach that threshold. With ~1,300 articles left to review, we would appreciate any editors that could contribute in helping to uphold the quality of GAs. If you have any questions about the process, reviewing, or need help with a particular article, please contact me or OhanaUnited and we'll be happy to help. --Happy editing! Nehrams2020 (talk • contrib) 06:13, 20 May 2009 (UTC)

[edit] Kernighan-Lin algorithm

Kernighan-Lin redirects to Lin-Kernighan, which discusses the TSP algorithm. But in my textbook and lecture "Kernighan-Lin algorithm" means the graph partitioning algorithm, not the TSP algorithm. Which algorithm does it usually mean? Should the article Kernighan-Lin be changed to discuss the partitioning algorithm instead? Offliner (talk) 10:37, 9 June 2009 (UTC)

It's been many years since I was voted an honorary physics and math major (BTW, project page is on my watchlist, so Offliner, I'm not following your edits). AFAIK, it should be a "see also." The Kernighan-Lin algorithm is a heuristic, while TSP (traveling salesman problem) and GPP (graph partitioning problem) are targets for application of the heuristic. Neither TSP or GPP should be named for Kernighan-Lin/Lin-Kernighan or the other way around, that is, separate articles for:

• GPP
• Kernighan-Lin
• TSP

I haven't checked the articles, but somewhere in TSP there should also be discussion of TSSP (Traveling Salesman Subset-tour Problem).

   I believe K-L is currently more associated with TSP, but in any event I think it's better to keep the algorithm and "P"roblems separate. The "P"roblem articles should not be about the heuristic to solve them. Hope this helps. PetersV       TALK 14:23, 9 June 2009 (UTC)

Afterthought, there's GCP (Graph Color Problem) as well. PetersV       TALK 15:01, 9 June 2009 (UTC)

Are you saying that both the KL algorithm for TSP and the KL algorithm for GPP use the exact same heuristic? It doesn't seem that way to me. In all the books I've seen so far Kernighan-Lin algorithm means the GPP algorithm. Thus I don't think it's correct that Kernighan-Lin redirects to an article about the TSP heuristic. I think we should:

1. rename Lin-Kernighan to Kernighan-Lin heuristic for traveling salesman problem
2. create Kernighan-Lin algorithm which will contain info about the GPP algorithm
3. add a short description of that algorithm to Graph partitioning problem also
4. make Kernighan-Lin a disambig page with links to Kernighan-Lin heuristic for traveling salesman problem and Kernighan-Lin algorithm

If someone insist, we can also name Kernighan-Lin algorithm => Kernighan-Lin algorithm for graph partitioning instead for clarity. Offliner (talk) 08:28, 10 June 2009 (UTC)

I think Kernighan-Lin algorithm for graph partitioning is appropriate and we can have Kernighan-Lin algorithm with a Redirect. Point 1-4 are perfect. --Sayed Mohammad Faiz Haider Rizvi (talk) 10:34, 10 June 2009 (UTC)

I looked up some papers on Google and it seems the heuristic algorithm for TSP is usually called the Lin-Kernigahn heuristic/algorithm, while the one for GPP is usually called Kernighan-Lin heuristic/algorithm (note the order of the names.) Perharps put them at Lin–Kernighan heuristic and Kernighan–Lin algorithm and put a note at the top of both articles. —Ruud 16:13, 10 June 2009 (UTC)

The respective papers are:

• BW Kernighan, S Lin (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal.
• S Lin, BW Kernighan (1973). "An effective heuristic algorithm for the traveling-salesman problem". Operations Research.

—Ruud 16:21, 10 June 2009 (UTC)

Application of the K-L algorithm outside of its original space is where some boundaries appear to cross, doing a survey of papers. Ruud's suggestion here is the best and simplest solution. Other applications of the algorithm can be mentioned (briefly) as appropriate. PetersV       TALK 16:46, 10 June 2009 (UTC)

I've renamed the articles. Kernighan–Lin algorithm could use a bit more content. —Ruud 23:13, 10 June 2009 (UTC)

I've expanded the article with a description and pseudocode. Others are invited to check the additions for errors and other issues. Offliner (talk) 13:47, 12 June 2009 (UTC)

[edit] First-order logic

I have recently been working, with some other editors, to improve the article first-order logic. As this is an area of overlapping interest between mathematics and computer science, editors here may want to look through the article and improve any shortcomings from a CS perspective. Any feedback on this relatively long article would be appreciated, but the section on automated theorem proving may be of particular interest. — Carl (CBM · talk) 22:01, 15 June 2009 (UTC)

[edit] Consensus Please

Excessive cross-posting. Spammed to 11 WikiProjects. [1] Hans Adler 14:32, 24 June 2009 (UTC)
The following is an archived debate. Please do not modify it.
In the article Physics of the Impossible a single editor removed material that I believe, very much enhanced this article. The other editor’s view is that the removed material was off topic. My view is that it is very much on topic. The current article is here: (current) The version which I restored is at my sub page here: (restored) Everything that was removed is related to the book. This is because, as the author writes: “The material in this book ranges over many fields and disciplines, as well as the work of many outstanding scientists.” There is a two and one half page list of the individuals, “who have graciously given their time for lengthy interviews, consultations, and interesting, stimulating conversations.” Most on this list happen to be scientists. I listed only the first 22 individuals and these are scientists. In addition, I linked their names to their biography on Wikipedia. I also listed each scientist’s fields of specialties. Many on the list in the article have more than one field of specialty (view here), and hence this reflects the breadth of knowledge contained in this book. If you look at this section in the restored article you will see what I mean. In addition, before this material was removed by the one editor, the article was much more interactive. It was also more in line with the intent of Wikipedia that that the readers (as well as the editors) have a satisfying experience with Wikipedia. One aspect of this more satisfying experience is being able to access the knowledge that is available at Wikipedia on the sciences, and, perhaps, the mathematics. So, I linked not only the names on the list, but also many of their scientific disciplines to the respective Wikipedia article. Accessing this knowledge supports the following WikiProjects and their respective portals: (there are more I am sure) WikiProject Astronomy WikiProject Books WikiProject Physics WikiProject Space WikiProject History of Science WikiProject Science WikiProject Mathematics WikiProject Technology WikiProject Computing WikiProject Computer Science WikiProject Engineering Also, there were graphics that were removed which support the article and the concepts in the book. I believe these should be restored as well. These are on the restored article page, at my sub page. The captions of the graphics show that the book is grounded in real science. If you scroll through the restored article you will see the variety of graphics. I believe these enhance the article aesthetically, as well as help to give a clearer picture of the concepts contained in the book and the article. Lastly, there were external links that were removed which reflect the concepts in the book. These external links were removed as though they were not relevant. For example, I will list some of the external links, and then the page number in the book, to which each link is related: Solar sails: pp. 152, 158 - 159, 166, 172… Space elevators: pp. 165 – 169 Black holes: 156, 232, 235 – 236… Travel at the speed of light: 159 – 161, 163 – 165, 169 – 170… Unfortunately the external links that were removed are going to have to be restored one at a time, because they cannot be cut and pasted back from the revision history without some distortion. I think these external links should also, be restored to the article. I think the bottom line is, let common sense decide. Even Wikipedia guidelines say that they are just guidelines, not letter of the law. I would appreciate a consensus on whether or not to keep the removed material. Please place your comments here: Consensus please. This is on the talk page of Physics of the Impossible. Thanks for your time Ti-30X (talk) 13:22, 24 June 2009 (UTC)

[edit] Use of 'source lang="foo"' (Syntax highlighting)

I'm against it unless it's defined in the language spec or until it's controllable via preferences. Is there a policy on this anywhere? If not, is this the right place to discuss it. Thanks! - Richfife (talk) 15:31, 3 July 2009 (UTC)

And I'm stongly against it until someone fixes the ridiculous colour scheme. :) Scheme (programming language) has plenty of examples of hard-to-read yellow-on-gray text. Haskell (programming language), on the other hand, highlights all strings with a strong green background, as if those were the most important part of the whole article. — Miym (talk) 16:05, 3 July 2009 (UTC)

You should be able to customize or disable the colouring in your personal style sheet. It could probably also be done using a "gadget" in the user preferences. I agree the default colour scheme (MediaWiki:Geshi.css) should be more readable and consistent. —Ruud 19:14, 3 July 2009 (UTC)

[edit] Sys-Con

The reliability of Sys-Con as a source is being discussed at Wikipedia:Reliable sources/Noticeboard#Sys-Con. -- Collectonian (talk · contribs) 04:48, 28 July 2009 (UTC)

[edit] Class names in bold

I noticed that many of the complexity class related pages have classes in bold. So it's PSPACE, instead of PSPACE, NP instead of NP, and so on. But then some pages don't have it this way. Should we write all complexity classes in bold wherever they appear? (Is there some policy regarding this?) --Robin (talk) 13:58, 29 July 2009 (UTC)

MOS:BOLD doesn't say anything about it, but I personally feel that having both uppercase and boldface is a bit much. —LOL ^T/_C 14:12, 29 July 2009 (UTC)

Actually, my personal opinion is that plain uppercase looks like shouting and bold uppercase looks acceptable, strangely enough. The latter also appears to be the convention used by modern authors. (Of course, the fact that they are uppercase in the first place is unfortunate, but there's nothing we can do about it.) Shreevatsa (talk) 15:09, 29 July 2009 (UTC)

I'm not sure what I prefer, but in Arora and Barak's book that you linked to, they also use capital boldface for names of problems, like SAT and Subset Sum. --Robin (talk) 19:35, 29 July 2009 (UTC)

No, for problems or languages they use capital sans-serif (non-bold): 3SAT, SUBSETSUM (except occasionally bold in text where they're actually using bold for emphasis). It's probably hard to tell on Wikipedia as the default font is sans-serif, but compare 3SAT, SUBSETSUM and 3SAT, SUBSETSUM. This means that we can't directly follow all their conventions, incidentally. Shreevatsa (talk) 20:09, 29 July 2009 (UTC)

I would prefer as little typographical mumbo-jumbo as possible. “Satisfiability” and “NP” are perfectly fine words, TCS neither needs nor deserves special considerations different from other encyclopaedic terms. NP should behave like USA, and Satisfiability like Entscheidungsproblem. (Also remember that we have very little control over Wikipedia’s appearance on various media and platform anyway.) Thore Husfeldt (talk) 07:23, 30 July 2009 (UTC)

If we decide to use NP instead of NP, there are tons of complexity articles which will have to be edited to reflect this. --Robin (talk) 14:28, 11 August 2009 (UTC)

[edit] The Compiler article

Hello! The Compiler article has an "expert" tag on it, and is Top-importance but only Start-Class. The article looks pretty factual to me, so I removed the old "disputed" tag, but I'd appreciate it if one of the self-declared Compiler Experts around here could do a quick look-over for serious problems. I think the expert tag could probably be removed, but I don't think of myself as an expert, y'know? Anyway, right, important stuff! Let's not ignore it! :) Indeterminate (talk) 09:02, 30 July 2009 (UTC)

[edit] Lambda calculus

Can someone with (at least) a graduate-level understanding of the topic take a look at the article, in particular the confusion with various typed lambda calculi; see the article's talk page for details. Pcap ping 17:31, 5 August 2009 (UTC)

[edit] Near Root Algorithm

Would someone experienced in determining how marginally notable a topic needs to be to justify an article, please have a look at Near Root Algorithm. Johnuniq (talk) 01:55, 11 August 2009 (UTC)

It seems to be exactly the Babylonian method, explained badly and without error analysis. --Robin (talk) 14:26, 11 August 2009 (UTC)

[edit] Reorganize the Computability articles

(Note: This is a cross-post from wikiproject math. The discussion has now moved to Talk:Recursion theory#Reorganize the Computability articles to keep the discussion centralized.)

We have these "general" articles:

• Computability, which incorrectly implies that computability in CS and Math are somehow disjoint. This should not be a dab or a stub!
• Computability theory (computer science), a poor quality article that focuses narrowly on automata and Turing machines (despite the name). Barely mentions lambda calculus in the history section and makes no mention of recursion theory or random access machine!!
• Model of computation, a sort of WP:DICTDEF

We also have much better articles on the important topics, recursion theory, lambda calculus, Turing machine, and random access machine; we also have a decent overview article on register machines in general.

The way I see it computability should be is a high-level intro to the often encountered equivalent models of computation: recursion theory, lambda calculus, Turing machine, and random access machine. This is along the along the outline of S. Barry Cooper's Computability Theory (see pp. 7-8), which despite being written by mathematician was quite satisfying for me as a computer scientist (despite the many misprints, and his insistence on calling RAMs URMs, but that's another matter).

Pcap ping 11:22, 13 August 2009 (UTC)

The discussion is now at Talk:Recursion theory#Reorganize the Computability article (edited note at top here) Dmcq (talk) 11:55, 14 August 2009 (UTC)

[edit] Category:Data types and Category:Type theory - crossref from WPMATH

How should Category:Data types and Category:Type theory be related to each other? See Wikipedia_talk:WikiProject_Mathematics#Category:Type_theory_and_Category:data_types

Further friction and little light now at Category Talk:Type theory. Are types in Computer Science and Mathematics different beasts? Pcap ping 10:46, 24 August 2009 (UTC)

[edit] Template categories

Just letting you know I've created: Category:Computer science templates, and Category:Computer science stub templates taking clue from Wikiproject Math. Please categorize suitable templates that you know about in those categories. Thanks, Pcap ping 04:57, 23 August 2009 (UTC)

There is a Category:Computing templates, which contains a lot of templates that rightly belong in CS templates. --Robin (talk) 13:54, 23 August 2009 (UTC)

They can be included in both. No need for a food fight. By the way, I've also created {{PL-stub}} which was sorely missing. The OOP-related stuff has so many articles that it probably should get its own stub type. Also, I've avoided tagging concurrency stubs with the PL tag. Those should probably get their own a well. Lotsa boring work. Pcap ping 14:05, 23 August 2009 (UTC)

All of those are navbox templates. Do not add them directly to Category:Computer science templates, but create Category:Computer science navbox templates if you feel like going over them. Pcap ping 14:09, 23 August 2009 (UTC)

See Category:Mathematics templates for further ideas on organizing this stuff. And, no they don't have navbox templates there, they despise them! Pcap ping 14:12, 23 August 2009 (UTC)

I thought the category was for navbox templates. It says "The pages listed in this category are meant to be navigational (navbox) templates."

About the stub template you created, aren't we supposed to first propose its creation at Wikipedia:WikiProject_Stub_sorting/Proposals? --Robin (talk) 14:54, 23 August 2009 (UTC)

See below for "asking permission". Yes, they have a few subdued "bottom of the page links templates"; compare to the gigantic ones found in most computer-related articles. The Wikipedia terminlogy in this area is also confusing, as "Navboxes" is somehow a supercategory of stub templates and all other. Perhaps calling them "see also navboxes" or "series navboxes" would be more explicit. That's why I think it's better to put them in a subcat, but I don't care much either way. Pcap ping 15:40, 23 August 2009 (UTC)

[edit] Asking permission to create stubs

I have a rather dim view of that wikiproject given the ridiculous procedural requirements listed there. They've never managed to get those requirements in the main guideline, so they're just sneaking them in through the back door by making you kowtow to them beforehand. What happens if articles in a stub category get expanded so that the number of stubs drops below their "magic" threshold for having a stub category; should the stub category be deleted and stubs up-categorized? That's just busy work to justify the existence of their project, which hasn't done much if anything for computer science articles as evidenced by the huge lump of topics in the main comp-sci stub category; not to mention that a lot of topics are listed as "computer-stubs" and what not. By the way, have you ever heard of computer languages as a topic of study? They had a silly {{compu-lang-stub}}, which I've redirected to {{PL-stub}}. Let them undo my work if they don't like it; I'm not going to ask permission. Some stub categories in the Math wikiproject plainly don't meet the requirements set out by the stubs wikiproject, but they're still around. The way I see it: if a wikiproject manages its own stub categories, "help" from the stubs project isn't needed. Pcap ping 15:29, 23 August 2009 (UTC)

See also Talk:Computer_language. Pcap ping 15:43, 23 August 2009 (UTC)

After giving it some further thought, I won't bother with stubs anymore. Basically, it's duplicated effort on top of categories. Stub "sorting" should all be done in software, i.e. with intersection of categories. That way you'd able to mark any article just with {{stub}}. No need for all the ridiculous infrastructure currently used on this wiki (have a look at the fr.wiki where there's only one stub type -- I don't know if they've activated DynamicPageList there or not). But then Wikipedia, unlike Google, is mainly based on grunt work (that rewards people with promotions in a bureaucracy) instead of good software, so I'm not holding my breath I'll see any changes. Pcap ping 17:28, 23 August 2009 (UTC)

I created a number of stub templates a few years ago (I'm pretty sure there was a {{compu-lang-stub}} back in those days.) Most of them got deleted by the stub sorting bureaucrats as the stub sorters wouldn't be able to properly differentiate between the various templates, or so I was told. This of course entirely ignored the fact that there were several people here at this project happy to properly sort the stubs. —Ruud 19:38, 24 August 2009 (UTC)

Logically every category should have a stub category associated with it. But it's not worth the hassle to create all those by hand; they should be database views, i.e. stub "sorting" should be done in software by intersecting the topic categories with a single stub category. The way things are done on Wikipedia, that's not very likely to happen. Luckily we don't need to obtain permission from WP:WikiProject Categories to create categories, but somebody is probably working to "fix" that... Pcap ping 07:33, 27 August 2009 (UTC)

[edit] A lot of articles are wrongly categorized in Category:Formal methods

See Category_talk:Formal_methods#A_lot_of_article_are_wrongly_categorized_in_this_cat. Pcap ping

Also, my rant here. Pcap ping 15:10, 23 August 2009 (UTC)

Yes, some of the people doing categorization have some trouble differentiating formal methods from formal systems. Just recategorize those articles as you come across them. At least it's not as annoying as anything remotely related to computing getting labeled as computer science. —Ruud 19:33, 24 August 2009 (UTC)

[edit] AfD input sought

Anyone's input on Wikipedia:Articles for deletion/Comparison of ABAP and Java would be appreciated. --Cybercobra (talk) 01:00, 26 August 2009 (UTC)

[edit] Category:Computer language stubs nominated for deletion

See Wikipedia:Categories_for_discussion/Log/2009_September_1#Category:Computer_language_stubs. Pcap ping 10:56, 1 September 2009 (UTC)

Discussion was moved to SfD. Consensus at SfD was to merge into Cat:Programming language topic stubs. You may tag with either {{prog-lang-stub}} or {{compu-lang-stub}} in the future. Thanks, A Stop at Willoughby (talk) 20:48, 13 December 2009 (UTC)

Also {{PL-stub}} was (rightfully) nominated for renaming at Wikipedia:Stub_types_for_deletion#.7B.7BPL-stub.7D.7D. Pcap ping 00:27, 2 September 2009 (UTC)

Consensus at SfD was to rename to {{prog-lang-stub}} and delete {{PL-stub}}. Please tag accordingly in the future. Thanks, A Stop at Willoughby (talk) 20:48, 13 December 2009 (UTC)

[edit] Computational complexity and analysis of algorithms and program optimization vs. algorithmic efficiency

I could not ignore that the last article above appears to be one giant, ad-hoc WP:CFORK of the other three, combining some issues. The terminology "algorithmic efficiency" is somewhat common in academia [2] (about 600 gbooks hits) but pales compared to "computational complexity" [3] (about 5000 gbook hits) or "analysis of algorithms (1200 hits) and about on par with "program optimization" [4]. Even then, "algorithmic efficiency" it's more of WP:DICTDEF that can refer to any number of things rather than a field of study. The citations given, as well as the frequent references to some concrete programming languages ("algorithmic efficiency" pretends to be about algorithms in the abstract), suggest that this article has mostly written by programmers with little regard for how academics consider these topics. Granted, it's going to be a monumental job merging the appropriate parts from algorithmic efficiency in computational complexity, analysis of algorithms and program optimization, depending on where a particular topic belongs. Do you guys think this should be done? Other ideas for dealing with this? Pcap ping 19:23, 1 September 2009 (UTC)

There seems to be very little content in algorithmic efficiency that would go in Computational complexity theory. The whole section on "Optimization techniques" can go in program optimization. After that, the rest can be merged with Analysis of Algos and Program Optimization, as needed. This step will take time, but might not be as bad as it looks. --Robin (talk) 03:50, 2 September 2009 (UTC)

I do not agree that program optimization and algorithmic efficiency are quite the same thing. Certainly, program optimization is a part of algorithmic efficiency but is generally focused more on optimizing existing programs rather than the more general algorithmic efficiency. Algorithmic efficiency considerations can, and in my opinion should, be taken into account at the design stage, not when data structures have been created and programs written. Algorithmic efficiency cannot be 'taught' in the conventional sense, since the algorithms themselves depend critically on human ingenuity (who knows when a better algorithm may emerge?) but rule of thumb guidlines of what makes algorithms more efficient/inneficient in practise can be provided to avoid pitfalls in real-world implementation. It is commonly believed that an optimizing compiler will 'optimize away' bad programming - it won't. It won't even optimize a poorly constructed SWITCH statement, let alone larger chunks of code or separately compiled procedures working in tandom. Similarly, Computational complexity theory and analysis of algorithms have little to do with real-world implementations addressing instead more theoretical aspects. All these separate articles have their proper place but merging them together is in my view inappropriate.

[edit] Concrete complexity

By the way, we do not seem to have an article on this, and we should. Any volunteers? Pcap ping 19:23, 1 September 2009 (UTC)

What is Concrete complexity? Can you link me to a paper? --Robin (talk) 03:44, 2 September 2009 (UTC)

A book would be a better idea, e.g. [5] [6]. See also what W. Gasarch thinks of this area. Pcap ping 16:10, 2 September 2009 (UTC)

[edit] In depth discussion whether programming language =?= computer language

At Talk:programming language. Since the article is rated Top importance for this project, I thought you should know... Pcap ping 00:25, 2 September 2009 (UTC)

[edit] Symbolic analysis for deletion

I've nominated this and Symbolic Program Analysis for deletion. Pcap ping 22:36, 4 September 2009 (UTC)

[edit] Use of primary sources in the history section of Math/TCS articles

This thread on uses of primary source in the history sections of Math articles (at WP:WPM, of course) may be of interest to participants here because a fair number of TCS articles are of central interests to both projects, and have such sections. Pcap ping 13:31, 5 September 2009 (UTC)

[edit] Some shades of WP:OR at Algorithm#Classification

Perhaps someone can find a good source for that? All books on algorithms I'm aware of do not bother with taxonomical issues at the level that some industrious Wikipedian(s) have... Pcap ping 15:25, 7 September 2009 (UTC)

[edit] Church-Turing thesis as "unsolved problem"

We have a box in that article that proclaims, rather idiosyncratically, that it is an unsolved problem. Of course, the actual (claimed) problem is to "formalize" it so it can be "proved". Even this appears to me to be an idiosyncratic view of a few authors, as most state that the thesis is not something that can be proved because in general one needs to "quantify" over all computational models (I can give citations if anybody doubts me). So, it's somewhat questionable to have it included in Unsolved problems in computer science as well, given that most authors do not believe it to be something of a provable nature. So, the box appearing in the CTT article reflects a minority POV in my view. Any other opinions? Pcap ping 23:04, 13 September 2009 (UTC)

I think the best approach would be to first re-write Unsolved problems in computer science so that we don't have Church-Turing thesis there; the box will be easy to remove after that. And in my opinion, it is clear that the problem of formalising Church-Turing thesis does not belong to a short list of the most important open problems in all computer science. Strong claims need strong evidence; if it was a major open problem, it would be mentioned in numerous textbooks, surveys, etc., and I don't see such references in the article. — Miym (talk) 23:35, 13 September 2009 (UTC)

By the way, people might be more eager to add things like "formalising Church-Turing thesis" to Unsolved problems in computer science if the list of unsolved problems looks too short, like it desperately needs some new entries. So adding real major open problems to the list might help. See Talk:Unsolved problems in computer science#Cleanup ideas for some discussion related to expanding the list. — Miym (talk) 23:45, 13 September 2009 (UTC)

[edit] Boolean algebra (dab)

See discussion at WP:WPMATH. Pcap ping 23:00, 17 September 2009 (UTC)

[edit] Transaction mechanism

I've just proposed deletion for the article Transaction mechanism. It's trying to describe something for economics which is non-standard and doesn't have a reliable source. However, while I was searching to verify that it's not something notable in economics, it turned up a fair amount in computer programming. I'd be happy to see the article go away, but if someone here thinks it can be re-factored into something meaningful, that would be good, too. CRETOG8(t/c) 06:27, 23 September 2009 (UTC)

That article your prodded can be safely deleted. We have a couple of compsci articles on Database transaction and Transaction processing. Those articles are somewhat stubish and not sufficiently general or even well-connected, e.g. the TP article only links to database transaction in the see also area. No effort is made to define transaction in general. Those articles also lack basic mathematical defnitions of the topics. There is actually more than one notion of transaction depending whether you use the page model or the object model. Those articles don't even use as reference the standard theory textbook in this area (Weikum and Vossen, Transactional information processing [7]). Like most compsci areas on this wiki, transaction processing needs expert editors... Pcap ping 07:32, 23 September 2009 (UTC)

After a quick look, the only good article in this area is Snapshot isolation, which does reference recent developments, e.g. Fekete et al. landmark paper. Pcap ping 07:55, 23 September 2009 (UTC)

[edit] Java WikiProject

I don't want to put a mumbo jumbo into the bongo, I don't want to do too much glitz in the blitz, damzels and sirs, but I wonder if it would be a good thing to create (like now or yesterday) a Java WikiProject along the classy Programming languages WikiProject (like there is for C++) under the Computing and Computer science WikiProjects. If I'm cor-rec-to, there are about 900 articles or more on Java technology in Wikipedia, which may be more than ALL other programming languages articles combined... Proof is in the pudding my good friends so let's join the bandwagon of free coffee from the east... Please go to this sexy page --Alainr345 (talk) 07:16, 24 September 2009 (UTC)

[edit] Popular pages

I have requested a list of popular pages for this project at [8]. --78.111.169.38 (talk) 10:11, 8 October 2009 (UTC)

[edit] Leadership?

A bit off-topic -- but -- virtually all of the edits I do at WP are on math articles, with some spill-over to physics and comp-sci. I've not been active for the last few years, because I got tired of the editorial nonsense that goes on. Despite being inactive, I recently was attacked, more or less unprovoked, by a new-age editor who had vandalized an obscure math article I wrote, and someone else reverted. When I told him off, I was promptly piled-on by five admins who blocked me for several weeks. I'm kind of shocked that the power structure here has changed so much that we've got these kinds of nasty, abusive people in admin roles. I complained to the Arb, but they ignored the case. I don't know what to do, other than to complain here, and ask everyone to try to band together, and to figure out how to get the ugly admins and the (incompetent?) leadership out of power, redo Wikipedia leadership, and restore some sanity.linas (talk) 16:43, 13 October 2009 (UTC)

• Could you link to the article and talk pages involved? Diego (talk) 17:43, 13 October 2009 (UTC)
  • This ANI thread was raised because of his messages. Might be the best place to look for info. -- M2Ys4U ^(talk) 18:58, 13 October 2009 (UTC)

This has been forum-shopped to Mediation, to the Arbitration Committee, and now to the talk pages of several WikiProjects. Editors coming to this situation with no prior knowledge should read Wikipedia:Administrators' noticeboard/IncidentArchive564#Nuclear meltdown at User talk:Linas, Wikipedia:Administrators' noticeboard/IncidentArchive567#User:Linas again, Wikipedia:Requests for mediation/User:Linas, and this declined ArbCom request to get up to speed. Please place all further discussion at Wikipedia:Administrators' noticeboard/Incidents#Linas, soapboxing on wikiprojects (and userpage), rather than having lots of little disjoint discussions everywhere that this has been shopped around to. Uncle G (talk) 02:05, 14 October 2009 (UTC)

Uncle G, you are very wrong, and your baseless attack on me is indicative of the utter failure of the power elite within wikipedia to run this project. There is a reason that editors are quiting WP, and that reason is people like you. linas (talk) 20:40, 3 December 2009 (UTC)

[edit] Many overlapping analysis of algorithms articles

I've noticed several overlapping articles related to analysis of algorithms, which makes it extremely confusing. I'm planning to edit some, merge some, and try to get an overall coherent structure for these. These are the articles I'm talking about:

• Best, worst and average case. The articles Worst-case complexity and Average-case complexity should be merged into this one. On the other hand, Worst-case execution time seems to be unrelated to these three. (Am I right? Or is Worst-case execution time a huge WP:CFORK of Worst-case complexity?)
• We have an article on Randomized algorithms and another one on Probabilistic analysis of algorithms, although Probabilistic algorithm redirects to Randomized algorithm. Should we have two separate articles on randomized and probabilistic algorithms? Or is it better to have one article, which explains it all clearly? (Including bounded-error probabilistic algorithms (Monte Carlo or BPP), and 1-sided error algorithms (RP or Co-RP), and 0-error (Las Vegas or ZPP) algorithms.)

Robin (talk) 23:42, 14 October 2009 (UTC)

I don't think you need to have a randomized algorithm in order to be able to perform a probabilistic analysis on it (that refers more to randomized input or giving a probability distribution of the run-time as the output of the analysis.) The rest is also dependent on whether you prefer the Britannica or Brockhaus method of organizing an encyclopedia, but my preference would be to have a single overview article on the analysis of algorithms. —Ruud 13:52, 15 October 2009 (UTC)

Agree. And in fact there is the Computational complexity theory but perhaps it isn't the name one would have thought of typing in and is I feel aimed a bit too much at the theoretical side for an introduction. Dmcq (talk) 15:55, 15 October 2009 (UTC)

Computational complexity theory is an extremely theoretical field, and it would be inappropriate to have any analysis of algorithms topics in that article. --Robin (talk) 16:06, 15 October 2009 (UTC)

Well then there's always Analysis of algorithms which I would have considered a level down. And that is a much more tractable article as an introduction. Dmcq (talk) 16:35, 15 October 2009 (UTC)

[edit] Can someone take a look at this?

Can someone who understands computability theory and/or German take a look at the following image which I translated from the original image at the German Wikipedia?

Unfortunately my understanding of computability theory is almost as bad as my understanding of German. I'm reasonably confident that the complexity theory and formal languages part has been translated correctly, but I'd like corrections/comments for that too. --Robin (talk) 04:33, 17 October 2009 (UTC)

By the way, is there a simple way to add clickable Wikilinks in SVG images? It would be great if all labels in this illustration were Wikilinks to the relevant articles. I found mw:Extension:ImageMap but not sure if it's the right solution. — Miym (talk) 11:12, 17 October 2009 (UTC)

I'm looking into this. I'll post here if I find out. --Robin (talk) 15:55, 17 October 2009 (UTC)

I think ImageMaps are the only way to do it. See how they've done it in Electricity distribution for example. --Robin (talk) 02:14, 18 October 2009 (UTC)

Technically, one can make URI links in SVG images using the a element, but it's pointless to do that on WP as the links cannot survive translation to PNG (which is what the site actually serves to the browser). — Emil J. 12:20, 19 October 2009 (UTC)

[edit] dANN and Johnson's algorithm

I could use a third opinion on Talk:Johnson's algorithm. Recently an IP added links to an open source graph library, dANN, to a bunch of graph algorithm articles and I reverted it as linkspam. The links have been added back again several times (mostly by another editor, not the IP), and the same anonymous editor (under a different number) is now arguing strenuously that dANN is a well-reviewed and well-regarded open source project and that the issues I have with its implementation of Johnson's algorithm should be discounted as original research. I'd welcome additional opinions, both on the question of whether this link should be included and on whether it's acceptable to judge the content of an external link oneself rather than relying on what other sources might happen to say about that link. Discussion should be taken to Talk:Johnson's algorithm where it is already ongoing rather than here, I think. —David Eppstein (talk) 08:00, 1 November 2009 (UTC)

[edit] CfD nomination of Category:Probabilistic_complexity_classes

I nominated Category:Probabilistic_complexity_classes at Wikipedia:Categories_for_discussion/Log/2009_November_17#Category:Probabilistic_complexity_classes to merged with its parent category. Comments/suggestions are welcome. --Robin (talk) 21:48, 17 November 2009 (UTC)

[edit] Pageview stats

After a recent request, I added WikiProject Computer Science to the list of projects to compile monthly pageview stats for. The data is the same used by http://stats.grok.se/en/ but the program is different, and includes the aggregate views from all redirects to each page. The stats are at Wikipedia:WikiProject Computer Science/Popular pages.

The page will be updated monthly with new data. The edits aren't marked as bot edits, so they will show up in watchlists. You can view more results, request a new project be added to the list, or request a configuration change for this project using the toolserver tool. If you have any comments or suggestions, please let me know. Thanks! Mr.Z-man 00:44, 1 December 2009 (UTC)

[edit] Request for article: Frame

I'd like to see an article for Frame (computer science), which explains what a frame is. The closest that I can find is frame language, which talks about frames without defining what they are, stack frame, which is a C/C++ concept only, and environment variable, which is a shell concept only. We don't have any articles that explain frames/environments for lisp or other functional languages. I have in mind something along the lines of Abelson, Sussman, "structure and interpretation of computer programs", section 3.2. Frames are a deep and important comp-sci concept, but most c/c++/java/perl/python programmers have only the vaguest notion of what that is, and think its a stack frame, which is just a balky special-case. linas (talk) 20:18, 3 December 2009 (UTC)

[edit] Merging "X problem" to "X"

I would like to encourage people to comment on these merger proposals:

• Talk:Dominating set#Merger proposal – merging Dominating set problem to Dominating set
• Talk:Independent set (graph theory)#Merger proposal – merging Independent set problem to Independent set (graph theory).

There are two other pairs of pages that could be merged as well:

• Clique problem to Clique (graph theory).
• Hamiltonian path problem to Hamiltonian path.

I would like to avoid the burden of maintaining pairs of largely overlapping articles. There also seems to be a lot of confusion when people create links to these articles. I think it helps a lot that we have only one article about, e.g., Vertex cover, with Vertex cover problem redirecting to it. Graph coloring is an excellent example of an article that covers both combinatorial and computational aspects of the same problem. — Miym (talk) 19:15, 5 December 2009 (UTC)

I support the merging of all such articles, as I commented on the other talk pages. --Robin (talk) 14:29, 6 December 2009 (UTC)

Does anyone think its a good idea to merge permanent with computing the permanent? --Robin (talk) 04:15, 7 December 2009 (UTC)

See also Permanent is sharp-P-complete and Wikipedia:Articles for deletion/Permanent is sharp-P-complete. But (even if one gets rid of the detailed proof in the #P-completeness article) these are three reasonably long and reasonably distinct articles on an important topic. I think trying to merge them would lead to something too big and unwieldy to work well as a single article. Of the three, the algorithm article and the lower bound article supply adequate references already to justify the notability of their subtopics. The main permanent article does not, and "permanent" is an unfortunate word to try to search for, but this search turns up plenty of references many of which have little or nothing to do with algorithms. —David Eppstein (talk) 20:58, 13 December 2009 (UTC)

I think that the #P-completeness article should be a different article, just like the proof of the Cook-Levin theorem should be a different article from the article on SAT or CircuitSAT. The articles on computing X and X might be merged, as User:Miym suggests above. I thought permanent and computing the permanent also seem to fall in the same framework. But I don't have a strong opinion about it. --Robin (talk) 21:39, 13 December 2009 (UTC)

I think it makes sense on heavily studied problems (including clique and Hamiltonian paths) to have separate articles about the mathematics of the problem (results about cliques that do not involve algorithms, of which there are many) and the computer science of the problem (algorithms for computing cliques, of which there are many). The reason for merging "Clique problem" and "Clique" is that both articles are really minimal, do not really cover either the mathematics or the computer science of the problem well, and do not clearly distinguish which aspect of the subject they are covering. But that's less true for the permanent, where the computer science side is represented not by a vague "permanent problem" algorithm but by two more specific articles, one about algorithmic aspects of the problem and the other about complexity theoretic aspects of the problem. I think the right thing to do in this case is to make the third article more specific, about the mathematics of the problem, and more detailed. I think the right thing to do in the long term for clique is similarly to have two or three articles (the NP-completeness of clique is not independently interesting the way the hardness of permanent is, but there are interesting things to say about the computational complexity of approximating cliques), but that would be a lot more work than merging our two existing inadequate articles. —David Eppstein (talk) 21:51, 13 December 2009 (UTC)

PS Note that in the case of cliques we do also have several articles on important mathematical subtopics associated with cliques: Ramsey's theorem and Turan's theorem, for instance. I don't think it would occur to anyone to merge those into the parent clique article. Similarly, if we had a focused article on algorithms for computing cliques, it shouldn't be merged into the parent article. But that's not what clique problem currently is. —David Eppstein (talk) 21:59, 13 December 2009 (UTC)

In general, if the "X problem" is too long it shouldn't be merged into X, but only a WP:SUMMARY of the algorithm(s) should be added to X, and similarly for complexity proof articles if they are long and notable (add only proof sketch to main article). So:

• I concur with merging Clique problem into Clique because the "problem" page is short. As David Eppstein pointed above, it could be split again later if too much material on algorithms is added.
• Agree with merging Hamiltonian path problem to Hamiltonian path for the same reason.
• Agree with merging Independent set problem to Independent set (graph theory). In this case the latter is short.
• Dominating set was already merged with Dominating set problem, I see. No objections. The same goes for Vertex cover/Vertex cover problem.
• The split between Permanent and Computing the permanent seems reasonable, although "Computing the permanent" could be renamed to Algorithms for computing the permanent, since the complexity proof isn't covered there.

Did I miss !voting on anything discussed above? Pcap ping 11:27, 14 December 2009 (UTC)

Re cliques, you mean clique (graph theory) not clique. But until yesterday clique (graph theory) was also very short. I'd like to work on expanding and improving the clique problem article (there is quite a bit of important material that should be covered and isn't) but it may take me a few days to find the time, so I'd appreciate holding off on this one. I have no immediate plans to work on the others listed here. —David Eppstein (talk) 16:53, 14 December 2009 (UTC)

Clique problem is now expanded, and quite large. I took the liberty of removing the merge tags since I don't think it makes sense any more. —David Eppstein (talk) 06:16, 17 December 2009 (UTC)

[edit] X Problem versus Computing X or Algorithms for X

Since we’re thinking about the X Problem pages, let me take up a related issue that’s been nagging me: For some reason we seem to have the convention of referring to the algorithmic issues around combinatorial construction X as X Problem. There is really no good reason for that. Though I haven’t done a tally, textbooks don’t refer to, say, the problem of computing a vertex cover as Vertex Cover Problem. They just call it Vertex Cover. (There are a few exceptions, such as the Traveling Salesman Problem, which always seems to have the “Problem” suffix.) So there isn’t really any previous art we have to follow. Moreover (and maybe more importantly), X Problem doesn’t communicate “Algorithms for X” to anybody outside algorithms theory either, any more than it does in Entscheidungsproblem or P versus NP problem or Inverse Galois problem. So I think a subsection called, e.g., Algorithms under the headline X is correct, with a possible subarticle then called Algorithms for X, or Multiplication algorithm or Computing the permanent or whatever is well-established in the literature. Thore Husfeldt (talk) 21:46, 14 December 2009 (UTC)

I did my homework now, regarding the terminology of computational problems.

Introduction to Algorithms uses the rhetoric prevalent on Wikipedia: For example, independent set is the combinatorial object, independent-set problem is the (optimisation version) of the computational problem of finding a maximum independent set. (Exercises to chapter 34) Note the hyphen; the book always does it like that: subraph-isomorphism problem, integer linear-programming problem, etc.

Algorithms by Dasgupta, Papadimitriou, Vazirani: Section 8.2 enumerates 18 computational problems, only Traveling Salesman Problem is given on that form, all others are like Shortest path or Independent Set. However, in the text itself, it often appears as “Recall the Knapsack problem”, with “Knapsack” in small caps, but not always. “Vertex Cover is a special case of Set Cover, which…”

Algorithm design by Kleinberg and Tardos includes a taxonomy of computational problems in section 8.10. Again, the problem is just called “Hamiltonian Cycle” or “Graph Colouring” (no special typeface). Even TSP appears just as “Traveling Saleman”.

Computational Complexity by Papadimitriou sets computational problems in small caps lowercase, like this: “CLIQUE and NODE COVER are NP-complete”. Again, no “— problem” suffix. TSP gets special treatement, section 1.3 is The Traveling Salesman Problem.

Encyclopedia of algorithms (Kao, ed.) has an entry called Traveling Salesperson Problem, which redirects to Traveling Sales Person with Few Inner Points, and an entry for Euclidean Traveling Salesperson Problem. But otherwise, it’s largely the other school: Graph Isomorphism is called just that (by McKay), Graph Coloring by (Langberg), etc.

There are more books that are relevant for such a survey, but I think it’s safe to say that there is no strong tradition within algorithms to refer to the computational problem by X Problem, and it certaily makes little sense to people outside of algorithms. Thore Husfeldt (talk) 10:19, 15 December 2009 (UTC)

I agree that X Problem isn't often used in the literature, primarily because the language associated with the Hamiltonian path problem, for example, is usually called HAMILTONIAN PATH. The problem is usually just referred to by the language, like PRIMES, or ST-CONNECTIVITY, or USTCON. Merging X with X Problem would, to some extent, solve this problem, since the X page will now have a subheading like "algorithms" or "computational complexity", instead of "X problem". --Robin (talk) 14:16, 15 December 2009 (UTC)

[edit] Status

A quick status update:

• Merging Dominating set problem to Dominating set: Done.
• Merging Independent set problem to Independent set (graph theory): Done (copy-editing needed, contributions welcome).
• Merging Clique problem to Clique (graph theory): Proposal withdrawn.
• Merging Hamiltonian path problem to Hamiltonian path: Not yet done, but looks straightforward.

— Miym (talk) 20:27, 22 December 2009 (UTC)

[edit] List of computer science conferences

I think the List of computer science conferences is now in a fairly good shape; however, I would like to get more feedback, especially regarding those fields with which I am not familiar. It would be great if the participants of this project could have a quick look at the list and see if it looks reasonable in their own areas of expertise. If you spot bogus conferences or minor workshops, please remove them; if a top conference is missing, please add it (with references); if some conferences are miscategorised, feel free to move them around. You can also mention obvious omissions on the talk page – I can try to find references, too. — Miym (talk) 22:07, 16 December 2009 (UTC)

[edit] Time complexity

Does anyone feel that it might be a good idea to merge the following articles: Constant time, Linear time, Polynomial time, Pseudo-polynomial time, Sub-exponential time and Exponential time into one article on time complexity? Currently, these articles are in a bad shape, and often have repeated (and contradictory) information. Also, we don't really have a good article that explains time complexity. --Robin (talk) 03:51, 17 December 2009 (UTC)

I think this would be a very good idea. We could use something like Big O notation#Orders of common functions as a starting point. I think we should also cover things like Logarithmic time, Linearithmic time, and Double exponential time, so that we would have a better target for these redirects as well. — Miym (talk) 10:01, 17 December 2009 (UTC)

Seems like a good idea in general, but some of those articles, like Sub-exponential time are not so short. Pcap ping 13:03, 17 December 2009 (UTC)

Sub-exponential time isn't short because it contains quasi-polynomial time as well, and a table. If we combine all, there will be just one table, and some text about each running time. I agree that such a merged article will be long, but I don't think it'll be too long, especially after removing all the overlap. --Robin (talk) 14:37, 17 December 2009 (UTC)

Seems feasible. Pcap ping 18:31, 17 December 2009 (UTC)

[edit] Theory of Computing (journal)

I just noticed that Theory of Computing (journal) has been proposed for deletion. I believe it should be possible to find sources that show the notability of this journal; however, I won't have time to do that before the prod expires. Perhaps someone else might be interested in having a look at the article? — Miym (talk) 13:02, 23 December 2009 (UTC)

Hi Miym. I've removed the deletion notice. It seems unreasonable to blindly apply the rule "Does it appear in an index?" when so few open access journals do. If someone wants to delete it, the should use an AFD, surely, since it is certainly contestable. ComputScientist (talk) 13:16, 23 December 2009 (UTC)

Can you provide some evidence that the journal passes WP:Notability (academic journals)? Ultimately I suppose such evidence would come out in an AfD, but I'm trying to figure out whether it would be appropriate to even start an AfD. —David Eppstein (talk) 17:35, 23 December 2009 (UTC)