Can Dijkstra's algorithm be modified to return paths with ascending edge-id's? Say that each edge in a directed graph is labelled with an ID. I want to run Dijkstra on the graph to find the shortest path between $source$ and $destination$, with the additional restriction that the shortest path must be in order of ascending ID's. For example, if the path is from $ A \to B \to C $, then $ID(Edge_{AB}) < ID(Edge_{BC})$.

Is this feasible in polynomial time with some modification of Dijkstra?

It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not dense, however, it will require extra amount of memory.

Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an $O(N \log N)$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with $O(M)$ complexity where $M$ is the number of edges.

The method:

Apply usual Dijkstra on the problem and find the shortest path.
Create an array of $M$ numbers initially assigned by -1.
As traversing the shortest path, change the value of each traversed edge ID
    position in the array to 1.
Scan the array for 1's to find the path in ascending order.

Note that, this is an $O(M)$ algorithm instead of $O(N)$. However, if the above assumptions are satisfied, it will work better than $O(N)$. So, it depends on how much your graph is dense.


Is there any difference between extensible records and dependent maps In a typed setting, records can be thought of as a map from field to type. If there is a well-typed record merge operation (which allows overlapping fields), is there any real difference between the resulting type and a dependent map in a dependently typed language?

Simple records correspond to maps of dependent type (and we don't have a merge operation yet). More precisely, the record type

{ lbl1 : A1, lbl2 : A2, ..., lblN : AN }

corresponds to the product type

∏ (ℓ : label), A ℓ

where label is the sum type

lbl1 + lbl2 + ... + lblN

and A : label → Type is the type family defined by

A lbl1 ≡ A1
A lbl2 ≡ A2
       ⋮
A lblN ≡ AN

The record type above is also equivalent to the simple product

A1 × A2 × ⋯ × AN.

You asked about extensible records. There are at least two ways to do this. Without any additional technology we can model an extension of

{ foo : A, bar : B } ≤ { foo : A, bar : B, baz C }

with a couple of function that map between them (projection in one direction and extension by an extra field in the other). This is all very mundane.

We could also ask for the type of all possible record types. Suppose we have a type label of all possible labels (in practice it could be string or some such). The type of all record types is

record ≡ label → option Type

An element R : record is a mapping from labels to optional types, where
R lbl takes value None if label lbl does not appear in R and value Some A if it appears and have type A.

If R : record then the type decribed by R is the product type

∏ (ℓ : label),
  match R ℓ with
  | Some A ⇒ A
  | None ⇒ unit
  end

This means that a record r of type R is a dependent function which takes a label ℓ to an element of A if ℓ appears in R and to the unit otherwise.

However, a merge operation is problematic, as well as a subtyping relation R ≤ Q. This is so because we cannot express the fact that a label lbl has the same type in record R and record Q. At best you can say that the types are isomorphic, or propositionally equal, but that's not what you want.

We can define an extend operation

extend : record → record → record

in which the first argument overrides the second one so that extend R Q has the fields of R additionally those fields of Q that do not appear in R:

extend R Q ≡
   λ (ℓ : label),
     match Q ℓ with
     | Some A ⇒ Some A
     | None ⇒ Q ℓ
     end


CRF message passing as convolution operation I was reading the paper _Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials (Philipp Krähenbül and Vladen Koltun, in Proceedings of 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011 pdf), and I didn't understand this equation (eq 5) in the paper:

I understand the first equation, but not the second one. If $k(f_i,f_j) = e^{-1*(f_i-f_j)^{2}}$, then $k(f_i,f_j)$ would return a scalar value between 0 and 1 ; 0 if $f_i$ and $f_j$ are far apart in the feature space, 1 otherwise. So, $k(f_i,f_j)Q_j$ adds a fraction of $Q_j$ to $Q_i$ . The first equation is clear. I don't understand how this leads to the 2nd equation. In the 2nd equation, the Gaussian kernel is now over $Q$  instead of being over $f_i,f_j$  and then multiplied by $f_i$. Where is the $f_j$? Can someone explain how the 2nd equation is derived from the first one?
$G \otimes Q$ would again return a value between 0 and 1, which is multiplied by $f_i$ (which is an n-dimensional feature vector). So the result of $(G \otimes Q)(f_i)$ would be an n-dimensional vector, and we subtract $Q_i$ (a scalar) from that. Am I misunderstanding something here?

I read the article. The meaning of the equation:
$$[G\otimes Q](f_i)$$ stand for $G$ convolution with $Q$ in the feature point $f_i$ and not multiplied by $f_i$.

The $f_j$ is hidden inside the convolution operation.

The actual operation is done using cross bilateral filter.
You can see more information on the Project site of the article.
You can also find a source code in this site.


How can I correct this Hamming code? I'm trying to decode the following Hamming sequence (using EVEN parity and knowing there is a 1-bit error), which contains an ASCII value: 01100110101

I've tried to check for the correctness of each parity bit:

    p1 p2 d3 p4 d5 d6 d7 p8 d9 d10 d11
     0  1  1  0  0  1  1  0  1   0   1
p1 - 0     1     0     1     1       1
p2 -    1  1        1  1         0   1
p4 -          0  0  1  1
p8 -                      0  1   0   1

p1, p4 and p8 checks are all even and correct.

p2 check is odd, hence the parity bit is incorrect and needs to be flipped. The actual message then becomes 00100110101 and the ASCII value can be read as 1011101.

Supposedly this value is incorrect - can anyone point out the mistake I made?

The original problem is, I believe, the following.

When using Hamming code with EVEN parity for 7-bit ASCII characters, the following symbol is retrieved: 01100110101.
Assuming a 1-bit error, what was the original stored symbol? Write down your answer as a 7-bit binary, with no spaces.

OP's statement, "..., which contains an ASCII value: 01100110101", rephrases the original problem statement in a slightly confusing way,  as pointed out by Yuval Filmus.
OP's procedure and result is correct, as said in Jakube's comment and indicated in D.W.'s comment. I have verified it as well according to Hamming code at wikipedia.
OP's procedure and result will not be repeated here.
Someone mentioned that "The usual Hamming code has length of the form $2^\ell−1$". For $\ell=4$, the usual Hamming code of length 15 is defined by the following table from wikipedia.  If we truncate the last 4 columns, we will get the truncated Hamming code of length 11, which should be, presumably, the Hamming code used in OP's question.

"Supposedly this value is incorrect - can anyone point out the mistake I made?"
This is the turning point to the climax (or anti-climax). There are four possibilities.

A different kind of (truncated) Hamming code is used.
For example, all four parity bits could have been specified to be put together in the first four bits. That is, the first four bits, 0110 are the usual p1, p2, p4 and p8 parity bits while the remaining 0110101 are the data bits. In that case, we rearrange the bits to form the usual Hamming code as (p1)(p2)0(p4)110(p8)101, which is 01011100101. Then p1, p2, p4 check are odd while p8 is OK. So we flip the $1+2+4 =7$-th bit to obtain 01011110101. So the corrected data bit will be 0111101. Well, OP can check if this or something similar is the case.

"This is from a quiz on my university's LMS, the site is saying my answer is incorrect."
As D.W. suggested, maybe they are wrong. Maybe whatever you read was in error. There might be a typo in the statement of the quiz. There might be an error in the original answer by the quiz owner. There might be an error in the answer-checking process by the site. There might be a critical typo in OP's post. And so on.

Jakube, D.W., I, and, apparently, many others have not been able to find the mistake. That is very unlikely, though.

The last possibility stands for, as always, all other probably even lesser possibilities.


Constructing an unrestricted grammar for a^n b^m c^n d^m I've been trying to construct an unrestricted grammar which has the language:

L = {a^n b^m c^n d^m | n>0, m>0}

But I can't seem to figure it out without making the derivations run an unreasonably long amount of time.  Can anyone help me devise an elegant way to create this grammar?

Edit: In order to clarify, I was trying to find an Unrestricted Grammar that would run in O(n^2) time or better.  As it stood, all of my solutions were exponential, which made parsing very long strings prohibitively costly.

How about the following:
$$
\begin{align*}
&S \to XY \\
&X \to aXC | aC \\
&Y \to BYd | Bd \\
&CB \to BC \\
&aB \to ab \\
&bB \to bb \\
&Cd \to cd \\
&Cc \to cc \\
\end{align*}
$$
In this grammar you need to apply $O(nm)$ rules to get $a^nb^mc^nd^m$.


Segment trees with insertion/deletion I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in the order that they appear in the input. The operations can be one of the following: update a position of the array with a new value, insert a new element at some index of the array, remove an element at some index of the array and query information about a range of the array.

I tried an implementation of Segment Tree where the nodes are stored in an array. Left child of node at index p is at index 2p, right child is at index 2p + 1. This implementation is not enough, because the tree is static. All I can do are range queries and update positions of the original array. Inserting or deleting elements in the original array requires the tree to be rebuilt, so the running time is O(n) (too slow for the test cases). My program is correct, but too slow.

I Googled about Segment Trees with insertion/deletion and I read that is possible to do that with self-balancing binary search trees, like AVL or Red-Black trees. But I'm having trouble to understand how insertion or deletion would work in this dynamic Segment Tree that I need.

Does anybody knows something about that?

I think  this Problem  is same as you asked and i solved this problem using  Treap .


Good book on the history of programming languages? I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, object oriented programming etc were developed? I was introduced to programming when OOP was well developed and hence I don't really know what it was like for OOP to be developed for the first time. Similarly for structured programming, procedural etc.

Is there a good book that starts with the first programmers who worked directly in computer code, and goes through the different developments, showing how the developments were non-trivial at the time (even though from our current perspective they might seem natural and obvious)?

There is an infrequently held conference series called History Of Programming Languages (HOPL). It was held in 1979, 1993, and 2007, the fourth installment is scheduled for middle of June, 2020.

The Proceedings for HOPL-I and HOPL-II were also published as books, for HOPL-III, both the papers and video recordings of the presentations are available. (Including the highly entertaining, though not necessarily highly scientific 50 in 50 by Guy Steele and Dick Gabriel, presenting 50 language-related ideas from 50 years in 50 words each within (a little bit more than) 50 minutes.)

There is also a website called Online Historical Encyclopaedia of Programming Languages, which collects about 9000 languages and presents them in the form of a hypergraph with several kinds of relationships (evolution-of, influence, dialect, …, also people involved, regions where it was developed, institutions, etc.) between them.


Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity? Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is not $\mathcal{O}(1)$, it is $\mathcal{O}(\log s)$, where $s$ is weight of the path from initial vertex to current.

And this means that complexity is $\mathcal{O}(|V|^2\log s)$.

Am I missing something?

Algorithms are usually analyzed under the word RAM model, in which basic operations on machine words cost $O(1)$. Machine words are defined as words of length $\log n$, where $n$ is the size of the input (in bits).

In the case of algorithms on weighted graphs, we could make the further assumption that weights are put in special registers for which "reasonable" arithmetic operations are $O(1)$. This assumption is made implicitly, without any mention of it, since the exact computation model isn't really needed when designing an algorithm, as long as you're not "cheating". It allows using floating point weights, for example.

The computation model serves two purposes:

To explain what constitutes "cheating", that is, what is not allowed (or rather, what is allow).
To allow proving lower bounds.

If we are not careful with the computation model, we could solve PSPACE-complete problems such as TQBF; see here.

One instantiation of the murky class of computation models for weighted graphs is allowing the weights to fit in a constant number of machine words; then we can just analyze the algorithm using the word RAM model. In this case, any weight encountered during Dijkstra's algorithm also fits in a constant number of machine words, since any such weight is the sum of at most $|V|-1$ weights. Therefore in the word RAM model, assignment (as well as addition) costs $O(1)$ rather than $O(\log s)$.


Cryptography substitution frequency analysis I am trying to find the plain text for the following cipher text using a frequency analysis

vr pvst yqlp mq nvf

But for the letters above this is really difficult, as if I use the alphabetic substitution technique, where I assume that v corresponds to e as this occurs most in the english alphabet. What about p, this also occurs three times, does this mean it corresponds to e. Same for r,s,t,y,l,m,n,j,f which occur only once. Is there an algorithm which looks at such duplicated frequencies, or do I guess:

v and p corresponds to e
q corresponds to t
r to f correspond to a

?

even using the bigram method for something like this is difficult as a bigram of pv is found,
if p = t
and v = h
that means p doesn't correspond to t anymore?

Thanks in advance!

I'm by no means an expert but it seems to me that your sample is far too short to be amenable to frequency analysis or, indeed, to cryptanalysis of any kind. Assuming a substitution cypher, you have only the information that eleven letters are used, and characters 1, 4 and 14; 3 and 10; and 8 and 11 are the same. There are fifteen unused characters so there's a huge amount of freedom. You only have a little more information than a one-time pad would give you.

In a long sample of text, it is likely but is not guaranteed that the most frequent character is 'e'; in a fifteen character sample, it's perfectly possible that there are no e's at all. ("Look at my odd words" is a sixteen-letter example.) Frequency analysis helps you figure out the substitutions but it doesn't guarantee to give you the answer with no more work.

Assuming the spaces are significant, your message could be "My emus love no imp". Or it could be something completely different.


How to show a set is $\Pi_2$ complete How can I prove that a set is complete for $\Pi_2$ complete? Can you give me an example proof? Say for $All_{TM}$ = Turing machines whose accepted language is all strings?

To show that the language is $\Pi^0_2$ complete you have to show two things:

The language is $\Pi^0_2$
Every $\Pi^0_2$ language is many-one reducible to your language

To show that your language is $\Pi^0_2$, informally, you need to know two things: (1) quantifiers over strings count the same as quantifiers over numbers, and (2) the predicate $P(M,\sigma)$ = "machine $M$ accepts string $\sigma$" is $\Sigma^0_1$. Your language is a universal quantifier in front of that $\Sigma^0_1$ relation, so it is $\Pi^0_2$.

To show that an arbitrary $\Pi^0_2$ language is many-one reducible to yours, it's easiest to show that some other language that you know is $\Pi^0_2$ complete is many-one reducible to your language. The details of that will depend on what languages you already know to be $\Pi^0_2$ complete. If you don't know any, then it helps to know that every $\Pi^0_2$ language is definable by a formula of the form $(\forall \sigma)(\exists \tau) R(\sigma,\tau)$ where $R$ is computable.


Why use maximum likelihood for word prediction? According to https://www.tensorflow.org/tutorials/word2vec/, the standard approach for predicting the next word in a word sequence is maximum likelihood. The predicted next word is the word that maximizes

$$P(w_t|h)=\frac{\exp(\text{score}(w_t,h))}{\sum_{w'}\exp(\text{score}(w',h))}.$$

To me, it seems that the word predicted from this model is always the word with the maximum score, in which case we could just use the score function for prediction.

What does maximum likelihood provide that a simple score function does not?

That approach is using a score function (in a particular way).  It is also using maximum likelihood.  Both ways of describing the approach are valid.

Why is it useful to think about this in terms of maximum likelihood?  Because it gives a more systematic way to think about this problem and others like it.

If we just want to think about maximizing a score function, the question that raises is -- what score function should we use?  How do we choose one?  It sounds arbitrary.

In contrast, the maximum-likelihood approach gives us a principled way to choose the function.  Here is how to derive that formula, given the maximum-likelihood principle.  First, they have apparently decided to use the following approximation for the probability of seeing $w_t$ as the next word, given history $h$:

$$P(w_t,h) = \exp(\text{score}(w_t,h)).$$

Once you've decided to do that, then by the definition of conditional probability it follows that

$$\begin{align*}
P(w_t|h)
 &= \frac{P(w_t,h)}{P(h)}\\
 &= \frac{P(w_t,h)}{\sum_{w'} P(w',h)}\\
 &= \frac{\exp(\text{score}(w_t,h))}{\sum_{w'}\exp(\text{score}(w',h))}.
\end{align*}$$


How to find indexes of numbers that has many occurrences? Disclaimer: This is a simplified part of a question from my homework, addressing the point that I didn't figure out.

  let A be a 1-indexed sorted array of $n$ elements.

  There are at most 3 numbers that has at least $\lfloor n/4 \rfloor+1$
  occurrences.

  Find three indexes that will surely "hit" all such numbers. Explain why it's certain.

Because this is a sorted array, all such numbers will be stacked together, so each "number group" have a limited freedom to travel around the array.

It feels like going symmetrically for $n/4$, $n/2$ and $3n/4$ would be a wise guess, but I'm not sure how to prove it, and furthermore $n$ might not be a multiplicity of 4, so we have to round up or down the indexes.

How can I tackle such question?

Let's assume for simplicity that $n$ is divisible by $4$. Aiming for a contradiction, suppose that there is some popular number (a number is popular if it appears at least $n/4+1$ times) which does not appear at any of the positions $n/4,n/2,3n/4$. Denote this popular number by $x$.

  Can $x$ appear before position $n/4$? between positions $n/4$ and $n/2$? between positions $n/2$ and $3n/4$? after position $3n/4$?

If the answer to all of these questions is no, then we have reached a contradiction, and the only way out is that $x$ appears in one of the positions $n/4,n/2,3n/4$.


Gale–Shapley algorithm is man-optimal I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/stablemarriageproblem/intro and here
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf
relies crucially on the fact that the disagreement happens for the 1st time when a man M approaches a woman W and we are trying to prove that in no matching matching M can be paired up with W.

If possible could you also give alternative proofs.

We use the following notation:

$M$ is the set of men, $W$ the set of women.
For a man $m$ and a set $W'$ of women, $\max_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ if $W'$ is empty. We similarly define $\max_w M'$ for a woman $w$ and a set $M'$ of men.

One way to view the Gale–Shapley algorithm is as maintaining a graph $G$ of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:

Create a complete bipartite graph $G$ with the men on one side and the women on the other side. The initial set of edges is thus $\{(m,w) : m \in M, w \in W\}$.
For each man $m \in M$, let $\operatorname{top}(m) = \max \{w : (m,w) \in G\}$ be the woman $m$ most prefers among his possible matches at this point; $m$ proposes to $\operatorname{top}(m)$.
For each woman $w \in W$, let $\operatorname{best}(w) = \max \{m : \operatorname{top}(m) = w\}$ be the man $w$ most prefers among those who propose to her; $w$ chooses $\operatorname{best}(w)$ (if different from $\bot$).
Remove $(m,\operatorname{top}(m))$ from $G$ whenever $\operatorname{best}(\operatorname{top}(m)) \neq m$, that is, remove $m$'s top choice as a possibility if she rejects him.
If any edge was removed from $G$ in Step 4, go back to Step 2.
Return the matching in which each man $m \in M$ is married to $\operatorname{top}(m)$, and each woman $w \in W$ is married to $\operatorname{best}(w)$.

The idea of the algorithm is that at each point, in every stable marriage, every match $(m,w)$ is an edge in $G$. The reason is as follows. Suppose that in Step 4, $\operatorname{best}(\operatorname{top}(m)) \neq m$ for some man $m \in M$, and consider any marriage in which $m$ is married to $w = \mathrm{top}(m)$. Let $m' = \mathrm{best}(w)$, so that $w = \mathrm{top}(m')$. Obviously $w$ by definition prefers $m'$ to $m$. Since $w$ was $m'$'s top possible choice, $m'$ must be married to someone he prefers $w$ over. Therefore $(m',w)$ is an unstable pair. This shows that no stable marriage can contain $(m,w)$, and so we can safely remove it from $G$ in Step 4.

Throughout the algorithm, no man $m \in M$ is ever left alone, i.e. there is always some $w \in W$ such that $(m,w) \in G$; this is important, since otherwise the algorithm isn't well-defined. This property holds due to the following list of observations:

Once $\operatorname{best}(w) = m \neq \bot$ at some stage for some woman $w \in W$, $\operatorname{best}(w) \neq \bot$ from that point on, and never becomes less desirable than $m$ from the point of view of $w$. This is because at the next iteration, $\operatorname{top}(m) = w$, so $\operatorname{best}(w)$ is at least as good as $m$.
If $\operatorname{best}(w_1),\operatorname{best}(w_2) \neq \bot$ at some iteration for $w_1 \neq w_2 \in W$, then $\operatorname{best}(w_1) \neq \operatorname{best}(w_2)$ at that iteration. This is since $\operatorname{top}(\operatorname{best}(w_1)) = w_1 \neq w_2$.
Every time an edge $(m,w)$ is removed, $\operatorname{best}(w) \neq \bot$. This is because $w = \operatorname{top}(m)$.

Suppose now that all edges adjacent to some man $m \in M$ are removed, and consider the iteration in which the last edge adjacent to $m$ is removed. At this point, all edges $(m,w)$ were removed, so by (3) and (1), $\operatorname{best}(w) \neq \bot$ for all women $w \in W$. By (2), the mapping $\operatorname{best}\colon W\to M$ is one-to-one and so in bijection. In particular, $m = \operatorname{best}(w)$ for some woman $w \in W$. But this means that $w = \operatorname{top}(m)$ and so $(m,w)$ would not be removed in Step 4. We conclude that no man $m \in M$ is ever left isolated.

Since we only remove edges, eventually Step 6 will be reached. At this point, $\operatorname{best}(\operatorname{top}(m)) = m$ for all men $m \in M$, and so $\operatorname{top}$ and $\operatorname{best}$ are inverses. This shows that the output is well-defined and a matching.

Moreover, the matching is stable. Indeed, suppose that $(m,w)$ was an unstable pair, $m$ preferring $w$ over $\operatorname{top}(m)$, and $w$ preferring $m$ over $\operatorname{best}(w)$. Since $m$ prefers $w$ over $\operatorname{top}(m)$, necessarily $(m,w) \notin G$. When this edge was removed, $w$ preferred $\operatorname{best}(w)$ over $m$, and by (1), at the end $w$ still prefers $\operatorname{best}(w)$ over $m$, leading to a contradiction.

Finally, the matching is man-optimal. This is because in any stable marriage, a man $m \in M$ is matched to one of its neighbors in the final graph $G$. The marriage output by the algorithm matches $m$ to his top choice $\operatorname{top}(m)$, so it is optimal from the point of view of $m$.

Moreover, the matching is woman-pessimal. For suppose there were some stable matching in which some woman $w \in W$ is matched to a man which she prefers less than her match $m = \operatorname{best}(w)$ returned by the algorithm. Since $G$ represents the only possible matches in stable marriages, $m$ must be matched to some woman he prefers less than $w = \operatorname{top}(m)$. Thus $(m,w)$ is an unstable pair, and we reach a contradiction.

This exposition is taken from Section 6.3 of this paper, where other algorithms are described and analyzed, culminating in Subramanian's fixed point algorithm.


Determine if there is a path with alternating edge colours in directed graph Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from $v$ to some red vertex with alternating edge colours (no edges of same colour are adjacent in the path, e.g. blue -> green -> blue -> ...).

If $G$ is acyclic, the problem looks simple - just use DFS. But how can one solve it if there are cycles in $G$?

Let's construct a new graph $G'$.

Every vertex $u$ from $G$ will become a pair of vertexes in $G'$, namely $u_{blue}$ and $u_{green}$ (index stands for the color of incoming edge).

Edge $u_{c_1}\rightarrow w_{c_2}$ in $G'$ exists iff

There is an edge $u \rightarrow w$ in $G$ colored $c_2$
$c_1 \ne c_2$

Now it's easy to see that every path in $G'$ corresponds to a color-alternating path in $G$ (and the converse is also true), i.e. color-alternating path from $v$ to $u$ in $G$ exists iff there is path from $v_{c_1}$ to $u_{c_2}$ in $G'$ for some $c_1, c_2$.


How to generate a degree sequence of a degree distribution How to generate a degree sequence of a degree distribution that follows the power-law in which I know $N=10^2$ and $\gamma=2.5$?

The degree distribution of power-law is $p_k \sim k^{-\gamma}$.

I want to generate a power-law network using the configuration model, but to do that I need to know the degree sequence $seq={k_1, k_2, ..., k_N}$.

Thanks

As you mention, the degree distribution follows a power law if the number of nodes of degree $k$ is roughly $N \times C^{-1} k^{-\gamma}$, where $C = \sum_{k = 1}^\infty k^{-\gamma} = \zeta(\gamma)$ (in your case, $C \approx 1.34$). Plugging in your numbers, we want roughly

75 vertices of degree 1.
13 vertices of degree 2.
5 vertices of degree 3.
2 vertices of degree 4.
1 vertices of degree 5.
1 vertices of degree 6.
1 vertex of degree 7.

This gives a total of 98 vertices. You can make it exactly 100 vertices in many ways — I'll let you think of one. Don't forget that the sum of degrees should be even.

The (potential) problem is that not every sequence is the degree sequence of a graph. Sequences which are realized by some graphs are known as graphic sequences, and are determined by the Erdős–Gallai criterion. If the resulting sequence doesn't satisfy this criterion, we're in trouble. However, I don't expect it to happen in your case. Indeed, my suggestion above (with 98 vertices) is graphical.


Prove Context Free languages not closed under difference? Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using pumping lemma?

Yes I believe it is possible to prove such a non-closure property without pumping a specific example language.

As noted in the comments, complement $\Sigma^* - L$ is a special form of difference. It turns out that complementation is an extremely powerful tool used with context-free languages. One can show that computation histories of Turing machines can be specied as complements of context-free languages. This seems to originated from J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings
of Symposia in Applied Mathematics, Vol. 19, AMS, 1967, 42-51.

A computation history (for a fixed TM $M$) is a string of the form $x\$C_0\$C_1\$\dots\$C_n$ where $x$ is an input string, $C_0$ is the initial configuration of $M$ on $x$, meaning a string of the form $q_0x$ where $q_0$ is the initial state, $C_n$ is a final configuration (with a final state) and each pair of consecutive $C_{i-1}\$C_i$ represents a single step of TM $M$.

The language of those strings is the complement of a context-free language.

What is CFL would be closed under complement? Then the context-free languages would be equal to the languages accepted by Turing Machines: the languages of valid computations would be context-free, and from this we can find their prefixes or the accepted inputs of the TM. I  do think that is a contradiction without the pumping lemma. We know there are more TM accepted languages than CF languages by complexity or decidability arguments.


Understanding the one-writer, many-readers problem? I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept:

I have a rough idea that there will be starvation/deadlock among the readers as there is one writer that multiple readers are trying to access at once. Can anyone please provide some further insight regarding the problems with the implementation of this situation?

I am not looking for any coding, that was just the sample code (pseudocode) I am working with. I am looking for the problem of the implementation. Upon further research I have assumed the following (based on the line: if readcount == 1 then semWait(wrt); :

There is one writer and many readers
The readers have priority over the writers
The possible problem: The writers cannot write until the reader has finished reading therefore starvation occurs

However upon re-evaluation of the code I have also assumed the following based on the lines:

semWait(mutex);
readcount := readcount - 1;
if readcount == 0 then up
semSignal(mutex);

Could I not also say that only one reader may read at a time therefore the other readers will be starved?

Therefore would either of these be the correct way of interpreting the coding to the problem is of the implementation or would I be wrong?

First,I would suggest (in the future as well) to write the pseudocode yourself (the commands for the readers/writers), It will be cleaner and easier to read than the image. Also, i would suggest briefly explaining the semantics of your operations (wait/signal/up, since you used all three in the code).

To your answer, readers not being able to read simultaneously does not mean starvation, although simultaneous reading ability is an additional requirement, at least in the classical formulation of the problem (moreover, readers can read simultaneously in this protocol). Starvation means that there exists a process stuck waiting while other processes share the resource (if one reader $r_1$ has to wait until $r_2$ is done, then he might read after $r_2$, who eventually will be done reading, so $r_1$ is not stuck).

This protocol (as  it seems to me) is the same as the one described here (under First readers-writers problem). It is easy to see (as mentioned in the link) that writers can be starved here. Suppose $r_1,r_2$ are reading at the same time, so the count is $2$. Imagine a scenario where whenever $r_1,r_2$ read together, the first to finish (and decrements the counter to $1$) immediately requests reading again (so the counter is back to $2$). This way the counter will never reach $0$ and the writer will be starved (stuck waiting).


"Dense" regular expressions generate $\Sigma^*$? Here's a conjecture for regular expressions:

  For regular expression $R$, let the length $|R|$ be the number of symbols in it,
  ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| = 2$

  Conjecture: If $|R| > 1$ and $L(R)$ contains every string of length $|R|$ or less, then $L(R) = \Sigma^*$.

That is, if $L(R)$ is 'dense' up to $R$'s length, then $R$ actually generates everything.

Some things that may be relevant:

Only a small part of $R$ is needed to generate all strings. For example in binary, $R = (0 \cup 1)^* \cup S$ will work for any $S$.
There needs to be a Kleene star in $R$ at some point. If there isn't, it will miss some string of size less than $|R|$.

It would be nice to see a proof or counterexample. Is there some case where it's obviously wrong that I missed? Has anyone seen this (or something similar) before?

Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is.

In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, not counting $\epsilon$ or $\emptyset$. However, $\emptyset$ can be eliminated from every expression not generating the empty language, and the expression can be "cleaned up" so that the number of $\epsilon$ it contains is at most $|\mathrm{alph}(R)|$ (Lemma on page 10 of the talk).

In page 51, for every $n \geq 3$ they construct a regular expression of size $O(n)$ over $\{0,1\}$ which generates all strings of size at most $\Omega(2^n n)$, but doesn't generate all strings. Note that "size" here is both in your sense and theirs, since we're using big-O notation. They also pose an open question to find the best dependence between the two parameters.


Context-free grammar to a pushdown automaton I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have on a homework that's due later today, so I'd appreciate some kind of help, even if it's just an explanation of the correct answers diagram. I need a PDA corresponding to this CFG:

$$S \rightarrow aSa | bSb | B$$
$$B \rightarrow bB | \epsilon$$

I know it will have to push X every time 'a' is read before a 'b', and pop X every time 'a' is read after a 'b'. But I'm not sure how to arrange the PDA in order to tell which a's came after b's. Also, I'm unsure of how to deal with the b's in terms of the stack, as there can be as many in the middle of the string as you want. Help appreciated.

Thanks, Pachun

This is basically the language of all palindromes over $\{a, b\}$ which can contain an arbitrary number of $b$'s in the middle. First, you could build a PDA for palindromes. This is a fairly standard language, so you should be able to find plenty to get you started. Then, you need to add a way to read an arbitrary number of $b$'s after you're done pushing new symbols to the stack, and before you start popping symbols. So the basic steps here:

Read $a$'s and $b$'s and push to the stack;
Read any number of $b$'s;
Read $a$'s and $b$'s and pop from the stack.

Please let me know if you need more guidance. Note that you're going to need to use nondeterminism here, so don't worry about it. This is a not a deterministic language (unless I'm mistaken... which has happened before).


Recoloring bipartite graphs Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation:

Choose a vertex $v_a$ in $A$
Flip the colors of $N[v_a]$, meaning that $v_a$ and every neighbor of $v_a$ will change color.

  Is there a polynomial time algorithm to select a recoloring set $X \subseteq A$ that will minimize the number of blue vertices? The number of recolorings needed is not relevant.

Observe that the order of flipping does not matter, and for every vertex in $A$, you either flip it or you don't.  We can think of the colors as a number which is incremented modulo 2.  This yields a trivial $O(2^{|A|} \cdot n)$ algorithm.

The problem is NP-complete and is thus not likely to admit a polynomial time algorithm.   Below is a proof of the NP-completeness of the problem, shown by a reduction from 1-in-3-SAT.

Let $\phi$ be an instance of 1-IN-3-SAT, where we are given a 3-CNF-SAT formula
asked to find a satisfying assignment where each clause is satisfied by exactly
one literal.  Let $V(\phi)$ be the set of $n$ variables, and $C(\phi)$ be the
set of $m$ clauses.

We construct an instance $G = (A,B,E)$ with a budget of $b = n + m$ (the allowed
number of blue vertices).

For each variable $x \in V(\phi)$, construct two red vertices $v_x$ and
$v_{\overline{x}}$ in $A$ together with $b+1$ blue vertices in $B$ adjacent to
both of them.  This forces exactly one of $v_x$ or $v_{\overline{x}}$ to be
flipped.  We also end up with $n$ flipped "variable vertices", thus using the
first part of the budget.

Remark: $\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$ are the only vertices in
$A$.

For each clause, say $c = x \lor \overline{y} \lor z$, we create $b+1$ blue
vertices and three extra red vertices $v_{x \in c},v_{\overline{y} \in c},v_{z
\in c}$, all in $B$.  Let $v_x,v_{\overline{y}},v_z$ all be fully adjacent to
the $b+1$ blue vertices and connect $v_x$ to $v_{x \in c}$, $v_y$ to
$v_{\overline{y} \in c}$, and $v_z$ to $v_{z \in c}$.

Now, since each clause gadget has $b+1$ blue vertices, we know that either one
or three literals in that clause have been flipped.  Suppose that three have
been flipped for one of the clauses.  But then we use at least budget $n + m +
2$.

Suppose that $\phi$ is a yes instance with a 1-in-3 assignment $\alpha: V(\phi)
\to \{\top,\bot\}$.  Flip every vertex which corresponds to $\alpha$.  Since
every clause is satisfied by exactly one variable, for each clause there is now
one blue vertex, and for each variable, exactly one of them is blue, hence we
have $n + m = b$ blue vertices.


Bubble Sort: Runtime complexity analysis line by line I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in "Introduction to Algorithms 3rd Ed" (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below).  I haven't found a line by line analysis like the Intro to Algorithms line by line analysis of this algorithm online, but only multiplied summations of the outer and inner loops.
For each line of bubblesort(A), I have created the following times run. Appreciate any guidance if this analysis is correct or incorrect.  If incorrect, how it should be analyzed.  Also, I do not see the best case where $T(n) = n$ as it appears the inner loop always runs completely. Maybe this is for "optimized bubble" sort, which is not shown here?
Times for each line with constant run time $c_n$, where $n$ is the line number:
Line 1: $c_1 n$
Line 2: $c_2 \sum_{j=2}^n j $
Line 3: $c_3 \sum_{j=2}^n j - 1$
Line 4: $c_4 \sum_{j=2}^n j - 1$ Worst Case
$T(n) = c_1 n + c_2 (n(n+1)/2 - 1) + c_3 (n(n-1)/2) + c_4 (n(n-1)/2)$
$T(n) = c_1 n + c_2 (n^2/2) + c_2 (n/2) - c2 + c_3 (n^2/2) - c_3 (n/2) + c_4 (n^2/2) - c_4 (n/2)$
$T(n) = (c_2/2+c_3/2+c_4/2) n^2 + (c_1 + c_2/2+c_3/2+c_4/2) n  - c_2 $
$T(n) = an^2 + bn - c$

The runtime in the original post is correct.  The O(n) runtime is for a different algorithm, called optimized bubble sort.


How does asynchronous operations save time in I/O I'm reading a book CLR via C# which says how Windows does asynchronous I/O:

To read data from the file, ReadAsync internally allocates a Task object to represent the pending completion of the read operation. Then, ReadAsync calls Win32's ReadFile function (#1). ReadFile allocates its IRP (I/O Request Packet) and then passes it down to the Windows kernel (#3). Windows adds the IRP to the hard disk drive’s IRP queue (#4), but now, instead of blocking your thread, your thread is allowed to return to your code; your thread immediately returns from its call to ReadAsync (#5, #6,
and #7). Now, of course, the IRP has not necessarily been processed yet, so you cannot have code
after ReadAsync that attempts to access the bytes in the passed-in Byte[]. Using the task object, you can call ContinueWith to register a callback method that should execute when the task completes and then
process the data in this callback method. Or, alternatively, you can use C#'s asynchronous function
feature to simplify your code by allowing you to write it sequentially.

The author also describes a scenario of how asynchronous operations save time in I/O:

let's say that your application wants to download 10 images from various websites and that it takes 5 seconds to download each image. If you perform this work synchronously (downloading one image after another), then it takes you 50 seconds to get the 10 images. However, if you use just one thread to initiate 10 asynchronous download operations, then all 10 are being performed concurrently and all 10 images will come back in just 5 seconds! That is, when performing multiple synchronous I/O operations, the time it takes to get all the results is the sum of the times required for each individual result. However, when performing multiple asynchronous I/O operations, the time it takes to get all the results is the time required to get the single worst-performing operation.

I don't understand how async operations can reduce the time from 50 seconds to 5 seconds. Let's change the NTFS Disk Driever to network adapter driver and change the read file async code to download file async code.
My understanding is, it is true that asynchronous operations allow fewer worker threads to handle incoming client's I/O requests, contrasted by synchronous operations, every I/O request need a worker thread to handle, and when the synchronous operation takes time to complete, the worker thread gets blocked too and therefore it cannot return to the thread pool to serve other requests. But for the network adapter driver, can still only complete one I/O operation one at a time.
For example, let's say the network adapter driver is handling the first I/O request (represented as an IRP queue) to download the first picture. Even though you use asynchronous operations, the worker thread that serves the first I/O request did return to the thread pool to serve the second I/O request, but the network adapter driver is still processing the first I/O request to download the first picture, so the second I/O request as an IRP is still queuing in the network adapter driver. The network adapter driver only handles the second IRP after the first one is completed, so the network adapter driver still serves the second I/O request after 5 seconds, and so on, so it still needs 50 seconds to download 10 pages. In other words, it is not worker threads blocking, it is the network adapter driver that's blocking.
so how can how async operations can reduce the time from 50 seconds to 5 seconds? Unless the network adapter driver itself is a small powerful computer that has multiple CPUs that can serve requests concurrently, but this is obviously not true, drivers like network adapter drivers are cheap devices, it can't be having expensive components like CPUs?

Issuing the ten requests in parallel is unlikely to give you a tenfold speedup, but will usually give you some speedup. It depends on where the bottleneck is. If the images are 5 MB each and your Ethernet/WiFi connection can only transfer data at 1 MB/s, then your network card will essentially be tied up for 5 seconds per image, and issuing the requests in parallel probably won't help. If the images are 5 kB each and you have a gigabit fiber Internet connection, and the 5-second delay is due to the servers being very slow to respond, then your network card will be idle almost all of the time, and you may actually get all of the images back in 5 seconds total if you issue the requests in parallel.
The network card only sends and receives small isolated data packets, typically of about 1500 bytes. It doesn't understand the concept of a TCP or HTTP connection. When it's not sending or receiving packets related to one connection, it can send or receive packets related to another, even if the first connection is still open.
The book is wrong to assume that the 10 requests are perfectly parallelizable; usually that isn't the case. Also, the parallelism it's talking about has nothing to do with asynchronous I/O as such. You'd get the same speedup by starting 10 threads and issuing a blocking I/O call in each one. That might be a bit slower because of thread-creation overhead, but might also be faster because it uses more CPU cores if you have them. For the highest performance you have to create one thread per CPU core and use asynchronous I/O in all of them. NT has built-in support for that model through I/O completion ports.


How are words assigned in machine language? So, if you have an 8-bit computer and it can perform a fetch cycle, meaning it can access its memory, how do you create words the computer understands.

If LDA "load the accumulator" is in the instruction set and its just something we named for humans and the computer understands binary...

How was this idea communicated in binary.

I see it's another language, in logic, two-state system,

literal b/c logic gates are

But how do you say load and add and such

These are the human terms but what would the computer hear?

LDA gets translated by the assembler to bytes that the machine can interpret.

The contents of these bytes are set by the instruction decoder, and often made to make the decoder as simple as possible. For example some bits may get passed straight to the execution unit so add and subtract differ by a single bit which triggers inverting the second operand and sets the carry in bit. The bits that decide which registers to use would be common to all instructions, stuff like that

The 3 letter acronyms are just shorthands set by whoever was in charge of writing the assembler.


Modeling an inequality problem to a graph Given $n$ variables : $a_1,a_2...,a_n$ and $m$ inequalities of the form $a_i<a_j$, we want to know if there's a positioning that satisfies all the inequalities.

  a. We want to modelize the problem to a directed graph $G=(V,E)$. $V=?,E=?$

$V=\{a_i|i\in[n]\}$ $E=\{a_ia_j|a_i<a_j\}$

  b. Complete the sentence: There exists a valid positioning iff...

$G=(V,E)$ doesn't contain directed cicles and parallel edges (i.e. to prevent $a_1<a_2$ $a_2<a_3\space$ $a_3<a_1\space$ and $a_1<a_2\space$ $a_2<a_1$)

  c. How do we determine if there exists a valid positioning? What would be the complexity of such action?

I guess check for directed cycles (which i don't know how) and parallel edges?

  d. If there's a valid positioning, how do we find it?

By giving the vertex with maximum $d_{out}$ the lowest number and so on?

I'd appreciate help with c and d.

You’re on the right track with your response to $c$. There’s a bunch of algorithms that solve $c$ and $d$ simultaneously. If you’re familiar with depth-first search, you can use that to solve the problem.

Another approach is what’s called “topological sort.” The key idea here is that if a directed graph has no cycles, then you can put the vertices in a line such that there are only edges that go from start vertex to an end vertex such that the end vertex is to the right of the start vertex. This is actually really easy to write an algorithm to do, give it some thought and see if you can’t come up with a clever trick.

The best case time for solving this problem is $O(|V|+|E|)$, and off the top of my head I can think of four algorithms that achieve that timing.


Recognizing interval graphs--"equivalent intervals" I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:

  Each interval graph has a corresponding interval model in which two intervals overlap if
      and only if their corresponding vertices are adjacent. Such a representation is usually far
      from unique. To eliminate uninteresting variations of the endpoint orderings, we shall
      consider the following block structure of endpoints: Denote the right (resp. left) endpoint of
      an interval $u$ by $R(u)$ (resp. $L(u)$). In an interval model, define a maximal contiguous set of
      right (resp. left) endpoints as an R-block (resp. L-block). Thus, the endpoints can be grouped
      as a left-right block sequence. Since an endpoint block is a set, the endpoint orderings within
      a block are ignored. It is easy to see that the overlapping relationship does not change if one
      permute the endpoint order within each block. Define two interval models for $G$ to be
      equivalent if either their left-right block sequences are identical or one is the reversal of the
      other.

I am unable to understand the notion of equivalent intervals. Can someone help me?

Imagine scanning the real line from left to right. Whenever an interval starts or ends, you make notice of it. For example, perhaps at some representation, at the point $3$ the intervals for $x_2,x_7$ start and the interval for $x_{15}$ ends, and at the point $4$ the interval for $x_2$ ends, and no points occur in between.

Suppose we "remove" the portion $(3.25,3.75)$ of the real line, thus pushing the point $4$ back to $3.5$. This only affects the value of some ordinates, so we would like to say that these two interval representations are "the same". Indeed, they are equivalent under the definition you give, since if we make a list of which intervals start and end at what point, then the lists would be identical, the only difference being the value of the ordinates.

Another operation we can do is reflecting the real line, say around zero. Now the interval for $x_2$ is $(-4,-3)$ instead of $(3,4)$, so that at the point $-4$ the interval $x_2$ starts, and at the point $-3$ the intervals for $x_2,x_7$ end and the interval for $x_{15}$ starts. Again, we would like both of these representation to count as "the same". This transformation is captured by the reversal clause in the definition you quote.


How to retrieve reset bit in constant time in a bit array In a game application there is a session id assigned to each player every time they start a new session.
Session id's are always unique and there can be billion users of this game. Whenever a user logs-in, get() function is called which basically assigns a bit to the user by setting a bit from a bitarray and when user logs out, set() function is called which resets that bit.

So,it may happen that at some point the bit array looks like below:
101010101000011111

For uint_32 bitarray[100000], 100000 integers needs to be searched for finding out reset bit in worst case if linear search is used. Is it possible to make this search constant time?

For a 32/64 integer and not using bit array this would be pretty much constant using bit operation (x&-x) but for a bit array getting constant time it would be not that easy.

Is there any data structure which I can use for this purpose? I think we can use skip list for this but need some information as to the right approach to insert and delete element from this skip list?

Access into a bit array is constant time.  In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, regardless of how large $i$ is.  That's all that you need to do to access a bit array.  In particular, if you have an array of bytes, then you can read the $i$th bit of the bit-array by reading $A[i/8]$ and doing a bit-masking operation to get the $(i \bmod 8)$th bit of that byte, and so on.

If you want to find a new session id that is not in use, that can be done in (expected) constant time as long as at least 1/2 of the session ids are not in use.  You simply pick a random session id, check whether it is in use, and repeat until you find one that is not in use.  If at least 1/2 of the session ids are not in use, the expected number of times you need to repeat this until you find one that is not in use is 2 (as it's expected the number of coin tosses until you get a heads, which is a geometric series), i.e., a constant.  Each iteration takes constant time, so the whole thing can be done in $O(1)$ time.

So, a bit array already meets all of your requirements. Just make sure that at least 1/2 of the session ids are not in use.

(What do you do if more than 1/2 of the session ids are in use?  Double the size of the array, copying over the old array if needed.  The doubling will happen rarely enough that the amortized time for each operation remains constant, i.e., $O(1)$.)


Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$? Here is pseudocode for the algorithm:

select(L,k)
{
if (L has 10 or fewer elements)
{
    sort L
    return the element in the kth position
}

partition L into subsets S[i] of five elements each
    (there will be n/5 subsets total).

for (i = 1 to n/5) do
    x[i] = select(S[i],3)

M = select({x[i]}, n/10)

partition L into L1<M, L2=M, L3>M
if (k <= length(L1))
    return select(L1,k)
else if (k > length(L1)+length(L2))
    return select(L3,k-length(L1)-length(L2))
else return M
}

Here is some analysis of the algorithm: http://www.ics.uci.edu/~eppstein/161/960130.html

The analysis suggests to use the recurrence relation $T(n) \leq \frac{12n}{5} + T(\frac{n}5) + T(\frac{7n}{10})$.  Solving this we get linear work for a call.  But aren't there log many recursive calls?  So that would be $n\log n$.

Put another way, conceptually this algorithm seems like it could be described as "for each call, cut the search area kind of like binary search, but not guaranteed to cut the search area by as much as binary search, and add a linear time partition".  Binary search runs in $O(\log(n))$, so adding a linear search per call would make it $O(n\log(n))$.

What am I not understanding about the linked analysis?

Consider the following series

$S = n + \lceil n/2 \rceil + \lceil n/4 \rceil + ... + 1$

There are $\lceil \log_2 n \rceil + 1$ terms but the sum is less than $2^{\lceil \log_2 n \rceil+1} < 4n$ always.

Similarly, in your algorithm even though you have $\log n$ recursions, each recursion successively does a fraction of work. Hence the total work done in linear in $n$, rather than $\Theta(n \log n)$ as the naive analysis suggests, just similar to the sum of the series above. '

Also note that $T(n)$ is $O(n)$ as well as $O(n\log n)$. This is because $O(n\log n)$ is also an upper bound to $T(n)$ and therefore it is incorrect to say, for example, "Why  is $T(n)$ not $O(n\log n)$?".


How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable? Say I have a set of 3-CNF clauses
$$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$

where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$.

How many satisfying assginments are there for $S$? In general, how many satisfying assignments are there for $S$ is the size of $S$ is k?

This is a question about what is a satisfying assignment for 3-disjunctive clause as much as it is about counting. For example when I just have $C = x_1 \vee x_2 \vee \bar{x_3}$, there are $2^3 = 8$ possible assignments:
$$1 1 1\\
0 1 1 \\
1 0 1\\
1 1 0\\
1 0 0\\
0 1 0\\
0 0 1\\
0 0 0
$$
But which one of these are satisfying assignments?

As you noted, for every clause there are $2^3$ possible assignments. Exactly one of them does not satisfy the clause: it's the one that has false for all variables that appear in the clause as a positive, and true for the variables that appear as a negative. In your example it is $001$. The rest of the assignments satisfy the clause. Therefore there are $2^3 - 1 = 7$ satisfying assignments for each clause, which means there are $7^k$ possible assignments in total.


Algorithm to evenly distribute a hierarchical dataset I am working on a chatbot designer interface. The dataset for the conversation flow consists of messages. Each message has a parent message and can have multiple possible next messages. The system displays one of the possible next messages depending on the reply. This makes it a complicated structure of parent-children relations.
On the dialog flow designer interface, the user is able to drag messages around in order to achieve a visual clarity of the designer dialog flow. This is loads of work for the user.
I want to implement an algo that would do this job for the user. So the messages should distribute themselves at even distances and making sure that their children are also around their parent message evenly distributed.
I have not studied algos, so I am not sure what jargon to look for. I don't even know the proper tag to use in this question. What this kind of algorithm is called and how to achieve this?

You want to use an algorithm for graph layout.  There are many out there, as well as some tools.


How to choose the number of HOG pyramid layers? Reading Histograms of Oriented Gradients for Human Detection, I cannot see any discussion of how many layers there should be in the HOG pyramid. OpenCV offers a scaling factor of 1.05 which would mean 15 layers between each halving and Object Detection with Discriminatively Trained
Part Based Model suggests 10 layers, but that is for their specific algorithm, I believe.

However, with 1280 x 960 source images these values become prohibitively expensive regarding performance. How does decreasing the number of layers affect detection rates? What exactly am I trading off?

That's a good question!

All of this will depend in your application and camera setup. Usually, it works like this: if you have a say 128x128 detector template you will be able to detect the object at this size and greater dimensions. When you go up at the pyramid the image size is smaller, but the detected object (w.r.t the original image) is bigger).

One of the main ways to reduce computational time is to reduce the number of pyramid levels. With all things kept unchanged, this will make you not detect very large objects. By the way, a common trick in object detection is to resize the image such that the object in the scene appear at the right scale w.r.t the pyramid.

If, you change the pyramid step, some object could be missed if their scale does not match any of the pyramid levels. In summary, as I said, it will depend on the setup (e.g. if you have a camera send people from a distance, usually you will need fewer leves of the pyramid).

I recently wrote a paper on using the camera calibration to estimate the best scales for people detection in a surveillance scenario. It could help you:

Fuhr, G.; Jung, C.R., "Camera Self-calibration Based on Non-Linear Optimization and Applications in Surveillance Systems," in Circuits and Systems for Video Technology, IEEE Transactions on , vol.PP, no.99, pp.1-1


Turing machine - infinite tape - does that thing exist? Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist?
Do we have the right to regard a machine (a construct) in the same way we regard a number or a set (an abstract)?

If yes could I similarly use a Turing angel with infinite scroll instead, would that be ok?

EDIT: since I cannot comment.
This question is somewhat different from infinity in mathematics because a set even infinite can have a finite representation. On the other hand there is no finite representation for an infinite tape  That is the algorithm that generates the output.

Computation requires resources, that means that it takes place in a time-space, not in an abstract timeless dimension.
While it could be ok to draw on demand more time for the computation pushing on to infinity, space has a cap on the amount of information it can hold, and before reaching that point the tape would revert to write only, that is implode into a black hole. So even if an algorithm is "finite" its output could be big enough to become "unreadable".
For example lets say we have a machine that counts all numbers at some Number H when trying to add more information on the tape the tape colapses forms a black hole and number H+1 becomes unreadable.
Counting up to H+2 is a finite process but cannot be completed.
One could argue that space and time restrictions should not concern us but I m not convinced that is true when dealing with objects embedded in spacetime

I could accept a definition of a machine with sufficiently large tape. But I think that the size does matter.
Can for example 2 Turing machines with different tape-size considered equivalent?

The tape is not infinite. It is unbounded.
There is an important difference.
We don't need infinite memory.
We only need to be able to add more memory over time as needed.
This is actually pretty close to what people do in practice.
When a program needs more memory it asks the operating system and
receives more memory.
If we see that a computer is short on memory we increase its memory.
It is becoming even easier with cloud computing.
So the assumption is not that the machine has infinite memory.
The assumption is that we can increase the memory as needed.

If your question is about the limit where
the needed memory reaches the limit of information
that can be stored in the universe
(assuming that it is finite and bounded by some fixed number)
then yes, we will not be able to add any more memory at that point.
In fact, if you assume that
the amount of information is bounded by a fixed number
then the world is a finite state machine.
However that is not the usual case.

However if you try to design programs as finite state machines
you are going to have a very difficult time
because the number of states is huge.
The number of states for a Turing machine with $m$ bits of memory
would be something like $2^m$.
Turing machines (and other similar models)
simplify things.
This is a rather common thing in sciences.
It is important to know the limits of a model but
the fact that a model is not a completely accurate representation of the world
doesn't imply it is useless.


How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular? I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression
 a(b*)c(d*)e

can be proved to be regular using pumping lemma. The string generated by this expression are of the form.

abcde
abbcdde...

We can not write these string in the form of $xy^iz$. We can only write it in the form $vx_1^iyx_2^jz$.
So, how can I prove using pumping lemma that the language generated by the expression is regular?

You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of

languages described by regular expressions;
languages accepted by deterministic finite automata (DFAs);
languages accepted by nondeterministic finite automata (NFAs).

If, additionally, you've proven that some or all of these definitions are equivalent, you can use any of the appropriate ones.

In this case, your language is defined by a regular expression. If that's your definition of regular languages, you're already done.

Our reference question has more information.


Mathematics Courses for Computer Scientists I am looking for standard math courses (Calculus 1, Calculus 2, Linear Algebra, etc.) that were developed specifically for computer scientists, and use computer-science examples for motivation. For example, the pagerank algorithm can be used to motivate eigenvectors and eigenvalues.

The Matrix in Computer Science (Brown)
http://cs.brown.edu/courses/cs053/current/lectures.htm

Coding the Matrix (Coursera)
https://www.coursera.org/course/matrix

Both are by Philip Klein
http://cs.brown.edu/~pnk/


What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$? I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed

if (n = a^b for some natural numbers a and b), output 'composite'

I have attempted to deduce the complexity of this line and have deduced the following. Assuming $n \geq 2$, $b$ must be bounded above by $\lceil \log_2 (n) \rceil$. Thus, if there exists $a,b \in \mathbb{N}$ such that $a^b = n$ then $n^\frac{1}{b}$ must be an integer. Thus, to test whether such values of $a$ and $b$ exist, we must check whether
$$
n^\frac{1}{x}
$$
is an integer for each $2 \leq x \leq \lceil \log_2 (n) \rceil$. This requires a maximum of $\lfloor \log_2 (n) \rfloor$ operations to be performed, so the complexity of this step (according to my likely incorrect analysis) would be $O(\log_2 (n))$.

However, on page 6 of the paper it says that the complexity of this step is $O^\sim (\log^3(n))$. Why is this?

Note that this question regards the specific complexity of this operation, rather than simply verifying that it is doable in polynomial time (which was done here).

The complexity very much depends on whether you are looking at the worst case, or at the average case when you choose n at random.

To find whether $n^{1/b}$ is an integer, you could pre-calculate the set of possible integers $(a^b) \mod k$ for various k, and check whether $n \mod k$ is among those values - if not then $n^{1/b}$ is not an integer. If n is chosen at random, then this will eliminate many cases very quickly.

You can numerically calculate $n^{1/b}$ and check if it is an integer. If you calculate this value with (log n / b + 20) bits precision, and n was chosen at random, then your chance is 99.9999% that you can prove it is not an integer - this will fail if the result is an integer or close to one. There is a clever method doing the calculation using quadratically convergent Newton iteration involving only multiplications and additions / subtractions. Since only the last step requires the full precision, and the calculation involves raising numbers to powers b which is done in log b multiplications, this can be done in $O ({(\log n)^2 \over b^2} * \log b)$ steps using naive multiplication, and $O ((\log n / b) * \log (\log n / b) * \log b)$ using FFT. For random n, most of the time this is all that is needed.

It is possible that we find $n^{1/b}$ rounded to the nearest integer and cannot prove that $n^{1/b}$ is not an integer. In these cases we may have to calculate $a^b$. Again, only the final product needs full precision, so this is done in $O(log^2 n)$ using naive multiplication, or $O (log n log log n) using FFT.


Checking if a kernel is valid The kernel is $K(x,z) = \sum_{i=1}^D (x_i+z_i)$

My approach was trying to express  $K = \phi(x)^T\phi(z) = (x_1 x_2 ... x_D \quad 1 1 ...1)(1 1 ...1\quad z_1 z_2 ... z_D )^T$ where $\phi$ is 2Dx1 and thus a Kernel.

The solution says:

K is not a kernel. Consider $x_1 = [1 \quad 0]^T \quad x_2 = [0 \quad 2]^T$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?

Your confusion is that you're using $\phi$ to denote two different mappings. The first one maps its input $v$ to the vector $\begin{pmatrix} v & \mathbf{1} \end{pmatrix}$, and the second one maps it to $\begin{pmatrix} \mathbf{1} & v \end{pmatrix}$. In the same way we can prove that $-1$ is the square of a real number: $-1 = x \cdot x = (-1) \cdot (+1)$.


Determine shortest path in a 4x5 grid graph Suppose we had a graph $G = (V,E)$.

This graph can also be seen as a $4x5$ grid graph as shown in the image.

There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and $1 \leq j \leq m-1$.

Similarly, there is a directed edge from $v_{i,j} \rightarrow v_{i+1,j}$ for $1 \leq i \leq n-1$ and $1 \leq j \leq m$.

What is the most efficient algorithm to determine the shortest path from $v_{1,1} \rightarrow v_{n,m}$? My main idea is to use the Bellman-Ford algorithm, but I am clearly not taking advantage of how this graph is laid out. Any guidance would be much appreciated.

EDIT: The edges are weighted and may possibly be negative.

Since your graph is a DAG you can topologically sort $V$ and solve your problem via dynamic programming by considering the vertices in reverse topological order.

For each vertex $v$, let $d(v)$ be the distance from $v$ to $v_{n,m}$.
Clearly, if $v = v_{n,m}$, then $d(v)=0$.

For $v \neq  v_{n,m}$, you have:
$$
d(v) = \min_{(v,u) \in E} \{ w(v,u) + d(u) \},
$$

where $w(v,u) \in \mathbb{R}$ is the weight of edge $(v,u)$ in $G$.

Both the topological order of $V$ and all the quantities $d(v)$ can be found in $O(|E|)$ time. Therefore the overall time required is $O(|E|) = O(|V|) = O(nm)$.


Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for undirected graphs with negative-weight edges but no negative cycles.

I have two problems in understanding this algorithm:

In step 3, why must $G'$ have perfect matchings so that we can apply Edmonds' Minimum Weight Perfect Matching Algorithm to $G'$?
In step 4, why must each circuit in $S$ have total weight $0$?
(A possible argument is like this: Because there are no negative cycles, we only need to show that each circuit in $S$ cannot have positive total weight. Maybe this can be proved by contradiction. Suppose that some circuit in $S$ have positive total weight, we need to show that $M$ is not a mimimum weight perfect matching or this cannot be a circuit. However, I failed to reach a contradiction.)

Related post: Finding shortest paths in undirected graphs with possibly negative edge weights.

An answer to the second problem:

Problem: Each circuit in $S$ must have total weight zero. Why?

Proof: By contradiction.
Suppose that some circuit $C$ in $S$ have nonzero total weight.
Because $G$ has no negative cycles, $C$ has positive total weight.
Note that $C$ does not contain $s$ or $t$. Therefore, the edges of $C$ are all $5$-edge gadgets; see step 2.
Then we can construct another perfert matching on $C$ whose total weight is zero by choosing the middle edge with weight $0$ of each $5$-edge gadgets and the edges between $v$ and $v'$ (for each $v$ in $C$; see step 1) also with weight $0$.
This contradicts the assumption that $M$ is a minimum perfect matching.


Explanation of roofline model I am currently studying the roofline model. Wikipedia [2] shows the following example graph:

The diagonal line shows $\beta * I$. But I do not understand why this line does not go through the zero point. If $I = 0$ so should $\beta * I = 0$. What am I misunderstanding here?
[2] https://en.wikipedia.org/wiki/Roofline_model

The axes are in logarithmic scale, and so don't really have a zero point. What you are seeing is
$$ \log P = \min(\log I + \log \beta, \log \pi). $$
The striking part is that the slope of the line is always the same.


are NP Complete languages closed under any regular operations? I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. Is it also true that NPC languages are not closed under the complement, concatenation, and kleene star operations?

For all of the examples in this answer, I'm taking the alphabet to be $\{0,1\}$. Note that the languages $\emptyset$ and $\{0,1\}^*$ are definitely not NP-complete.

The class of NP-complete languages is not closed under intersection.  For any NP-complete language $L$, let $L_0 = \{0w\mid w\in L\}$ and $L_1 = \{1w\mid w\in L\}$.  $L_0$ and $L_1$ are both NP-complete but $L_0\cap L_1 = \emptyset$.
The class of NP-complete languages is not closed under union. Given the NP-complete languages $L_0$ and $L_1$ from the previous part, let $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ and $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$.  $L'_0$ and $L'_1$ are both NP-complete but $L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under concatenation. Consider the NP-complete languages $L'_0$ and $L'_1$ from the previous part.  Since both languages contain $\varepsilon$, we have $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under Kleene star.  For any NP-complete language $L$, $L\cup \{0,1\}$ is NP-complete but $\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.
If the  class of NP-complete problems is closed under complementation, then NP = coNP. Whether this is true or not is one of the major open problems in complexity theory.


Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms? So sometimes in combinatorics, you are computing the count $a_n$ of something that depends on a natural number parameter $n$. Either by hand or using a computer, you can often compute some initial terms in the sequence $(a_n)_n$. Now, you can enter those initial terms into the Online Encyclopedia of Integer Sequences, and if you are lucky you can get a match with a formula and info that will help you prove that your sequence satisfies that formula. But what if your exact sequence is undocumented but is directly related to a known sequence? Like if your sequence is double or the square of another known sequence? Or if your sequence can be expressed either directly or as a summation involving hypergeometric terms? If a computer could propose formulas for a sequence given some initial terms, it might help the mathematician immensely because when they finally look at the correct formula, it might become clear to them why the formula is true based on the structure of the problem and the formula. Has there been any progress in enabling computers to "guess" succinct formulas for integer sequences given some initial terms?

An exact solution to this problem is of course impossible (for example is $3,5,7$ the sequence of odd integers or of primes?) but there are ways to get answers when the sequence is not in oeis but its "related" to some sequence in the database.

One way to do so is to use superseeker. Basically you send the sequence that you got to superseeker@oeis.org and then the server tries some algorithms in order to find a relationship between your sequence and the ones in oeis.

Hence a good start is to check what kind of tests/algorithms are used by superseeker (iirc there is a description about that somewhere on the site)


Is there a name for this priority queue data structure? While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of some set, and each internal node is the $\max$ of its two children. I came up with a BuildHeap algorithm that's $O(n)$, a GetMax algorithm that's $O(1)$, an Insert algorithm that's $O(\log n)$, and a Delete algorithm that's $O(\log n)$. The number of nodes in this "heap" is $2n-1$ where $n$ is the number of elements in the underlying set. The structure is simpler than a binary heap.

Is there a name for this data structure?

[edit]

Code:

import Data.List
import Data.Ord

data Heap a = Leaf a | Branch a (Heap a) (Heap a) deriving Show

getMax :: Heap a -> a
getMax (Leaf x) = x
getMax (Branch x _ _) = x

leaf :: Ord a => a -> Heap a
leaf = Leaf

branch :: Ord a => Heap a -> Heap a -> Heap a
branch h1 h2 = Branch (max (getMax h1) (getMax h2)) h1 h2

buildHeap :: Ord a => [a] -> Heap a
buildHeap xs = fst $ buildSubHeap (length xs) xs
  where buildSubHeap 1 (x:xs) = (Leaf x, xs)
        buildSubHeap n xs = let (leftSubHeap, remainder1) = buildSubHeap (div n 2) xs
                                (rightSubHeap, remainder2) = buildSubHeap (n - div n 2) remainder1
                            in (branch leftSubHeap rightSubHeap, remainder2)

insertIntoHeap :: Ord a => a -> Heap a -> Heap a
insertIntoHeap x (Leaf y) = branch (leaf x) (leaf y)
insertIntoHeap x (Branch m h1 h2) = branch h2 (insertIntoHeap x h1)

deleteInsignificantElement :: Ord a => Heap a -> Heap a
deleteInsignificantElement (Branch _ (Leaf x) (Leaf y)) = Leaf (max x y)
deleteInsignificantElement (Branch _ h1 h2) = branch (deleteInsignificantElement h2) h1

getInsignificantElement :: Ord a => Heap a -> a
getInsignificantElement (Branch _ (Leaf x) (Leaf y)) = min x y
getInsignificantElement (Branch _ h1 h2) = getInsignificantElement h2

replaceMax :: Ord a => Heap a -> a -> Heap a
replaceMax (Leaf x) y = Leaf y
replaceMax (Branch m h1 h2) y | getMax h1 == m = branch (replaceMax h1 y) h2
                              | getMax h2 == m = branch h1 (replaceMax h2 y)
                              | otherwise = undefined

deleteMax :: Ord a => Heap a -> Heap a
deleteMax heap = replaceMax (deleteInsignificantElement heap) (getInsignificantElement heap)

data HeapObserver a = Singleton a | PushHeap a (Heap a) deriving Show

popHeap :: Ord a => Heap a -> HeapObserver a
popHeap (Leaf x) = Singleton x
popHeap heap = PushHeap (getMax heap) (deleteMax heap)

undown :: Down a -> a
undown (Down x) = x

heapsort :: Ord a => [a] -> [a]
heapsort [] = []
heapsort xs = map undown . flattenHeap . buildHeap . map Down $ xs
  where flattenHeap heap = case popHeap heap of
                           Singleton y -> [y]
                           PushHeap y ys -> y : flattenHeap ys

example_list = [234,234245,13235,14223,12,5,41,24,132,4134,25,234, 94875937, 34059, 784, 34875, 234, 765, 909]

main :: IO ()
main = print (heapsort example_list == reverse (sort example_list))

This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that:

You have fast set and get at any index
You have fast "aggregate" queries on ranges
You can support fast update queries on ranges, for some combinations of updates and queries

The $j$th node at height $k$ in the tree "summarizes" a subarray $[j*2^k, (j+1)*2^k)$ of the original array. Since each element of the array appears in only logarithmically many such subarrays, we can do updates in $O(\log n)$ time.

The range queries can use any associative operation. In your example the operation is $\max$, but other examples include sum, product, even standard deviation (via sum and sum of squares).

I originally called this a Fenwick Tree (aka Binary Indexed Tree), which is a similar structure but which compresses the tree into only exactly $n$ storage with no overhead(but loses access to the original array).


Rechecking contiguous characters (as in run length encoding) So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more contiguous characters. This is for run length encoding or something. For example:

  zz22344a is two z's, two 2's, one 3, two 4's, and one a.

Once you've parsed the original string, you retain only the characters and sizes in an array.

struct Run { char whatChar; int length; }

Run* runArrayVar;

void parseIntoArray(char* sourceChars);   // creates runArrayVar

I won't put the implementation of parseIntoArray() here because it's trivial to do with a loop, but I'll assume that arrays are null-terminated, although in the problem they don't have to be. Here is the problem part. I want to implement a function like this:

void alterArray(char* newSourceChars, int changedOffset,
                int changedLength, int changedCharsAdded);

This responds to a change in the source text. Included is the new text, the beginning and length of the altered area, and for reference, how many extra characters were added. For example, take the original zz22344a. If the substring 223 was pasted over with 23_44, then the new string would be zz23_4444a and the new array would be two z's, one 2, one 3, one _, four 4's, and one a.

I could get the new runArrayVar naively by just calling parseIntoArray, but I want to be less naive: I want to step through and only change the parts of runArrayVar that need to be changed. Finding the first changed element is pretty easy; skip through until you find one that overlaps changedOffset (you need to test one extra char after the element). After that it gets dicey and I can't figure it out. Take the above example:

zz needs to be re-checked because the character right after it might have been changed to a z. It wasn't, so it remains zz. Now we're at offset 2.

22 is rechecked, and it turned into 2. So OK. Now we're at offset 3.

3 is rechecked, and it's the same. So we're at offset 4.

44 is rechecked, and apparently turned into an underscore. So we're at offset 5.

At this point we're still looking at characters that have changed, and we're at 4444. According to the previous logic, a turned into 4444. OK. Now we're past the characters that have changed, and our array still has an element with one a left over. I can keep parsing and terminate the array when I hit the end of the string, but suppose that a was actually a million as in a row. The algorithm should be able to reason that it doesn't have to do any more work and terminate. If you look at the example, there is nothing you could have changed that particular section into that would influence the a.

This is difficult. I've tried it a lot of different ways and I can't figure out exactly when the algorithm needs to terminate. Please let me know if you have any ideas!

If a Run only retains characters and sizes in an array, it seems as though you only need to find the indices corresponding to changedOffset and changedOffset + changedLength, and then potentially change the sizes of the characters in the indices to the right and left by simple addition. That is, if you have an array of Runs:
$$[(x,1),(y,2),(a,2),(b,1),(c,1),(z,2),(x,1)]$$
for alterArray("ac_zz",3,4), it is first determined that the $a$ and $c$ are the beginning and ending characters (the $b$ is eliminated). This is done by simply adding: $1+2=3$ (from the $1x$ and $2y$) and $2+1+1=4$ (from the $2a,1b,$ and $1c$).

Then you check whether either side has to be combined: on the left side, the $y$ is not affected; on the right side, the $z$ is affected and so we add $2+2=4z$. The $x$'s are never checked.


Non Deterministic PDA accepted language not clear This is a PDA from the lecture slides I'm using:

They say it accepts all words that contain double a's. While it makes some sense it's not full proof.

What prevents the second a to be read in the left branch not the right? Or even a 3rd..4th a and so on? Is that the case of human Intervention like needed in PDA for oddpalindrome?

Also as far as I understand a PDA needs to read the whole input tape AND have an empty stack by the end which doesnt seem to be the case if the input is more than an a. What am I not understanding?

The PDA you're linking to is non-deterministic; indeed, the state you are confused about has two out-edges labeled $a$. For the PDA to accept its string, it's enough for there to be one accepting computation – what you refer to inaccurately as "human interference" [intervention?]. Regarding the acceptance condition of the PDA, figure out what acceptance condition makes this PDA accept the advertised language, and this is the accepting condition that you should have in mind.


Show that approximation ratio for a convex hull algorithm is $\pi/2$ Facts: n points in the plane, each has one of k colors, all k colors are represented.

Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small as possible.

Greedy algorithm: For each point p, for each color c not equal to p, select the point of color c closest to p. In the end, choose the point set that has a convex hull with the smallest diameter (diameter is the distance between the two points furthest apart.)

Why is the approximation ratio $\pi/2$?

This was an exercise on my graduate level algorithms exam. We were only given a few lines to answer so it should be simple enough, but I do not know where to start.

Here is a suggestion as to where to start. Suppose that the optimal solution has diameter $D$. Its optimal value is at least $2D$. If you could somehow show that the set selected by the greedy algorithm has diameter $d \leq D$, then it would follow that its value is at most $\pi d \leq \pi D$.


Prove that AVL tree has this kind of property with Fibonacci sequence Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$  where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=1, F(n) = F(n-1) + F(n-2) ~~~~\forall n \geq 2$

This is my go:

We know it is an AVL tree so $h = \log_2{n}$
Thus we need to prove that $n \geq F( \log_2{n})$

$F(\log_2{n})= F(\log_2{n}-1)+F(\log_2{n}-2)$
However I am stuck from here, I don't know what this helps me with and I am clueless on what to do next..
I would appreciate your help, thank you!

Let $T$ be an AVL tree of $n > 0$ nodes having height $h \ge 0$. You can prove that $n > F(h)$ by induction on $h$.

For $h=0$ the claim is true since $n=1$ and $1 > 0 = F(0) = F(h)$.
For $h=1$ the claim is true since $n \ge 2$ and $2 > 1 = F(1) = F(h)$.

For $h \ge 2$, let $r$ be the root of the AVL tree. The subtree $T_\ell$ rooted in the left child of $r$ and the subtree $T_r$ rooted in the right child of $r$ exist are both AVL trees. Moreover, since $T$ is balanced, at least one tree $T'$ among $T_\ell$ and $T_r$ must have height $h-1$, while the other tree $T''$ must have height at least $h-2$.

By inductive hypothesis the number $n'$ of nodes of $T'$ is more than $F(h-1)$, while the number of nodes of $T''$ is more than $F(h-2)$.
Therefore, the number of nodes $n$ is:
$$
n = 1 + n' + n'' \ge 3 + F(h-1) + F(h-2) = 3 + F(h) > F(h).
$$


Superscalar processors and complex instructions I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia.

How do such redundant units work?

Is a complex instruction (for accelerating heavy process, for example Instructions used in Intel IPP, Integrated Performance Primitives) decomposed in micro operations befaure being dispatched among these redudant functional units?

What about hardware instructions? Like AES-NI?

I also read the Wikipedia article SMT and did not understand the following sentence:

  Superscalar means executing multiple instructions at the same time while thread-level parallelism (TLP) executes instructions from multiple threads within one processor chip at the same time.

I don't understand very well the distinction between these two things. Can somebody explain the subtleties?

You should understand that any program is a sequence of instructions (ok, you an think of it as a collection of threads, where every thread is a sequence of instructions or a virtual process that executes that series of instructions). The instructions are supposed to be executed one after another. Single pipeline processor fetches instruction as they are ought to, every clock cycle and keeps its functional unit executing an instruction per cycle. This is not very true actually because execution takes multiple cycles and you fetch next instruction before previous is complete. But we pretend that instructions are still executed one after another and you still need one FU. Superscalars, however, cheat. They tell to the user that they still execute her program as designed, one instruction after another, yet take a window of neighbor instructions and execute them at once. They introduce extra FUs (Wikipedia called them "redundant") for this technique, called "Instruction Level Parallelism" (ILP).

Superscalars also have to entail a complex dependency detection and maintenance mechanism. As Amdahl has explained), because instructions of the same thread operate on the same data set, you have a lot of dependencies, especially among neighbor instructions and, thus cannot gain a lot of parallelism at ILP. The parallel pipelines are therefore sometimes used to execute different threads. This is full-scale parallelism already (except the synchronization cases and cache contention, which prevents any advantage of TLP over ILP, especially if von Neumann bottleneck is considered). Such TLP is known as hyperthreading. Yet, it is true parallelism since now threads are indeed executed in parallel, as if there are multiple cores, rather than parallelism is emulated by periodically switching threads on a single pipeline and, therefore, is also called "simultaneous multithreading".

I do not even see any reason to differentiate between multicore and hyperthreading. Since different pipelines execute different threads, this means that they have separate instruction pointer, set of registers and everything you need for the context, which are switched. Might be the common cache and shared FUs is the only things that distinguishes single core from multiple cores. Yes, shared cache. This may save you from cache incoherence /memory consistence problems that can happen in truly multicore system.


Why the number of adresses stored on RAM is equal to $2^x$ when has "x" adress lines? I know that a RAM when has 20 adress lines can store up to 2^20 data. I don't know the reason. What is that for and how?

On the image, where and what is the 2^20?

$2^{20}$ "data" is rather a vague value. If you have 20 bits for address lines you can possibly have $2^{20}$ combinations. If each address line represent 1 bit of data then you've got  total $2^{20}$ bits of data to store in a memory. However most machines store 1 byte of data for every address combination giving you $2^{20}$ bytes or $1$ MB


findMax reduce to sort Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too?

I'm confused with this spread of lower bounds and applicability of reductions.

After you sort an array, the minimum can be found in the first position, and the maximum can be found in the last position. This reduces finding the minimum and maximum to sorting an array. However, sorting is actually more difficult than just finding the minimum or maximum, so it's not clear what this reduction is good for.


0/1 Knapsack problem with overlapping items Here's a doozy:

Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack?

In this problem, you can think of an "item" as a bag of coins with the following properties:

There are many, many different types of coins (1M+)
Every coin is worth the same amount
Each bag has at most one of any type of coin

For example, bag 1 might have two coins, one of type A and another of type B. And bag 2 might have two coins, one type B and one type C.

We can only take one of each type of coin. So picking bag 1 and bag 2 would mean that we have 3 total coins (one A, one B, and one C).

How can we figure out which bags to take to maximize the number of coins you can take?

The subproblems aren't independent, so I don't think we can use dynamic programming.

For extra credit:

How can we get within a certain threshold, say 10%, of the capacity W as fast as possible?

Calling this a variant of Knapsack is a bit confusing, since it's more like maximum-weight independent set. Bags are nodes, bags that share a type of coin have an edge between them, and the number of coins in each bag is the weight of the node. Going the other way is annoying, translating unweighted MIS into this problem is easy though.

Anyway here's a direct ILP formulation of the coins/bags thing:

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
take_bag[i] ∈ { 0, 1 }

You could use the linear relaxation of that to do branch & bound, which you can stop early when you're happy enough with the gap between the best found solution and the objective value of the linear relaxation. Or check the literature for MWIS solving. There are many approximation algorithms as well.

Taking into account the capacity constraint, the ILP model becomes

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
sum of take_bag[i] * size[i] ≤ W
take_bag[i] ∈ { 0, 1 }


removing ε production It's not that i dont know how to remove εproduction but when complex problem arises i get confused for example

S-->Aa/aaB

A-->a/ε

B-->bbA/ε

CFG without ε production for the above question is

S-->Aa/aaB/a/aa

A-->a

B-->bbA/bb

here i replaced A,B with ε in all productions to obtain the result

But for questions like this one

S-->ABCa/bD

A-->Bc/b

B-->b/ε

C-->c/ε

D-->d

how many possabilities will occur in S production

I understood your confusion

firstly here C,B,A,S all approach ε at one point

so solving in the method you solved previous example put ε one by one in S then consider all combinations like this

S-->ABCa/bD/BCa/ACa/ABa/Aa/Ba/Ca/a

A-->Bc/b/c

B-->b

C-->c

D-->d
firstly in S for (ABCa) put ε in A then B then C later BC,CA,AB,ABC
so if you follow this fashion you get the answer