Wikipedia talk:WikiProject Computer science/Archive 8

src: upload.wikimedia.org

Video Wikipedia talk:WikiProject Computer science/Archive 8

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)

Maps Wikipedia talk:WikiProject Computer science/Archive 8

Formal language

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

• 30 April
• 5 May (after my substantial rewrite)
• 25 May ("philosophy of logic" version)

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)

src: jech.bmj.com

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)

src: upload.wikimedia.org

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)

src: jech.bmj.com

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)

src: upload.wikimedia.org

"Cycle"

I wanted to find more info on "cycles" per The Jargon File v4.4.7 http://www.catb.org/~esr/jargon/html/C/cycle.html

"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 2³⁰ or 10⁹ 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)

src: jech.bmj.com

WikiProject:Software

src: upload.wikimedia.org

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)

src: upload.wikimedia.org

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)

src: jech.bmj.com

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)

src: upload.wikimedia.org

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)

src: jech.bmj.com

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)

src: upload.wikimedia.org

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)

src: upload.wikimedia.org

"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. -- 201.17.36.246 (talk) 02:14, 24 July 2008 (UTC)

src: upload.wikimedia.org

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)

src: jech.bmj.com

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

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)

Missionaries

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:

• Algorithmic game theory
• Algorithmic mechanism design
• Algorithms for matrix multiplication
• Arithmetic circuit complexity
• Average case complexity
• Circuit complexity
• Combinatorial auction
• Conductance (probability)
• Derandomization
• Discrete harmonic analysis
• Glauber dynamics
• Hardness of approximation
• List-decoding
• Locally decodable code
• Locally testable code
• Max-flow min-cut
• Metric embedding
• Model of computation
• Online algorithms
• Polynomial identity testing
• Polynomial-time hierarchy
• Price of anarchy
• Primal-dual approximation algorithm
• Probabilistically checkable proofs
• Property testing
• Propositional proof complexity
• Quantum computation
• Sketching algorithms
• Sparsest cut
• Streaming algorithms
• Unique games conjecture
• Worst case complexity
• Zero knowledge proof

--Preceding unsigned comment added by The Anome (talk o contribs)

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)

I DON'T UNDERSTAND. WHAT IS THE PROBLEM WITH THE ABOVE SENTENCE? IT READS PERFECTLY WELL TO ME. Raul654 (talk) 18:09, 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 ^{talk ? guestbook ? contribs} 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 ^{talk ? guestbook ? contribs} 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 http://legoofdoom.blogspot.com/2009/01/conclusion.html . 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 ??
-- 201.37.230.43 (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), 76.91.204.240, 76.79.179.55, 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 (talk o contribs) 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]. 99.65.75.17 (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 (talk o edits) 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 (talk o edits) 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 ${\displaystyle X_{1},\ldots ,X_{n}}$ with expectation bounded by ${\displaystyle \mu }$, ${\displaystyle 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 http://portal.acm.org/citation.cfm?id=1007352.1007443 .

1. Is the theorem and conjecture notable? The author is a well-respected researcher in complexity theory and the original article was presented at STOC 2004. The inequality is however not well-used. Google Schoolar reports 17 citations: http://scholar.google.com/scholar?cites=11347979119245205986 . Out of these, one probability theory paper improves the inequality (showing 1/8 instead of 1/13 when ${\displaystyle \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 (talk o contrib) 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)

Sys-Con

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:

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

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

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

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

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

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 fr.wiki where there's only one stub type -- I don't know if they've activated DynamicPageList there or not). But then Wikipedia, unlike Google, is mainly based on grunt work (that rewards people with promotions in a bureaucracy) instead of good software, so I'm not holding my breath I'll see any changes. Pcap ping 17:28, 23 August 2009 (UTC)

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

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

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]. --78.111.169.38 (talk) 10:11, 8 October 2009 (UTC)

Leadership?

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

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

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

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

Many overlapping analysis of algorithms articles

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

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

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

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

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

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

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

Can someone take a look at this?

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

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

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

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

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

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

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 http://stats.grok.se/en/ but the program is different, and includes the aggregate views from all redirects to each page. The stats are at Wikipedia:WikiProject Computer Science/Popular pages.

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

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:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

Status

A quick status update:

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

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

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)

Book:Encryption

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)

OpenCog

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.

• Ahmet_Yalç?nkaya: Turkish_roboticists; All_unreferenced_BLPs
• Alan_Harshman: Computer_scientist_stubs; All_unreferenced_BLPs (A7 speedy deletion)
• Alan_Mackworth: Artificial_intelligence_researchers, Fellows_of_the_American_Association_for_Artificial_Intelligence; All_unreferenced_BLPs
• Alec_Yasinsac: American_computer_scientists; All_unreferenced_BLPs
• Ali_Jafari: Computer_scientist_stubs; All_unreferenced_BLPs
• Andrew_B._Lippman: American_computer_scientists; All_unreferenced_BLPs
• Anind_Dey: Human-computer_interaction_researchers, Ubicomp_Researchers; All_unreferenced_BLPs
• Bill_Griswold: American_computer_scientists, Computer_scientist_stubs; All_unreferenced_BLPs
• Birger_Møller-Pedersen: Computer_scientist_stubs; All_unreferenced_BLPs
• Bob_Sproull: Computer_graphics_researchers, Computer_science_writers; All_unreferenced_BLPs
• C._Mohan: Indian_computer_scientists; All_unreferenced_BLPs
• Claude_Crépeau: Canadian_computer_scientists; All_unreferenced_BLPs
• Clyde_Kruskal: American_computer_scientists; All_unreferenced_BLPs
• Daniel_A._Reed_(computer_scientist): Scientific_computing_researchers; All_unreferenced_BLPs
• Daniel_Goossens: Artificial_intelligence_researchers; All_unreferenced_BLPs
• Daniel_Kottke: American_computer_scientists; All_unreferenced_BLPs
• David_B._Fogel: American_computer_scientists, Artificial_intelligence_researchers; All_unreferenced_BLPs
• David_Hanson_(robotics_designer): Roboticists; All_unreferenced_BLPs
• David_Moon: American_computer_scientists, Computer_scientist_stubs, Programming_language_researchers; All_unreferenced_BLPs
• David_P._Reed: American_computer_scientists; All_unreferenced_BLPs
• David_R._Wallace: American_computer_scientists; All_unreferenced_BLPs
• Diane_Pozefsky: American_computer_scientists, Computer_systems_researchers, Women_computer_scientists; All_unreferenced_BLPs
• Driss_Kettani: Canadian_computer_scientists, Moroccan_computer_scientists; All_unreferenced_BLPs
• Ed_Seidel: American_computer_scientists; All_unreferenced_BLPs
• Evgeniy_Gabrilovich: American_computer_scientists; All_unreferenced_BLPs
• Franz_Baader: German_computer_scientists; All_unreferenced_BLPs
• Harry_R._Lewis: American_computer_scientists, Theoretical_computer_scientists; All_unreferenced_BLPs
• Ian_Cullimore: Computer_hardware_researchers, English_computer_scientists; All_unreferenced_BLPs
• Inman_Harvey: British_computer_scientists; All_unreferenced_BLPs
• Jacek_Karpi?ski: Polish_computer_scientists; All_unreferenced_BLPs
• Jack_Cole_(scientist): Computer_scientist_stubs; All_unreferenced_BLPs
• James_H._Morris: American_computer_scientists; All_unreferenced_BLPs
• Jennifer_Mankoff: American_computer_scientists, Human-computer_interaction_researchers, Ubicomp_Researchers, Women_computer_scientists; All_unreferenced_BLPs
• Johanna_Moore: British_computer_scientists, Fellows_of_the_British_Computer_Society; All_unreferenced_BLPs
• John_M._McQuillan: American_computer_scientists; All_unreferenced_BLPs
• John_Wainwright_(computer_scientist): Programming_language_researchers; All_unreferenced_BLPs
• Josef_Kates: Canadian_computer_scientists; All_unreferenced_BLPs
• Joseph_Ó_Ruanaidh: Irish_computer_scientists; All_unreferenced_BLPs
• Judith_Donath: American_computer_scientists, Computer_scientist_stubs, Human-computer_interaction_researchers, Women_computer_scientists; All_unreferenced_BLPs
• Kevin_Jordan: Human-computer_interaction_researchers; All_unreferenced_BLPs
• Kevin_Lenzo: American_computer_scientists, Computational_linguistics_researchers, Computer_scientist_stubs; All_unreferenced_BLPs
• Larry_E._Smith: Artificial_intelligence_researchers; All_unreferenced_BLPs
• Les_Hatton: British_computer_scientists; All_unreferenced_BLPs
• Leslie_P._Kaelbling: Fellows_of_the_American_Association_for_Artificial_Intelligence, Roboticists; All_unreferenced_BLPs
• Li_Sanli: Chinese_computer_scientists, Teachers_of_computer_science; All_unreferenced_BLPs
• Mark_Grand: American_computer_scientists; All_unreferenced_BLPs
• Martin_Newell_(computer_scientist): American_computer_scientists, British_computer_scientists, Computer_graphics_researchers, Computer_scientist_stubs; All_unreferenced_BLPs
• Masaru_Tomita: Japanese_computer_scientists; All_unreferenced_BLPs
• Michael_Baumgardt: German_computer_scientists; All_unreferenced_BLPs
• Michael_Loren_Mauldin: American_computer_scientists; All_unreferenced_BLPs
• Nikolai_Bezroukov: Computer_scientist_stubs; All_unreferenced_BLPs
• Nikolay_Brusentsov: Computer_scientist_stubs, Russian_computer_scientists; All_unreferenced_BLPs
• Orkut_Büyükkökten: Turkish_computer_scientists; All_unreferenced_BLPs
• Paramjit_Singh: Indian_computer_scientists; All_unreferenced_BLPs
• Patrick_J._Hayes: British_computer_scientists, Fellows_of_the_American_Association_for_Artificial_Intelligence; All_unreferenced_BLPs
• Paul_Dourish: American_computer_scientists, British_computer_scientists, Human-computer_interaction_researchers, Scottish_computer_scientists, Ubicomp_Researchers; All_unreferenced_BLPs
• Per_Håkan_Sundell: Swedish_computer_scientists; All_unreferenced_BLPs
• Rashim_Mogha: Computer_science_writers; All_unreferenced_BLPs
• Richard_Fikes: Artificial_intelligence_researchers, Fellows_of_the_American_Association_for_Artificial_Intelligence; All_unreferenced_BLPs
• Richard_Vaughan_(robotics): Roboticists; All_unreferenced_BLPs
• Robert_Kinoshita: Roboticists; All_unreferenced_BLPs
• Roger_Moore_(computer_scientist): American_computer_scientists, Computer_systems_researchers, Programming_language_researchers; All_unreferenced_BLPs
• Simon_Cozens: Computer_scientist_stubs, Perl_writers; All_unreferenced_BLPs
• Somenath_Biswas: Indian_computer_scientists; All_unreferenced_BLPs
• Srinivasan_Keshav: American_computer_scientists, Canadian_computer_scientists, Computer_scientist_stubs, Computer_systems_researchers; All_unreferenced_BLPs
• Stanis?aw_Radziszowski: Polish_computer_scientists; All_unreferenced_BLPs
• Stephen_J._Mellor: British_computer_scientists, Computer_scientist_stubs; All_unreferenced_BLPs
• Steve_McConnell: Software_engineering_researchers; All_unreferenced_BLPs
• Steven_Muchnick: American_computer_scientists; All_unreferenced_BLPs
• Ted_Lewis_(computer_scientist): American_computer_scientists; All_unreferenced_BLPs
• Thomas_Binford: Computer_vision_researchers; All_unreferenced_BLPs
• Wally_Feurzeig: American_computer_scientists, Artificial_intelligence_researchers, Programming_language_researchers; All_unreferenced_BLPs
• Willy_Susilo: Australian_computer_scientists; All_unreferenced_BLPs
• Wolfgang_Nebel: German_computer_scientists; All_unreferenced_BLPs
• Yi_Mu_(academic): Australian_computer_scientists; All_unreferenced_BLPs

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)

• These should be easy to source, as they are Gödel Prize winners: Neil Immerman, Salil Vadhan, Silvio Micali. -- Miym (talk) 10:50, 23 January 2010 (UTC)
  • Yeah, we should prioritize, and expect to lose some at least temporarily given the pressing (soccer) of the BLP urgentists. (We don't seem to have an article on that notion) Pcap ping 11:25, 23 January 2010 (UTC)
    • I added some references to articles in Category:Fellows of the Association for Computing Machinery ? Category:All unreferenced BLPs, changed the tag from {{BLP unsourced}} to {{BLP refimprove}}, and struck them out in the above list. While at it, I noticed that there were some articles on ACM fellows, Turing award winners, etc. that were not counted as computer scientists in the above list. Hence I added Category:Fellows of the Association for Computing Machinery, Category:Turing Award laureates, Category:Gödel Prize laureates and Category:Knuth Prize laureates to Category:Computer scientists. It might be good to re-generate the list to include people from those categories as well. -- Miym (talk) 21:06, 23 January 2010 (UTC)
• Re-generated from [14]; no significant changes. -- Miym (talk) 22:06, 23 January 2010 (UTC)
  • Again, a bit shorter list now. -- Miym (talk) 21:41, 24 January 2010 (UTC)
• By the way, here is a CatScan list of computer scientists with {{BLP refimprove}}, if someone is interested in fixing those as well. -- Miym (talk) 22:32, 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)

3-satisfiability

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. Jwesley₇₈ 05:03, 10 March 2010 (UTC)

 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, Jwesley₇₈ 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)

Source of the article : Wikipedia