# Tag Info

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 ...

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 ...

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 ...

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 ... 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 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 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 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 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. 2 Let N(t,S) be the least number of values from S which sum to t. The basic recurrence is$$ N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1).  I'll let you work out the details. This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$. If we think of $t$ encoded in binary, then this algorithm runs in ...

2

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming. Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible ...

2

You need to be aware that the complexity of insert and pop can be $O(n)$ in python ($n = \text{length($L$)}$). Hence, the time complexity can be $O(n^2)$.

1

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, ...

1

Your problem is no harder and no easier than the approximate subset-sum problem. There is a natural approach for your problem: Find any subset that sums to something close to zero, and output it. Remove those numbers from the set $A$. Go back to step 1 and repeat, until the set $A$ is empty. This requires a way to find a subset that sums to approximately ...

1

Your function has constant running time (or linear running time, depending on how range is implemented). I suggest running it step-by-step and seeing what happens.

1

Time complexity, like any other nontrivial property of programs, is undecidable: there can be no algorithm to compute it, in Python or anything else.

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