Computing desk
< November 23	<< Oct \| November \| Dec >>	November 25 >

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.

November 24

Determine subtree height in a binary tree is O(n) or O(1)?

AVL tree is of binary trees. When inserting a node into an AVL tree, the rotation balancing the tree needs tree height info. of some subtrees. In this implementation, the tree height is defined as:

/*  The function Compute the "height" of a tree. Height is the
    number of nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
   /* base case tree is empty */
   if(node == NULL)
       return 0;
 
   /* If tree is not empty then height = 1 + max of left
      height and right heights */
   return 1 + max(height(node->left), height(node->right));
}

It is actually a recursive function which actually traverse the entire subtree to just find out the subtree height, if I understand correctly.

My questions are:

(1) Is the complexity of function height() O(n) where n is the number of nodes in the subtree?

(2) Since insertion operation of AVL tree is O(log n), does it mean finding subtree height like function height() does doesn't slow down the insertion and result in an overall O(n) insertion complexity?

(3) Does it help to add a treeHeight member to the node structure like this:

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
    int treeHeight; /* ***** add this to keep track tree height to prevent tree traversal everytime the tree height is queried ***** */
};

so we can calculate tree height in constant time O(1) by:

node->treeHeight = 1+ max(node->left->treeHeight, node->right->treeHeight);

sort of like Dynamic programming method to find out shortest path in a graph? -- Justin545 (talk) 04:22, 24 November 2014 (UTC)[reply]

The implementation you show is for determining the height of a given tree, which structure is unknown. Specifically it is not an AVL tree. In no way it is 'a definition' of a tree height. So it has nothing to do with AVL handling complexity.
Furthermore AVL trees do not need the exact height, it's sufficient to know whether both subtrees are equal height or which of them is higher. See AVL tree article for more details. --CiaPan (talk) 06:04, 24 November 2014 (UTC)[reply]

finding files in Win 8.1

The upfront search facility is no help with finding files by name on my laptop. Am I missing something? How do I find a file if I don't know where it is in the folders structure? --Halcatalyst (talk) 04:28, 24 November 2014 (UTC)[reply]

What is the oldest activie linux distro when you count also forks?

Wikipedia say slackware is the oldest active linux distro. Doest this count also forks of some other distro? If no, the answer to the question is still slackware?

Softlanding Linux System from May 1992 begat Slackware as a fork and could be considered the oldest founder of any currently active Linux distribution. SLS also inspired the creation of Debian as an alternative distribution. --Mark viking (talk) 21:33, 24 November 2014 (UTC)[reply]

I was not asking about the oldest distro that have a fork that is still being developed. But you aslready answered my question. If slackware is a fork, even when counting distros that are fork in the equation, slackware is the oldest distro still in development.

Website to block an ISP

I know that ISP's are the one's that normally block websites, but is it possible to do it the other way around? I get far too many hits on my website from my company, that it's creepy. On Google Analytics, the ISP is displayed as my company's name -- e.g. "Wikipedia". I would like to block all hits from a service provider that identifies itself, for this example, as Wikipedia. The problem is, I host my website through a host (Wix) that makes website design/publication easy, but limits the code I can put on it. As far as I'm aware, all I can use is HTML code. Is there anyway I can block a ISP with that? If not, at least something equally creepy for them back, like a message that comes up saying "Hello someone from Wikipedia [for example], you're visit has been logged", for further example. Thanks 92.237.191.99 (talk) 18:37, 24 November 2014 (UTC)[reply]

No, really, the only thing your server knows is the IP address...which you might be able to correlate with an actual business address. However, I don't think there is a way to get that information in pure HTML/JavaScript. In Javascript, you can get the Referrer of the current document:

  var x = document.referrer;

...and the result will be the URL of the webpage where the person clicked in order to get to your page. If everyone at your company is clicking some internal website to get to yours - then that might actually work. However, the privacy issues surrounding this "referrer" information are kinda nasty - so many browsers and web-intermediaries scrub that information - so it will certainly not be reliable.

However, it's possible that your web service provider allows PHP scripting in your web pages...and if so, then you can do it in PHP by comparing $_SERVER['REMOTE_ADDR'] with the address range of your company and generates an appropriate response if there is a match,

SteveBaker (talk) 21:00, 24 November 2014 (UTC)[reply]

Hi Steve, thank you. I have the IP address that all the traffic from my company comes from, but my Wix are rubbish, and they don't have PHP or Javascript support. Thanks anyway :) 92.237.191.99 (talk) 22:04, 25 November 2014 (UTC)[reply]

What can a .SCR file do?

I received an .SCR file from a friend a few minutes ago via Steam. I knew full well that his account was hijacked and it was not him who sent me that file. I have dealt with many malware in my time (.exe, .com, .vbs, .bat), but this is the first time I encountered a .SCR extension. The context menu showed 2 options: Test and Install, with the former being default. No administrative privilege was required, meaning it could not make change to important system folders. In a moment of curiosity and being over-confident, I gave it a Test to see what it could do. It showed an image in Windows Photo Viewer to fool me (as expected), but actually ran as a background process (out of my expectation), and I killed it.

My friend told me that his account was hijacked and all his virtual items had been lost, because of that .SCR file. I don't know how he "used" it (Test or Install, but likely Test since it is the default). I've checked my system and found no unusual startup application and running process, and I am 99% sure I am safe. But I still want to know what .SCR files can do in term of malicious activities (maybe recording keystrokes I guess). I am sure it cannot do everything like an .exe because it is not designed for that purpose. -- Livy (talk) 19:16, 24 November 2014 (UTC)[reply]

.SCR is the extension for a Windows screensaver program (the .SCR extension allows the little program that lets you choose which screensaver to run to know it's suitable to work as a screensaver). But it's really absolutely the same as a .EXE - it's a fully fledged unsandboxed executable with full permissions (hmm, I confess I'm not sure that's true on later Windows, but it certainly was the case at least as far as XP). So it can do anything that an .EXE can do - if it genuinely wasn't from your Steam friend, you should surely assume you're infected with professional-grade malware, and take appropriate steps. -- Finlay McWalterᚠTalk 19:22, 24 November 2014 (UTC)[reply]

Worse than I thought. As far as I know executable files like .gadget can execute malicious code, but they are somewhat limited by their extension (some Gadgets require external .exe running in the background for full features because they cannot do everything). I knew it was a screen saver file, that's why I was confident and gave it a Test. In the worst case, I still highly doubt its ability without administrative privilege. -- Livy (talk) 19:37, 24 November 2014 (UTC)[reply]

I don't normally comment on this help desk, but it's really quite dangerous to run a .scr file just to see 'how much damage it would do'. In this instance, you saw the process and terminated it. That's fine. But most malware adds itself to some sort of startup mechanism so when you restart, it will restart that malware. I'm glad that you checked for this, but sometimes they can be sophisticated little buggers and do stuff even more surreptitiously. Might I suggest that if you're planning to do this in the future, use Sandboxie? Tutelary (talk) 19:46, 24 November 2014 (UTC)[reply]

It was my bad, I know. There were several years when I lived without any antivirus. It was XP time, with zillions of malware but I never got infected (except for infection via Windows XP network exploits, which was out of my control). I have been always confident of what I do since then. But this time, it was a moment of silliness. I considered it a casual screen saver with malicious code, and underestimated its capability. It is Windows after all, where any programs can do anything. I'll send that .SCR file to Microsoft so that they can analyze and add it to the next definition (I am using MSE). They are not very active recently like they were before though. -- Livy (talk) 20:09, 24 November 2014 (UTC)[reply]

If you really want to mess them up, upload it to Virustotal. They upload it and distribute it to all the major AVs. So it'll be caught a lot more. They -hate- people who upload it there, as it distributes their sample and makes it less likely to infect people. Tutelary (talk) 21:45, 24 November 2014 (UTC)[reply]

Is there a tool to translate messy HTML into a structured format?

Becoming interested in web page development, I started out with a WYSIWYG program. As I went along, I found I had to learn a little HTML to resolve certain types of error. Later I did learn HTML. I thought it might be fun to to start out with a fairly complicated web page and try to make it more intelligible and also tighten it up: the code I'm dealing with works, but it is loaded with extraneous junk which I believe the WYSIWYG program put in, because no human being could possibly have made it that messy.

Taking a whole page into account is more complicated than looking around for simple bugs. But I have "translated" a very messy, somewhat complex, page of HTML into a structured format. Hey, it wasn't that easy! I frequently got lost and confused. Age, I guess. But I've enjoyed doing it; it takes me back to my programming days long time ago, when we had low-level code and structure was immensely important, at least to me.

I wonder: Do any tools exist to translate HTML into a structured format? I wouldn't buy it, but I'd be interested in knowing how it works. --Halcatalyst (talk) 22:29, 24 November 2014 (UTC)[reply]

There is HTML Tidy. -- Gadget850^talk 01:25, 25 November 2014 (UTC)[reply]

This is one of a general class of things called "pretty printers" - if you Google "pretty-print html" then "HTML Tidy" comes up first - but there are lots of others. Add in the XML pretty-printers (which may or may not do a decent job with HTML) and you have a bunch of other options. Additionally, many text editors (vim and emacs, for starters) have options to automatically beautify HTML.

Another idea is to use Chrome for viewing your file, then open up the developer tools and view your code in the "Elements" tab....or use Firefox and use the Web Developer/Web Console/Inspector tool. Both of these can fold up the code and nicely indent it with color coding for reserved words, tags, attributes, etc.

Thank you. I looked at the Chrome "Elements" tool and it looks like they take it <...> by <...>, which is great for serious debugging, though not for what I'm doing. I looked at the wiki reference you gave and found these

Examples of fixes it can make to bad HTML:

Straighten mixed-up tags

Fix missing or mismatched end tags

Add missing items (some tags, quotes, ...)

Report proprietary HTML extensions

Change layout of markup to predefined style

Transform characters from some encodings into HTML entities

Since I'm mostly in it for the learning, I will take these as my goals. Basically, I want to gtake this one page I'm working with to include CSS and reach full HTML status.

By the way... in looking at the "Elements" rendition of my page, I saw two things that aren't visible to me in Notebook or in the source code KomPozer offers: #Shadow-root and &webkit-keyframes. What are these? --Halcatalyst (talk) 05:10, 25 November 2014 (UTC)[reply]