Cancellation of inequalities in floating point arithmetic In finite precision floating point arithmetic the associative property of addition is not satisfied. This is, it is not always the case that $$(a+b)+c=a+(b+c)$$
Even $a=(a+b)-b$ is not always true.
To prove that $x+y<z$ is equivalent to $x<z-y$ with real numbers we can add $-y$ on both sides of $x+y<z$ to get $(x+y)-y<z-y$ and then from this $x=x+(y-y)<z-y$. But I can't repeat the last step for floating point.

Question 1: Are the inequalities $x+y<z$ and $x<z-y$ equivalent in finite precision floating point arithmetic?

Question 2: Are the inequalities $x+y\leq z$ and $x\leq z-y$ equivalent in finite precision floating point arithmetic?

I was too hasty and updated without checking properly. What I really indented to ask is if the breaking of the equivalence could be as drastic as:

Question 3: Could we have $x+y<z$ and $x>z-y$?

Possibly there are already answers below for this. If so, I will check them when I get a chance and select the answer.

Motivation: There is that interview problem that given an ordered array of numbers and a threshold it asks for the number of pairs of numbers of the array which sum is not larger than the threshold. Possible solutions aside, I wanted to understand the particular point of the dangers of switching between testing $x+y<z$ (and also $\leq$ depending on which variant of the problem is presented) and testing $x<z-y$ (or $\leq$).

Consider the case that x and y hold the largest representable value for the current type, and z is positive infinity. By the rules of floating point arithmetics, x + y is now infinity, which isn't less than infinity. On the other hand, z - y is also infinity, which the largest representable value is less than.
Another example would be when x is very small negative, and y = z and much larger in magnitude than x. Then x + y = y = z, but z - y = 0, which is larger than x.
The examples work for your second question as well if you flip the signs of all numbers - !(l > r) is nearly equivalent to l <= r. NaNs break the equivalence, but those aren't useful as examples to your question anyways.


For what data structures is jump search practically useful? Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long backwards steps, guarantees only a single backwards step); thus, it may be preferable to binary search if reverse traversal is significantly more expensive than forward traversal.

Now, it's not hard to contrive situations in which that is the case--say, a skip-list which is doubly-linked at the lowest level (so that reverse traversal is possible) but singly-linked for every skip-link (so reverse traversal isn't fast). But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

Any context in which data is stored on a physical medium that allows forward jumping quicker than backwards jumping is a candidate. Just think of an ordinary hard drive. Its disk spins in a specific direction, making a forward jump much quicker than a backwards jump. To jump one unit backwards you need the disk to complete (nearly) a full rotation whereas jumping one unit forwards is near-instantaneous. Tape is another example, though here it is mostly the change of direction that is costly rather than backwards jumping specifically. For data stored in RAM, a CPU architecture might be specifically optimized for forward search rather than backward search (in principle, caching and branch prediction might cause differences in the speed of forward and backwards jumping).


Does data entropy depend on the arrangement of the characters in a file? From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing 256 different symbols and we made a bigger file consisting of many copies of that file, And because the small file has the maximum entropy a file of its size can have, the big file will also have that high entropy (because all characters have the same probability). Although that file has high entropy it still can be compressed to a very smaller size. What did I misunderstand here?

Entropy is a property of the source of the data, i.e., of the distribution that the data is drawn from -- not a property of the particular file.  You can't calculate the entropy given a single file.  Instead, you need to know the distribution that file came from.  Or, to put it another way, the entropy is a measure of the process used to generate the particular file, not a measure of one particular file you happened to get from that process; and observing one  output from that process isn't enough to let you calculate the entropy of the process.  So, the question isn't well-formed.

You might be thinking of forming the empirical distribution of characters, then assuming the file came from a memoryless iid source (where each character was drawn independently according to that distribution), and then calculating the entropy under that assumption.  But that assumption doesn't hold for your bigger file, so this isn't a valid way of calculating the actual entropy of the process that was used to generate the bigger file.

To learn more: How to practically measure entropy of a file?, https://en.wikipedia.org/wiki/Entropy_(information_theory).


Is stack based memory allocation memory allocated at run time or compile time? In stack-based memory allocation: is memory allocated at compile time? If so, then how can we allocate space for, say, n number of recursive calls made during the execution of the program?

The amount of stack space allocated to a process (or a thread, if you are talking about multithreading) is decided at run time, when it starts - usually by the system, which just allocates a fixed amount without regard to what the program might actually need: "allocate a megabyte and keep your fingers crossed". Alternatively, when creating a thread within a program, it is sometimes (depending on the system) possible for the programmer to specify the size of the stack required by the thread - but this, too, is done before knowing what the thread's real requirements might be.

With virtual memory, of course, what is really allocated is address space rather than actual memory, so in principle one could just increase the address space allocated to each thread and cross one's fingers a little less. But the same point remains: a fixed limit is being imposed, in advance, without knowing what is actually going to be needed.

Ultimately no reliable computer system can have both unlimited recursion and stack-based storage. Mainframes such as the IBM 360 did not use stacks for return addresses or for local storage. There are "stackless" implementations of various programming languages - any programming language could be implemented stacklessly if people really wanted to do it.

This Stack Exchange answer goes into much greater detail, more rigorously.


Number of possible sequence partitioning Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) so that any sub-sequence starts and ends with a 1, and can contain an arbitrary number of 0s?

For example: Given the sequence 1 0 1 1 0 1 there are only 3 ways of partitioning the sequence:

1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

I am pretty sure the solution implies dynamic programming, since the solution requires a fast execution time (< 1 second).

The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^*1$. Other variants can be solved in a similar way.

Suppose that the original sequence is $a_1,\ldots,a_n$. Let $b(i,x)$ denote the number of ways to partition $a_1,\ldots,a_i$ into any number of subsequences of the form $10^*1$ and $x$ subsequences of the form $10^*$ (open subsequences).

Initially $b(0,0) = 1$ and $b(0,x) = 0$ for $x > 0$. Let us now consider how to calculate $b(i+1,\cdot)$ given $b(i,\cdot)$. There are two possibilities to consider:

If $a_{i+1} = 0$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ by attaching $a_{i+1}$ to any of the open subsequences. Thus $b(i+1,x) = xb(i,x)$ in this case.
If $a_{i+1} = 1$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ in one of two ways: either it "closes" an open subsequences, or it forms a new open subsequences. Thus $b(i+1,x) = (x+1)b(i,x+1) + b(i,x-1)$.

The total number of partitions is then $b(n,0)$. Since $0 \leq x \leq n$, we can compute $b(n,0)$ in time $O(n^2)$ using dynamic programming.

As an illustration, here is a run of the algorithm on the sequence $1,0,1,1,0,1$. The columns correspond to $i$, and the rows to $x$:

$$
\begin{array}{c|cccccc}
x/i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
0 & 1 & 0 & 0 & 1 & 0 & 0 & 3 \\
1 & 0 & 1 & 1 & 0 & 3 & 3 & 0 \\
2 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\
3 & 0 & 0 & 0 & 0 & 1 & 3 & 0 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 3
\end{array}
$$


Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive? After removing multi-sets and sets that have elements that don't exist in $S$.

$S$ = $[9,6,7,4,5,1,8]$

$C$ =$[[9,6,7],[4,5],[1,8]]$

Transform the values in $C$ of the shared index values with $S$. (This must be done before touching $S$)

$C$ = $[[1,2,3],[4,5],[6,7]]$

And do the same for $S$

$S$ = $[1,2,3,4,5,6,7]$

Square each $x$ integer in both $S$ and $C$

$f(x)$ = $x^2$, $x ∈ S$ then $C$

$S$ = $[1, 4, 9, 16, 25, 36, 49]$

$C$ = $[[1,4,9],[16,25],[36,49]]$

Then remove all sets with repeating sums to prevent false positives. This means no $[1],[1]s...$ that could be used, to sum up to the total sum of $S$, This also means $[1,4,9]$ or $[4,9,1]$. (leave one though!)

After the transformation is complete use subset-sum solver and define total-sum as $140$ (total-sum of $s$)
Define list of integers as a summed up set of $C$ = $[[14],[41],[85]]$
Run Algorithm and get the solution

Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $4^2=2^2+2^2+2^2+2^2$. This is enough to construct a counterexample.

Let $S=\{1,2,3,4,5,6,7\}$ and $C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$.

There is no exact cover (the only way to get $4$ is to take $\{1,3,4,5,6,7\}$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.


algorithm with $f(n) = log^2(n)$ I have to write an algorithm that exactly reflects this recurrence:
$$
T(n)=\begin{cases}
Θ(1)\;\;\;\;n \leq 1\\
2T(n/2)+log^2(n)\;\;\;\;n >1
\end{cases}
$$
I have tried this way:

//the array starts from 1
    mergesort(A[], b, e)
    {
       if(b < e)
       {
          p = (b+e)/2;
          mergesort(A, b, p);
          mergesort(A, p+1, e);
          for(i = 1; i <= e; i = i*2)
             for(j = 1; j <= e; j = j*2)
                puts("");
       }
    }

does the algorithm respect the recurrence?

EDIT:

could a solution be?

//I have only changed the two fors
            mergesort(A[], b, e)
            {
               if(b < e)
               {
                  p = (b+e)/2;
                  mergesort(A, b, p);
                  mergesort(A, p+1, e);
                  for(i = 1; i <= e-b; i = i*2)
                     for(j = 1; j <= e-b; j = j*2)
                        puts("");
               }
            }

Your first algorithm as written cannot be correct since it has a time complexity of at least $\Omega(n \log^2 n)$ and the solution to your recurrence equation is $T(n)=\Theta(n)$. To see this notice that at least half of the $\Theta(n)$ leaves of the recursion tree requires time $\Theta(\log^2 n)$ to execute the two nested for loops at the end.

Your second algorithm is correct but it is overcomplicated and has a misleading name.

Assuming that $n$ denotes the value of the input (and not its size), that arithmetic operations require constant time, and that / denotes integer division, a simple algorithm is:

Input: a positive integer n.

f(n):
   if(n==0)
      return;

   f(n/2);
   f(n/2);

   for(i=1; i<x; i=i*2)
      for(j=1; j<x; j=j*2)
         no-op;


What is the complexity of deciding if the intersection of a regular language and a context free language is empty? Let's say we have a context free language, the CFG that produces it.

And then we have a DFA for a regular language.

If the intersection is empty is decidable, but how and how efficiently?

And if you could be so kind, please explain the best known algorithm as simple as you can?

The answer depends on how the two languages are given to you; I will assume that the context-free language is given as a CFG, and that the regular language is given as a DFA/NFA. Beigel and Gasarch show how to compute a CFG for the intersection in polynomial time. You can then check whether the resulting language is empty using grammar simplification (described in any decent textbook).


Difference between deterministic and nondeterministic universal turing machine It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a deterministic UTM can simulate another deterministic TM with running time $t(n)$ in time $ t(n)\log(t(n))$.

My question is: why is there a $\log(t(n))$ slowdown in the simulation of a deterministic TM by a UTM, as opposed to a constant factor slowdown in the nondeterministic case?

Please refer to the answer in the similar question, "Why is simulation by non deterministic Turing machine faster than a deterministic one?".

Basically, in the non-deterministic universal Turing machine we guess the contents of the tape and check if the guess is correct later on. This allows us to save time going to and fro in the work tape.


Can subtracting o(1) from the parameter of a function change its Θ-class? I would like to know if it is possible that two functions $f(n), g(n)$ can exist such that both of the following conditions are met:

$g(n) = o(1)$
$f(n-g(n)) \neq \Theta (f(n))$

I though I found $1/n$ and $1/n^2$ but I think I got it all wrong.

Is it even possible?!

Let $g(n) = 1/n$ and define
$$ f(n) = \begin{cases} n & \text{if $n$ is an integer}, \\ \log \lceil n \rceil & \text{otherwise}. \end{cases} $$
For an integer $n>1$, $f(n) = n$ while $f(n-g(n)) = \log n$.


Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$ The full question is: Construct a Turing machine that recognizes the set $\{0^{2n}1^n \mid n\geq 0\}$.  The Turing machine starts with the input on the tape and the head over the leftmost symbol of the input.  The symbols to the left of the input are blanks out to infinity, as are the symbols to the right of the input.  If the string is accepted, the machine should halt with 1 on the tape (the rest of the tape should be blank).  If the string is rejected, the machine should halt with 0 on the tape.

Yes, this is a homework question, but I think I just need some help understanding the problem. We have not gone very in depth into Turing Machines, and he suggested we should just write the answer graphically like a  Deterministic Finite State Machine with read, write, and direction in the transitions.

I am getting stuck because I can only think about it in terms of 3 different paths (being 001, 100, 010), but I know this is most likely not correct, and I do not know how to recognize if the string is not in the set. I understand that the machine know the string has ended when it reads a blank, and then it will move right one and write either a 1 or 0 depending on if the string is accepted or not, but I can only think about it as 3 different paths.

Help would be appreciated! Thanks!

Here is a Turing machine on the online simulator I found here.

name: Recongnize 0^2n 1^n
init: s0
accept: acc

s0, 0
s1, _, >

s1, 0
s2, _, >

s2, 0
s2, 0, >

s2, 1
s2, 1, >

s2, _
s3, _, <

s3, 1
s4, _, <

s4, 0
s4, 0, <

s4, 1
s4, 1, <

s4, _
s0, _, >

s0, _
acc, _, -

The idea is to delete the two zeroes on the left, got to the end on the right, delete one, go to the way to the left, repeat. Accept only when after deleting 1 on the right the tape is empty.


Pumping Theorem and K I have an example from a textbook using a language $L = \{ a^nb^ma^n : m, n \ge 0, n \ge m \}$.

  We can use pumping theorem to show that $L$ is not context-free. If it were, then there would exist some $k$ such that any string $w$, where $|w| \ge k$, must satisfy the conditions of the theorem. We show one string $w$ that does not. Let $w =a^kb^ka^k$ where $k$ is the constant from the pumping theorem [...]

Why have they chosen to use $k$? My understanding from the pumping theorem definition is that $k$ is an arbitrary integer $>1$
What is the relation of $k$ to $n$ and $m$ in the original language definition?
Members of $L$ can have more $a$'s than $b$'s, but $a^kb^ka^k$ will result in an equal number of $a, b$. Is it not necessary in this case because an equal number of $a$'s and $b$'s is still a member of L? What happens when $L = \{ a^nb^ma^n : m, n \ge 0, n > m \}$ and $a^kb^ka^k$ is not part of $L$?

I think this is holding me back from understanding how to prove my homework question of:

  Prove whether the language $\{a^xb^yc^xd^y: x, y \ge 0\}$ is context free or not

Apologies if these are basic. I've been racking my brain for days on these kinds of questions and I'm so lost. Thanks for any assistance.

Definition from Wikipedia:

If a language L is context-free, then there exists some integer p ≥ 1 (called a "pumping length"[1]) such that every string s in L that has a length of p or more symbols (i.e. with |s| ≥ p) can be written as
s = uvwxy
with substrings u, v, w, x and y, such that

|vwx| ≤ p,
|vx| ≥ 1, and
$uv^nwx^ny$ is in L for all n ≥ 0.

k is called the pumping length and it's a positive integer. (it can be equal to 1).
k is NOT an arbitrary integer and every CFL is guaranteed to have one.
They chose the string w, since it's a contradicting example. (it's not a unique contradicting example)
I advise you to separate the string w (s in the definition) to different cases for-each position of v and x might be (which satisfy (!) the properties in the definition) and see if choosing some n (0 ... inf) creates a word that is not in L.
If w is in L and don't satisfy the pumping lemma (all the possible cases resolved in contradictions) -> L is not a CFL.
[Note that n=0 will remove x and v from the string, which sometimes help]
[Notice that w (in your example) is $\geq$ k, that's why you can use the pumping lemma. For strings that are shorter, you can't use it.]
For example (1 case): if v and x consists only of 'b', choosing n = 2 will create a string with number of 'b' strictly larger than 'a' which is not satisfying L properties.
k has no relation to n and m, it's a constant. For each CFL you are guaranteed to have one.
Hint for your homework : a possible contradicting example choice is very similar to your example.


What is a sticky bit in computer architecture? I am reading about a counter implementation in RISC Architecture. The specification reads,

  Sticky overflow bit is set when the counter wraps through zero.

I can infer that the overflow bit is set when the counter reaches maximum value(all 1's) and another increment makes it 0(all 0's). What is the meaning of the sticky overflow bit?

A sticky overflow bit means that the next operation that does not overflow (but would set the bit if it did) will not clear the bit. The value is sticky/persistent and must be cleared to detect newer overflows.


Producing a total or partial order from an inconsistent relation Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through repeated application of the comparison function, such that each element in the set is represented at least once.
How can I use this input to produce a total order? What is the class of algorithms that can be applied here?

For greater clarity, I'll provide a concrete example.
What are the best pizza toppings?
My set of elements $E$ includes some popular pizza toppings: pepperoni, cheese, mushroom, pineapple, bellpepper, olive.
Then for each of my friends, I pick randomly sized subsets of toppings and ask my friend to put them in order from best to worst. My friends dutifully reply, and create the input for my algorithm:

cheese, pepperoni, olive
cheese, pineapple, mushroom, olive
bellpepper, mushroom, olive
pepperoni, cheese, olive
cheese, bellpepper

There does seem to be a fuzzy order here (everyone agrees olives are the worst) but my friends have not arrived at consensus about which is the better pizza topping: cheese or pepperoni. Considering where items occur in the inputs, and how frequently they occur, I would probably produce an order something like this.

cheese > pepperoni > bellpepper > pineapple > mushroom > olive

I'm just not sure how to go about formalizing this and making it work for much larger inputs.

I think the solution probably involves graphs and weighted edges, but I lack sufficient familiarity with graph algorithms to recognize whether this is a named area of study. I already came across "topological sorting" but that only works for directed acyclic graphs, and I am specifically interested in inputs that cannot produce a DAG.
I also noticed that this problem seems similar to voting for elected representatives. Is it, in fact, the same class of problem?

It's hard to say without more context and more modelling.  It will require some assumptions on how the results of the comparison function relate to the (hidden) desired total order.
It's possible you might want the Bradley-Terry-Luce model.  If so, there are many standard algorithms.  See also https://cs.stackexchange.com/a/85204/755.
It's possible you might want some ranking system, like Elo, etc.
It's possible you might want a ranked voting system, such as IRV, Condorcet method, Borda count, or any of many others.  They all have various flaws and tradeoffs.  There is a proof that no system will have all the properties we might want -- see, e.g., Arrow's theorem and the problem of non-transitivity (that even if each of your friend's individual preferences is transitive, i.e., a total order, then there is no guarantee that there exists a global total order that is consistent with all of them).


Miss penalty for Write request in a Write-Back style system If the processor is trying to write a word to a certain memory location, and the system uses a write-back style architecture, what happens in case of a miss? I'm assuming that the system would first load the cache line, update the specific word, and keep the cache line in the cache until it has to be replaced. Then it would commence the write-back operation upon removal.

So, the penalty for a missed write-back is actually a cache line read, correct?

Depends on what you mean by "penalty". In theory (and in practice in high performance processors), a store does not need to stall subsequent instructions, so there's essentially no penalty at all from a store miss.

If you're talking about issue-to-commit time (i.e. when the store can be considered permanent) then the latency would indeed be when the cache line read occurs.

NOTE:

Most if not all architectures (ARM for example) allow non-temporal store hints. In practice most processors treat these as non-cacheable stores. So they go directly to memory without the need to grab the data into cache.

Some microarchitectures detect store streams to a temporal block. They support a type of RdNoData command that simply grabs store permissions without transferring data.


Why is EXACT-CLIQUE not in co-NP? In my lecture I saw the problem of
$\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$

I understand this problem is obviously not in NP as we would need to check all cliques, but if we consider the complement of the problem, (i.e. is the largest clique not of order $k$), wouldn't this be in NP? Because we could simply use non-determinism to guess a clique bigger than $k$ and then check if it indeed makes a clique. My lecturer said however that the problem is not in co-NP but I did not understand the explanation.

The problem "Does the largest clique have a size ≤ k" is in co-NP - if the answer is NO then there is a clique of size > k, and guessing that clique proves that the answer is NO.

But the problem here is "Does the largest clique have a size of exactly k". If the answer is NO then it could be that the largest clique has size k-1 and there are no cliques of size k, k+1, k+2 etc. Sure, you could guess a clique of size k-1 - but that doesn't prove a clique of size k doesn't exist. And you can't guess a clique of size k+1 because no such clique exists.


Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$ I need to solve the following recurrency: $T(n) = 2T(\sqrt{n}) + O(1)$. It's for a simple undergrad problem that a student asked me, but I really couldn't solve it. Since it is for an undergrad question, it would be nice to solve it only with algebraic manipulation and reduction to a well known recurrence, or in the end use the master theorem or a recursion tree. Looking at this question, I tried to make $m=\log(n)$, but I got lost at squeezing the $\log$ inside the term $T(\sqrt{n})$. Is it like $T(\log(\sqrt{n}))$ or $T(\sqrt{\log(n)})$? Or is this the wrong approach?

Since Master theorem is in terms of fractions of $n$ in the recurrence, and you have a fractional power of $n$ in the recurrence, try to convert between powers and multiplications. Taking $\log$ or $\exp$ of something usually helps with that.

Let $x=\log n$, $F(x)=T(\exp x)$. Then you have this recurrence:

$F(x)=T(\exp(\log n))=T(n)=2T(\sqrt n)+O(1)=2T(\exp (\frac{1}{2}\log(n)))+O(1)=2F(\frac{x}{2})+O(1)$

Then apply Master theorem to $F(x)$ and get $F(x)=O(x)$.

Therefore $T(n)=F(\log n)=O(\log n)$.


Construction of a counter automaton for the complement of the palindromes How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = \{0,1\}$?

The definition I am using for 1-NCAs consists of:

$S$, the set of states,
$\Sigma$, the alphabet ($\Sigma = \{0,1\}$ in our case),
$s_{0} \in S$, the initial state,
$F \subseteq S \times \{\text{zero},\text{nonzero}\}$, the set of accepting states, and
$\delta : S\times\{\text{zero},\text{nonzero}\}\times A \rightarrow S \times \{-1,0,1\}$, the transition function.

Given a word $w = x_1x_2\ldots x_ny_1y_2\ldots y_n$, I know that if $x_i$ is not equal to $y_{n-i+1}$, the palindrome requirement fails. I have a feeling that the counter has something to do with that distance in between those letters but formalizing this is what I am stuck at.

Since a 1-NCA is the same thing as a NPDA (nondeterministic pushdown automaton) with only one symbol in the stack alphabet, I would accept answers using such PDAs also. This is especially since I find very few texts discussing counter automata.

If you know that $L$ can not be recognised by a $k$-DCA for any $k$, this gives the hint that you need to use nondeterminism to do it with 1 counter.

What we can do then is guess where the mismatch characters are, in particular, what we'll do is check that $x_{i} \neq y_{n-i+1}$ by using the counter to determine first that we're at position $i$ in the input (or rather, nondeterministically guessing that some $i$ is the right index to remember), then guessing nondeterministically that we've reached position $n-i+1$, checking that the two symbols at those positions are different, then counting down to check that we actually were at the right spot (i.e. the counter will have to be back to zero exactly when we reach the end of the input).

One version of this looks like:

So $s_{0}$ counts up until the symbol just before the one we're interested in. We nondeterministically guess to stop and record what symbol we see by moving to a different state, then $s_{1}$ and $s_{2}$ basically ignore the rest of the input until we guess we've reached the $(n-i+1)^{th}$ symbol, at which point we make sure it's different to the one at $i$, then $s_{3}$ counts down for the rest of the input. If there's no input left when the counter hits zero, we can move to $s_{4}$ and accept. If we move to $s_{4}$ too early, we can't accept because there's still input to be processed (so you could take some of the nondeterminism out by putting in an explicit sink state etc.), if we guessed to early which one was the mismatched symbol, then we can't reduce the counter to zero, so we can't get to $s_{4}$.


How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$.  Note that we don't relax $u$ and $v$ on each iteration through the edges.

What I don't understand is that if $G$ is an undirected graph with $n$ vertices, then it is equivalent to a directed graph with $2n$ vertices.    We simply think of the edge between $u$ and $v$ as a set $\{u,v\}$ for an undirected graph, and as the ordered pair $(u,v)$ for a directed graph.

I don't understand why the Bellman-Ford algorithm needs only $n-1$ repetitions for both a directed and undirected graph.  It seems like it should take $n-1$ repetitions for directed graph, and $2n-1$ repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.

Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?

The Bellman-Ford algorithm does not work on undirected graphs with negative weights, because $(u,v)$ and $(v,u)$ are not allowed on the same path, but the Bellman-Ford algorithm does not handle this constraint. In fact, if the weight of $(u,v)$ is negative, $(u,v)$ and $(v,u)$ form a negative cycle.

If your weights are all non-negative (which is possibly your case according to your comment), the Bellman-Ford algorithm can work on undirected graph. The reason why it requires only $n-1$ iterations is explained in D.W.'s answer. However, you may want to take the advantage of non-negative weights and use some more efficient algorithm (like Dijkstra's algorithm).

Otherwise you can use the technique of T-joins or perfect matching.


Maximum number of points that two paths can reach Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, y_j)$ if $x_i \le x_j$ and $y_i \le y_j$. The question is: given these $n$ points, what is the maximum number of points that we can reach if we are allowed to draw two paths that connect points using the above rule? Paths must start from the origin and may contain repeated points. $(0, 0)$ is of course not included in the points reached.

An example: given $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$, the answer is $8$ since we can take $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ and $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$.

If we are allowed to draw only one path, I can easily solve the question by dynamic programming that runs in $O(n^2)$. I first sort the points by decreasing $x_i+y_i$. Let $D[i]$ be the maximum number of coins that one can pick up from coins $1$ to $i$ in the sorted list. Then $D[1] = 1$ and $D[i] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$. The answer then is just $\max\limits_{1\le i \le n} D[i] + 1$.

But I cannot come up with a recurrence relation for two paths. If anyone has any idea about such a recurrence relation, I would be happy to hear what they are.

The problem, restated and generalized: given a finite set $S$ equipped with a partial order $\le$, find chains $C_1, C_2 \subseteq S$ maximizing $\lvert C_1 \cup C_2 \rvert$. The question is about the case where $S \subseteq \mathbb R_+^2$ and $(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$.

Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$\bigl((0,0),(0,0)\bigr) < \bigl((1,0),(0,0)\bigr) < \bigl((2,0),(0,0)\bigr) < \bigl((2,0),(1,0)\bigr),$$ so this notion of best does not have optimal substructure.

Instead, we look for chains in the set $T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement.

Lemma 1 (no retracing). Let $C \subseteq T$ be a chain and define $C_1 := \{x \mid (x, y) \in C\}$ and $C_2 := \{y \mid (x, y) \in C\}$. For all $z \in S$, we have $z \in C_1 \cap C_2$ if and only if $(z, z) \in C$.

Proof. The if direction is trivial. In the only if direction, for all $z \in C_1 \cap C_2$, there exist $x, y \in S$ such that  $(x, z), (z, y) \in C$. Since $C$ is a chain, $(x, z) \le (z, y) \vee (z, y) \le (x, z)$. Assume symmetrically that $(x, z) \le (z, y)$, which implies that $x \le z \le y$. We know by the definition of $T$ that $x \nless z \wedge z \nless y$, so $x = z = y$, and $(z, z) \in C$.

Lemma 2 (existence of restricted best chain). For all chains $C_1, C_2 \subseteq S$, there exists a chain $C \subseteq T$ such that $C_1 \subseteq \{x \mid (x, y) \in C\} \subseteq C_1 \cup C_2$ and $C_2 \subseteq \{y \mid (x, y) \in C\} \subseteq C_1 \cup C_2$.

Proof (revised). We give an algorithm to construct $C$. For convenience, define sentinels $\bot, \top$ such that $\bot < x < \top$ for all $x \in S$. Let $C_1' := C_1 \cup \{\top\}$ and $C_2' := C_2 \cup \{\top\}$.

Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.
Let $x'$ be the next element of $C_1$, that is, $x' := \inf \{z \mid z \in C_1' \wedge x < z\}$. Let $y'$ be the next element of $C_2$, that is, $y' := \inf \{w \mid w \in C_2' \wedge y < w\}$.
If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.
If $y < x' < y'$, set $(x, y) := (x', x')$ and go to step 9.
If $y \nless x' < y'$, set $x := x'$ and go to step 9. Note that $x < x' \wedge x \nless y$ implies that $x' \nless y$.
If $x < y' < x'$, set $(x, y) := (y', y')$ and go to step 9.
If $x \nless y' < x'$, set $y := y'$ and go to step 9. Note that $y < y' \wedge y \nless x$ implies that $y' \nless x$.
This step is never reached, as the conditions for steps 3–7 are exhaustive.
If $x \ne \top$ (equivalently, $y \ne \top$), set $C := C \cup \{(x, y)\}$ and go to step 2.

Dynamic Program. For all $(x, y) \in T$, compute $$
D[x, y] := \sup\biggl(\Bigl\{D[z, w] + [x \ne z] + [y \ne w] - [x = y] \mathrel{\Bigl|\Bigr.} (z, w) \in T \wedge (z, w) < (x, y)\Bigr\} \cup \bigl\{2 - [x = y]\bigr\}\biggr),
$$
where $[\textit{condition}] = 1$ if $\textit{condition}$ is true and $[\textit{condition}] = 0$ if $\textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.


Examples of logic gates using non-standard models These are the only ones I have been able to find online:

Pulley Logic Gates
Marble adding machine
MARBLE COMPUTER LOGICAL AND GATE

I would like to find some more discrete models like these (as opposed to say, water logic gates or things like that). Not sure if there is a library of different techniques to build logic gates outside of electronics, or if not, what some other good examples are like these above, that perhaps demonstrate further their functionality.

Picture hanging can realize any monotonone boolean function.

I.e., you can hang a picture using two pins so that it falls IFF both pins are removed. This is trivial to achieve, and realizes an AND gate.

However, you can also hang it so that it falls IFF either pin is removed. Implementing this OR gate is not so trivial at first.

See the linked paper for nice pictures.


What is the duality between path cover and flow? Let there be a bipartite directed graph $G=(V,E)$.
Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean?
How can we extract a flow from a path cover (and similarly, extract a path cover from a flow)?

Presumably, the flow would send $k$ units of flow along the edge $(u,v)$, where $k$ is the number of paths in the path cover that traverse that edge.
I haven't verified that this will always be guaranteed to be a valid flow for all possible path covers, but it doesn't seem like it on first glance, so more context might be needed to resolve that.


network address translation I'm having some difficulty understanding ip addresses. Let's say:

Question Info:

private subnet 192.168.0.0/24

IP addresses 212.201.49.1-5

Now, a host 192.168.0.2:1234 retrieves a web page from the web server at 42.35.12.33.

Then, host 192.168.0.5:1234 retrieves a web page from the web server at 100.12.45.11

Answer Part:

Now, I have this information for first the request part:

internal

192.168.0.2:1234 (src)

42.35.12.33:80 (dest)

external:

212.201.49.1:1234 (src)

43.35.12.33:80 (dest)

Where does 80 come from at the end of dest?

Now, for the second request, the src address of external is 212.201.49.2:1234.

Why is it 2.1234? In the 3rd one, it was 1 again.

Usually writing an ip address and a number after the : ,it means the number after the : is  the port

In the internal part:
192.168.0.2 is the private ip address of the host its his ip address inside the network,notice that we have 2 types of ip addresses: private ip address-which is the ip address inisde out network and public ip address which is our ip address in the "internet"
so 192.168.0.2 its the private ip address of the host and the 1234 its the port of the client-the host

now the 42.35.12.33 is the ip address of the web page and the page listens to the port 80

In the external part:
we can see the  ip address of the host has changed,why has it changed?because what i said before about private and public ip addresses this-this ip is the external ip which the host was provided(i suggest reading about NAT if you want to understand this part deeper) the port of the host stays 1234


Can this equation be solved in polynomial time? I came across a more general form of this question.

Can we find the value of variables in polynomial time ?

Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ values can only take positive integer values ranging from 1 to $n$.

We have equation generator,
$$a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$$

for variables $x,y,z\in \{1,2\ldots, n\}$.

$f$ can be any thing such as $x, x^{2}, \log x$ etc.

Given that the constants are rational numbers and that there exists a solution, can we solve for the variables in polynomial time?

Update: Please note that I am not giving a single instance of $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$, instead I am giving you the entire family of all possibilities of the above equation.

Basically I am giving you a black box, if you input $f$ it gives you corresponding $k$, given that $f$ is computable in polynomial time. We can do this multiple times. The goal is to solve for variables using this black box, in a polynomial time.

So we have:
    1. The values of $m$ and $n$
    2. The constants $a,b,c ...$
    3. The equation generator $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$

We can go on choosing different $f$ and the generator will give us corresponding equation, with a new $k$.

Goal:
To solve for variables in the equation when $f(x) = x$

Update 2: For people wondering the origin of the question and its purpose. If the answer for this question is yes, then I think Sudoku can be solved in polynomial time. I tried to make use of the numerical property of Sudoku, that the sum of the entries of any row or column is known. By dealing each unknown cell as a variable we could treat each row and column as an equation. For a Sudoku of $n*n$ it would result in $2n$ equations with $n^2-k$ variables where $k$ is the number of already filled cells. This is an underdetermined system of equations. We could represent this in a matrix and it can be reduced to Echelon form. This can be repeated for sum of squares, cubes etc etc of the values. If we could solve this we could solve Sudoku.

Summary

Your problem remains NP-hard, despite the fact that the algorithm can choose the function $f$.  Consequently, no, you should not expect a polynomial-time algorithm.

The problem is at least as hard as the subset-sum problem.  Fortunately, subset-sum is one of the easier NP-hard problems, so if your problem instance is small enough, you might be able to use algorithms for subset sum to solve your problem.

Problem statement

I'm going to reformulate your problem statement, so we are all on the same page:

Input: integers $m,n, a_1,\dots,a_m$; and access to an oracle, as follows:
Oracle: has secret values $x_1,\dots,x_m \in \{1,\dots,n\}$; when provided a function $f:\{1,2,\dots,n\}\to \mathbb{N}$, the oracle outputs the value $a_1 f(x_1) + \dots + a_m f(x_m)$
Goal: find $x_1,\dots,x_m$

An algorithm

You could use algorithms for subset-sum to help solve your problem, using the following strategy.

Let $\delta_1$ denote the function so that $\delta_1(1)=1$ and $\delta_1(j)=0$ for all $j \ne 1$.  Send $\delta_1$ to the oracle, and call the result $k_1$, i.e., $k_1 = a_1 \delta_1(x_1) + \dots + a_m \delta_1(x_m)$.  Notice that $k_1$ is a sum of the a subset of the $a_i$'s, namely, those where $x_i=1$.  In other words, $k_1=\sum_{i \in S_1} a_i$ where $S_1=\{j : x_j=1\}$.  So, feed $a_1,\dots,a_m$ and $k_1$ into an algorithm for the subset sum algorithm, and ask it to find a subset of the $a_i$'s that sums to $k_1$.  If this subset sum problem has a unique solution, then the result will tell you which $x_i$'s have the value 1.

Next, let $\delta_2$ denote the function so that $\delta_2(2)=1$ and $\delta_2(j)=0$ for all $j \ne 2$.  Send $\delta_2$ to the oracle, and call the result $k_2$.  Do the same thing, using a subset-sum solver to find a subset of $a_i$'s that sum to $k_2$; if this solution is unique, that will be the set of $x_i$'s that have the value 2.

Repeat, for $\delta_1,\dots,\delta_n$, until you have learned all the value of all of the $x_i$'s.

If you're lucky, the subset-sum problem has a unique solution at each stage, and after solving $n$ subset-sum problems you can read off the values of the $x_i$'s.  If you're unlucky, it has multiple solutions, and now you might need to consider all combinations of solutions to find a combination where the subsets are disjoint.

(Incidentally, once you've queried the oracle on $\delta_1,\dots,\delta_n$, you can predict the response of the oracle on any other function, so there's not much point in querying it again.  This shows that $n$ queries to the oracle suffice; we'll never need more than that.)

The problem is NP-hard

Here is a reduction to show that the problem is as hard as subset sum.  In particular, we'll show that the special case of your problem where $n=2$ is as hard as subset sum.  Suppose we have a subset sum instance, namely numbers $a_1,\dots,a_m$ and a target $t$.  We'll show how to use any algorithm for your problem to solve this subset sum instance.

We will implement a sneaky oracle, which behaves as follows: when provided a function $f:\{1,2\} \to \mathbb{N}$, it returns the value

$$f(1) \cdot (a_1 + \dots + a_m) + (f(2)-f(1)) \cdot t.$$

Notice that the sneaky oracle doesn't have a particular set of values $x_1,\dots,x_m$ in mind.  Nonetheless, if there is a subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle would be equivalent to what we would obtain if we had an ordinary oracle where the $x_i$'s were 2 for all $i$ in that subset and 1 otherwise; and if there is no subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle are not equivalent to  any ordinary oracle (for any value of the $x_i$'s).

Now, ask the purported algorithm for your problem to work with this sneaky oracle and find values for the $x_i$'s.  If the algorithm for your problem finds a solution for the $x_i$'s, that yields a solution for the subset sum problem (simply include the $a_i$'s where $x_i=2$ in the subset).  If the algorithm for your problem doesn't find a solution for the $x_i$'s, there is no subset of the $a_i$'s that sums to $t$.

(Strictly speaking, this shows the case where $n=2$ is hard.  However, one can show that increasing $n$ does not make the problem any harder.  Thus, the case where $n=\sqrt{m}$ is also hard.)


Real-time systems and real-time operating systems Just to understand the topic a little bit better, I would like to know if there is a difference between real-time systems and real-time operating systems.

I know that a real-time system is a system for processes that have to meet deadlines and fulfill real-time requirements. If a deadline isn't met, it can lead to drastic consequences.
And a real-time operating system is an operating system that also has to fulfill real-time requirements.
The examples I found on the internet are mostly the same and also other details are quite the same.

But are there any major differences, if yes which ones?

A system is several things working together. A real time system might include computer hardware and software. Depending on where you draw the line it might include sensors and actuators reaching into the "real" world (sorry for the pun ). The software might include an operating system, or not.

A realtime operating system is a set of software components with the purpose of making it easier for you as a programmer to write the application software of a real time system. Typically the OS helps in handling hardware and dividing the processor among several tasks. It could include tools used to create the system, to find bugs and to measure performance. This is a kind of software reuse, and I tend to think of it as "me beeing a midget, standing on the shoulders of the titans previous to me".

A real time system can loosely be defined by the statement "even if the response is correct, if it is too late it is as bad as if it was wrong". The concept of too late is the major concept in a real time system. This could be on a time scale of pico- or microseconds (sort of difficult with software), milliseconds or seconds (typical realtime areas) or even minutes, hours, days or years (probably not called realtime, but could be).

Often a real time system includes some mechanism to handle serious errors. The concept of fail-safe is often used. As example, even if the software stops totally, or part of the hardware becomes unserviceable, some hardware function in the system turns outputs to a safe state and maybe restarts the software. Another exemple might be that cars with computer controlled ignition and fuel injection has a special "limp-home" mode allowing you to do something useable even when some of the sensors are broken. Here the computer might be working, but not all parts of the system.

When human life is at risk, say in space exploration, the fail-safe solution might include running several computers in parallell and turning off suspicious ones using external hardware. The space shuttle is a famous example with several computers running in parallell and special hardware selecting to kick out erraneous ones. In addition there was a special fallback computer, using different hardware and software written by a different team to handle if the main computers would go totally off.


Understanding the coefficient matrix of Hermite Interpolation I was not sure whether this is a computer science question or a math question, so I posted it here, hope that it is alright.
I am trying to learn the technique of Hermite interpolation. I do understand that it is a generalization of Newton polynomial interpolation, which also considers derivatives to ensure continuity of the interpolated curve at the provided points.
In the book Computer Animation — Algorithms and Techniques by Rick Parent, there is a definition of Hermite interpolation that looks like this:

Hermite interpolation generates a cubic polynomial from one point to another. In addition to specifying the beginning and ending points $(P_i,P_{i+1})$, the user needs to supply beginning and ending tangent vectors $(P'_i,P'_{i+1})$ as well.

Here, just the first derivatives are considered, and the aim is to find a polynomial of degree 3 by finding appropriate coefficients $a_3,a_2,a_1,a_0$ such that we have $a_3x^3 + a_2x^2 + a_1x + a_0$. These are found by solving a system of linear equations. So far, so good.
Now, in the book, the matrices look like this:

The general matrix form for a curve is $P(u) = U^TMB$. In the case of Hermite interpolation,
$$
U^T = \begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} \\
M = \begin{bmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \\
B = \begin{bmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{bmatrix}
$$

I do not understand the matrix $M$, I do not see where the values are coming from. Are these fixed, or can I somehow compute them?

We are looking for a curve
$$ P(u) = a_3 u^3 + a_2 u^2 + a_1 u + a_0 $$
which satisfies the following properties:

$P(0) = P_i$.
$P(1) = P_{i+1}$.
$P'(0) = P'_i$.
$P'(1) = P'_{i+1}$.

In terms of the coefficients $a_0,a_1,a_2,a_3$, these are:

$a_0 = P_i$.
$a_3 + a_2 + a_1 + a_0 = P_{i+1}$.
$a_1 = P'_i$.
$3a_3 + 2a_2 + a_1 = P'_{i+1}$.

In matrix form, this reads:
$$
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix} =
\begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 3 & 2 & 1 & 0 \end{pmatrix}
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix}
$$
Inverting the matrix, we get
$$
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix} =
\begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix}
$$
Therefore the equation of the curve is
$$
P(u) = \begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix}
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix} =
\begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix}
\begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix}
$$


Minimum spanning tree using DFS and BFS Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs?

I have gone through many answers but each answer says something different and I am not convinced.

Briefly, the answer is no, we cannot construct minimum spanning tree for an un-directed graph with distinct weights using BFS or DFS algorithm. This post provides a counterexample.

Computing MST using DFS/BFS would mean it is solved in linear time, but (as Yuval Filmus commented) it is unknown if such algorithm exists. However, there is an expected-linear-time randomized algorithm computing the MST.


Making a recursive formula for finding amount of ways to spend money on beer So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.

The information available is that there are $n$ different beers with different prices, the $i$th beer has a price $p_i$.  Students have $C$ amount of money

How would you make a recursive formula for the amount of ways students can spend exactly $C$ money on beer?

The $n$-the beer has price $p_n$. You can use $k$ items of beer $n$, provided $k\cdot p_n\le C$. The remaining money can be used for beers $1$ to $n-1$. That gives a recursive approach.


Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it? I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the same problem, there exist two opposite Monte-Carlo Algorithms capable of giving a certain answer. (By opposite, I mean one would be sure when it's FALSE, and the other would be certain when it's TRUE)

For example : There exist a prime number test Monte-Carlo based algorithm that can check whether or not a number "n" is prime. If the answer is FALSE, then "n" is not a prime number (it is a composed number). However, if the answer were to be TRUE, then "n" COULD be prime (with a certain probability). To my knowledge, there is no efficient algorithm (Monte-Carlo) capable of saying with certainty if "n" is a prime number.

A Las Vegas algorithm is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both algorithms (or running them in parallel), halting whenever one of them produces a certain answer.

In the language of complexity theory, this corresponds to the statement $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$. You can find more information on $\mathsf{ZPP}$ on Wikipedia.


Recursive definition for the length of a string? I found a couple of answers online but I don't quite understand why the answer is right:

The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the string is 1 + length of the tail

Strings are concatenations of characters. Hence, any non-empty string $w$ has a first character $x$ and can be written as $w = x w'$, where $w'$ is the tail string. It follows from the definition of a string's length that $|w| = |x w'| = |x| + |w'| = 1 + |w'|$.


Proof that $a^{n^2}$ is not regular Show that $L=\{a^{n^2} | n \geq 0\}$ is not regular

Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me.
I tried to look if I get some contradiction by using the pumping lemma for regular languages and I worked it out like this:

Suppose $L$ is regular. Then there must be a natural number $m$ for all words $z$ in $L$ with length $|z| \geq m$ and there exists a decomposition $z = uvw, |uv| \leq m, |v| > 0$, so that $u(v^i)w$ is in the language for any $i \geq 0$.
Consider the string $a^{m^2}$.
Then $uv = a^{k^2} = a^{x+y}$, for some $k \leq m$ and $x = (k-1)^2$.
Then $v = a^y = a^{2k-1}$.
Let $i = 2$. Then $u(v^2)w = a^{x+2y}$. But $\sqrt{x+2y}$ is not necessarily a natural number -> Contradiction! Hence, $L$ can not be regular.

Well, I know that this way is unnecessarily complicated and you can prove it differently (I already know the most simple solution). But my question here is: Is my proof valid as well or does it contain any flaw? Is it formally correct?
I appreciate any feedback! Thanks!

You can't deduce that $uv = a^{k^2}$, all that the pumping lemma gives you is that $|uv| \leq m$. Not all numbers less than $m$ are squares. Not only that, but even supposing that $uv = a^{k^2}$, there is no reason to assume that $v = a^{2k-1}$; all the pumping lemma gives you is that $v$ is non-empty. Finally, in order to get a contradiction, it is not enough that $x + 2y$ need not be a square, it must not be a square! Since $x$ and $x+y$ are adjacent squares, it is actually case that $x + 2y$ is not a square.


Confusion over the complexity of parameter passing in merge sort I'm working through CLRS on problem 4-2, which says the following:

  Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.

  This problem examines the implications of three parameter-passing strategies:

  An array is passed by pointer. Time $ = \Theta (1)$.
  An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
  An array is passed by copying only the subrange that might be accessed by the called procedure. Time $= \Theta(q-p+1)$ if the subarray $A[p \ldots q]$ is passed.

  Consider the recursive merge sort algorithm. Give recurrences for the worst-case running times
  of binary search when arrays are passed using each of the three methods above,
  and give good upper bounds on the solutions of the recurrences. Let $N$ be the size of the original problem and $n$ be the size of a subproblem.

For part (2), one solution I have seen is:

  $$T(n) = 2T(n/2) + cn + \color{red}{2N} = \color{blue}{4N} + cn + 2c(n/2) + 4T(n/4) = 8N + 2cn + 4c(n/4) + 8T(n/8) = \\ \qquad
     = \sum_{i=0}^{\lg{n}-1}(cn + 2^iN)
     = \sum_{i=0}^{\lg{n}-1}cn + N\sum_{i=0}^{\lg{n}-1}2^i
     = cn\lg{n} + N\frac{2^{\lg{n}} - 1}{2-1}
     = cn\lg{n} + nN - N
     = \Theta(nN) \\ \qquad
     = \Theta(n^2)$$

I don't understand where the $\color{red}{2N}$ has come from. The $2T(n/2)$ is the "conquer" part, and the $cn$ is the "combine" part, leaving the $\color{red}{2N}$ to be the "divide" part, but I'm not sure why it's $2N$ rather than just $N$, as you are only copying the $N$-length arrary over once.

Also, I don't understand where the $\color{blue}{4N}$ has come from (following the previous equality). Surely, $$T(n) = 2T(n/2) + cn +2N \\ = 2\underbrace{[2T(n/4) + c(n/2) + 2N ]}_{T(n/2)} + cn + 2N \\ = 4T(n/4) +2cn + 6N \ ?$$

Finally, am I right in thinking that the last equality holds because $N$ is some subset of $n$, so $n$ = $k N$ (for some constant $k$), so $T(n) = \Theta(n) \cdot  \Theta(N) = n \cdot  n = n^2$?

The $N$ is incurred once for every recursive call, since this is the cost of passing a parameter. Since there are two recursive calls, it's $2N$. As for the $4N$, this seems like a mistake. Don't expect solutions you find on the internet to be correct. Finally, $N$ is not a subset of $n$. It is the size of the original array. A less confusing way to write the conclusion would be $\Theta(nN) = \Theta(N^2)$. Note that it is always the case that $n \leq N$ (and not the other way around).


Having trouble proving vertex cover greedy algorithm So this is my first time posting, but I don't know where else to go. I've spoken with several PHD and Masters students and they referred me here. I've been looking at the Vertex Cover problem and came up with an algorithm to find the optimal minimum. I've tried this on several graphs as examples and it's found the optimal every time. Could someone please help me prove that either this finds the optimal for all VC problems or if there is a counter example disproving it? Thanks in advance.

Given Graph G = (V,E), find minimum Vertex Cover

Sort the vertices by the number of edges associated; greatest to smallest O(nlogn)
While there are unmarked edges in E: O(V)

Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges O(V*E)
Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily.
Skip vertices that have no unmarked edges.

For each vertex in S, in the order they were added:

Remove vertex from set S and update edge markings. If any associated edge becomes unmarked, reselect vertex and remark the edges. Otherwise, remove vertex from S (nobody wanted them anyways ) O(V*E)

Return S

Algorithm runs in O(V*E). The edge markings can be maintained in a VxV table.

I had initially missed parts 2.3 and 3.

If I'm not still missing something, then your algorithm can find a non-optimal cover for the hexagon, and necessarily finds a non-optimal cover for  $K_{3,3}$ minus one edge. (Those are both connected balanced-bipartite graphs, so each half of their bi-partitions is a three-vertex vertex cover.)

The hexagon's vertices all have degree two, so "highest edge count (total)"  won't do anything, and your algorithm will fall back on 2.2 for each loop through 2. Your algorithm's initial choice for the hexagon doesn't matter, and its next choice will be an arbitrary one of the three vertices in the hexagon's opposite half. If your algorithm chooses the middle of those three  (i.e., the opposite vertex), then its next choice won't matter and part 2 will finish by choosing an arbitrary one of the vertices in the remaining unmarked edge. If its last choice is the one that is opposite from its next-to-last choice, then S will be the four vertices vertices from two opposite edges, which is a minimal vertex cover, in which case part 3 can't remove anything.

$K_{3,3}$ minus one edge has four vertices with degree three and no vertices with higher degree.Those four vertices are each adjacent to a degree-two vertex, so will all be put into S. Due to the removed edge, putting those four in will result in there being no unmarked edges. Since only that edge was removed, S is a minimal vertex cover, so part 3 can't remove anything from it.


Specific example of a problem that shows why **NP** isn't low for itself Wikipedia says

  Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely... .

This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but can be solved efficiently by a NTM with oracle access to another NTM?

As Pål GD mentions in the comments, $\mathsf{NP}^\mathsf{NP}$ is usually knows as $\mathsf{\Sigma}_2^P$, the second level of the polynomial hierarchy. If $L$ is any $\mathsf{\Sigma}_2^P$ complete problem, then $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ is equivalent to $L \in \mathsf{\Sigma}_2^P \setminus \mathsf{NP}$. So any $\mathsf{\Sigma}_2^P$-complete problem is a concrete example for a problem in $\mathsf{\Sigma}_2^P \setminus \mathsf{NP}$ under the reasonable assumption that $\mathsf{\Sigma}_2^P \setminus \mathsf{NP} \neq \emptyset$. In other words, these are the problems "most likely" to be the concrete examples you seek.

One canonical complete problem for $\mathsf{\Sigma}_2^P$ is $\exists \forall\mathsf{SAT}$: given a formula $\varphi$ on variables $\vec{x},\vec{y}$, is is true that there exists an assignment $\alpha$ to $\vec{x}$ such that $\varphi|_{\vec{x} = \alpha}$ becomes a tautology? It is easy to see that this can be solved by an $\mathsf{NP}^\mathsf{NP}$ machine: the machine guesses $\alpha$, and uses the oracle to verify that $(\lnot \varphi)|_{\vec{x} = \alpha}$ is unsatisfiable.

Generally speaking, the assumption $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ seems stronger than $\mathsf{P} \neq \mathsf{NP}$, and when proving conditional results, we prefer assuming the latter rather than the former. But it is generally conjectured that the entire polynomial hierarchy is strict, a much stronger assumption.


How should i guide a program to perform correct things? I want to make a small model of A.I. which can learn itself. I am inspired by 1000+ monkey theorem which states that if 1000+ monkey bangs a keyboard for enough long, then they will eventually produce a Shakespeare's play. So, if you give a banana to one monkey when he produce a correct word, then he would eventually learn to do correct things. I think it is related to neural network.

So, practically i want to start with basic alphabets and digits and then my program would permutate and combine those to form words. Now, if the words they form matches with those in English Dictionary, i want to reward the program. However i couldn't think of any possible approach to this. How could this be implemented?

The "Infinite Monkey Theorem" doesn't say that monkeys will learn.  On the contrary: it says that if monkeys keep typing random stuff long enough (i.e. not using any sort of learning), the works of Shakespeare will eventually come out purely by chance.  It is the Law of Truly Large Numbers.

So you're right: you need to build feedback into the system.  The program should change its behavior based on your feedback.  This is known as reinforcement learning and it is used a lot in AI.  An overarching term for this, I believe, is machine learning.


Is a language recursive? 2 wrong ways of solving Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on  $x$ different from the result of $M_2$ on  $x\}$
that means: if $M_1$ accept, $M_2$ reject and vice versa
$NPA=\{L|\exists M_1,M_2$ Nondeterministic polynomial TM $ s.t. Disagree(M_1,M_2)=L\}$
Is $NPA=R$?
I thought about this problem from 2 clashing ways:

If I choose $M_1$ to accept any input and $M_2$ to reject any input, for given $L$ each $x\in L$ will be $x\in Disagree(M_1,M_2)$ so $NPA=R$
To accept $L$, $M_1$ and $M_2$ should run on every $x\in L$ and even if it's a single step the input ($L$) is a countably infinite set, so it's impossible to run on all the $x\in L$, so $NPA\neq R$

When I saw the answer, I understood that both of my ways wrong, but I can't understand in which step?

I'll assume that $R$ is the set of recursive languages and that in the definition of $NPA$ we are talking about Nondeterministic Polynomial Time.

You are just proving that, for $L \in R$, $L \subseteq Disagree(M_1, M_2)=\Sigma{}^*$ which says nothing about $NPA = R$.

To accept a language $L$, there must be some machine $M$ such that for each string $x \in L$ the computation $M(x)$ halts in the accepting state and for each string $x \not\in L$ the computation $M(x)$ does not halt. To decide a language $L$, the machine must halt in all inputs and, furthermore, if $x \in L$ the machine halts in accepting state, otherwise the machine halts in rejecting state.
That doesn't mean that the machine is "tested" simultaneously on an infinite number of strings.

That being said, when you want to prove that two sets are equal you need to prove that each one includes the other.
When you want to prove that two sets are different, it is sufficient to find some language that is in one set but non the other.
In your case, the requirement that $M_1, M_2$ must halt in a polynomial number of steps is suspicious.
If $L \in NPA$, then there are Nondeterministic machines $M_1, M_2$ such that they both halt in a polynomial number of steps and disagree precisely on $L$. From those machines, you can construct a Nondeterministic machine $M_{1,2}$ that decides $L$ in polynomial time, hence $L \in \mathcal{NP}$ and this proves the inclusion $NPA \subseteq \mathcal{NP}$ by generality of $L$.
By the Time Hierarchy Theorem,
$$NPA \subseteq \mathcal{NP} \subsetneq \mathcal{N}EXP \subseteq R$$
Hence $NPA \neq R$.


Complexity of computing $n^{n^2}$ What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?

By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log_2 n$ bits. So the total amount of time required is $\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$.


Is finding a path with more red vertices than blue vertices NP-hard? Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

I think it should be possible but our TA said this was NP-hard.

Idea for a solution:

From $G$ create $G'=(V',E')$ as follows:

Split all $v \in V\setminus \{s,t\}$ in two vertices $v_{in}$ and $v_{out}$. $V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) \in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x \in \{s,t\}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices. So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.

Now, we introduce weights as follows:

$w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
$w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
$w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.

Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.

Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?

Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.

I think the best to show NP-completeness, is to use the Hamiltonian path problem. Let's take a graph $G'$ of $N$ red vertices.

Then you build a graph $G$, adding $s$, $t$ and $N-1$ blue vertices to $G'$. You first chain with edges all the blues vertices from the source to the last blue one ($s$->$b_1$->$b_2$->...->$b_{N-1}$). Then you put edges from $b_{N-1}$ to every red vertex and an edge from every red vertex to $t$.

So a single path from $s$ to $t$ passes necessarly through all blue nodes ($N-1$) and then have to pass to all red nodes ($N$) to answer to

Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?

which is thus like answer to:

Is there an Hamiltonian path in $G'$

So your problem is indeed NP-complete.


Does undecidability ever imply unmeasurability and make a notion of probability ill-defined? Not sure precisely how to ask this question, but I want to understand if it is meaningful to ask about probabilities when aspects of the definition might be undecidable.  My curiosity extends to potential implications for definitions of entropy in physical systems.  Let me try to get a little more precise about the question, and maybe someone can point me in the direction of papers or textbooks that address the topic, or has an answer themselves.
For example, imagine I have a dynamical system which can be mapped to a universal Turing machine, so there are some input settings where I can map the outputs to Halting vs not.  Now some inputs are chosen at random, and I want to know the probability that the machine halts or not.  Does the fact that knowing if the problem halts on the input or not is undecidable imply that the a probability measure is ill-defined in this case?  Are there any implications for probability of input or output in such a case?

The space of possible inputs of a Turing machine is countable, so all its subsets are measurable. Same for outputs.
However, it's possible that this probability is not computable. In particular, you may want to look up Chaitin's constant. It isn't exactly what you are talking about, but closely related.


Predecessor-subgraph property In the proof of the predecessor subgraph property (page 14 of the following notes)
http://www.cs.sfu.ca/CourseCentral/307/binay/shortestpath.pdf
$d[v_i] \geq d[v_{i-1}]+w(v_{i-1},v_{i})$ is assumed true. Why is this? Shouldn't it be the other inequality:  $d[v_i] \leq d[v_{i-1}]+w(v_{i-1},v_{i})$ by triangle inequality?

I think the LHS is assumed by argument to be: $d[v_{i}]= \Sigma_{j=1}^{j=i} w(v_{j-1},v_{j})$. Since $d[v_{i-1}]= \delta(s,v_{i-1})$ = $min$$\{w(p) : s \rightsquigarrow^p v_{i-1}\} $  on the RHS, where $w(p)= \Sigma_{j=1}^{j=k}w(x_{j-1},x_{j})$ for any path $p: x_{0}=s, ... ,x_{k}=v_{i-1}$, we have the inequality $d[v_{i}]\geq d[v_{i-1}]+w(v_{i-1},v_{i})$.


Time complexity of insertion in binary search tree Given a binary search tree $T$, we insert $n$  elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$ then we balance $T$. what is time complexity insert $n$ items in such tree?
I think be $O(n)$, but when i want draw a such tree i get stuck.

It can't   be $O(n)$.
Suppose $n=2^k$,and for given $n$ elements, we inserted $\frac{n}{8}$ and $T$ is balanced. Now suppose you insert next $\frac{n}{8}$, But suppose when you inserted
$\frac{1}{2}\frac{n}{8}$ elements that  those make a chain with length $O(n)$. So for next $\frac{1}{2}\frac{n}{8}$    elements you maybe have cost $O(n)$ for each insertion. As a result the time complexity of $n$ insertion is $O(n^2)$.


Questions from Dijkstra's EWD 1300: "The notational conventions I adopted, and why" A link to the transcript of the manuscript: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html

My questions:

What does Dijkstra mean by:

  "Do not introduce priority [precedence] rules that destroy symmetry. I remember how
  much more pleasant the predicate calculus became to work with after we
  had decided to give con- and disjunction the same binding power and
  thus to consider p ∧ q ∨ r an ill-formed formula."?

Specifically: can you illustrate how a precedence rule where conjunction has higher precedence than disjunction would destroy symmetry?

Then, what does he mean by (please note that he uses the "." operator to denote function application):

  "As time went on, I learned to appreciate expressions built with
  operators as a way of avoiding functional notation. We can write the
  difference  a−b  as  dif.(a, b) or exc.(b, a), where min and exc are
  functions of an ordered pair. (I believe that the notion of “function
  of 2 arguments” is now obsolete.) But we can also write the “curried”
  versions (min. a). b and (sub. b). a in which, for instance, sub is a
  higher-order function such that sub. b decreases its argument by b (so
  that sub.(−1) would be the successor function). Functions dif, exc,
  min and sub are different functions and as soon as the operation of
  functional composition enters the game, the distinctions are
  essential. But as long as we don’t do functional composition, the
  choice between the four options is irrelevant and writing the
  expression a−b is a lovely way of avoiding being overspecific."?

Specifically: what is the function exc, and how is it that a-b can represent both exc and min? Am I correct in understanding that min is the minimum function?

Conjunction and disjunction are dual, but if conjunction has higher precedence than disjunction, then dual to p ∧ q ∨ r is (p ∨ q) ∧ r != p ∨ q ∧ r.
As you can see exc is dif with its arguments flipped: exc(x, y) = y - x. min is probably short for "minus", not "minimum".


Why is left recursion bad? In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?

Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser.

Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$  is of the form:

$\alpha \rightarrow \alpha \beta$

with $\alpha$ an element of $V$ and $\beta$ an element of $V \cup \Sigma$. (See the complete formal definition for the tuple $(V,\Sigma,R,S)$ there).

Usually, $\beta$ is actually a sequence of terminals and non terminals, and there is an other rule for $\alpha$ where $\alpha$ does not appear in the right hand side.

Whenever a new terminal is being received by the grammar parser (from the lexer), this terminal is pushed atop the stack: this operation is called a shift.

Each time the right hand side of a rule is matched by a group of  consecutive elements at the top of the stack, this group is replaced by a single element representing the phrase newly matched. This replacement is called a reduction.

With right recursive grammars, the stack may grow indefinitely until a reduction occurs, thus limiting rather dramatically the parsing possibilities. However, left recursive ones will let the compiler generate reductions earlier (in fact, as soon as possible). See the wikipedia entry for more information.


What is the asymptotic behaviour of a sum of powers of three? I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer.

I'm given:
$3+9+27+\dots+3^n$. My first assumption is that $3^n = \Theta(3^n)$. The method we're supposed to use goes something like this:

$3+9+27+\dots+3^n<3^n+3^n+\dots+3^n$

Or I think that's what we're supposed to do here. I'm not sure how to simplify a sequence of repeating $3^n$ in order to find a constant C.

Any help is appreciated.

First, your assumption, I'm more concerned with just finding big oh, since that can be used to find big omega is a bit dangerous. You could indeed easily find a $O()$ upper bound for your sum, $S(n)=3^1+3^2+3^3+\cdots+3^n$ by observing that each term is less than $3^n$ so you could have
$$
3^1+3^2+\cdots+3^n\le \underbrace{3^n+3^n+\cdots+3^n}_{n}=n3^n=O(n3^n)
$$
but that's a huge overestimate (try it for, say, $n=5$) and so will almost certainly not serve as a suitable big-Omega bound*. Instead, you could simply use the formula for a geometric series and get an exact value, but suppose you didn't know that formula (or were prohibited from simply invoking it).

On the way to finding a good estimate, you could always try this helpful idiom: We've written $S(n)=3^1+3^2+3^3+\cdots+3^n$ and so we also have $S(n+1)=3^1+3^2+3^3+\cdots+3^{n+1}$ so
$$\begin{align}
S(n+1)-3S(n)&=(3^1+3^2+\cdots+3^{n+1})-3(3^1+3^2+\cdots+3^n)\\
 &=(3^1+3^2+\cdots+3^{n+1})-(3^2+3^3+\cdots++3^{n+1})\\
 &= 3
\end{align}$$
But we also know that $S(n+1)=S(n)+3^{n+1}$ so we have
$$
3=S(n+1)-3S(n)=S(n)+3^{n+1}-3S(n)=-2S(n)+3^{n+1}
$$
and so with a little algebra we find
$$
S(n) = \frac{3^{n+1}-3}{2}=\frac{3}{2}(3^n-1)
$$
Since we have an exact value for the sum, we can easily see that $S(n)=\Theta(3^n)$. However, if you need to establish explicit constants to show $S(n)\ge c\,3^n$ (for big-omega) and $S(n)\le d\,3^n$ (for big-o) it's not too difficult. (Hint, can you see that you can use any $d\ge 3/2$?)

$^*$As an aside, you might have been misled in your choice of replacements at the very start by the proof that $1^k+2^k+3^k+\cdots+n^k\le n^k+n^k+\cdots+n^k=n^{k+1}$ which does indeed lead to a big-Theta estimate, though for a different sum.


Is unrestricted grammar equivalent to deterministic Turing machine? Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second rule and so on. Else, if match(es) is found, we return to first rule and start of the string and start loop again.
I have 3 questions:
1. Have anybody studied transformations with similar rules?
2. Which machine accepts language corresponding to such grammars and rules?
3. How one can alter described algorithm to make deterministic Turing machine such a corresponding machine?

Such a grammar system is Turing-complete.  I can encode a tag system, and tag systems are known to be Turing-complete.


How many combinations will be generated if below conditions are put? I need a generalized formula for a set having size(s) having below restrictions,

for ex. X = 2,7,11,17,26

I want only the first combination 2+7 & ignore all of the combinations that start from 2+? (2-num combinations only) same for 3-num consider 2+7+11 & ignore all 2+7+?

Formula should be applicable for any set X without size restriction.

$2^{n-1}-1$

Hint: 1) if you are summing with $k$ numbers $x_1,x_2,.., x_k$ note that once you choose upto $k-1$, last selection is forced on you as the next ascending number to $x_{k-1}$.
2) You are allowed to choose first $k-1$ numbers from n-1 numbers


What is an ordered array? I am not able to find a clear explanation about Ordered Arrays. All I know is

  The array is 1-ordered it is in the usual order. (For the
  1st must be less than the 2nd which in turn must be less than the 3rd
  which ... which must be less than the $n$th.)

But what is 2-ordered, 3-ordered... so on array?

Can someone guide me?

Borrowing the definition from Gaurang Tandon's question:

An array $A[1...n]$ is said to be k-ordered if
$$A[i - k] \leq A[i] \leq A[i + k]$$
for all $i$ such that $k < i \leq n - k$.
For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.

I must also say that I've never seen a similar definition before (and I find it to be quite un-useful, but maybe it is important somewhere).
Another definition I have seen, extends the ordering to $k$-dimensional objects. For instance, with two dimensions:

Given vectors $v=(v_1,v_2)$ and $u=(u_1,u_2)$,  we say that $v>u$ in a 2-ordering if
$$v_1 > u_1$$
or if
$$ v_1=u_1 \text{ and } v_2>u_2$$

Then, an array of vectors $v[1...n]$ is $2$-ordered if for every $i$, $v[i]<v[i+1]$ via the above 2-ordering.


Does this shuffle have non-zero probability for all permutations? I was trying to do some code golf, when I created the following algorithm to shuffle a string:

for(;k-->0;y=s,s="")for(var c:y.split(""))s=Math.random()<.5?s+c:c+s;

To explain better what it does, I've recreated it in Python:

import random
str = "Randomize me!"
print('[',str,']',sep='')
temp=""
for _ in range(len(str)): # repeat as many times as the string is long
  for char in str:        # take the string's chars and randomly construct a temporary
    temp = temp + char if random.choice([True, False]) else char + temp
  temp, str = "", temp    # use the temporary as the basis for the next iteration
print('[',str,']',sep='')

Also, per request, here it is in pseudocode:

SHUFFLE(STR)
 0 TEMP ← ""
 1 LOOP STR.LENGTH TIMES:
 2     FOR EACH CHAR ∈ STR:
 3         IF COIN-FLIP
 4             TEMP = TEMP + CHAR
 5         ELSE
 6             TEMP = CHAR + TEMP
 7         END IF
 8     END FOR
 9     STR ← TEMP
10     TEMP ← ""
11 END LOOP
12 RETURN STR

The output looks randomized to me. However, if you only consider one iteration of the algorithm, the first character put into temp is always str[0]. The second character put into temp on this iteration is always str[1], which must be next to str[0] according to the way characters are appended. Therefore, after one iteration, the probability that the shuffled string has the first character outside of the center is 0, and the probability that it is not adjacent to the second character is 0.
I tried to remedy this problem by repeating the shuffle once for each character in the string. Intuitively, it seems to work, but I can't seem to prove that all permutations of the input string can show up.

So, here's the question: do all permutations of the input string have non-zero probability as output from this shuffle?

Yes. Your algorithm can return all permutations.
You can prove it by fixing any arbitrary permutation $\pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $\pi$.

For $i=0$ this is trivial.
For $i>0$: Let $n$ be the lenght of str, $x$ be the character in position $1+n-i$ of $\pi$ (indexing positions from $1$), and $j$ be the index of the first occurrence of character $x$ in str with the additional constraint that $j \ge i$ (this index always exists by induction hypothesis). A string temp that will satisfy the induction thesis (as it will be assigned to str) can be found as follows:

copy the first $j-1$ characters from str to temp (by appending them to temp). In particular this copies the first $i-1$ characters of str which, by induction hypothesis, match the last $i-1$ characters of $\pi$.
prepend the $j$-th character of $x$ of str to temp.
append the remaining $n-j$ characters of str to temp.


Is $\ L = \{ \ w \in \{a, b, c\}^* \ | \ w = uv \ \ and \ \ \#_a(u) + \#_b(u) = \#_b(v) + \#_c(v) \ \} $ regular? I wonder whether the following language is regular:  $$ L = \{ \ w \in \{a, b, c\}^* \ | \ w = uv \ \ and \ \ \#_a(u) + \#_b(u) = \#_b(v) + \#_c(v) \  \} $$ where $\ \#_x(w) $ is the number of occurrences of$\ x $ in$\ w $.

Your language is not regular, since
$$
L \cap a^*bc^* = \{ a^n b c^m : n \neq m \}.
$$
I'll let you figure out why.


Can NP-Hard be converted to NP? I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem.

Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

Also, are NP-Hard problems inter-convertible?

The picture I always visualize for this is the one featured on here on the Wikipedia page for NP-Completeness. The definition of NP-Hard is that it is the set of problems to which all NP problems can be reduced in polynomial time, so, for example, the bounded halting problem - does a Turing Machine $M$ halt within $k$ steps, is strictly not in NP, because there is no way to check in polynomial time whether a Turing Machine halts in $k$ steps. However, all problems can be converted to the bounded halting problem very easily, simply by building a Turing Machine which ostensibly solves the problem and asking whether it halts in some appropriate amount of time.

This answers your first question: not all NP-Hard problems are in NP or can be reduced to them. As for the second: Some NP-Hard problems can be converted to one another. For example, the EXP-TIME class, which can be though of as the next class beyond P, has EXP-TIME-Complete problems just like NP has NP-Complete problems, and there are classes even beyond that, indefinitely.


Finding k'th smallest element from a given sequence only with O(k) memory O(n) time Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with "max"; but it cannot update quickly; Means that if we consider max then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How do I solve this problem?

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use  a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat.

This takes $O(k * n/k) = O(n)$ time and $O(k)$ space.


Thoughts on definition for disadvantage of concurrent processing? I'm a Computer Science student currently learning about concurrent processing. I found the benefits and disadvantages in my book vague, did some online research and put together a more detailed way of defining the disadvantage of concurrent processing; thoughts and corrections are appreciated.

Book version: "The drawback is that if a large number of users are all trying to run programs, and some of these involve a lot of computation, these programs will take longer to complete."

My version:
Using concurrent processing on multiple users running the same program, means no one can finish until everyone has nearly finished. This is inefficient compared to consecutive processing where the last user would finish at the same time as the last user in concurrent processing, but some users would finish significantly earlier. However the scaling of this inefficiency is limited by the amount of threads, because concurrent processing only switches between the first process of each thread queue. The process at the beginning of each thread can change with the use of interrupts though.

Do you think I elaborated on the book properly, or misunderstood it?

I'm studying for the same A Level and have found that deadlock, starvation, race conditions and the overhead affiliated with coordinating simultaneous threads are reasonable, in-depth disadvantages of concurrent processing

Deadlock occurs when each process/thread is waiting for another to finish (meaning that no process is ever able to complete). For example, this happens with cyclic dependencies (e.g. when process A needs B which needs C which needs A).

Starvation is when a process is always denied a resource that it needs, resulting in the process never completing.

Race conditions are when two processes are sharing the same storage location (i.e. variable) and the result of operations depends on the order in which they are ran.

Overhead - there is additional processing overhead to coordinate the individual threads (and combine their results). This can mean, for some problems, a single thread is more efficient than multiple.

Hope I've helped clarify things for anyone who was also confused with this topic,

Josh

Sources:

Cambridge Elevate OCR A Level Textbook

Rensselaer Polytechnic Institute Lecture Notes


Is MIN or MAX-True-2-XOR-SAT NP-hard? Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?

Let:

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,\\
\forall_{C_i} \left.C_i=(p \oplus q)\right|_{\left(p\in \mathbf x \vee\neg p\in\mathbf x\right),\left(q\in \mathbf x \vee\neg q\in\mathbf x\right)}
$$

The $\text{2-XOR-SAT}$ problem is to find a satisfying assignment of $\mathbf x$ that would make $\Phi\left(\mathbf x\right)=T$. This is in $P$, as it can be encoded in a set of linear equations mod $2$.

The $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ problems are to maximize or minimize the number of true values in $\mathbf x$, respectively, subject to the constraint that $\Phi\left(\mathbf x\right)=T$.

Build an implication graph, in the style of solving $\text{2-SAT}$: each literal gets a $x_i$ node and a $\neg x_i$ node. Each clause is turned into implications, each implication gives a directed edge from the antecedent-node to the consequence-node.
Collect all the connected components of this graph.
Each connected component will have only $2$ states: since each relationship is of the forms $x_i=x_j$ or $x_i \ne x_j$; this means if you assign even a single variable, the entire component will be force-assigned. This means you only have $2$ choices for each component.
For each connected component, greedily choose the assignment state that will increase (for $\text{MAX}$; decrease for $\text{MIN}$) the truth values in $\mathbf x$.


Decide if L is regular or not and argue it. Trying to use Pumping Lemma Part (a): Let $L = \{x \in \{0,1\}^* \mid  \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$.

So I want to use the pumping lemma. But I'm having a hard time choosing a string so that I can show that it is not regular.

I've been thinking about how I could use something like the string, s, = $0^{3p}1^p$. But I do not see how you use that fact (I would like to show that xyyz would equal $0^{4p}1^p$). This route seems unfruitful. So any help would be nice.

Part (b): Let $L = \{x \in \{0,1\}^* \mid \exists k \in \mathbb{N}, \#0(x) + \#1(x) = 2k\}$.

Again stuck on this problem. My original approach was to leverage the fact that the parity is the same on the 0s and 1s (if one is even, then so does the other and vice versa. Same for odd parity.)

Again, this does not seem to be working.

(a): Recall that regular languages are closed under complement, i.e if $L$ is regular, so is $L'$. ($F_{L'} = Q_L- F_L$)

Assume that $L$ is regular.
This follows: if $L = \{x \in \{0,1\}^* \mid |x|_0 \neq 4.|x|_1 \}$ is regular, then so is $L' = \{x \in \{0,1\}^* \mid |x|_0 = 4.|x|_1\} $

Now you should show that $L'$ is not regular. And that gives you a contradiction.

(b) You can construct the following DFA for this.


Decision tree complexity of deciding whether array is "zigzag" I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

  Input: an array with $n$ numbers.

  Output: boolean answer for the question if there exist $1\le i\le j\le n$ so that:

  All the elements in the array between $1$ and $i$ are in ascending order.
  All the elements in the array between $i$ and $j$ are in descending order.
  All the elements in the array between $j$ and $n$ are in ascending order.
  We call this type of array a zigzag array.

I have these ideas: in general, in order to find an upper bound I am looking for an efficient algorithm. For lower bound I am using the decision tree model. For example: in order to find the lower bound for comparison sort algorithms of $n$ numbers, we have $n!$ leaves on the binary decision tree, so we have $n!$ different possibilities for sorting $n$ numbers, which results in an $Ω(n \log n)$ lower bound.

For upper bound I am thinking about just moving from the first element step by step and finding if the array is a zigzag or not, so upper bound is $O(n)$

Lower bond: I don't know how many different possibilities of zigzag arrays of length $n$ we have, so i don't know how so solve it. If one of you has a different method of finding the lower bound I will be happy to know.

You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument. Whenever the algorithm compares two elements $s<t$, the answer is always $A[s]<A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is $A[n-1]>A[n]$.

It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A[1] < A[2] < \cdots < A[n-2] < A[n] < A[n-1]$). Now suppose you make less than $n-3$ comparisons. In particular, if you think of your comparisons as edges on the graph on vertices $\{1,\ldots,n-2\}$ (we ignore comparisons to $A[n-1]$ or $A[n]$), then the graph is disconnected. In particular, there are vertices $s<t \leq n-2$ which weren't compared. It is therefore consistent that $A[s] > A[t]$ whereas $A[t] < A[n-1] > A[n]$ (for example, the order could be $A[1] < \cdots < A[s-1] < A[t] < A[s] < \cdots < A[n-2] < A[n] < A[n-1]$), in which case the array isn't zigzag since it has two disjoint decreasing parts. Hence the algorithm doesn't know the answer.


Need help to come up with definitive proofs with regard to Planar Graphs I was working through a few problem sets and came across this question

Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle consisting of three edges).
Question 1: Into how many regions does a representation of the Planar Graph $G$ Split the plane?

Incase of this question, since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$  and got my final answeras $2(v+2)$.

Question 2: Suppose the vertices of the planar graph G are colored in three colors. A region is called to be tricolored (or bicolored) if its vertices are colored in exactly three (or two) different colors. Similarly, a monocolored region is the one with all its vertices colored in exactly one color. Prove that the number of tricolored regions is always even no matter how the vertices are colored.
(Hint: If you place a new vertex inside a region (triangle) of G and connect it with all vertices of that region, then all regions are still triangles and the parity of the total number of regions stays the same.)

This question seemed very straight-forward to me on account of my previous answer. Since I derived the value $r = 2(v+2)$ which would always remaining even while incrementing $v$. I don't really understand the point of the Hint or maybe what exactly we have to prove here.
Any help with regard to the same would be appreciated. Thanks!

Since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$  and got my final answer as $2(v+2)$.

The final answer should be $2(v-2)$.

  Since I derived the value $r=2(v-2)$ which would always remaining even while incrementing $v$.

You are right that $r$, the number of regions will always remain even since $r=2(v-2)$. However, question 2 is asking you to prove "the number of tricolored regions is always even no matter how the vertices are colored.".

  I don't really understand the point of the Hint or maybe what exactly we have to prove here.

The hint is meant to give you a clue how to reduce the number of vertices.  The proof (or my proof) is quite easy and direct once you know it. I will let you figure out your proof.