What is a bicriteria approximation algorithm? What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization?

This is where I came across it: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. The paper is about a streaming version of the k-means algorithm. There are references in the paper but none of them give an explanation as to what a bicriteria approximation algorithm is. I cannot seem to find anything on Google that will give me a precise definition either.

I'll expand on the answer by Yuval Filmus by providing an interpretation based on multi-objective optimization problems.

Single-objective optimization and approximation

In computer science we often study optimization problems with a single objective (for example, minimize f(x) subject to some constraint). When proving, say, NP-completeness, it is common to consider the corresponding budget problem. For example, in the maximum clique problem, the objective is to maximize the cardinality of the clique, and the budget problem is the problem of deciding whether there is a clique of size at least k, where k is given as part of the input to the problem.

When it is not possible to compute an optimal solution efficiently, as in the case of the maximum clique problem, we seek an approximation algorithm, a function that outputs a solution within a multiplicative factor of an optimal solution. You could also consider an approximation algorithm for the budget problem, a function that outputs a solution that satisfies f(x) ≥ ck in the case of a maximization problem, where c is a number less than one. In this situation, the solution may violate the hard constraint f(x) ≥ k, but the "severity" of the violation is bounded by c.

Multi-objective optimization and bi-criterion approximation

In some cases, you may want to optimize two objectives simultaneously. For a rough example, I may want to maximize my "revenue" while minimizing my "cost". In such a situation, there is no single optimal value, as there is a tradeoff between the two objectives; for more information, see the Wikipedia article on Pareto efficiency.

One way of turning a two-objective optimization problem into a single-objective optimization problem (for which we can reason about the optimal value of the objective function) is to consider the two constraint problems, one for each objective. If the problem is to simultaneously maximize f(x) while minimizing g(x), the first constraint problem is to minimize g(x) subject to the constraint f(x) ≥ k, where k is given as part of the input to this single-objective optimization problem. The second constraint problem is defined similarly.

An (α, β)-bicriteria approximation algorithm for the first constraint problem is a function that takes a budget parameter k as input and outputs a solution x such that

$f(x) \geq \alpha k$,
$g(x) \leq \beta g(x^*)$,

where $x^*$ is a solution that achieves the optimal value for g. A bicriteria approximation algorithm for the second constraint problem outputs a solution such that

$f(x) \geq \alpha f(x^*)$,
$g(x) \leq \beta \ell$,

In other words, the bicriteria approximation algorithm is simultaneously an appoximation for the budget problem in the first objective and the optimization problem in the second objective. (This definition was adapted from page four of "Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints", by Iyer and Bilmes, 2013.)

The inequalities switch directions when the objectives switch from maximum to minimum or vice versa.


How do the bits of a certain emoji code for all the colors? I am watching an introductory course on computer science. At one part, it starts talking about unicode and how the bits 11111011000000010. He states that that codes for a laughing/crying face emoji.

However, he later on talks about how the pixels are each created through a number of bytes.He says the bytes 72, 73 and 33 make light red, light green and light blue.

My question is, if there are so many bytes which make up all those pixels in an emoji, how do the bits 11111011000000010 represent all those pixels of colour?

That binary number does not contain the information about the pixels in the image which is used to show the emoji. It is only a number which, according to the Unicode standard, refers to that emoji. Every program which shows text (e.g. email reader, web browser, ...) must have a way to convert that number into the actual pixels. Usually, in modern computers, there is a font file, which contains all the information about the pixels of each character. So, when the program has to display the emoji, it accesses the file and reads the pixel data corresponding to the emoji, and sends those pixels to the screen.

Note that the Unicode standard does not specify what these pixels are, but only that they should represent, say, a "cake emoji". Every program might use a different font, showing the cake in a different way.

This also happens for regular characters. Unicode says that "A" is represented by number 65, but there are many fonts that can be used to show that "A".


Worst Case for AVL Tree Balancing after Deletion After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing operation is said to be O(logn).
What is the worst case for balancing? (I guess it will require balancing at every node all the way up till the root)
Any specific type of tree providing the worst case?

To make a lot of rebalancing, you would like to make your AVL tree as imbalanced as possible. And the worst case is a Fibonnachi-like tree:

, where $T_n$ is a tree with $T_{n-1}$ as a left child and $T_{n-2}$ as a right child ($T_1=T_2=$single-node tree).
On this example, if you remove 19, then node 18 must be rebalanced. After that, node 13 must be rebalanced. Essentially, you will have a rebalance at every level above node 20. You can build an arbitrary large such tree. I didn't check, but it should be simple to prove that removing the rightmost node always suffices for the worst case.


Shortest path from source to all vertices, but with some wildcards Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated with it. Vertex $1$ is source vertex. You have $K$ wildcards. In the path from vertex $1$ to vertex $i$ ($2 \leq i \leq n$), you can use at most $K$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be $0$ if you use a wildcard on an edge). Note: You can use at most $K$ wildcards from vertex $1$ to vertex $2$. Now you can again use at most $K$ wildcards from vertex $1$ to vertex $3$ and so on to vertex $n$. In other words, you can use at most $K$ wildcards in each path from source to destination. You have to find minimum distances from node $1$ to all other nodes in graph.
Constraints: $1 \leq n, m \leq 500000, 1 \leq K \leq 15$
Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $k$ edges from $m$ edges in $\binom{m}{k}$ ways. And for each case find shortest path, but that will be too much time complexity.

Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \{1,\ldots,K\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.

I'll let you figure out why this works.


Number of min-cuts of a graph It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts.
It follows from Karger’s algorithm Analysis.

Is there a different combinatorial proof of this fact? Was this known before Karger’s paper?

An earlier proof that associates to an arbitrary graph G a certain "structural graph" was shown by Dinitz, Karzanov and Lomonosov in 1976 [1].

[1] Dinitz, E. A., Karzanov, A. V., & Lomonosov, M. V. (1976). On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, 290-306.


Devising a way to spot a contradiction given a set of statements using graphs If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.

Would there be a way to figure out that there is a contradiction in this set of statements using graphs?

My attempt at it was to symbolize each of the names, assuming they have different first letters to statements like, J = M, M = S, C = S, C ≠ J.

My idea is to find a cycle after using DFS on some graph but I'm having trouble making the actual graph which is perhaps the most troublesome part.

I hope I'm on the right track. Any help would be much appreciated!

Edit: The comment makes a good point and the statements do have inequalities as well, but I'd like to make another attempt at that on my own afterwards. If the question were to be simplified to just "as tall" and "not as tall", what sort of graph would I make?

First, you can consider only the equality relationships and build an undirected graph with each edge representing each equality relationship. Then you can simply apply BFS or DFS to partition this graph into connected components.

Next you can consider the "<" and ">" relationships. You can treat each connected component as a vertex and add directed edges so that $(u,v)$ represents the relationship $u<v$. Then you can detect if there is a cycle in the directed graph by DFS again. If there is cycle, there is a contradiction among these relationships; otherwise the relationships we processed so far are consistent.

At last you can consider the "$\neq$" relationships. You can simply check for each relationship $a\neq b$ if $a$ and $b$ belong to the same connected component. If $a$ and $b$ belong to different connected components for all relationships $a\neq b$, then all the relationships are consistent; otherwise there is a contradiction.


What Does The Notation of Union Over K represent? I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows:
$$P= \bigcup_{k}TIME(n^k)$$
I have not seen the Union over k notation before. K is a constant. A quick introduction to the meaning of this notation would be enormously helpful.

Thank you

Authors often leave out the domain of the union if it is clear within the context. Here, $k$ is a natural number, i.e. $P = \bigcup\limits_{k \in \mathbb{N}} TIME(n^k) $. This is what it means for a complexity function to be bounded by a polynomial: there is a constant $k$ such that the function is in $\mathcal{O}(n^k)$.


Enumerating the elements of an integer lattice $\mathbb{Z}^n$ The elements of $\mathbb{Z}$ can be enumerated as $0, 1, -1, 2, -2, 3, -3, \ldots$. Similarly, the points of the lattice $\mathbb{Z}^2$ can be enumerated

$$(0,0), (1,0), (0,1), (-1,0), (0,-1), (2,0), (1,1), (0,2), (-1,1), \ldots$$

I would like to extend this algorithm to $\mathbb{Z}^n$. Is there a simple way to do that?

Note that the ordering of the elements may vary. The only condition should be that if $B_1$ and $B_2$ are two closed balls in the metric $L^1$ on $\mathbb{Z}^n$, and $B_1 \subset B_2$, then all the elements of $B_1$ should be enumerated before any element of $B_2 - B_1$.

Your additional condition requires the tuples to be listed in ascending order of the sum of the absolute value of their components. We are free to choose the order of tuples with the same sum, so I propose the following procedure:

list(k,n) lists the $k$-tuples, where the absolute values sum to $n$:

For i=n downto -n:
  Output all outputs of list(k-1,n-|i|), each prefixed by i.

list(k) lists all $k$-tuples:

n=0;
While true:
  Output all outputs of list(k,n).
  n++.


Does this DFA describe this regular expression? For the expression (ab)*ba I came up with the following (very poorly drawn):

However, this was not the correct answer - apparently the solution requires five states. I don't understand why my DFA doesn't describe the expression. My interpretation of the expression is "ab any number of times, followed by ba". Is this correct?

For something to be a DFA, it should have transitions from every state for every letter in the alphabet. Your alphabet is {$a, b$}, so every state should have a transition for $a$ as well as $b$, e.g., your state 2 does not have a transition for $a$. Complete your DFA and you'll get what is that 5th state that you are missing.


Algorithm and proof for combining a list of node connections into groups of nodes efficiently My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a path between them have the same label (I believe the term for this is a "connected component") and nodes that do not have a path between them have different labels. Put another way, each connected component has a unique label.

NOTE: I haven't done all that much in the way of discrete math proofs since college, so hopefully you can bear with me and correct my terminology/methods if necessary.

To clarify, the data is in the form of a list of pairs of connected nodes.

For example:

n_1, n_3
n_3, n_5
n_5, n_7
n_5, n_9
n_2, n_4
n_4, n_6

In this <contrived> example, the odd-numbered nodes all belong to the same group, and the even-numbered nodes belong to another group.

I believe the way to do this is to process each item in the list according to the following rules:

Maintain an ordered list (call it "encounteredNodes") of all encountered nodes and the group label they have been assigned to
Maintain an integer variable (call it "nextLabel") that is incremented and returned each time a new unique label is needed
For each item in the list, determine if either node has been encountered yet.

If neither node has been encountered, get a new unique label from nextLabel and add both the nodes to encounteredNodes with this new uniqueLabel
If one node has been encountered but not the other, assign the label of the previously-encountered node to that of the unencountered node.
If both nodes have been previously encountered, take the lesser label of the two and use it to replace the label of all nodes in encounteredLabels that have the greater label of the two.

After one pass of this "for loop" through all the nodes, the algorithm is complete and the nodes have been grouped according to the goal. I believe the proof can be shown in this way:

Lemma 1: None of the operations can result in 2 previously encountered nodes that already have the same label being assigned to different labels. Because of this, already encountered nodes never "split off" from their group of nodes with the same labels, and once two nodes have the same label, they will never have differing labels (though they may change together to the same new label) for the remainder of the algorithm.

Assume there are two nodes that have a path between them via the list of edges, yet after the algorithm finishes, they have different labels (call them $L_1$ and $L_2$. If that's the case, then either...

They each contain a node (and these two nodes are directly connected), or...
there is a "chain" formed of groups of nodes where each group has the same label and the chain can be traversed to get from $L_1$ to $L_2$.

However neither of these scenarios can occur based on the algorithm. In the case of 1, there would have to have been a pair of connected nodes in the list where one node belongs to $L_1$ and one node belongs to $L_2$. However, after the algorithm processed this connection, both nodes would have the same label, and because of Lemma 1, they would have the same label until the end of the algorithm. In the case of 2, the neighbouring links in the chain could not exist because of the first case. Thus. This is a proof by contradiction.

Is this all sound? Also, I was never that great at algorithm runtime calculations, but I think it would be $O(n \log{n})$ because iterating the list of connections is linear time, but each iteration requires a search of ordered lists. Is this correct?

You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges.

The performance of the algorithm you described is much worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:

$v_{2k},v_{2k+1}$

$\vdots$

$v_2, v_3$

$v_0, v_1$

$v_{2k}, v_{2k-1}$

$\vdots$

$v_3, v_4$

$v_2, v_1$

The introduction of the edge $v_{2k}, v_{2k-1}$ requires relabeling $v_{2k}$ and $v_{2k+1}$, introducing $v_{2k-2}, v_{2k-3}$ requires relabeling $v_{2k-2}, v_{2k-1}, v_{2k}$ and $v_{2k+1}$. Finally, introducing $v_2,v_1$ requires relabeling $v_2,\ldots,v_{2k+1}$. This ends up being quadratic in $n+m$.

The idea behind your algorithm is somewhat valid though, and you can implement it much more efficiently using the Union-Find data structure which, if you will, can "defer" the relabeling.


will this be decidable or partially decidable? $A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$

Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is possible. Then deciding whether cardinality is greater than 3 should be decidable. But the material that i have been studying says it is partially decidable. Which one is right?

The language is clearly not decidable; use Rice's theorem. See e.g. our reference question.

We can certainly simulate $M$ on every input by dovetailing and count accepted inputs; if $|L(M)| \geq 3$ our counter hits three after finite time and we accept, otherwise we loop. Therefore, $A$ is semi-decidable.


Minimum spanning tree of a connected induced subgraph I'm doing an online course in which I'm struggling with the following multiple-choice question:

Suppose $ T $ is a minimum spanning tree of the connected graph $ G $.
Let $ H $ be a connected induced subgraph of $ G $. (I.e., $ H $ is
obtained from $ G $ by taking some subset $ S \subseteq V $ of
vertices, and taking all edges of $ E $ that have both endpoints in $
> S $. Also, assume $ H $ is connected.) Which of the following is true
about the edges of $ T $ that lie in $ H $? You can assume that edge
costs are distinct, if you wish. [Choose the strongest true
statement.]

For every $ G $ and $ H $, these edges form a minimum spanning tree of $ H $
For every $ G $ and $ H $, these edges are contained in some minimum spanning tree of $ H $
For every $ G $ and $ H $ and spanning tree $ T_H $ of $ H $, at least one of these edges is missing from $ T_H $
For every $ G $ and $ H $, these edges form a spanning tree (but not necessary minimum-cost) of $ H $

I don't understand why option 4 is not correct; the hint given is as follows:

Suppose G is a triangle and H is an edge.

Suppose that G is a triangle with nodes 1, 2, and 3, all connected, and we choose the subgraph H from nodes 1 and 2, thus including only the edge (1,2). That edge then forms a minimum spanning tree of those two nodes, no?
Incidentally, the answer

For every G and H, these edges for a minimum spanning tree of H

is also incorrect.

Suppose that $G$ is the triangle on $\{1,2,3\}$ (with arbitrary edge weights), that $T$ is $\{\{1,2\},\{1,3\}\}$ (without loss of generality), and consider $H = \{\{2,3\}\}$, which is induced by $S = \{2,3\}$. No edges of $T$ lie in $H$, and in particular these edges do not constitute a spanning tree of $H$.


Avoiding overflows while computing $e^x$ by Taylor series I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is:

$$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!} $$

from math import factorial
def e_x(x, n):
    return sum(pow(x, k)/factorial(k) for k in range(n))

Edit: Python seems to handle large integers pretty well so I'm more interested in the algorithm itself.

I want to avoid overflows during the calculation of the $k!$, so my intuition is that by looking at the $k$th-term and trying to do intermediary divisions an overflow might be avoided.

My naive solution was to just do $\frac{x}{k} \cdot \frac{x}{k-1} \cdot \ldots \cdot \frac{x}{1} \cdot \frac{x}{1}$, but the error became unbearable after some few iterations. I'm not using any high (arbitrary) accuracy floating point library (although I'm interested in knowing how would this be implemented in those).

Of course there are better numerical ways to compute exponential, but if you want to use Taylor expansion only, the better approach is to reformulate the expansion to avoid computing large nominators and denominators. This leads to an $O(n)$ algorithm, where $n$ is the number of iterations. Yours is $O(n^2)$ if you compute factorial and power literally (probably the python library is computing factorial with a gamma function and power with exp).

Here is a javascript program. print() is a function to write strings to console.

function myexp(x, max_itr)
{
    var y = 1.0, t = 1.0;
    for (var i = 1; i < max_itr; ++i) {
        t *= x / i;
        y += t;
    }
    return y;
}

var x = 1.2;
print("Math.exp: " + Math.exp(x));
print("10 iterations: " + myexp(x, 10));
print("99 iterations: " + myexp(x, 99));

The output is:

Math.exp: 3.3201169227365472
10 iterations: 3.3201150098285708
99 iterations: 3.3201169227365472

EDIT:

Alternatively, you can reformulate Taylor expansion as:

$$ e^x = 1 + \frac{x}{1}\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\cdots\right)\right)\right)$$

An implementation in javascript:

function myexp2(x, max_itr)
{
    var y = 0.0;
    for (var i = max_itr; i >= 1; --i)
        y = 1.0 + x / i * y;
    return y;
}


NFA or DFA for strings the contain exactly twice substring ab? Given the language with alphabet: $\{a, b, c\}$
Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$.
I'm stuck with "exactly twice $ab$". Can somebody give me some ideas. It's also very good if you can suggest me the regular expression of this statement.

To answer these kind of questions try to break down your problem into smaller parts.

Can you find a NFA that accepts all words that contain the substring $ab$ exactly once?
If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\circ L_2 =\{uv\mid u\in L_1 \text{ and } v\in L_2\}$?
Can you find a NFA that accepts all words that contain a $c$?
If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\cap L_2 =\{u \mid u\in L_1 \text{ and } u\in L_2\}$?

Steps 2. and 4. are well known closure constructions for regular languages. Its not hard to come up with these constructions by yourself, but there are also part in most of the textbooks.

As pointed out in the comments, the concatenation is in your case more subtle, since the first string might end with $a$ and the second one might start with  $b$. This can be fixed by setting $L_1:=\{w \mid \text{$w$ contains $ab$ once in the end}\}$. In particular, you can always split the words of your language exactly after the first occurrence of $ab$.


Why does a RNN network output different based on the training sequence I've set up an RNN LSTM network in Java using DL4J as the library.

I currently have 500 examples of positive text, and 500 examples of negative text.

When I fitness the training data by first training all the negatives and then all the positives, my predictions only favor high positive responses even for things that would be considered negative in my training examples.

And if I reverse it and train positive first and then train negative last everything is favored as a negative in high 80 - 90%.

However, when I train in an oscillating pattern such as: Positive, Negative, Positive, Negative and so on, the predictions become accurate again and similar examples of negative text are picked up relatively accurately and vice versa for positive text.

I've only just started studying machine learning in general but I can't quite find any resources explaining why the sequence of training impacted my model so hugely. Is this normally how an LSTM network should behave or is oscillating the training data the correct approach?

Would the classification of a messages negative intent be something an LSTM RNN network should be used for or should I consider another network?

RNNs are pattern recognition tools. It is't entirely clear to me what it is exactly that you are trying to do, but if you simply intend for it to classify positive and negative messages a regular Neural Network might be better suited.

What your RNN does (if implemented correctly) is learn classifications in the context of the sequence. i. e. It is learning: what are the odds of a given input X being positive/negative knowing the preceding N outcomes.

This should already be giving you some insight on why different orderings of the training data skew the results. If your training set is all positives followed by all negatives then the vast majority of your training set will be teaching the network that a sequence of positives almost certainly indicate a positive message and vice versa.

Building a good dataset is by far the most important part of applying machine learning and I suggest you look for some high level explanations of the different types of ML and some general information on bias in data.


Median-of-Medians proof for time complexity Wikipedia mentions, that from the formula
$$
T(n) \leq T(n/5) + T(n\cdot7/10) + c \cdot n
$$

one can "easily" show using induction that

$$
T(n) \leq 10 \cdot c \cdot n
$$

I am, as it seems, not so smart. So, can anyone tell me how to show this using induction?

Assuming that you got the base covered, here is the inductive step:
$$
T(n) \leq T(n/5) + T(7n/10) + cn \leq 10c(n/5) + 10c(7n/10) + cn = 10cn.
$$
(Cheating a bit, since $n$ isn't necessarily divisible by 10; but that's a problem in the recurrence.)

You can also just apply the Akra–Bazzi theorem.


What kind of pattern recognition algorithm would Facebook use to detect suicidal users? Facebook announced that it would employ a machine learning "reporting process using pattern recognition in posts previously reported for suicide" (https://newsroom.fb.com/news/2017/03/building-a-safer-community-with-new-suicide-prevention-tools/).

Could anyone explain in more detail how this pattern recognition algorithm might work in their reporting system? Is it possible to say what kind of classification algorithm are they most likely using? Something similar to a spam filtering algorithm?

Here's the section I quoted from:

"Based on feedback from experts, we are testing a streamlined reporting process using pattern recognition in posts previously reported for suicide. This artificial intelligence approach will make the option to report a post about 'suicide or self injury' more prominent for potentially concerning posts like these. We’re also testing pattern recognition to identify posts as very likely to include thoughts of suicide. Our Community Operations team will review these posts and, if appropriate, provide resources to the person who posted the content, even if someone on Facebook has not reported it yet"

I would take march average to calculate several indicators from posts of the same user including but not limited to:
 - emotional-tagged words from posts (using available dictionary for this purpose)
 - sudden changes in the writting style
 - response times to messages
 - relationship changes
 - job changes

Also tagged messages reported by users, if it abides with policy also filtering concerns from private messages (reading them is probably illegal, but feeding machine learning scripts, maybe would be ok). For the supervised learning, the morbid idea is to feed learning algorithm the posts of people who made attempts.

To feed any data it should be preprocessed (to get rid of noise - texts that have no indicating value), possibly with included data about gender, age, education. Since it may not be properly filled in, maybe some additional scavenging and recognition of profile images (to determine age fir example) may be needed.

From reading the link it looks like scheme to allow flagging concerns, also the group of experts is reviewing the reports, so it is for sure mixture of unsupervised, supervised and experts learning system, scrapping every possible data.

To answer the main question, it depends on data acquired, resources available (for example how many review hours from experts they are willing to afford). The gathered data (and assumed certainty) shapes the used algorithms. The other problem is that there are no good enough tests to tell apart depressed or suicidal people apart based only on social media or written tests, so my bet is there are at least several algorithms formed into polling system, quite like ICD-11 or DSM-V diagnostic manuals, poll-based operationslisation of state to detect disorders. But the sentiment analysis gives roughly 20% of good results when used for opinions, for emotion detection it vastly degrades, so this approach would not be considered as is for safety reasons. The Stanford NLP unit works hard on higher level understanding of text, with sentiment analysis demo available. It works poorly for short texts, peaking at moderately long ones. It may be incorporated into longitudal working (time based consecutive tests), where afaik it could yield 25% for negative mind state of user.

Your idea of spam filtering may work in this context, where filter detects anomalies of behaviour or predefined patterns comming from tagged messages, but it must yield many false positives (due to weak patterns available).

The natural choice would be RNN, as Martin wrote, to account for dynamic temporal behaviour, if any other NN is used, such feature would be simply emulated, to match temporal behaviour of suicide plans. Estimating risk factors and including personal data (some auxiliary tests are required to asses personality traits, hopefuly these are quite accurate and work even in transparent setting, when someone is evaluated from behaviour), there should exist several time scale factors independently at least for every main personality type. The main disadvantage here is accuracy of profile data, for example five years inaccuracy in the age field filled by user matters. If someone for some reasons fills birthday date wrongly, the learning system cannot depend on valuable data what user does that day and whom meets. This may seem as tangential, but users privacy is important here, if someone feels insecure, the important data is lost, otherwise inferrence is inaccurate.

TLDR;
The algorithms used is not arbitrary chosen, it does not matter which one is performant or accurate for some tasks, it is data dependend choice, so it is hard to pick. Another factor is assesment, which is far from ideal. We can conclude that there are non-standard algorithms created solely for this task (perhaps including several known ones), but the heavy lifting is still done by people, as the machine learning works as screening test, flagging for review.

The fresh and interesting article about Predicting Risk of Suicide Attempts Over Time Through Machine Learning claims 80-90% accuracy, but is not applicable here, because it uses medical records to work.


point clouds in machine learning What is the purpose of point clouds in machine learning?

Consider the following suggestion:
Say I have a table (per year) of records (such as days) each of which is made of n real numbers such as temperatures per hour). Can I use the table as a data point to do classification of the year as hot/cold or something like that?

Any real-world examples of point cloud data?

The term "point cloud" is normally used to refer to a set of points (locations) in 3D space.  So, a table of temperatures would normally not be called a "point cloud".


Where can a student learn image processing? I am a student of computer science with interest in image processing. I have learned how to apply a few effects to images like making them grayscale, sketching them out of lines, etc.

I would like to learn more about the algorithmic techniques  behind creative manipulation of images like making them sepia-tone, smudging them, etc.

Can someone please point me in the right direction?
How do I learn the fundamentals of these algorithms?

There are books on digital image processing which you can look into. Many common image manipulation techniques, such as smudging (usually known as blurring) are accomplished by image filtering, which is a process of applying a two-dimensional filter to an image: the value of each pixel in the new image is a linear combination of its original value and the original values of its neighbors. Sepia tone is an example of color manipulation: assuming the image is stored as RGB, this amounts to applying some carefully constructed mapping on the R,G,B values of each pixel. The mapping can be represented as a table $\{0,\ldots,255\}^3 \to \{0,\ldots,255\}^3$, or alternatively some formula can be applied instead.


An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

I came across the following topic titled Bad Case for Subset Construction (2.3.6). I cannot follow the example given over there, about NFA N that can accept strings with 1 at the $n^{th}$ position, and that the DFA formed from that NFA thereafter will have no equivalent with fewer than $2^n$ states.

  They argue that The DFA $D$ must be able to remember last n symbols it
  has read. Since any of the $2^n$ subsets of the last n symbols could
  be 1, if D had fewer than $2^n$ states, then there would be some state
  $q$ such that $D$ can be in state $q$ after reading two different sequences of n bits, say $a_{1}a_{2}...a_{n}$, and $b_{1}b_2...b_n$.

Here is an extract from the book itself:

I have been trying to comprehend the proof, including this line and the subsequent paragraph that follows, but I have not been able to.

Can someone please explain the approach ?

The proper way to do this proof is using Myhill–Nerode theory, which I will now explain. For a regular language $L$, say that $x,y$ are inequivalent if there exists a word $z$ such that $xz \in L$ and $yz \notin L$, or such that $xz \notin L$ and $yz \in L$. In every DFA accepting $L$, the state that is reached after reading $x$ is different from the state that is reached after reading $y$ (exercise). Hence, if we find a collection $x_1,\ldots,x_M$ of words such that $x_i,x_j$ are inequivalent for all $i \neq j$, then every DFA for $L$ must contain at least $M$ states (exercise).

For your language $L = \Sigma^* 1 \Sigma^{n-1}$, you can take as your collection of words the set of all words of length $n$. If $x,y$ are two different words of length $n$ then $x_i \neq y_i$ for some $i$; say $x_i = 0$ and $y_i = 1$. Then $x 0^{i-1} \notin L$ (since the $n$th from last bit is $x_i$ = 0), whereas $y 0^{i-1} \in L$ (since the $n$th from last bit is $y_i$ = 0). This completes the proof.


Algorithm A vs Algorithm A*: What's the difference? I can find quite a bit of literature on A* but very little on A.

What is the difference between the two search algorithms?

Both A and A* algorithm use a best-first search to find the least cost path from a start state to a goal state.

Best-first search applies a heuristic evaluation on the states to find the 'best' state.
Consider the evaluation function f,

f(n) = g(n) + h(n)

where g(n) measures the cost of reaching any state n from the start state
and h(n) is a heuristic estimate of the cost of going from state n to a goal.
f(n) estimates the total cost of the path from the start state throngh n to the goal state

If this evaluation function is used with best-first search, then the result is Algorithm A.
Here h(n) is just an estimate of the cost of going from n to a goal. The actual cost is not known.

Now consider the evaluation function f*,

f*(n) = g*(n) + h*(n)

where g*(n) is the cost of the shortest path from start state to state n
and h*(n) is the actual cost of the shortest path from state n to goal.

Although f* does not exist for most real problems, we would like f to be a close estimate of f*.
In algorithm A, g(n) is a reasonable estimate of g*(n).

g(n) >= g*(n)

They are equal when the graph search has discovered an optimal path to n.

Although we may not compute h*, it is often possible to determine whether or not the heuristic estimate h(n) is always less than or equal to the actual cost of minimum oath, h*(n).

If the Algorithm A uses a function f in which

h(n) <= h*(n) ,

it is called algorithm A*.


Is there a problem that cannot be represented using graph? It is obvious that the representational power of graphs are huge.
Is there a problem that cannot be represented using graph?

I have recently asked this question to my students and no answers came up. I could not answer this either.

For instance:
Problem: Finding the shortest path between two given cities in a country.
Graph type: Directed, weighted.
Vertices: Cities.
Edges: An edge $(i,j)$ indicates there is a way from city $i$ to city $j$ and weight of $(i,j)$ indicates the distance between cities $i$ and $j$.

Problem: Expressing your feelings using crayons.
Graph type: Directed, weighted.
Vertices: Neurons in the brain.
Edges: Values of electronic signals being transmitted among neurons.
Output: Interpretation of the signals by the brain.
(Just kidding)

Edit:
Problem in this post means, a problem that can be solved using computers.

It's trivial to encode natural numbers as graphs (represent $n$ by a path of length $n$, or by $K_n$) so anything that can be represented as numbers can be represented as graphs.


Why is this function computable in $O(n^{1.5})$ time? My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$ such that $n$ is sandwiched between $f(i)$ and $f(i+1)$."

How can I convince myself that we can in fact easily find $i$ in $O(n^{1.5})$ time? As $f$ is defined recursively, I think we have to compute $f(1),f(2),f(3)\dots f(j)$ until $f(j)\geq n$. In order to find out the time that these computations take, I think we have to find a suitable upper bound for $i$ dependent on $n$ and we have to find an upper bound on the execution time of the function $x\to2^{x^{1.2}}$. In the end, we can hopefully show the quoted proposition. Unfortunately, I don't see neither one thing nor the other.

I forgot to mention: Please note that we are in a nondeterministic context. So $f$ is claimed to be computable in $O(n^{1.5})$ by a nondeterministic Turing machine.

As quite a few people have already read this question, with some of them finding it useful and interesting too, but nobody answered so far, I want to provide some more information on the context: The quoted claim is an integral part of the proof of the nondeterministic time hierarchy theorem. The proof (with the claim) can be found e. g. in the book by Arora and Barak, but I have found quite a few other resources on the Web too which present the same proof. Each of those calls the claim easy or trivial and does not elaborate on how to find $i$ in $O(n^{1.5})$ time. So either all these resources just copied from Arora and Barak or the claim is in fact not so difficult.

Denote by $|x|$ the length of a number $x$, i.e. $\lfloor \log_2 x \rfloor + 1$ (for $x > 0$). Calculating $2^x$ requires time $O(x)$ in the RAM model, and so calculating $f(i+1)$ from $f(i)$ takes time $O(f(i)^{1.2}) = O(|f(i+1)|)$. Since $f(i)$ is growing faster than geometrically, the overall time to calculate $f(i+1)$ is $O(|f(i+1)|)$. As you point out, you need to do so until $f(i+1) \geq n$, which means that $f(i) < n$. Therefore the total running time is $O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$.

In the Turing machine model with a single tape, calculating $2^x$ takes time $O(x\log x)$, and so the total running time is $O(n^{1.2} \log n) = O(n^{1.5})$. The algorithm for computing $2^x$ replaces $[x]$ by $1[[x]]$ (here $[x]$ is the binary representation of $x$, and $[[x]]$ is the binary representation using different digits $0',1'$), and then repeatedly runs the transformation $[[x]] \longrightarrow 0[[x-1]]$, which takes time $O(|x|) = O(\log x)$.


Turing Machine That Accepts Machines With Undecidable Languages So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) is undecidable }. (in words, a Turing machine that accepts encodings of machines that accept undecidable languages.)

I'm trying to reduce the accepting Turing machine (A TM) to Undecidable TM in the following manner:

Take Turing machine M and string x as inputs.
Create M' that works as follows: For input y, M' simulates M on x. If M accepts x, then M' acts on y as some Turing machine that accepts an undecidable language. Else, M rejects y.
Pass M' to Undecidable TM. Iff Undecidable TM accepts M', then M must accept x, else M' does not accept an undecidable language.
Thus, we can decide whether a machine M accepts input x.

The problem is that I cannot create a machine that accepts an undecidable language to put inside M' for this reduction. I have read my lecture notes and looked for advice on Google, but haven't made any headway. I'd appreciate it if someone has some insight on how to finish this proof or approach this another way. Thanks a lot.

The language you are describing is called an "index-set", which means that it is accepting languages, rather than machines specifically. More formally, if we have two machines $M_1, M_2$, and $L(M_1) = L(M_2)$, then $M_1 \in Undecidable \iff M_2 \in Undecidable$.

There's a theorem called Rice's Theorem that says that index sets are always undecidable. The proof on the Wikipedia page shows how you can reduce the halting problem to any index set.


Each finite segment of a noncomputable integer sequence is computable Wikipedia claims that "each finite segment of noncomputable sequence of integers is computable".

It continues to clarify: For any noncomputable function, "for any given value of n, [...] a trivial algorithm exists (even though it may never be known or produced by anyone)".

While I do believe this for the given example with busy beavers, I am not certain this is always correct. Is there a proof of this statement?

This is quite a fundamental point in computability theory, which has to do with the difference between being able to find and algorithm and knowing that an algorithm exists.

To illustrate the point, suppose I tell you that I'm thinking of a number between 1 and 10. Is there an algorithm that prints the number I'm thinking of? Of course! for every $i\in \{1,...,10\}$ there is an algorithm that prints $i$ and halts, so in particular, there is an algorithm that prints the number I'm thinkng of.

Do you know which algorithm prints the number I'm thinking of? no.

Similarly, every finite sequence can be printed by some algorithm. If you have a computable representation of that sequence, you can also find that algorithm, but if this finite sequence is given as an uncomputable function, then you cannot find the algorithm.

One classic example for this issue is the following: consider some TM $M$ and input $w$, we define the number $t$ as follows: $t=1$ if $M$ accepts $w$, and $0$ otherwise.

Is there an algorithm that prints $t$? yes - either the algorithm that prints $1$ and halts, or the algorithm that prints $0$ and halts.

Is there an algorithm that, given $M$ and $w$, computes the algorithm that prints $t$? No - as this would contradict the fact that $A_{TM}$ is undecidable.


DFS produces the correct Topologically ordered sequence Prove that DFS produces the correct topologically ordered sequence.

I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph.
Now to prove that the above algorithm returns a topological sorting, we can use some lemmas about DFS $-$ namely the Parenthesis Theorem as well as the White Path Theorem. I will not get into the proofs of each lemma but we will use the following:
A corollary of the parenthesis theorem, as follows:

Consider vertices $u$ and $v$ in $G$. Then $v$ is a descendant of $u$ in the DFS forest of $G$, if and only if $d(u)<d(v)<f(v)<f(u)$, where $d(x')$ is the discovery time of vertex $x'$ and $f(x')$ is its finish time.

Also, we will use the white path theorem which states that

Vertext $v$ is a descendant of vertex $u$ in the DFS forest if and only if at time $d(u),$ there exists a white path from $u$ to $v.$

Now let $e = (u,v)$ be an edge in the input graph. We want to prove that in our output, $u$ comes before $v$. We can show that by proving that in our DFS traversal, $f(u) > f(v).$
CASE I: $d(u) < d(v)$
By the White Path Theorem, $v$ is a descendant of $u$. This is because at time $d(u)$, there is a white path in $G$, which must be from $u$ to $v$ as there exists edge $e = (u,v)$. Hence, we can use the corollary of the parenthesis theorem to show that $f(u) > f(v).$
CASE II: $d(v) < d(u)$
At time $d(v)$, there is no white path from $v$ to $u$, as that would imply that $G$ has a cycle (meaning that it is not a DAG), and hence $u$ cannot be a descendant of $v$ in the DFS forest of $G$. So by the parenthesis theorem, we have $d(v) < f(v) < d(u) < f(u)$. Again, we proved that $f(u) > f(v)$.
Hope that helped :)


Check if language is decidable I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.

I know that every finite language is decidable, but I am not sure if this has anything to do with this particular problem.

Every help is appreciated, I am a little lost.

Thank you

Define C = { $L | L$ is decidable by a turing machine with at most 42 states }

Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^*$

By Rice's theorem, the language $S=$ { $w | L(M_w) \in C$ } is undecidable. This language is precisely the language in question


Showing that DNF VALID is coNP-hard I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), but I'm really struggling to show that DNF VALID is coNP-hard.

  The complement of DNF VALID = {ϕ | ϕ is not in DNF OR ϕ is falsifiable}

A simple algorithm for the complement of DNF VALID:

On a non-deterministic TM M: "on input ϕ (boolean formula):
 1. Scan through ϕ and check whether ϕ is on DNF.
      If it is, accept,
      if not, continue to step 2.
 2. Non-deterministically choose a valuation for ϕ
 3. If ϕ is falsifiable accept, if not, reject

To show that DNF VALID is coNP-hard I think that I need to show that a language that is NP-complete can be reduced in polynomial time to the complement of DNF VALID, but I'm not sure with which language to choose, and I could really use some help on how to go forth with the reduction.

A formula $\varphi$ in DNF is valid if and only if $\neg\varphi$ in CNF is unsatisfiable. Since CNF-SAT is NP-complete, it follows that DNF-VAL is coNP-complete. You are right that you need to show an NP-complete language can be reduced in polynomial time to the complement of DNF-VAL. Since this complement is just CNF-SAT, try reducing SAT to CNF-SAT.

There are a lot of proofs of this reduction around; this one[1] looks good if you just want to see an answer.

[1] Howell, Rod. "SAT-CNF Is NP-complete." (2000).


How can a probability distribution across classical states be computed for the measurement of a Quantum State represented by a Complex Vector? Suppose I have a quantum state represented by a Complex vector, arbitrarily:

$[~-0.538, 0.044 - 0.323i, 0.706, 0.044 + 0.323i~]$

With each value in that vector corresponding to some classical state:

$[~ |00\rangle, |01\rangle, |10\rangle, |11\rangle ~]$

What is the correct mathematical formula to derive a probability distribution across possible classical states that could be observed in measurement from this complex vector?

E.g. how do I find individual real values for $p(|00\rangle)$, $p(|01\rangle)$ etc. in this example?

The quantum state is a vector $v$ of unit norm. The probability of measuring outcome $x$ is $\|v_x\|^2$, the squared magnitude of the corresponding coefficient in the vector. Since $v$ has unit norm, these probabilities add up to $1$.


Join with Bloom-filters can you tell me how i can use a bloom-filter by a joining operation with two tables?

let's assume that:

Table A ={A_id,B_id,age}, Table B = {B_id, color}.

now i want to use a bloom-filter so i can do the join operation faster, but i do not know how i can use this in this case.
I would first take from A the PK A_id and bloom-filter that with some hash functions and just mark the indexes with 1 and then i would do the same operation with Table B and finally just AND both results. but it's not correct...

A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives.  A join (specifically, an equi-join) which is expected to have some non-matching keys can be sped up by pre-processing the valid keys from one table into a Bloom filter.  The join operator tests each key from the other table against the Bloom filter first and only does a full lookup for each positive ("maybe in the set") result.

For instance if you are joining on B_id above, you might first preprocess all of the B_id's in table B into a Bloom filter, and use it to test each B_id in table A for a possible match.  If a B_id from A tests negative in the filter, you can discard it, so you only consult table B for B_id's which are either in B or are false positives.

The benefit of using a pre-filter is basically in the number of negatives it can eliminate at a lower per-key cost than a full lookup.  The filter may also be a smaller size than the set of keys it represents, so it can be broadcast to all threads or nodes that are processing the join in a distributed environment.

Ives and Taylor summarize a number of techniques like this in Sideways Information Passing for Push-Style Query Processing.


Are two languages regular if the union is regular? Statement:

  For any two languages $L_1$ and $L_2$ if $L_1 \cup L_2$ is regular, then $L_1$ and $L_2$ are regular.

Why is this statement false? Could somebody give me an example.

Pick $\Sigma = \{a,b\}$, $L_1 = \{ a^n b^n : n \in \mathbb{N}\}$ and $L_2 = \Sigma^* \setminus L_1$.

The union $L_1 \cup L_2$ is $\Sigma^*$ and hence is regular, but none of $L_1$ and $L_2$ is.


How do deal with the following situations using Prim's algorithm? Consider the following Graph

We want to generate the MST using Prim's algorithm.

Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other alternatives.

Do we ever take the self loop? Why not?

Suppose we just moved from C to D

D only has one edge connecting to E, under Prim's algorithm we will take that edge right?

Now we have travelled from C to D to E, now I am making a choice at E. By picking the edge with the lowest weight we are back at C and the loop from C, D, E continues on forever

What should we do if we enters an in-terminating loop?

First of all , MST of a connected graph is a subgraph with the following properties:
i. Spanning Tree: No cycles -> n-1 edges(easy to prove)
ii. If we sum up the weights, we get the lowest possible.

Prim's algorithm is a greedy algorithm, which means that we always choose the best choice in every step(greedy).

From i, you can see that you never get self loops (acyclic).
Yes, because it's the edge with the lowest weight not because it is the only edge in this moment from D to connect in E; there maybe exist another edge eg. C->E would have been the next choice had the weight between D->E is 5.
No, it does not get to a non-terminating loop, you never choose the same edge again. Think like, there is a set S with all the edges that have not been discarded, after you choose the edge e then S is changed to S-e. In your example the best choice is to choose E->F.


How can I find minimum number required to add to sequence such that their xor becomes zero Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.

Consider the following examples :

For $1, 3$ the answer is $2$;  adding $2$ to $1$ we get $3 \oplus 3=0$.
For $10, 4, 5, 1$ the answer is $6$;  adding $3$ to $10$ and $3$ to $5$ we get $13 \oplus 4 \oplus 8 \oplus 1 = 0$.
For $4, 4$ the answer is $0$, since $4 \oplus 4 = 0$.

I tried working on binary representations of sequence number but it got so complex. I want to know if there is any simple and efficient way to solve this problem.

It seems to me that $a = a_i \oplus \dots \oplus a_n$ holds all necessary information: the $1$bits in $a$ are the bits you need to flip in (exactly) one of the $a_i$. As you are only allowed to add, you have to find one $a_i$ where the corresponding bit $j$ is $0$ and flip it -- this causes the same cost for all $a_i$, that is $2^j$, so the choice does not matter. Trouble begins if there is no such $a_i$.

That is why you have to do this iteratively and work from the least significant bit upwards. Proceed as above; if there is no suitable $a_i$, choose the $a_i$ with the maximum number of $1$ bits left of the current position -- this increases the chance of finding a suitable candidate in future iterations --, flip the bit and carry over, that is flip all ones to the left until you flip a zero to a one. Note that we still add $2^j$). As carry propagates only to the left, earlier choices are not invalidated. Recompute $a$ and continue with $j+1$; iterate until you have $a=0$.

Note that this is only a heuristic as far as I can tell: the choice of $i$ may be suboptimal if it causes many bits in $a$ to become non-zero. I am not sure if this can be avoided.


Can you apply neural networks to design algorithms? I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math problems.

A few CS/math friends were teaching me about P=NP and I was wondering whether a potential way to identify an algorithm that can convert the exponential time it takes to solve NP solutions into polynomial time is to use a genetic algorithm that applies brute-force until such an algorithm is identified.

Apologies if I’m misunderstanding anything or being too naive. Thank you for your time.

There are a few issues to consider.

If P!=NP, this approach is doomed from the start because you can't try every one of the infinite number of possible algorithms in finite time. That's I think the main deal-breaker here. Unless P=NP, which most people doubt, then the best you could ever do is say "my AI failed to find a polynomial-time algorithm in X amount of time", which doesn't mean no such algorithm exists. If you assume that P=NP, then in principle, an evolutionary algorithm, neural network, or other search technique could potentially find an example of a polynomial algorithm for an NP-complete problem, and that's all you need to prove that P=NP.

In practice, there are some challenges to deal with. I'm sure certain approaches would be more natural to try than others. Neural nets require numeric vectors of inputs and outputs, so you need to develop some way to encode an algorithm as a vector and a way to determine a binary "is_polynomial" so that you have an error gradient to follow. Or I suppose a continuous function measuring "degree of polynomial-ness" if such a thing makes sense. You're certainly going to need some way to measure success regardless of approach, but something like Genetic Programming could theoretically eliminate the need for a cumbersome translation of algorithm to real vector, since GP operates directly on an executable representation. Give it a Turing-complete set of operators to work with and it could presumably eventually find a polynomial solution if such a thing exists.

It's also far from clear that you have a friendly search space to work with here. I think most of the time, your hypothetical GP or whatever is going to wander around a very flat plateau of individuals that don't even successfully solve the problem, regardless of run-time. You could attempt to introduce a gradient to follow by favoring shorter programs or programs that terminate faster or whatever thing you came up with, but there's no good reason to think that gradient points in the direction of the prize-winning algorithm you're looking for. Theoretically, there are fairly easy conditions to meet that say given infinite search time, a given algorithm will eventually find any arbitrary solution that exists, but a workable algorithm in practice tends to require there be some structure in the search space that can be exploited. If you make a local move somewhere in the space that looks like it's better, you want that move to take you generally closer to the solution you're looking for. If the world looks basically random in terms of what moves me closer or further away, search algorithms struggle to do better than just randomly trying things.

Short answer, it's conceivably possible to build an algorithm that searches for poly-time solutions to an NP-hard problem, but the world is likely constructed so that that won't actually solve the problem you hope to solve.


Why is superscalar processor SISD? From Wiki - Superscalar processor:

  (Line 1): superscalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor. In contrast to a scalar processor that can execute at most one single instruction per clock cycle, a superscalar processor can execute more than one instruction during a clock cycle *by simultaneously dispatching multiple instructions* to different execution units on the processor.

  (Line 8): In Flynn's taxonomy, a single-core superscalar processor is classified as an *SISD* processor (Single Instruction stream, Single Data stream)

I understand ILP, which means two instructions executed at the same time. My problem is that: If one doesn't fetch two instructions simultaneously, how can it dispatch multiple instructions to different execution units...? Or I misunderstand the meaning of instruction stream, which it's single stream but one can fetch two instructions at the same time, why sounds so counter-intuitive?

From Wiki - SISD:

  (Line1): In computing, SISD (single instruction stream, single data stream) is a computer architecture in which a single uni-core processor, executes *a single instruction stream*, to operate on data stored in a single memory.

There is a single instruction stream. Modern processors just manage to pick up multiple instructions from the instruction stream simultaneously.

For something like a POWER processor, where each instruction is always four bytes in size, that is quite easy. Instructions are loaded into cache lines, and if a cache line holds 8 or 16 instructions, it is quite easy to read four instructions at the same time.

For an x86 processor, it is more difficult because instructions have different sizes. Still, it is possible (with a lot of effort) to read several consecutive simple instructions simultaneously.


Upper and lower tangent line to convex hull from a point Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper tangent line if orientation of $S,i,i+1$ is greater than zero (anti-clockwise) and if orientation of $S,i,i-1$ is greater than zero as well. Same for lower tangent line where I checked if its clockwise orientation. $S$ is a point from where I want my tangent line to go, $i$ is a point on a convex hull and $i-1$,$i+1$ are its neighbours. This is the only source I've found so far [Link]$_1$ and I really can't understand the algorithm for now.

Let's assume that the convex polygon $P$ is defined as an ordered list $(p_0,p_1,...,p_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$ and a next point $Next(p)$ according to this order, taking into account that:
$$Prev(p_0)=p_{n-1}$$
$$Next(p_{n-1})=p_0$$
The binary search over this list is very similar to a binary search over a regular array - on each step you have a $p_{left}$ point, a $p_{right}$ point and a $p_{mid}$ point. You check some condition on the $p_{mid}$ point and then choose a $[p_{left},p_{mid}]$ interval or a $[p_{mid},p_{right}]$ interval for the next step.
The condition you want to check is the following one. In order for the $p_{mid}$ point to be the tangential point for all lines going through the query point $S$, both neighbors of the $p_{mid}$ point must be on the same side of the line, connecting the point $S$ and the $p_{mid}$. You'll have to choose, which side of this line is right and which side is wrong - this will define, which tangent line you'll get (upper or lower). So, if the previous point $Prev(p_{mid})$ is on the wrong side, then you choose the left interval. Similarly, if the next point $Next(p_{mid})$ is on the wrong side of this line, then you choose the right interval for the next step. This algorithm will stop on one of two tangential points if and only if the point $S$ is located outside of the polygon $P$.
The algorithm doesn't need any preprocessing of the convex polygon $P$ and nevertheless finds tangential points for any query point, located outside of the polygon, in $O(\log n)$ time.


Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1? Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ extends naturally to languages: if $L$ is a language over $\{a, b, c\}$, then $f(L)$ is the language over $\{0, 1\}$ defined as $\{f(w) \mid w\text{ is in }L\}$.

Prove that if a language $L$ is decidable, then so is $f(L)$.

I am thinking that since $L$ is decidable it must be regular so there exists a DFA for $L$. $f(L)$ is closed -- dk how to prove though. Then $f(L)$ is also regular. Therefore is also decidable.

Let $f$ be any computable mapping such that $|f(x)| \geq c|x|$ for some $c > 0$. For every language $L$, if $L$ is computable then so is $f(L)$.

To see this, let us be given an input $y$. We go over all strings $x$ of length at most $|y|/c$. For each of them, we check whether $x \in L$ and $f(x) = y$. If we found such a string $x$, then $y$ is in the language, otherwise it isn't.


How are bitwise operators used in normalisation of floating-point numbers? After having spent a significant amount of time googling this topic, I am still struggling to confidently answer the following question:
Identify the process using logical operators to normalise a floating-point number.

My first assumption was, we use the binary shift to remove the leading 0's (for positive numbers) or 1's (for negative numbers) and then use XOR to increase the exponent by the required amount.
I do not understand, however, what happens to the binary point.
Let's say we have the number 1.75 represented as 000001.11 in 8-bits. If I shift it to the right by one place, I lose the 1 at the end. If I shift it to the left by 4 places, how does the computer know to move the binary point between the first two bits from the left? I am lost. How do bitwise operations work in this case?
Thank you in advance for your time and help.

It's helpful to think of the number in the following representation( I choose 3.75 as an example):
$$2^0 * 11.11_2  = 3.15$$
Now $2^0 = 1$ so we can just write it in front of the number. Now we want to normalize $3.75$ meaning we need to transform it to $2^e * 1.m$ where $e$ and $m$ are some bitstrings. Notice that we can shift a binary number to the left by dividing it by to e.g. $4 = 100_2 = 2* 010_2 = 2*2* 001_2$. I hope you can see how dividing/multiplying by 2 corresponds to shifting (in base 2!). Lets shift 3.75 in such a way that a 1 is in front of the comma:
$2^0 * 11.11_2 0 = 2^1* 1.111_2$; as you can see we shifted 3.75 and thereby pulled a $2$ out of it and increased the exponent to account for the $2$. The value of the number is still 3.75 it's just written down as $2* 1.875$. This is the normalized form. Now the exponent $e$ and the places behind the comma are stored in a floating point number. Why don't we need the $1$ in front of the comma? Cause the normalized form guarantees that there is a 1 so it's redundant to store it.


Greedily Schedule Events based on value/hours Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts 5hrs and has a value of 10 then you will gain 10 points. If you only attend for 3 hours, you only get 3*(10/5) = 6 points. The output that the algorithm should produce is the maximum number of points that can be obtained by attending combinations of various events. Note: you are allowed to leave and come back to an event.

My Algorithm (pseudocode):

Sort all the events $E$ by order of their $v_i/h_i$ ratio to produce a new set of events $E'$ such that $E'[1]$ has a higher value/hours ratio than $E'[2]$, $E'[3]$, etc...
$max = 0$
For each event $e \in E'$

$h =$ hours that have not yet been taken
$max\ += h* (e_{v_i}/e_{h_i})$

Note: I did not specify in the algorithm how to determine the hours that have been scheduled/taken already but you can assume that there is an array that flags hours that have been scheduled.

I do believe that my algorithm gives the optimal result, but how do I prove this?

I'm assuming that the value given to $h$ in each step is "number of hours during the running of the event, which are not yet covered". (Your wording is somewhat ambiguous.)

In  the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

From the constraints given, we see that the event visited at one point in time has no influence on the profit we can make at a different moment in time. Thus, the optimal solution will be to visit the most profitable event at each point in time, i.e. during each hour. Now, we only have to show that the algorithm achieves this:

Assume that there is an hour $h$ during which the algorithm suggests to visit event $e$, while visiting $e'$ would be more profitable. Since $e'$ is more profitable, it will have been put before $e$ during the first step of the algorithm. Furthermore, since $e'$ has been scheduled for $h$, $h$ must have been available when the algorithm processed $e$ and (since the algorithm never frees an hour) also when it processed $e'$. But this means that the algorithm would have scheduled $e'$ for hour $h$, contradicting our assumption. Thus we conclude that the algorithm is correct.


Largest number of unique values in sets Let's say I have 100 sets of values, and each set contains roughly 100,000 values.  From these sets, I want to find the 10 sets that collectively have the largest number of unique values.

The brute force method of just checking all combinations is a combinatorial nightmare.  I also thought about doing a rough approach (solution doesn't have to be perfectly optimal) of just finding 'the next best set' to add in sequence.  So finding the largest set, then checking each of the rest of the 99 sets for smallest overlap, then checking the next 98 sets for smallest overlap, etc, but that's still 100+99+98+97+96+95+94+93+92+91 = 955 things to do.

Is there something more efficient?

Your problem is known as Maximum coverage. The greedy algorithm (repeatedly take a set which covers the maximum number of uncovered elements) is a $1-1/e$ approximation, and runs quite efficiently.


Proof that a randomly built binary search tree has logarithmic height How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't understand it.

Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced:

Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this case 3). With a little math, $n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$, which is to say it has $O(\log n)$ height. For the entirely unbalanced tree, the height of tree is simply $n-1\rightarrow O(n)$. So we have our bounds.

If we were constructing a balanced tree from an ordered list $\{ 1,2,\dots,n\}$, we'd choose the middle element to be our root node. If we are instead randomly constructing a tree, any of the $n$ nodes are equally likely to be picked and the height of our tree is: $$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$
We know that in a binary search tree, the left subtree must only contain keys less than the root node. Thus, if we randomly choose the $i^{th}$ element, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements, so more compactly: $h_n=1+\max (h_{i-1},h_{n-i})$. From there, it makes sense that if each element is equally likely to be picked, the expected value is just the average of all cases (rather than a weighted average). Hence: $\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

As I'm sure you've noticed, I've deviated slightly from how CLRS proves this, because CLRS uses two relatively common proof techniques that are disconcerting for the uninitiated. The first is to use exponents (or logarithms) of what we want to find (in this case height), which makes the math work out a little more cleanly; the second is to use indicator functions (which I'm just going to ignore here). CLRS defines the exponential height as $Y_n=2^{h_n}$, so the analogous recurrence is $Y_n=2\times\max (Y_{i-1},Y_{n-i})$.

Assuming independence (that each draw of an element (out of the available elements) to be the root of a subtree is irrespective of all previous draws), we still have the relation: $$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$
for which I did two steps: (1) moving the $\frac{1}{n}$ outside because it is a constant and one of the properties of summations is that $\sum_i ci=c\sum_i i$, and (2) moving the 2 outside because it is also a constant and one of the properties of expected values is $\operatorname{E}[ax]=a\operatorname{E}[x]$. Now we're going to replace the $\max$ function with something larger because otherwise simplifying is difficult. If we argue for nonnegative $X$, $Y$: $\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$, then:
$$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$
such that the last step follows from the observation that for $i=1$, $Y_{i-1}=Y_{0}$ and $Y_{n-i}=Y_{n-1}$ and going all the way to $i=n$, $Y_{i-1}=Y_{n-1}$ and $Y_{n-i}=Y_{0}$, so every term $Y_0$ to $Y_{n-1}$ appears twice, so we can replace the entire summation with an analogous one. The good news is that we have a recurrence $\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$; the bad news, is that we're not much further than where we started.

At this point, CLRS pulls an induction proof $\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$ out of their ... repertoire of mathematical experience, one that includes an identity $\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$ they leave to the user to prove. What's important about their choice is that its largest term is $n^3$, and recall that we are using exponential height $Y_n=2^{h_n}$ such that $h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$. Perhaps someone will comment why this particular binomial was chosen. The general idea though is to bound from above our recurrence with an expression $n^k$ for some constant $k$.

To conclude with a one liner:
 $$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n) $$


Trying to understand the proof of the halting problem presented in Sipser textbook I'm having some problems to understand the classic proof of the halting problem.

The Proof:

$A_{tm} = ${$<M,w>$ | $M$ is a $TM$ and $M$ accepts $w$}.

We assume that $A_{tm}$ is decidable and obtain a contradiction.

  I have no problem to imagine that. It's a machine that accepts some string $w$. But it must not accept others strings $not-w$. And if it's decidable, it always halts.

Suppose that $H$ is a decider for $A_{tm}$. On input $<M, w>$, where $M$ is a $TM$ and $w$ is a string, $H$ halts and accept if $M$ accepts $w$. Furthermore, $H$ halts and rejects if $M$ fails to accept $w$. In other words, we assume that $H$ is a $TM$, where

\begin{equation}
  H(<M, w>)=\begin{cases}
    accept  &\text{if $ M$ accepts $w$}.\\
    reject & \text{if $ M$ does not accept $w$}.
  \end{cases}
\end{equation}

  Here I have the impretion that $H$ is doing the same thing that $A_{tm}$ does.
  But If it's saying that $H$ is decider, I can assume that $H$ has some magic power to discover if $A_{tm}$ will halt in input $w$

Now we construct a new Turing machine $D$ with $H$ as a subroutine. This new TM calls H to determine what $M$ does when the input to M is it own description $<M>$. Once $D$ has determined the information, it does the opposite. That is, it rejects if $M$ accpets and accepts if $M$ does not accept. The follow is a descripion of $D$:

  No problem here.

\begin{equation}
  D=\begin{cases}
    1.  &\text{Run $H$ on input <M, <M>>}.\\
    2. & \text{Output the oposite of what $H$ outputs; that is, if $H$ accpets, reject and if $H$ rejects, accept}.
  \end{cases}
\end{equation}

  Here is where I find hard to understand. The input string of $H$ is $<M, w>$, how could it run some thing like $<M, <M>>$ ?

  If was only $<M>$, I could imagine that $w$ is the empty string.

I understand the halting problem with  the following code:

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

The first misconception is that $A_{TM}$ is a Turing Macahine. $A_{TM}$ isn't a machine, it's a language, $H$ is the machine that decides the language $A_{TM}$. So you give $H$ a string that consists of two parts, a string $M$ that describes a Turing machine, and another string $w$, which can be anything.

This leads us to the second part, $w$ can be any string - it's the theoretical input to $M$ that you want to know whether $M$ would accept or not. So $H$ should accept if $M$ would accept $w$, and reject otherwise (i.e. when $M$ doesn't accept, which could be by rejecting or never halting). $\langle M \rangle$ is just a string, it happens to coincidentally be a description of a Turing Machine, but it is still just a string. So there's no reason we can't ask "does $M$ accept the string which is its own description?"


Trouble understanding the master theorem, from Jeffrey Erickson's Notes I'm looking at Jeffrey Erickson's Notes on the master theorem
(page 10).

Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k>1$ then T(n) is $\Theta(n^{\log_b(a)})$. But I get a different result.

Using recursion trees we have $$T(n) = \sum_{i=0}^{\log_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum_{k=0}^{\log_b(n)} k^i f(n)\,.$$

If $k<1$ then this is $\sim f(n)$ as desired. If $k=1$ then this is $\sim \log_b(n)f(n)$ as desired. But if $k>1$ then this is an ascending geometric series, so the last term dominates. Then we have $$\sim k^{\log_b(n)}f(n) = n^{\log_b(k)}f(n)\,,$$ which is wrong; the right answer is $\Theta(n^{\log_b(a)})$. Where does my reasoning go off the rails, and what is the correct solution?

Any help is appreciated.

EDIT: I think my answer is actually right, and is equivalent to Erickson's simpler answer. Note that $k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$  Hence $k^{\log_b(n)}f(n) = a^{\log_b(n)}f(1) \sim n^{\log_b(a)}$.

You can further simplify $n^{\log_b(k)}f(n)$.

We have $\frac{a}{k}f(\frac{n}{b}) = f(n)$. If $c = \log_b(n)$, we can apply this identity $c$ times to get $\left(\frac{a}{k}\right)^c f(1)$.

So $n^{\log_b(k)}f(n) = n^{\log_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log_b(n)}\left(\frac{a}{k}\right)^{\log_b(n)} f(1) = a^{\log_b(n)}f(1) = \Theta(n^{\log_b(a)})$


Undetectable error correcting codes I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code.

The result must also be indistinguishable from random. It should not be possible to detect the presence of error correction from the result.

Is it possible? And if so, how?

PS: Related: https://crypto.stackexchange.com/questions/80890/error-correcting-codes-that-are-indistinguishable-from-random

One natural approach is to apply the error-correcting code, then encrypt the codeword with a stream cipher (e.g., AES-CTR mode).  The recipient can decrypt (this will not increase the number of bits with an error), then decode the code to correct any errors.  Anyone who does not know the symmetric key will be unable to distinguish the transmitted ciphertext from a random string.


Kosaraju’s Algorithm - why transpose? In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing time and then traverse original graph.
In other words, we would find finish times of all vertices and start traversing from lowest finish time to greatest (by increasing finish time)?

Additionally, if we do topological sorting on some DAG, and then reverse edges (transpose adjacency matrix) and do topological sorting again - should we get to equal arrays, just in reversed order?

EDIT:
Algorithm description from other topic:
Correctness of Strongly Connected Components algorithm for a directed graph

Taking the transpose and using the list based on finishing time both together ensure that if you have edge A->B(in original graph) where A and B are simply connected sub-graphs than in second dfs A would have finished before start of B(See that in transposed graph edge is from B->A). If we do not take transpose then this is not ensured.

Example:

1->2

2->3

3->4

4->2

3->5

dfs(decreasing finishing time finishing times):1,2,3,5,4
Now if you start from 4 you will visit 5 through 4->2->3->5. But 4 and 5 are not simply connected.

For the second part you may or may not get reversed arrays depending on the order of supplying vertices.


Zero-knowledge proof of intractibility of NP-complete problems I am not an expert in Zero-knowledge proofs and I am interested in its applicability to general mathematical proofs.

Suppose we're willing to assume that NP-complete problems are intractable and require exponential time algorithms.

Can we construct a zero-knowledge proof of the intractability of Hamiltonian cycle problem, under this assumption? Is it possible without assuming the existence of one-way functions?

"A zero-knowledge proof of the intractability of the Hamiltonian cycle problem" doesn't make sense.  You should refer to the formal definition of a zero-knowledge proof system.  When we talk about a zero-knowledge proof system, it is a zero-knowledge proof system for a family of statements.  For the problem to be interesting, the family needs to be infinite.

"The intractability of the Hamiltonian cycle problem" is not a family of statements; it is a single statement.  It doesn't make sense to talk about a zero-knowledge proof in that sense -- you end up with something trivial and degenerate and uninteresting.

In particular, that single statement ("the Hamiltonian cycle problem is intractable") is either true, or it is false.  If it's true, there is a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "yes, the statement is true".  If it's false, there is also a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "no, the statement is false".  Either way, there exists a zero-knowledge proof system that satisfies the definition.  But this is not very interesting or meaningful.

From a formal mathematical perspective, in the phrase "zero-knowledge proof", you shouldn't think about "zero-knowledge" as a modifier to the word "proof".  Rather, you should think about the phrase "zero-knowledge proof system" as an indivisible term with a specific mathematical definition.  A "zero-knowledge proof system" is not even in the same category as a "proof"; they are like apples and oranges.


Linear Temporal Logic, Idempotent law in many lecture notes, I have seen the LTL idempotent law for until and its equivalence is described as $\phi U(\phi U \psi) \equiv \phi U\psi$ and also $(\phi U \psi)U\psi \equiv \phi U \psi$
. Also by definition of $G$, some formula holds in every state. So if globally $\phi$ holds until we see $\psi$ does it make every state after it true? question might sound weird but by formula  is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi)  $

Also by definition of $G$, some formula holds in every state.

Well, $\sf true$ holds in every state. I'm unsure about why you mention $G$ here.

  So if globally $\phi$ holds until we see $\psi$ does it make every state after it true?

A state can not be true or false, like 42 can not be true or false. This is meaningless.

  is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi)  $

Take $\phi = \sf false$ and $\psi = \sf true$. Then, $G(\phi U \psi)U\phi$ is equivalent to $\sf false$, and $G(\phi U \psi)$ is equivalent to $\sf true$.


How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5? I'm trying to write a formal proof in automata theory to show a few properties of DFAs but I am having some trouble with this that I am trying to incorporate into my proof. I want to show how many languages $S$ there are such that $S\subseteq\{0,1\}^*$ and $\forall s\in S, |s|\leq 5$ where $s$ is a string.

I got that there are $2^1+2^2+...+2^5 = 62$ different strings such that $|s|\leq 5$ but that is where I am stuck. How many different languages can I create with $62$ strings? Would it simply be $62!$ ?

First, you seem to have missed the empty string, so there are actually 63 possible strings. In any language, each of the 63 strings could either be in or not in the language, so there will be a total of $2^{63}$ different languages. In the jargon, that's a BFN.


Recognizing Horn clauses I am currently studying model theory and I am trying to decide if a clause is a Horn Clause. I know that a Horn Clause is a clause with at most one positive literal, but there are some clauses that it is not easy to decide whether they are Horn or not.

E.g.,

(P->Q)->W

Is there any way to decide whether this clause is Horn or not, or do I have to make further calculations in order to bring it to a Disjunction form?

Let's start with some definitions:

A literal is either a variable (a positive literal) or the negation of a variable (a negative literal).
A clause is a formula which is equivalent to a disjunction of literals.
A Horn clause is a formula which is equivalent to a disjunction of literals, at most one of which is positive.

Your formula $(P \to Q) \to W$ is not equivalent to a disjunction of literals. Indeed, if it were, since it depends on all variables $P,Q,W$, it would have exactly one falsifying assignment (with respect to $P,Q,W$). Yet it has three: $(P,Q,W)=(F,F,F),(F,T,F),(T,T,F)$. So it is not a clause, and in particular not a Horn clause.


Find all critical edges for minimum spanning tree This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne.

  4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to $E \log E$. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).

There is an algorithm (see below), as well as an accepted answer, at stackoverflow.
However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m \log m)$ is achieved in this algorithm (given the hint in the answer).

The algorithm is (in my understanding):

Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.

My questions are:

How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
How to achieve $O(m \log m)$ with appropriate data structures?
If this algorithm is wrong, how to solve the problem?

Since Kruskal's algorithm sorts the edges according to their lengths, the trick here i to partition the edges into subsets of edges with equal lengths.

For each subset (in increasing order) check which components are being joined using each edge of this set before joining them. If two (separate) components are being joined using more than one edge of this subset then both (all) these edges are non critical (since we can choose any of them and still get a spanning tree).

Now we are visiting each subset (and accordingly each edge) two times, the complexity is still in $O(|E|)$ and we need an additional $\log$ for the DSU join operations.

However, you should be aware of the case where for example three edges $\epsilon_1,\ \epsilon_2,\ \epsilon_3$ of the same lengths joins components $V_1-V_2, V_2-V_3, V_3-V_1$ respectively, which makes non of them critical point since we can use any two of them and leave the third one. A solution of this problem is to add all this edges at first to the Graph, then you will have a non tree graph, with cycles in places where you had many choices, and that makes the critical edges exactly the Bridges (check the link) in this graph.

P.S since bridges can be found in $O(|V| + |E|)$ total runtime is still $O(|E|*\log|E|)$


Compute sum of edges in paths from source to target node? Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u <v (see the graph below). The weight $w(u,v)$ on each edge is a positive number. For a given node $i$, I am interested in computing the  following term $s[i]$ defined as follows:
s[i] is sum of weights on any edges (w.o duplicates) of some paths from the source node 1 to the node i.
For example, in the below graph s[6] =  3+ 2+ 10 + 20 + 200 + 100 = 335.
I am struggling how to come up with a linear time w.r.t $|V|$ and $|E|$ to compute $s[i]$ for a given node $i$.
I am thinking of using dynamic programing. For example, suppose we already can compute $s[j]$ up to $j<k$, to compute $s[k]$ we might attempt $s[k] = \sum_{i} s[i] + w[i,k]$ if there is an edge $(i,k)$. For example, to compute $s[6]$ we need $s[4]$ and $s[5]$,
So $s[6] = (s[4] + 200) + ( s[5]+ 100) = (3+200) + ( (3+2+20+2+10) +100) $ but this approach fails since we did not take into account that  the edge $(1,4)$ is shared in computing $s[4]$ and $s[5]$. The edge $(1,4)$ should be summed one time in $s[6]$.

A simple approach that should work w/out need for a hash table is as follows:
Let two boolean arrays $a,b$ such that

$a[u] =1 $ iff a path $1 \ldots u$ exists

$b[u] =1$ if a path $u  \ldots i$ exists

Both can be calculated in $O(V+E)$ time : $a$ with a simple BFS from $1$, and $b$ by a bottom-up approach of examining the vertices in the reverse topological order.
Now, you consider each edge of the graph $ u \rightarrow v$ and add $w(u,v)$  to the answer iff $a[u]=1$ and $b[v]=1$.
Because the graph is a DAG the two paths above must be disjoint thus their concatenation is a valid path from $1$ to $i$ and since we consider each edge once, there are no duplicates.


Reducing context-free languages with polynomial-time reductions So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$.

Can $L \le_p M$ ? Why or why not? How do polynomial time reductions even work with CFLs in general?

Since context-free languages are in P and $M$ is non-trivial, there is an easy polynomial time reduction from every context-free language $L$ to $M$. The reduction decides whether the input is in $L$ or not, and according to that outputs either $\epsilon$ or $0$, say.


Are fully connected layers required for convnets? I have a reinforcement learning model I'm trying to create for a grid based game. One of the features of the game is that the game board can get bigger mid game, although I know this is a problem that machine learning isn't very good at. However, one idea that I had was to train a convolutional neural net model that doesn't have a fully connected layer at the end, so that the input and output size of the net can vary together, and the model will still work because it won't need any additional weights to produce an output. In addition, adding a fully connected layer or two at the end would be a very large amount of extra weights to train, since the action space of the problem is very large (15232 discrete actions if I remove the expanding grid portion of the game). If my calculations are correct, a single fully connected layer would become 464 million more weights. Which seems like a lot compared to my existing 223,350 trainable parameters.

Here is one iteration of this network type I've tested:

For this model, the observation space is 92 layers deep, and 28 wide by 16 tall. And the action space is 34 layers deep, and 28 wide by 16 tall. I'm not getting amazing results from this network (although better than random choice), which could be due to a multitude of reasons. However, I don't know if this is bad idea as I'm having trouble reasoning about this design generally.

Is a fully connected layer at the end necessary for the network to learn global ideas about the observation space?

There are no rules.  You can do whatever you like.  The ultimate test is how well it works; you'll have to try it and see.

But the short answer is: no, fully connected layers are not required.  You can build a network that is purely convolutional, with no fully connected layers.  It's hard to know how well it will work, without trying it.


Can I encode a graph in a unary alphabet For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly.

Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with such alphabet?

In my reasoning, I think you can, since if you can map any binary string, to a unary string, then you can transitively mapping one adjacency matrix to a unary string, hence a graph. Does this reasoning have any flaw? Is this a valid argument?

As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say
$$ \epsilon, 0, 1, 00, 01, 10, 11, \ldots. $$
Let $w_i$ be the $i$th string in this order. You can convert from binary to unary by mapping $w_i$ to $1^i$ and vice versa.

You mention that you are worried that this encoding is not efficient. From the perspective of complexity theory, this is not so clear, since if your representation is very large, then it is fair to allow you a lot of time to encode and decode it. In formal terms, for a representation of length $n$, you should be able to encode and decode in time polynomial in $n$.

Consider the example of graphs. In order to encode a graph in unary, you first encode it in binary, say using $m$ bits. Then you output $1^n$ for some $n \approx 2^m$. You can easily compute the output in time polynomial in $n$. Going the other way around, you can convert $1^n$ to the corresponding binary string $w_n$ in time polynomial in $n$ as well, and decoding the binary representation only takes time polynomial in $m = O(\log n)$.


Clarification reg. jump consistent hashing I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2)

"Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+1) / i."

My understanding is that:

P(j ≥ i) is the probability that a key "jumps"/moves to a different bucket after bucket#i
r is a pseudo random number between [0, 1) with a uniform distribution
b is the last bucket# for which a jump occurred for this key

In particular, I am having trouble understanding this phrase: "we set P(j ≥ i) iff".

Set it to what? Do they mean to say "We want a key to jump to a different bucket ≥ i with a random probability r. This means that P(j ≥ i) ≥ r, which implies that (b+1)/i ≥ r. Hence the smallest such bucket number is obtained by the equation i = floor((b+1)/r)"?

I suggest this as a better version of the paragraph.

Now, for a given $i$ and $k$, we generate a pseudorandom variable, $r$, that is uniformly distributed between 0 and 1, and set $j = \lfloor(b+1) / r\rfloor$. This gives $P(j \ge i) = (b+1) / i$, as we want:
$P(j \ge i)$
$ = P(\lfloor(b+1) / r\rfloor ≥ i)\quad$ substituting the definition of j
$ = P((b+1) / r \ge i)\quad$ because $i$ is an integer
$ = P(r \le (b+1) / i)\quad$ solving the inequality for $r$
$ = (b+1) / i\quad$ because $r$ is uniformly distributed between 0 and 1


What is the Meaning of the Notation What is meant by saying an algorithm runs in time $Poly(|S|,n,\frac{1}{\epsilon})$.

Can somebody explain with an example.

It means that there exists a polynomial $f(x,y,z)$ such that the algorithm runs in time $f(|S|,n,\frac{1}{\epsilon})$.

Specifically, it means that there are constants $c_1,c_2,c_3\ge 0$ such that the algorithm runs in time $O(|S|^{c_1}\cdot n^{c_2}\cdot (\frac{1}{\epsilon})^{c_3})$.


Compression for set of integers preserving their sequence For a given positive number n. Numbers from 0 up to n, are streamed one by one in some order without repetition.

What would be recommended a strategy to store the order of these n numbers in the most space conservative way?

Highest priority is to consume minimal bits to store the order.
Second highest priority is to have minimal effort in adding the incoming number to the current order
Least priority is the computational complexity in retrieving the order.

Retrieval will be done only when all n numbers have been added.

Deletion operation will not be performed.

Given that all the numbers form 0 to N-1 are to be stored, and their order, there will be N! permutations.  The minimum number of bits needed to store any combination and its order from an randomly selected order will be

$$\lceil \frac{\log(n!)}{\log(2)}\rceil$$

For example give a range of {0..99} (N=100) the Number of bits to store the permutations is $\lceil \frac{\log(100!)}{\log(2)}\rceil = 525\text{bits}$.

This can be encoded using a Mixed-Radix Calculation, or can be done using Arithmetic Coding (with a slight extra few bits).

In short using a LIST of the numbers to choose from. Each time one of the numbers is eliminated, to take the last number in the list, move it to fill in the eliminated number, adjust the "stats" for Arithmetic coding. Since All the symbols are equally, the same percent applies to all the symbols, and makes easy and Linear time to encode.

Each elimination increase percent chance of the next symbol (IE Number) occurring in the remaining of the list using list of the 0..(N-1) and using the move the last item to the empty position, and shorten the list.

A hash table can be used to make finding the number to replace be done in $\mathcal O(1)$ expected time, for the $\mathcal O(N)$ sequence.