# 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

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

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.

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.

1

You can solve this in $O(|E| \log |V|)$ time, if all weights are non-negative. Basically, you'll build a larger graph, of twice the size, then do a shortest-paths query in this graph. I will call the edges of the original multigraph regular and added edges of the form $i\to j$ for $i\subset j$ as irregular. For each set $i$, you have two vertices $i^-,i^+$...

1

When you slice a Numpy array, you get a special "slice" object, which holds pointers back into the array it was taken from. So if you do the same slicing operation twice, you'll get two different slice objects, which contain pointers to the same array in memory. (If you compare them using == instead of is, you'll see they compare equal, even though they're ...

1

You've divided the x values into 10 columns, and divided the y values into 10 rows, so we have a 10x10 grid. Take any row that is already covered by some already evaluated point, and remove it from the set of rows. Do the same with the columns. In your picture, we are left with 6 rows and 6 columns. Consider the 6x6 grid obtained by looking only at those ...

1

The constraints you have are not very clear (why should you start with "central items" ?). You should maybe try to come up with a well defined problem by precisely defining the clustering(s) you are looking for. For example, if the clustering you want is such that the maximum number of clusters is $k_{max}$ and the maximum distance between two elements in ...

1

ReLU is used in all layers except at the very end. Normally softmax is used at the final output, to normalize the outputs to be in the range [0,1] and to ensure the outputs sum to 1.

1

Your analogy is mistaken. You assume that, if you glanced at your calendar, you would quickly be able to identify all ten-day blocks of free time. Actually I bet you'd have all kinds of problems with that. Can you really tell at a glance the difference between a free block of $863\ 999$s (ten days minus a second) and one of $864\,000$s? Honestly, even if ...

1

I would cluster (e.g. kmeans) the pixels in the interesting area by their hue (in the HSL color space), and then extract the information you want from each cluster.

1

I would suggest looking into standard methods for image processing. You could use the Hough transform to detect circles. You could potentially use morphological transforms and the watershed algorithm to smooth out and remove noise and detect boundaries between the regions.

1

Backslash is the escape character to allow you to enter non-printable characters into a string literal. One of the most known escape sequences for example is \n for a newline. \a is the bell character and \b is the backspace character.

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