Wikipedia:Reference desk/Archives/Computing/2016 October 29

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

October 29

Malfunctioning Windows 10 on HP Pavilion

I recently bought a new HP Pavilion with Windows 10 OS. I understand now why MS has been pushing Windows 10 on the public free of charge. The OS is full of ads. Some of that I have been able to remove. Then there are two major problems. A message for updates comes in from MS and I click OK. The system begins to update, proverbial white dots begin to roll around a small circle, I can see the percentage of what has been done, until it reaches 70 or 71%. Then the progress stops and after 40 minutes or so the OS begins to undo the changes after saying that update could not have been completed. It's happened 5 times already, last time this morning. It take an hour for the whole procedure. It is irritating and offensive.

The second problem is that many windows I invoke (open) get frozen on the desktop, like IE, FireFox, etc. It drives me nuts. No button will respond to any click until I invoked the Task Manager with Ctrl+Alt+Del. Today is the first time when even this drastic intervention stopped working.

So, I have two serious problems. I wonder if anybody could comment on them.

I also have a Linux Ubuntu machine. It works like a clock. Very simple and effective. MS has packed this Pavilion with bizarre features nobody needs, like Cortana. I tried to uninstall Cortana but it is irreducible. How to remove Cortana? I am about to join Microsoft hate crowd. --AboutFace 22 (talk) 17:57, 29 October 2016 (UTC)

The first step should always be downloading and creating Windows 10 insallation media (See [ https://www.microsoft.com/en-us/software-download/windows10 ]), formatting the hard disk, and doing a new install without the stuff HP adds. Be prepared to spend some time waiting as windows installs updates.

Next you should remove the Microsoft-added bloatware. See [ http://www.makeuseof.com/tag/easily-remove-bloatware-windows-10/ ] or [ https://www.hackread.com/windows-10-is-spying-on-you/ ] to do this manually.

Finally, you might consider using Spybot Anti-Beacon. See [ https://www.safer-networking.org/spybot-anti-beacon/ ]

There are other tools that claim to do similar things:

[ https://www.whatswithtech.com/how-to-stop-windows-10-from-spying-on-you/ ]

[ http://neurogadget.net/2015/08/20/windows-10-privacy-tools/13016 ]

[ http://www.ghacks.net/2015/08/14/comparison-of-windows-10-privacy-tools/? ]

[ https://bgr.com/2015/08/14/windows-10-spying-prevention-privacy-tools/ ]

--Guy Macon (talk) 18:46, 29 October 2016 (UTC)

THANK YOU VERY MUCH. I APPRECIATE IT. --AboutFace 22 (talk) 00:49, 30 October 2016 (UTC)

"Hot air balloon problem"

Resolved

I just came up with this problem and am wondering about its computational difficulty (as in, its worst-case runtime).

A hot air balloon pilot wants to go from point $A\in \mathbb {Q} ^{n}$ to $B\in \mathbb {Q} ^{n}$. There is a function $\mathbf {v} (h):\mathbb {Q} \to \mathbb {Q} ^{n}$ which gives the wind vector at height h (here, "height" is not a position parameter, but instead, considered as just a parameter the pilot can increment/decrement - the height will not change if the pilot does not decide so). Because weights are a finite resource, the pilot can only move up a given number of units $K_{up}\in \mathbb {Q} ^{+}$ n times, and can only move down $K_{down}\in \mathbb {Q} ^{+}$ m times. Every minute, the pilot has three choices: go up by K_up, decrementing his n "up" movements, go down by K_down, decrementing his m "down" movements, or maintain the current height, which implies maintaining the existing velocity (for simplicity, assume v is time independent and depends only on height). Each minute, regardless of the decision, the velocity vector is added to the current position (so the vector is always in units of position per minute). Assume that height changes are fast enough such that one can ignore the effect of winds between the starting and ending heights for every height change. The decision problem then is, can the pilot make this journey? Formally, is there a sequence of height increments starting from height 0, as described above, such that the sum of all the resultant velocity vectors is the position vector from A to B?

This problem is clearly in NP because any solution could be easily verified by just walking the proposed solution sequence. But is it in P, or is it NP-intermediate or something?--Jasper Deng (talk) 19:06, 29 October 2016 (UTC)

If I understand this question correctly. Your asking about forecasting a flight path and thus being able to choose altitude/wind currents rather than using app like [1] to log your flight path/track flown. A bit like being able to fly an aerial route map.--Aspro (talk) 20:45, 29 October 2016 (UTC)

@Aspro: No, it should've been clear that this is a theoretical computer science problem I just came up with. It has many unrealistic assumptions that would preclude its use in practice.--Jasper Deng (talk) 22:12, 29 October 2016 (UTC)

Assuming there is a finite number of heights, then all the paths will be a linear combination of the f(v) values. Which ones of these can get you from A to B can then be solved as a simultaneous linear equation, that will give the times that you spend at each height. This will take polynomial time. Note that there may not be a single solution. So then you have to intersect your constraints on n and m. This will result in a more limited simplex that will contain all the answers - possible routes. If you are limited to doing this on minute boundaries, and not at arbitrary times, then you have more contraints, and will likely have no solution. But in anycase this should be solvable or proved you can't do it in polynomial time. Graeme Bartlett (talk) 01:03, 30 October 2016 (UTC)

The existence of such a linear combination is necessary, but not sufficient for a solution. The way the problem is constructed, one cannot "jump levels", i.e. I cannot go from height N to N + 2K_up without first passing through N + K_up or other intermediate levels (depending on K_down and K_up and whether they're equal). I'm not sure you could formulate these constraints as linear ones, especially when K_up is not the same as K_down.--Jasper Deng (talk) 01:27, 30 October 2016 (UTC)

I am assuming that you spend no time in your transitions of height. The possible levels should be n×m or less. Just being able to move one up or one down at a time is just yet another constraint. It would result in a smaller intersection of the simplexes with less than n×m dimensions. Read Linear programming, and Simplex algorithm. If it is an Integer programming problem, then it becomes much tougher. Graeme Bartlett (talk) 01:51, 30 October 2016 (UTC)

That assumption is correct. I have learned integer linear programming in the past but am unsure of its applicability here. To be clear, yes this is an instance of integer programming, because we are really looking at an integer lattice generated by the different values of v, since one may not take nonintegral linear combinations here. All known algorithms for a general ILP run in at least pseudopolynomial time (since ILP is NP-complete). An $O(mn)$ solution would still be only pseudopolynomial in m and n. Even if we did not restrict it to integers, I'm not sure of how one could encode the m and n constraints in only polynomially many inequalities.--Jasper Deng (talk) 04:12, 30 October 2016 (UTC)

Your problem-setup assumes perfect a priori knowledge of the field (the wind function at all positions), correct?

Your algorithmic running-time bound - and the result of your decision-problem - depends entirely on the properties of this field. If the field is entirely unconstrained, the decision is much harder - you might have to traverse every possible path, which is a graph search in dimensionality n × m × h. (This is not a realistic model of normal wind, but it's how you described the problem: wind can cross other flow lines and speeds can vary without constraint). If the field is uniform at all positions, the decision problem is easy, almost trivial. If there is some constraint, like a smoothness constraint, on the field, there might be a more efficient way to reduce the span of your search space.

I think I'd begin by looking at our article on graph connectivity to see what prior art exists. It's a safe bet to say that your problem is a special-case of some already-published theoretical work. We just need to figure out what obtuse mathematical keyword describes your graph and its connectivity property.

Nimur (talk) 13:53, 30 October 2016 (UTC)

The wind field has no smoothness or other conditions imposed on it, but yes, you know it as a given. I wanted to avoid thinking of it as a graph problem: a graph to represent it would ignore the vector arithmetic aspect of this problem, and IMO would not be easier than an integer programming formulation, as described above.--Jasper Deng (talk) 19:20, 30 October 2016 (UTC)

Because the question is "can the pilot make the journey?", I would place it in P, easily calculable using lazy evaluation. If, instead, you asked "what is the optimal journey?", I would not place it in P because it is unlikely that there is a linear solution that finds the optimal journey. Nearly all problems can be divided like this. The classical Traveling Salesman is hard because it asks for the minimal path. If, instead, you asked for any path, it would be an easy problem. 209.149.113.4 (talk) 11:33, 31 October 2016 (UTC)

@209.149.113.4: And your algorithm is? Lazy evaluation is not relevant here. And also, this asks for a solution within the aforementioned bounds on m and n height changes - therefore, one could easily restate the problem here as an optimization problem w.r.t. either of those variables. Also, a pure decision problem in NP is also generally not known to be in P - 3-SAT makes no mention of optimization at all and is NP-complete.--Jasper Deng (talk) 15:36, 31 October 2016 (UTC)

The discussion above seems to imply that there are nearly infinite paths to get to any position. Because this is limited to specific positions, I prefer to think in terms of graph theory and call each position a node. The reality is that there are very few paths to get to any specific node. You have a source (starting point) and sink (ending point). The starting point itself eliminates a large chunk of the possible paths. Think of a standard Cartesian graph. Assume the starting point is as 0,0 and all the nodes are in a large rectangle from 0,0 to 100,100. If the balloon can only rise or fall 1 node on the Y axis per turn, that means that the balloon can never reach 0,2 because that requires a rise of two nodes. Similarly, if the goal is to land at 100,0, being at 100,2 is failure because you can't drop two nodes. Being at 99,3 is failure. Being at 98,4 is failure. Of course, this all assumes that winds blow in a positive direction from X=0 to X=100. It should be apparent that a lazy evaluation from 100,0 would eliminate 1/4 of the nodes. Moving forward from 0,0 would eliminate 1/4 of the nodes as well. But, a lazy evaluation tends to be quicker at asking "can it be done." From 100,0, how can you get there? Only look at nodes that could possibly get you there. From those nodes, how can you get to them? Only look at nodes that get you to them. Keep backtracking. If you hit 0,0, it can be done. If you hit all dead-ends, it cannot. My gut feeling is that this could be converted into a static graph in linear time. Then, you have a source and sink on a static graph that just screams to use Dijkstra's algorithm. 209.149.113.4 (talk) 14:17, 1 November 2016 (UTC)

@209.149.113.4: Except, that's just wrong. Please re-read the problem: the vectors' components are in general not of the same sign and "height" is a parameter separate from the position vector (so one does not talk of a "target height"). Also, in general, $K_{down}\neq K_{up}$. And in any case, you cannot solve this, nor can you reduce it, in linear time (or polynomial time at all, in fact), using your purported strategy, even in the special case you mentioned. This would at the minimum require $\Omega (|A-B|)$ time - pseudopolynomial in the storage size of A and B. You also ignore the constraints on the number of height changes allowed, which makes the allowable future travels from a given point dependent on previous movements.--Jasper Deng (talk) 14:30, 1 November 2016 (UTC)

I read that the pilot begins at height 0. Then, the pilot can increase or decrease height at will, once per minute. Therefore, height is not a continuous vector. It is a discrete set of values. I assume it cannot go negative. It obviously has a maximum value, which is the minimum of how many times it may increase height or decrease height (assuming the goal is to end at height 0). So, ignoring everything else in the entire problem, one part of it is to go up and down, beginning at height 0 and ending at height 0, correct? If not, you really need to restate the problem.

Next, you state that you want to know if the pilot can make the journey. What journey? A journey has a starting and ending point. You don't clearly state what the starting and ending point might be. I assume you have a starting point you will call point A. You then want to travel to point B. The goal is therefore to begin at height 0 at point A and end at height 0 and point B. If that is not the case, then you really need to restate the problem.

Assuming that the two above assumptions are correct, you have a pilot that begins as position A,0 and wants to go to position B,0. Why not restate that with numbers: 0,0 to 100,0. So, in this case, the journey is 100 units. We can consider the first number to be X on a Cartesian plane and the second number (height) to be Y. For every Y, you claim that there is a wind vector that increases/decreases the X velocity of the pilot. The pilot can increase/decrease Y or stay at the same Y per turn (minute). If that is not correct, you really need to restate the problem.

Assuming that everything is correct so far... This problem CAN be written as a graph theory problem. It CAN be written as a directed node problem. You keep claiming that it cannot be reduced to a simple graph without explaining why you believe that it cannot. I personally would treat it as a 3D graph. You begin at 0,0,0 (the third dimension is X velocity). What can you do? Go up. There is an issue here. Does the wind at height 1 affect velocity when you move into height 1 or does it affect velocity only if you remain at height 1? I will assume it affects you as soon as you enter the height. So, if wind velocity at height 1 was 3, moving up from 0,0,0 would move to 0,1,3. From there, you have 3 choices. You should see a decision tree (graph) forming. Just don't use depth-first search on an infinitely-sized decision tree. 209.149.113.4 (talk) 16:17, 1 November 2016 (UTC)

@209.149.113.4: No, please don't put words in my mouth. I never said it couldn't be reduced. I said it couldn't be reduced in polynomial time. I thought the problem's statement is clear: we have $A,B\in \mathbb {Q} ^{n}$, and height was explicitly stated to be a parameter independent of those. I also never restricted height to be nonnegative. The semantics of the wind vector were a bit vaguely stated, but can be formalized as follows: on taking the ith decision, you add the wind vector at the ending height to your total displacement. So if I start at the origin and increase my height, my displacement is now $\mathbf {v} (K_{up})$. You also keep ignoring the fact that in general, $K_{up}\neq K_{down}$ and are nonintegral (so at best, you're only treating a special case), and like I stated, due to the constraints m and n, your current displacement and height is insufficient data to determine what paths are allowable from a given point. And in any case, even your reduction is not polynomial time, and can't be. My problem also never constrained h = 0 at the end, only the start (in real life, one would parachute out!).

In fact, I now can see that this problem is NP-complete by reduction from a variation of the subset sum problem. Suppose that we have a finite set of integers |S| indexed with natural numbers i from 1 to k = |S| (i.e. the ith element is denoted S_i; assume without loss of generality that this indexing represents a greatest-to-least sorting). Let A and B live in one-dimensional space. Set A = B = 0. Set m = n = 2k. Let $K_{up}=2,K_{down}=1$. Let v(h) be given as $S_{l}$ if $h=2l-1$ for integers l from 1 to k, S₁ at height 0 (ruling out the trivial solution), and zero otherwise. Then any admissible path consists of a nonempty multiset of integers in S summing to 0 - a variation of the subset sum problem that is NP-complete per this. Any subset of the values in S can be used: if I am at an odd-numbered height (with nonzero wind vector), I can skip the following entry of S by first going down by 1, and then going up by 2 twice. If I am at an even-numbered height and want to use the value of S at the next odd-numbered height, then I go up by 2, and go down by 1. At most, I need two up and two down operations per each of the k levels, hence the values of m and n.

Please, actually read what I wrote. Unless you are claiming P = NP, there is no way this problem is easy with a graph algorithm.--Jasper Deng (talk) 18:18, 1 November 2016 (UTC)

I believe this is where the problem comes in. Quoted from above: "...my displacement is now $\mathbf {v} (K_{up})$." I read that as claiming that the displacement jumps to whatever the vector magnitude might be at that height. But, within the real-world example of a balloon, wouldn't the displacement be changed by the vector instead of replaced by the vector? For example, if my displacement was currently 13 and I moved up to a height with a magnitude of 3, my displacement would be 16, not 3 - correct? If that is correct, which I believe it is, then this is very similar to a summing or knapsack problem. There is a catch though. Once I pick a height, I immediately eliminate many other options. That is based on my understanding that you can only move up or down a single "unit" of height. I cannot go from height 1 immediately to height 3. I have to pass through height 2 and be affected by that wind first. Then, it appears that the goal is to reach a specific value for displacement from the start, regardless of ending height. I know you keep pushing that height and displacement have no relationship to one another. I do not see how you can frame this as a balloon moving around and not apply both height and displacement to a single balloon. Are there two balloons? One has height and the other has displacement? I believe it is one balloon with height and displacement. But, it keeps getting clearer that what I am reading and what you are writing have practically nothing in common. 209.149.113.4 (talk) 19:36, 1 November 2016 (UTC)

@209.149.113.4: I also stated that height changes are atomic: You are affected only by the wind at the height you end up at after each view. "Displacement" is a vector quantity so I can't fathom why you are mentioning it as a scalar above. And like I said, this is a theoretical problem with little practical value; the "hot air balloon" construct is only an analogy. Also, your "unit" of moving up and down is once again generally not the same for those two operations.

When I say "height" is an independent parameter, I mean precisely that. It's every bit as independent of position as time is (don't even talk about relativity). Is this physical? No. But can I come up with this in theory? Definitely yes. If you can't understand what I think is a pretty clear statement of the problem, then I'm not sure what to say. Take it at face value - don't overthink it. The quoted text you referred to refers to the special case of starting from the origin. If I am working in two dimensions and I am already at (5, 24), and am making a decision while at height 9, then after choosing to move up, I update my displacement vector to (5, 24) + v(9 + K_up).

I must remind you that you originally claimed that this problem was in P. Good luck with that.--Jasper Deng (talk) 19:52, 1 November 2016 (UTC)

USB 3.0 Hub ports

Moved from Wikipedia:Reference desk/Miscellaneous § USB 3.0 Hub ports

 – 47.138.165.200 (talk) 22:26, 29 October 2016 (UTC)

1) What do call a hub box that consist of a Micro SD card slot, memory card slot along with few USB insertion ports? An example of a design or just the name of what it is called as a whole, is sufficient.

2) This point is irrelative to the above and is as follows:

My Laptop is from the year 2012 or so. I think the USB box port[s] attached is of v2.0. I wonder if v3.0 wired products will function as it should thereafter connecting to this v2.0 box, or, do I require a USB 3.0 box in order for a v3.0 wired product(s) to function efficiently? — Preceding unsigned comment added by 103.230.104.22 (talk) 19:08, 29 October 2016 (UTC)

If I understand your description correctly, it's generally called a "USB memory card reader" or something along those lines. USB is designed to be forwards- and backwards-compatible. Any USB 3.0+ device should work with a USB 2.0 port of the same connector type, but speeds will be limited to 2.0 speeds. --47.138.165.200 (talk) 22:37, 29 October 2016 (UTC)

I would call it a memory card reader with USB3.0 hub (or similar). That seems to be what other sites call it too [2] [3] [4]. (Last one is a 2.0 only.) Nil Einne (talk) 01:57, 30 October 2016 (UTC)

Any idea why/when the DC Power Plug should be used?; I'm happy with Nill's Point no: 1. However, I'm looking for more ports, 10+ or so. 103.230.105.20 (talk) 19:14, 31 October 2016 (UTC)

Again assuming I'm interpreting you correctly, the power plug is to provide power to the ports in the USB hub. Typically the hub can operate with or without this; you only need it if you plug in a USB device that draws a lot of power. --47.138.165.200 (talk) 03:08, 1 November 2016 (UTC)