Wikipedia talk:WikiProject Computer science/Archive 8

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Archive 5 Archive 6 Archive 7 Archive 8 Archive 9 Archive 10


Todo list

Hey all, I (apparently re-) introduced the Todo list. Specific requests for editing assistance should be added there so that they're more easily seen, and preserved across archives. If there are any outstanding issues remaining from the archives, please copy them into the Todo list. Ham Pastrami (talk) 19:01, 6 May 2008 (UTC)

Why are you messing about with the project page so much? There are other people who use it, the recent changes links are useful. MattOates (Ulti) (talk) 12:25, 7 May 2008 (UTC)
I've added back the "recent changes" links (and a few other things that recently went missing). --Allan McInnes (talk) 17:11, 7 May 2008 (UTC)
No problem, if you didn't like the changes you are naturally free to revert or improve them. The thing is, judging by the lack of activity in the project I'm not so sure that they are that useful. My changes were intended to help people get into the project and up to speed without being deluged by a myriad of links that, to me, only seem to clutter the page. I mean, the point of a WikiProject page is to provide some kind of focus. Linking every possible shortcut that someone might use doesn't seem to be the best way of coordinating effort. If you personally use these shortcuts a lot, you can always make them part of your personal user page. Ham Pastrami (talk) 20:43, 30 May 2008 (UTC)

Formal language

I think the article formal language has degraded severely over the last few weeks. Here are some milestones:

The degradation is probably due mainly to the activism of Gregbard, but the narrow (philosophical) POV of Philogo doesn't help either. I encourage anyone interested in the topic to comment on Talk:Formal language. If there is enough support perhaps we can revert the article to a sane earlier version. --Hans Adler (talk) 10:05, 25 May 2008 (UTC)

capitalization of eponymous laws -- opinions sought in move discussion

If you have an opinion on capitalization of "law" in titles, there's an open discussion on a move proposal in Talk:Moore's Law, an article in this project. Dicklyon (talk) 18:18, 30 May 2008 (UTC)

added a new page - cyber-physical systems

Hello, I added a page on cyber-physical systems, right now it's a total stub but hopefully people can add more to it. I've listed a few papers from the NSF workshop on CPS, and have some mobisys papers in mind, maybe some text books too. Hope people can help! Thomaslw (talk) 12:30, 5 June 2008 (UTC)

More pictures

So I got Fred Brooks and Michael Flynn, and I'll have Tom Sterling before the month is out. If you look at the infobox, you'll see that I recently added a bunch of turing award winners. Specifically, I added all of the living ones whose articles don't have pictures. Since virtually all computer scientists have email addresses, I think contacting each of them with a request is a feasible idea - and starting with the oldest of them is a prudent one. (I'd like to avoid a repeat of what happened with Robert Tomasulo; I emailed Fernando Corbato tonight) If anyone feels up to the job, I'd appreciate all the help I can get. Raul654 (talk) 01:17, 11 June 2008 (UTC)

Tom Sterling done. Fernando Corbato emailed me back yesterday with good news. I hope to have his pic up soon. I've added the Eckert-Maunchly award winners to my to-do list. Raul654 (talk) 19:34, 23 June 2008 (UTC)

I've been sending out a lot of emails trying to get pictures. I've created user:Raul654/Computer to help keep track of my progress. Also, apparently a great many article-worthy computer scientists are part of MIT's CSAIL. I'm in touch with the CSAIL photographer - hopefully I'll be able to get those articles illustrated in bulk. Raul654 (talk) 19:55, 28 June 2008 (UTC)


I wanted to find more info on "cycles" per The Jargon File v4.4.7

"The basic unit of computation. What every hacker wants more of.... One can describe an instruction as taking so many clock cycles. Often the computer can access its memory once on every clock cycle, and so one speaks also of memory cycles. These are technical meanings of cycle. The jargon meaning comes from the observation that there are only so many cycles per second, and when you are sharing a computer the cycles get divided up among the users. The more cycles the computer spends working on your program rather than someone else's, the faster your program will run. That's why every hacker wants more cycles: so he can spend less time waiting for the computer to respond."

I wanted more info on "cycle" e.g. What exactly does it correspond to in a non-slang sense? Is this term/concept still found useful today, or have subsequent developments in computing made this less relevant? It used to apparently be common for sysadmins to adjust things so that they received a disproportionate share of "cycles", whereas users whom they found annoying had their computers throttled back to one operation per decasecond - does that still happen much?

Our disamb page Cycle lists Instruction cycle. That article does not make clear to me whether this is the same meaning as the Jargon File sense (I think that it is, but I'm not sure.)

Would anyone care to either add something on this to Instruction cycle, or create a new appropriate article, or add content to some other existing article (and add a link to that article at Cycle)?

(I will not be doing this myself. If you have info on this, please do not simply respond here, but create article/content/disambiguation so that other Wikipedia users may benefit thereby.)

Thanks! -- Writtenonsand (talk) 13:38, 12 June 2008 (UTC)

All synchronous processors - that is, pretty much all the ones you've ever used - synchronize their actions according to some common clock. Each cycle (Instruction cycle) corresponds to exactly one tick of that clock. Yes, this is still a very relevant concept in computer science/engineering.
As for your final question, some older computers used to have a Turbo button which locked the system speed to some multiple of clock ticks (that is, instead of completing a cycle on every clock tick, they'd complete it on every 2nd, 3rd, 4th, etc clock tick). This slowed the computer system down, and allowed the user to play some games that depended on computer system timing. Admittedly this has the potential for abuse, but it's rather easy to notice and fix, and I don't know of any instances where this was abused. You may also want to read our nice (Unix) article. Raul654 (talk) 14:00, 12 June 2008 (UTC)
Just to add a few quick notes: You probably already knew that processor speed is measured in "Hertz" (Hz), but you might not have realized that Hz is defined as cycles-per-second. The greater the Hz, the larger the number of "clock ticks" per second. As of 2008, most processors are rated in the Gigahertz (GHz) range, which depending on who you ask is either 230 or 109 cycles-per-second.
Instructions take X number of cycles to execute, and operations take Y number of instructions to complete, but X and Y vary depending on the architecture of the processor. To avoid apples-and-oranges comparisions, MIPS (millions of instructions per second) and FLOPS (floating-point operations per second) are sometimes used in place of Hertz.
Finally, note that the inverse of Hertz is "period", defined as seconds-per-cycle. One would probably describe the period of a GHz processor in terms of nanoseconds (a nanosecond is 10-9 seconds). Groupthink (talk) 22:35, 12 June 2008 (UTC)


WikiProject Software Hello WikiProject Computer science. You have been invited to join WikiProject Software, a WikiProject dedicated to improving the Software-related articles on Wikipedia. You received this invitation due to your interest in, or edits relating to or within the scope of the project. If you would like to join or just help out a bit, please visit the project page, and add your name to the list of project members. You may also wish to add {{User WikiProject Software}} to your userpage and == WikiProject Software Centralized Announcement System ==

{{Wikipedia:WikiProject Software/Announcement-u}}

to the top of your talk page.

If you know someone who might be interested, please pass this message onto others by pasting this code into their talk page:

== [[Wikipedia:WikiProject Software|WikiProject Software]] Invite == {{subst:Software invite|~~~~}}


ulimit nominated for deletion

See Wikipedia:Articles for deletion/Ulimit. To what extent should Wikipedia cover Unix utilities and shell built-ins, without going against the "Not an instruction manual" rule? Since this is just one of many articles devoted to a Unix command, it is a question that the members of this project might be interested in. I'm posting here because Unix is listed as "belonging" to this WikiProject. --Itub (talk) 10:11, 17 June 2008 (UTC)

Because of its centrality in practical computing (outside the Microsoft world and evne there to a large but not so obvious extent), Unix concepts are relevant to understanding modern computing. Fork, pipe, standard in and standard out, grep, more (or less), root, shell, ... are all, in my view candidates for Wikipedia article, without violating the NotAManual policy. There are certainly Unix aspects which don't (all those exec variants, for instance, or the differences between BSD and Sys V versions of ps, for another), but good sense will make the distinction. There's likely to be conflict at the edges, of course, but this is likely unavoidable, editors being editors. So I would vote against routine deletion for articles on Unix utilities. ww (talk) 03:23, 19 July 2008 (UTC)

Rename proposal for the lists of basic topics

This project's subject has a page in the set of Lists of basic topics.

See the proposal at the Village pump to change the names of all those pages.

The Transhumanist 09:56, 4 July 2008 (UTC)

Changes to the WP:1.0 assessment scheme

As you may have heard, we at the Wikipedia 1.0 Editorial Team recently made some changes to the assessment scale, including the addition of a new level. The new description is available at WP:ASSESS.

  • The new C-Class represents articles that are beyond the basic Start-Class, but which need additional references or cleanup to meet the standards for B-Class.
  • The criteria for B-Class have been tightened up with the addition of a rubric, and are now more in line with the stricter standards already used at some projects.
  • A-Class article reviews will now need more than one person, as described here.

Each WikiProject should already have a new C-Class category at Category:C-Class_articles. If your project elects not to use the new level, you can simply delete your WikiProject's C-Class category and clarify any amendments on your project's assessment/discussion pages. The bot is already finding and listing C-Class articles.

Please leave a message with us if you have any queries regarding the introduction of the revised scheme. This scheme should allow the team to start producing offline selections for your project and the wider community within the next year. Thanks for using the Wikipedia 1.0 scheme! For the 1.0 Editorial Team, §hepBot (Disable) 22:04, 4 July 2008 (UTC)

A discussion

An important discussion on " Should WikiProjects get prior approval of other WikiProjects (Descendant or Related or any ) to tag articles that overlaps their scope ? " is open here . We welcome you to participate and give your valuable opinions. -- TinuCherian (Wanna Talk?) - , member of WikiProject Council. 14:51, 8 July 2008 (UTC)

All code in templates proposal

Please take a look at my proposal at Wikipedia:Village_pump_(proposals)#All_code_samples_should_be_transcluded, and respond on that page. Thanks! Dcoetzee 00:25, 18 July 2008 (UTC)

Assistance request

I've been forced into the position of asking for assistance with the content and writing style of an article I've been long editing. Since it's pretty central to computer use, and referenced in the WP's new user page, getting it to a good condition is important. The article is Password strength, and the history is more or less as follows. For some time, the article had been accumulating cruft or one kind or another, as many do, and earlier this year (see page history) an editor notice this and began a major revamp. I had also noticed it, but hadn't gotten up the gumption to dive in myself. So I decided to assist as I could. There was some difficulty (well covered on the talk page) over both technical issues and writing issues. Email exchanges (very much along the lines of the talk page discussion) failed to produce much progress.

The article is now stalled (3RR is on the horizon), but is in an unsatisfactory state, both from confusion about technical issues (eg, randomness v entropy in this context) and with respect to writing -- organization, and clear and helpful presentation.

Editor relations having become wedged, I have resolved to ask for assistance. Any here who are willing to lend a hand should look over the situation, and attempt to make improvements. Thanks. ww (talk) 03:48, 19 July 2008 (UTC)

"ToonTalk computer programming language" needs your help

Could members of this project please take a look at ToonTalk computer programming language and regularize the article title, as well as formatting and terminology within the article? Thanks. -- (talk) 02:14, 24 July 2008 (UTC)

Optimal classification

Hi - is there anyone in the project who works in pattern recognition and statistical classification? I'd appreciate some insights into the optimal classification article (see Wikipedia:Articles for deletion/Optimal classification). Thanks! --Jiuguang (talk) 16:43, 24 July 2008 (UTC)

Articles flagged for cleanup

Currently, 507 articles are assigned to this project, of which 173, or 34.1%, are flagged for cleanup of some sort. (Data as of 14 July 2008.) Are you interested in finding out more? I am offering to generate cleanup to-do lists on a project or work group level. See User:B. Wolterding/Cleanup listings for details. More than 150 projects and work groups have already subscribed, and adding a subscription for yours is easy - just place a template on your project page.

If you want to respond to this canned message, please do so at my user talk page; I'm not watching this page. --B. Wolterding (talk) 18:19, 2 August 2008 (UTC)

Integrated banner with {{WikiProject Computing}}

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

This project is a subset of the parent project WP:COMPUTING.This project articles contains both {{WikiProject Computer science}} and {{WikiProject Computing}} and possibly other descendant wikiproject banners also.

I am proposing the use of the integrated banner of {{WikiProject Computing}} , if there is a consensus among our project members...

Example :

{{WikiProject Computing|class=start|importance=Mid|science=yes|science-importance=low}}

will produce...

WikiProject Computing / CompSci (Rated Start-class, Mid-importance)
WikiProject icon This page is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology 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.
Start-Class article Start  This page does not require a rating on the project's quality scale.
 Mid  This page has been rated as Mid-importance on the project's importance scale.
Taskforce icon
This page is supported by WikiProject Computer science (marked as Low-importance).
  • This project and its autonomy will remain the same...
  • No pages have to be moved as a task force.

The advantages of this are :-

  • Intergated banner which takes up less space and avoid clutter of different Computer related WikiProjects.
  • Greater co-operation and co-ordination among computer related wikiProjects.
  • Each WikiProject doesnt have to maintain an assessment department...Since the standards for WP 1.0 Assessment is same for all WikiProjects, single assessment is only required for all the computer related WikiProjects. This means more time for individual computer wikiprojects to help and improve the articles in their scope..
  • Seperate stats for quality and importance for both parent and descendant projects ( as before)
  • Catergory intersection of quality and importance available like Category:Amiga articles by quality and importance for WP:Amiga

Possible Actions:

Thoughts ?? -- Tinu Cherian - 04:29, 3 August 2008 (UTC)

Oppose - I don't believe that every computer science article should also be a computing article, and furthermore I find these integrated banners highly cluttered. I would prefer the banners remain separate. Adam McCormick (talk) 20:39, 3 August 2008 (UTC)
Still Oppose - Computer science is not a subfield of computing. Computing really shouldn't cover topics such as Artificial intelligence, machine learning, data mining, algorithms or computational complexity. These topics are the meat of computer science but don't even require the use of a computer. By integrating the banners, you would force many topics that have nothing to do with computers, or information technology to be grouped there. This is not acceptable. CS is not a subfield of computing, Programming is, maybe, a subfield, but the meat of CS is not and grouping them is not correct. Adam McCormick (talk) 15:49, 5 August 2008 (UTC)
Oh? I'm curious to know what approach would you use to do Artificial intelligence, machine learning, data mining, algorithms or computational complexity without computers (other than study them and never put them into practice) ;-) Diego (talk) 16:39, 5 August 2008 (UTC)
There are good examples in the area of, say ... Turing undecidability, which are mathematical proofs, and not something you'd implement as an algorithm. -- Or oracle machines, which are computers that could never be built, (at least, not as Turing machines .. perhaps quantum computers?) but the theory is still interesting. Please note that oracle machines are not arcane, they're commonly covered in undergrad texts on computing theory. I've been reading Barendregt's book on lambda calculus, and while its technically comp sci, 99.999999% of it will never ever be implemented as a computer program or hardware or anything -- its a math book, for all intents and purposes. linas (talk) 17:35, 5 August 2008 (UTC)
Oppose - For same reasons as Adam McCormick --Cybercobra (talk) 21:53, 3 August 2008 (UTC)
Still oppose --Cybercobra (talk) 05:19, 6 August 2008 (UTC)
Oppose - per Adam McCormick — Johnl1479 22:11, 3 August 2008 (UTC)
After reading the extending explaination by the 'nominator' below, I would like to change my vote to Support. Computing != Computer Science, but project Computer_Science extends ComputingJohnl1479 04:38, 5 August 2008 (UTC)
Yes, that's true, but the argument below is that Computing extends Computer science or for those C++ folks, class Computing : public ComputerScience which is not a valid assumption. Adam McCormick (talk) 15:54, 5 August 2008 (UTC)
I'm also reading it like class ComputerScience: public Computing, which is mostly true in a practical way (the exceptions that I listed below would be friend class DiscreteMathematics; ) although it's not strictly true in an ivory tower sense. The wp:wikiprojects are not an ontology. Diego (talk) 16:20, 5 August 2008 (UTC)
Java ftl... :-P. Anyway, now I'm confused. Is he saying 1) Computer Science is a child of Computing, or that 2) Computing is a child of Computer Science? 'Cause that is what is all depends on. — Johnl1479 02:02, 6 August 2008 (UTC)
Ah, to hell with it, I still opposeJohnl1479 02:04, 6 August 2008 (UTC)
Oppose - computing != computer science. Iknowyourider (t c) 01:19, 4 August 2008 (UTC)
May I know what exactly are the concerns in the integrated banner ?
The scope of Computing WikiProject is defined here...Wikipedia:WikiProject_Computing > Scope and Goals. On a broader view, it can said that the scope of Computing WikiProject is articles related to areas or subjects relating to computers , computing and information technology. Please note that WP:COMPUTERS was merged to WP:COMPUTING long time back. "computing" means using computers and other computing machines. It includes their operation and usage, the electrical processes carried out within the computing hardware itself, and the theoretical concepts governing them (computer science).
Isnt single banner better than the article being tagged separately by say WP:COMPUTING and WP:Comp Sc, WP:software etc...I feel that it avoids the clutter of banners better-- Tinu Cherian - 02:09, 4 August 2008 (UTC)
Perhaps the kind of people who are interested in computer science are not interested in other aspects of computing, and v.v. ? Perhaps your proposal is similar to trying to merge WP:Linux and WP:Windows into, for example WP:Computer Users -- it might not be something that everyone would agree to. linas (talk) 03:21, 4 August 2008 (UTC)
Oppose - per Adam. --Chet B. LongTalk/ARK 02:20, 4 August 2008 (UTC)Support - after reading the new definition and clarification by Tinucherian. --Chet B. LongTalk/ARK 18:17, 5 August 2008 (UTC)

let me explain further. This is NOT_A_MERGER_PROPOSAL between WP:COMPUTING and WP:CompSc..... WP:COMPUTING is like a parent project ( call it umberalla project) to all computer related aspects and wikiprojects similar to WP:Christianity. People are welcome to work in any of the descendant projects like WP:Anglicanism or WP:CATHOLIC or even work with WP:Christianity as a whole. Similarly people are free to work in either WP:Linux or WP:Windows or both or even WP:COMPUTING depending on their interest.The autonomy of individual WikiProject remains the same ( see WP:Amiga or WP:Websites ). This effort is just a initiative to work in greater collabration between the computer related WikiProjects.

The seperate importance for each WikiProject helps to identify the importance of the article for each project seperately. Howover the |class= parameter which defines the quality of the article is same for all projects which is in accordance with the WP 1.0 Assessment standards.

Think of these advantages :

  • Only one assessment rating is needed , whether it is computing, networking , comp sc. etc ,which gives the WikiProject members more time in article improvement and less overhead for administrative activities.
  • A article may be a tagged by different computer related WikiProjects say WP:Computing, WP:Comp Sc. , WP:Databases ? Which is better ? Having a single banner which supports all or different banners which takes up too much space on the talk page.

Having said that, there is no clear line separating the two projects of WP:Computing and WP:Comp Sc.. All articles in WP:Comp Sc is within the scope of WP:Computing but not viceversa. The scope of WP:Computing is boarder and Comp Sc related articles account for a major portion of the articles. This calls for better interaction and co-operation of these WikiProjects -- Tinu Cherian - 04:38, 4 August 2008 (UTC)

For - I believe Computer Science is extended arm of Computing and there is no harm in having integrated banner for sister projects or parent-child projects, infact it makes tagging easy. Where ever there may be requirement a specific note may be left that explaining standing of article e.g. Bio-Informatics may come under Computing, Computer-Science, Databse, etc. as bio-informatics is related with them all(in field of Computation). There is very good example of same pattern being follwed by WikiProject India where articles fall under scope of different projects but we use integrated banner there listing different projects under umbrella of WP India. To conclude, I think it is great to integrate different inter-related projects in one banner. --Sayed Mohammad Faiz Haider Rizvi (talk) 04:21, 4 August 2008 (UTC)
still for --Sayed Mohammad Faiz Haider Rizvi (talk) 09:01, 6 August 2008 (UTC)
for - WP is otherwise cluttered with too many banner templates - a unified one is much better than two separate. Said: Rursus 06:41, 4 August 2008 (UTC)
For - but with reservation. Computer Science is the top level (i.e. parent class) of the academic field. As such things like databases, AI, and even Software Engineering all really belong as a sub class of computer science. The only example I can think of that is computing but not computer science would be an article on the computer industry - and even then some may disagree. All that said, an integrated approach sounds good, and if computing has been chosen as the parent... so be it. Oboler (talk) 10:55, 5 August 2008 (UTC)
For - per Sayed Mohammad Faiz Haider Rizvi. There may be some very abstract mathematical non-computing results that are of interest for Computer-Science and not for Computing (e.g. general articles in topology, order theory or formal systems), but having them enclosed by the former would give enough hint of this, and they should be the exception more than the rule. Also articles about particular tools or platforms (Windows, Oracle, Logitech...) are of interest for Computing but not really for Computer-Science, so the second is mostly a subset of the first. Diego (talk) 12:58, 5 August 2008 (UTC)
Still For - this fusion is not about defining the fields of Computer Science and computing, is about joining forces in a practical way. Adding CS as a subsidiary project of Computing would allow for greater visibility to a more diverse audience, and would do nothing to change the platonic definition of both disciplines. Diego (talk) 16:47, 5 August 2008 (UTC)
Oppose - the kinds of article qualities that might make for a good article on databases are in general quite different than the kinds of qualities that would make for a good article on comp-sci. I think it's healther to evaluate an article from several perspectives, driven by specialists, rather than some vague general one-size-fits-all, lowest-common-denominator evaluation. linas (talk) 17:25, 5 August 2008 (UTC)
Comment - I think the integrated banner approach is very interesting. See for example Talk:Deep Impact (space mission). WP:WikiProject Space has a very broad scope, similar to this project, but they were able to organize the child projects appropriately. I think if there is a combined WikiProject for both Computing and CS, then the integrated banner makes more sense (you can incorporate software engineering, crypto, etc). --Jiuguang (talk) 18:30, 5 August 2008 (UTC)
For - I've not been very active, but I think that might give me a slightly more objective view. The argument of what is and what isn't Computing or Computer Science, is not in dispute here, from what I can tell? The banner is only displayed on the Talk page anyway, correct? Everyone opposing: your arguments would be valid if it were suggested that all Categories should be changed so that everything came under Computing, instead of Computer Science. The only thing I can see proposed here is the unification of administration of the projects, where appropriate, which I can only see being a good idea. Some review instead of no review, regardless of how generic or one-size-fits-all has to be an improvement (rather a Computing Project person than some unqualified random with too much time on their hands), and anyone can step in and dispute that review at a later time, or claim ownership by the Computer Science project specifically. Maybe there needs to be further discussion about what the joint banner means. I assume from the current format there is another version that says it has X importance to WikiProject Computing? Although I am "For" I don't really see why this is important, or really that great a help. If we spent this amount of time and energy on some collaborative editing of Computing/Computer Science articles instead of bureaucracy we wouldn't need to worry about administration ;D That last statement is under the assumption everyone edits for fun in their free time and gets enough TPS at work? MattOates (Ulti) (talk) 18:45, 5 August 2008 (UTC)
  • Weak Support - I can easily see both sides of the argument here. In short, not repeating the arguments above, I think the advantages of integrating a banner outweigh the disadvantages. --ZeWrestler Talk 00:29, 6 August 2008 (UTC)

Comments: Altough there is a better support for the integrated banner use, I dont wish to proceed without addressing the concerns of those who oppose. To be fair, I had dropped a note regarding this discussion to the talk page of ALL the members.
Let me go through some of the concerns expressed by some of the project members :

  • Computer Sc is a subset of Computing ?
    • Ans : Probably not, but WikiProject Computer Sc is a subset of WikiProject Computing. I would have definitely opposed to idea of Categorization of Comp Sc articles under Computing. And here lies the difference. Dont be mislead by the name WP:Computing. The scope of WP:Computing is 'anything related to computers and computing' in simpler terms ( including the science of it ) . Please note that WP:Computers was merged to WP:Computing long back for remove redundant project infrastructure.
  • Will WP:Comp Sc lose its autonomy and independancy ?
    • Ans : No ! This initiative is to reduce the Bureaucracy and administrative overhead on computer related WikiProjects and enhance greater collabration and cooperation.Since the scope of these projects are loosely overlapped ,many members are already members of both the projects. As I had said earlier , this is NOT a merger proposal of WP:Comp. Sc and WP: Computing. Think of the advantage of ONLY one single quality assessment to be done for every article unlike each WikiProject member manually assessing the quality of the article for each project banner. Still each project will get seperate stats for quality and their own importance scale. The importance of a particular article for WP:Computing may of Mid-importance but for WP:Comp Sc, it may be Top-importance. This facility is available in the intergated banner. Tell me which is better ? a clutter of computer related banners on the talk page or an integrated banner which servers all purposes! Frnd, we are making the the changes only on the talk pages not the articles. The result : you have more time to work on the articles of your interest. Having said the above , we are extending this initiative to all computer related wikiprojects.

-- Tinu Cherian - 06:06, 6 August 2008 (UTC)

Comment It is my opinion that WP:ComputerScience should not be a subset of WP:Computing. To answer the response to my last post above, graduate level CS courses in Machine Learning, Artificial Intelligence, Algorithms, Data Mining, and many other core CS topics do not rely on the use of computers. Most rely on advanced mathematics and bookwork, and may not even be implementable. Sure, many of the concepts are implemented on computers to show how they work, but they are not "Computing" concepts and are not specific to 'anything related to computers and computing'. They are no more a part of computing than Calculus is. Sure you use calculus to build computer programs but that should not put it under the Computing WikiProject.
I understand that you are not proposing that the two WikiProjects merge but you are forcing the improper assumption that WP:Computing should encompass all articles even tangentially relating to Computers which is not accurate and will only serve to inflate the size of that WikiProject and dilute its ability to improve its articles, not reduce any perceived bureaucracy. Adam McCormick (talk) 15:02, 6 August 2008 (UTC)

Comment I've been largely inactive for a long while, so I'm a bit out of touch on the whole banner thing. However, reviewing the comments above, it would seem that: some articles fall clearly into both Computing and Comp Sci; some articles seem to fall primarily or exclusively in Comp Sci; and some articles seem to fall primarily or exclusively in Computing. So perhaps instead of replacing the current two banners with a single integrated one, both banners could be modified to have an integrated option. Then, if an article is primarily Comp Sci, it can use the Comp Sci banner; if it has enough overlap into Computing, it can reference Computing with its integrated option. Likewise, if an article is primarily within Computing, it can use the Computing banner; if it has enough overlap into Comp Sci, it can reference Comp Sci with its integrated option. If a given article has overlap into both but is contentious enough that one of the two projects doesn't want to use the integrated banner, then just use both. In other words: implement and use the integrated banners where they make sense, but not where they don't. Then you get to reap the benefits of an integrated banner where you can, without losing the benefits of having separate banners where they'd be useful. Would that be an acceptable option? – Zawersh 19:48, 6 August 2008 (UTC)

I think that's an excellent suggestion. --Allan McInnes (talk) 22:49, 6 August 2008 (UTC)
I support that option too. Best of two worlds. Diego (talk) 08:08, 7 August 2008 (UTC)
This would be a reasonable alternative, IMHO. --Cybercobra (talk) 08:21, 7 August 2008 (UTC)
Very reasonable, but then let us decide the articles which doesnt need to use an intergated banner ? -- Tinu Cherian - 09:32, 7 August 2008 (UTC)
Why not just modify the template and let the wikiprojects work the rest out? Seems a lot of work to decide this now for every single article... --Cybercobra (talk) 10:17, 7 August 2008 (UTC)

Comment Two importance ratings is one too many. Can this banner possibly stick to one topic with one rating? (Thanks for the heads up on my talk page by the way and apologies if this has already been addressed.) -SusanLesch (talk) 19:18, 7 August 2008 (UTC)

The seperate importance ratings are important and has the following advantages :
  • More flexibility for both parent and descendant projects. ( greater independance and autonomy , I would say)
  • An article might be of say Mid importance for Computing Project, Top Importance for WP:Comp Sc and even may be Low importance for WP:Databases. This helps such situations.

Please note that this initative is extended and in discussion with all the computer related Wikiprojects and there is more or less unanimous support now.

You may need not consider this banner integration as an overhead as I will make sure the present importance rating for this project is properly carried over to the new banner parameters during the banner intergation . I will make sure there is no or minimal overhead to the descendant project members for this banner intergation ( TinucherianBot is a hardworking Bot :) ). Whether or not the you may need to add importance rating to newer articles is left to the descendant WikiProject members.. -- Tinu Cherian - 04:54, 8 August 2008 (UTC)

Oppose sorry, but because as said above "this is NOT a merger proposal of WP:Comp. Sc and WP: Computing". The idea of one or two WikiProjects breaking ranks to have their own special-cased conglomeration sounds confusing. And further confused if the suggestion above succeeded in making the banner flip back and forth from one WikiProject to another. Thanks for your suggestion but in my opinion it is probably better to conform to the model that is used by all of the projects. Regarding "Please note that this initative is extended and in discussion with all the computer related Wikiprojects and there is more or less unanimous support now", WikiProject Computing has no discussion at all. Maybe you can provide a better link. -SusanLesch (talk) 05:41, 8 August 2008 (UTC)

Please see below :
  • Disussion for Intergated banner for the existing Task forces and absorption of Inactive Wikiprojects can found here.
  • Discussion at WP:Websites can be found here.
  • Discussion for WP:Computer networking can be found here
  • Discussion for WP:Software can be found here.

-- Tinu Cherian - 06:01, 8 August 2008 (UTC)

Comment Can you please stop breaking up the threaded discussion? I for one have no problem with those other projects being brought under computing (Websites, software and Networks don't exist without computers), but just because there hasn't been any discussion from those projects (or at computing) does not create "Unanimous support". I for one think that there is not enough support shown ant any of those links to combine the templates. I do see that you are contributing the vast majority of the discussion which makes it difficult to follow at best. I don't see any consensus that this proposal go forward, and nothing you have said refutes the points made in opposition above. Adam McCormick (talk) 16:13, 8 August 2008 (UTC)
I second the sentiments with regard to the non-threaded responses being hard to follow. --Cybercobra (talk) 18:50, 8 August 2008 (UTC)

Perhaps it would be better if WP:CompSci was completely divorced from WP:Computing, and instead got married to WP:Math? That way we could use the "integrated" mathematics banner for the WP:CompSci articles. This would more closely mirror how these disciplines are actually related in the "real world", where CompSci is academic, whereas Computing is a commercial activity. If there are overlapping articles, they could have two banners: one from WP:Math, and one from WP:Computing. This would make for a very clear, clean-cut distinction. linas (talk) 16:55, 8 August 2008 (UTC)

Eh, IMHO, CompSci should be its own separate thing. Certainly parts are mathy e.g. algorithm articles, but other parts, e.g. programming language articles, definitely stray from mathematical subjects but are within the domain of CompSci. But this is all tangential to the discussion at hand, which is merely about merging banners. Cybercobra (talk) 18:50, 8 August 2008 (UTC)
linas, that is only true for a subset of computer science and for the way it is taught in some universities. Computer Science is usually: (a) It's own department (b) Part of the science department (c) part of the engineering department (d) part of the mathematics department. I don't want to be really geeky, but... I did gather raw data on this in 2001 by going through every department at every unversity teaching computer science in the US as well as Australia. It was for a survey an unfortunately I only have the results online for those that responded - Australia [1] , and USA [2]. Beware small samples! (the original data as I said was from every department and collected via inspection of their websites) Oboler (talk) 05:07, 11 August 2008 (UTC)

Totals as of 19-Aug-2008

7 Oppose
5 Support
1 Weak Support

Johnl1479 16:54, 19 August 2008 (UTC)

Support/Opposes comments copied to below poll data.The user may shift to appropriate vote if I am wrong in reading your comments. -- Tinu Cherian - 07:22, 20 August 2008 (UTC)


  1. TinuCherian
  2. Chet B. Long
  3. Sayed Mohammad Faiz Haider Rizvi
  4. Rursus
  5. Zawersh
  6. Oboler
  7. Diego
  8. Jiuguang
  9. MattOates (Ulti)

Weak Support

  1. ZeWrestler


  1. Adam McCormick
  2. linas
  3. Cybercobra
  4. Johnl1479
  5. Iknowyourider
  6. SusanLesch

Closure of the Proposal : As the person who made this proposal , I am withdrawing this proposal for WP:COMP SC. Altough there is a greater support for the Intergated banner , I dont believe there is a consensus for the integrated banner migration for WP:Comp. Sc. Altough there is some pointy and ownership issues in some of the oppose reasons, I respect your valuable opinions. Having said that, we have done this integration successfully for other descendant projects like WP:SOFTWARE , WP:Comp Networking etc. Should anyone feel this proposal is still possible with consensus among the project members , this discussion may be opened anytime. Thanks for your time and valuable comments. -- Tinu Cherian - 11:59, 9 September 2008 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Network effects

I've just tagged Network effect, Metcalfe's law and Reed's law for WikiProject Economics. I'm guessing someone might want to tag them for this project as well. CRETOG8(t/c) 05:19, 30 August 2008 (UTC)

Wikipedia 0.7 articles have been selected for Computer science

Wikipedia 0.7 is a collection of English Wikipedia articles due to be released on DVD, and available for free download, later this year. The Wikipedia:Version 1.0 Editorial Team has made an automated selection of articles for Version 0.7.

We would like to ask you to review the articles selected from this project. These were chosen from the articles with this project's talk page tag, based on the rated importance and quality. If there are any specific articles that should be removed, please let us know at Wikipedia talk:Version 0.7. You can also nominate additional articles for release, following the procedure at Wikipedia:Release Version Nominations.

A list of selected articles with cleanup tags, sorted by project, is available. The list is automatically updated each hour when it is loaded. Please try to fix any urgent problems in the selected articles. A team of copyeditors has agreed to help with copyediting requests, although you should try to fix simple issues on your own if possible.

We would also appreciate your help in identifying the version of each article that you think we should use, to help avoid vandalism or POV issues. These versions can be recorded at this project's subpage of User:SelectionBot/0.7. We are planning to release the selection for the holiday season, so we ask you to select the revisions before October 20. At that time, we will use an automatic process to identify which version of each article to release, if no version has been manually selected. Thanks! For the Wikipedia 1.0 Editorial team, SelectionBot 23:02, 15 September 2008 (UTC)


If Civilized People Ever Send Missionaries To The Computer Scientists To Inform Them For The First Time That Lower [hyphen omitted] Case Initial Letters Exist And That Hyphens Exist, Would The Missionaries Be Killed Immediately Or Would They Be Allowed Any Last Words Before They Died? Michael Hardy (talk) 13:54, 25 September 2008 (UTC)

No last words: they'd be strung up high, next to the Schemers hung in dynamic-wind nooses -- sad old souls who'd used their last escape continuation. Tragic, really. (I hope you can figure out for yourself why hyphens are disallowed inside of identifiers in infix languages. As for initial lower-case characters, you betray your innocence: how could you have camelCase or posix_style without them?) --mgreenbe (talk) 15:10, 25 September 2008 (UTC)

Well today I moved Crossing [no hyphen here] Based Interfaces (plural) to crossing-based interface (lower-case initials, hyphen included, singular). I've done things like that before. Am I in danger? Michael Hardy (talk) 18:19, 25 September 2008 (UTC)

I've done tons of those, as well as tons of putting en dashes in things like Bose–Einstein condensate, and only rarely do I get any feedback or questioning. Dicklyon (talk) 18:31, 25 September 2008 (UTC)

So apparently they don't kill the missionaries; they just ignore them. I keep finding computer science articles called Something Based Something with no hyphen and all capitals, or Something Based Somethings—plural in disregard of WP:MOS's preference for singular. I think they must be taught to write that way in computer science courses. Michael Hardy (talk) 21:47, 25 September 2008 (UTC)

I have not seen a disproportionate amount of these problems in CS; it's pervasive. Dicklyon (talk) 02:20, 26 September 2008 (UTC)

It really does happen far more frequently in computer science than in most fields. Also in business management articles and a few other topics. Michael Hardy (talk) 21:13, 1 October 2008 (UTC)

Hmm, I haven't noticed the phenomenon, but I once had to use the German version of Microsoft PowerPoint: The default setting is To Capitalise Every F*** Word, Even Though Nobody Ever Does This In German. It strikes me that the kind of article that you mentioned are exactly those that I would expect to have an unusally high percentage of PowerPoint users as editors. --Hans Adler (talk) 10:39, 2 October 2008 (UTC)

"Dubious reference" at Graph isomorphism

See Wikipedia:ANI#.22dubious_reference_....22.3F and the talk page of the article. The controversial content is about the ease/difficulty of computing isomorphism for regular graphs, so I thought this would be a good place to ask for help. VG 23:51, 30 September 2008 (UTC)

Lambda calculus and friends

So there's lambda calculus, but there's also pages for untyped and typed versions, as well as simply typed and polymorphic...and and and. I would not suggest that we just have a single, big PTS page and give the different formation rules, but how do people feel about abstracting out some of the description? I see two options:

  1. separate articles on syntax, operational semantics, and simple typing for the lambda calculus
    System F and the Calculus of Constructions can simply refer to those as necessary
  2. one big article on lambda calculus (syntax, dynamic and static semantics)
    extensions can refer to sections in the lambda calculus page

Any bias either way? Is there a protocol for levels of abstraction in mathematical articles I don't know about? Do we want an infobox? (Various common properties: PTS rules in the lambda cube, confluence, strong normalization, seminal paper, etc.) If no one cares, I'm happy to be bold... --mgreenbe (talk) 13:02, 1 October 2008 (UTC)

Untyped lambda calculus thankfully redirects to lambda calculus, which is what it should do. I see no problem having simply typed lambda calculus, System F, and CoC as separate articles. See the Lambda_cube article, which unfortunately lacks the obligatory picture. Adding a pictorial infobox for those calculi articles in the Lambda cube may be useful, but it's a fair bit of work. The article on general Typed lambda calculus is a bit difficult to follow, but stands on its own since it generalizes Lambda_cube. So, I'm not sure I understand your proposals. VG 14:58, 1 October 2008 (UTC)
Ah...didn't see the redirect. So it's not as bad as I thought. But I mean that each of these articles, in order to be readable to non-experts, should include the syntax, semantics, and appropriate typing rules. I think the lambda cube and pure type system approaches are easy ways to understand the whole...after you've understood them. From a theoretical perspective, a single page on PTS with a discussion of various rules would suffice, but that's not useful to most encyclopedia readers. Likewise, it's important to have pages for individual points in the lambda cube.
Concretely, I was thinking we could try to unify the style and treatment of the lambda calculus across multiple articles, as there's a lot of redundancy at present. --mgreenbe (talk) 19:59, 1 October 2008 (UTC)

Difference between this WikiProject and Wikipedia:WikiProject_Computing?

I this WikiProject supposed to focus more on the theoretical side and WikiProject Computing on the hardware side? In practice I see a lot of redundancies, especially having two assessments for most articles. Perhaps the assessment processes of the two projects should be unified... VG 14:34, 1 October 2008 (UTC)

Perhaps you havent see the the discussion above ? -- Tinu Cherian - 10:17, 9 October 2008 (UTC)
VG, this project is supposed to focus on computer science (i.e. the study and the science of the theoretical foundations of information and computation and their implementation and application in computer systems), while WP:Computing -- as the name suggests -- covers computing (i.e. "the activity of using and developing computer technology"). There is certainly some overlap between the two topic areas. And I suppose you could characterize the difference as focusing on "theory" vs. "hardware". However, my own preference is to view computing as focused on using computer technology (hardware, software, or a mix), and to view computer science as concerned with the fundamental properties of computation (which may have implications for computing, but also for biology, process planning, control systems design, and a host of other disciplines in which processes performing some kind of "computation" may be observed to exist). --Allan McInnes (talk) 20:52, 9 October 2008 (UTC)
Yeah, I agree with making some distinction, but does the perspective matter so much that two reviews are necessary for each article? VG 15:38, 8 November 2008 (UTC)

Ga Sweeps Reassessment of Functional Programming

Functional programming has been nominated for a good article reassessment. Articles are typically reviewed for one week. Please leave your comments and help us to return the article to good article quality. If concerns are not addressed during the review period, the good article status will be removed from the article. Reviewers' concerns are here. --Malleus Fatuorum (talk) 23:20, 6 November 2008 (UTC)

Where is this review taking place? I don't see it... VG 15:41, 8 November 2008 (UTC)
Never mind, I found it. VG 15:43, 8 November 2008 (UTC)

Scott Aaronson's theoretical computer science article improvement project

Scott Aaronson has launched a small project to improve Wikipedia's coverage of theoretical computer science topics: see this blog entry.

Here's a list of the topics on which he is soliciting contributions:

—Preceding unsigned comment added by The Anome (talkcontribs)

Literacy issues

Some People Say It's Not Completely True That People In The Computer Science Field Don't Know That Lower [hyphen omitted] Case Initial Letters Exist. I Just Found This:

The term Customer Edge (CE) refers to the Router at the customer premises which is connected to the Provider Edge of a service provider IP/MPLS network.

Now Supposing We Grant That "Customer Edge" Requires Capital Initial Letters Because The Gods Of Computer Science Require That Particular Form Of Worship. That Still Leaves Not Only The Question Of Why Most Computer Science Articles Use Capital Letters In Section Headings In Disregard Of WP:MOS, But Also This: Observe The Word After The Phrase "refers to the".

Maybe The Pharmaceutical Industry Will Some Day Introduce A Drug To Treat This Condition. Michael Hardy (talk) 17:31, 18 December 2008 (UTC)


MustBeABadHabbitThatComesFromUsingTooMuchCamelCase. — xDanielx T/C\R 21:54, 28 December 2008 (UTC)

"Permanent is sharp-P-complete" proposed for deletion

Please see the article Permanent is sharp-P-complete and the deletion discussion Wikipedia:Articles for deletion/Permanent is sharp-P-complete.

A number of discussants feel that if the article were re-written to be about the theorem rather than about the proof then it could be saved. Michael Hardy (talk) 12:19, 19 December 2008 (UTC)

Artificial Intelligence issues branching between WikiProjects

Hi CompSci people, I am an active member of WikiProject Robotics and as it turns out, we both have been trying to cover artificial intelligence in our respective WikiProjects! I found out recently that Wikipedia:WikiProject Artificial intelligence redirects here. I'd like to see what your thoughts are in regards to setting line if you will what types of AI should this WikiProject be covering and what types of articles WP:ROBO should focus on.

In other news, ANPR is up for Wikipedia:Featured article review/Automatic number plate recognition. Now this article currently is not a WP:WPCS article yet, but I would like some help rescuing this FA from being demoted. Any assistance would be helpful. Thanks. - Jameson L. Tai talkguestbookcontribs 05:46, 14 January 2009 (UTC)

I don't think we really need to define a "line" at all. WPCS also naturally overlaps with parts of the Mathematics Wikiproject, but it's never been necessary to define a "line" there. We've always been able to successfully collaborate on those articles that happen to fall inside the overlap (which is ill-defined at best anyway). We tend to leave it up to individual project members to decide on a case-by-case basis whether they think a given article should be considered within the scope of the project. --Allan McInnes (talk) 21:33, 14 January 2009 (UTC)
Great! I thought as much. I guess my response would be - do the members of this WikiProject consider ANPR a part of your WikiProject?  :-) - Jameson L. Tai talkguestbookcontribs 09:17, 15 January 2009 (UTC)

LEGO Turing machine

IMHO very interesting "hardware implementation of a 'Turing machine'" constructed of LEGOs at Aarhus University by Mikkel Vester, Sean Geggie, Martin Have, and Anders Nissen
A blog about the project at . Also includes demonstration video. Video also available on YouTube.
I understand that hardware implementations of Turing machines are not "real" Turing machines, nevertheless I think that many people would find an article about them interesting. Hardware implementations of the Turing Machine ??
-- (talk) 00:36, 30 January 2009 (UTC)

Coordinators' working group

Hi! I'd like to draw your attention to the new WikiProject coordinators' working group, an effort to bring both official and unofficial WikiProject coordinators together so that the projects can more easily develop consensus and collaborate. This group has been created after discussion regarding possible changes to the A-Class review system, and that may be one of the first things discussed by interested coordinators.

All designated project coordinators are invited to join this working group. If your project hasn't formally designated any editors as coordinators, but you are someone who regularly deals with coordination tasks in the project, please feel free to join as well. — Delievered by §hepBot (Disable) on behalf of the WikiProject coordinators' working group at 05:11, 28 February 2009 (UTC)

GA Reassessment of Programming language

Programming language has been nominated for a good article reassessment. Articles are typically reviewed for one week. Please leave your comments and help us to return the article to good article quality. If concerns are not addressed during the review period, the good article status will be removed from the article. Reviewers' concerns are here. --Malleus Fatuorum 14:41, 3 March 2009 (UTC)

P=NP edits: Martin M. Musatov

Someone (probably Martin M. Musatov himself) has been disruptively editing Wikipedia articles with a purported solution (or something) of the P = NP problem, on articles such as: P = NP problem, P versus NP (newly created), Martin M. Musatov, and under many different accounts and addresses, including MartinMusatov (blocked),,, Libertyrights, and probably more accounts in the future. (The person has also been doing this outside Wikipedia, leaving comments on CS blogs etc.) I don't know the right way to deal with this; could someone look into the duplicate accounts? --Shreevatsa (talk) 03:25, 6 March 2009 (UTC)

I've seen this guy around too, and warned him at least once. I suggest reporting this at Wikipedia:Sockpuppet investigations, to start. Dcoetzee 03:29, 6 March 2009 (UTC)

This is a ridiculous unsubstantive claim. To what to you have I to accuse? Answer me this then you may speak. Until then you will remain silent and obedient like a dog. —Preceding unsigned comment added by Anonymousacademic (talkcontribs) 12:43, 10 April 2009 (UTC)

It should be noted Dcoetzee has been documented as operating a bot wrecklessly to revert his disputed edits automatically when contested [3]. (talk) 03:03, 29 November 2012 (UTC)

Looking for watchers for active queue management

The article Blue (queue management algorithm) had outstanding vandalism for 3 days, probably because of a small number of watchers. Please add it if interested. Dcoetzee 05:26, 9 March 2009 (UTC)

Article alerts

This is a notice to let you know about Article alerts, a fully-automated subscription-based news delivery system designed to notify WikiProjects and Taskforces when articles are entering Articles for deletion, Requests for comment, Peer review and other workflows (full list). The reports are updated on a daily basis, and provide brief summaries of what happened, with relevant links to discussion or results when possible. A certain degree of customization is available; WikiProjects and Taskforces can choose which workflows to include, have individual reports generated for each workflow, have deletion discussion transcluded on the reports, and so on. An example of a customized report can be found here.

If you are already subscribed to Article Alerts, it is now easier to report bugs and request new features. We are also in the process of implementing a "news system", which would let projects know about ongoing discussions on a wikipedia-wide level, and other things of interest. The developers also note that some subscribing WikiProjects and Taskforces use the display=none parameter, but forget to give a link to their alert page. Your alert page should be located at "Wikipedia:PROJECT-OR-TASKFORCE-HOMEPAGE/Article alerts". Questions and feedback should be left at Wikipedia talk:Article alerts.

Message sent by User:Addbot to all active wiki projects per request, Comments on the message and bot are welcome here.

Thanks. — Headbomb {ταλκκοντριβς – WP Physics} 08:59, 15 March, 2009 (UTC)

Help with data structure template

Hi, I just created {{Data structures}} to aid with navigation in related articles. Please help populate the navbox with appropriate entries. I am going through Category:Data structures and List of data structures (which you can also help with) but now would be a good time to mention otherwise "hidden" topics. Ham Pastrami (talk) 04:57, 20 March 2009 (UTC)

I noticed this is still in its early stages, so I linked List of data structures in its footer. I hope you think that is useful.
Meanwhile, I created a new navigation box myself, for inter-process communication, at {{IPC}}. It needs review and discussion at Template talk:IPC.
--Hroðulf (or Hrothulf) (Talk) 19:47, 9 May 2009 (UTC)

Pbit nominated for deletion

Please consider expressing your opinion in discussion about this article - Wikipedia:Articles for deletion/Pbit. I think this nomination need more expert point of view.Mathel (talk) 20:12, 5 April 2009 (UTC)

Long lists of external links

Many algorithm articles seem to contain extremely long lists of external links. I think this is against WP:EL: "long lists of links are not acceptable" + other points in the guideline. Often the links seem to be to sites which I normally wouldn't consider reliable sources. Links to Java applets, illustrations, etc. are completely unnecessary in my opinion. Most of the sites containing these would never pass WP:RS. I think we should cut down the external link sections to the bare minimum. Links to scientific publications should be strongly preferred over anything else. Offliner (talk) 04:07, 7 April 2009 (UTC)

I think some amount of implementation pointers can be useful, but I agree that we tend to have too many of them. If you find some of these and don't have time to clean them out yourself or want a second opinion first, {{linkfarm}} is an appropriate tag to use. But I don't think links to scientific publications should be in the external links section: if they're good enough to include they should be good enough to use as actual references rather than links. —David Eppstein (talk) 04:17, 7 April 2009 (UTC)
What I think should definitely be removed outright without a question: 1) links to personal blogs, 2) links to personal websites of non-notable persons, 3) links to implementations by non-notable persons. There seems to be a lot of linking to source code written by "some unknown guy in the Internet." According to WP:EL the linked sites should be reliable: (Links normally to be avoided:) Any site that misleads the reader by use of factually inaccurate material or unverifiable research. See Reliable sources for explanations of the terms "factually inaccurate material" or "unverifiable research" Many sites/projects linked to are of completely unknown reliability. Sure, having links to various implementations is useful, but is it encyclopedic? Why not just let the reader google up such materials himself? Offliner (talk) 22:23, 7 April 2009 (UTC)
Since there are so many blogs and personal sites out there, it's a service to the encyclopedia reader to point them to a handful of such sites that scientifically/mathematically knowledgeable editors have reviewed and deemed to be interesting/informative. Twenty or thirty links would be a "link farm"; a dozen are not. PetersV       TALK 01:36, 10 April 2009 (UTC)
I have a Huffman coding recent spat in mind. PetersV       TALK 01:39, 10 April 2009 (UTC)
In most cases, links with useful content should have that content integrated into the article. The link should appear as a reference, where needed and not redundant. A list of links that simply repeat or add content that should be in the article is not optimal. The only links that should really remain are those that are 1)authoritative in some way, such as the person credited with the design of the algorithm, 2)exhaustive in such a way that it would be impractical to include all of the pertinent details (such as a research paper). It's been my experience that having more than two or three links means that the article is either incomplete, and needs to be expanded, or there's a lot of low-value links. A dozen links is fairly excessive. Ham Pastrami (talk) 10:40, 12 April 2009 (UTC)

Source code written by editors

I've noticed that many articles seem to contain source code that is written by Wikipedia editors. I feel that including code written by editors is completely against all Wikipedia guidelines, such as WP:NOR. One might argue, that source code is an illustration of the article subject, much like self-taken photographs or self-made SVGs that are widely used in WP. But I think that still does not excuse us from ignoring very basic Wikipedia guidelines. I'd say that the only case when we should include source code in articles is when we can directly copy it from a free reliable source.

This seems like a very important subject - has this been discussed before somewhere? Or maybe there is some kind of guideline for including source code that I'm unaware of? Offliner (talk) 22:31, 7 April 2009 (UTC)

Offliner asked me look at this as an outsider. I've looked at some of the articles in question, and they are for the most part unsourced. The articles are failing a core policy, that being of verifiability. Everything that appears in Wikipedia articles need to be published in a reliable source and cited that others can verify it. If it isn't sourced, it is valid for {{fact}} and ultimate removal if sources aren't forthcoming. If sources can't be found it constitutes original research, and that is most definitely not allowed. As this is obviously affecting a lot of articles by the looks of it, discussion at village pump may be in order to get wider input into what clearly looks like a problem. --Russavia Dialogue 22:51, 7 April 2009 (UTC)

Next we'll be outlawing articles that contain prose written by Wikipedia editors, I suppose, and only allowing Wikipedia articles to contain text that has already been published by a free reliable source? This is not intended purely as sarcasm: often code or pseudocode is the clearest way to describe an algorithm, and copying someone else's code is in most cases a copyright violation. So how do you expect us to proceed? —David Eppstein (talk) 22:52, 7 April 2009 (UTC)

I don't see any exception in WP:NOR, WP:V or WP:RS that would allow us to write source code ourselves and claim that it correctly implements the algorithm that is the subject of the article. I'm not sure what exactly we should do, that is why I'd like to see some discussion. But I'd say we need to do the obvious: give a ref for every piece of source code in Wikipedia, make sure that it is from a reliable source and that it is not a copyright violation. Offliner (talk) 23:02, 7 April 2009 (UTC)
I agree that it needs to be taken to a higher level (village pump). In some ways, it's more similar to creating an image (say, a map or a graph) for posting on Wikipedia. tedder (talk) 23:18, 7 April 2009 (UTC)
I posted on WP:VPM also: [4]. Offliner (talk) 23:42, 7 April 2009 (UTC)
I don't see any exception in those policies that lets us write prose ourselves, either. And yet we do anyway. How is it different to be writing in, say, Python, than in English? —David Eppstein (talk) 23:51, 7 April 2009 (UTC)
We are allowed to write prose ourselves if it contains the same information which is published in the cited reliable source. But as I have pointed out, most source code examples do not cite their sources at all. Writing Python is very different from writing English, I think. If you write a sentence in English, it is easy for anyone to check if it corresponds to what is said in the reliable source. For Python code, this is not the case. Also note, that including source code as an example for an algorithm amounts to making the claim "this code correctly implements the algorithm," which is OR if the code is written by an editor and no source is given for it. Offliner (talk) 23:59, 7 April 2009 (UTC)
Anyone who is fluent in English can read English prose and understand it. Anyone who is fluent in Python can read Python code and understand it. Perfect analogy. Funny that they're both called languages. Tparameter (talk) 10:10, 17 April 2009 (UTC)
It is preferable to include code or pseudocode from a reliable source. However, "real code" includes lots of distracting details that we don't need for exposition, and code from books is typically non-free and substantial enough to invalidate a fair use claim. Thus it makes perfect sense for editors to write their own code. This does have the unfortunate consequence that editors frequently introduce errors into code snippets. The analogy with prose is appropriate: a person can examine the pseudocode in a reliable source, compare it to the pseudocode/code in an article, and see that they implement the same algorithm. Dcoetzee 00:02, 8 April 2009 (UTC)
I can write an image in a markup language. Does that mean we need to have refs for every graph or map or image that has been created for Wikipedia? In any case, not everything needs to be sourced: WP:V says "Editors should provide a reliable source for quotations and for any material that is challenged or likely to be challenged, or the material may be removed." That makes me think a straightforward python program doesn't need to be cited. However, if it is challenged, we are back at the same position. tedder (talk) 00:03, 8 April 2009 (UTC)

(some replies below merged back from Wikipedia:Village_pump_(miscellaneous)#Source_code_written_by_editors)

We have long accepted this, along with simples examples in mathematical and scientific articles. Remember that WP:V only requires sources for things that are challenged or likely to be challenged. Simple, short examples are fine. The Bellman-Ford algorithm article has a lot of problems, but there are many other articles that are not problematic. — Carl (CBM · talk) 23:02, 7 April 2009 (UTC)
Most of the source code I've seen wouldn't qualify as a simple, short example. Also, what about WP:COS? "This policy does not prohibit editors with specialist knowledge from adding their knowledge to Wikipedia, but it does prohibit them from drawing on their personal knowledge without citing their sources." WP:NOT#HOWTO might also be relevant. Offliner (talk) 23:35, 7 April 2009 (UTC)
My opinion is that if it is on WP, it needs to have been published by a reliable source previous to its insertion, otherwise it is original research, regardless of whether it is likely to be challenged or not. That of course is just my opinion. Does fair use apply for code/calculations, given that this is an educational setting after all? --Russavia Dialogue 23:33, 7 April 2009 (UTC)
While there is often too much source code in articles, simple examples can often be helpful and don't violate policy. The fact that some piece of code performs a stated computation is a matter of mathematical fact. Given the algorithm or concept described (which should have references in the prose) and the definition of the language (which should be referenced in the linked page for the language) the example can be verified. This is not OR in the same way that "22.3/5 = 4.46" or "this sentence contains the word example" is not OR. However, many of the existing C examples are overly complicated for what they are trying to show. Using psuedocode is better in case of algorithms, or much shorter examples for illustrating other concepts, "this an example of a recursive lambda-term" for example. OrangeDog (talkedits) 23:46, 7 April 2009 (UTC)
The fact that some piece of code performs a stated computation is a matter of mathematical fact. Could be, but is it an obvious fact? If you think the code in Bellman-Ford algorithm is correct, could you provide us a sample mathematical proof? It might take a while to do that. It seems to me that you are implying that the burden of evidence does not lie on the editor who inserts the code. It seems to me that you are saying that anyone can write some code, insert it to an article claiming that it correctly implements the algorithm that is the subject of the article, without having to provide a source or any direct evidence for this claim, simply because "the fact that some piece of code performs a stated computation is a matter of mathematical fact." Offliner (talk) 00:24, 8 April 2009 (UTC)
Firstly, I think that C sample is overly complicated and unnecessary so I see no point in proving its correctness. I suppose another analogy would be to natural language translations (e.g. "Haben Sie noch etwas Geduld" means "Have you some more patience?"), except programming languages are much simpler than natural languages.
As I've written in Wikipedia talk:WikiProject Computer science, my position is that, as code snippets are used here, they are not significantly different from writing prose, or maybe more like writing chemical formulas or mathematical equations: they are a way of expressing ideas for other people to read, in a language that is more precise than English. We don't forbid people to write a mathematical formula unless that formula has already appeared in a reliable source. We don't forbid people to write an English sentence unless that sentence has already appeared in a reliable source (in fact, it's the opposite, we prefer not to plagiarize). By the same token we should not forbid people from writing code snippets that do not come from other sources. In the specific example given, Bellman-Ford algorithm, I would keep the pseudocode but delete the longer C implementation, not because it's original research but because it's long and redundant and doesn't add any useful content to the article for the human reader. That is, it's not a WP:OR issue but a WP:NOT issue: Wikipedia is not a code repository, so if the algorithm has already been clearly described to a human reader in pseudocode then there's no point in keeping the C code. —David Eppstein (talk) 23:55, 7 April 2009 (UTC)
I removed the C source code from the Bellman-Ford algorithm page. Some other people may want to put that page on their watchlist. — Carl (CBM · talk) 00:25, 8 April 2009 (UTC)

As examples of short code snippets that are short and not hard to verify by eyes, see Halting problem, Smn theorem, and Kleene's recursion theorem. One could complain about the latter two using lisp, but not about the code being original or hard to check. — Carl (CBM · talk) 00:28, 8 April 2009 (UTC)

What do you think of the code in Red-black tree? It is long, detailed and hard to check. One of the cited references (Cormen) has the full pseudocode, but the code in the article is C, and it is probably written by an editor on the basis of the textbook pseudocode. Offliner (talk) 00:38, 8 April 2009 (UTC)
The final piece, about tail recursion loop optimization, should be left out; it's quite long and on a topic somewhat tangential to the overall article. The other pieces are individually quite short, and would be easy to verify from any book that explains the algorithm. Moreover, I do not think that the article would become any clearer to read if those short code fragments were replaced by English alone. So I would say we should remove the last big block and leave the others. — Carl (CBM · talk) 00:42, 8 April 2009 (UTC)
Those snippets are mine, and I agree (I did not write the large one). The code is based in a straightforward manner on the referenced lecture notes, and in fact was written to roughly parallel those notes in structure. At the time I wrote it in C mainly so that I could verify its correctness with testing, but it may have become stale due to incorrect edits since then. Dcoetzee 01:41, 8 April 2009 (UTC)

By the way, in connection with this discussion, I yesterday removed a large amount of source code from breadth first search. My feeling (as expressed above) is that source code can be an effective way of communicating an algorithm, and that (if it follows a published algorithm) it isn't original research, but that there's no good reason to have multiple implementations of the same algorithm in different languages. In the BFS case, I felt that the algorithm itself was more clearly expressed by the pseudocode already existing in the article than by any of the implementations — the bulk of the code in each implementation involved boilerplate code that had nothing to do with the specific algorithm — so I left only the pseudocode and deleted the other implementations.

There is also an argument for using suitable languages. Code that demonstrates data structures (like a red-black tree) should probably use an object-oriented language rather than C. It will usually be simpler to write and easier to validate. C is horrible for correctness with all its nasty direct pointer and memory manipulations. For more theoretical concepts, a functional language or a flavour of lambda calculus would often be more suitable. OrangeDog (talkedits) 18:26, 8 April 2009 (UTC)

Umm, folks, we prefer code written by WP editors because it is then GFDL licensed as opposed to taking code samples from books or periodicals and opening ourselves to legal action over misuse of intellectual property (IP). And the idea that WP editor code is WP:OR is so totally barking up the wrong tree. I deal with code and associated IP every day. People here are worried about legal implications of WP:BLP? That's nothing compared to the legal implications of abusing WP:CLP (Code of a Living Person). PetersV       TALK 01:46, 10 April 2009 (UTC)

Based on the above discussion, I think the Python implementation code in Dijkstra's algorithm is unnecessary (the pseudocode should be enough), too long and too error-prone. However, some seem to object to the removal: [5]. What do others think? Offliner (talk) 09:40, 12 April 2009 (UTC)

It's an interesting point, but I'd be more concerned about the nature of the content rather than the specifics of its correctness. Simple code samples that illustrate a concept are not terribly different from constructing prose, as others have said. Large code samples that contain full implementations of a complex algorithm, on the other hand, probably shouldn't even appear in the article. Wikipedia isn't a code repository. I think code samples should be limited to illustrating language syntax and semantics (where they are actually necessary for illustration), not to provide working implementations of some concept (which is basically pasting source code into an article). Ham Pastrami (talk) 11:00, 12 April 2009 (UTC)

I agree that the Python code at Dijkstra's algorithm could be removed. It's redundant to the code above it, and in a section entirely on its own with no prose. Code, like mathematical equations, should be used in small pieces to support the text around it. — Carl (CBM · talk) 12:36, 12 April 2009 (UTC)
I also agree in this case, and just removed it. Again. (There's a bit of an edit war going on in this case.) —David Eppstein (talk) 14:53, 12 April 2009 (UTC)
This topic has come up here before. I remember there being quite a bit of discussion, but the only remnant Ive been able to dig up is at Wikipedia talk:WikiProject Computer science/Manual of style (computer science). As I recall, the general consensus was to try to minimize code samples (ideally using the just to explain language syntax). The rationale was that by sticking to pseudocode (preferably referenced pseudocode) we'd avoid issues with original research, avoid people bogging the articles down with lengthy and language-specific implementation details, and minimize the proliferation of code additions that seem to happen whenever someone feels that their pet language isn't adequately represented. Take a look back thorugh the archives of the Quicksort article to see what I mean - the article was dominated by implementations in an incredible number of different languages. Also, as you rightly point out, Wikipedia is not a code repository. --Allan McInnes (talk) 01:17, 17 April 2009 (UTC)

Computer virus AfD: Wikipedia:Articles_for_deletion/Win32_Swizzor

FYI. 14:49, 10 April 2009 (UTC)

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 X_1, \ldots, X_n with expectation bounded by \mu, P\left(\sum X_i - \mathbf{E}\left[\sum X_i\right] < \delta \mu\right) \geq \min\left((1+\delta)^{-1}\delta, 1/13\right) 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 .

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: . Out of these, one probability theory paper improves the inequality (showing 1/8 instead of 1/13 when \delta=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)

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)

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)

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 (talkcontrib) 06:13, 20 May 2009 (UTC)

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)

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)

Consensus Please

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)


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

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)

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)

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)

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)

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:

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)

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)

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)

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 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)

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)

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)

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 Category: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)

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 [7] (about 600 gbooks hits) but pales compared to "computational complexity" [8] (about 5000 gbook hits) or "analysis of algorithms (1200 hits) and about on par with "program optimization" [9]. 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.

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. [10] [11]. See also what W. Gasarch thinks of this area. Pcap ping 16:10, 2 September 2009 (UTC)

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)

Symbolic analysis for deletion

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

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)

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)

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)

Boolean algebra (dab)

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

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 [12]). 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)

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)

Popular pages

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


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)

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:

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)

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?

Theoretical computer science.svg

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)

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)

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)

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 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)

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)

Merging "X problem" to "X"

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

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

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:

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)

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)


A quick status update:

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

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)

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)
I've added a merge template to each of those pages, pointing here for discussion. Let's see if anyone has any better ideas or objections to this proposal. --Robin (talk) 00:00, 30 December 2009 (UTC)
Since most of the functions discussed work equally well for space complexity, perhaps we should let the new article be called "time and space complexity"? --Robin (talk) 16:36, 31 December 2009 (UTC)
I'm not sure if that'd be a good idea. Currently we have several articles on "this-and-that time" and hardly any articles on "this-and-that space". Perhaps we should stick to the original plan and create an article on time complexity first and see what it looks like. We can create another article on space complexity later (or rename time complexity to time and space complexity). — Miym (talk) 17:38, 31 December 2009 (UTC)
OK, the only reason I suggested space is that I ran across this article on polylogarithmic space. Maybe that article is just about functions that are polylogarithmic, but it seems like a CS article. Anyway, let's go ahead with time complexity first. --Robin (talk) 17:55, 31 December 2009 (UTC)
It seems that even though the article Polylogarithmic mentions memory usage, it doesn't say anything non-trivial that is really specific to space complexity. I think we can explain polylogarithmic time in time complexity, possibly re-using some material from Polylogarithmic. We can then redirect polylogarithmic time to time complexity. — Miym (talk) 18:05, 31 December 2009 (UTC)

I've gone ahead and created time complexity and merged most of the articles I mentioned. The article isn't in great shape now, but hopefully over the new few days it should become a complete and informative article. Please feel free to add more content, or merge pages I've missed out. Any help in editing is greatly appreciated. --Robin (talk) 05:09, 10 January 2010 (UTC)

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)
Theory of computing is a well respected journal, has a high standard of articles, and their board of editors includes a very large fraction of all the big names in theory, from Aaronson to Yao. IMHO, the fact that TOC does not pass WP:Notability (academic journals) is a point against WP:Notability (academic journals), not TOC. I now looked up WP:Notability (academic journals), which appears to be only a proposed guideline, which several editors do not support. --Robin (talk) 00:16, 30 December 2009 (UTC)
I really doubt this does not pass WP:Notability (academic journals), so to use it as an argument against that guideline is rather moot. If it's considered reliable and influential, it passes criterion 1. If it's frequently cited, then it passes criterion 2. And if it has a significant history, it passes criterion 3. It definitely seems to pass #1 and #2. It's a bit young for #3, as long as any criteria is met, it's fine.
Anyway, I really didn't come here to talk about that guideline, I just wanted to point you to Wikipedia:WikiProject Academic Journals/Writing guide. I find it to be incredibly helpful to get a solid start. Headbomb {ταλκκοντριβς – WP Physics} 16:51, 30 January 2010 (UTC)


I feel the title is not the best one for this book (although I'm not entirely sure what exactly the book is about). Could someone give it a look? Headbomb {ταλκκοντριβς – WP Physics} 21:18, 8 January 2010 (UTC)

I'm not excited at all by the "book" feature on this wiki, but if you want to pursue that WP:CRYPT is best. Pcap ping 21:22, 8 January 2010 (UTC)
Alright thanks. Also why are you not all that excited about this feature? Headbomb {ταλκκοντριβς – WP Physics} 21:54, 8 January 2010 (UTC)
Because Wikipedia articles are written specifically with WP:NOTTEXTBOOK in mind. Reading a series of articles here isn't going to be a substitute for a real book on a topic. Pcap ping 22:26, 8 January 2010 (UTC)
Well they are obviously not replacements for text books, but they do make excellent "encyclopedic overviews" of a topic (which can be read offline). Take for example Book:Hydrogen, Book:Frédéric Chopin, or Book:Derfflinger class battlecruisers. But its true that some topics do make better books than others. Headbomb {ταλκκοντριβς – WP Physics} 23:04, 8 January 2010 (UTC)

Names of exponential time complexity classes

I believe that the classes for exponential time, non-deterministic exponential time and double exponential time are more commonly known as EXP, NEXP and EEXP, instead of EXPTIME, NEXPTIME and 2-EXPTIME as used on Wikipedia. As it is the more common name, I would like to rename the articles to reflect this. Does anyone object to this? --Robin (talk) 23:44, 10 January 2010 (UTC)

By gut feeling tells me that we should stick here with the notational conventions used in the complexity zoo. Hermel (talk) 23:14, 21 January 2010 (UTC)
Indeed, the names I suggested are used on the Zoo and elsewhere. --Robin (talk) 21:08, 28 January 2010 (UTC)


Is anyone familiar with recent trends in AI here? This project doesn't seem particularly notable to me. I left a merge proposal there like two weeks ago, but obviously the pages don't get much editor traffic (no replies so far). Pcap ping 20:13, 11 January 2010 (UTC)

Unref'd CS BLPs in danger of immediate deletion thanks to ArbCom

Nick Pippenger - Ken Forbus - Martin Newell (computer scientist) - David Moon - Judith Donath - Bill Griswold - Srinivasan Keshav - Laszlo Belady - Ian Watson (scientist) - Simon Cozens - Jim Kurose - Nikolai Bezroukov - Stephen J. Mellor - Birger Møller-Pedersen - Alan Harshman - Kevin Lenzo - Ali Jafari - Nikolay Brusentsov - Jack Cole (scientist) - John Day (computer scientist) - Tadao Takaoka - Brian Fox

This list was generated by User:CBM. Please remove them from the list as you fix them. Pcap ping 21:46, 21 January 2010 (UTC)

I knew that looked too short to be the full list. Results by catscan follow. Note: don't panic if you see no entries struck; it's because the list has been recently regenerated, not be cause no progress is being made. See further discussion below the list itself.

Manually found:

  • Manuel Blum: not tagged, but only has links to his home page(s); I've seen aggressive admins prod articles like this.

Pcap ping 01:53, 23 January 2010 (UTC)

WP 1.0 bot announcement

This message is being sent to each WikiProject that participates in the WP 1.0 assessment system. On Saturday, January 23, 2010, the WP 1.0 bot will be upgraded. Your project does not need to take any action, but the appearance of your project's summary table will change. The upgrade will make many new, optional features available to all WikiProjects. Additional information is available at the WP 1.0 project homepage. — Carl (CBM · talk) 03:10, 22 January 2010 (UTC)

Assessment for Aspect weaver

When someone gets a chance, would they mind completing the assessment of aspect weaver? I'd do it myself but I think that's a bit of a conflict of interest, as I'm both the creator of the article and working on pulling it to GA status. It's not there yet, but I was hoping for an interim review. (Any suggestions would be most appreciated, as well.) On that note, is there any kind of mechanism with which to syntax highlight AspectJ code? I've been using <source lang="java"> for now since it's the closest match, but an appropriate highlight for aspect-specific keywords would be nice. --Shirik (Questions or Comments?) 08:24, 23 January 2010 (UTC)

Proposal at Wikipedia talk:Technical terms and definitions

I have made a proposal for formatting of computer science-related articles at Wikipedia talk:Technical terms and definitions. Based on a recent peer review, it seems there is no formal guideline for this, and I think this will help solidify what I think is a logical and standard formatting guideline for computer science-related articles. Please check it out at Wikipedia talk:Technical terms and definitions and offer your comments. Thanks! --Shirik (Questions or Comments?) 19:32, 29 January 2010 (UTC)

Criteria for "Comparison of ..." software articles

I know this is somewhat off-topic here, but this is where the cool heads lurk :-) I've started a RfC on my proposal for dealing with one of these articles, where the discussion has been particularly heated. My proposal is not specific to one kind of software, so hopefully the result of the discussion can be used as a precedent for all similar articles. Please participate at Talk:Comparison of Internet Relay Chat clients#A way forward. Pcap ping 15:10, 30 January 2010 (UTC)

Book:Datastructures vs. Book:Data structures

These obviously overlap with one another. Which should be merged into which (or is one completely redundant with the other)? Pcap suggested to "...merge, then delete Book:Datastructures, which is less organized and uses a non-standard name". I would rather have someone knowledgeable perform the merge than me however. Headbomb {ταλκκοντριβς – WP Physics} 16:44, 30 January 2010 (UTC)

I did the merge now. Andreas Kaufmann (talk) 08:45, 13 February 2010 (UTC)
Excellent! Thanks a bunch. Headbomb {ταλκκοντριβς – WP Physics} 12:38, 13 February 2010 (UTC)

AfDs of interest

Dinero (cache simulator) (was kept). By the way, Mark D. Hill certainly qualifies for a bio per WP:PROF; [15] [16] Pcap ping 03:41, 6 February 2010 (UTC)

Fabrik (software) (was kept) some visual programming experiment in Smalltalk that has over 100 citations. Pcap ping 08:02, 6 February 2010 (UTC)

Setrag Khoshafian (was deleted), a object-oriented database researcher, former faculty, moved to industry, hard to find a page about him. Also, his adviser (I guess) Patrick Valduriez deserves a bio with h-index of 39. [17]. Worked in databases and published o few books too. Pcap ping 10:07, 17 February 2010 (UTC)


Unlike 2-satisfiability, which is a pretty decent article, we don't have an article on 3-satisfiability. It redirects to the general problem, which only has a few lines about it. But what we do have are several distributed articles about variations of the problem, such as One-in-three 3SAT, MAX-3SAT, (SAT, ε-UNSAT) (one of the worst titles ever.. who has a key on their keyboard labeled "ε"?!), and MAX-3SAT(13). I would like to suggest all of these be merged to 3-satisfiability, and let the main article on the Boolean satisfiability problem have a WP:SUMMARY style section on 3SAT. The decision and optimization versions of 3-satisfiability are important enough to have more than enough material to fill one article. --Robin (talk) 23:13, 31 December 2009 (UTC)

I've put some merge templates on the relevant pages. In short, I'm proposing that 3SAT related articles be merged with a newly created page on 3-satisfiability. MAX-SAT related articles be merged with maximum satisfiability problem, and MAX-3SAT related articles be merged with MAX-3SAT. I'm proposing separate articles since combining MAX-3SAT and 3SAT might lead to a very long article. --Robin (talk) 16:54, 26 February 2010 (UTC)

Two articles - one subject

Hi, I know next to nothing about computer science so I'm asking here. Today I discovered the articles Grafting (algorithm) and Grafting (computer). Can someone who understands the topic take a look at the two and decide whether they're actually about the same thing, and if so, merge them? Thanks! +Angr 09:47, 10 February 2010 (UTC)

They are not the same, but I also don't think the algorithm in grafting (algorithm) is commonly known under the name "grafting" (if it even has any). —Ruud 14:49, 10 February 2010 (UTC)
Okay, well I'll leave it for you people to sort out! +Angr 15:25, 10 February 2010 (UTC)
Good job with the moves from "(computer)" to "(decision tree)". I was about to do the same. Perhaps Grafting (algorithm) should also be moved to Grafting (ordered tree)? Pcap ping 15:37, 10 February 2010 (UTC)
The article describes an algorithm for converting an ordered tree into a binary tree, copied from an algorithmic programming contest exercise called "tree grafting". But as I said, I'm not sure if this is the correct name or if that algorithm even needs its own page. —Ruud 15:46, 10 February 2010 (UTC)

Manual of style vote on source code in articles

A vote is being taken at Wikipedia talk:Manual of Style (mathematics)#Source code and pseudocode. Read carefully! This concerns the allowance of implementations of mathematical algorithms, and in particular moves to disallow implementations in proprietary languages such as MATLAB. LokiClock (talk) 00:09, 23 February 2010 (UTC)

Automate archiving?

Does anyone object to me setting up automatic archiving for this page using MiszaBot? Unless otherwise agreed, I would set it to archive threads that have been inactive for 30 days and keep ten threads.--Oneiros (talk) 18:00, 9 March 2010 (UTC)

Sounds good. --Robin (talk) 19:13, 9 March 2010 (UTC)
Good idea. Jwesley78 05:03, 10 March 2010 (UTC)
Yes check.svg Done--Oneiros (talk) 00:40, 11 March 2010 (UTC)

unreferenced BLP list

I've taken the liberty of adding the project to User:DASHBot/Wikiprojects. A page will be generated at Wikipedia:WikiProject Computer science/Unreferenced BLPs listing known unreferenced BLPs tagged under our wikiproject. --Cybercobra (talk) 20:59, 15 March 2010 (UTC)

...And apparently we're clean! (probably as result of the referencing campaign that used to be on this page but has since been archived) --Cybercobra (talk) 08:56, 16 March 2010 (UTC)

Theoretical Computer Science

I started a discussion here about removing 'Theoretical Computer Science" from the "Applied Mathematics" footer template. Please participate there. Thanks, Jwesley78 20:54, 18 March 2010 (UTC)

Tree structure

Should we decide of a style for all trees to be because at the moment they are very inconsistent. We could decide on some software to generate them, upload them as svg, and nominate the old ones for deletion. Software could be Graphviz perhaps. Also adding tree/graph structures to the manual of style after we decide could be nice. Wikiproject math could benefit from our experiences after this as well for their Graph theory articles. How does the community feel? Examples of inconsistencies include 2-3-4 tree, B-Tree, Red-black tree, Binary search tree, Hash tree, and more! --Chrismiceli (talk) 20:01, 20 March 2010 (UTC)

Software engineering?

Is software engineering really in the scope of WPCS? The project page claims so, however I've looked through quite a few software engineering-related pages and they aren't tagged. Honestly, computer science and software engineering are two quite different fields, and that's why they're two completely different majors. Sure, they have some overlap, but the terms are still distinct. For that reason, I proposed a new project on software engineering, though admittedly this was before I noticed on WPCS's project page that Category:Software engineering was included as relevant. I'm posting here to get a little more input from members of this project to see if (1) others agree that software engineering should be a separate project and (2) if any members of WPCS (like myself) would also be interested in joining that project were it to be created. Any input is most appreciated. --Shirik (Questions or Comments?) 20:01, 14 March 2010 (UTC)

I agree it's not within WPCS' scope and should be recategorized into the right WikiProject (either your proposed one or WikiProject Computing). --Cybercobra (talk) 20:06, 14 March 2010 (UTC)
As the project scope and goals section says (emph. mine):
The scope of the project includes all articles in the area of computer science, and may overlap with articles in areas such as mathematics, logic, and software engineering as well.
I think it'd be worthwhile to have a separate software engineering Wikiproject. But do keep in mind that some people consider software engineering to be a part of computer science. I don't personally hold that opinion, but the fact that some people do certainly indicates that there is potential for overlap between the two projects. I don't see that as a problem - there are also articles that overlap with WPMath, but they've never been a source of difficulty. --Allan McInnes (talk) 22:54, 14 March 2010 (UTC)
I agree with User:Cybercobra. --Robin (talk) 00:31, 15 March 2010 (UTC)
Oh I'm not going to deny that if it's a separate project there would be some overlap. However the entirety of software engineering I don't believe is in CS's scope, but that's what the project page seems to claim right now. For example, I don't consider requirements engineering part of computer science, however I do consider revision control as relevant to both. --Shirik (Questions or Comments?) 00:37, 15 March 2010 (UTC)
I really can't see how you're interpreting the current project page as claiming ownership of all SE articles. As I pointed out above, the "scope and goals" statement specifically says that there "may be some overlap" with SE, not that SE falls entirely within the scope of WPCS. The category list you're referring to is labelled "relevant categories", not "categories over which we claim sole dominion", or even "categories that contain only articles within the scope of this project". Note that the same list also contains Category:Computer engineering - like SE, an area of overlap rather than containment. I can't see anything else on the page (aside from a table of possibly useful stub templates) that even mentions SE. So what exactly is the problem here? --Allan McInnes (talk) 01:54, 15 March 2010 (UTC)
Please don't take offense; I wasn't trying to point out a problem. I was trying to ask for input to see if others agree with me and to see whether or not this proposal is a good idea. Nothing more. --Shirik (Questions or Comments?) 05:31, 15 March 2010 (UTC)
None taken. Just trying to understand your statement that "...the entirety of software engineering I don't believe is in CS's scope, but that's what the project page seems to claim right now...". If the project page needs to be modified, by all means let's do it. I just don't see how or where you're getting the interpretation you've claimed. --Allan McInnes (talk) 07:03, 15 March 2010 (UTC)
I admit that when I first viewed the project page with regards to this problem, the fact that Category:Software engineering was present in the "relevant categories" list led me to believe that the entirety of software engineering was covered by WPCS. However, if I had read more closely, the section above clearly states that it's not. I don't have a suggestion on a means through which to make that any more clear, so perhaps that point is moot. Regardless of the project page, though, I'm glad to see I'm not alone in the belief that software engineering is an independent topic (which does happen to overlap with CS). That was my primary purpose for posting here, to see if I was on the right track with that thought. --Shirik (Questions or Comments?) 16:07, 15 March 2010 (UTC)

PL/SE is the usual grouping in ACM and most comp sci depts, so it is considered part of computer science, for better or worse. Wikipedia is not the place to fix great wrongs, real or perceived. Pcap ping 14:48, 21 April 2010 (UTC)