Computing desk
< February 11	<< Jan \| February \| Mar >>	February 13 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 12

Skiplist search complexity

Disclaimer: I'm still in high school and haven't received any formal eductation in comp. sci., so this is probably a stupid question. Read at your own risk.

According to skip list, the search complexity of this structure is of the order of ${\mathcal {O}}(\log n)\,$ , and I don't understand why this is. Big-O notation refers to an upper bound, and a skiplist is basically a linked list with some probabilistic randomness - so shouldn't the upper bound be ${\mathcal {O}}(n)\,$ ? Isn't this essentially the same scenario as quicksort, which is ${\mathcal {O}}(n^{2})\,$ even though it's almost always much faster than other such algorithms?

Could anyone explain why this is the case?

Thanks a lot, Aseld ^talk 07:11, 12 February 2009 (UTC)[reply]

The skip list is already sorted, so finding a particular value is significantly less work than a full sort. A standard

{\mathcal {O}}(n)\,

search just requires traversing down the list checking each value—in the worst case, we will have checked all 'n' values. A skip search, however, is an approximate generalization of a binary search, modified for application to a linked list. In a simple binary search of an array, we can eliminate half of the array with each test, meaning we achieve better than

{\mathcal {O}}(n)\,

. Linked lists, however, complicate things because we don't know how long the list is, and we can't just pull the middle value out for a test; instead, we create parallel probabilistic linked lists. A search then starts with the shortest linked list, which only contains a fraction of the total values. Once we've identified two values that span our search value, we switch to a more complete linked list and repeat our search on that segment. Once we search the bottom segment (from the original linked list), we are done. Like the binary search, this search method also allows us to skip the majority of values in our linked list, so it's performance is also better than

{\mathcal {O}}(n)\,

. Proving the performance is

{\mathcal {O}}(\log n)\,

requires somewhat less hand-waving and somewhat more math. – 74 07:55, 12 February 2009 (UTC)[reply]

Ah, got it - I forgot that skip lists have to be sorted. Thank you! --Aseld ^talk 07:57, 12 February 2009 (UTC)[reply]

Resolved

StuRat (talk) 15:17, 12 February 2009 (UTC)[reply]

Nokia 5800 problem

OK, so my dad bought himself a Nokia 5800 to replace his old mobile phone. We installed a file manager and some songs on it, but after a few days, my dad got pissed off when the handset can't recieve certain MMS messages (in this case, a downloaded ringtone) properly, with the message "Message could not be adapted for your phone" or something similar. I told him that it may be due to compatibility problems, but he argued that he couldn't believe that "an 8GB phone can't receive an MMS" or something.

Is it due to network problems, or does it have something to do with the phone or the file browser I installed? Blake Gripling (talk) 08:37, 12 February 2009 (UTC)[reply]

I've always had to phone my service provider when changing phones. They normally have settings for each brand. Sometimes, as in the case of my latest phone, it even requires a secure connection to a local server. Phone customer services and they should be able to help. Sandman30s (talk) 11:31, 12 February 2009 (UTC)[reply]

Internet on C/C++

Is there any way to access HTTP on standard C/C++? I found something known as Libcurl, but I was looking for something on standard C/C++ preferably. Thanks. Magog the Ogre (talk) 08:57, 12 February 2009 (UTC)[reply]

In a word, no. However, libraries like curl (or if you want more control, Berkely sockets) are pretty much ubiquitous these days. --Aseld ^talk 09:11, 12 February 2009 (UTC)[reply]

Hey, look what I found. Help much appreciated. Magog the Ogre (talk) 05:21, 13 February 2009 (UTC)[reply]

tab characters in Safari

I sometimes need to enter a tab character into a textbox on webpages in Safari on OS X. Surely there is some way to do this other than copying and pasting a tab from another program? Googling didn't turn up anything obvious.... --140.247.243.160 (talk) 16:17, 12 February 2009 (UTC)[reply]

Why won't a number of spaces work ? StuRat (talk) 16:19, 12 February 2009 (UTC)[reply]

There are lot of situations where a tab and a bunch of spaces are not equivalent at all, especially involving code of some sort. --98.217.14.211 (talk) 23:09, 12 February 2009 (UTC)[reply]

One source suggested ctrl + Tab ↹, though obviously not for your browser/OS. Another option is to use the "personal information" storage capabilities of your browser: set your name as a tab character, then insert it when you want a tab in a textbox. You might also be able to configure a keyboard or mouse shortcut in your browser to paste in a tab character, or use a greasemonkey (or equivalent) script to automatically swap some combination of characters ("<tab>", for instance) for a tab. – 74 16:54, 12 February 2009 (UTC)[reply]

Both of these seems pretty silly work-arounds.... (seriously, set one's name as a tab character?) --98.217.14.211 (talk) 23:09, 12 February 2009 (UTC)[reply]

Cannot Open Pendrive Folder

When I right-click on the thumbnail of my pendrive folder, and click on either Open or Explore, my computer displays an error message saying:

Please insert a disk into drive I:

I tried formatting it by right-clicking and selecting the Format option, as well as from Command Prompt itself. Neither worked. Please help. Is this something to do with autorun.inf?? 117.194.229.146 (talk) 16:45, 12 February 2009 (UTC)[reply]

Are you absolutely sure that you're right-clicking the correct thumbnail? If you plug it in and then pull it out, does Windows complain? (If it doesn't, this suggests that Windows isn't even seeing it.) And what happens when you plug it into somebody else's computer? Morenoodles (talk) 08:40, 13 February 2009 (UTC)[reply]

I'm absolutely sure that it's the right thumbnail. What's more is that, later, I noticed that if I go to the properties of the pen drive, Windows shows used space as 0 bytes, and even free space as 0 bytes, whereas the pen drive's capacity is 512 MB. Windows doesn't give any kind of complain on pulling out the drive. I haven't tried it on anyone else's computer yet. Please help. 117.194.227.183 (talk) 15:36, 13 February 2009 (UTC)[reply]

How do you know that it is the correct thumbnail? My windows occasionally changes its mind about which letter drive maps to my pendrive. To check if your pendrive is being recognised, see if it appears and disappears in "my computer" as you plug it in and remove it. Have you tried different USB ports? Dbfirs 20:49, 15 February 2009 (UTC)[reply]

I've once mistaken a USB-MMC/Mini SD adapter to be a pendrive, and that's what it told me then. 119.111.70.146 (talk) 23:39, 16 February 2009 (UTC)[reply]

how to uninstall windows xp and install a fresh windows 2000 professional

How to uninstall windows xp and install a fresh windows 2000 professional. Please give me a step by step procedure to do this. —Preceding unsigned comment added by 218.186.12.219 (talk) 16:48, 12 February 2009 (UTC)[reply]

(after edit conflict)Boot off the Windows 2000 cd and choose to reformat the hard drive, however, i am curious as to why you want to use 2000 instead of XP. Windows 2000 forms part of the base code for Windows XP (the other part is Windows NT). I would recommend XP over 2000 any day. Buffered Input Output 17:19, 12 February 2009 (UTC)[reply]

I agree. It's not like the highly questionable Vista, which explains why many people stick with XP. Going back to 2000 really is a step backwards.

Note that formatting the hard drive will also wipe out any other applications or data you have on the computer, but is the best way to remove all traces of XP. Still, I'd highly recommend doing a backup to another disk, flash drive, or DVD first, in case you ever want XP back and/or any of the apps or data. StuRat (talk) 21:36, 12 February 2009 (UTC)[reply]

any way to color gmail letters sent to a different mailbox?

I forward a few gmail accounts to a master account, but is there any way to add coloring to see which box each one landed in? I only have a few (3-4). Thanks! —Preceding unsigned comment added by 82.120.236.246 (talk) 17:16, 12 February 2009 (UTC)[reply]

I do much the same as you, so I use filters. What you need to do is go to the master account and click "Create a filter" at the top. Then there's several options you can fill in (including what email address it's from/was sent to). Hit "Next Step" and then assign it a label (or star it, or whatever you want to do with it). It works very nicely. --Alinnisawest,^{Dalek Empress} (extermination requests here) 15:15, 13 February 2009 (UTC)[reply]

Alternative to Windows Briefcase

I use Windows XP and a Windows "Briefcase" to synchronise files on my USB stick with those on my hard-drive. Frequently, something happens which causes the briefcase to declare both versions have changed, even when they clearly have not. Thus I'd like an alternative, perhaps open-source application, that I can use on Windows XP. Does anyone have any suggestion? ----Seans Potato Business 18:24, 12 February 2009 (UTC)[reply]

If it's a one-way sync (that is, you'll only change one copy, and the other is a backup) use the excellent rsync. If it's a genuine 2-way sync (where either or both copies of a file can change, and you're willing to manually resolve what is essentially the same as a Wikipedia edit conflict) use Unison (file synchronizer). 87.112.81.29 (talk) 21:04, 12 February 2009 (UTC)[reply]

I tried to install Unison but it gave an error about the lack of libgtk-blah blah.dll, which I acquired on the internet and then it gave another error of the lack of libgdk_pixbuf-blah blah.dll - I already installed GTK. Are there any programs easier to install? Unison isn't really being developed any more.

I've used Synctoy, which is pretty good. It's not open source (it's from Microsoft) but it seems to work pretty well from what I've seen. - Akamad (talk) 12:46, 13 February 2009 (UTC)[reply]

Sudden Strike 3

On Sudden Strike 3, when you play the first game in one of the campaigns and get the message 'Mission Accomplished' at the end, what are you supposed to click? It gives two options, 'Continue' (which makes me continue the slaughter in the same scenario), or 'Save and Quit' (which saves the game and brings you back to the Main Menu). How am I supposed to play the second and subsequent scenarios in the campaign? Going back to the saved game is exactly the same as just clicking 'Continue' in the first place.--KageTora (talk) 19:41, 12 February 2009 (UTC)[reply]

Not having played the game, I may be wrong, but I suspect completing the mission unlocks the next mission, which you may then access from somewhere in the main menu. -- Captain Disdain (talk) 20:25, 12 February 2009 (UTC)[reply]

Perhaps it's less-than-subtle political commentary? – 74 06:48, 13 February 2009 (UTC)[reply]

Pfft. The game came out before the mission even began. -- Captain Disdain (talk) 08:58, 13 February 2009 (UTC)[reply]

Sorry, I left off the smiley on my post above. Technically, according to IGN, Sudden Strike 3 was released on March 31, 2008, while the "Mission" began on March 20, 2003 (with "Mission Accomplished" on May 1, 2003). However, it's quite difficult to believe that a game studio would intentionally irritate its fans just to make a political statement, so I'm still not seriously suggesting it. – 74 13:35, 13 February 2009 (UTC)[reply]

(Also, just to point something out, the Mission Accomplished sign was for that particular ship, not for the whole war, so the point's moot anyway.) --Alinnisawest,^{Dalek Empress} (extermination requests here) 15:11, 13 February 2009 (UTC)[reply]

Our article tends to disagree; specifically, Rumsfeld is quoted "...they fixed the speech, but not the sign." – 74 15:57, 13 February 2009 (UTC)[reply]

Oh, I realize you were kidding, I was just being pedantic. But, uh, it's my mistake, actually, because apparently I decided to get stupid: when the original poster asked about this, I looked up Sudden Strike 3 without realizing that it redirects to the article for the first Sudden Strike, and I noted the 2000 release date -- which, of course, refers to the first game, not the third one. So when I said it came out before the mission even began, I was really referring to something that only existed in my head. Sorry! -- Captain Disdain (talk) 09:23, 15 February 2009 (UTC)[reply]

Well, I can't believe that any game worth its credibility would create a 'campaign' with only one scenario, especially one where you just sit on Omaha beach and turkey-shoot thousands of Germans. There must be additional scenarios for it to be a 'campaign'. I just have no idea how to access them, and I am not playing the scenario again, because it took me two days to do it in the first place!--KageTora (talk) 15:43, 13 February 2009 (UTC)[reply]