Proving correctness of an iterative Fibonacci algorithm

The condition $a \leq b$ is a loop invariant, but it captures very little of the operation of the loop. A better loop invariant is
$$ a = F_{i-2} \text{ and } b = F_{i-1}. $$
This clearly holds just before the loop. The loop sets $a' = b = F_{i-1}$, $b' = a+b = F_{i-2}+F_{i-1}=F_i$, $i' = i+1$, from which it is easy to prove that it maintains the loop invariant. When the loop has finished, we must have $i = n+1$, and so $a = F_{i-2} = F_{n-1}$ and $b = F_{i-1} = F_n$.

There is a weak point in this argument: How do we know that $i = n+1$ at the end of the loop? We can fix this by strengthening the loop invariant to
$$ a = F_{i-2} \text{ and } b = F_{i-1} \text{ and } i \leq n+1. $$
This holds just before the loop since $n \geq 1$ (assuming $n \geq 0$, a precondition that needs to be added to the entire function). It is maintained during the loop since at the beginning of each iteration $i \leq n$. Finally, after the loop we have $i \leq n+1$ and $i > n$, which forces $i = n+1$ since $i$ is an integer.


Is it possible to build DFA for odd-length words with 1 in the middle?

No, you can not. Proof by Pumping Lemma: Assume $L$ is regular and $n$ be the pumping length consider the word $w=0^n10^n$. Thus there are $x,y,z \in \{0,1\}^*$ with $|xy|<n$ and $|y| > 0$ such $xyz=w$. Then $\forall i\in \mathbb{N}_0: xy^iz \in L$.

But due to its length constraint $x$ and $y$ consist of $0$ only and all are before the $1$. Thus $xy^2z = 0^{n+|y|}10^n \notin L$.

Thus, $L$ is not regular and can not be expressed by any DFA.


How do I convert the following GNFA to regular expression?

Given an NFA, we can simplify it to an equivalent NFA with possibly fewer states by repeatedly applying the following two pruning steps:

Remove any states which are not reachable from the initial state.
Remove any states from which no final state can be reached.

In your case, this will result in removing the left bottom state.


What is the grammar for language $L={a^nb^m : n \neq m-1}$?

If you split the grammar into two parts for disjoint parts of the language you better take different names for the variables, since they have a different meaning in the two parts.


Why is backtracking a necessary step in the Maze problem?

Your question title doesn't match your question details.
You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking.
A general technique for solving questions like this is as follows.
We'll investigate statements about the state of the program. In this case, statements about the contents of the matrix.
We start by looking at the intended outcome: the required postcondition. A postcondition is a statement that must always hold after the program terminates. In this case: what is the matrix supposed to contain after the program terminates?
The answer: the cells of the matrix must mark a path found from start to finish, if such a path exists. All cells marked 0 must be off that path, and all cells marked 1 must be on it.
Then, we figure out which invariant the program maintains in order to achieve the required postcondition. An invariant is a property that always holds: before, while, and after the program runs. In this case: which cells are supposed to be marked 1 while the program is in progress?
The answer: they are exactly the cells of the path found from the starting point to the current cell. If the program always successfully maintains this invariant, the required postcondition will always be met.
To maintain the invariant, when you add a cell to the path, it must be marked;
and when you retrace a step, removing the last cell from the current path, that cell must be unmarked.
What if we don't unmark it? Then, the program will maintain a different invariant: namely, the matrix will mark exactly those cells that have ever been visited, whether they are on the current path or not. This is the invariant Hansel was trying to maintain with his breadcrumbs.
If you follow Hansel, after the program terminates, all cells ever visited will be marked, even those that aren't on the path that was eventually found (and such cells will exist if any backtracking occurred). The requirement was for only the cells on the path to be marked. Backtracking can actually occur, so the program will no longer always be doing what it's supposed to do: it will no longer meet its required postcondition.


Time complexity to find Median of Medians

The running time of counting sort isn't $O(n)$, in general.  If you are guaranteed that every element of the array is an integer in the range $1..n$, then the running time of counting sort is $O(n)$; but if you aren't guaranteed that, in general the running time could be much worse.

Since the question doesn't make any guarantees that the elements of the array will be in a specified range, you can't claim that counting sort will have $O(n)$ running time, and your analysis of Approach #1 is not correct.

Approach #2 does indeed provide an algorithm with running time $O(n^2 \log n)$.  However, that's not the best algorithm.  There are better algorithms, which can find the median in $O(n)$ time.  So, the correct answer is $O(n^2)$ ... but not for any of the reasons listed in your question.  See https://en.wikipedia.org/wiki/Selection_algorithm and Find median of unsorted array in $O(n)$ time.


Name for almost random memory distribution on the heap

This is fragmentation.  See https://en.wikipedia.org/wiki/Fragmentation_%28computing%29 for a definition.  Fragmentation can happy on any kind of storage; most commonly it is discussed for persistent storage (e.g., in filesystems), but heap fragmentation can also happen, and that is what you are describing.  See also https://en.wikipedia.org/wiki/Memory_management (which discusses heap fragmentation).


If $N$ is bounded by a small upper limit, asymptotics cease to be useful. At that point you want either exact operation counts, or even better just measure actual speed.


Time complexity of Sieve of Eratosthenes

Write a sum for the number of operations of removing multiples of primes. How many operations to remove all multiples of 103 for example from an array of n bits? How many operations to remove all multiples of a prime number p? So you get a sum.

Then you need to know what the sum 1/1 + 1/2 + 1/3 + ... + 1/n is (roughly) and importantly why. You see that by adding 1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 ... + 1/15) + ... and there is an obvious upper bound.

Now instead of adding 1/k for $2^m ≤ k < 2^{m+1}$ you add 1/k for only the primes k with $2^m ≤ k < 2^{m+1}$. How many are there? What sum do you get now? And then you have a sum that looks almost exactly like the one you started with and gives you the result.


Let us denote by $x_1,\ldots,x_n$ the qualities of the $n$ persons; so the $x_i$ are iid random variables distributed uniformly over $[0,1]$.
If you know $x_1,\ldots,x_i$, then $X_i$ becomes deterministic. For example, if $x_1 = 0.3$ and $x_2 = 0.5$ then $X_2 = 1$, whereas if $x_1 = x_2 = 0.4$ and $x_3 = 0.1$ then $X_3 = 0$. If you know only some of $x_1,\ldots,x_i$, then you can calculate the distribution of $X_i$, as your example demonstrates.
None of this is needed to calculate $\mathbb{E}[X]$, however. Using linearity of expectation, we know that
$$
\mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i] = \sum_{i=1}^n \Pr[X_i = 1].
$$
In other words, in order to calculate the expected number of people hired, all we need to do is to calculate the probability that $X_i = 1$. This probability is $1/i$. You're right that the probability changes if we know more about the $x_j$, but so what? We are not interested in calculating $\mathbb{E}[X]$ given partial knowledge of the $x_j$. Instead, we want to calculate the expected value of $X$ when $x_1,\ldots,x_n$ are chosen uniformly at random from $[0,1]$, independently. This is the relevant distribution for calculating $\Pr[X_i = 1]$.
What might be throwing you off is the trick of using linearity of expectation. It allows us to treat the random variables $X_i$ completely independently, although the variables themselves are certainly dependent.


$\#P$ closure under binomial coefficients?

Let me take a guess: you mean an operation of the form $f(x) \mapsto \binom{f(x)}{d}$, where $d$ is a constant. Let's assume also that $f(x)$ is the number of $y$ such that $\phi(x,y)$. Then $\binom{f(x)}{d}$ is the number of $d$-tuples $y_1,\ldots,y_d$ such that $y_1 < \cdots < y_d$ and $\phi(x,y_1) \land \cdots \land \phi(x,y_d)$.


Where to get graphs to test my search algorithms against?

Search the inter-webs.

SNAP is a set of networks hosted by a prof at Stanford. Several real world examples in a variety of settings.

Net Wiki is hosted by a UNC math prof., again several links to real datasets as well as links to other data resources.

OpenFlights Has airports and routes between them (spatial network).

OpenStreetMap user edited network of roads for most of the world. You can also download subsets (e.g. just roads in Ohio, or just highways in North America). Format is in xml, not super easy to parse, but its a real world ~2d cyclic network.

There are several other resources as well, you'll just have to dig a little.


Data structure choice for a query-update-delete problem

Store your data structure in a red-black tree where the first component of a key (i.e. p in (p,q)) is the key and the values are red-black trees of the second parts of keys with identical first part.

So, for the set $\{(a,b), (a,d), (d,b), (e,f), (e,g)\}$, you would store a tree with three keys (a, d, and e). The value for the key a would be a red-black tree with b and d, the for the key d would be a red-black tree with b, and the value for the key e would be a red-black tree with f and g.

A red-black tree can be split in $O(\lg n)$ time, so query-delete would take $O(\lg n) + O(\lg n) = O(\lg n)$ time - $O(\lg n)$ for the tree lookup and $O(\lg n)$ for the split of the tree. This doesn't include the cost of deleting, deconstructing, finalizing, or disposing of the deleted elements.

insert would also be $O(\lg n)$.

Query-delete can be made $O(1 + \lg k)$, where $k$ is the size of the deleted set, by keeping a pointer to the smallest key in the big tree and searching from the ends of the little tree, rather than from the root.

Amortized, query-delete is $O(1)$: using the banker's method, simply put a single on each item in the little trees. Since returning $k$ items takes $O(1 + \lg k)$ time and returns $k$ coins, its amortized cost is now $O(1)$, while insert's is $O(1 + \lg n) = O(\lg n)$.


Enumerating the List of `nPr` (n Permute r) objects

This is more of a MATLAB specific answer

  arrayfun(perms,nchoosek(A,r))

*Think of this as conceptual answer, because I have have been away from MATLAB and can't test it right now.

In other words,

get unordered combinations of elements in A, taken r at a time. using nchoosek.
get ordered combinations (with perms) of each unordered combinations. Applying a function to each element of a list can be done via arrayfun.


Many-one reductions between the set of true sentences and a particular arithmetical set

For any such $X$ we have $X\le_mTh(\mathbb{N})$ but not conversely (and in fact $Th(\mathbb{N})$ is vastly more complicated than $X$).
To see that $X\le_mTh(\mathbb{N})$, we want to translate a question of the form "Is $n\in X$?" into one of the form "Is $\psi_n$ a true sentence?" for some appropriate sentence $\psi_n$. Now "$n\in X$" is equivalent to "$\gamma(n)$," and that's almost a sentence in the language of arithmetic - the only issue is that "$n$" isn't a symbol in the language of arithmetic (which consists only of $0,1,+,\times,<$). Do you see a quick way around this?

 Each natural number $n$ has a corresponding numeral, usually denoted "$\underline{n}$," which is just an appropriate string of the symbols $0$," "$1$," "$($," and "$)$" (or is the symbol "$0$" if $n$ is $0$): e.g. $\underline{4}$ is the string $((1+1)+1)+1$. Then if we let $\psi_n=\gamma(\underline{n})$, we have that $\psi_n\in Th(\mathbb{N})$ iff $n\in X$.

Note that here I'm conflating e.g. the number $0$ and the constant symbol $0$; this is annoying, but standard.

The other direction is a consequence of Tarski's undefinability theorem: just show that anything many-one reducible (or even Turing-reducible) to an arithmetically definable set is itself arithmetically definable. This will show that we never have $Th(\mathbb{N})\le_mX$ (or even $\le_TX$) for such an $X$. The key here is to show that the basic notions of computability theory are arithmetically definable:

 Use Kleene's $T$-predicate to talk about computable reductions.


Intersection and union of a regular and a non-regular language

We can prove this by contradiction.
Lets define $\overline{L_1} = \Sigma^* \setminus L_1$. Then we can reformulate $L_2$:

$L_2 = ((L_1 \cup L_2) \setminus L_1) \cup (L_1 \cap L_2) = ((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$

We know:

Regular Languages are closed under union, intersection and complement
$\overline{L_1}$ and $L_1 \cap L_2$ are regular
$L_2$ is not regular

Now assume $L_1 \cup L_2$ is regular: Then $((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$ is regular (as it is only a union/intersection of regular languages), so $L_2$ would be regular. That is a contradiction, therefore our assumption is false, and $L_1 \cup L_2$ can not be regular.


You choice is certainly correct.

However, there is nothing wrong with your teacher's code, either. Here is an excerpt from CLRS.

  The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold.

We certainly prefer the operation be made in the easiest way or the fastest way. However, there is no requirement the modification must be made in the easiest way or even in any easy way. Nor does it require that the modification be made in the fastest way or even in any fast way. All it requires that the operation of deletion should produce another binary search tree that has all nodes from the given binary search tree without that specific node (and no more nodes).  How those remaining nodes form a binary-search-tree is completely free of restraints.

Your teacher's code, on the other hand, is probably the shortest clear code that does the job. The more I study it, the more ingenuity I find.


Is the runtime complexity of sorting $O(n\log n)$ or $O(n\log^2 n)$?

Algorithms are usually analyzed using the random access machine model. In this model, arithmetic operations on machine words take time $O(1)$. A machine word contains $O(\log n)$ bits, where $n$ is some natural parameter, say the length of the input (in machine words!).

Given this definition, comparison-based sorting algorithms run in time $O(n\log n)$ as long as the arguments fit in a constant number of machine words.

Sorting algorithms probably take more than $n\log^2 n$ time on a Turing machine, since Turing machines have no random access. Turing machines are not so interesting, however, for analyzing the running time of algorithms, except for special circumstances such as proving results on the Turing machine model itself.

In your particular case, you can actually sort the array in $O(n)$ using counting sort. The $\Omega(n\log n)$ lower bound only holds for some models such as the comparison model.


Can I use breadth-first search for topological sorting?

BFS for topological sort seems possible to me.

All we need to add to the baseline BFS is a stack.  The idea is that in BFS, nodes are traversed by levels relative to the starting node.  When we get to the level where none of the nodes have un-visited children, we know that these nodes will be the first to put in topological ordering. Then we look at their immediate predecessors, and we know that they will be second to put in topological ordering. And we look at a level above, and so on.

Here is a pseudo-code snippet that does this on a subgraph reachable from the start_node (it'd be straightforward to extend it to the entire graph):

# Returns a list of nodes in topological-ordering.
def top_bfs(start_node):
    queue = [start_node]
    stack = []
    while not queue.empty():
        node = queue.dequeue()
        if not node.visited:
            node.visited = True
            stack.push(node)
            for c in node.children:
                queue.enqueue(c)
        else:
            # node's ordering should be lowered because previously visited.
            adjustedNode = stack.remove(node)
            stack.push(adjustedNode)

    stack.reverse()
    return stack


Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.


I am interpreting the word "whenever" in the definition of $T$ to mean that $T$ consists of all pairs $\langle M, w \rangle$ such that either $M$ accepts $w$ and $w^R$ or $M$ rejects $w$ and $w^R$. Please, correct me if this is wrong.

I will show a reduction from $A$ to $T$. Input $\langle M, w\rangle$ will be transformed to $\langle M', w'\rangle$ as follows:

$w' = 0w1$
$M'$ on input $w'$ strips the first bit $b_1$ and last bit $b_2$ off $w'$. Let $w$ be the remaining string. If $b_1 = 0$ then $M'$ runs $M$ on $w$ and outputs accordingly. Otherwise, if $b_1 = 1$ then $M'$ simply accepts.

I claim that $\langle M, w \rangle \in A$ if and only if $\langle M', w' \rangle \in T$:

If $M$ accepts $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and accepts. Also, $M'$ on $(0w1)^R = 1w^R0$ immediately accepts, since the first bit is $1$. Thus, $\langle M', w' \rangle \in T$.
If $M$ doesn't accept $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and doesn't accept. However, $M'$ on $w^R = 1w^R0$ accepts. Thus, $\langle M', w' \rangle \notin T$.


Why is the throughput (performance) of the Aloha protocol ≈ 0.18?

This number is reached first by assuming that messages will be produced and sent according to a Poisson process.

$$P[(N(t + \tau) - N(t)) = x]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^x }}{{x!}}$$

This means, that the probability of $x$ messages arriving for the given interval $[t, t+\tau]$ where $\lambda$ messages are expected to arrive, is equal to right side of the equation. In other words, if we are expecting 10 messages to arrive per hour, the chances of 6 messages arriving in an hour is roughly 6.3%.

Now, messages sent by ALOHA need to be alone in order to make it to all other the nodes undisturbed. In other words, no other nodes can be sending messages at the moment we want our message to be sent and must stay silent until our message is completely sent.

This means we want to find: $$P(exactly\space1\space\space message\space arriving) * P(exactly\space0\space\space messages\space arriving\space in\space next\space t)$$

The odds of exactly one message arriving is

$$P[(N(t + 1) - N(t)) = 1]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}}  = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

The odds of 0 messages arriving for $t$ is:

$$P[(N(t + 1) - N(t)) = 0]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 0 }}{{0!}}  = e^{ - \lambda\tau} = e^{ - \lambda}$$

and together they make

$$\lambda e^{ - \lambda} \times e^{ - \lambda} = \lambda e^{ -2 \lambda}$$.

This function tells us the throughput of the Aloha for all values of $\lambda$. So which $\lambda$ offers the highest throughput? To find out, we take the derivative of $\lambda e^{ -2 \lambda}$ and get:

$$ e^{ -2 \lambda} - 2\lambda e^{  -2 \lambda}$$
set to 0 and solve for $\lambda$ and we get

$$\lambda = \frac{1}{2}$$

This means that in order to have the highest throughput (i.e. be most efficient) we should have an expected rate of incoming messages to be $\frac{1}{2}$ per timeslot.

And after all that, what is the maximum throughput that we get when we have an expected rate of $\frac{1}{2}$? Simply, plug it into our equation  $\lambda e^{ -2 \lambda}$ and we get:

$$\frac{1}{2} e^{ -1} = 0.18393.... $$


How a Data Compression Software Reads a File as pure Binary File and makes Output?

A file is a byte stream

Although OSes provide some bells and whistles (such as metadata, or forks), most define a file as a sequence of 0 or more bytes.

Each byte in the file is a numerical value from 0 to 255 (inclusive). There's nothing more to it.

A file format is a way of giving meaning to the bytes in a file

For a simple example, you could have a file representing a black-and-white image, where each byte is either 0 (black pixel) or 1 (white pixel), one row after another. Perhaps the first two bytes encode the image width as a 16-bit number, and the second two bytes encode the height as a 16-bit number.

This example is very inefficient, since each pixel byte can never use the possible values 2-255. You may want to read about information theory.

"Text file" is a file format

In a text file, every possible value 0-255 is given a meaning, a specific letter, number, symbol, or a "special effect" character like newline. Sort of. Strictly speaking, in the ASCII encoding, only values 0-127 have a meaning.

There are many different text encodings, although only a few common ones. In Unicode, characters are not always 1 byte in length.

But let's stick with ASCII. If you store "51a3" as text, the byte values 53, 49, 97, 51 will go into the file, as they correspond to "5", "1", etc.

If you store the hexadecimal value 0x51 and 0xa3 as bytes, then there will simply be those two bytes (81, 163 in decimal.) So this is half the number of bytes. However the file is no longer a text file because 163 is not defined in ASCII.

Other file formats require purpose-built software

Text files are popular because you can open them in any editor (Notepad, nano). As you understand, they are not very space-efficient.

But it is not difficult to write your own software. Here is an example.

#!/usr/bin/env python3

# PART 1 - WRITE BYTES TO A FILE

save_hex = "60b725f10c9c85c70d97880dfe8191b3"

print("Saving:", save_hex)

# group save_hex into groups of 2
save_ints = []
i = 0
while i < len(save_hex):
    # the 16 makes int() treat the value as hex
    integer = int(save_hex[i:i+2], 16)
    save_ints.append(integer)
    i+=2

print("Integer values:", save_ints)

# create a bytes object out of an array of numbers
save_raw = bytes(save_ints)

with open('myfile.raw', 'wb') as f:
    f.write(save_raw)

# PART 2 - READ BYTES FROM A FILE

with open('myfile.raw', 'rb') as f:
    contents = f.read()

print("Loaded: ", end='')
for byte in contents:
    print('{:02x}'.format(byte), end='')
print()

After running this check the length of the file is half the length of the hex string. Also, learn to use a hexdump tool to inspect the contents of the file.

Python's bytes objects have a lot of features but if you use the basic idea above (list of ints in range 0-255 -> bytes object) and (iterate over bytes object and get an int in range 0-255) then you don't need to get too deep into the details.

All-purpose compression software usually doesn't understand the files it compresses

When you put an mp3 file into a ZIP or RAR, the compression software treats it as a sequence of bytes, the same way it would treat a JPEG or EXE or HTML file.


$L \in RE/R$ such that $L^R \cup L \in R$

Since this sounds like a homework question to me, I will give the answer as a series of hints. (You should make a serious effort to solve the question after each hint, instead of just reading them all in short succession.)

First: Such an $L$ exists and $L \cup L^R$ is not necessarily $\Sigma^*$.

   Try $L \cup L^R = \{a^nb^n\} \cup \{b^na^n\}$.

   For each $n$, $L$ should contain exactly one of the words $a^nb^n$, $b^na^n$. How can you do this so that $L$ is in $RE/R$?

And finally the solution:

   Let $K$ be any set in $RE/R$ and let $L = \{a^nb^n \mid n \in K\} \cup \{b^na^n \mid n \notin K\}$.


This is my first post on StackExchange! I realize it's on a fairly old post but perhaps someone else will appreciate an explanation!
I will preface this by saying that I come from a background in software development and mathematics, but I'm going to try and lay it all out, step-by-step without using coding concepts, just math.
All of the formulae will be at the bottom, in case you are uninterested in the explanation behind each.
From here on, $H$ will represent Hue, $S$ will represent saturation, and $V$ will represent value. We will also need to represent Chroma, which is the difference between max and min values of the RGB model, which will be represented by $C$.
Also, red, green, and blue will be represented by $R$, $G$, and $B$ respectively.
First we will find some intermediary values that we will need in order to derive other values. We will start with finding the max, which in the HSV model is coincidentally the value attribute itself.
$$max = V$$

Now we will find the Chroma. I'll post the formula first then show how it is derived.
$$C = S * V$$
This comes from the formula to calculate the saturation in your RGB to HSV image above, in which
$$S = (Max(R,G,B) - Min(R,G,B)) / Max(R,G,B)$$
As we just discovered, $V$ is equal to $Max(R,G,B)$, so we can replace it in the previous formula, to arrive at
$$S = (V - Min(R,G,B)) / V$$
Therefore we can find $C$ by multiplying $S$ by $V$, thus eliminating $V$ from the denominator on the right hand side.
$$C = S * V = (V - Min(R,G,B)) / V * V$$

Knowing $C$, we can now find $min$.
$$min = max - C$$
This comes from the formula for $C$ itself. All we need to do is rearrange the variables. We can do this two ways, but I'll keep it to the one that just uses addition and subtraction operations.
First we need to get min to the other side, which will negate it's value implicitly. We do this by adding $min$ to both sides.
$$C + min = max - min + min$$
so
$$C + min = max$$
Then we need to move $C$ to the other side, this time we will subtract it from both sides.
$$C - C + min = max - C$$
The $C$ values on the left hand side cancel out and we are left with our formula for $min$ above.

Our last variable to calculate will be $H'$, but we have to prepare it first. This explanation will be a bit long and also a little "leap-of-faithy" which I was hoping to avoid, but hopefully I can give enough detail to make the reasoning behind a later step a little more understandable.
Recall that $H$ in the RGB to HSV conversion is calculated differently depending on the max value. There are $3$ ways to calculate it. We also know that the range for $H$ is $[0$ to $360)$.
Therefore each of the $3$ equations must result in a unique range of $120$ values each, as $360 / 3 = 120$
Let's first take a look at the calculation for $H$ when $R$ is the $max$,
$$H = 60 * (0 + (G - B) / (R - min))$$
Assuming that $G$ is larger than $B$, our result will always be positive. If $R = 1$, $G = 1$, and $B = 0$, $min$ would be equal to $B$, and our formula would look like
$$H = 60 * (0 + (1 - 0) / (1 - 0))$$
which resolves to
$$H = 60$$
On the opposite side, let's assume that $B$ is larger than $G$. Now our result will always be negative. Let's use the same values from the last example, but switch the $G$ and $B$ values, so now $G = 0$ and $B = 1$. The $min$ remains $0$ as $G$ is now the smallest of the RGB values. Our new formula looks like
$$H = 60 * (0 + (0 - 1) / (1 - 0))$$
resolving to
$$H = -60$$
Notice the range of the results from these two examples?
$$range = 60 - (-60) = 120$$
So we know that these are the minimum and maximum values for $H$ when $R$ is the largest of the RGB values. Now let's take a look at just one half of the formula for when $G$ is the largest.
Recall
$$H = 2 + (B - R) / (G - min)$$
Assuming that $R$ is greater than $B$, our result will again be negative. We'll let $G = 1$, $B = 0$, and $R = 1$ (For the sake of readability and ease-of-understanding, I'm allowing $R$ to equal 1. In reality, it could only approach $1$ but never equal it exactly, as that would force $H$ to take the first formula since it would consider $R$ as the $max$ value). The $min$ value is equal to 0. Our formula will look like
$$H = 60 * (2 + (0 - 1) / (1 - 0))$$
resolving to
$$H = 60$$
We already know that this must be the smallest value for $H$ when $G$ is the largest RGB value, and you can check for when $B$ is the largest if you like, but this means that the only negative values we can have for $H$ are in the range $[-60$ to $0)$. This also indicates that the range of values to multiply by $60$ when solving for $H$ must be in the range $[-1$ to $5)$. The range has $6$ values $5 - (-1) = 6$, so $60 * 6 = 360$.
Okay, that was a whole load of information just to say that we need to convert $H$ back into this "pre-scaled" range of $[-1$ to $5)$, that will be called $H'$. This is done simply enough by
$$H' = (H - 360) / 60$$ when $H >= 300$, and
$$H' = H / 60$$ when $H < 300$
The variable $H'$ is equal to a value in the range

$[-1$ to $1)$ when the $max$ is $R$,
$[1$ to $3)$ when the $max$ is $G$,
$[3$ to $5)$ when the $max$ is $B$,

Okay, those are all of the intermediary variables we need in order to finally solve for our $R$, $G$, $B$ values.
First, we have to determine what range $H'$ is between in order to know which RGB components we are solving for in each subsequent step.
If $H'$ is in the range $[-1$ to $1)$, then we will be solving for $G$ and $B$. We know from your RGB to HSV conversion that our minimum and maximum values for $H$ are $[-60$ to $60)$ when $R$ is the largest. So, when we divide that range by $60$ to arrive at $H'$, we get the range $[-1$ to $1)$. This also means that
$$R = max$$
Recall that this range depends on the relationship between $G$ and $B$. If $G > B$, the resulting value was positive, and if $G < B$, then the resulting value was negative.
With that in mind, we need to find out the sign polarity of $H'$. There is a slight modification in the following formula that will become apparent when I explain what to do if $G$ or $B$ is the maximum value instead of $R$.
If $H' - 0 < 0$, then
$$G = min$$
and using our $H'$ formula for when $R$ is the maximum value, we can substitute in our values for $H'$, $R$, and now $G$, which will allow us to rearrange the formula and solve for $B$. We also already have a variable for $R - min$, which is the same as $max - min$, which in turn is equal to $C$.
$$H' = 0 + (G - B) / C$$
In theory we must first subtract $0$ to the other side, but since it doesn't affect anything at the moment, I'll ignore it. We first multiply out the denominator on the right hand side to get
$$H' * C = G - B$$
and then subtract $G$
$$H' * C - G = -B$$
finally we need to invert the entire equation. I will swap the right and left hand sides as well for readability
$$B = G - H' * C$$
Therefore, when $H'$ is in the range $[-1$ to $1)$ and $H' - 0 < 0$
$$R = max,$$
$$G = min,$$
$$B = G - H' * C$$

What if $H' - 0 >= 0$?
This just means that instead of $G$ being less than $B$, now it's greater than $B$.
There is a slight alteration to the formula for $G$, which isn't quite the same as it was for when $G$ was less than $B$.
Recall that
$$H' = 0 + (G - B) / C$$
But this time we know $H'$, $R$, and $B$, which means we must solve for $G$
Again, I'll ignore the 0, and multiply out the denominator from the right hand side
$$H' * C = G - B$$
and finally add $B$ to both sides to remove it from the right hand side,
$$H' * C + B = G$$
Therefore, when $H'$ is in the range $[-1$ to $1)$ and $H' - 0 >= 0$
$$R = max,$$
$$G = B + H' * C,$$
$$B = min$$

The other cases are derived in much the same way, with slight modifications.

if $H'$ is in the range $[1$ to $3)$, the $max$ value will be $G$
if $H'$ is in the range $[3$ to $5)$, the $max$ value will be $B$

Let's assume our max value is $G$. Our $H'$ equation is now
$$H' = 2 + (B - R) / (G - min)$$
Since our max is now $G$, the expression $G - min$ is the same as $C$, so
$$H' = 2 + (B - R) / C$$
Remember when I said I'd make as small modification to a formula that might not make sense straight away but would come into play later? Well, it's back. To check for polarity here, we must subtract the value corresponding to which RGB value is greatest from $H'$.
So, we check for polarity by

$H' - 0$ when $max$ is $R$,
$H' - 2$ when $max$ is $G$, and
$H' - 4$ when $max$ is $B$

Now, we can't ignore the $2$ in our new $H'$ formula, so we'll first subtract it from both sides
$$H' - 2 = (B - R) / C$$
then multiply out the denominator
$$(H' - 2) * C = B - R$$
At this stage, if $(H' - 2) < 0$, we will be solving for $R$ since we know that in order for that sign to have been negative, $R$ must have been greater than $B$, meaning
$$B = min$$
and after subtracting $B$ to the other side and inverting the entire equation,
$$R = B - (H' - 2) * C$$
So, when $H'$ is in the range $[1$ to $3)$ and $H' - 2 < 0$
$$R = B - (H' - 2) * C,$$
$$G = max,$$
$$B = min$$
Similarly to our case from earlier, if $min$ was $R$ instead of $B$, then
$$B = R + (H' - 2) * C$$
So, when $H'$ is in the range $[1$ to $3)$ and $H' - 2 >= 0$
$$R = min,$$
$$G = max,$$
$$B = R + (H' - 2) * C$$

Similarly, with no more explanation, it should hopefully be apparent that
When $H'$ is in the range $[3$ to $5)$ and $H' - 4 < 0$
$$R = min,$$
$$G = R - (H' - 4) * C,$$
$$B = max$$
And when $H'$ is in the range $[3$ to $5)$ and $H' - 4 >= 0$
$$R = G + (H' - 4) * C,$$
$$G = min,$$
$$B = max$$

Hopefully that fully explains everything! I know it was quite a long read but I wanted to give as thorough an explanation as possible. I don't believe I missed anything, but if I did please let me know so I can amend it. Also, with a bit of rearranging, you can arrive at the formulae given on the Wikipedia page, but this post is already so long!
The formulae for everything are included below, thanks for reading!

$$max = V$$
$$C = S * V$$
$$min = max - C$$

If $H >= 300$ then
$$H' = (H - 360) / 60$$
otherwise if $H < 300$ then
$$H' = H / 60$$

If $H'$ is in the range $[-1$ to $1)$

 If $H' - 0 < 0$

   $R = max$
   $G = min$
   $B = G - H' * C$

 Otherwise if $H' - 0 >= 0$

   $R = max$
   $G = B + H' * C$
   $B = min$

If $H'$ is in the range $[1$ to $3)$

 If $H' - 2 < 0$

   $R = B - (H' - 2) * C$
   $G = max$
   $B = min$

 Otherwise if $H' - 2 >= 0$

   $R = min$
   $G = max$
   $B = R + (H' - 2) * C$

If $H'$ is in the range $[3$ to $5)$

 If $H' - 4 < 0$

   $R = min$
   $G = R - (H' - 4) * C$
   $B = max$

 Otherwise if $H' - 4 >= 0$

   $R = G + (H' - 4) * C$
   $G = min$
   $B = max$


Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

I attempted to solve the question separately:
The "no more than two 5s" bit can be represented by the regex $a^*(\epsilon+5)a^*(\epsilon+5)a^*$.
The "no two 6s in a row" bit can be represented by the regex $(a+6a)^*(6+a+\epsilon+6a)$.
Where $a\in\{1,2,3,4,7,8,9,0\}$.
Notice that we could potentially replace all the a*s in the first regex with the second regex, but this is problematic since it would allow double 6s. So I drew a FSM that uses this idea without violating the constraints. Hopefully, you could work out the regex and minimize the FSM if it can be minimized.
The language is regular since an FSM that defines it exists, hence its regular expression can be obtained.


Returning a random subset with length k of N strings while only storing at most k of them

Use reservoir sampling.  This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$.  You always have one string in memory. When you read the first string, you store it in memory.  Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far.  At the end, output whatever is stored in memory. The end result is that each string in the input is equally  likely to be output.  See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$.  See Wikipedia's description for details.


Greyscale image to binary image conversion using operations on pixel

You are looking for a thresholding algorithm.  There is no correct or incorrect algorithm.  Some methods tend to work better than others on specific types of images; which method is best may depend on what kind of images you usually work with. I suggest studying standard thresholding methods and picking one.


Finding asymptotically tight bounds $\Theta$ of two procedures

Note that the first algorithm never terminates for $n>1$; it starts with $i=0$
and multiplies $i$ by $2$ in every iteration of the outer loop, so we never get
$i \geq n$. I'll assume we start with $i=1$ instead.

I have some problems with your approach.

What are you counting? Why?
Where do the $\Theta$-terms in the recurrences come from? Don't you know better?
Your $\Theta$-"arithmetic" is flawed. Please check your definitions and maybe our related reference questions.

To give you something to work with, let's look at your first algorithm. I say we count arithmetic operations and comparisons because they seem to be the most numerous (no other operations occur in the inner loop). Each loop translates to a sum, so we get

$\qquad\displaystyle T_c(n) = \sum_{i=0}^{\lfloor \log_2(n) \rfloor} 4 + T_c(n-2) + \sum_{j=0}^{\lceil \log_2(n) \rceil} 3$

and $T_c(0) = T_c(1) = 0$. You have to solve this recurrence; note that it contains a bit more detail than yours. If you throw such detail away, you should be very certain that this is justified (which is why professors do it all the time when appropriate). Such certainty comes only with practice, so you should work a few cases through rigorously.

First, you should simplify the sums. For the purpose of obtaining $\Theta$-bounds, you can work with upper and lower bounds on the recurrence. For instance, consider

$\qquad\displaystyle T_c^\leq(n) = (\log_2(n) + 1) \cdot (4 + T_c^\leq(n-2) + 3(\log_2(n) + 2))$ and

$\qquad\displaystyle T_c^\geq(n) = (\log_2(n) - 1) \cdot (4 + T_c^\geq(n-2) + 3\log_2(n))$

with the same anchors. If you get the same $\Theta$-bounds (or compatible $O$- and $\Omega$-bounds) from these, you have by $T_c^\geq(n) \leq T_c(n) \leq T_c^\leq(n)$ and squeeze theorem a $\Theta$-bound for your original recurrence.

Strategies for solving recurrences are already exhibited in detail in our reference question, so I'll leave that part to you.


Given a set of points in the plane all laying on the axis, find the number of right angled triangles

Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane.

Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ axis and the right angle is at the $y$ axis. The third is analogous where two vertices lay on the $y$ axis and the right angle is at a point on the $x$ axis. Let us solve the first two cases the third one can directly be derived from the second one.

The first case. Note that by excluding the origin from the set any point on the $x$ axis with a point on the $y$ axis form such a triangle with the origin so the number of such triangles is number of points on the $x$ axis times the number of points on the $y$ axis (excluding the origin).

The second case. Lets $X$ be the list of all points on the $x$-axis sorted in ascending $x$ coordinate and analogously we define the list $Y$ for points on the $y$-axis. $X$ and $Y$ can be build in time $O(n \log n)$. Note that for a fixed point on the $x$ axis the other point must be on the other side of the $y$-axis and as further it is from the axis, as further the $y$-vertex must be from the origin. So we can again use a sliding window approach. For each point $x_1$ to the left of the $y$-axix (we do the same later with the opposite side), iterate over all points $x_2$ to the right of the $y$-axis one by one from the left to the right and for each find the coordinate $y$ such that the points $x_1, x_2  (0, y)$ are a right-triangle wirth right angle at $y$. This can be found easily, since $y$ must be the point of intersection of the circle having $\overline{x_1 x_2}$ as a diameter with the $y$-axis. Note that $x_1, x_2 (0,-y)$ is also such a triangle. So we will keep two iterators starting at $y$ and one going upwards the other downwards, for each $x_2$ move both iterators till they reach a point whose absolute $y$-coordinate is not less than $y$. If it is equal to $y$ increase the number of triangles by one and iterate.

Here is an $O(n^2\log n)$ solution. For each point $p$ we will find the number of triangles that have a right angle at $p$ in time $O(n\log n)$. By iterating over all $p$ we can find the total count in the given time bound.

To this end let us sort all the points in polar angle relative to $p$ (we exclude $p$ from the set. Note that for a chosen candidate $p'$ we get that all triangles having an edge $\overline{pp'}$ have the third vertex at a fixed angle and hence all possible candidates appear consequently in the sorted list. So let us union all points having the same polar angle with $p$ in groups and keep a count for the size of each group. Now we can use a sliding-window approach to find for each group $g$ the group of points $g'$ (if it exists) such that $p$ forms a right triangle with each point of $g$ and point of $g'$. Note that by iterating over all groups we would have counted each triangle twice so we have to divide by 2 (or stop when the second pointer reach the first group).


Why isn't the Generalized Super Mario Bros. obviously in NP?

One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify the portion of the video game that is nessecary for their reduction framework.

Another aspect is that a priori I would see no reason that e.g. Donkey Country would be PSPACE-hard (which the paper shows), but SMB not. Sure, likely the framework from the paper cannot be used directly to show SMB is PSPACE-hard, but that doesn't mean it isn't possible. So, it doesn't seem obvious to me why SMB is not PSPACE-hard, from which it follows that it isn't obvious that it lies in NP. (as long as you don't think it is obvious that PSPACE$\neq$NP, at least)

As for your specific reasons why SMB might not be in NP, the fact that other games are PSPACE-hard seems a good argument why a polynomial certificate may not exist. However, proving that there indeed cannot be a polynomial size certificate would be the same as proving PSPACE$\neq$NP, so there are no known techniques to do that.

The second reason is related to the reason why the other games are PSPACE-hard. In general, solving two-player games can be done by reasoning "If P1 makes this move in turn 1, then for all moves P2 can do, pick a move for P2 s.t. $\ldots\ldots$ at the final move, P1 wins". This is the same as determining whether there is a satisfying assignment to a boolean formula with alternating universal and existential quantifiers: the true Quantified Boolean Formula problem (QBF). QBF is a PSPACE-complete problem.

This means that a 2-player game is PSPACE-hard if the above strategy of essentially going over all the moves is the only strategy to be guaranteed to win. The strategy of the 'computer' is of course limited in being only a simple function of the current state, but such a limited strategy can apparently be enough, as in the other games that are shown to be PSPACE-hard.

One question that may rise is why it is obvious that the problems lie in PSPACE. The authors cover this on page 2, but I will rephrase their argument here for the sake of completeness. Their main assumption is that the size required to describe the internal game state is polynomial in the input size. Their (somewhat informal) argument for this is that state changes of the game must controlled by a 'simple' and deterministic function of the player input. From the assumption it follows that we can solve a game reachability problem by making moves nondeterministically while maintaining the current game state. This means that the problem is in NPSPACE, and therefore in PSPACE as PSPACE=NPSPACE.


Extracting Boolean Function using Machine Learning

If you have an exhaustive list of all possible inputs, and the output for each, you already know the relationship between the input and output.  You don't need fancy machine learning.

If you want to explicitly write a formula for this relationship, it is easy to write a DNF formula (each clause corresponds to a single input-output pair, i.e., a single row in the truth table).  It's also easy to write a CNF formula, using a similar construction (each clause corresponds to a single input where the corresponding output is false).

If you want to find the minimal-length formula for this relationship, that is probably NP-hard (in fact it is "even harder" in some sense).  However there are heuristics.  Read about Karnaugh maps, Quine-McCluskey, the Espresso heuristic, and the fields of logic synthesis and circuit minimization.

I don't expect machine learning to perform better than existing methods.  Existing methods have a lot of intelligence built in, based on this specific problem.  ML methods wouldn't be able to benefit from any of that.

Ultimately, if you want to know whether some machine learning method performs better than standard methods, the only way to know for sure is to try it.  But I don't expect it to yield useful results, without new insights.


Finding loop invariant of Lowest common multiple function

Well, a possible loop invariant is "$x$ is a multiple of $a$ and $y$ is a multiple of $b$".

Then this almost proves partial correctness, because we know that after the loop terminates $\neg(x \neq y) \to x = y$, thus $x$ must be a multiple of both $a$ and $b$.

What this loop invariant doesn't show is that $x$ is the smallest possible such number.

To solve this, we must complicate our loop invariant:

If $x \geq y$, $x$ is the smallest multiple of $a$ that is bigger than or equal to $y$.
If $y \geq x$, $y$ is the smallest multiple of $b$ that is bigger than or equal to $x$.

Now it's up to you to prove that this invariant is correct.


How to compute Jacobi symbol efficiently?

The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.


Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $

The solution depends on the initial conditions. For example, if $T(0) = T(1) = T(2) = 2$ then $T(n) = 2$ for all $n$, but in general the recurrence converges to a pattern of length $4$. The limiting patterns are of the form
$$
a, \frac{ab\pm\sqrt{(ab)^2-4(a+b)}}{2}, b, \frac{ab\mp\sqrt{(ab)^2-4(a+b)}}{2}
$$
For example, if $T(0)=T(1)=T(2)=1$ then $a ≈ 3.13200592382654$ and $b ≈ 1.35282312408545$. For large $n$, the values $T(4n),T(4n+1),T(4n+2),T(4n+3)$ are close to
$$ 3.13200592382654, 2.06091243965066, 1.35282312408545, 2.17613759887451. $$
(So we choose $-$ in the $\pm$.)
The above was determined empirically. It would be nice to come up with a proof.


Proving correctness of inefficient algorithm - Path between two vertices

If we interpret d/2 as real number division, then A(G,s,t,3) will run forever. If we interpret d/2 as integer division such as 3/2=1, then the algorithm will fail for a graph which is just a path of 6 vertices and 5 edges. If we interpret d/2 rather unnaturally as integer division of d+1 by 2, the algorithm becomes correct but the semantic of A(G,s,t,d) is not very natural either.

Hence, we will change the following part of the algorithm

              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF

to

              IF A(G,s,v,d/2) AND A(G,v,t,(d+1)/2) THEN
                   RETURN TRUE
              ENDIF

together with the conventional interpretation of d/2 and (d+1)/2, the integer division.
We will see this change makes the most sense as shown by the simple proposition below that characterizes the semantic of function A(G,s, t,d).

We have the following proposition.

Reachable(d): A(G,s,t,d) returns TRUE if and only the distance from s to t is less than or equal to d.

Let us prove the above proposition by induction on d.

The base case when d = 1 is trivial.

Suppose reachable(d) is true for all d <= n, where n>=1. Let check the case when d=n+1.  There are two cases.

n+1 is even. Suppose n+1 = 2k. Checking the definition of function A, we can see that A(G,s,t, n+1) returns TRUE if and only if there is a vertex v such that both A(G,s,v, k) and A(G,v,t,k) return true, i.e., both the distance from s to v and the distance from v to t are less than or equal to k, thanks to the induction hypothesis since k <=n. That means the distance from s to t is less than or equal to 2k = n+1.
n+1 is odd. I will leave this case for you to check.

Proof is done.

The correctness of the algorithm is the correctness of reachable(|V(G)|), since there is path from s and t if and only if the distance from s to t is less than or equal to |V(G)|-1 (or |V(G)|, which is equivalent).

To verify that this algorithm can be very inefficient, we should find an example where it runs very slowly.  We would like to choose a graph for which A(G,s,t,d) computes as much as possible and return as late as possible. How about graphs with no edges? Let D be a graph of 2^n vertices without an edge.

Claim: A(D,s,t,2^k) will call A(D,*,*,2^(k-1)) 2^(n+1) times.

Claim: A(D,s,t,2^n) will call A(D,*,*,1) (2^(n+1))^n=(2^n)^(n+1)=|V(D)|^(log |V(D)| +1) times.

I will let you contemplate why this algorithm is so inefficient.


What does the "principle of deferred decisions" formally mean

The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.

One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has some sequence of the form $HTHTHH\dots$, and we query this oracle to tell us the next randomized outcome.

Basically we can defer the act of actually using a randomized input for  as long as we have to and this won't affect the randomness of this input.


Fast multiplication with a full binary $n \times 2^n$ matrix

Suppose that $A$ were a $1 \times n$ matrix, let $X_n$ denote your matrix for a given value of $n$, and let $A_{<n}$ consist of all but the last entry $A_n$ of $A$. Then up to rearrangement,
$$
AX_n = \begin{bmatrix} A_{<n} X_{n-1} & A_{<n} X_{n-1} + A_n \end{bmatrix},
$$
where $+A_n$ means adding $A_n$ to all entries. The running time of this procedure satisfies the recurrence
$$
T(n) = T(n-1) + O(2^{n-1}),
$$
whose solution is $T(n) = O(2^n)$, which is linear in the size of the output. This should be compared to the trivial $O(n2^n)$ solution.

You can save a factor of $n$ in your case in the same way. The resulting algorithm is asymptotically optimal.


Computational complexity vs Computational cost

To answer your question as stated: "computational complexity" typically refers to the $\Theta$-class of a certain (often implicit) measure of computational cost.
That said, I prefer to use the terms like this:

Use "complexity" when talking about problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

Use "costs" when talking about algorithms. You would say, "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

This is consistent with common use, that is every expert will understand what you're saying, but avoids using the term "complexity" for different things.
Rationale

Complexity theory and analysis of algorithms (AofA) are distinct fields with different goals and techniques. It's not helpful to use terminology that muddles the two together.
Side note: teaching only the complexity-theory side of things makes large parts of the AofA literature inaccessible to computer science graduate, which I think is a shame. See the work of Flajolet and Sedgewick if you're interested in these things.

"Cost", other than "complexity", is used for precise measures like, say, "the number of comparisons" often analysed in sorting. Such a cost measure is (given an algorithm and a machine model) a well-defined function on the inputs (other than "time") and can be analysed rigorously.

Every algorithm has many cost measures with different asymptotic behavious; in sorting, for instance, number of comparisons, swaps, and many more. Therefore, asking for "the complexity of the algorithm" is an oversimplification, and only meaningful under certain assumptions/conventions.

The analysis of cost measures can yield testable hypotheses, if it's more precise than Landau bounds. "Complexity" results are not testable.

"Complexity" of an algorithm can be rigorously defined in terms of cost measures, if one so desires. The other way around does not work.
For instance, an algorithm's "(time) complexity" is usually taken to mean the $\Theta$-class of dominant, additive cost measure that is defined by a function on basic operations. However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "[cost measure] is in $\Theta(\_)$".


How to label a video for supervised learning?

Try Computer Vision Algorithms and Applications by Richard Szeliski and label propagation in video sequences.
To get a good grasp on the topic also Supervised Sequence Labeling with Recurrent Neural Networks. I proposed these resources as they cover the labeling, machine learning and are very in-depth materials (book, dissertation and the paper about propagating labels).

Video is the natural extension of the image, but to get fully working methods we also have to account for scene movement and changes. And I belive that in the video point is referenced by $x, y, t$.


Reducibility and Artificial Neural Networks

Not really.  I respect what you're trying to achieve, but I don't think it's possible to achieve what you want, given our current level of knowledge of neural networks.

We already know that convolutional neural networks perform better for some problems, and fully-connected neural networks (what you call MP) work better for other problems.  So you can't expect to find that one is always better than the other.

It has been proven that any computable function can be approximated arbitrarily well by some fully-connected neural network.  However, the catch in this theorem is that the theorem doesn't tell us how large the neural network needs to be.  We already know that sometimes a larger network is more accurate, but is also slower to train, so that's a pretty big caveat in the theoretical result.

And if you want to compare two different network architectures -- say, convolutional vs fully-connected -- then such a comparison won't be useful if it doesn't take into account the size of the network.  If you need 1 billion parameters to make a fully-connected network work well, or 1 million parameters to make a convolutional network work well, are they equally good?  No, you'll probably prefer the convolutional network.  It's not at all clear how to get useful reductions between the two architectures that tells us anything about the size of the neural network.

So, no, you're probably not going to get some useful theory this way that says "you can throw away all other architectures other than type X".


Why doesn't my object code/machine code contain 1's and 0's

This is a result of the program that opened the file.

All files on the system are in binary. What matters is how you interpret it.

The editor you used has displayed the digits in their common form:

"UH...." is the equivalent hexadecimal "5548...."  which is binary "101010101001000...."

Thus you need a Hex or Binary editing program to 'view' the '1's and '0's.


It can be, but the solution process is equivalent to converting a CNF formula to DNF, which is NP-hard.  You will at worst end up exploring an exponential number of disjunction branches.


What is meant by the term 'state' in a finite-state machine?

A state is simply an assignment of all possible variables of a system to values. A state transition then means a transition from one possible set of values of variables to another set of values.

To see how this might be useful, imagine a set of two switches $S$ and a light bulb $B$ that are connected to emulate some unknown logical gate. If you want to find out what that gate is, you can use a state machine model:

Say $I = \{S,B\} $

Initial State: $I = \{\{0,0\},0\}$

State transitions:

$\{\{0,0\},0\} \rightarrow \{\{1,0\},1\} \rightarrow \{\{0,1\},1\} \rightarrow \{\{1,1\},0\} $

It is evident that every state is just a set of different possible values of $I.$

By looking at the values of $B$ for a set of values of $S$, You can easily deduce that the system emulates a XOR gate.


Compile a programming language with itself

The trick is bootstrapping. You first write a compiler for your language (or a subset thereof) in some other language. Then you write a compiler for your language (or a large subset of the one you can already handle) in your language. You use the former compiler to compile the new compiler, and then the new compiler can compile itself.


Set of Turing machines that halt after exactly 14 steps

I assume you mean $M_i$ is a TM which is determined by Gödel Number $i$ such that from $i$ one can always construct $M_i$ in finite time and that $A = \{i \mid M_i \text{ halts after exactly 14 steps on \(x\) as input, where $i$ is a G}\ddot{o}\text{del Number}\}$ where $x$ is constant.

$A$ is recursive if there exists a TM for $A$ that always halts.

Such a TM can can be constructed as follows:

If $i$ is a Gödel Number construct $M_i$, else $i \notin A$, halt.
Run $M_i$ on the constant $x$ for 14 steps, if it halts after exactly 14 steps then $i \in A$, else $i \notin A$, halt.

Both 1 & 2 always halt which means that the TM always halts. So $A$ is recursive.


Does immutability in functional programming really exist?

When a program starts it has fixed data structures with fixed data

This is a bit of a misconception. It has a fixed form and a fixed set of rewrite rules but these rewrite rules can explode into something much larger. For instance the expression [1..100000000] in Haskell is represented by a very small amount of code but its normal form is massive.

  One can't add new data to these structures

Yes and no. The purely functional subset of a language like Haskell or ML can't get data from the outside world but any language for practical programming has a mechanism for inserting data from the outside world into the purely functional subset. In Haskell this is done very carefully but in ML you can do this whenever you want.

  There are no variables in the code

This is pretty much true but don't confuse this with the idea that nothing can be named. You name useful expressions all the time and constantly reuse them. Also both ML and Haskell, every Lisp I have tried, and hybrids like Scala, all have a means of creating variables. They just are not commonly used. And again the purely functional subsets of such languages don't have them.

  You can merely "copy" from the already data or currently calculated
  data

You can perform calculation by reduction to normal form. The best thing to do is probably to go write programs in a functional language to see how they do in fact perform calculations.

For instance "sum [1..1000]" is not a calculation I want to perform but it is quite handily done by Haskell. We gave it a small expression that had meaning to us and Haskell gave us out the corresponding number. So it definitely performs calculation.

  If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?

You don't add a new item to a list, you create a new list out of the old one. Because the old one can't be mutated it is perfectly safe to use it in the new list, or whereever else you want. Much more data can be safely shared in this schema.

  What is the point in having a program that can't get new data? Say you
  have a sensor attached to your computer that wants to feed data to the
  program. Would that mean that we can't store the incoming data
  anywhere?

As far as user input goes, any practical programming language has a way of getting user input. This happens. However there is a fully functional subset of these languages that you write most of your code in and you reap the advantages in this way.

  How is functional programming good for machine learning in that case?
  Since machine learning builds from the assumption of updating the
  program's "perception" of things - thus storing new data.

This would be the case for active learning but most machine learning I have worked with (I work as a code monkey in a machine learning group and have done so for a few years) has a one time learning process where all the training data is loaded in at once. But for active learning you can't do things 100% purely functionally. You are going to have to read in some data from the outside world.


Is the longest Hamiltonian cycle NP-complete?

Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the decision version of that problem.

Here, the decision version is:

  Does the weighted graph $G$ have a Hamiltonian path with total weight at least $x$?

For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least $x$. So, the decision version is in NP.

To understand why we look at the decision version, first note that NP is a class of decision problems, so only a decision problem can be NP-complete. (although we can construct an analogue of NP for optimisation problems, as in this answer). Solving the optimisation version also solves the decision version, so the optimisation version is at least as hard as the decision version. Since the theory gets easier when working with decision problems, focusing on the decision version is often helpful.


Where does the base come from in a subsequence count?

You can think of a subsequence $Y$ of $X$ as a characteristic vector $\chi_Y$  that has $m$ elements, one per element of $X$. The $i$-th element of $\chi_Y$ is $1$ if the $i$-th element of $X$ is also in $Y$ and $0$ otherwise.

It is easy to see that this is a bijection: every subsequence $Y$ has a distinct characteristic vector $\chi_Y$, and every characteristic vector $\chi_Y$ is associated to a distinct sequence $Y$.

This means that the number of subsequences $Y$ is equal to the number of vectors $\chi_Y$. Since each vector $\chi_Y$ has $m$ elements, each of which can have one of $2$ possible values, this number is $2^m$.

A concrete example of a sequence $X$, a subsequence $Y$, and its characteristic vector $\chi_Y$ is the following:


What are the primal and dual planes in the context of the point-line duality?

In short, the original $(x, y)$-plane is the primal plane and the new $(a, b)$-plane the dual plane.

More specifically, in a $(x, y)$-plane (or coordinate system)1, a non-vertical line can be represented as $\ell \colon y = ax - b$, where $a \in \mathbb{R}$ is the slope and $b \in \mathbb{R}$ the $y$-intercept. Hence, to describe a line, we just need to scalars, $a$ and $b$. We can state that a line has two degrees of freedom.

The idea of the duality between lines and points is that lines in the $(x, y)$-plane can be thought of or represented as points in a new $2$-dimensional space (or coordinate system), in which the coordinate axes are labeled $(a, b)$, rather than $(x, y)$. This new plane is denoted or labeled as $(a, b)$ to emphasize the fact that the values that $a$ and $b$ may assume respectively refer to the slope and $y$-intercept of the line $\ell$ in the original $(x, y)$-plane.

For example, the line $\ell : y = 2x + 1$, in the $(x, y)$-plane, corresponds to the point $\ell^* = (2, −1)$ in this new $(a, b)$-space 2, 3; that is, $\ell^*$ is a $2$-dimensional point with $2$ as the value of the $a$-coordinate and $-1$ as the value of this $b$-coordinate. A point $p=(5, 2)$ in the $(x, y)$-plane corresponds to the line $p^* \colon b = 5 a - 2$ in the $(a, b)$-plane 4. Similarly, a point $q = (1, 6)$ in the $(a, b)$-space, corresponds to a non-vertical line, $q^* \colon y = 1x − 6$ in the "original" plane $(x, y)$. And a line $t \colon \frac{1}{2} a - 5$ in the $(a, b)$-plane corresponds to the point $t^*=(\frac{1}{2}, 5)$ in the $(x, y)$-plane.

A convention is to call the original $(x, y)$-plane the primal plane, and the new (a, b)-plane the dual plane.

Why is $(x, y)$ the "original plane"? What's "original" about it? It's simply the plane where our initial problem is formulated. For example, we may have a problem where we are given a set of points. Then, we say that those points are given in the primal plane. We may convert our points to lines in the dual plane, because maybe we can formulate our problem in terms of lines, and the new problem is easier to solve.

Of course, we could have labeled the "original" plane with other letters, e.g. $(g, h)$, but we often label it $(x, y)$, so the new system is labeled differently, e.g. $(a, b)$. We could have labeled the new plane or coordinate system $(o, z)$: it really does not matter, i.e. it's just notation!

Here's a picture which summarizes all these words

Notes

Note that we label this plane $(x, y)$, but could have labeled it $(u, v)$ or any other tuple of two letters: it does not matter (as long as we are consistent).
Note the $-$ (i.e. the minus) in front of the $1$ in the point $\ell^*$.
We use an asteristik, $*$, to denote the dual of some object. For example, $u^*$ is the dual (in the dual plane) of $u$ (in the $(x, y)$ or primal plane). $u$ can either be a line or a point. If $u$ is a line, then $u^*$ is a point. If $u$ is a point, then $u^*$ is a line.
Note the $-$ (i.e. the minus) in front of the $-2$ in the equation of the line $p^*$.


Given 2 sets of n points: minimize sum of traveled distances

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances.

There have been several improvements since the Hungarian Algorithm, at least in terms of asymptotic bounds.  Depending on the exact size of the graph, any of several algorithms may be the best.  A table in the paper by Cohen, et al gives details.  Edmonds and Karp's algorithm is $O(nm + n^2 log n)$, and is still the best bound that doesn't depend on the maximum weight in the graph.  Cohen's algorithm appears to be the best for sparse graphs, which is not your situation.  I think the best for your dense graph would be Sankowski's $\tilde{O} (W n^\omega)$, since it doesn't depend on $m$.

I do not know if there are ways to exploit this problem's specific weight structure (Euclidean distances) for further improvements.

Sources:

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{(10/7)} log W)$ Time.
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
https://arxiv.org/abs/1605.01717v3 (preprint)

J. Edmonds and R.M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow
Problems. J. ACM, 19(2):248–264, 1972.

Piotr Sankowski. Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, chapter Weighted Bipartite Matching in Matrix Multiplication Time, pages 274–285. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
http://link.springer.com/chapter/10.1007%2F11786986_25


The answer is wrong.

Deadlock implies starvation, and the given code suffers from deadlock, here's how.

Say p0 executes wait(S); and then p1 executes wait(Q);. Now both the semaphores S and Q have value = 0.Now p0 will keep on waiting due to statement wait(Q); and p1 will keep on waiting due to statement wait(S);.

Freedom from starvation means that:

  if a thread tries to acquire a lock , it will eventually succeed.

This does not happen here, so the answer is wrong.


Counting the number of subsets with positive sum

Suppose that you could solve this in $T(n)$. Given a list of positive integers $a_1,\ldots,a_n$ and a target $T$, consider the two instances $a_1,\ldots,a_n,-T$ and $a_1,\ldots,a_n,-T+1$. Denoting by $N(\cdots)$ the number of positive sums, we get:

$N(a_1,\ldots,a_n,-T)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is larger than $T$.
$N(a_1,\ldots,a_n,-T+1)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is at least $T$.

By comparing these two numbers, you can solve SUBSET-SUM in time $T(n+1)$.

(There are some potential differences in the computation models, that I leave you to ponder.)

There is a simple $O(2^{n/2})$ algorithm, which proceeds as follows. We break the array $s_1,\ldots,s_n$ into two equal halves. We compute an ordered list $A_1,\ldots,A_{2^{n/2}}$ of all sums of the first half, and an ordered list $B_1,\ldots,B_{2^{n/2}}$ of all sums of the second half. This takes time $O(2^{n/2})$ if done carefully (by iterative merging). We put a pointer $j$ at $B_{2^{n/2}}$, and decrease it until $A_1 + B_j \le 0$. The value of $j$ tells us the number of pairs $(1,j')$ satisfying $A_1 + B_j > 0$. Then we do the same for $A_2$ — note that we can start the scan at the current value of $j$; and so on. This phase also takes $O(2^{n/2})$.


Depends on how close you want to look.

On face value, break, continue, etc. are implemented by unconditional jumps, which are (under most RAM-/CPU-like models) primitive instructions of the machine. So they certainly have some constant cost; $O(1)$ is a valid bound.

That's not very interesting, though: all primitive instructions have constant cost. If you want to answer questions like, "can I speed up my algorithm by adding/removing break/continue?", the situation becomes more involved.

The true cost of jumps depends on many factors, e.g.

the type of pipeline the CPU uses,
which type of speculative execution happens (if any),

and so on. My guess is that an unconditional jump -- other than conditional jumps -- should behave well in many regards. They are most certainly cheaper than completing the loop would be.

If the true cost matters to you, I recommend you benchmark the alternatives at hand. Be aware that the effect you're trying to measure may be smaller than the noise introduced by benchmarking, and you may have to account for that.


Help me understand this Turing-machine Problem concerning $A_{TM}$

Solving the language $L_1$ means knowing for every TM if it's semi-deciding the $A_{TM}$ problem.
Your instinct is right - it is empty and therefore decidable. If it wasn't empty by any chance, then by Rice's theorem it would have not been decidable


Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

Time complexity of algorithms is usually given as big O. There are many reasons for this, including tradition, but when pertinent reason is that in some cases the time complexity depends on the input. For example, a sorting algorithm might run in $O(n\log n)$ in the worst case, but in $O(n)$ in the best case, and so it is not correct to say that it runs in $\Theta(n\log n)$.

In your particular case, your algorithm runs not only in $O(n)$ but also in $\Theta(n)$. Stating that it runs in $O(n)$ doesn't rule out a matching lower bound — it just doesn't tell the complete story.


Converting an infix expression to postfix

There is a sort of an exception to '^', the exponentiation operator since it is right associative. That is, $a^{b^c}$ means $a^{\left({b^c}\right)}$ instead of $\left(a^b\right)^c$. That is, (a+b)^(p+q)^(r*s*t) means (a+b)^((p+q)^(r*s*t)) instead of ((a+b)^(p+q))^(r*s*t).

When you reach the first ^ while evaluating postfix expression ab+pq+rs*t*^^, you will pop out the result of rs*t* and the result of pq+. You get the expected exponentiation as expected.


Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

You might be looking for the Cholesky decomposition. The referenced article also contains an example for  $M$ having negative entries. Note the constraints on $M$ for this decomposition to exist.


Ideas for CS-related challenge for teams of high school students?

One activity that I really liked is the following: devise a way to communicate a short text message across a long soccer field, without using electronics and without shouting.  You can use any large field or open area that is large enough that they won't be able to hear each other by shouting, yet provides line of sight.

The idea is that the team will get together in advance to devise a communication method.  Then, half of the team stands at one end of the field, and the other half at the other end.  The first half is given a message, and they have to communicate it to the other end.  They are scored based upon the accuracy of the received message and how long it takes them.

This is a very cool exercise.  It gives them a lot of opportunity for ingenuity.  You can give them a few materials and they can select a signaling scheme -- maybe use flags, or mirrors, or large objects, or you name it.

They'll have to devise an efficient method of encoding text into something they can signal, and a good signalling algorithm.  It's their interests to trade off efficiency for robustness (redundancy to deal with errors in receiving the data).  They might choose to use a forward error correcting code (e.g., add some redundancy), or they might choose to use an acknowledgement/retry mechanism (where the recipient can signal "didn't get that, please try again").

Another thing that is nice about this exercise is that it provides an opportunity for teamwork and brainstorming and cooperation within their team.  It's always more fun to do this stuff together with a few others than to do it on your own.

If you like, you can point out the rich history of signalling schemes that have been used in the past: semaphore, Morse code, the signal fires used by Alexander the Great, etc.

If you don't like that one:

CS Unplugged is one of the best resources.  If they don't have anything you like, this might be pretty tough.

By the way, please keep in mind that competition has mixed effects, some good and some bad.  Competition is good for motivating for some students but at the same time, some students find competition demotivating.  Also, there is a gender gap here; competitions are more likely to turn off women than men, which might not be desirable in an activity for high school kids, given that there are already enough barriers keeping women out of computer science.


If $L$ is recursive then so is $L^*$, and vice versa

The second claim is wrong. Let
$$ L = \{0,1\} \cup \{010^n : \text{the $n$th Turing machine halts}\}. $$
Then $L^* = \{0,1\}^*$ is recursive, but $L$ isn't recursive.

For the first claim, your proof is not convincing. You need to explain how a Turing machine can decide whether a given word $w \in \{0,1\}^*$ can be written as a sequence of words from $L$. One way is to consider all possible partitions into non-empty subwords, and check whether one of them has the property that all subwords are in $L$.


About the definition of "differential privacy" in communication complexity

Your definition is wrong. The correct definition is as follows. A protocol $P$ is $\epsilon$-differentially private (for $\epsilon > 0$) if for any two inputs $Z_1,Z_2$ differing in a single coordinates and any $p$,
$$
e^{-\epsilon} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^\epsilon.
$$
For small $\epsilon>0$, $e^\epsilon \approx 1 + \epsilon$, and $e^{-\epsilon} \approx 1 - \epsilon$; the quantity $e^\epsilon$ is easier to work with compared to $1+\epsilon$, since $e^{\epsilon_1} e^{\epsilon_2} = e^{\epsilon_1+\epsilon_2}$, whereas $(1+\epsilon_1)(1+\epsilon_2) \approx 1 + \epsilon_1 + \epsilon_2$ holds only approximately.

Another small note: the upper bound implies the lower bound and vice versa.

The definition implies that for any two inputs $Z_1,Z_2$ that differ in at most $d$ places,
$$
e^{-\epsilon d} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon d}.
$$
In particular, if the inputs have length $m$, then for any $Z_1,Z_2$ we have
$$
e^{-\epsilon m} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon m}.
$$
In your case $m = 2n$.


Finding Connected Components Dependent on Order?

There's a few things we need to clear up.

First, the graph you show is directed. Are we talking strongly-connected, weakly connected, bilaterally-connected, etc. What you mean by connected here matters.

Secondly, in such an algorithm, usually you keep searching until each vertex in the graph has been assigned a component.

So, if you use the algorithm(s) properly, and keep searching until all vertices have been classified, the output will not depend on what vertex you start at. Each vertex belongs to exactly one connected component (whichever variety you choose), and a correct algorithm will assign it as such, regardless of the start vertex.

However, if you start at a vertex, you might not find all vertices just in the search starting from that vertex, which is why you need to repeat your search until you have seen all vertices.


Information theory of instruction set architecture design?

It seems you are interested in how to represent instructions in the most compact size. But that is quite a secondary consideration.
The most important two considerations are: 1. Being able to decode an instruction in the shortest possible time. 2. Determine the length of an instruction in the shortest possible time.
Why is this so important? Let's say you have an instruction to add two integers. This can be done very fast, say 300 picoseconds. Now when you decode that instruction, the decoding must be done in a time comparable to that of an addition, or the decode time becomes what limits the speed of your CPU, instead of the time that is actually needed to do the work.
The time to determine the length of an instruction is even more critical. Modern CPUs will often execute up to four instructions per processor cycle. So they must be able to decode four instructions per cycle. To do that, they must be able to determine the length of the first instruction, the second instruction, and the third instruction, before they can figure out where the fourth instruction starts, and start decoding that instruction. So we need to determine the length of three instructions, and decode a fourth, in the time it takes to add two integers!
So you can see how decoding must be absolutely fast. You just don't have the time to use any decent compression algorithm because it would slow down everything.
Update: ARM processors with fixed instruction length can decode 9 instructions per cycle, while variable length x86 instructions are limited to 4 decodes per cycle. So this is not something that can be solved by throwing transistors at the problem.


It depends on the form of $f$. If $f(x) = x$, then it is identical to subset-sum. If $f(x) = 0$, then it is a trivial problem with an $O(1)$ solution: return $true$. You can possibly define $f$ in other ways to make the question more or less difficult, as well.

See below a mini-complexity zoo corresponding to different choices of $f$:

for $f(x) = c$, the problem is $O(1)$ (return true iff $c = 0$).
for $f(x) = 0$ for $x \geq 0$ and $f(x) = 1$ otherwise, the problem is $O(n)$ (linear search for any number greater than 0)
for $f(x) = 0$ for $x \geq c$, $c > 0$, $f(x) = 1$ otherwise, the problem is no more than $O(n \log n$) (sort the items in the set in descending order, and see if any prefix sums to a working solution)
for $f(x) = ax + b$, the problem is as hard as subset-sum (in an informal sense, and I don't provide a construction to demonstrate the reduction from subset-sum to this... if I'm wrong about this one, please let me know!)
for $f(x) = 0$ if the Turing machine encoded by $x$'s binary representation halts when given the binary representation of $x$ as input (alternatively, when given the empty tape as input, and similar kinds of halting problems), and $f(x) = 1$ otherwise, the problem is undecidable (a solution to the problem for this $f$ could solve the halting problem)

Anybody see anything else fun?


How to use homomophism in closure proofs?

Prerequisite: you have to understand the basic techniques beforehand (or imagine/search/develop them on the fly).

A string homomorphism or simply a homomorphism maps each character to a single string (possibly in a different alphabet). For example, let $f(a)=ab$ and $f(b)=ba$. Then $f(ab)=abba$ and $(\{a, ab^2\})=\{ab, abbaba\}$.

A string substitution or simply a substitution is a mapping that maps each character to a language (possibly in a different alphabet). For example, let $f(a)=\{x\}$ and $f(b)=\{y, xz\}$. Then $f(ab)=\{xy,xxz\}$ and $f(\{a^2, b^2\})=\{x^2, y^2, yxz, xzy, xzxz\}$. The effect of substitution is not only changing the characters, but also including more variations. A substitution can be considered as the "union" of many homomorphisms.

Instead of explaining the formula $L/R = h(f(L) \cap (\Sigma^*\cdot g(R)))$, let
us discover that formula by trial and error, starting from examining the target, $L/R$.

$L/R$ is made up by words each of which is the prefix of a word in $L$ whose remaining part is in $R$.

So, as a first step, given a word $w\in L$, we want to chop off a part of it. How to chop off a part? Mapping the letters to the empty string! Letting $h(a)=\lambda$, the empty word for all $a\in\Sigma$, we get $h(L)$.

Oh no! We just mapped every word in $L$ to the empty string! That is useless. What we want is to map a suffix that is in $R$ to empty string. For a word that looks like $xy\in L$, we want to chop off $y\in R$. How to carve out the suffixes? That means we should use intersection to target the remaining part. All words that end with a $y\in R$ are $\Sigma^*\cdot R$.

Now $L\cap \Sigma^*\cdot R$ are all the words in $L$ that end with a word in $R$.

Let us apply $h$ to it. Still, all of them are mapped to the empty string. We have to modify $h$ so that it will only map the letters in $R$ to empty string. Well, that is absurd since the letters in $R$ are the same as the letters used by $L$!

Wait. Let us suppose $R$ does use a different set of alphabet. For example, if $abc\in R$, we can imagine that actually means $a'b'c'\in R$. In other words, let us replace $R$ by $g(R)$, where $g(a)=a'$ for all $a\in\Sigma$.

Darn! Now $L\cap (\Sigma^*\cdot g(R))$ is empty. We need to change $L$ the the same way as $g$. Well then, it will not make any improvement. Is there a way to change $L$ to include the result of changing by $g$ as well as keeping itself intact?

String substitution comes to the rescue. We can let each letter in $L$ be itself or itself prime. This last ingenious touch almost concludes our journey. We have
$h(f(L)\cap (\Sigma^*\cdot g(R))$.

What we got are all those suffixes in $g(R)$. However, we should become cautiously confident the solution is within reach since we get something non-trivial and strongly related.

In fact, all we need is letting $h$ preserve $a$ while erasing $a'$ instead. That is, $h(a)=a$ for all $a\in\Sigma$ and $h(a')=\lambda$. There remains some verification to do, but we have gone through the hard part of the journey.

Hopefully, you could gain some understanding if you have followed the above journey.

Here are two related exercises.

Exercise 1. Show that the left quotient $L\backslash R = \{ y \mid \exists x \in L \text{ such that } xy \in R \}$ is regular where $L$ and $R$ are regular. (In fact, the condition $L$ is regular is not necessary.)

Exercise 2. Let $L = \{ w \mid \text{odd}(w) \in L_1 \text{ and } \text{even}(w) \in L_2 \}$, where odd$(w)$ is the string of all letters of $w$ in odd positions and even$(w)$ is the string of all letters of $w$ in even positions. Show that $L$ is regular iff $L_1$ and $L_2$ are regular.


Time complexity for searching $k-th$ element from starting and ending of a linked list

If you start from the beginning, it does not matter how big the list is, you have to go through the links a constant number of times no matter what.

n = 100, n = 1000, does not matter, you just have to follow exactly 7 links (independent of n).


What subfields in computer sciences may one study without learning Object Oriented Programming?

Depending on where you study, you might be able to get a CS degree without Object Oriented Programming, but the chances are slim. Most degrees would require you to take some programming courses using some general purpose languages along the way, and that will often be Java, C++ or similar, and there you have OOP. Hard to avoid.
But that's good for you, because if you want any job outside university, and you have not a clue about OOP, your chances are practically zero to get any job.


Row Major Vs Column Major Order: 2D arrays access in programming languages

The way you access the array affects performance.

It depends on how the matrix is represented and stored in memory.  Often a matrix is stored in row-major order, so that consecutive elements of a row are contiguous in memory.  Reading memory in contiguous locations is faster than jumping around among locations.  As a result, if the matrix is stored in row-major order, then iterating through its elements sequentially in row-major order may be faster than iterating through its elements in column-major order.

Of course, if the matrix is stored in column-major order, the reverse will be true.

See https://en.wikipedia.org/wiki/Row-_and_column-major_order for more on the subject.


Step 2 is just a change of coordinate system from one camera's coordinate system to the other camera's coordinate system.  It's easy to do, using a "change of basis".

The extrinsic parameters of the depth camera tell you how to transform from the depth camera's coordinate system to the world coordinate system (a transform between two 3D coordinate systems).  The extrinsic parameters of the thermal camera tell you how to transform from the 3D world coordinate system to the thermal camera's coordinate system.  If you combine these two transformations, you have a way to transform from Depth_3D to Ther_3D.

So if you have the extrinsic parameters, you should already know how to do this.

See, e.g., https://en.wikipedia.org/wiki/Pinhole_camera_model and https://en.wikipedia.org/wiki/Camera_matrix and https://en.wikipedia.org/wiki/Camera_resectioning, or any textbook that describes camera intrinsic and extrinsic parameters.


An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running times are not polynomial.

There are things in between - for example, the best known algorithm for factoring runs in time $O(\exp(Cn^{1/3} \log^{2/3} n))$ for some constant $C > 0$; such a running time is known as sub-exponential. Other algorithms could run in time $O(\exp(A\log^C n))$ for some $A > 0$ and $C > 1$, and these are known as quasi-polynomial. Such an algorithm has very recently been claimed for discrete log over small characteristics.


No number is equal to Zero, is this statement true or false?

It is false if and only if there is a number that is equal to zero.

"There is a number that is equal to zero" is true if and only if zero is a number. Without any context (there might e.g. be some very strange definitions given earlier in the exercise), we cannot say whether zero is considered a number in this case. If there is no other context given in the exercise, it should be clear that zero is a number.

For example, the domain of discourse might be only positive integers*, when zero is not a number, but then it would be very weird to use the word "zero" in the sentence in the first place.

*The set of natural numbers has two contradicting definitions, $\mathbb{N}=\{0,1,2,\dots\}$ (non-negative integers) and $\mathbb{N}=\{1,2,\dots\}$ (positive integers). This might be the source of confusion in your case.


The tutorial that you link to does not explain what "translating" between Mealy and Moore machines actually means, which is however crucial. In every step of its computation, a Mealy machine first reads the next input character, and then produces the next output character while transitioning to the next state. A Moore machine, one the other hand, first produces the next output character and then reads the next input, after which it transitions to the next state.

These two modes of computation are different and hence there is no translation between them that does not alter the semantics of the machine. When you translate from Moore to Mealy, you can build a machine that ignores the next input, produces the next output, and only then takes input and state into account to transition to the next state. The resulting Mealy machine in a sense ignores the next input until it wrote the next output.

When you translate from Mealy to Moore, you have a problem: to compute the next output, you need the next input....which is only available to the machine after producing the next output. What you can do during the translation is however to build a Moore machine that produces its output delayed by one step. This requires you to store the last output in the state component, which blows up the automaton. Whether the resulting Moore machine is good for anything practical is a different question. Even with this semantics-altering translation, there is still the problem that the Moore machine needs to give some initial output, which needs to be defined. This could be an arbitrary one or a designated "no data" output character. This seems to be the choice of your tutorial - rather than having more than one initial state, you declare the one to be initial that is labeled by the output character representing ``nothing''.

Having to choose some initial output shows you that this is no one-to-one translation.


What is the purpose of learning propositional logic

Briefly, one can't learn AI without it.
Some of the main content areas of AI are based on logic: knowledge representation, planning, natural language semantics and reasoning. Have a look at the leading AI textbook to see this in detail. A lot of this uses first-order logic, but first-order logic and many of the other major forms of logic are built on propositional logic.
AI has either used or created several other kinds of logic: non-monotonic logic, temporal logic, fuzzy logic, intuitionistic logic, and modal logic. Check out this 5-volume set about logic in AI.
Back to propositional logic: in the 90's it was realized that SAT solvers (programs which could find satisfying assignments to most propositional logic formulas) could solve formerly intractable problems in AI planning. This has been an active research field ever since.
Propositional logic also has a number of very desirable properties: it is consistent, complete, sound, and decidable. Not all forms of logic have all these properties. For example, decidability breaks down in first order logic.
Finally, it's worth knowing that a lot of other stuff in computer science is based on propositional logic. Consider one of the fundamental theorems of complexity theory: the Cook-Levin theorem, which provides a theoretical basis of complexity theory by showing that bounded computations in a Turing machine can be modeled with propositional logic.


Modelling using propositions, syntax and standards

Generally you have:

Some boolean variables that collectively represent the current state, say $s,t,u$.
Some boolean variables that collectively represents the inputs, say $i,j,k$.  For instance, you might have one variable per sensor (assuming each sensor returns a boolean value).
Some boolean variables that collectively represents the inputs, say $o,p,q$.  For instance, you might have one variable per actuator (assuming each actuator can be either on or off).
Some boolean variables that collectively represent the next state.  You could give them a different name (e.g., $x,y,z$), but often, to help us remember the relationship to the variables for the current state, we used primed versions of the variables for the current state.  So, the next state might be represented by $s',t',u'$.

Now, we introduce a predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ to represent the transition relation.  The idea is that if this is true, it means the following: if you're in state $s,t,u$ and you receive inputs $i,j,k$, then you output $o,p,q$ AND transition to the state $s',t',u'$.  You can use boolean logic to express the predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ as a boolean formula, using AND, NOT, OR, implication, etc.

Then you also need to describe the initial state of the system.  For instance, it might be $(s,t,u)=(T,F,T)$.

As you can see, the notation can get a bit much.  Often we collect all the variables associated with the current state into a vector $s$ of variables, $s=(s_1,\dots,s_k)$ where the state is $k$ bits (it is represented by $k$ boolean variables), and collect all of the variables associated with the input into a vector $i$ of variables, $i=(i_1,\dots,i_m)$; you similarly collect all the output variables into a vector $o=(o_1,\dots)$; and the next state is given by a vector $s'=(s'_1,\dots,s'_k)$ represents the next state.

As a generalization, you can consider variables that have more than two possible values (they aren't restricted to be booleans).  Booleans are convenient for digital logic implementation, but more general variables can enable a specification that is easier to think about and understand.

So, basically, yes, this is compatible with the kind of approach you were showing.


By definition - for example Herbert B. Enderton - A Mathematical Introduction to Logic-Academic Press (2001), page 53 - simply saying CNF is conjuction of disjuntions or product of sums.

So, as we agreed earlier,
$$(I \lor M) \Rightarrow H = (\neg I \lor H) \land (\neg M \lor H )$$

For $(I \land M) \Rightarrow H$ we can get $\neg (I \land M) \lor H=\neg I \lor \neg M \lor H$ and this last is CNF

For third case for $(\neg I \land \neg M) \Rightarrow H$ answer is analogical $2$d case: $\neg(\neg I \land \neg M) \lor H = I \lor M \lor H$ and this also is valid CNF.

And answer for the last question is yes - $A_1 \lor A_2 \lor \cdots  \lor A_n$ is valid CNF if each $A_i$ is  either a sentence symbol or the negation of a sentence
symbol - it's allowed to have just one conjuct.
Let me add, that one symbol is as CNF, so DNF.


OS: Are User-level threads and software threads (and also kernel-level threads and hardware threads) the same?

Kernel threads and user threads are both software threads. This is only terminology, but I think that hardware threads in your book are the actual CPU cores including hyperthreading threads that the CPU can run at once. So a hardware thread is not instructions or an actual thread, it is simply the threads that the CPU supports. For example, if the CPU has 4 cores and each core uses hyperthreading to have 2 virtual threads each, then you would have 8 hardware threads available for software threads to run.
Kernel threads and user threads are separated by a permission bit in the page tables. Having a thread with a permission of 0 (kernel thread) doesn't make the thread a hardware thread. It is simply a software thread running in kernel mode.


Confusion about definition of languages accepted by Turing Machine, very basic question

Even in a deterministic Turing machine, the transition function $\delta$ may be a partial function i.e. there can be pairs of states and tape symbols for which the transition function is not defined. If the Turing machine is in state $z$ and reads symbol $\alpha$ and $\delta(z,\alpha)$ is not defined then it halts. Usually the accepting states $E$ are implemented by creating states for which the transition function is undefined for all inputs i.e. the Turing machine will always halt once it enters a state $z \in E$, regardless of the symbol it reads from the tape. You may also have other halting states, but if the machine halts in a state $z \notin E$ then it has rejected the input string.


exact matching between two strings - linear edit distance?

As far as I understand you cannot solve the problem in linear time. If in the first string every character a-z is followed by *, the problem coincides with substring matching. So, isMatch("a?a?b?b?b?a?b?a?b?a?","abba") asks whether abba is a subsequence of aabbbababa.


What is the average time complexity, for a single linked list, for performing an insert?

Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space.
If you want to insert at the beginning of the list, you just make the new list head the node you want to insert, and link it to the previous  list head.
If you want to insert at the end of the list, you can also hold the end of the list as a pointer and insert a new node after it.
If you want to insert in an arbitrary place in the list, then linearly going there is going to be the best you can do ( to  my knowledge ).
Statistically  you'll have to go through $(n+1)/2 $ nodes to get through yours.


Minimum number of moves in this Graph Coloring "Game"

The value of $p(G,v)$ is at most $r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that the colors assigned to every pair of adjacent vertices differ on at least one coordinate. Equivalently, $p(G,v) \leq r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that every pair of adjacent vertices gets a different color. Stated differently, $p(G,v) \leq r$ iff $\chi(G) \leq v^r$, where $\chi(G)$ is the chromatic number of $G$. This implies the formula
$$ p(G,v) = \lceil \log_v \chi(G) \rceil. $$
A similar relation should hold for the case of hypergraphs if you use the correct definition of chromatic number.