Articulation Vertex, significance and real world usage? This question is not about any particular algorithm to look for articulation vertices (cut vertices) in a graph but rather seeking real world applications of algorithms involving such vertices.

I am going through Skienna's The Algorithm Design Manual and it gives an example of an articulation vertex in a telephone network as an approachable example.

Personally, I think there may be applications in networking where multipathing is implemented using more than one switches between the same set of connected hosts to provide tolerance against failure of one of the switches. But still, an algorithm to look for an articulation vertex is not directly applicable in this scenario.

Are there any real world examples of articulation vertices and how looking for them helps solving problems arising due to such vertices ?

EDIT:

Just adding a bit more food for thought. I think simulation based applications or maybe gaming could have some applications ?

For e.g. a game engine may generate some graph based entities on the fly, let's say a building which a player must go into in a FPS game. For testing the the on the fly part, it may be useful to look for parameters which may generate buildings(graphs) which are biconnected (or higher connected) for easy or easier settings where as graphs with articulation vertex can be considered to be hard settings.
(Easy or hard here are relative terms and the semantics may be even reversed depending on the outcome of players' entering the graph)

First, yes, probably.  One example is when we wish to split the graph into its sets of biconnected components.

Second, I think you misunderstand the purpose of the exercise.  The goal is to teach you to think in terms of graph algorithms, not necessarily give you the solution for existing real world problems.

Most real world problems differ slightly from textbook exercises and examples.  But the goal is to give you a toolbox so you can handle similar problems.

It is also important that you understand what an articulation point (or a cut vertex) is, as well as the similar concept for edges (bridge), so that you get a better understanding of graphs and graph connectivity.  It is crucial to understand the concept of cut vertices and bridges before lifting the definitions to their more general versions on vertex- and edge-connectivity (separators and cuts).


efficiently find connected components in undirected graph considering transitive equivalence I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By "equal" I mean transitive equivalence:
 If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx
import itertools
from matplotlib import pyplot as plt

EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}

def foo(u, v):
    # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.
    return (u, v) in EQUAL_EDGES

def main():
    g = nx.Graph()
    g.add_nodes_from(range(1, 5 + 1))
    for u, v in itertools.combinations(g.nodes, 2):
        are_equal = foo(u, v)
        print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
        if are_equal:
            g.add_edge(u, v)

    conn_comps = nx.connected_components(g)
    nx.draw(g, with_labels=True)
    plt.show()
    return conn_comps

if __name__ == '__main__':
    main()

the problem with this approach  is that I get many redundant checks that I would like to avoid:

1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2!=3  # redundant check, if 1==2 and 1==3 then 2==3
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok

I want to avoid running in O(n^2) time complexity.
What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?

Using depth-first search, compute the connected components, by constructing a mapping that maps each node in a connected component to the first node you visited in that component. This is linear in the number of nodes and edges. Preserve that mapping. Two nodes are equivalent if and only if they map to the same node.


How do I solve this graph with Dijkstra's Algorithm? I just drew this graph completely random:

I found the shortest path (marked in red) by simply checking everything. But the reason was to use Dijkstra's algorithm. But when I try I get stuck in a loop. Lake a look at my calculations:

How to read it is:

Top Row: Wich node
Section t: Total distance traveled
From: Wich node did I come from
The 10 over S and every other section can be read like this

To come from S to node 1, the complete path takes 10 time units

So, if you try to follow Dijkstra's algorithm you will get something like this:
S->D->C->5->4->6->D->S->5->4->6->D->(and so on)

I get stuck in a loop. I understand that when I return to S I can reset the time to 0, witch make at least the first bit correct, S->5->4, but than it get stuck.

How are you supposed to solve a problem like this based on how the algorithm is formed? For me, it is obviously stupid to just go around this route, but for an algorithm it is not.

Thank you in advance!

Firstly, I suggest that you start off with a simple graph (5 nodes would do). I believe you are mixing Dijkstra with A* search algorithm and are trying to perform A* search (even without knowing it).

For Dijkstra:

Assign to each node a distance value. 0 for initial node and infinity for all other nodes (since they are not visited)
Set initial node as current. Mark other nodes as unvisited. Create a set of all unvisited nodes.
For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
When we are done considering all of the neighbors of the current
node, mark the current node as visited and remove it from the
unvisited set. A visited node will never be checked again.
If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity, then the algorithm has finished.
Otherwise, select the unvisited node that is marked with the
smallest tentative distance, set it as the new "current node", and
go back to step 3.

If you need more help on this method, let me know!


An algorithm to generate all connectible pair combinations In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know where to start. In this example let's assume that we have 3 value pairs

1 2

2 3

3 1

The aim of a riddle is to make as much UNIQUE pair connections as possible. So the first KeyValuePair can connect on value 2 of second KeyValuePair, whereas second KeyValuePair can connect on number 3 of third KeyValuePair. Start and End key can not be the same. Here is a graphical representation of the expected result:

Valid combinations:

1 2  (1 - 2 connection)

2 3  (2 - 3 connection)

3 1  (3 - 1 connection)

1 2, 2 3 (1 - 3 connection)

1 2, 3 1 (2 - 3 connection)

2 3, 3 1 (2 - 1 connection)

Invalid combinations:

3 1, 1 2 (3 - 2 connection, duplicate)

2 3, 1 2 (3 - 1 connection, duplicate)

3 1, 2 3 (1 - 2 connection, duplicate)

1 2, 2 3, 3 1 (connection: 1 - 1, not unique, 'Start' and 'End' key can not be the same)

I hope I did not miss anything :). A graphical representation of joining would be:

Pair 4 1 was added for the sake of demonstration. In a real world application I expect there to be 100+ pairs. Therefore an algorithm must be efficient. Also (sorry if this is too much) I will need to make sure that there are no more than 3 pairs in a chain (therefore above image is not entirely correct)! But this requirement can be ignored right now, for the sake of simplicity. How to design an algorithm like this?

EDIT:
Based on comment replies I think I need to provide additional explanation of the real use-case for this algorithm. In reality there will be currencies instead of numbers. So EUR/USD is 1 - 2, USD/RUR is 2 - 3, RUR/EUR 3 - 1, in that case (EUR/USD - USD/RUR) is also 3 - 1, but fundamentally it is different kind of conversion! What we are searching here is basically how every currency can be converted to any other currency. For that same reason EUR/USD - USD-RUR - RUR/EUR (= EUR/EUR) is not a valid case. Hope that explains it a bit better.

Model the whole thing as a directed graph.

Currences are nodes.
Conversions are edges.
Conversion factors are edge weights.

So, in your example, you'd have nodes EUR and USD, and edges from EUR to USD with weight 2  resp. from USD to EUR with weight 1/2.

Now, every (directed) path from one currency to another represents a potential series of conversions, and the total conversion factor is the product of all traversed edge weights.

Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. Furthermore, finding the "longest" path may be NP-hard.


Is it possible to transmit bits digitally? I have learnt that all data transmission is analog. Is there any mediums that could transmit bits digitally?

HDMI interface is one example of being able to tranmit high-speed digital data. It works using an encoding technique called TMDS (Transition Minimized Differential Signaling) which you can read more about here
Also, HDMI can only be used with older analog-only devices (using connections such as VGA, etc.) by means of a digital-to-analog converter or AV receiver, as the interface does not carry any analog signals from Wikipedia


Why doesn't Knuth's linear-time multiplication algorithm "count"? The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of logarithmically-sized multiplications. It runs in linear time.

The article acts like this algorithm somehow doesn't count as a "true" multiplication algorithm. More significantly, it's considered to be an open question whether multiplication can be done in even O(n lg n) time!

What details of this algorithm disqualify it from counting as a "true" multiplication algorithm?

My guesses are:

Precomputing the table takes more than linear time. On the other hand, it can still be done in n lg n time so that would still seem to be impressive.
Random access is somehow not allowed. But then why can other algorithms use things like hash tables and pointers?
It somehow scales wrong as you increase a machine's word size, like if you have a 256 bit machine that does 256 bit multiplications in a single instruction then there's no point to this algorithm until you have more than 2^256 elements. On the other hand, we bother with the inverse-ackermann factor in union-find.
The "is there a linear time multiplication algorithm?" question is secretly in terms of some weaker machine, but this only gets hinted at.

While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called RAM machine, in which variables are allowed to hold integers of size $O(\log n)$, where $n$ is the size of the input. The bit complexity is, however, $O(n\log n\log\log n)$, and for this model, Fürer's algorithm is faster.

The quest for fast integer multiplication algorithms in the literature has concentrated on bit complexity as the complexity measure; this is like allowing your registers to hold only one bit (or only $C$ bits for some arbitrary constant $C$). It is expected that integer multiplication takes $\Omega(n\log n)$, though it's not clear whether this should be tight, and no non-trivial lower bounds are known (so this $\Omega(n\log n)$ is just a conjecture).

For a discussion of the "correct" model for practical multiplication of large integers, check Fürer's recent paper. His conclusion is in favor of the "practical" Schönhage–Strassen algorithm (there are two of them, and the other one has better bit complexity but performs worse in practice; Fürer addresses this issue in the paper).


Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure? I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of data structure (array of small integers with a sign). How could you encode the BigInt as a sequence of bits, and how would you decode it? I don't see how to properly perform the bitwise manipulations or how to encode an arbitrary number in bits larger than 32 or 64. If a language is required then I would be doing this in JavaScript.
For instance, this takes bytes and converts it into a single bit stream:
function arrayOfBytesTo32Int(map) {
  return map[0] << 24
    | map[1] << 16
    | map[2] << 8
    | map[3]
}

How would you do that same sort of thing for arbitrarily long bit sequences?

Look at Elias delta or gamma coding as an example.


Complexity of algorithm inserting an element in a circular linked list at the front end In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here)

But in a book currently, I have, it is mentioned that it is done in O(n) (the usual method). I also saw few lecture ppts, they all mention the usual method of traversing the list & adding an element.

My question is :

In practical scenarios which method is used ?
I am about to attend an exam, which consists of MCQs, if above question is asked shall I mark O(n), since that is the standard answer ?

The method used in practical scenarios depends on the scenario (and on the programmer). There are several possible issues influencing the choice of implementation:

Whether the algorithm is known to the programmer.
Ease of coding (it's easiest if it's already implemented in some library you can use).
Speed - that depends on how the data structure is used.
Space overhead taken by the data structure.

An intelligent programmer should take all of these into account, and try to make themselves more knowledgeable of various algorithms and data structures.


Storing a playlist as plain text file What are the disadvantages of storing a playlist as plain text in a text file?

This is what I thought:

The main disadvantage of storing the play list as plain text is its simplicity. The basic conceptual structure of the rows of values can be very inefficient and inappropriate for data sets with complex structure. The low-level format of storing everything as characters with one byte per character is very inefficient in terms of amount of computer or phone memory required. It can also lead to massive redundancy (repetition of values). The speed of access and space efficiency for large data set is also not ideal. The second disadvantage is the fundamental structure of plain text file format means that each line of the file contains exactly one record or case in the data set. This only works well when a data set only contains information about one type of object. However, this is not the case as storing the playlist would mean that we also need to store all the information about the songs such as the name and song time. So there would be information about two different types of objects. A plain text file format does not allow for sophisticated data models. A plain text format is unable to provide appropriate representation of complex data structure like a playlist.

Now my question is instead of storing the playlist as plain text in a text file, what would be a more suitable way of storing objects? Please explain. Thank you.

I don't see anything wrong with storing a playlist as a plain text file.  Simplicity is not a disadvantage.  It's likely to be more than efficient enough, given the size of a typical playlist (implement it and see!).


multithreading - duration of jobs " How long will it take for 2 jobs to complete if they're running in parallel, knowing that both have a total of 20 minutes of CPU usage time and 50% IO"

I calculated the CPU usage: 1-0.5²=75%.
To my understanding, if they're running sequentially, time needed to completion is 80 minutes (each job needs 40 minutes to complete)
therefore time needed to complete both jobs in parallel is 75% * 80 = 60 minutes.

However here is the correct answer:

" CPU utilization is 75%. Thus each one gets 0.375 CPU minute per real time minute. To accumulate 20 minutes of CPU time, a job must run 20/0.375=53.33 minutes. Thus, in parallel, time to completion for both jobs is 53.33 minutes".

I don't get where the 0.375 came from ?

What are CPU minutes ?

Help is appreciated

I don't get where the 0.375 came from ?

If the CPU utilization is 75%, and it's shared equally between two process, each of them gets 37.5%.

  What are CPU minutes?

A CPU-minute is the amount of work done by one CPU in one minute.


Proving landau notation statements If we have the function $f : \mathbb{N}_0 \rightarrow \mathbb{N}$ with $f(n) = n^2$ and we look at the following representations of the sets $\mathcal{o}(f),\mathcal{O}(f),\Theta(f),\Omega(f),\omega(f) $:

Now I have to list all necessary statements which are proving that the illustration is correct.

The necessary statements are in my opinion:

\begin{align}
\Theta (f)&\subseteq \mathcal{O}(f) \\
\Theta (f)&\subseteq \Omega (f) \\
\Theta (f)&= \mathcal{O}(f) \cap  \Omega (f) \\
\omega (f)&\subseteq \Omega (f) \\
\hbox{o}(f)&\subseteq\mathcal{O}(f) \\
 \, \emptyset &=\, \omega (f) \cap \hbox{o}(f)
\end{align}
Now I have to proof two statements of my choice. But how to proof that in a formal correct way. (I understand the intuitive proofs but I don't know how to do it formally correctly.)

Hope somebody can help.

Here is an explanation by example. Let $\Theta'(f) = \{ g : g(n)/f(n) \text{ tends to a positive limit} \}$. I will show that $\Theta'(f) \subseteq \Theta(f)$. The first step is to write the definitions. There are several variants of the definitions, and I picked one arbitrarily; you should use the definitions that were stated in class.

  Let $f\colon \mathbb{N} \to \mathbb{N}$.

  $\Theta'(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $x \in \mathbb{R}_+$, $\lim_{n\to\infty} g(n)/f(n) = x$.
  $\Theta(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$, for all $n \geq n_0$ it holds that $a f(n) \leq g(n) \leq b f(n)$.

The next step is to take a function $g \in \Theta'(f)$.

  Let $g \in \Theta'(f)$. Then there exists a positive $x \in \mathbb{R}_+$ such that $$ \lim_{n\to\infty} \frac{g(n)}{f(n)} = x.$$

Finally, we have to show that $g \in \Theta(f)$. For that we have to come up with positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$ such that $af(n) \leq g(n) \leq bf(n)$ for all $n \geq n_0$.

  By the definition of limit, there exists $n_0$ such that for $n \geq n_0$,
  $$ \left|\frac{g(n)}{f(n)}-x\right| \leq \frac{x}{2}. $$
  Therefore for $n \geq n_0$,
  $$ \frac{x}{2} \leq \frac{g(n)}{f(n)} \leq \frac{3x}{2}, $$
  implying
  $$ \frac{x}{2} f(n) \leq g(n) \leq \frac{3x}{2} f(n). $$
  Taking $a = x/2$ and $b = 3x/2$, we see that $g \in \Theta(f)$.

Only the latter two steps really belong to the proof. The first one states the claim. It is a very important step — without knowing what you're trying to prove, you won't be able to prove it.


Is this an abuse big O notation as a power of a number? Theorem 7.11 in Introduction to the theory of computation 3rth edition says

  Let $t(n)$ be a function where $t(n)>n$. Then every $t(n)$ time
  nondeterministic single-tape Turing machine has an equivalent
  $2^{O(t(n))}$ time deterministic single tape Turing machine.

I can understand that in this proof when we have a nondeterministic TM which every node in it can at most go to $b$  other nodes in its computation tree, then the time complexity of a deterministic Turing machine simulating it would be $O(t(n)b^{t(n)})$. But I'm not sure if I understand the $2^{O(t(n))}$ correctly.

Does it means that if $f(n) \in 2^{O(t(n))}$ then
$\exists b\in \mathbb{N} \; f(n)\in O(b^{t(n)})?$

On the other hand, the claim 1.5 in the Computational complexity book says

  For every $f : \{0, 1\}^∗ \rightarrow \{0, 1\}$ and time-constructible
  $T : N\rightarrow N$, if $f$ is computable in time $T(n)$ by a TM $M$
  using alphabet $\Gamma$, then it is computable in time $4 log |\Gamma|T(n)$
  by a TM $M$ using the alphabet $\{0,1,\square,\rhd\}$.

So every nondeterministic TM M running in $t(n)$ time can have an equivalent nondeterministic TM using $\{0,1\}$ alphabet running upper hand in $|\Gamma|^2t(n)$. Thus this equivalent TM's computation tree has at most 2 different branches in each step. Then we can have a deterministic simulator of that TM running in time $O(2^{|\Gamma|^2t(n)})$.

The intersection of 2 above statement suggests that carelessly we can say $O(2^{t(n)})=2^{O(t(n))}$, but we know $\forall b>2,\; b^{t(n)}\notin O(2^{t(n)})$.

Unfortunately, I didn't find any definition of $2^{O(t(n)}$. I wish to know is there any formal definition for $2^{O(t(n))}$?

-
Edit: There is a similar question here. But I'm doubting its answer is the same since the big O notation in the power is not just $O(1)$.

Suppose we have nondeterministic TM that each node of it goes to 3 other nodes. Then there is a deterministic Turing machine that simulates it in time $t(n)3^{t(n)}$. So we can't say that there is a constant $k$ that $t(n)3^{t(n)} < 2^{kt(n)}.$

Meanwhile, when I think more, this definition holds if we ignore the Sipser proof. I mean if we begin the proof by the statement that every nondeterministic TM has a version $\{0,1\}$ alphabet running in $c.t(n)$ then the answer's definition is correct.

I wonder if there is bad use of big O notation in the Sipser's book or $2^{O(t(n))}$ has a different definition.

This is perfectly standard use of big O notation, despite some purists disliking it. Here is what the passage you quoted means:

Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) = O(t(n))$.

This is still somewhat ambiguous, since it’s perhaps not clear what variables the big O depends on. In this case, big O hides a universal constant:

There exists a constant $C>0$ such that the following holds.
Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) \leq Ct(n)$ for all $n$.

This allows us to rephrase the statement in yet another way:

There exists a constant $C>0$ such that the following holds.
Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{Ct(n)}$ time deterministic single tape Turing machine.

(This assumes that by “$f(n)$ time machine” we mean a machine running in time at most $f(n)$.)


Sort array of 5 integers with a max of 7 compares How can I sort a list of 5 integers such that in the worst case it takes 7 compares?  I don't care about how many other operations are performed.  I don't know anything particular about the integers.

I've tried a few different divide and conquer approaches which get me down to 8 compares, such as following a mergesort approach, or combining mergesort with using binary search to find the insertion position, but every time I end up with 8 compares worst case.

Right now I'm just looking for a hint, not a solution.

There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between.

The first comparison is easy: you have to compare two keys, and since you don't know anything about them, all choices are equally good. So let's say you compare $a$ and $b$, and find that $a \leq b$. You now have $2^6 = 64$ possible answers left, and $60$ possible permutations remaining (since we have eliminated half of them).

Next, we can either compare $c$ and $d$, or we can compare $c$ to one of the keys we used in the first comparison. If we compare $c$ and $d$, and learn that $c \leq d$, then we have $32$ remaining answers and $30$ possible permutations. On the other hand, if we compare $c$ with $a$, and we discover that $a \leq c$, we have $40$ possible permutations remaining, because we have eliminated $1/3$ of the possible permutations (those with $c \leq a \leq b$). We only have $32$ possible remaining answers, so we're out of luck.

So now we know that we have to compare the first and second keys, and the third and fourth keys. We can assume that we have $a\leq b$ and $c \leq d$. If we compare $e$ to any of these four keys, by the same argument we used in the previous step, we might only eliminate $1/3$ of the permutations remaining, and we're out of luck. So we have to compare two of the keys $a,b,c,d$. Taking into account symmetry, we have two choices, compare $a$ and $c$ or compare $a$ and $d$. A similar counting argument shows we must compare $a$ and $c$. We can assume without loss of generality that $a \leq c$, and now we have $a \leq b$ and $a \leq c \leq d$.

Since you asked for a hint, I won't go through the rest of the argument. You have four comparisons left. Use them wisely.


Reassigning BT root and its children Given the root of a binary tree, for instance below, I am running the following tests in Python:
     1
    / \
   2   5
  / \
 3   4

Test 1:
cur = root
root = None
print(root, cur)
None, node 1

Test 2:
cur = root
root.left = None
print(root.left, cur.left)
None, None

In both tests cur and root point to the same memory location. In test 1, why changing root to None did not modify cur? But in test 2 when I assign root.left to None, cur.left is also changed?

Variable cur and root points to the same object at the start. Think of it as assigning an object two names - root and cur.
In test1 you changed the object pointed to by root. This means that the name root has been assigned to a different object. However, cur remains to be the name of the object at the start. So now root and cur do not point to the same object.
In your test2 you did not change the object pointed by root, but you modified the object shared by both cur and root, through root so changes to this shared object will be reflected in both.
Try to read this for more info https://realpython.com/python-variables/


How can I prove the correctness of this exponentiation algorithm using induction? I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
Exp(n)
    If n = 0
        Return 1

    If n is even
        temp = Exp(n/2)
        Return temp × temp
    Else
        temp = Exp((n−1)/2)
        Return temp × temp × 2

$Exp(0) = 1 = 2^0$ is trivially correct (hard coded) by the algorithm.
Assume the algorithm holds for values of $n$ up to $k$. Now consider the algorithm for input $n = k+1$. We compute $Exp(n) = Exp(k+1)$ using the algorithm:
In the case that $n = k+1$ is even:
The algorithm computes $temp = Exp(\frac{k+1}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k+1}{2}}$ because we assumed the algorithm is correct for values up to $k$ [1]. The algorithm correctly returns $temp*temp = 2^{\frac{k+1}{2}}*2^{\frac{k+1}{2}} = 2^{k+1}$.
In the case that $n = k+1$ is uneven:
The algorithm computes $temp = Exp(\frac{n-1}{2}) = Exp(\frac{k+1-1}{2}) = Exp(\frac{k}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k}{2}}$ because we assumed the algorithm is correct for values up to $k$ [1]. The algorithm correctly returns $temp*temp*2 = 2^{\frac{k}{2}}*2^{\frac{k}{2}}*2 = 2^{k+1}$.
i.e. since $Exp(0) = 1$ is trivially correct by the algorithm and we showed that the algorithm is correct for $Exp(n+1)$ if $Exp(n)$ is correct; it follows that the algorithm is correct for every $n \geq 0$.
[1] Technically you also have to show that $\frac{k+1}{2} \leq k$ and $\frac{k}{2} \leq k$ for every $k > 0$ but that seems easy enough to prove.


What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete? This question is not meant to be too theoretical or nitpicky. I have experience programming, so I'm trying to get a better understanding of what it takes to get Turing-completeness by using my intuition about practical programming languages.

Basically: What minimal elements of a language like Javascript do we need to have Turing completeness, and why? (I'm pretty sure we don't need interfaces or subclasses, etc).

Extra question: Is there a simple, natural polynomial-time reduction from a language like Javascript/C++/C# to a Turing machine?

It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all three languages.

The While language is also good for an intuition of Turing completeness. You need

Potentially infinite loops, because Turing complete computations may not terminate.
Condition-dependend behaviour, so that you can break out of loops (important: in contrast to for loops, the time after which the loop ends is not be known in advance).
A data type with an infinite domain.

In both examples I gave above, the third ingredient is the type of integers of unbounded size. Arguably, it is not natively supported in C++ (I do not know about JavaScript or C#. A "normal" programming that has it is Python 3.)
You promised not to nitpick, but if you did one would have to either

replace your languages by "conceptual" variants thereof where integers are unbounded, or
implement unbounded integers in a library (like GNU MP). When you do that, you inevitably use the "true" third ingredient of your languages: They achieve infinite-domain data through dynamic allocation.

All of the above would as well hold for C. Yet your question, at least the title, is specifically about OOP languages. Basically, your three languages are extensions of C by objects. My Turing-complete subsets then discard these extensions. At the moment I cannot come up with natural subsets of any of these languages where some OOP feature is essential for Turing completeness.

As for simple, natural, polynomial time reductions to Turing machines: Polynomial time is possible, natural in a sense, simple I do not think (such a reduction is a full-feature compiler for the language, so it cannot be any simpler than the language is).
Let there be three tapes. One for the heap, one for the stack and one for indexing. The heap and the stack would contain sequences of substrings like [1010011] which encode unbounded integers (83 in this case). When used as pointers, these integers are somehow mapped to positions in the heap or the stack. Indexing an element of the heap or the stack works by copying the pointer to the indexing tape and then moving to the respective part of the tape by using the indexing tape as a counter.


What is an algorithm to find the largest rectangle of white space in an image? Take an image, (the Google home page) is a good example.

I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.

Do you know any algorithms that would do this?

Subtract $254.9999999$ from all pixel values, so black corresponds to $-254.9999999$ and white to $0.0000001$.

Find the 2D subrectangle with maximum sum.  There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/).  As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).

Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if  you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.


Does KMP Algorithm handle finding multiple matches in overlapping cases? I am wondering if KMP algorithm can find multiple matches in a given string when there is an overlap.

Here is an example.

  Word to Search from (S): abcabcabc
   Search word (W): abcabc

If you look at "W", it matches "S" from index 0 as well as from index 3

(abcabc)abc
abc(abcabc)

When I looked at the pseudo code on Wikipedia and implemented it, KMP algorithm seems to return only after the first match ((abcabc)abc).

Am I implementing it wrong or does KMP doesn't handle overlapping cases?

This most likely is dependent on the implementation. The failure function is used when the matching of "next" character fails, thus falling back to a prefix of the pattern which is the longest proper suffix up to that point.

Now when we find a match, we are at a accepting state. This accepting state has no need to look at the "next" character because it accepts no more characters thus it should automatically fail at the next character. This is easier to see in a String Matching DFA. Note that this comparison is valid because KMP is based on a string matching DFA.

We can create a DFA for "ABCABC" (dotted lines are failure functions):

The accepting state automatically fails on whatever input is next, but should pick back up at state 3. So if you implement the failures correctly, it should continue to find the overlapping occurrences.

If you look at the worked examples of the failure function you can see the last state (accepting state) has the length of the longest suffix which is also a proper prefix. This is what you should use to "auto-fail" back to after finding a match. I believe this is also captured in the pseudocode for KMP, where it sets m and i:

  ...
    if i = length(W) then
      return m (or store/use occurrence)
      let m = m + i - T[i], i = T[i] (preparing for search next occurrence)
  ...

The return here should be removed if you want to find more than one match.


For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular? In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$.  The subsequence is proper if $k < n$ and $k > 0$.

With this definition given, a homework problem asks the following: Suppose $L$ and $L_1$ are languages, and define $L \diamond L_1$ to be the set $\{x \in L : \text{no string }  x' \in L_1 \text{ is a proper subsequence of } x\}$.  If both $L$ and $L_1$ are regular, does it follow that $L \diamond L_1$ is regular?  Justify your answer.

I've attempted to construct an NFA that would recognize $L \diamond L_1$, but this went nowhere, as things soon got overly complicated.  Any ideas or suggestions?

Since this is a homework question, I'll just give a hint.

Hint: Let $L_2$ be the set of supersequences of words in $L_1$, i.e.,

$$L_2 = \{x \in \Sigma^* : \exists y \in L_1 . \text{$y$ is a subsequence of $x$}\}.$$

If $L_1$ is regular, what can you say about $L_2$?  Is it regular?  If you have a NFA for $L_1$, can you construct a NFA that would recognize $L_2$?

If you are not sure, try some examples of regular languages $L_1$, and work out $L_2$ looks like for each example.


alpha equivalence of lambda calculus I am pretty new in λ calculus. And I am now trying to understand Alpha equivalence. Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one? Here is one example:
 (λx.(λx.x(λy.x)x)x)x

And by applying alpha equivalnce I can rewrite it to:
  (λw.(λz.w(λy.z)z)w)x

Is my understanding correct ?

Here is one example:
 (λx.(λx.x(λy.x)x)x)x

And by applying alpha equivalnce I can rewrite it to:
 (λw.(λz.w(λy.z)z)w)x

Is my understanding correct ?

There is a small error in your rewriting: at λz.w you have changed the meaning of the expression, because now the bound variable refers to the outer lambda abstraction, instead of the inner lambda abstraction as before. Instead, it should be λz.z. Other than this, the rewriting is correct.

Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one?

Yes, this understanding is correct.


Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class I am trying to understand the space and time Hierarchy theorems according to

  Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach

but the more general case.

What I don't understand is why the language decided by our custom machine is in the larger complexity class. For example, with the case of time complexity, the cost of simulating the input machine is $t_1 \log t_1$, so why is the language decided by it in $DTIME(t_2)$ but not in $DTIME(t_1 \log t_1)$?

thanks

A rich man walks into a bar and says, "I can buy this beer because I am a millionaire." Eloo says, "The beer costs \$5. I don't understand why this millionaire can buy it, but this guy with five dollars can't."

Remember that $\mathrm{DTIME}[f(n)]$ is the class of languages that can be decided by a deterministic Turing machine that uses at most $f(n)$ steps on any input of length $n$. So, since $t_1\log t_1\leq t_2$, anything in $\mathrm{DTIME}[t_1\log t_1]$ is in $\mathrm{DTIME}[t_2]$.


Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best") The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the total value of my items but I am willing to accept a "good" order if it means finding it quickly.
The Problem (in maths)
Given $N$ monotonically decreasing functions $f_i$(x) where $1 <= i, x <= N$ and a set $S = \{1, 2, 3, ..., N\}$
Find $\alpha$, a permutation of $S$ which maximizes the objective function $g(\alpha) = \sum_{i=1}^{N} f_i(\alpha(i))$
In the event that this is a hard (e.g. NP-Complete) problem, I would rather have an approximation algorithm which returns a permutation that gives some local maxima of $g$ with provable guarantees on the distance to the optimal one.
My Thoughts
I am not very familiar with optimization problems but this feels like one that should be well known. I feel that if I knew the name of it I would have been able to search it on my own.
I am able to put more constraints on $f_i$ if needed but I would prefer to allow it to be any monotonically decreasing function.
I cannot brute force this as the values of $N$ I work with lead to far too many permutations.
My initial thought was to use a greedy algorithm which chooses the highest valued remaining item starting with position 1 and iterating until position N. I know this will not produce the best result but it is possible it produces a "good enough" result. I am not comfortable with using this greedy algorithm unless I have a proof of how effective it is.

One approach is to view this as an instance of the assignment problem: you have a bipartite graph, with items on the left and positions on the right, and $f_i(p)$ tells you the value of matching item $i$ to position $p$, so draw an edge $i \to p$ with weight $f_i(p)$, and then find the maximum-weight bipartite matching.  This will give an optimal solution.  It also demonstrates that the problem can be solved in polynomial time, i.e., it is not NP-hard.  The running time will be $O(n^3)$, which might be reasonable if $n$ is not too large but might be too expensive if $n$ is very large.
It might be possible to find some other algorithm that is more efficient (i.e., has faster runtime), by taking advantage of the fact that each $f_i$ is monotonically decreasing.


A fuzzy string matching algorithm for finding all occurrences from a set of strings in a large string I have thousands of documents, and a term list with thousands of entries. The entries in the term list range in length from an acronym of two characters to a 14-word phrase with 96 characters. I would like to find every occurrence of any term in the term list in each document in the order that they appear.

I have created two test implementations so far: one using the Aho-Corasick algorithm and the other using n-gram matching. I tested them both on a medium-sized document (8 MB). The Aho-Corasick algorithm came up with over 8700 matches in 24 seconds. This would be great, except that I would like to use a fuzzy matching algorithm, and Aho-Corasick only finds exact matches. N-gram matching found 9600 matches, since some of them are approximate, but it took 885 seconds!

As such, I would like suggestions on an efficient fuzzy matching algorithm for finding matches from a set of strings. Is there any way to modify the current code I have for the Aho-Corasick algorithm so that it can take into account Levenshtein distance? I have found some other questions on this site that are related, but I didn't feel like they solved my problem. Thanks.

One approach: Build a BK tree containing the terms in your term list.  Given any word $w$, this lets you efficiently find the term that is closest to $w$ in Levenshtein edit distance.

Now the problem becomes easy.  Do a linear scan over the document.  For each word, look it up in the BK tree to find the closest match in your term list, and if it is close enough, output it.

Alternatively, you could read Peter Norvig's tutorial on spell checking, and the references he lists there, and try using that.  They might be especially effective if your fuzzy matching only considers very small Levenshtein edit distance (e.g., distance 1 or 2).


Do problems that have unary encodings automatically become unary languages? This problem has confused me a lot, can any of you help me out.
Thank you.

A unary language is a subset of $\sigma^*$ for some letter $\sigma$. If your language is of this form, then it is unary. Otherwise it isn't.

A unary encoding is an encoding of some data as a subset of $\sigma^*$. For example, one possible unary encoding of the natural numbers is $n \mapsto 1^n$. Any language in which instances are unary encoded is a unary language, simply because it is a subset of $\sigma^*$. For example, the language of all primes encoded in unary is a unary language.


Algorithm: Finding median in a sorted array with duplicates If array is sorted we can generally find median in O(1) by returning the element at the middle.
But what if there are duplicates?

E.g [2, 2, 3, 3, 3, 3]

Yes. Even with duplicates, the process of finding median is same. See  this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice


How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes So here's the problem:

-You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid square is empty)

-You must minimize the number of empty grid squares by filling this grid with Tetris shapes which are each composed of exactly 4 blocks (a block is 1x1)

What is an algorithm that can consistently do this given any mxn partially-filled grid?

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X.

Consider the set of choices you have:
For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the board. Let matrix $A$ be our exact cover matrix. The columns of $A$ are the constraints that must be satisfied exactly once i.e. there is a constraint for every unfilled grid location on the given board. Each row represents a "choice" i.e. a tetris piece, orientation and location and has $1$s in only the columns which correspond to the locations that that placement of the tetris piece would cover.

To account for the grid locations that have already been filled, we make sure that any row is removed that would either

Fall outside of the $m$x$n$ grid
Cover one of the cells already covered in the given $mxn$ grid

Then it remains to select a subset of rows $S$ such that for each column $i$:
$$\sum_{row\in S}row[i] = 1$$

Algorithm X is one way of solving this problem (with the help of the dancing links technique. Other algorithms exist as well (AC3 is taught as an introductory constraint-satisfaction solver algorithm at some universities). Soduku puzzles are another example of exact cover problems.

Notice that max cover is a decision problem, whereas the question you posted is an optimization problem. This can be addressed by just searching for the maximum number of columns covered over the search. Of course this will result in a much slower runtime since you will have to run the algorithm for longer. You may benefit from introducing some heuristics into your search as well. For example, say you are at some point in your search where:

The best cover you have seen so far covers $s$ locations.
Your current cover covers $k$ locations.
There are $x$ remaining open locations on the board that are part of a connected group of at least 4 open locations.

If $k+x\leq s$, you can cut the search tree off here, since there is no way this current layout of tiles can lead to a better solution that the one you have already found.


Determining the linear address So I am working on a question that requires me to find the linear address.

Here's some information:
Main memory size is 8GB, which translates to $2^{3} * 2^{30} = 2^{33}$.
Block size is 16KB each, which translates to $2^{4} * 2^{10} = 2^{14}$.

I was then required to find:

(i) The number of blocks in main memory:
 $2^{33}/2^{14} = 2^{19}$ blocks.

(ii) The number of bits required to address a block:
$19$ bits.

(iii) The number of bits required for an offset within a block.
I am not so sure if I did this bit correctly, but I ended up with:
$2^{14}$ bits.

These are the parts that I'm having trouble calculating or knowing what to do. Can I be guided accordingly, please?
(iv) The linear address for:
(a) Block 32, byte 100 (b) Block 1000 byte 1800.

(v) The block and offset of a byte for the linear address:
(a) 32431 (b) 232156

Suppose that a memory of size $M$ is divided into blocks of size $B$:

Block 0 consists of cells $0,\ldots,B-1$.
Block 1 consists of cells $B,\ldots,2B-1$.
Block 2 consists of cells $2B,\ldots,3B-1$.
Block $k$ consists of cells $kB,\ldots,(k+1)B-1$.

The "linear address" of a cell is its address in the memory.

Another way of addressing it is by giving which block it belongs to, and what is its offset inside the block. For example, linear address $B+2$ corresponds to block 1, offset 2.

Given a block and an offset, you can easily compute the corresponding linear address; and given the linear address, you can easily compute the block and the offset. Rather than spelling out the arithmetic, I challenge you to come up with the requisite formulas. Using these formulas, you can complete your exercise.


Represent there are infinitely many in FOL How to represent in first order logic the expression:

  "there are infinitely many"

To be honest I'm confused and not even sure whether you can represent them in first order logic.

The existing answers provide examples of contexts where "there are infinitely many" can be expressed. However, there is an important sense in which "there are infinitely many" cannot be expressed in a first-order way without some additional context restrictions:

Specifically, fix your favorite first-order language $\Sigma$. Then it's a consequence of the compactness theorem that there is no $\Sigma$-sentence $\varphi$ which is true in exactly the infinite $\Sigma$-structures:

If there were, then $\neg\varphi$ would hold in exactly the finite $\Sigma$-structures.
Then the $\Sigma$-theory $\{\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j): n\in\mathbb{N}\}\cup\{\neg\varphi\}$ would be consistent (since any finite fragment holds of any sufficiently large $\Sigma$-structure), so by compactness has a (presumably non-unique) model $\mathcal{M}$.
But $\mathcal{M}$ must be infinite, since any structure satisfying $\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j)$ has at least $n$ many elements. By assumption on $\varphi$, this means $\mathcal{M}\not\models\neg\varphi$, and we have a contradiction.

Phrased most relevantly to your question, what we've shown is that even the sentence "There are infinitely many $x$ satisfying $x=x$" is not expressible in first-order logic.

On the other hand, when we restrict attention to specific structures we often have a better situation:

There are many natural structures over which the quantifier "there are infinitely many $x$ such that" is expressible. For example, in $(\mathbb{N}; +,\times,<)$, we may write "there are infinitely many $z$ such that $\varphi(z)$" as "$\forall x\exists y(x<y\wedge \varphi(y))$."

The other two answers fall into this category: they exhibit structures over which "there are infinitely many" is a first-order definable generalized quantifier.


Equivalence of data-flow analysis, abstract interpretation and type inference? @Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of running the inference algorithm) of data-flow analysis, abstract interpretation, and type inference.

In some sub-cases (like between forward context-sensitive interprocedural data-flow analysis and abstract interpretation) the equivalence is relatively obvious to me, but the question seems more subtle for other comparisons.  For example, I can't figure out how Hindley-Milner type inference could be used to prove some of the properties that can be proved with flow-sensitive data-flow analysis.

What are the seminal references discussing the equivalences (or differences) between data-flow analysis, abstract interpretation and type inference?

Data flow analysis and type inference are specific instances of abstract interpretation.

Data flow analysis and abstract interpretation look similar since they are both about computing a fix point. Data flow analyses typically have finite-height abstract domains which ensures termination. In general, abstract interpretation does not assume such abstract domains; to deal with infinite height domains abstract interpretation uses techniques of widening and narrowing.

It turns out that type inference is also about fix-point computation, although that is far from obvious, imo. Here is a paper that explicitly shows that types are abstract interpretations: paper. Basically, types are seen as an abstraction of program concrete semantics. In Hindley-Milner type system, for instance, abstract domain of types is of infinite height and computing a (most general) type using unification is essentially performing a (very imprecise) widening operation.


Context-Free Languages where every rule produces at most one non-terminal Consider a context-free grammar where all rules produce at most one non-terminal (i.e., there is at most one non-terminal on the right-hand side of a rule). What is the class of languages which are accepted by such a grammar?

If you like, we may assume that all rules are one of the following forms, where $V, V'$ denote non-terminals and $a$ denotes a terminal:

(i) $V \to aV'$

(ii) $V \to V' a$

(iii) $V \to \epsilon$

If all rules are of the form (i) or (iii) we get the class of regular languages. On the other hand, we can also recognize more languages, such as the language of palindromes.

Therefore, it is somewhere between regular languages and context-free. Does it perhaps coincide with unambiguous context-free or deterministic context-free?

A grammar where every production has at most a single non-terminal is called a linear grammar. If the non-terminal is rightmost in all productions, it is a right linear grammar; if the non-terminal is leftmost in all productions, it is a left linear grammar. Left and right linear grammars produce regular languages (and every regular language can be described by a right and a left linear grammar), but unrestricted linear grammars produce a proper superset of regular languages ($a^nb^n$ is linear), are not necessarily deterministic (the set of palindromes is linear), and are a proper subset of context free languages (the Dyck language [Note 1] has no linear grammar. The Dyck language has a deterministic grammar, so linear languages are not a superset of deterministic languages, either.)
It is not decidable whether a CFG has a linear grammar, a result proven by Sheila Greibach in 1966 (http://dl.acm.org/citation.cfm?doid=321356.321365)

Notes

The Dyck language is the set of all strings of square brackets where the brackets are balanced, given by the deterministic CFG:

$$S \to \epsilon \mid \mathbb{[}\; S\; \mathbb{]} \; S$$


Heights series in the DFS traversal of a binary tree Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3:

             3
           /   \
         /       \
       /           \
      2             2
    /  \          /  \
   /    \        /    \
  1      1      1      1
 / \    / \    / \    / \
0   0  0   0  0   0  0   0

When we do a depth-first traversal  and note the height of each node, we get the following array (for any N>3):

[0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, ...]

Note how the head of the array isn't dependent on N and can go infinitely.

I'm looking for a function F that, for any index in that array, would give the corresponding value. For example:

F(2) = 1
F(4) = 0
F(6) = 2

If possible, the function shouldn't be recursive. I do no want to have to iterate through millions of elements to calculate a height at an index far in.

In each node, store the number of nodes that are in its subtree. This can be maintained efficiently during tree manipulation operations.

Then, you can find the $k$-th node of a DFS-traversal in time corresponding to its level: recurse left if the left subtree contains more than $k$ elements, recurse right if it contains more, stop if neither applies. With a simple counter, you get the level of the node you find.

This applies to trees in general.

In your special case, you already know all the numbers so just don't actually have to see the tree. "Search" for $k$ in the virtual tree where each subtree has $2^{L+1} - 1$ nodes, $L$ being the level. This gives you an $O(N)$-time algorithm, discounting the exponentiation.


SICP: applicative or normal order evaluation I'm trying to solve Problem 1.5 from SICP book.
Consider the following definitions:

(define (p) (p))
(define (test x y) (if (= x 0) 0 y))
(test 0 (p))

The question is, what would happen if (test 0 (p)) is interpreted in applicative vs normal order.

(Applicative: evaluate all the arguments and then apply the operand. Normal: fully expand the expression and then evaluate it.)

I intuitively feel that the answer must be that one of the two gets into an infinite loop, while the other stops due to the fact that if is a special form, which does not evaluate the else-branch if the then-branch is already evaluated.

Question is: will this happen? And which one will not get into an infinite loop and why?

My reasoning is the following:

Applicative: tries to evaluate all the arguments first.

(test 0 (p)) evaluates 0 to 0 and (p) to (p).

Thus the next step:

(test 0 (p))  --> same as above, we are in an endless loop.

Normal: fully expands the expression

(test 0 (p))  --> expanded to:

(if (= 0 0) 0 (p))  --> expanded to:

(if (= 0 0) 0 (p))  --> ... (it got in an infinite loop too)

OR: does it stop at this point, because if is a special form? (Even though this is true, if we stop now, we did not really expand everything first, as we were supposed...)

This is how I understand it:
; Normal
(test 0 (p))
(if (= 0 0) 0 (p)))

Normal order continues expanding because it hasn't yet reached an expression with only primitives, which recurses into an infinite loop replacing (p) by (p).
; Applicative
(test 0 (p))
(if (= x 0) 0 y))
(if (= 0 0) 0 y))

Applicative order applies the procedure (the if predicate) to the arguments that are the values of its sub-expressions. Because if short-circuits, the expression reduces to #t before before evaluating sub-expression y.


How does a TLB and data cache work? I'm trying to study for an exam and I realized I'm confused about how the TLB and data cache work.

I understand that the TLB is essentially a cache of most recently used physical addresses. However, I was looking at a diagram in my textbook (shown below), and I don't understand what's going on in it. It suddenly splits up the physical address and uses it to index the cache, I guess. But why is it showing the cache and data separately? and why is the byte offset just left floating? I'm pretty sure the cache is supposed to store data as well. I don't think its sole purpose is to determine whether or not there's a hit or miss inside of it.

I apologize for my ignorance in advance, but the book barely covers TLB's (it's like a little more than a page) and it doesn't do a very good job at explaining the relationship between a TLB and cache.

I think I see your confusion.  The TLB and the data cache are two separate mechanisms.  They are both caches of a sort, but they cache different things:

The TLB is a cache for the virtual address to physical address lookup.  The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables.  However, doing the lookup in the page tables is slow (it involves 2-3 memory loads).  If the processor had to do this lookup every time any instruction accessed memory, this would cause a substantial slowdown.

Therefore, the TLB acts as a dedicated cache for this lookup.  The TLB has a few TLB entries, where each TLB entry contains both a virtual address and its corresponding physical address.

The TLB lets the processor very quickly convert virtual addresses to physical addresses.  If an instruction asks the processor to do some memory operation on a (virtual) address, the processor first checks to see whether the TLB contains an entry for that virtual address.  If it does, then that's called a "cache hit" for the TLB lookup, and since the TLB entry also contains the translated physical address, the processor immediately knows what physical address to use.  If it doesn't, that's a cache miss for the TLB lookup, and the processor has to laboriously do the virtual-to-physical conversion by walking the page table.  (Once it finishes doing that conversion, it adds an entry to the TLB so that future conversions of that virtual address will happen much more quickly.)
The data cache is a cache for the contents of memory.  Main memory lets you specify a physical address and read the value at that physical address.  However, main memory is slow.  If we had to go to main memory every time we wanted to do any memory operation, our processor would be very slow.

Therefore, the data cache acts as a dedicated cache for memory reads.  The data cache has some cache entries, where each cache entry contains a physical address and the value of memory at that address.

The data cache lets the processor very quickly read from memory.  When the processor wants to read memory at some (physical) address, it first checks the data cache to see whether it contains a cache entry for that address.  If it does, this is known as a "cache hit" (in the data cache), and the processor can immediately use the data value stored in that cache entry, without needing to contact main memory.  If it doesn't, then this is a "cache miss" (for the data cache), and the processor needs to go to main memory.  (After the processor receives the value at that address from main memory, it adds a cache entry to the data cache so that attempts to read that same address will hit in the data cache.)

They are both caches, but they serve a different purpose.  The processor uses both for each memory operation: it first uses the TLB to convert from virtual address to physical address, then it checks the data cache to speed up the process of reading the value stored in memory at that address.

For more details, you can read the Wikipedia article on TLBs.  If you do a search, there is a lot of other information available on TLBs and data caches. I suggest searching for "TLB" and for "L1 cache" or "L2 cache" (the latter 2 are kinds of data caches).

(For future reference: we expect you to do some research on your question before asking here, and to check standard Internet sources.  If the answer can be found in Wikipedia, you haven't done enough research on your own.  You might have had better luck if you'd checked Internet sources for information on how
TLBs before asking here.  See also How much research effort is expected of Stack Overflow users?.  So, take the opportunity to use this as a lesson for how you can improve your own research skills -- something that will be valuable to you throughout your career.)


What is the difference between a "meta model" and "design patterns"? Where is the difference between a "meta model" and "design patterns"?

If you take, for example, Fowlers "Identity Field" from his book "Patterns Of Enterprise Application Architecture": Why is this a pattern and not a meta model?

Thanks!

Design Pattern: It is a "good practice". It can be considered as a possible solution for a problem that may ofter occur. The solution usually comes from the experience.  Examples are MVC and Identify Field.

Metamodel: It can be considered as a set of rules, constraints and constructs that allow to model a problem.
As an example you can consider a map.

A map allows to model the reality, so a map can be considered the model. The metamodel of a map is the legend: the constructs that you need to use in order to represent borders, rivers, lakes,...

In your case Identify Field is just a good practice that you can decide to follow or not. It's not a constraint/rule.


Haskell monad bind operator type In Haskell, the Monads type class has the bind operator, which is represented by the symbol >>=

The type of such operator is:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Why does the function need to be (a -> m b)? Why functions the preserve che inner data type (a -> m a) are not allowed?

Has this choice been made for some convenience in the language design, or does it have some other reason?

Here's a nice, and accessible, blog on why we need the type to have that form.

http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

Also, this blog motivates why we want them this why and how they naturally arise in our daily workings :)

Enjoy!


Are EAX , EBX registers 64 bit in length in modern processors The EAX, EBX and ECX registers on a cpu are they 64 bits for a 64-bit cpu ?

No, they still refer to a 32bit register. But they are part of 64bit registries RAX, RBX and RCX.
The main reason for this is backward compatibility.


Algorithm for designing a binary code with predefined distance Suppose I have a matrix $A$ with its entry $A_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that the Hamming distance between code word for $i$ and $j$ is (roughly) proportional to $A_{ij}$?

A related question is that given a set of points, design a binary code where the Hamming distance is (roughly) proportional to the Euclidean distance.

This is known as an embedding into $\{0,1\}^n$.  Your matrix $A$ defines a weighted graph, and you want an embedding into the hypercube.

I suggest you examine the literature on low-distortion graph embeddings, which have been studied in great depth in the computer science literature.  You might find some existing constructions on this topic.  I'm not deeply familiar with that literature myself and I don't know whether you will find anything directly applicable.


Weird behaviour of softmax derivative? I have been implementing  some neural networks  in MATLAB and recently I noticed a weird thing while implementing softmax derivative:

Setting the derivative to one, rather than using the actual derivative converges faster.

I have to admit that the derivative of softmax in particular confused me quite a bit, since the actual derivative requires the Jacobian as opposed to other activation functions that only depend on the input.
That is, for output vector of size nx1, the derivative of the activation function is also nx1 (see ReLU, tanh etc.) but for softmax is nxn.

Anyway, the simple case is to consider the diagonal of the Jacobian which is “out*(1-out)” as derived and proposed in a couple of sources around [1-3]. However setting the derivative to “1” shows faster convergence.

I am not fully sure to say how this phenomenon generalises but I tried with different settings, architectures and optimisers and the issue seems to persist.

I made an example of a 2x5x5x2 feedforward network with tanh in all but last layer, where I’ve used softmax, classifying a typical XOR problem using cross-entropy loss with ADAM optimizer.

Does anyone have any hunch why this would happen?

Refs:

1: https://eli.thegreenplace.net/2016/the-softmax-function-and-its-derivative/
2: https://math.stackexchange.com/questions/945871/derivative-of-softmax-loss-function
3: https://datascience.stackexchange.com/questions/29735/how-to-apply-the-gradient-of-softmax-in-backprop

P.S. I am aware that showing this behaviour in only one problem does not mean that it happens always, but in a couple of experiments I have done, this behaviour seems to be persistent

I'm not sure what you mean by "the simple case is to consider the diagonal of the Jacobian".  Are you perhaps doing some unusual variation of gradient descent where you compute only the diagonal of the Jacobian, but not the other entries?  If you are, then don't be surprised if it performs poorly.  Don't do that.  I wouldn't expect that to work well.

Instead, I recommend you follow the standard approach: use backpropagation to compute the gradient and use gradient descent to update the weights.  There are many standard tutorials on how to do that.  Realistically, we never need to compute the Jacobian matrix for the softmax directly.  Instead, we look at the output of the loss function, and we compute the gradient of that with respect to the weights.  That doesn't require a Jacobian, because we are computing the gradient of a function that has a single output.  Then, we use the gradient to update the weights (that's the gradient descent part).

If you're implementing this yourself from scratch, there are many things that can go wrong.  I recommend implementing a gradient check to make sure you are computing the gradient properly.  But, more realistically, I recommend using some existing framework for training neural networks (e.g., Keras, Torch, etc.) rather than trying to implement it from scratch.  If you implement from scratch, there are many ways you can create some small implementation error that will lead to results that are subpar but hard to debug.


What was the first programming language with loop break? While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL.

Algol _? -> CPL -> BCPL -> C -> C++ -> Java -> JavaScript

What was the first programming language to introduce the feature of being able to break out of a loop from the body?

This feature existed in BCPL and is implied to have existed (from its manual) in CPL which was introduced in 1963.

ALGOL 60 was CPL's main influence, but ALGOL 60 did not have the feature.

The structured programming movement started around 1966.

Given the turmoil in the committee between ALGOL 60 and ALGOL 68 (which spawned many languages), was this the source of the feature? Did it exist under a different form at the time as a block EXIT perhaps?

I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote:

  "CPL did have a break command to cause an exit from a repetitive command such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967."

[...]

  "The introduction of break in CPL was almost certainly influenced by Dijkstra's paper..."

He also pointed me to the following document (see page 5):

http://www.cl.cam.ac.uk/~mr10/cpl2bcpl.pdf


Difference between sequential and parallel divide and conquer In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy

  In divide and conquer, we solve a problem recursively, applying three
  steps at each level of recursion:

  Divide the problem into a number of subproblems that are smaller
  instances of the same problem

  Conquer the subproblems by solving them recursively. If the
  subproblems sizes are small enough, however, just solve the problems
  in a straight forward manner.

  Combine the solutions into the solution of the original problem.

This algorithmic strategy is assumed on sequential machines and is a non-parallel divide and conquer strategy.

How is parallel divide and conquer different from the above? Which step among divide, conquer, combine will be different?

My assumption is that the dividing step will not change and combine step will not change, but only the conquer step changes and the change will be that each subproblem will be solved in parallel. Is it true?

Just like you wrote, you can solve independent subproblems in parallel. Here are two examples:

In merge sort, you can sort the two halves of the input in parallel, and then merge them together sequentially.
In quicksort, you split the input into two halves sequentially, and can then sort both of them in parallel.

In the first case there is no divide step, and in the second case there is no conquer step. In other cases probably all three steps will be present.

Some divide-and-conquer approaches have a single subproblem. This is the case in binary search. Such algorithms do not benefit from parallelization.


Choose the kth choice of choosing n things out of m Say I have a list, L, of m things.

I want to pick n things out of the total of m things in the list.

Suppose there are W ways of doing this. I want to choose the kth way where k is in the range 1..W.

i.e. my function is this:

ChooseKthChoiceOf(L,n,k){
   ....
}

Any good algorithms for this?

This is called unranking.  The combinatorial number system provides a clean solution to this particular problem.

See also https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/ for further reading.


Finding integrality gap for maximum weight independent set One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my LP relaxation.

As far as my knowledge goes, integrality gap for maximization problem is the the maximum ratio cost(LP)/cost(ILP) over all instances of a problem. But I've been googling for a little bit, and most examples only showed how to get a lower bound of integrality gap by taking some arbitrary instance. Is it possible to get an exact ratio?

Suppose you prove that an upper bound on the integrality gap is $\alpha$.
  The goal is to “create” an instance (weighted graph, or better yet, a family of weighted graphs) where the value of the optimal LP solution is $\alpha$
  times the value of the ILP solution.

Independent set ILP
$$O_{ILP}=\max\sum_{v\in V}x_{v}\cdot w(v) $$
such that
$$x_{v}+x_{u} \leq 1\ \ \ \forall u,v\in V$$
$$x_{v}\in\{0,1\}  \ \ \forall v\in V$$

The relaxation is straight forward. say the value of the optimal solution to the LP is $O_{LP}.$ Now, you want to upper bound $ O_{LP}/O_{ILP}.$
  To do this, try to consider a rounding scheme that converts a solution for the LP into a feasible solution for the corresponding ILP. One such scheme involves reasoning about the constraints, that is $x_{v}+x_{u}\leq1$
 for every edge in G.
  This implies that at least one of $x_{u}$
  or $x_{v}$
  is atleast $1/2$,
  and therefore all vertices in $v\in V$
  such that $x_{v}>\frac{1}{2}$
  is an independent set in $G$.
  I'll leave it to you to reason about how to compare $O_{LP}$
  and $O_{ILP}$, (i.e. determine the maximum of the ratio $\alpha=\max O_{LP}/O_{ILP}$), and to find an instance where $O_{LP}$ is atleast $\alpha.$


Structural induction on generic list In preparation for an exam, I've come upon the following problem.  Given the constructors :

[]: -> T LIST

[a]:T-> T LIST

cons(a,x) : T x T LIST -> T LIST ( a is added to the beginning of the list)

And the functions :

size(l) : T LIST -> N (number of elements in l)

reverse(l): T LIST -> T LIST ( reverses the order ofthe elements in the list)

unique(l) : T LIST -> T LIST - returns a list of the elements in 'l' that only appear once

repeated(l) : T LIST -> T LIST - returns a list of the elements in 'l' that appear more than once

max?(e,l) : T x T LIST -> Bool - returns true if 'e' is the maximum element in the list, false otherwise

Prove by structural induction that :

max?(e, l) -> max?(e, unique(reverse(l))) || max?(e, repeated(reverse(l)))

I've managed to simplify this to :

max?(e, l) -> max?(e, unique(l)) || max?(e, repeated(l))

But I don't see how to proceed towards proving what is asked...

Used definitions of functions:

    unique([]) = []
    unique([e]) = [e]
    unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false unique(cons(e, L)) = unique(L), if member(e, L) = true

    repeated([]) = []
    repeated([e]) = [e]
    repeated(cons(e, L)) = cons(e, repeated(L)), if member(e, L) = true unique(cons(e, L)) = unique(L), if member(e, L) = false

    reverse([]) = []
    reverse([e]) = [e]
    reverse(cons(e, L)) = append(reverse(L), [e])

    also,
    member : Element x List -> Bool
    member(e, []) = false
    member(e, [a]) = (e == a) (true, if a is equal to e; false, if a isn't equal to e)
    member(e, cons(a, L)) = (e == a) V member(e, L) (V is logical disjunction)

    append : List x List -> List
    append([], L) = L
    append([e], L) = cons(e, L)
    append(cons(e, L1), L2) = cons(e, append(L1, L2))

Note: I mixed up boolean functions and propositions in what follows for
brevity, and I hope it'll not cause any confusion.

I assume you have defined the function $\max?$ something like this:

max?(e, l) = ge_all?(e, l) && member(e, l),

where

ge_all?(e, []) = True
ge_all?(e, cons(x,xs)) = e >= x && ge_all? e xs.

You will need a bunch of lemmas [they can be proved using structural induction]:

Lemma 1: $\text{member}(e, l) \implies \text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ [this one is suggested by @Alexander]. Its proof is pretty boring because of lots of subcases.

Lemma 2: $\text{ge_all?}(e, l) \implies \text{ge_all?}(e, \text{unique}(l))$.

Lemma 3: $\text{ge_all?}(e, l) \implies \text{ge_all?}(e, \text{repeated}(l))$.

Theorem: $\max?(e,l) \implies \max?(e, \text{unique}(l)) \vee \max?(e, \text{repeated}(l))$.

Proof sketch:

$\max?(e, l)$ implies $\text{member}(e,l)$, which in its turn implies $\text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ [by lemma 1]. So we consider two cases:
(1) $\text{member}(e,\text{unique}(l))$ and (2) $\text{member}(e,\text{repeated}(l))$.

In the case (1) we can prove $\text{max?}(e,\text{unique}(l))$ like this: $\max?(e, l)$ implies by definition $\text{ge_all?}(e,l)$, which [by lemma 2] implies $\text{ge_all?}(e,\text{unique}(l))$. Since $\text{ge_all?}(e,\text{unique}(l))$ and $\text{member}(e,\text{unique}(l))$ we get $\text{max?}(e,\text{unique}(l))$.

The case (2) is similar. End of proof.


CNF satisfiability with a bound on number of clauses Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness if we restrict attention to problem instances where k scales sublinearly in n? For this question, I am not requiring clauses to consist of 3 literals, but I still need the formula to be CNF.

More generally, how does complexity scale (for known algorithms) with k?

Here is an $n^{O(k)}$-time SAT algorithm: try all (at most $n^k$) ways how to select one literal from each clause, and accept whenever the selection is such that it does not include any contradictory pair (i.e., a literal and its negation). So, if $k$ is substantially smaller than $n$, you get a subexponential algorithm, and you should not be able to prove NP-completeness of such a restricted problem.


Modifying digraph to make it strongly connected I came across this problem and have not been able to find a solution.

Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the modified graph $G'$ has a path from any vertex to any other vertex. That is, we can remove any edge between any two vertices and add them back to the graph any which way.

Anyone have any idea how to solve?

Clarification for edge modification:
You can edit edges any which way for a cost of one move. Once you remove an edge between any two vertices, you can reattach it to the same two vertices but flipped, or attach it to two different vertices entirely, or just have the edge go from the original source vertex to another vertex, or a different source vertex to the same destination vertex.

On solvable instances (not all instances are solvable; see narek Bojikian's comment on my other answer for a simple necessary and sufficient condition), this is NP-hard by reduction from Directed Hamiltonian Path. The basic idea is to add enough isolated vertices to the input digraph to force the only possible solution to be a single cycle, and then see whether it is possible to accomplish this with few enough moves that the unmoved edges must form a DHP in the original digraph.

Given an instance of Directed Hamiltonian Path consisting of a digraph $(V, E)$ with $n=|V|, m=|E|$, add $m-n$ isolated vertices. Observe that a single SCC can be formed by rearranging the $m$ edges into an arbitrary cycle that touches each of the $m$ vertices that now exist. This can be done trivially if we are prepared to move all $m$ edges, but if we limit ourselves to moving at most $m-n+1$ edges, then this is possible only if $m-n+1$ edges are moved from somewhere to form a path that connects some vertex $u$ of the original digraph to some new isolated vertex, visits each new isolated vertex in some order, and finally returns to some other vertex $v$ of the original digraph. (We have $u \ne v$ since $u=v$ would leave just $n-1$ edges available to visit all $n$ vertices of the original digraph, which is not enough.) In this case, the unmoved $n-1$ edges that remain necessarily form a path from $v$ to $u$ through the $n$ vertices of the original digraph, and thus constitute a DHP through it. This shows that a YES answer to the constructed instance implies a YES answer to the original problem.

To see that a YES answer to the original DHP problem implies a YES answer to the constructed instance, pick up the $m-n+1$ edges that are not part of the DHP, and construct a path as described above, forming a single cycle comprising all $m$ vertices using just $m-n+1$ moves.


Is this a correct way to thing about asymptotic notations? I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering why are we allowed to compute a sum of a polynomial and a set. Why not just teach that for every $n\in\mathbb N$ there is a $f:\mathbb N\to \mathbb N$ such that $f\in \Theta(n)$ and $2n^2+3n+1=2n+f$? Is this a formally correct way to think $\Theta$ notation? Or should I learn some other book to learn O-notations, like J.D. Murray: Asymptotic analysis? Or do I have some misunderstanding that becomes clear if I first learn some book of axiomatic set theory?

The answers and comments by other users here do a good job of explaining how the notation works, so I figure I'll explain why the notation is used this way. The reason for the notation is already evident in your question: writing out the set inclusion explicitly makes it way more verbose.

When you are learning asymptotic notation for the first time, it is helpful to clearly state that $O$, $\Theta$, etc. are not functions and that "equality" does not behave like equality in statements involving these symbols. But when you are an expert in a field reading a hundred-page paper written by other experts in the same field to communicate with their kin, you really don't want to have to read this kind of boilerplate over and over again if you can avoid it.

The purpose of asymptotic notation is to allow the author to state theorems and intermediate steps in an extremely compact fashion. When you read something like $f(n) = 5n^3 + 3n^2 + o(n^2)$, what you are really reading is, "$f(n)$ is equal to $5n^3 + 3n^2$ plus a bunch of junk that neither you nor I have time to care about because it is sufficiently small that its exact value is irrelevant to the correctness of the rest of the argument I am about to present". Writing everything out in terms of statements about sets would obscure the point the author is trying to communicate.


Solving "coin exchange" for coins of power values by greedy algorithm When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?

For example, if $a = 3$, $n =3$, we get the following coin values: 1, 3, 9, 27. When total exchange is 16, answer is 4 coins, as returned by greedy algorithm, $16=9+3+3+1$.

For the coin values: 1, 3, 9, 27, suppose $16 = a_0 + 3a_1 + 9a_2 + 27a_3$ is the coin exchange with minimal number of coins. Note that $16\equiv a_0 \equiv 1(\operatorname{mod}3)$. If $a_0 \ge 3$, then we can subtract 3 from $a_0$ and add 1 to $a_1$ to obtain coin exchange with less number of coins. So, $a_0$ must be the remainder of 16 divided by 3. Hopefully, you can see where I am going.

All numbers or variables below are nonnegative integers. $(d_nd_{n-1}\cdots d_0)_a$ means the integer with those digits in base $a$, i.e., $(d_nd_{n-1}\cdots d_0)_a=\sum_{i=0}^{n}d_ia^i$ where $d_i\lt a $ for $i\le n$.

Here is the general theorem.

(Greedy algorithm works for power coins) Let $a\ge2$ and $n\ge0$. If $e_na^n+(e_{n-1}e_{n-2}\cdots e_0)_a=\sum_{i=0}^nc_ia^i$, then $ \sum_{i=0}^ne_i\le\sum_{i=0}^nc_i$.

Proof by mathematical induction on $n\ge0$.

The base case, when $n=0$ is trivial.

Suppose it is true for some $n\ge0$. Let us check the case of $n+1$. Suppose  $m=e_{n+1}a^{n+1}+(e_ne_{n-1}\cdots e_0)_a=\sum_{i=0}^{n+1}c_ia^i$. Note that $e_0$ is the remainder of $m$ divided by $a$.

If $c_{0}\ge a$, we can subtract $a$ from $c_0$ and add $1$ to $c_1$ to reduce sum $\sum_{i=0}^{n+1}c_i$. Without loss of generality we can assume $c_{0}\lt a$, i.e., $c_0$ is also the remainder of $m$ divided by $a$.

Now let $m'=(m-e_0)/a=(m-c_0)/a$. Then $m'=e_{n+1}a^{n}+(e_{n}e_{n-1}\cdots e_1)_a=\sum_{i=0}^{n}c_{i+1}a^i$. By induction hypothesis, we know $\sum_{i=0}^ne_{i+1}\le\sum_{i=0}^nc_{i+1}$. Adding $e_0=c_0$ to both sides, we obtained the wanted inequality for the case of $n+1$. Q.E.D.

What is left to be explained is that $\sum_{i=0}^ne_i$ does
come from the greedy algorithm. That easy task will be left for interested readers to verify.


Polynomial Complexity (Relative to the Size of the Input) I came across the following statement:

"Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial."

I suppose it has something to do with the notion of polynomiality in terms of the input. All three variables are given as input. I am still not sure why it wouldn't be polynomial if $b$ was as big as $n$.

We could say $O(n + mn)^3)$ then which would be dominated by $O((mn)^3)$ for $m \geq 0$.
It is even given, that $m \leq n$ which means that we can say $O(n^6)$ as worst case.

Now I would say this is certainly polynomial, because our solution is of the form $O(n^c)$ with $c \in \mathbb{R}$ which means that it is polynomial in the size of $n$.

What am I missing here?

The statement meant to say that "if b is asymptotically smaller than n" i.e. $b=o(n) \space or \space b=O(n)$.
If $b$ was asymptotically larger than $n$, i.e. $b=\omega (n) \space or \space b=\Omega(n)$, then the complexity would become, $O(b^3)$, i.e. not polynomial in $n$.

For example, lets consider two cases.

$b$ is asymptotically smaller than $n$, i.e. $b=O(n)$.
$$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$
$$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$
We know that $b=O(n) \implies bn=O(n^2),\space bn^2=O(n^3) \space and \space b^2n=O(n^3). $
From this, we can conclude that, $m^3b^3=O(3nm^2b^2)$, $3nm^2b^2=O(3n^2mb)$, and $3n^2mb = O(n^3)$.
$$\implies O((n+mb)^3)=O(n^3)$$
$b$ is asymptotically larger than $n$, i.e. $b=\Omega(n) \space or \space n=O(b)$.
$$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$
$$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$
We know that $n=O(b) \implies nb=O(b^2),\space nb^2=O(b^3) \space and \space n^2b=O(b^3). $
From this, we can conclude that, $n^3=O(3n^2mb)$, $3n^2mb=O(3nm^2b^2)$, and $3nm^2b^2 = O(b^3)$.
$$\implies O((n+mb)^3)=O(b^3)$$

In your approach, assuming $b$ to be numerically smaller than $n$ would lead to correct analysis. But what the statement means is that $b$ is asymptotically smaller than $n$. Like, $b=log(n) \space or \space b=\sqrt{n} \space or \space b=log(log(n))$


Number of DFA states required What is the minimal number of DFA states required to recognize binary numbers (encoded MSB to LSB) which are divisible by 6 and 8?

For divisibility by $6$ we required $6$ states.

For divisibility by $8$ we require $4$ states.

So in total, we need $6 \times 4$ states = $24$ states.

Am I correct? Can we do it with fewer states?

In order to obtain an upper bound on the number of DFA states required to recognize some language, the simplest method is to give a DFA with that (or lower) number of states. In order to obtain a lower bound on the same number, the easiest route is to give $m$ pairwise indistinguishable words. These are $m$ words $x_1,\ldots,x_m$ such that for each $i \neq j$ there exists a word $y$ such that $x_i y \in L$ whereas $x_j y \notin L$, or vice versa. This set of words shows that every DFA for $L$ must contain at least $m$ states (why?).

In your case, the minimal number of states is much smaller than 24, though the exact number depends on the encoding. Instead of solving your question, let me calculate the minimal number of states in a DFA accepting all (non-empty) decimal numbers (encoded MSB to LSB) which are divisible by 6. I claim that this number is 4. For the upper bound, consider a DFA with states $q_0,q_1,q_2,q_A$, where $q_0$ is the initial state and $q_A$ is the accepting states. The transition table of the DFA is
$$
\begin{array}{c|ccccccccccc}
\delta & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline
q_0 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\
q_1 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 \\
q_2 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 \\
q_A & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\
\end{array}
$$

You can show by induction that upon reading a word $w$:

If $w = \epsilon$ or $w \equiv 3 \pmod{6}$, the machine is in state $q_0$.
If $w \neq \epsilon$ and $w \equiv 1,4 \pmod{6}$, the machine is in state $q_1$.
If $w \neq \epsilon$ and $w \equiv 2,5 \pmod{6}$, the machine is in state $q_2$.
If $w \neq \epsilon$ and $w \equiv 0 \pmod{6}$, the machine is in state $q_A$.

This easily implies that this DFA accepts our language.

For the lower bounds, we use the set of words $\{0,1,2,3\}$. The following table gives the words $y$ separating each pair of words:
$$
\begin{array}{c|cccc}
y & 0 & 1 & 2 & 3 \\\hline
0 & & \epsilon & \epsilon & \epsilon \\
1 & \epsilon & & 2 & 0 \\
2 & \epsilon & 2 & & 0 \\
3 & \epsilon & 0 & 0 &
\end{array}
$$
(These correspond to the states $q_A,q_1,q_2,q_0$.)


Amortized value of dequeue with potential function A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty.
Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1).
A 'heavy pop' is in a scenario when we have k elements, only in 1 stack and we wish to pop the other stack.
For example, n elements in head and we want to pop the tail.
In this case, we push all elements from head stack to the empty stack, than push n/2 elements to the tail and the remaining n/2 back to the head.

I'm having troubles finding the potential function for this solution, or the amortized value for that case.
If I define the potential function to be the number of current elements in the deque, I get linear time. I don't know if this is true but I feel like it's not.

The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease.  Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$.

(For simplicity I represent hard pop as combination of two operations - rearrangement of elements using the third stack and a light pop)

Before the rearrangement, one of the stacks is empty, and other one contains $k$ elements, and right after both contains $\frac{k}{2}$. Therefore, the potential decreases on $2k$ and amortized cost of rearrangement is

$(k + \frac{k}{2} + \frac{k}{2}) + (-2k) = 0 = O(1)$

The amortized costs of light pop and push are clearly $O(1)$ as well as potential increases on $2$ at most.


A monad is just a monoid in the category of endofunctors, what's the enlightenment? Pardon the word play. I'm a little confused about the implication of the claim and hence the question.
Background: I ventured into Category Theory to understand the theoretical underpinnings of various categorical constructs and their relevance to functional programming (FP). It seems (to me) that one of the "crowning gems" at the intersection of Cat and FP is this statement:
A monad is just a monoid in the category of endofunctors
What is the big deal about this observation and what are its programmatic/design implications? Sources like sigfpe and many texts on FP seem to imply the mindblowingness of this concept but perhaps I'm unable to see the subtlety that's being alluded to.
Here's how I understand it:
Knowing something is a monoid allows us to extrapolate the fact that we can work within a map-reduce setting where the associativity of the operations allows us to split/combine the computation in arbitrary order i.e., (a1+a2)+a3 == a1+(a2+a3). It can also allow one to distribute this across machines and achieve high parallelization. (Thus, I could mentally go from a theoretical construct -> computer science understanding -> practical problem solving.)
For me it was obvious (as a result of studying Cat) to see that monads have a monoidal structure in the category of endofunctors. However, what is the implication one can draw from this and what is its programmatic/design/engineering impact when we're coding with such a mental model?
Here's my interpretation:

Theoretical Implication: All computable problems at their heart are monoidal in a sense.

Is this correct? If so, I can understand the enlightenment. It's a different perspective on understanding the notion/structure of computable problems that wouldn't be obvious if coming from only a Turing/Lambda model of computation and I can be at peace.
Is there more to it?

Practical Implication: Is it simply to provide a case for the do-notation style of programming? That is, if things are monoidal we can better appreciate the existence of the do/for constructs in Haskell/Scala. Is that it? Even if we didn't know about the monoidal underpinnings, we needn't invoke the monoidalness to make this claim since bind >>= and flatMap constructs are defined to be associative. So what gives? Or is it more to do with the foldability of monadic constructs and that is the indirect enlightenment that is being alluded to?

Question(s): What am I missing here? Is it simply the recognition of the fact that monads are generalized monoids and that they can be combined in any order similar to map-reduce operations like monoids? How does knowing about the monoidal property help improve the code/design in any way? What's a good example of before/after to show this difference (before knowing about monads/monoidality and after)?

This answer may not be exactly what you are looking for. That is, I think perhaps the importance of this characterisation is being overemphasised here. The quote

a monad in X is just a monoid in the category of endofunctors of X

is originally from Mac Lane's Categories for the Working Mathematician, where it appears as a helpful intuition for the definition of monad, which, alone, can seem quite unfamiliar at first. By characterising it as a monoid in a particular monoidal category, the reader is given an alternative perspective. Note that the chapter on monads actually comes before the chapter on monoidal categories: the remark is intended to be helpful, rather than precise (it is made precise only later).
The quote was then rephrased in James Iry's infamous article Brief, Incomplete and Mostly Wrong History of Programming Languages.

A monad is just a monoid in the category of endofunctors, what's the problem?

Presented out of context, as it is in the article, it is meant to amuse. The quote has since become a meme in the functional programming community, primarily because it is amusing, rather than a key insight for functional programming (though it does also serve to pique the curiosity of functional programmers, drawing them into the wonderful world of category theory). My view is that this characterisation, while helpful and interesting, is not as important as one might imagine from its popularity.
However, this is not to say there is no insight to be gained from this characterisation. First, let me point out that, while the presentation of a monad with a multiplication and unit is clearly suggestive of a monoid, as you point out, the Kleisli presentation, with a bind and return operation, is not. It is the Kleisli presentation that is common in functional programming, so certainly the characterisation as a monoid is more interesting from this perspective.
From a theoretical perspective, one of the insights is indeed that many natural structures in computer science (and mathematics) are monoidal. From the perspective of monads (particularly with their relation to cartesian operads and Lawvere theories), monoidal structure corresponds to substitution structure (equivalently, composition structure). Substitution is ubiquitous in computer science (for example, capture-avoiding substitution in a type theory, or grafting of trees). Monads are just one more example.
While understanding formally the statement in question may not be enlightening, I suggest that it is enlightening to understand the different perspectives on monads, as it allows you to see the different ways in which monads might be used (e.g. as containers, describing algebraic structure, describing multi-compositional systems, etc.). It can be hard to appreciate just how often they pop up without having seen the different lights in which they can be seen. In this sense, monads as monoids is just one perspective (and probably not the most enlightening).
Finally, while monads themselves are inarguably very useful in pure functional programming generally, I'm not sure the perspective as monads as monoids is helpful per se. I think the Kleisli perspective, which happens to be equivalent, is the most enlightening perspective here.
In summary, this response may be a little disappointing: I don't think that understanding this relationship is all that helpful or enlightening practically (i.e. for programming). However, it is a useful perspective to keep in mind, along with the others, when considering monads theoretically.


Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$ Prove that $H_r(S) = H(s) / \log_2r$.

I'm not sure how to prove this. Any help would be greatly appreciated!

There's nothing to prove here, this follows by Definition. Assume a discrete r.v. $X$, then

$$H(X) \triangleq \mathbb{E}[-\log \Pr(X)]$$

and,

$$H_r (X) \triangleq \mathbb{E}[-\log_r \Pr(X)].$$

Therefore, the claim follows (using $E(aX)=aE(X)$ for a constant $a$). Note that in your question you use $H(X)$ as the binary entropy $H(X) \triangleq H_2(X) = \mathbb{E}[-\log_2 \Pr(X)]$, hence the multiplicative factor is $\log_2 r$.