# Tag Info

25

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So ...

23

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: blocks) Elm F# (if #light "off" is not specified) Genie Haskell (only for where, let, do, or case ... of clauses when braces are omitted) Inform 7 ISWIM, the abstract language that ...

16

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines. For comparison, consider the word RAM model. In this model, memory is divided into words, words can be accessed in constant time, and the size of the problem can be represented using $O(1)$ words. So, for example, when analysing a comparison-...

10

There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to language compilers with JavaScript as target and esoteric Whitespaces. There is also Agda - interactive theorem prover, which is probably not what you had in ...

9

Is this correct? I haven't seen anyone else claim that Python compares ints in log time. No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the Python version is also $O(1)$. The problem is that we are trying to ...

6

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...

6

Although this may seem like a trivial point, your first sentence is incorrect. The functions are not equivalent. To make them equivalent, the C function should use GMP (or similar) to implement arbitary-precision arithmetic. Now, the reason this observation is not trivial, is that the extent to which it's reasonable to say that the two are equivalent, is ...

4

Unfortunately, this has no name—because it doesn't work. Pontus provided a good test case. lst = [2, 1, 3, 4, 5] sort_algo(lst) print(lst) [2, 1, 3, 4, 5] It's been mathematically proven that comparison-based sorting algorithms (that is, sorting algorithms based on comparing elements against each other, rather than exploiting certain clever tricks) can ...

4

Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$. Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).

4

Make fits your description, even though it probably isn't quite what you have in mind, with its limited syntax and power. It infamously indicates its code blocks (recipes) with a particular form of whitespace: one tab character. Alternative ways are available (e.g. GNU Make supports using an alternative character), but rarely used in practice. Another ...

3

You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number: $$00000001000011001100000001000000$$ Now you extract the 14 most significant bits: $$00000001000011$$ Converting to decimal, this is 67.

3

There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let $D(S,m,n)$ be the number of ways to obtain a change of $n$ using the first $m$ coins of $S = S_1,\ldots,S_M$. We have $D(S,m,0) = 1$, $D(S,m,n) = 0$ when $n < 0$, and otherwise  D(S,m,n) = \sum_{i=1}^m D(S,i,n-S_i)...

3

This area is known as black-box optimization: you have a function $f(x,y,z)$ where you have the ability to evaluate $f$ on an input of your choice, and you want to find $x,y,z$ that maximizes $f(x,y,z)$. (Here $x$ is the decision threshold, $y$ is the maximum % gain per trade, and $z$ is the stop loss, and $f(x,y,z)$ is the amount of ending money at the end ...

3

Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time. When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot. But when you try to parallelize an easy task it might take longer to handle ...

3

You are unsure how to answer the question. When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come. A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls. Now ...

3

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account. One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more ...

3

The reason you are seeing these results are not due to the memory limits of your computer, but rather of the limits of the encoding of "floating point" numbers. Python uses 64 bit floats (aka double precision floating point numbers), which are well described on wikipedia: https://en.wikipedia.org/wiki/Double-precision_floating-point_format In short, there ...

3

Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on. I run your script, and looked at the resulting file. On my machine, the file square_root_of_2_with_536870912_bits.txt contains 161.614.250 digits, and the last 161.597.755 ...

3

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$. One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$...

2

Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem. The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough. ...

2

So you have the right logic, if you have a loop of $O(n)$ iterations, the complexity of the entire loop will be $O(n*\text{complexity of loop operations})$. In this case, you again are correct that your loop's complexity is $O(n)$ for each iteration. Your last bullet point shows that you understand this as well, as the total loop complexity is then $O(n^2)$...

2

Let's call your proposal X, instead: X = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x))) For convenience, we can rewrite it as M = (lambda x : f(x(x))) # depends on f X = lambda f : (lambda x : f( lambda z: x(x) (z) )) M Now, when we invoke X(f), we get X(f) = (lambda x : f( lambda z: x(x) (z) )) M = f( lambda z: M(M) (z) ) ...

2

Your question appears to be a very long version of "Could we add some sort of punctuation to Polish notation so that it's unambiguous where each numerical operand ends?" Yes, of course you could. Normally, we use a space and write the numbers most-significant digit first but, sure, if you want to use the symbol ∅ and write the digits in the opposite order, ...

2

To answer your question literally, yes, the code does just return a string of length $n$ where $n$ is the length of the integer that we pass. And this is the right way to think about it. Your source, though, is using $n$ to denote the value of the integer, not its length. This is an unusual thing to do and it is, in my opinion, a very bad idea when ...

2

The length of the binary representation of a natural number $n$ is roughly $\log_2 n$. As an example, the number represented by the binary string $10^{n-1}$ of length $n$ is $2^n$. Your sources are misleading. Usually $n$ is reserved for the input length or a related quantity, not the input value. If the input to a function is an integer $m$, then the input ...

2

Think carefully about the flow. Your innermost While loop runs through b = 1, 2, each time it hits. It does this for EACH value of a in the outermost loop. So when a == 2, we progress inward and run through that loop twice. a == 2 both times.

2

Here is an easy way to answer this kind of question. Modify the function so that it counts the number of multiplications it performs. This can be done in various ways, which I'll let you figure out. Alternatively, you can write a recurrence equation for the number of multiplications. Let us denote the number of multiplications when the argument is $n$ by $M(... 2 Suppose that the candidates are$x_1,\ldots,x_n$and the target is$T$. I'm assuming all candidates are positive. If$T < 0$then there are no solutions. If$T = 0$then the only solution is the empty solution. Otherwise, there are two kinds of solutions:$x_1$together with a solution for$T - x_1$using all candidates. A solution for$T\$ using the ...

2

Are you writing an interview test right now ? __name__ is not a function. Is a special keyword used by Python and its value is ‘__main__’ if the script is run directly from terminal. So if another script.py imports the one in the photo, the code inside the if statement won’t execute. sys.argv Is a list of the arguments of the script, if given any from ...

2

You can always convert any recursive algorithm (that uses the call stack) into a iterative algorithm where you explicitly push and pop onto a stack that you manage. This should eliminate recursion depth exceeded errors.

Only top voted, non community-wiki answers of a minimum length are eligible