User talk:David Eppstein

Hi, and welcome to my User Talk page! For new discussions, I prefer you add your comments at the very bottom and use a section heading (e.g., by using the "New section" tab at the top of this page). I will respond on this page unless specifically requested otherwise.

DYK for Sint Servaasbrug

Orlady (talk) 12:03, 4 October 2011 (UTC)

CCI update

Wikipedia:Contributor copyright investigations/20110912 is now complete. Thank you for your assistance in the evaluation of this CCI.

Your help there is appreciated. :)--Moonriddengirl ^(talk) 12:15, 6 October 2011 (UTC)

Berger

A belated "nicely done.", glad to see I was wrong about the availability of more biographical information on the mathematician. Thanks! --joe decker^{talk to me} 17:08, 7 October 2011 (UTC)

Wikipedia:Articles for deletion/CVonline

Could you have a look at Wikipedia:Articles for deletion/CVonline? I'm not sure if it's exactly in your area, but this looks like a good faith effort to move an academic repository into Wikipedia, which has been somewhat prematurely derailed. Cheers, —Ruud 02:09, 11 October 2011 (UTC)

A barnstar for you!

	The Editor's Barnstar
	Great work on Michal Heiman. Drmies (talk) 18:05, 13 October 2011 (UTC)

Thanks!

Nira Radia

Hey, it seems that you just deleted Radia tapes controversy for Copyright vios. Can you please restore it to a version which I edited? There were no copyright violations in my version. This was a major event covered daily for months in all media in India and is part of one of the most influential events ever to happen in India. If you could have posted a notice I would have checked it out first. There must be something to be done other than deleting the entirety of the work. Please talk to me. Blue Rasberry (talk) 13:50, 15 October 2011 (UTC)

Ok, I've restored the last clean version prior to the point where the copyvios started. —David Eppstein (talk) 14:49, 15 October 2011 (UTC)

Thanks. I am happy with what you did. Related copyvio problems were in related articles, and the same solution was applied there. Please do not be so quick on the trigger next time! Blue Rasberry (talk) 17:35, 15 October 2011 (UTC)

Reverting of Dmcq on Prime number

I'm simply too embarrassed for words on my failure of logic on this one - apologies. I trust you'll understand the erasure of my own text. Quondum (talk) 03:40, 17 October 2011 (UTC)

No problem. We all make mistakes. —David Eppstein (talk) 03:45, 17 October 2011 (UTC)

Template:Did you know nominations/Thomas Kirkman

Hi. The DYK hook for the Thomas Kirkman article was waiting to go the main page, when another user edited the DYK hook to change "no mathematics" to "no algebra or geometry," based on his reading of a cited source. DYK requires that hooks be supported by the article, which still said "no mathematics" and did not mention algebra or geometry in that context. I checked the sources and edited the article so it would support the hook. After you removed the mention of algebra and geometry from the article, and I've pulled the hook out of the DYK queue so the contention can be resolved at Template:Did you know nominations/Thomas Kirkman. Please come by and have your say. --Orlady (talk) 16:21, 18 October 2011 (UTC)

thnx(: !

ur a great person and lots of fun and u know how 2 have a good time ahahah!!!!!!11

Hooperhog (talk) 02:04, 19 October 2011 (UTC)

DYK for Thomas Kirkman

Thank you for supporting the DYK project Victuallers (talk) 12:04, 21 October 2011 (UTC)

Nice article

Enjoyed Pythagorean tiling and the painting! PumpkinSky talk 12:57, 22 October 2011 (UTC)

DYK for Pythagorean tiling

The DYK project (nominate) 12:02, 23 October 2011 (UTC)

A barnstar for you!

	The Original Barnstar
	Great work on Pythagorean tiling! ♦ Dr. Blofeld 12:19, 23 October 2011 (UTC)

Thanks! —David Eppstein (talk) 15:51, 23 October 2011 (UTC)

New Page Patrol survey

New page patrol – Survey Invitation Hello David Eppstein! The WMF is currently developing new tools to make new page patrolling much easier. Whether you have patrolled many pages or only a few, we now need to know about your experience. The survey takes only 6 minutes, and the information you provide will not be shared with third parties other than to assist us in analyzing the results of the survey; the WMF will not use the information to identify you. If this invitation also appears on other accounts you may have, please complete the survey once only. If this has been sent to you in error and you have never patrolled new pages, please ignore it. Please click HERE to take part. Many thanks in advance for providing this essential feedback. You are receiving this invitation because you have patrolled new pages. For more information, please see NPP Survey

John F Healy

What is wrong with you that you feel it necessary to keep deleting the article that I wrote about my father who was a leading academic?? — Preceding unsigned comment added by JOHNDENNISH (talk • contribs) 20:48, 26 October 2011 (UTC)

I don't have any idea what you're talking about. John F Healy hasn't been deleted, and I don't think I've even seen it before your message. But you should also read Wikipedia:Conflict of interest. —David Eppstein (talk) 20:58, 26 October 2011 (UTC)

Thank you

For putting flesh on Ralph Richardson (Chancellor) Ottawahitech (talk) 13:57, 28 October 2011 (UTC)

SloanesRef

I guess you're watching it, but in case not, please check the changes I made at {{SloanesRef}} (you just mentioned that template at Template talk:OEIS). Johnuniq (talk) 04:28, 29 October 2011 (UTC)

Yes, your changes popping up on my watchlist were what reminded me of the existence of this template. —David Eppstein (talk) 04:29, 29 October 2011 (UTC)

CCI update

Wikipedia:Contributor copyright investigations/Joyaaioxom is now complete. Thank you for your assistance in the evaluation of this CCI.

--Moonriddengirl ^(talk) 15:12, 30 October 2011 (UTC)

Golden ratio revert

Hi David. You recently reverted one of my edits of golden ratio. You commented htmlified math changes the notation (phi rather than varphi), confusing when the latex math still uses varphi and not really the right symbol. I have a few problems with this:

• <math> already outputs Unicode/HTML if you do not specify "\,". In this case, it outputs the exact symbol I used in my edit, as shown in the table below:

LaTeX name	LaTeX image	LaTeX HTML	Unicode	Unicode	Unicode number and Name
\varphi	$\varphi \,$	$\varphi$	φ	φ	03C6, Greek small letter phi
\phi	$\phi \,$	$\phi$	ϕ	ϕ	03D5, Greek Phi symbol
\Phi	$\Phi \,$	$\Phi$	Φ	Φ	03A6, Greek Capital letter phi

Apart from minor font-related differences, I see no incorrect symbols here. This would contradict your argument that I was using the wrong symbol... can you clarify?

• By reverting the entire edit you also undid other changes that afaik are improvements. Do you have any arguments why you reverted them as well?
• The page already uses the same Unicode symbol φ that I used in multiple locations, so your revert does not actually solve the problem you mention in your argument.

Unless you can explain in more detail, I will go ahead and re-apply my edit. In the future, might I suggest that if you disagree with parts of an edit, but the edit does not obviously introduce errors, that you contact the author and discuss your concerns first? This would be more productive than undoing an entire edit because you feel parts of it are possible confusing.     — SkyLined (talk) 12:42, 9 November 2011 (UTC)

What I see in the first two entries of the table is the right symbol; everything else is not right. By the way, I am viewing math on Wikipedia using User:Nageh/mathJax, which generates much nicer display of <math>, so any change that turns <math> into something else is an uglification for me. Additionally, see WP:RETAIN — until we have a single standard solution for math formatting on Wikipedia, we shouldn't be gratuitously changing formats. —David Eppstein (talk) 16:56, 9 November 2011 (UTC)

Your argument is that the change could introduce confusion because it symbol looks wrong. However, you also mention that it looks wrong to you because you have installed some specific extension that changes the way math blocks are rendered. My changes makes things less confusion for users that do not have this extension, which afaik is by far the majority of Wikipedia users. Are you asking me to keep things confusing for the majority of users? (Let me clarify where this confusion comes from; the text uses "math" phi, "unicode" phi and "unicode italics" phi, all to represent the same symbol)

Also, can I assume you have no problem with the other changes I made? If so, I can at least re-apply those while we discuss this. Thanks!     — SkyLined (talk) 22:09, 9 November 2011 (UTC)

I've just installed mathJax to see what you were talking about. However, even with mathJax installed everything looks the same, apart from minor font related differences, as shown in this screen-grab I made.

Is this what you are seeing as well? If so, I don't understand why you oppose my changes.     — SkyLined (talk) 18:24, 13 November 2011 (UTC)

Probably we have different unicode fonts installed. What I see differs from yours in that the third and fourth columns on the first row look more similar to the same columns on the second row, rather than (as in your screenshot) looking more like an open phi. Oddly, though, when I look at the original table in the wiki text editor I get the open phi characters. —David Eppstein (talk) 19:31, 13 November 2011 (UTC)

Would you mind telling me what OS/browser/font you are using and if you manually changed the font? I've tested this with the latest version of MSIE, Firefox, Opera, Safari and Chrome on Windows 7 and all show the same results as above, even if I change the default font. I believe this problem is on your end, and that most Wikipedians do not have this problem. If so, I am going to re-apply my changes to improve the page for the majority of users.     — SkyLined (talk) 06:34, 14 November 2011 (UTC)

OS X. I usually use Chrome but it looks the same in Safari. I think I'm using the standard OS X fonts. And I still think gratuitously changing math formatting styles, especially from something that works (but is by default a little ugly) to something that doesn't work as reliably, is the wrong thing to be putting your energy into. —David Eppstein (talk) 08:07, 14 November 2011 (UTC)

I'll have a look on my Mac when I have the time. Btw, on slow connections and mobile sites, the images that Wikipedia serves where math is used make the page slow to load and use a lot more bandwidth. Also, you cannot copy+paste math blocks, and accessibility tools do not work on them at all, making the page less accessible to visually handicapped users. IMHO, this is sufficient reason to avoid math where possible, but I understand that others may feel different about this. I'll see if I can find out what the WP:MOS has to say about this and/or start a discussion there. I'll leave the page as is for now.     — SkyLined (talk) 14:24, 14 November 2011 (UTC)

This is what The MoS has to say about LaTeX:

"Having LaTeX-based formulae in-line which render as PNG under the default user settings, as above, is generally discouraged"

Sounds to me like my edit was justified.     — SkyLined (talk) 14:33, 14 November 2011 (UTC)

Lodovico Pizzati's deletion

Hello David, I've just realized that this article I edited some weeks ago had been deleted by you with the following explanation: WP:BLPPROD: Nominated for ten days with no sources present in the article. I am quite sure of having inserted in the article some good sources and, unfortunately, nobody told me that the article had been nominated for deletion. I would like to ask you either to retrieve the deleted article or send me the content of it by email. In either case I will edit the article and make sure that it will follow Wikipedia rules. Pizzati is a well-known figure and politician in Veneto Region, Italy and deserves an article. --Checco (talk) 23:53, 9 November 2011 (UTC)

Thanks a lot, David. I restored the article at its original place, adding facts and sources. However, the sources the other user deleted as "unreliable forum references" were not forums at all and were actually the official websites of the parties Pizzati led over the years, so I re-introduced them as very relevant sources. If you have time, please check the article and tell me if there are still problems. Many thanks. --Checco (talk) 01:06, 10 November 2011 (UTC)

LA-area Meetup: Saturday, November 19

	National Archives Backstage Pass at the Reagan Library
	You are invited to the first-ever backstage pass tour and Wikipedia editathon hosted by the Reagan Presidential Library, in Simi Valley, on Saturday, November 19th! The Reagan Library, home to a real Air Force One and other treasures from American history, will take Wikipedians on a special tour of the grounds and archives, followed by an editathon; free catered lunch provided. Please sign up! Dominic·t 21:05, 10 November 2011 (UTC)
	If you would not like to receive future messages about meetups, please remove your name from Wikipedia:Meetup/LA/Invite.

On Duval's algorithm

Hi,

You just deleted my sample Haskell implementation of Duval's algorithm generating Lyndon words' sequence, saying that best algorithms run in constant time. Thanks for pointing that out, but:

• as far as I know, Duval originally described two algorithms with different complexities, but his paper is inaccessible to me (can't find it available online for free);
• I couldn't find any description of more efficient algorithms.

So can you either point me to the description, or maybe write some description yourself, so I can learn those better algorithms?

Also, I don't think Wikipedia should only show best algorithms - the one that runs in O(n) is just good enough for illustrative purposes.

Minoru-kun (talk) 20:55, 13 November 2011 (UTC)

I very strongly disagree that an O(n) algorithm is just as good as an O(1) one for purposes of illustrating the O(1) algorithm. It completely misses the point of designing algorithms to be efficient. If you want to write about algorithms that are not as efficient as the best ones known, you also need to find sources for those specific algorithms justifying them on some sort of historical significance grounds; otherwise you're committing original research. And if I hadn't deleted it for that reason, I might have for a different reason: I think Haskell is very difficult to read. Anyway, here's an implementation I wrote in Python a couple of weeks ago.

def LengthLimitedLyndonWords(s,n):
    """Generate nonempty Lyndon words of length <= n over an s-symbol alphabet."""
    w = [-1]                            # set up for first increment
    while w:
        w[-1] += 1                      # increment the last non-z symbol
        yield w
        m = len(w)
        while len(w) < n:               # repeat word to fill exactly n syms
            w.append(w[-m])
        while w and w[-1] == s - 1:     # delete trailing z's
            w.pop()

Obviously, it can occasionally take more than constant time, but what Berstel and Pocchiola prove (and their paper is publicly available through the link in the Lyndon word references) is that its average time per generated word is constant. —David Eppstein (talk) 21:56, 13 November 2011 (UTC)

Oh, so it wasn't an algorithm itself you wasn't satisfied with — it was my implementation of it. I completely agree with deletion, then. (By the way, I just noticed that there's a little bug in there, so thanks for saving time of those readers who may just dumbly copy it and wonder why it doesn't work).

I also failed to understand that in fact there's no O(1) algorithm, it's just one that have O(n) complexity in worst case but O(1) in average — excuse me for that.

As for Haskell, I agree that sometimes it may look little scary, but consider the following implementation of standard factorization using another Duval's algorithm:

factorize = helper [] 1 0
  where
    helper :: [String] -> Int -> Int -> String -> [String]
    helper acc j k str 
      | j + 1 == length str  = acc ++ [str]
      | str !! j == str !! k = helper acc (j+1) (k+1) str
      | str !! j >  str !! k = helper acc (j+1)  0    str
      | str !! j <  str !! k = let acc' = acc ++ [take (j-k) str]
                                   str' = drop (j-k) str
                               in helper acc' 1 0 str'

String indexing is quite clumsy, but handling of different cases is just awesome. I don't think "if's ladder" would be easier to understand.

By the way, I'm going to describe that algorithm and add the code shown above as an example — I hope you don't mind. —Minoru-kun (talk) 22:48, 13 November 2011 (UTC)

Is that factorization algorithm really clearer than the following? I have no idea what a line like "| j + 1 == length str = acc ++ [str]" is supposed to mean, it just looks like a randomly-permuted sequence of symbols and operations.

def ChenFoxLyndonBreakpoints(s):
    """Find starting positions of Chen-Fox-Lyndon decomposition of s.
    The decomposition is a set of Lyndon words that start at 0 and
    continue until the next position. 0 itself is not output, but
    the final breakpoint at the end of s is. The argument s must be
    of a type that can be indexed (e.g. a list, tuple, or string).
    The algorithm follows Duval, J. Algorithms 1983, but uses 0-based
    indexing rather than Duval's choice of 1-based indexing."""
    k = 0
    while k < len(s):
        i,j = k,k+1
        while j < len(s) and s[i] <= s[j]:
            i = (s[i] == s[j]) and i+1 or k     # Python cond?yes:no syntax
            j += 1
        while k < i+1:
            k += j-i
            yield k

def ChenFoxLyndon(s):
    """Decompose s into Lyndon words according to the Chen-Fox-Lyndon theorem.
    The arguments are the same as for ChenFoxLyndonBreakpoints but the
    return values are subsequences of s rather than indices of breakpoints."""
    old = 0
    for k in ChenFoxLyndonBreakpoints(s):
        yield s[old:k]
        old = k

So you find Haskell code hard to read just because you don't know Haskell? Oh well…

Yes, I do find Haskell implementation clearer than Python one, just because I don't need to mentally execute the code to see how it would behave. Code in Haskell looks just like a set of rules, so all possible cases is clearly right there. Python code can't be analyzed that easily.

While Python code may be easier to understand to the person with some background in imperative languages, that doesn't mean it's the best option. Talking about the code you shown, reader still need to know about generators and slices, and it's not just a matter of syntax so it can't be thoughtlessly deduced from the code itself. If you strive for understandability for average reader that much, why not advocate pseudocode?

Still, that discussion led me to the conclusion that in this article sample code isn't necessary at all, so I'll remove my implementation.

Thanks again for pointing out errors in my understanding of subject, I really appreciate that. — Preceding unsigned comment added by Minoru-kun (talk • contribs) 10:03, 14 November 2011 (UTC)

I know many programming languages. but Haskell isn't one of them. I think the point is less which languages I know and more what the typical reader of that article is likely to be able to read, anyway. —David Eppstein (talk) 15:56, 14 November 2011 (UTC)

Revisit RfC for Notability (astronomical objects)?

You provided a question at this RfC, and the involved editors gave some answers. Would you consider revisiting the discussion and seeing if the guideline merits your support? Cheers, AstroCog (talk) 14:31, 16 November 2011 (UTC)

Binary search algorithm

Hello.

I've re-posted the url in the external links section. Consider this...

In my opinion: The primary purpose of any technical documentation is to disambiguate its subject matter. The url in question attempts to do just that. I would consider it an introduction using plain-spoken language that provides examples for those whom seek an entry level discussion on the topic. I submit that it be left in place for that reason. Thanks for reading!

Msswp (talk) 23:52, 20 November 2011 (UTC)

Disambiguation for computational complexity

Hello. You have a new message at PhnomPencil's talk page.

Computer network diagrams issue

Hello David, a while back the wiki page named network diagram was renamed to "computer network diagram" to differentiate network diagrams created by project managers vs those created by computer professionals. whilst valid, most computer professionals simply search for the words "network diagram" .. and this in turn points to your page on google as the words "network diagram" appears in your article.

to help direct users to computer network diagram page, might you be open to considering removing the two words "network diagram" in your first paragraph.. "A drawing of a graph or network diagram is basically a pictorial representation .."

Also I believe we should offer users the choice when they type in "network diagram" to either goto..

• graph drawing
• network diagram (Project management)
• network diagram (computer networks)

Many thanks

It might be reasonable to have a disambiguation page for "network diagram" that discusses all of these meanings. It would not be reasonable to remove "network diagram" from the graph drawing article. —David Eppstein (talk) 19:53, 23 November 2011 (UTC)

that would makes sense.. I will create a dis-ambiguous category page or the most appropriate holder for such a landing page and will inform you once thats done so we can change current re-direction that is happening when searching for "network diagram" in wikipedia that takes the user to graph drawing by default.

many thanks. — Preceding unsigned comment added by 204.239.136.99 (talk) 20:43, 23 November 2011 (UTC)

Counting Sort edits

I was curious why you deleted references to Counting Sort article in Dr. Dobb's Journal that illustrate the use of the merge pattern that is described in the paragraph of the Counting Sort wiki page. — Preceding unsigned comment added by Duvavic1 (talk • contribs) 03:47, 24 November 2011 (UTC)

I deleted the same article earlier when I was cleaning up counting sort. See my comment on this diff — basically, I think the Dobbs articles are bad references because they assume a model of counting sort where only the keys are sorted, and that there is no other data associated with their keys. That is a very restrictive assumption that makes the algorithm almost useless; for instance, it makes it impossible to use the algorithm even within radix sort. So I think people who try to read it as a reference will just end up more confused than if they didn't. Additionally, since the parallelization described in the article can be sourced to earlier research papers, removing the citation does not cause any problems of not properly crediting the original inventors of the technique. Finally, judging by your user name, there is a conflict of interest problem with your edits. —David Eppstein (talk) 06:24, 24 November 2011 (UTC)

I agree with your assertion about conflict of interest, as I did not realize that Wikipedia had such a policy - a very good idea indeed. I will need to remove references to my own papers in other places within Wikipedia, which makes me a bit sad since they provide immediately useful implementations to software developers. I disagree with "sorting of keys only makes the algorithm almost useless; for instance, it makes it impossible to use the algorithm even within radix sort", as this implementation of Counting Sort lead to the development of (and is used in) Parallel In-Place Radix Sort algorithm which is currently being used by Sandia National Lab.