'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet? I am designing a poker agent with different heuristics to decide whether to raise, fold or pass (in Texas holdem poker). I am planning to have 4 heuristics with the agent biased to one of them.

The poker game will consist of 10 agents playing against each other.

I have two heuristics now:

bluff - Agent would keep betting until all others fold
odds>pot odds - https://www.youtube.com/watch?v=1wux3avg1CM&feature=relmfu

I need to know what other heuristics a poker agent can use to make a decision.

Here are some of the heuristics I use when playing online on XBOX live against bots, but the game is so much better with human players, bots are boring and predictable.

Obviously, what are you hold cards. Rockets to 7-2 off suite. There are many poker tables that give you the odds for the hold cards.
How many players at the table. The more players you have the better your hand has to be because more cards are in play for making better hands. When you get down to one-on-one, even a high card is often good, but with a table of 10, you should be holding at least a high pair after the river.
Is the card generator truly random. For the XBOX live games it is rumored they use a card generator named the "Action Engine" because it is designed to generate action on the table by setting up possible flushes and straights. You would not believe how many people chase down the river hoping for a straight or flush, problem is they tend to get it more often than random because of the simulated gambling.
Is there a pattern to the players betting? Do they continue to bet on each card? Do they slow play when then have a good hand or the nuts? Do they bet really big when bluffing? Do the bet really big when they have a high card or better? I their betting related to the the cards they have? Do they ever bluff?
Are you allowed to keep a database of all hands? This is a big advantage if allowed.
Position. Are you the dealer or in the blind? Ever heard the saying that poker is a game of position.
Does a player re-raise?
Does a player fold before or on the river to hide their cards if they don't believe they have a good hand even if they can check?
Do they play most hands or are conservative. A conservative player will bet only on good cards and you can pretty much count on that, while a player who plays most to all hands means that you have to more attentive to them having the nuts from the flop no matter what the flop is.
Does the player have a limit they never bet or raise beyond?
How many out cards do you have versus all of the possible out cards.
Does the player play the heavy? At what level will they play the heavy against another player?
Is the player afraid to call an all-in.
Is there a level below they will not raise? I.e. only raise if a King or higher in their hold cards, or have a pair or higher with what's on the table?
Do they go all in if the best hand can only be made by the cards on the table?
Do they bluff more when A's, or possible straights or flushes appear?
Is there betting based on money amounts or multiples of the blind?
Does there style of play changed based on their money amount? Based on a multiple of the blind? Based on who sits next to them?
Can you use the length of time the opponent uses to play a turn to your advantage?
Is the player trying to win the game or just play to make it to the money rounds?
Are the players susceptible to being pulled into betting wars?
Can betting big on the river cause the player to fold more than normal?
Can always re-raising a player get them to change their playing style?
Are their bet amounts increasing or decreasing as the hand progresses?
Is there a minimum amount they always bet no matter what they have in the hold?

These are just the basic ones for playing a bot, if you add a human player the list of heuristics gets much more complicated.


Static type analysis with dynamic scoping? Both in school and out, I have only ever encountered dynamic scoping paired with dynamic typing. Is there any published work (even if just academic, not yet implemented in a "real" programming language) on doing static type verification with dynamic scoping?

It seems to me that it should be possible if the type checker can build a static call graph for the program, and then check that all accessed variables are defined somehow in all possible traversals, and unify types between different traversals that lead to the same access point. While doable, though, that's potentially a very expensive operation, so I'd be interested to see if there is any way to significantly optimize it.

For reference, Scala seems like a decent proof-of-concept for some first steps towards such a dynamically-scoped type system with its concept of "implicit arguments"; it just requires that all usable edges in the dynamic call graph through which dynamically-scoped values can pass be manually type-annotated by the programmer, rather than assuming that all edges in the call graph are usable and having the compiler figure out the types automatically.

There is a paper titled Implicit Parameters: Dynamic Scoping with Static Types that discusses just such a system.

The implement a slightly different system from Scala under the name "implicit parameters". By having compiler automatically generate implicit parameters in any function that calls other functions with implicit parameters the problem becomes nearly identical to standard type inference. Additionally, since these implicit parameters are still part of each functions type signature they propose a syntax for declaring most of a functions signature, while still allowing the compiler to determine the types of any implicit parameters.


How can ws with |w| = |s| and w ≠ s be context-free while w#s is not? Why does (if so) the seperator $\#$ is making a difference between the two languages  ?

Let say:

$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

Here is a proof and a grammer representing $L$ as a $CFL$

And below Im adding a proof for $L_{\#} \notin CFL$ :

Does the $\#$ sign truly make a difference? if so, why is that ? and if not, which one of the proofs is wrong and where?

Proof that $L_{\#} \notin CFL$ :

Assume by way of contradiction that $L ∈ CFL$. Let $p > 0$ be the pumping constant for $L$
guaranteed by the pumping lemma for context-free languages. We consider the word
$s = 0^{m}1^{p}\#0^{p}1^{m}$ where $m=p!+p$ so $s ∈ L$.
Since $|s| > p$, according to the pumping lemma there exists a representation $s = uvxyz$, such that
$|vy| > 0$, $|vxy| ≤ p$ , and $uv^{j}xy^{j}
z ∈ L$ for each $j ≥ 0$.

We get a contradiction by cases:

If $v$ or $y$ contain $\#$: Then for $i = 0$, we get that $uxz$ does
not contain $\#$, so $uxz \notin L$ in contradiction.
If both $v$ and $y$ are left to $\#$: Then for $i = 0$, we get that
$uxz$ is of the form $w\#x$, where $|w| < |x|$, so $uxz \notin L$.
If both $v$ and $y$ are right to $\#$: Similar to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| < |y|$: Then
for $i = 0$, we get that $uxz$ is of the form $w\#x$, where $|w| >
   |x|$, so $uxz \notin L$.
If $v$ is left to $\#$, $y$ is right to it, and $|v| > |y|$: Similar
to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| = |y|$: This is
the most interesting case. Since $|vxy| ≤ p$, $v$ must be contained
in the $1^{p}$ part of $s$, and $y$ in the $0^{p}$ part. So it holds
that $v = 1^{k}$ and $y = 0^{k}$ for the same $1 ≤ k ≤ p$  (in fact,
it must be that $k < p/2$). For each $j ≥ 0$, it holds that
$uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\#0^{p+j·k}1^{m}$, so if it
happens that $m = p + j · k$, then it holds that $uv^{j+1}xy^{j+1}z
   \notin L$ in contradiction. To achieve this, we must take $j =
   (m-p)/k$, which is valid only if $m − p$ is divisible by $k$. Recall
that we chose $m = p + p!$, so $m − p = p!$, and $p!$ is divisible by
any $1 ≤ k ≤ p$ as wanted.

Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it.

Let's consider the three languages

$\qquad\begin{align*}
  &L_=     &\!\!\!\!\!\!\!\!\!
       &= \{ xy   \mid |x| = |y|, x \neq y \}, \\
  &L_{\#}  &\!\!\!\!\!\!\!\!\!
       &= \{ x\#y \mid  x \neq y \},\ \text{and} \\
  &L_{=\#} &\!\!\!\!\!\!\!\!\!
       &= \{ x\#y \mid |x| = |y|, x \neq y \}.
\end{align*}$

As we have seen here, $L_=$ is context-free. The trick is, in the grammar, to generate symbols "on the right" but count them "on the left" later (or the other way around), making sure mismatching symbols appear at matching positions. The length condition is trivial since it reduces to even length.
You can construct an NPDA with a similar idea, using the stack to match the position.

$L_\#$ is also context-free. The proof is even simpler: the mismatching symbols appear the same distance away from the beginning resp. the separator. Unequal lengths can be checked separately; non-determinism "chooses" between the two options.

Now, as you show, $L_{=\#}$ is not context-free. Here is why the proofs for the other two languages break down.

In the grammar for $L_=$, if we have to generate a separator in the middle we can not "reassign" symbols from "left" to "right".
Instead of "accept if lengths unequal or mismatch" we have to "accept if lengths equal and mismatch". Non-determinism can not help us with the and!

So what it boils down to, intuitively, is that conditions of the form "$x \neq y$" and "$|x| = |y|$" are both "context-free" in the sense that they can be checked with a stack, but not using finite control. Therefore, a PDA can do one but not both.

The PDA for $L_=$ "cheats" since it does not really check these conditions for $x$ and $y$; it splits the word up in a different way. That's no longer possible if you have the separator.

Addendum: I boldly claimed that $L_= \in \mathrm{CFL} \implies L_{=\#} \in \mathrm{CFL}$ because CFL is closed against inverse homomorphism. While it's true that $f(L_{=\#}) = L_=$ with $f$ the identity except it deletes $\#$, that is not relevant. $f^{-1}(L_=) = L_\#$; nothing can be said about $L_{=\#}$.

Addendum II: Note that $L = \{ x\#y \mid |x| = |y| \}$ is trivially context-free. Hence, with $L \cap L_\# = L_{=\#}$ we have a nice example for CFL not being closed against intersection.


How to find the reverse of a binary string with simple binary operators? I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome?
So my approach is to feed the input to a circuit that reverses the input, ie if the input is 0111010, I need the output to be 0101110. Is this possible to achieve with only, and/or/xor/not and these simple operators in a generic way (on paper, not looking to implement a circuit with a predefined number of bits)?
Once I have this reversed output, I can use it with an "and" gate to compare to the original input and see if they match, but I'm stuck at the first part.
I appreciate your suggestions
Thanks in advance

Yes, absolutely.  Every boolean function can be implemented by a circuit.  In this case, it suffices to XOR bits 1 and $n$; bits 2 and $n-1$; and so on; and then take the NOR of all of the outputs of these XOR gates.


Evaluating correctness of various definitions countable sets I was trying to understand the definition of countable set (again!!!). Wikipedia has a very great explanation:

  A set $S$ is countable if there exists an $\color{red}{\text{injective}}$ function $f$ from $S$ to the natural numbers $\mathbb N$.
  If such an $f$ can be found that is also surjective (and therefore $\color{red}{\text{bijective}}$), then $S$ is called countably infinite.
  In other words, a set is countably infinite if it has $\color{red}{\text{bijection}}$ with the $\mathbb N$.

So I summarize:

$S$ is countable iff $S\xrightarrow{injection}\mathbb N$
$S$ is countably infinite iff $S\xrightarrow{bijection}\mathbb N$

But then wikipedia confuses by stating following points:

  Theorem: Let $S$ be a set. The following statements are equivalent:

  $S$ is countable, i.e. there exists an injective function $f : S → \mathbb N$.
  Either $S$ is empty or there exists a surjective function $g : \mathbb N → S$.
  Either $S$ is finite or there exists a bijection $h : \mathbb N → S$.

Q1. I feel 2nd statement is wrong, as it allows some element in $S$ to not to map to any element in $\mathbb N$. That is $\mathbb N \xrightarrow{surjection} S$ does not imply $S\xrightarrow{injection}\mathbb N$. Hence $S$ is not countable. Right?
Q2. 3rd  statement defines countably infinite set, so its countable also. Right?
Q3. Also I dont get if the extra restrictions of emptyness and finiteness in statements 2 and 3 are required.

Wikipedia further says:

  Corollary: Let $S$ and $T$ be sets.

  If the function $f : S → T$ is injective and $T$ is countable then $S$ is countable.
  If the function $g : S → T$ is surjective and $S$ is countable then $T$ is countable.

Q4. Here, too, I feel 2nd statement is incorrect for the same reason as 2nd statement in the theorem. Right?

The Wikipedia theorem is correct. More generally, if $A$ is an ordered set and there exists a surjection $g\colon A \twoheadrightarrow B$ then there exists an injection $f\colon B \hookrightarrow A$ given by $f(b) = \min g^{-1}(b)$. This is an injection since $g(f(b)) = b$.

More generally, if you assume the axiom of choice then you don't need to assume that $A$ is ordered, since the axiom of choice guarantees the existence of a function $f\colon B \to A$ satisfying $f(b) \in g^{-1}(b)$ for all $b \in B$.


Prove the equivalence between a CFG and a Context free language I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules:

$S\rightarrow a^2Tb$

$T\rightarrow a^3Tb^2 |\epsilon$

are equivalent to each other.

I'm going to prove this by saying $L(G)\subseteq L$ and $L \subseteq L(G)$. I was able to prove the first one. I should be able to prove the second one with induction on the length on a word $w$. But how can I do that? The induction basis should start at length 3, because the smallest word $w \in L$ is $aab$. But the second word has a length of 8. This means the stepsize in the induction proof is 5. I've never done an inductive proof with a stepsize different from 1. How can I do something like this as it's not possible to state in the induction step that "We assume that the theorem holds for $|w|=n$, now we are going to proof that it holds for $|w|=n+5$"?

UPDATE:
I think I found a solution to my own question:

Inductionbasis: Suppose $|w|=3$. Then $w$ must be $aab$ because that's the only word of length 3 that satisfies the requirements for the language L. But $aab$ is also an element of $L(G)$. The basis is OK.

Induction hypothesis: Assume that the theorem holds for all words $w`$ with length $|w`|=3+5n$. We are now going to proof that the theorem also holds for all words $w$ with length $|w|=3+5(n+1)$.

$w$  must be of the form $\alpha a^3b^2 \beta$ to be an element of $L$. Now consider the word $z=\alpha \beta$ with length $|z|=3+5n$. Then, by induction, we know that $z \in L \implies z \in L(G)$. Because $z \in L(G)$ it must hold that $z$ is of the form $a^nb^m$ with $2n=3m+1$. If we add the 3 $a$'s and 2 $b$'s from $w$ to this equation, we find that $2(n+3)=3(m+2)+1$. The following applies to this equation:

$2(n+3)=3(m+2)+1$

$\iff 2n+6=3m+6+1$

$\iff 2n+6=3m+1+6$

$\iff 2n+6=2n+6$

Thus, $w$ also satisfies $L(G)$. QED

Is this proof correct?

Since this is a very simple "linear" grammar, its language can be determined by looking at the possible derivations.

Clearly a successful derivation has to start with $S\to a^2Tb$, then repeats $k$ times the production $T\to a^3Tb^2$ and closes with $T\to \epsilon$. That will give strings of the form $a^{2+3k}b^{1+2k}$ with $k\ge 0$. (1)

Then we need to establish that these are exactly the strings of the form $a^ib^j$ with $2i=3j+1$. (2)

One direction is easy, strings of the form (1) satisfy (2) -- you solved that yourself -- by observing that
$2(2+3k) = 3(1+2k)+1$.

Your proof for the other direction sounds good, but it is not clear to me how one argues that the induction has step size $5$ (other than by trial and error).

The following would work. Start with (2) for natural numbers $i,j$.

This implies $3j+1$ is even (and non-negative).

Or, $3j$ is odd, so $j$ is odd, which means it is of the form $j=2k+1$ for $k\ge 0$.

Then $2i=6k+4$, or $i=3k+2$, and we are done.

This argument seems rather ad hoc. Note the similarity between this exercise and linear algebra. There are two different representations for a line in 2D: using vectors or equations. Here these are:

$\{ (2,1)+ k\cdot(3,2) \mid k\in \mathbb R \}$
$\{ (x,y) \mid 2x-3y=1 \}$

Unfortunately, I do not think linear algebra tricks directly work, as we here must restrict ourselves to integers and not the real numbers.


How to evaluate recommendation engine without ground truth? I have developed an algorithm which recommends geographical locations to users based on popular trends and their own interests. The dataset is created by my organization. So the user selects a few categories and based on his interest and rating by other people he is presented with recommended places for him.

How do you evaluate or use metrics for such system given that ground truth doesn't makes sense in this case ?

EDIT:
I meant that how to evaluate the accuracy or quality of results in such case especially for published work.

EDIT 2 (as per the request for details in the comments)

Details of the system

The user indicates his preferences from a predefined set of tags (cultural, mountains etc)
Users can also rate different places on a scale of 1-5.
Users profile (geographical location, places already visited etc are already stored in his profile)
Based on user's choice and other heuristics(rating etc), a set of places is recommended by the system.

One of the best ways to benchmark such big systems is to use a service like Amazon Mechanical Turk (AMT). First you implement a user interface for everyday users where they could specify whether or not the recommendations are relevant. Then you submit this to Amazon Turk and let many people try it out.

You could further process the results of an Amazon Turk to really benchmark your system and obtain quantification of accuracy of it.

Team of Fei Fei Li used similar technique for benchmarking their Fine Grained segmentation algorithm. The paper is here: http://vision.stanford.edu/pdf/DengKrauseFei-Fei_CVPR2013.pdf

Naturally using AMT won't give you a realtime solution, where you get a benchmark everytime a recommendation occurs, however you can prepare a subset of your dataset and let AMT guys evaluate the system using GUI you provide. Again, a sample data collection system is described here: http://ai.stanford.edu/~jkrause/papers/fgvc13.pdf

I have no intention of advertising it but AMT is also an economical workaround.


Conditions to apply Source Coding Theorem I was wondering what are the conditions to apply source coding theorem (SCT).

1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT?

I was asking because in my lecture, SCT is only discussed in uniform coding section.

2. Is the result of SCT for uniquely decodable coding or is it for lossless coding?

In Wikipedia SCT, it's said $f$ is unique decodable code, then we have SCT. In my lecture, it gives me an impression that SCT is generally applied to all lossless coding.

It is an average in bits/symbol and does apply to all coding schemes.
You're correct, the number of bits/symbol needed is equal  or larger than the entropy rate (asymptotically, though) of the source for any lossless code.
If you allow for lossy coding, then a generalization called rate-distortion function is needed to lower bound the rate required.


How convert instances of a language efficiently into 3SAT instances? The following question is from Sanjeev Arora and Boaz Barak ( not homework )

  Show that for every time constructible
  $T:N \to N$, if $L \in NTIME(T(n))$ then we can give a polynomial-time Karp reduction from $L$ to $3SAT$ that transforms instances of size $n$
  into 3CNF formulae of size $O(T(n)logT(n))$. Can you make this reduction also run in $O(T(n)logT(n))$?

The best I could come up with is a $O(T(n)^3)$ formula. We take each configuration to be of at most length $T(n)$ and the machine runs for $T(n)$ steps. So we have a grid of $T(n)$ rows each with $T(n)$ columns. Each row represents a configuration. We just impose the condition that each row follows from the previous by using $M's$ ( where $M$ is a machine deciding $L$ in $O(T(n))$ time ) transition function in at most one step. The first row should represents start configuration and last row represents the accept configuration. Thus an $O(T(n)^3)$ formula is formed by this approach.
How can I do better ?

The idea is to reduce an instance  $x$ to $\phi$ that uses only $O(T(n))$ symbols and clauses. $\log T(n)$ will be the length of binary representation of each symbol. This is the upper limit that you cannot cross if you want to solve the problem. So, you will have to optimize quite a bit. See the oblivious TM and state representation in Arora and Barak to get an idea.


Minimum sum of two numbers formed from digits of two arrays Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the one with the smallest $n_1$ is chosen.

Restrictions:

Time: 0.1 s (brute force ain't gonna do it)

Memory: 2 MB

This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n_1$ at the end. Observation: after this process is done all remaining digits in both arrays are different (but this is not very relevant).

Brute force the next digit of $n_1$, there are at most 9 possible digits that can be used for $n_1$. Fix a digit $d$ not used yet in the first array. Once $d$ is fixed as the next digit of $n_1$ use the largest digit lower than $d$ for $n_2$ (if no such digit exists continue with next digit for $n_1$).

After we have this prefix for $n_1$ and $n_2$ we already know that the inequality $n_1 > n_2$ holds, whatever order we use for following digits. In order to minimize $n_1 - n_2$ we should order remaining digits from first array in such a way that $n_1$ is minimized and order remaining digits from second array in such a way that $n_2$ is maximized. For the first case we should add remaining digits of $n_1$ in non-decreasing order, and for $n_2$ in non-increasing order.

Next is the pseudo-code for the explained algorithm. Notice that $n_1$ and $n_2$ are treated as string, not like numbers, so addition means concatenation. Also, instead of dealing with array of digits as input, convert them to array of frequency, $F_i(d)$ denotes how many times digit $d$ can be used for number $n_i$.

F1 = Frequency of each digit in first array.
F2 = Frequency of each digit in first array.

n1 = ""
n2 = ""

# Remove common digits in both arrays
for d in [0..9]:
    while F1[d] > 0 and F2[d] > 0:
        n1 += d, n2 += d
        F1[d] -= 1, F2[d] -= 1

# Brute force next digit for number n1
for d1 in [1..9]:
    # Ignore digit if it is not available
    if F1[d1] == 0:
        continue

    d2 = None

    # Iterate backwards and find higher digit available for d2
    for d2_it in [d1 - 1..0]:
         if F2[d2_it] > 0:
             d2 = d2_it
             break

    # If there is no available next digit for n2 continue
    if d2 is None:
        continue

    tmp_n1 = n1 + d1
    tmp_n2 = n2 + d2

    # Add next digits greedily
    for d in [0..9]:
        for i in [0..F1[d]):
             tmp_n1 += d

    for d in [9..0]:
        for i in [0..F2[d]):
             tmp_n2 += d

    # Check difference of this pair
    # and keep better pair accordingly to problem restrictions.
    # This function will be called at most 9 times.
    report tmp_n1, tmp_n2

Notice that report will be called 0 times in case there is no valid answer.


Lower bound for point set triangulation How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$?

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \log n)$. Is it valid to argue that since the convex hull is also part of the triangulation it can't be done faster or else the lower bound for the hull would also be lower?

Edit: By Triangulation I mean connecting all the points via non-crossing edges such that they form triangles: https://en.wikipedia.org/wiki/Point_set_triangulation

No, that's not a valid argument.  You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.


How are lamport timestamps useful in practice? I am reading Lamport's paper titled Time, clocks, and the ordering of events in a distributed system

I understand what's in there more or less, but I am confused whether Lamport timestamps on their own are useful in practice since just by looking at the logical timestamps, we can't say anything about which happened before what. It seems to me that Lamport timestamps on their own aren't useful, and we need to extend them to something like vector clocks to be useful in practice. Am I missing any details?

As Wikipedia explains:

The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.
Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender. The above mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.

In distributed systems, it is often necessary for (almost) all the nodes to reach agreement on things such as the order of events. That agreed upon order need not be the God's Eye knowledge of the order of events. There are various other distributed agreements needed.


How to find the number of discrete states possible by current computers? In his famous article, "Computing Machinery and Intelligence", Allan Turing talks about discrete-state machines and the largeness of the number of states provided by that time "state-of-the-art" machine, "Manchester Machine", which he states is about 2^165,000. Link to the article

Well, that was 1950's. I'm trying to compare it with modern day computers and get an average number of states for a usual commercial machine. How can I find it?

Is it related to memory size (Turing calculates it by the number of "stores", or sheets of paper available)? If so, would this make the number of states tend to infinity due to the current possibility of writing/erasing memory at will?

Acording to the suggestions that were given in the comments to the question, the number of distinct discrete states possible by a machine are related to the size the machine's of memory (or "stores" space, using Turing's nomenclature).

Since a bit has two distinct discrete states, a byte then have $$ 2^{2^3}=2^8 $$ discrete states.

Two bytes, $$2^{2*2^3}=2^{16}$$

Hence, a commercial availabe 4GB DDR3 RAM machine would roughtly be $$ 2^{2^2*2^{30}*2^3} =2^{2^{35}}=2^{34,359,738,368} $$

Further, today's (March 2017) world fastest computer, Sunway TaihuLight, with more than 1 PB memory, would have rougthlty $$ 2^{2^{50}*2^3}=2^{53}=2^{9,007,199,254,740,992}$$ distinct discrete states.

Correct math if wrong, but the idea is this, taking in account only main memory (disregarding cpu registers, secondary memory and cache, as j_random_hacker stated that could be done).


Regular expression for the second symbols from the front and the back are equal I am practicing for an exam. I am trying to convert a language to a regular expression. The language and my solution is as follows:

$L=\{w∈\{a,b\}^+│|w|≥4\  and\ the\ second\  symbols\  from \ the \ front\  and\   the\  back\  are\ equal\}$

Solution: $(a+b)x(a+b)^* x(a+b)  \ \ where\ x=(a+b)$

Is this correct? If not, can someone correct me. also, am I allowed to use variables in regular expressions?

Thanks in advance

You asked two questions.  The usual rule on this site is to ask one question per post.

No, you're not allowed to use variables in regular expressions.  Regular expressions have a formal definition.  To qualify as a regular expression, you need to meet the requirements in the definition.  The definition can be found on Wikipedia or in your favorite textbook, and you'll note that it does not allow "where" or "variables".

For your first question about how to find a regular expression for a language, take a look at How to prove a language is regular?.


ip/tcp packet decoding without wireshark How can we manually read and interpret packets properly without using wireshark?
Now from the Ethernet header I know that the Destination MAC Address should be at the 5th byte (after converting bits/bytes). So from this data, I thought it would be 4a onwards. However, in reality it's 00:17:f2:d0:4c:82.
Same goes for the IP source destination. For instance, the source should be at 13-16 bytes. According to the readings, I guess it should be 0800 onwards. But in reality, it is on 0a 32 e7 85 but I don't get why? I am just confused on how to interpret this data correctly or maybe I am understanding the general header structure incorrectly.
https://ntquan87.wordpress.com/2015/08/17/reading-packet-hex-dumps-manually-no-wireshark/

My guess is that what you are seeing is a Level 2 Ethernet frame and therefore the preamble is missing. Also the Ethernet checksum seems to be missing. In this case everything seems to line up (the packet type inside the Ethernet frame, the IPv4 version, the IPv4 packet length, the packet type, i.e. TCP, inside the IP packet,  ...). Then you'd read your packet as in the picture.

The TCP payload is

474554202f20485454502f312e300d0a
557365722d4167656e743a2057676574
2f312e31312e340d0a4163636570743a
202a2f2a0d0a486f73743a207777772e
696574662e6f72670d0a436f6e6e6563
74696f6e3a204b6565702d416c697665
0d0a0d0a

and decodes to:

GET / HTTP/1.0
User-Agent: Wget/1.11.4
Accept: */*
Host: www.ietf.org
Connection: Keep-Alive

which is coherent with the fact that the destination port is 80.


Can someone clarify landau symbols definition please? I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know that technically the correct notation is to say $f(n)$ is an element of $O(f(n))$, not $f(n) = O(f(n))$.

Loosely, my understanding is this, given$ f(n) = n^2 + 2n +log(n)$ Big O represents the upper magnitude, so it would be correct (according to a past CS tutor), but not very accurate, to say $O(f(n)) = n^3$, but incorrect to say $O(n) = log(n)$, whereas the $Ω(f(n)) $represents the lower bound, so it would be correct, but inaccurate to say $Ω(f(n)) = log(n)$ or (not sure about this one), $Ω(f(n)) = 1$.

I know that $Θ(f(n))$ is defined as the intersection of $O(f(n))$ and $Ω(f(n))$, but is it valid to drop off lower orders of magnitude in the case of $Θ(f(n))$? ie. is $Θ(f(n)) = n^2$ correct? If not, what is the correct equality?

What I am entirely unsure about is $o(f(n))$ and $ω(f(n))$. I've seen the mathematical definitions and I know that the only difference between them and $O(f(n))$ and $Ω(f(n)) $respectively is that rather than "there exists C", it is "for all C", but my understanding of mathematical symbols is (at this stage) embarrassing. If anyone could shed some light on all of the above it'd be appreciated, thanks.

In the case of $O(f(n))$ and $\Omega(f(n))$ you are correct in that they can be wildly inaccurate and still be correct, for instance, $n$ is $O(2^n)$ - this just does not provide good information.

For $\Theta$ yes you can drop the lower orders of magnitude. What "$f(n)$ is $\Theta(g(n))$" means is that there are two constants, $C_1$ and $C_2$, and two values $n_1$, $n_2$ such that $C_1g(n)>f(n)$ for all $n$ greater then $n_1$, and likewise $C_2g(n)Nf(n)$ for all $n$ greater then $n_2$. In your case we can see that multiplying $n^2$ even by 2 will dwarf the remaining values of $f(n)$ for sufficiently large $n$, likewise multiplying by 1 will make it always smaller.

Little $o$ and $\omega$ notation is used to describe a function as being orders of magnitude less then another. When we were in big $o$ notation, as long as one constant $C$ existed such that $Cg(n)>f(n)$ then $f(n)$ is $O(g(n))$, with little $o$, every possible $c$ must cause this to happen. The easiest way to find this is to take the limit of $\lim_{x \to \infty} \frac{f(n)}{g(n)}$: if it is zero then $f(n)$ is $o(g(n))$; if it is $\infty$ then $f(n)$ is $\omega(g(n))$


Not Hamiltonian is in NP Class? I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest.

From this book and other study in complexity theory, I have seen the following statement:

  The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?

  Determining a that a Graph is not Hamiltonian is in NP-Class.

I read another book on this book on end of page 306, the authors wrote this is NP-Hard. anyone could clarify me?

The statement

  Determining a that a Graph is not Hamiltonian is in NP-Class.

is neither true nor false. It doesn't have a truth value, since there's a type mismatch. Similarly, the statement

  The color red is in NP.

is neither true nor false.

Here is something which is true. Let $L$ be the language of all Hamiltonian graphs. That is, $x \in L$ if $x$ encodes a Hamiltonian graph. (We fix the encoding once and for all.) The language $L$ is in NP since to prove that $x \in L$, one just needs to present a Hamiltonian circuit (a proof whose size is polynomial in the input size), and this proof can be verified in polynomial time.

Furthermore, $L$ is NP-complete. The book you're consulting probably has a proof. Therefore, if $L$ were in coNP, then NP=coNP, which is believed to be false. So it is probably the case that $L$ is not in coNP. But we don't know for sure.

The language $L'$ of non-Hamiltonian graphs is the complement of $L$ (modulo boring technicalities arising from the fact that not every string encodes a graph). Since $L$ is NP, $L'$ is in coNP. We can also see it directly: to prove that $x \notin L'$, one just needs to present a Hamiltonian circuit.

Furthermore, $L'$ is coNP-complete, since $L$ is NP-complete. Again, it is probably the case that $L'$ is not in coNP, since otherwise NP=coNP, which is believed to be false.


Regular expression and Right Regular grammar for decimals starting with 1 ending with 9? I was trying to do the following:

  Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). For example 12.9, would be a valid decimal number while 0.129 would be not since it does not begin with 1.

but it didn't seem to work:

1(0|1|2|9)*.(0|1|2|9)*9

or

S::=1X
X::=E|0X|1X|2X|9X|Y
Y::=.Z
Z::=E|0Z|1Z|2Z|9Z|A
A::=9

Why? Whats the correct answer?

Your regular expression is correct, however, your grammar isn't. Assuming $E = \varepsilon$, you can derive words like $S \to \mathtt{1}\,X \to \mathtt{1}\,\varepsilon = \mathtt{1}$.

A right regular grammar might look like this:
\begin{align}
S &::= \mathtt{1}\,A\\
A &::= \mathtt{0}\,A \mid \mathtt{1}\,A \mid \mathtt{2}\,A \mid \mathtt{9}\,A \mid B\\
B &::= \mathtt{.}\,C\\
C &::= \mathtt{0}\,C \mid \mathtt{1}\,C \mid \mathtt{2}\,C \mid \mathtt{9}\,C \mid D\\
D &::= \mathtt{9}
\end{align}


Complexity of 3SAT variants This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order such that the betweeness constraint of each triple is enforced while in the later problem there is a total order such that the betweeness constraint of each triple is violated.

What is the complexity of the following 3SAT variants?:

3SAT_1={($\phi$): $\phi$ has an assignment that makes every clause false}

3SAT_2={($\phi$): $\phi$ has an assignment such that exactly half of the clauses are true and the other half is false}

3SAT_1 is easy, and a variant of 3SAT_2 is NP-complete. My guess is that 3SAT_2 is also NP-complete. Update: my guess is proved below.

Let $C = x\lor y\lor z$ be a clause. Then $\lnot C = \lnot x \land \lnot y \land \lnot z$. An assignment makes every clause of $\phi$ false if it makes all their negations true. The conjunction of the negation of all clauses is just a big conjunction. A conjunction is satisfiable if and only if it does not contain a variable and its negation. So 3SAT_1 is in P (in fact it's in AC$^0$).

The variant of 3SAT_2 asks whether $\phi$ has an assignment that makes exactly $8/9$ of the clauses true. This is clearly in NP. To reduce 3SAT to this variant, take the formula $\phi$, and for each clause $C$ in $\phi$ add the eight clauses
$$(x_C \lor y_C \lor z_C) \land \cdots \land (\lnot x_C \lor \lnot y_C \lor \lnot z_C).$$
In any assignment, exactly seven of these are correct. In total we have $9|\phi|$ clauses. Of the $8|\phi|$ that we added, exactly $7|\phi|$ are always correct. Hence $\phi$ is satisfiable if and only if in the new formula one can satisfy exactly $8|\phi|$ constraints, which are $8/9$ of its clauses.

Update: Here is a reduction from 3SAT to 3SAT_2 itself. Given a formula $\phi$, consider two cases. The first case is when we can falsify all clauses in $\phi$ at once. As shown above, in this case each variable appears only positively or only negatively, and so setting it appropriately, the formula is satisfiable. Otherwise, add $|\phi|$ clauses of the form $x \lor y \lor z$, where $x,y,z$ are new variables. In any assignment either all of these are satisfied, or all are not satisfied. Since the original clauses cannot be all falsified at once (by assumption), the new formula can be half-satisfied if and only if the original one is satisfiable.


Variation of the Partition Problem Is the variation of partition problem where instead the sum of the sets only be equal to a value $B$, they could also differ by two ( i.e., the sum of one set could be $B-1$ and the other $B+1$ ) still $NP$-complete?

Yes.  To reduce the ordinary partition problem to this variant, just multiply each element by 3.  Now, the case where the weights of the two partitions differ by two cannot arise so, if the instance is a yes instance, it must be because there's an equal-weight partition.


Given a Noisy Curve, Write a Function to Output Likely Slopes I am training a Variational Autoencoder (type of convolutional neural network), and have been plotting cost over time. The result is a noisy curve, shown here:

I would like to write a function that gives the probability that the cost function has bottomed out, i.e. that its slope going into the future is zero. Due to the noise, I can't just take the derivative of the cost function, as it oscillates stochastically. I could take the derivative of the moving average of the cost function, but it would be unclear what window size to use, and regardless a single window size would be useful for only part of the line (the noise tends to increase over time).

Is there some mathematical function/theorem I can use to take the local noise of the curve into account, and output a range/distribution of probable slopes? I would imagine the output being something like a histogram with the most likely slope at the middle and increasingly less-likely slopes off on the sides.

A moving window (with some reasonable window size) is probably hard to beat.  I don't know of any parameter-less solution.

Another possible approach could be to estimate the slope of the last 10% of the data, and compare this to some threshold.  (So, the 1000th data point uses the average of points 900-1000.  The 2000th data point uses the average of points 1800-2000.  And so on.)  This way, if it does flatten out, then if you continue for another 10% longer, you'll reach a point where the last 10% is all flat and the procedure will likely terminate.  This may do 10% more iterations than "necessary", but that might be acceptable given that in return you get a procedure that doesn't require a fixed window size.

However, choosing a threshold might be a bit tricky.  I'm not sure how to do that in a reasonable way.

Given a bunch of data points, you can compute a least-squares fit for the regression line through those points, and find an estimate of the slope of that line.  You can also compute a confidence interval for that slope.  This will give you a range of plausible slopes.


Expected number of comparisons in a merge step? I know that merging two sorted arrays takes worst case n comparisons. However, there will often be cases where one array is depleted before the other, letting us just append the remainder of one array to the combined sorted array. I've also read that merging takes the same amount of comparisons (wrt to n) to any input of size n. How is this represented in the mergesort recurrence relation and time complexity?

I will answer your first question about the expected number of comparisons from a statistics/probability standpoint because I think it's rather interesting and non-obvious. Let's assume the input is random, both arrays to be merged are the same length ($n/2$), and the merging algorithm is the generic step by step compare and insert method.

Let $C(i)$ be the number of ways to merge the two arrays of length $n/2$ in $n/2 + i$ comparisons.

Clearly $C(0) = 2$ because this means we are doing exactly $n/2$ comparisons then appending the rest of one list to the end of the other. If we have two lists $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2, \ldots\}$, then these merges would look like:
$$[a_1, a_2, \ldots, a_{n/2}, b_1, b_2, \ldots, b_{n/2}]$$
or
$$[b_1, b_2, \ldots, b_{n/2}, a_1, a_2, \ldots, a_{n/2}]$$

We then have $C(1)$ is the number of ways we can nest $b_1$ within $[a_1, a_2, \ldots a_{n/2}]$ (and the mirror of this, nesting $a_1$ into $b_{1\ldots n/2}$). This can be expressed similarly to the number of integer solutions to equations. We can insert $b_1$ into $a_{1\ldots n/2}$ in the following locations represented by the symbol $\diamond$:
$$[\diamond a_1 \diamond a_2 \diamond \ldots \diamond a_{n/2 - 1} \diamond
 a_{n/2}]$$
It is important to note that we can not place $b_1$ immediately after $a_{n/2}$ as that will create a redundant count to what we already counted in $C(0)$. So this reduces our number of locations from $n/2$ to $n/2-1$ which we can choose from.

Let $n/2 = k$ for simplicity. We can express $C(i)$ as a combinatorial expression:
$$C(i) = 2\binom{(k-1) + (i + 1) - 1}{(i+1) - 1} = 2\binom{k + i - 1}{i} = \frac{2(k+i - 1)!}{i!(k-1)!}$$

So we now have the total number ($N$) of possible merges is the total number of ways of choosing $n/2$ elements from a set of $n$. This can be seen easily if you imagine a skeleton array of length $n$, we then must select $n/2$ spots in this array to put one of our arrays being merged (and symmetrically the other array would be placed in the holes). We then have:
$$N = \binom{n}{n/2} = \binom{2k}{k}$$
This is again clear to see when we sum the $C(i)$s:
$$\begin{align}
\sum_{i=0}^{k-1} C(i) & = \sum_{i = 0}^{k-1} 2 \binom{k + i - 1}{i}\\[0.5em]
& = 2\binom{2k - 1}{k - 1}\\[0.5em]
& = \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em]
& = \frac{2k}{2k}\cdot \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em]
& = \frac{(2k)!}{k!k!}\\[0.5em]
& = \binom{2k}{k} = \binom{n}{n/2} = N
\end{align}$$

We then can find the probability of $k + i$ comparisons as:
$$\begin{align}
P[X = k + i] & = \frac{C(i)}{N}\\[0.5em]
& = 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}
\end{align}$$
Then it's easy to get the expected value:
$$\begin{align}
E[X] & = \sum_{i = 0}^{k-1} (k + i) \cdot 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}\\[0.5em]
& = \frac{2k^2}{k + 1}\\[0.5em]
& = \frac{n^2}{n + 2} \approx n -2
\end{align}$$
From this it's clear to see that the expected number of comparisons is pretty close to $n - 2$. In fact we can pull up a table to see how they compare:
$$\begin{array}{|r|r|r|}
  \hline n & \lfloor n^2/(n+2) \rceil & n - 2\\
  \hline 2 & 1 & 0\\
  \hline 4 & 3 & 2\\
  \hline 8 & 6 & 6\\
  \hline 16 & 14 & 14\\
  \hline 32 & 30 & 30\\
  \hline 64 & 62 & 62\\
  \hline 128 & 126 & 126\\
  \hline 256 & 254 & 254\\
  \hline 512 & 510 & 510\\
  \hline 1024 & 1022 & 1022\\
  \hline
\end{array}$$
Another visual, here is the probability mass function of $x$ comparisons for merging into an array of size $1024$ (e.g. merging two arrays of size $512$):


Removing duplicates efficiently and with a low memory overhead I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

we have a range of integers $S = \{1, \dots{}, N\}$ with $N$ big (say $2^{40}$)
we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
we then need to store $f[S]$, that is $\{f(x) | x \in S\}$

I have a quite accurate (probabilistic) estimation of what $|f[S]|$ is, and can therefore allocate data structures in advance (say $|f[S]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

a bitset is out of the question because the input set does not fit into memory.
a hash table, but (1) it requires some memory overhead, say 150% of $|f[S]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
a simple array with a binary search tree, but this requires $O(N \log |f[S]|)$ time.
maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (https://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, https://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.

Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$.  For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits.  Try to store $z$ (not $x$!) at location $y$:

When $A[y]=z$ already, do nothing: $x$ is a duplicate.
When $A[y]$ is uninitialized, store $z$ at $A[y]$.
Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists.  You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short.  When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing.  If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$).  This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.


Is the given language decidable for turing machine? I am going through undecidability of TM and found this question

$L=\left \{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \}$

I think it is decidable as number of strings in the language is prime ,i.e , 2,3,5,7,11,13,17,............. It seems to me like it is accepting all the strings.

If it has accepted 17 strings, then it must have accepted 12 strings, 14 strings, 16 strings and so on. Actually i am not getting from where to start.

Can anyone provide legal explaination of what is actually happening here ?

Consider a problem 'A' which is undecidable. If 'A' is reducible to another problem 'B', then problem 'B' is undecidable.

Consider following two statements:

p: Turing machine halting problem is undecidable.
s: A given Turing Machine 'M' reaches a state 'q' on reading input 'w'.

If we can modify statement 'p' in such a way that the answer to 's' will be answer to 'p', then we can say problem 's' ( statement 's' ) is undecidable.

Also note that I will be using a term "Dead Configuration" to mean the Turing machine is in a state from which no further transitions is defined i.e, a Turing machine halts because of a dead configuration.

Modified version of 'p': A Turing machine halts only at state 'q'.

That is, whenever a Turing machine reaches a dead configuration, we will make a transition to 'q'.
Modified version pf 'p' is undecidable, which means it is undecidable that a Turing machine reaches a state 'q' on reading any input.
Hence, problem 's' is also undecidable.

On the same lines statement 's' can be modified to prove that the problem, "Turing machine will accept a string" is undecidable.

Hence, if the problem: "whether a string is accepted by a Turing machine" is undecidable then the problem of counting the number strings in a language will also be undecidable.


Can someone give me an explanation of how dcaches works? So, I'm trying to do a computer architecture assignment and there's a question about dcaches. Here's the question:

  Given a 16 word dcache initially filled with word address 0, 1, 2, …15
  memory data (referenced by the datapath in that order). Below is the next
  sequence of data memory address references given as word addresses.
   1, 18, 2, 3, 4, 20, 5, 21, 33, 34, 1, 4

  a) Assuming the dcache is direct-mapped with one-word blocks, list if each
  reference is a hit or a miss. Show the state of the dcache after the last reference. What is the hit rate for this reference string?

I'm not asking for a solution but would just like to know what is considered a miss or hit and how this is calculated? Also, what would be the difference if the dcache had a two-word blocks instead of 1?

Any help is greatly appreciated.

what is considered a miss or hit and how this is calculated

A hit occurs if the request word is in the cache; if not, we have a cache miss.

It isn't clear how much you understand about hardware caches from the question, but I'll assume you at least know the definition of cache sets and lines.

In a direct-mapped cache, each cache set can hold only one line. Thus, the number of sets is equal to the number of cache lines. Usually, cache lines are many words long (e.g. 64-byte cache lines), but in your example a cache line consists of a single word. Since the cache can hold 16 words (lines), we can deduce that there are 16 cache sets.

Each memory address is mapped to a set. The set holding a memory address is determined by the address's set-index bits. If there are 16 sets, then each address must have $lg 16 = 4$ set-index bits. Let's assume these are the lower-order bits of the address. So, for example, address 7 will uses cache set 7 (because the binary representation of 7 is 00000111).

In this problem, the cache starts full (often referred to as a warm or hot cache). You are given a sequence of memory addresses. Each memory address will be either a hit or a miss, as defined earlier. If the address is a miss, the word at that address must be brought into the cache, and the old value is ejected from the cache.

  Also, what would be the difference if the dcache had a two-word blocks instead of 1?

If the size of a cache line is two words, then you have twice as many values in your cache. It is then possible that a requested word is already in the cache, even if you have never requested that address before. This will happen if you previously addressed a word in the same cache-line as that word.


What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them? Starting with an image, I have taken its fourier transform and then modified it, and finally taken the inverse fourier transform of the modified fourier transform to get my resulting image.  In my result, I get a lot of very small imaginary components in each pixel.  My question is what causes these, and is there some insight into how I can play with a fourier transform in such a way that I won't get these imaginary components once I invert the transform at the end?

The reason this is an issue for me is because although I can simply zero out the imaginary components, or take the magnitude of each complex number as the pixel value and still obtain the resulting image that I desire, once I take the fourier transform of that new image, it does not yield the fourier transform that I used to generate the image previously.  Because the English is getting messy, it's much easier to see in pseudocode:

function fft(input):
   return 2D fourier transform of input 2D array

function ifft(input):
   return 2D inverse fourier transform of input 2D array

function fix(image):
   zero out imaginary component in each pixel of input image (2D array)
   return updated image

// Suppose we have computed an input 2D matrix, and are ready to ifft it to get an image
input = /*...*/
test1 = fft(ifft(input))
test2 = fft(fix(ifft(input)))

While test1 will yield back the matrix (up to floating point errors) input that we started with, the image generated is not a real image.  If we attempt to fix the image, we find that test2 significantly differs from our input.

What I would like to do is understand how to modify the fourier transform in such a way that I can achieve my original input after going through the process of taking the inverse fourier transform, storing that as a valid image, and then taking the fourier transform of that image.

The Fourier Transform is the change of basis, the discrete signal from image, which is finite, gets transformed into sines. The transformation itself is prone to rounding, because in frequency domain there is no such thing as finite impulse or rectangular for that matter (see Gibbs effect), there will be some approximation.

The complex numbers represent the transformed signal, where amplitude is the length (magnitude) of the number while phase is the angle. Cutting off the imaginary part destroys the phase and changes the amplitude so image looks like a noise. There is no way to avoid Imaginary part (unless the image itself is fully even-symmetric then Im is zero).

The small components in Imaginary part cannot be avoided, extending precision will help a lot, but please keep in mind that some inputs cannot be preserved and some loss will occur. Using only magnitude and discarding the phase is equivalent to saving pixel intensities and discarding the location.

If you want to store FFT result as the valid image, the best idea is to produce two images, for Real and Imaginary part or another pair using Phase and Magnitude. Another idea is to save separate channels, which works for grayscale image but is not sn option for grayscale. This operation is very lossy, some fixed unsigned integer (for example 8bit) is converted into complex pair, both floating point, so using any standard storage option will lose crucial data. Probably to make it work the log transform would be need.


Convert HSV to RGB colors HSV colors are composed of a triple of numbers: hue $\in [0, 360)$ (in degrees), saturation $\in [0, 1]$ and value or brightness $\in [0, 1]$. RGB colors instead are more well-known and are also composed of a triple of numbers all of them in the range $[0, 1]$ or in a byte $[0, 255]$.

I was trying to implement an algorithm that converts HSV colors to the corresponding RGB ones, and I managed to do it based on the following algorithm provided by Wikipedia. (I'm reporting the whole related text).

  $C = V \times S$

  \begin{align}
 H^\prime &= \frac{H}{60^\circ} \\
 X    &= C (1 - |H^\prime \;\bmod 2 - 1|)
\end{align}

   ($R_1$, $G_1$, $B_1$) =
    \begin{cases}
   (0, 0, 0) &\mbox{if } H \mbox{ is undefined} \\
   (C, X, 0) &\mbox{if } 0 \leq H^\prime < 1 \\
   (X, C, 0) &\mbox{if } 1 \leq H^\prime < 2 \\
   (0, C, X) &\mbox{if } 2 \leq H^\prime < 3 \\
   (0, X, C) &\mbox{if } 3 \leq H^\prime < 4 \\
   (X, 0, C) &\mbox{if } 4 \leq H^\prime < 5 \\
   (C, 0, X) &\mbox{if } 5 \leq H^\prime < 6
  \end{cases}

  Finally, we can find $R$, $G$, and $B$ by adding the same amount to each component, to match value

  \begin{align}
 &m = V - C \\
 &(R, G, B) = (R_1 + m, G_1 + m, B_1 + m)
\end{align}

where $H$ is the hue, $V$ is the value, $S$ is the saturation, $C$ is what Wikipedia calls the chroma and $R, G, B$ are correspondingly the values of red, green and blue.

Before wanting to find a way to convert HSV colors to RGB Colors, I had already a formula to convert RGB colors to HSV, which I wanted to manipulate to obtain a inverse formula, but I didn't manage to do it.

Here's a picture:

I could show you my attempts, but they are not useful.

Question

How is the formula (provided by Wikipedia) to convert a HSV to RGB colors derived from the formula in the picture above to convert RGB to HSV colors?

I'm asking this question here because I'm looking for a mathematical manipulation of one formula to arrive at another. I'm also asking this question because I think it could be interesting also for others. If you think this question should be moved to another stackexchange's website, feel free to migrate it or just tell me and I will post it where you indicate me.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 If $H' - 0 < 0$

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

 Otherwise if $H' - 0 >= 0$

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

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

 If $H' - 2 < 0$

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

 Otherwise if $H' - 2 >= 0$

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

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

 If $H' - 4 < 0$

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

 Otherwise if $H' - 4 >= 0$

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


Is Python a context-free language? From Wikipedia: Off-side_rule#Implementation, there is a statement:

  ...This requires that the lexer hold state, namely the current
  indentation level, and thus can detect changes in indentation when
  this changes, and thus the lexical grammar is not context-free –
  INDENT/DEDENT depend on the contextual information of previous
  indentation level.

I'm a bit confused. Some lexical grammars of Python is not context-free but INDENT/DEDENT themselves can be expressed in CFG. So lastly, Python is a context-free language or not?

Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces and store that info in a table for later use. This is similar to something like trying to write a parser for the language $a^nb^{2n}c^n$, where you must keep track of value of $n$.

A simple example of adding additional power to a lexer is removing redundant whitespace symbols (space/tabs/newlines) or removing comments which has no meaning for the parser (parsing a CFL).

As another example, roughly it can be described as following. Assume a grammar $a^nb^mc^k$ which is clearly CFG.  You use BISON/YACC like tools to generate a parser for this grammar. Then you can introduce an additional rule like number of $a$s must be equal to the number of $c$ which makes the language non CF. So you just add extra logic (manually coding) to your parser to handle that rule by means of, say, annotated trees. Your original language is still context free but extra piece of code you added manually allows it to accept non CF subset of the original language.

I don't think that such parsers are generated automatically by compiler tools (at least I don't know) and so that ("non context free") part must be coded manually.


how to prove the periodity of an LFSR everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness?
I've tried o prove it like that:
given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then:
$$
{h(x) \over c(x)}=G(x)= \sum^\infty_{k=0}a_kx^k=\sum^{\pi -1}_{k=0}a_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}_{k=0}a_kx^k \over 1-x^\pi}
$$
and I'm not sure where to go from here

Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x_0$, the state after $t$ steps is $x_t \equiv x_0 x^t \pmod{c(x)}$. In particular, $x_t = x_0$ if $x_0 (x^t-1) \equiv 0 \pmod{c(x)}$.


Finding a language for a NFSA I'm having a bit of trouble determining what language the following non-deterministic finite state automaton accepts.

Assuming the alphabet of this machine is ${a, b}$, I deduced that this automaton would accept words of the following characteristic: a word $w$ would be accepted if $w$ had zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s and $b$'s.

Is there a more clear and concise explanation of what sorts of words are accepted by this automaton or would my explanation be suffice? Any suggestions would be appreciated!

You have correctly identified your alphabet, but your verbal description is, indeed,complex.  Your NSA would accept any string with at least 2 as.

There are many ways to describe NSAs. A regular expression or a regular grammar could be appropriate here. If this is for class, I would ask your professor what format he or she prefers.


Proving a certain hypothesis class on a given distribution is not learnable I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to solve it:

Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge \forall \, 1\leq j \leq m, \,x_j(i)=y_j)>\delta$
Original phrasing:
Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Define the hypothesis class $\mathcal H_N = \{h_i: \mathcal X_N \to \mathcal Y \mid 1 \leq i \leq N \}$, where $h_i(x) = x(i)$.
Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge L_S(h)=0)>\delta$

So a few things:
$S$ is obtained by randomly and independently drawing $(x,y)$ pairs from $\mathcal D_N$,
$L_D(i) = \mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y)$,
x(i) - is the i'th coordinate of the $N$ dimensional vector x.
What I tried to do was:
First of all, fix an $i\in \{1,...,N\}$ and consider $\mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y) = 2\frac{2^{N-1}}{2^{N+1}} = \frac{1}{2} > \epsilon $ for any $\epsilon \in (0,\frac{1}{2})$ so the first requirement is rather redundant.
Second, independently drawing a sequence $S$ of $m$ pairs (with repetition) such that every pair has $x(i)=y$ is with probability $\mathbb P_{S\sim \mathcal D^m} (\forall \, 1\leq j \leq m : x_j(i)=y_j) = \prod_{j=1}^m \mathbb P_{(x,y)\sim \mathcal D} (x_j(i)=y_j) = \frac{1}{2^m}$.
Now that's for a single fixed $i\in [N]$, trying to lower bound the probability of an existence of such an $i$ could either be done by just ignoring the rest and saying $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j)\geq \frac{1}{2^m} > \delta$
But that is a very gross estimation so I calculated the probability exactly using inclusion-exclusion principle like so:
let $1 \leq i_1 < i_2 <... < i_k \leq N\,$ then $\mathbb P_{S\sim \mathcal D^m} (\bigwedge_{t=1}^k \{ \forall \, 1\leq j \leq m, \,x_j(i_t)=y_j\}) = (\prod_{t=1}^k \mathbb P_{S\sim \mathcal D^m} (x(i)=y))^m = \frac{1}{2^{km}}$
finally we get:
$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j) =
 \sum_{i=1}^N (-1)^{i-1}{{N}\choose{i}}(\frac{1}{2^m})^i$
And now my goal is to lower bound this by $\delta$ and using some closed form of this expression.
My question is first, is my analysis even correct and second, how would you proceed?
Thanks in advance!

Since each $x$ is uniformly chosen, the probability of having a certain value at the $i$'th spot is independent of the probability of finding some other certain value in the $j$'th spot. You showed this already, but notice it means that you dont need the inclusion-exclusion principle, and instead the probability will just be the probability of the complement, which is $1-\frac{1}{2^{km}}$. You can now easily choose $k$ such that this probability would be bigger than $\delta$


Coin Change Problem(Greedy Algorithm) In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?

Example- $(1,3,4)$ are denominations of coin.
If I want to pay $Rs.6$ then the smallest coin set would be $(3,3)$.
This solution set cannot be found by greedy Algorithm because it does not satisfy $(\frac{4}{3} > \frac{3}{1})$.

For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to give us 22 cents. Then there is nowhere left to go, we cant possibly get to 23 from here. We do have a solution though with $(0,4,1)$


Is there an algorithm or shortcut for continually updating and summing sub-sections of arrays? Let's say I have an NxN array if integers. I want to continually update it, but also continually query for the sum of an arbitrary sub-section. So example would be as follows:
We start with a 3x3 array of all 0s.
Operations:

update 1,1 to 3
update 1,2 to 1
update 0,0 to 2
update 2,2 to 6
print sub-section starting at 1,1 going to 2,2 (should print 10)
more updates...
more queries...

The array looks like this at the time of first query:
2 0 0
0 3 0
0 1 6

I want to do this for much larger arrays, and much more queries in a reasonable amount of time. I believe less than O(N^2) per query is possible. Any ideas?
EDIT: I'm asking this because Hackerrank has several of these types of questions and I was banging my head against a wall trying to come up with a strategy.

The data structures you're looking for are quad trees (for linear time queries, logarithmic time updates, quadratic space) or the more complicated 2d interval trees (for logarithmic time queries, logarithmic time updates, $O(N^2 \log N)$ space).

I suspect you are trying to solve competitive programming problem, if so please state it in your question.


CFG problem solved with PDA - looking for alternative solution I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$
and what I have done so far is to make PDA which simply does the following:

If on the stream there is "a" -> push $\xi$ in the stack
If on the stream there is "b" and the stack is empty -> push $\zeta$ in the stack
If on the stream there is "b" and there is $\xi$ in the stack then while there are $\xi$ in the stack read b from the stream and pop $\xi$.
If there is "b" on the stream and no $\xi$ left in the stack continue reading "b" and push $\zeta$.

And so on counting the a,b,c and d's which I get, but the problem is that my transition function is getting really big and I'm gonna have some troubles to convert it into CFG, so there must be straightforward way to do it and seems I can't find it.

Can somebody help me, please?

First assume $n\ge m$.
Then we can take $i=n-m$ and we have $i+k =l$, so strings are of the form

$ a^i a^m b^m c^k d^k d^i$.

You can do a CFG for that.

Then consider $n\le m$.


Proving whether an input sequence is in a given RE language I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this statement.

The fundamental doubt is that the statement itself is well-stated. If I'm using the term 'execution' to describe the act of matching the rules one input element by one, is this statement valid?
Is this statement (deciding whether an input sequence is in a language is impossible without an execution) not exactly limited to RE? In other words, I wonder this statement also holds even for the languages in other classes.
I'm not even sure how I can search for this statement and confirm from the external source.

(By RE, here I indicate the recursively enumerable languages, not the regular expression)

A language is recursively enumerable if there exists a Turing machine that:

halts and says "yes" whenever its input is in the language;
either halts and says "no" or just doesn't halt whenever its input is not in the language.

The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given the code of a Turing machine which accepts some language) and a string, can determine whether the string is in the language or not. In general, all you can do is run the Turing machine and see if it accepts its input. However, if it seems to be taking a long time to run then, in general, there's no way of figuring out if it's in an infinite loop, so even this doesn't actually work.

However, that doesn't mean that you can never tell whether a particular machine will have certain behaviour.  For example, it's easy to tell that the machine

IF the first character of the input is 0 THEN accept
ELSE [do something complicated]

will accept any string that begins with $0$.  More sophisticated analytic techniques will allow you to prove that more complicated machines do or do not accept certain inputs.  However, what the lack of a general algorithm means is that, whatever analytic techniques you develop, there will be some machines and some inputs (in fact, infinitely many of them) where your techniques fail. In those cases, your only options are to develop even more advanced techniques (which still won't work in all cases) or to give up and just run the machine.


Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $ Is there any difference between saying
$ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $
with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $?
I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$
my understanding is that there is no difference between them and for $w = abaaabbb$ we have $ w \in L_1$ and $w \in L_2$ . but I have a feeling that maybe $w \notin L_1$, because it doesn't have the same $n$ for different $a^n b^n$.
Also, does the same apply for Kleene star $*$ too? for example if we have  $ L_3 = \{(a^n b^n)^m \mid n \ge 1, m \ge 0\} $ and $ L_4 = \{a^n b^n \mid n \ge 1\}^* $, Are $L_3$ and $L_4$ equal?

Indeed, $abaaabbb \notin L_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.
The language $L_2$ is the Kleene closure of $\{a^nb^n \mid n\ge1\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do not have to stick with the same one each time, like in $L_1$. Hence $L_2$ contains $abaaabbb$.
As for your original version of the question (now edited) it contained the notation $\{(a^nb^n)^+ \mid n\ge1\}$. I would not denote a language that way. The Kleene plus is a language operator, which takes a language (set of strings), and turns it into a language. By writing $\{(a^nb^n)^+ \mid n\ge1\}$ you get the set $(a^nb^n)^+$ within the set brackets, which can be called a "type error".


Why shift means push terminal symbol and state into the stack? Why not push only state? Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal symbol are deleted and the terminal symbol will never be used.

Why not push into the stack only state?

(English is not my native language, so please be kind to my mistakes)

You are talking about the typical description of LR parsing. And you are completely right, the "state" (if you look closely, it is the state of the DFA that recognizes left hand sides of productions when processing the current stack's contents) encodes all information needed. Adding the symbol is redundant. As far as I can tell, it is usually added to clarify what is going on (just a list of state numbers would be completely opaque).


Recurrence with Minimum I need to solve the following recurrece:

$T(n,m)=\begin{cases}
1, & m\leq 2(n-1)!\\
\min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else}
\end{cases}$

Note: in the first line beneath the $\min$ we have $a,b$ and in the next line it's $a\cdot b$.

I find it difficult to solve this recurrence as it contains $\min$, so I tried to calculate the minimum, but I didn't know how to prove it (I believe that the minimum occurs at $a=b=\sqrt{(n-1)!}$, but I don't know how to prove it...). So I am stuck with this.

Any help would be highly appreciated!

Edit:

Experiments show that

$T(n,m)=\begin{cases}1 & f(n,m)\leq 0\\ 3+2\Big\lfloor\frac {f(n,m)-1}{(n-1)!}\Big\rfloor & \text{else}\end{cases}$

for $f(n,m)=m-2(n-1)!$, and considering the $\min$ of an empty set to be infinity.

Let us prove that for $m \geq 1$,
$$
T(n,m) = \max(1, 2\lfloor \tfrac{m-1}{(n-1)!} \rfloor - 1).
$$
(This is the same as your formula.)

If $m \leq 2(n-1)!$ then by definition $T(n,m) = 1$, and indeed $\lfloor \tfrac{m-1}{(n-1)!} \rfloor \leq 1$, showing that our formula also gives the value $1$. If $m > 2(n-1)!$, then
$$
T(n,m) = \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n-1,a) + T(n-1,b) + T(n-ab).
$$
Since $ab \leq (n-1)!$ also $a,b \leq (n-1)!$, and so $T(n-1,a) = T(n-1,b) = 1$. Therefore
$$
T(n,m) = 2 + \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n,m-ab) = 2 + \min_{1 \leq c \leq (n-1)!} T(n,m-c).
$$
We can prove inductively that $T(n,m)$ is monotone nondecreasing, and so
$$
T(n,m) = 2 + T(n,m-(n-1)!).
$$
From here it's not too hard to prove the formula by induction.


while loop for bitwise conversion program int counter(char c){
    int count = 0;
    while (c!=0){
       if((c & 1) !=0)
         count++;
       c = c >> 1;
}
}

I am trying to understand a program that counts the number of 1s in the binary representation of the input character. While I understand the & part and the count part, I don't get why we're checking for c!=0 in the while loop. I know each character is 8 bits. For instance, if the input character is "2" then the binary representation is 10. The count will be 1. So we start by checking the first binary number "1". Then we shift by 1 and it becomes 01? So then do we check 1 again? Or do we check 0? But if we check 0 then does the while loop not run at all?
An example of the steps would be really helpful.

The & operator is a bitwise "AND". Since the binary representation of 1 consists only of a 1 on the least significant bit, the operation c & 1 checks if $c$ contains a 1 on the least significant bit. Another way to say it is that c & 1 is the remainder of $c$ modulo 2, that is 0 if $c$ is even and 1 if $c$ is odd.
The >> is a logical shift right, that is the deletion of the least significant bit.
For example, if $c = 26 = (11010)_2$, the steps are:

c & 1 = 0 so count is not modified. $c$ becomes $1101$;
c & 1 = 1 so count is incremented. $c$ becomes $110$;
c & 1 = 0 so count is not modified. $c$ becomes $11$;
c & 1 = 1 so count is incremented. $c$ becomes $1$;
c & 1 = 1 so count is incremented. $c$ becomes $0$.
c != 0 is not true so the algorithm stops. count was incremented thrice, and three is indeed the number of 1's in the binary representation of $c$.


What language can be created from a regular expression with nulls? The usual regular expressions I have seen are those with non-null inputs (e.g. $a$, $b$). A few days ago, I saw, for the first time, a regular expression that has a null ($∅$) in it.

$$ r_{1}= (cε + d∅)^{*}, Σ = \{c,d\} $$

This confused me since I do not know how a language would be created from $r_{1}$.

What would a language created from a regular expression be like if that regular expression has a null (like $r_{1}$ above)?

Additionally, what would a language be like if the regular expression from which the language is created from contains $ε$ (for example, like $r_{2}=(aε)(bε)ε, Σ = \{a, b\}$, and again, like $r_{1}$ above)?

The regular expression $\emptyset$ matches nothing at all: not the empty string, not any non-empty string.

Any concatenation with $\emptyset$ also matches nothing: a string would only match $d\emptyset$ if it could be divided into some part that matches $d$ and some part that matches $\emptyset$, but no such part exists.  So $d\emptyset$ is the same thing as $\emptyset$: it matches nothing at all.

An alternation ("or") of something with $\emptyset$ has no effect: $c\epsilon+\emptyset$ means "anything that matches $c\epsilon$ or matches $\emptyset$" and that's just "anything that matches $c\epsilon$."

So $c\epsilon+d\emptyset$ is the same thing as $c\epsilon$ which, in turn, is the same thing as $c$.  The regular expression you quote is equivalent to the simple $c^*$.

Conceptually, $\emptyset$ plays a similar role to zero in addition and multiplication. Adding zero to anything doesn't change it, just as alternation of a regular expression with $\emptyset$ doesn't change it. Multiplying anything by zero makes it equal to zero, just as concatenation of any regular expression with $\emptyset$ turns it into $\emptyset$.

$\emptyset$ might seem rather pointless as a regular expression. It's needed because, without it, the empty language (the one with no strings at all in it, i.e., the set $\emptyset$) wouldn't be regular. To see this, it's not hard to prove by induction that every regular expression that doesn't contain the character $\emptyset$ must match at least one string. However, we want the empty language to be regular, because it's accepted by an automaton – in fact, by any automaton with no accepting states.


BCNF Decomposition: Confusion regarding given answer I encountered the following question:

Given a relation R(A, B, C, D) with the following functional dependencies:
A -> B, C -> D, B -> C.

The BCNF Decomposition of R is:

A) {(A,B), (C,D), (B,C)}
B) {(A,B), (C,D), (A,C)}
C) {(B,C), (A,D), (A,B)}
D) All of the above

According to my understanding the solution should be D) ALL of the above.
This is because for each schema, the condition for BCNF holds as given by this link: http://www.cs.sfu.ca/CourseCentral/354/jpei/slides/UsingBCNF-3NF.pdf
      (Page 18)

The other two do not preserve some dependencies but in BCNF decomposition it may happen that the dependencies are not preserved.

However, the answer is given as (A). Please can someone explain? Thanks.

For the relation R(A, B, C, D) with the following functional dependencies:

1.A -> B
2.C -> D
3.B -> C

candidate key = A

The correct way to decompose a relation such that it satisfies BCNF property is following.

The FD 2 and 3 are violating the BCNF property(LHS should be key) i.e to convert the relation into BCNF it is needed to be decomposed.

To decompose this find the FD which violates the BCNF property in our case FD 2 and 3 violates.

Seprate out this FD into a different relation i.e our new relation is

R1 = (A,B) with FD A-> B
R2 = (B,C,D) with FD B->C and C->D

Again for the R2 the key is B and FD C->D violates the BCNF property we further split R2 into R12 and R22

R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

Now the final obtained relation after decomposition is

R1 = (A,B) with FD A-> B
R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

The above relations are the only decomposition of R that satisfies BCNF property.

For more insights refer this http://www.cs.toronto.edu/~faye/343/f07/lectures/wk12/moreBCNF.pdf


Reduction from SUBSET-SUM to 0-1-INT-PROG The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.
I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.
My attempt:
Given an instance of SUBSET-SUM $<\{a_1, a_2, \cdots, a_n\}, k>$ we construct an instance of 0-1-INT-PROG $<[a_1, a_2, \cdots, a_n], [k]>$.
Claim: $<\{a_1, a_2, \cdots, a_n\}, k> \in $ SUBSET_SUM if and only if $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.
proof of forward direction. When there exists a subset $S' \subseteq S$ whose sum is $k$, for each $a_i \in S'$, let $x_i = 1$. If $x_i \not \in S'$, then $x_i = 0$. Then $x$ is an $n$-vector which achieves $[a_1, a_2, \cdots, a_n] \cdot x = k$. So $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.
Question:
When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $x$ vector with $[a_1, a_2, \cdots, a_n] \cdot x \leq k$, does not imply that there exists a subset $S' \subseteq S$ whose sum is $k$, because of the less than or equals to.
So how can I approach the backwards direction?

Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\{a_1, a_2, \dots, a_n\}$. Construct an $0$-$1$-integer program with $n$ binary variables $x_1, \dots, x_n$ and the following constraints:
$$
\begin{align}
a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\
-a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k
\end{align}
$$
Or, in matrix form:
$A =
\begin{bmatrix}
a_1 & a_2 & \dots & a_n \\
-a_1 & -a_2 & \dots & -a_n
\end{bmatrix}$ and $b=\begin{bmatrix} k \\ -k\end{bmatrix}$.
If you have a solution $S' \subseteq S$ to the subset sum instance, then you can pick $x$ as the characteristic vector of $S'$ to satisfy the constraints (as you correctly point out in your question). I.e., set $x_i = 1$ if and only if $a_i \in S'$ so that $Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$.
On the other hand, if $Ax \le b$ then the first constraint is $a_1 + a_2 + \dots + a_n \le k$ and second constraint implies $a_1 + a_2 + \dots + a_n \ge k$. Then, we necessarily have $a_1 + a_2 + \dots + a_n = k$, showing that $S' = \{ a_i \mid x_i = 1\}$ is a solution to the subset sum instance.


Getting speed difference between signal comparison using Dynamic Time Warping I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed

But is there a possible way to find the speed difference between the two signals being compared?

To clarify my question.
I am working on a project to find similarity between two motions.
The data being compared is in the form of Quaternion. By using DTW I was able to find the similarity/ dis-similarity between these motion signals, However I would like to know is there a way to find if one motion signal is slower/faster than the other.
Ex: both motions are actually similar, but one of the motion is slower than the other

There is no single "speed difference".  The way DTW works is that it checks whether you can find a match by slowing up and/or speeding up one of the signals.

For instance, suppose you want to match signal X to signal Y, which last 3 minutes.  It's possible that the best match might involve speeding up signal Y for the first minute, slowing it down for the second minute, and leaving its speed unchanged for the third minute.  Thus, there's no one speed, no one speed difference, and no simple answer to whether Y is faster than X or not.  Rather, the answer is: "faster in parts, slower in others".

Once you find the best match using DTW, you can easily recover in which parts Y was faster than X, and in which parts Y was slower than X.  I encourage you to do a bit more reading about how DTW works -- it'll probably all become clear as you understand the gist of the idea.


If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory? Let's say we are working with a system that has 40 physical address bits. The total physical address space (assuming byte-addressable memory) is $2^{40}$ bytes, or 1 TiB. And if virtual addresses are 48 bits in length, that means there are more addresses available to virtual memory than there are locations in physical memory.

This makes sense to me, because the "excess" addresses could refer to hard disk locations as well. However, what I don't understand is how the translation between virtual and physical addresses occurs. I assume there is a mapping stored somewhere which links VAS locations to the physical locations. If there are more virtual address locations than physical locations, how can all of these mappings possibly be stored in memory? At minimum you would need 48 bits to store each virtual address, and then another 40 to store the physical location it maps to. So obviously you cannot just store a 1:1 mapping of each virtual address to its physical counterpart, as mapping every location would take more memory than physical memory itself.

What exactly am I missing here?

The trick to making this work is "paging."  When bringing data from a hard disk into physical memory, you don't just bring a few bytes.  You bring an entire page.  4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper.  If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages).  That's much easier!  The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal.  In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.