How can we design an efficient warehouse management program? Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box stack is 1400 mm. There are 3 box sizes with varying heights (other dimensions are the same). The heights of the boxes are 170 mm, 200 mm and 270 mm. An item is possible to place only in one type of box. All boxes are compatible to stack with each other. There are only two objectives: the number of completed pallets should be minimal, and the height difference of towers of boxes can be at most 500 mm.

The goal is to design a warehouse management program, which takes the order as an input, that is, the information of ordered items and how many boxes has been ordered. The program should determine how many boxes of each product should be stacked on a determined pallet and on a specific stack. A single product is always associated with only one box type.

How should one construct this kind of a program? I'm looking for general design guidelines and the methods to achieve the desired result. All tips and advices are welcome. I appreciate your effort.

It looks like what you have is a variant of the knapsack problem.  However, you have an advantage that, rather than trying to optimize one "sack", you're simply trying to minimize the number of sacks (or in this case, pallets.)

I would have my program start by adding up the total height of the boxes I have to stack, and dividing it by the total height I could get out of each pallet if I could pack it perfectly (in this case, 7000mm).  If there's no possible way I could fit the boxes I'm given on less than three pallets, for example, I'm better off knowing that to begin with.

So once I've calculated my P, the number of pallets I may be able to fit my boxes on (if I'm lucky and calculate well) I'm going to start distributing my biggest boxes first.  I've got 5*P stacks to fill; I'm just going to go around them, always choosing the stack that's currently the lowest height to put the next box on.  I'll continue that as I run out of the biggest boxes and move on to the next biggest.

If I'm fortunate, this is all I'll need to solve the problem.  If I'm less fortunate, I'll have to have code that explores to see if swapping boxes around creates the room I need.  This is where the problem gets hairy; there's only so much you can do other than just plain trial and error.

In planning for that contingency, I might be well-advised to do some searching to see if there are any "perfect" stacks that can be made with the box sizes I'll have to work with (for instance, 7 of the 200 mm boxes make a perfect stack).  Any "perfect" stacks that I can make simplify the task of figuring out how to swap boxes between the remaining stacks ... or, regrettably, accepting that there's no way to swap boxes around so that they fit on our hoped-for number of pallets.


Ideas for CS-related challenge for teams of high school students? I am helping design a CS-related activity for a Let's Talk Science competition, which promotes STEM amongst high school students. In the competition, teams of six students will move from station to station, trying to complete each as quickly as possible.

One station might give the team a metre stick, then ask them to measure the height of a building. (This can be solved by using similar triangles to estimate the building's height.) Time penalties are added to the team's completion time depending on how close their answer was.

My constraints are thus:

Most students won't have CS/programming knowledge
Challenge should not require a computer
Idea should challenge teams of six students for 15-20 minutes
Challenge must have clear answer that can be objectively scored (not judged)

One reasonably good challenge presents a sentence encoded with a Caesar cipher, then asks the students to decode it. The person running the station give a short explanation of what a Caesar cipher is, then leave the teams to decode the text. Time penalties are awarded based on correctness -- each incorrect character adds a 30-second penalty.

The Caesar cipher idea has been used often in the past, however, and I'm trying to develop something novel. I have been through the various activities on CS Unplugged, but none appealed to me -- the exercises I saw were generally aimed at illustration and not suitable for competition, were too simple, or required too much explanation of background knowledge.

Do you have any ideas on what would make a fun CS-related challenge for teams of six high school students?

Thanks!

One activity that I really liked is the following: devise a way to communicate a short text message across a long soccer field, without using electronics and without shouting.  You can use any large field or open area that is large enough that they won't be able to hear each other by shouting, yet provides line of sight.

The idea is that the team will get together in advance to devise a communication method.  Then, half of the team stands at one end of the field, and the other half at the other end.  The first half is given a message, and they have to communicate it to the other end.  They are scored based upon the accuracy of the received message and how long it takes them.

This is a very cool exercise.  It gives them a lot of opportunity for ingenuity.  You can give them a few materials and they can select a signaling scheme -- maybe use flags, or mirrors, or large objects, or you name it.

They'll have to devise an efficient method of encoding text into something they can signal, and a good signalling algorithm.  It's their interests to trade off efficiency for robustness (redundancy to deal with errors in receiving the data).  They might choose to use a forward error correcting code (e.g., add some redundancy), or they might choose to use an acknowledgement/retry mechanism (where the recipient can signal "didn't get that, please try again").

Another thing that is nice about this exercise is that it provides an opportunity for teamwork and brainstorming and cooperation within their team.  It's always more fun to do this stuff together with a few others than to do it on your own.

If you like, you can point out the rich history of signalling schemes that have been used in the past: semaphore, Morse code, the signal fires used by Alexander the Great, etc.

If you don't like that one:

CS Unplugged is one of the best resources.  If they don't have anything you like, this might be pretty tough.

By the way, please keep in mind that competition has mixed effects, some good and some bad.  Competition is good for motivating for some students but at the same time, some students find competition demotivating.  Also, there is a gender gap here; competitions are more likely to turn off women than men, which might not be desirable in an activity for high school kids, given that there are already enough barriers keeping women out of computer science.


Label groups of vertices in a graph in an efficient manner without BFS/DFS I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in \mathcal{E}$. I define a (global) threshold $T$ such that if $w((u,v)) < T$ the two vertices $u,v \in \mathcal{V}$ are in the same group: $g \in \mathcal{V} \rightarrow \mathbb{Z},   g(v_1) = g(v_2)$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.
The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $w((u,v)) < T$ for any of the edges and neither $u$ nor $v$ have been assigned a group (for example $g(u) = g(v) = -1$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$. If at some point $w((x,y)) < T$ and $w((y,z)) < T$, but $g(x) \ne g(z)$ then set $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ and $h(g(z)) \leftarrow h(g(x))$. After this procedure it should hold: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ if there exists a path from $u$ to $v$: $\pi = e_1,...,e_n$ such that $w(e_i) < T$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $|\mathcal{V}|$ memory for each array $g,h$. Is there a way to optimize this further?

As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).


How do I simplify this boolean expression? I have constructed truth tables to prove that:
$ABC + ABC'+ AB'C +A'BC = AB+AC+BC$

How do I prove it by simplifying the expression? I know that I can simplify:  $ABC + ABC' = AB(C+C')=AB$. However I can't repeat this for $AB'C$ or $A'BC$, to get the answer I desire.

I'm fairly new to boolean algebra and have tried to use the basic identities to figure it out, but can't seem to get there.

$
\begin{align}
ABC + ABC' + AB'C + A'BC = \\
ABC + ABC + ABC + ABC' + AB'C + A'BC =  & & & \text{(2x Idempotency)}\\
AB(C + C') + ABC + ABC + AB'C + A'BC = & & &\text{(Distribution)}\\
AB + ABC + ABC + AB'C + A'BC = & & & \text{(Negation)}\\
AB + (AB + AB')C + (AB + A'B)C = & & & \text{(2x Distribution)} \\
AB + (A(B+B'))C + ((A+A')B)C = & & & \text {(2x Distribution)} \\
AB + AC + BC & & & \text{(2x Negation)}
\end{align}
$

I'm not proficient at this kind of derivations so please correct any notation/terminology


Turing machine with repeated strings How would I go about making a Turing machine to accept the following language L?

$$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$

I was thinking counting the number of symbols in the input string and then dividing by three to find the beginning of each instance of w and then testing if each instance is the same, but this seems a bit roundabout.

I feel like there is a way by marking the first three symbols and then moving the 2nd and 3rd markers until the strings in between them are the same but I'm having a hard time articulating this into an algorithm.

Can anyone point me in the right direction?

From the comment: a quick way is to think that you are working on a two-tapes TM (initially the second tape is empty). You start placing $abc$ on it; then continue scanning it expanding the $a$, $b$ and $c$ substrings ($aabbcc,aaabbbccc,aaaabbbbcccc,...$) until the length of the second string matches the length of the input (or reject if you "overflow" it).
During a scan simply replace the first $b$ with 1 $a$, the first 2 $c$s with 2 $b$s and append 3 $c$s at the end.

   Input: 011010110101101
2nd tape: <empty>
  Scan 1: abc
  Scan 2: aabbcc
  Scan 3: aaabbbccc
  Scan 4: aaaabbbbcccc
  Scan 5: aaaaabbbbbccccc

At this point it should be easy to check if the three subwords are equal ... finally think how to "merge" the second tape into a single one (just add extra symbols to the tape alphabet ...).


Can you recognize or decide if a Turing Machine has an infinite sized language? That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?

Similarly, can you recognize or decide if a Turing Machine has an uncountably-infinite language?

To elaborate somewhat on Yuval's comment:

(1) Some languages have an infinite number of strings, some do not. This makes the property non-trivial, and Rice's theorem says that recognizing whether the language of a Turing Machine has a non-trivial property is undecidable. This problem is undecidable.

(2) All languages are countable; none are uncountable. This makes the property trivial. Deciding whether the language of a TM has a trivial property is always decidable: if it's a property all languages have, then answer yes; if it's a property no languages have, answer no.

(A word of general caution, though it doesn't apply here. Rice's theorem applies only to properties of languages themselves, not properties of the TMs that might accept them. This is an important distinction. Rice's theorem only works for properties that have to do with the language and strings it contains.)

For reference: Rice's Theorem


Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It is then stated that using the pumping lemma, it can be shown that if 01(001)^n01 is accepted for n=0,1,2,3,4,5 then all strings of the form 01(001)*01 must also be accepted.
I know of the pumping lemma but do not see how the next leap has been made. Why is it sufficient to only test n up (number of states) - 1?

Let the automaton have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$, and suppose that $|Q| = n$. Denote the language that it accepts by $L$.
Suppose that $xy^iz \in L$ for $i = 0,\ldots,n-1$. Denote $p_i = \delta(q_0,xy^i)$. We consider two cases:

The states $p_0,\ldots,p_{n-1}$ are all different. In this case, $Q = \{p_0,\ldots,p_{n-1}\}$, and so $\delta(q,z) \in F$ for all $q \in Q$, implying that $\delta(q_0,xy^iz) \in F$ for all $i$, and so $xy^iz \in L$ for all $i$.
For some $j < k$, we have $p_j = p_k$. It follows that the sequence $p_i$ is eventually periodic, and so again $xy^iz \in L$ for all $i$.


How to prove the following xor equation? In a test paper, a question is given as :

Let, x1^x2^x3^x4 =0 where x1, x2, x3, x4 are Boolean variables,and ^ is the XOR operator.

Which one of the following must always be TRUE?
(A) x1x2x3x4 = 0
(B) x1x3+x2 = 0
(C)  x1'^x3' = x2'^x4'
(D) x1+x2+x3+x4 = 0

+ is OR and concatenation is AND operator.

Correct answer is C, which I guessed because when all booloean variables are 1, then, neither A,B, or D will hold,But what is the correct way to get to option C?

(I use the symbol $\oplus$ here because $\wedge$ is mathematically used for conjunction ("and") instead of exclusive-or)

First we rearrange the terms,
\begin{align}
 x_1 \oplus x_2 \oplus x_3 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 \oplus x_2 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 &= x_2 \oplus x_4
\end{align}
Then use $a \oplus b = a' \oplus b'$ to get (C).
$$ x_1' \oplus x_3' = x_2' \oplus x_4' $$


Doubt on Karger's Algorithm for Min-Cuts I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My doubt is in the 2nd part of the question.

2nd part of the question asks to find the probability of contracting 2 vertices in each step of the algorithm.

My approach is that - Since contracting 2 vertices is equivalent to contracting an edge, because every time we contract an edge, we are contracting 2 vertices into 1, so to answer the question, I can just find the number of edges at each step 'i' in my algorithm and and find the probability.

For example, if the number of edges in step 'i' of my algorithm run is 5, I can say that Probability(Contracting 2 vertices) = 1/5. since we can pick anyone of the 5 edges.

Please help me out in finding if my approach is right or wrong.

The approach is right, however, you are missing a little detail. Karger's algorithm runs on multigraphs. Hence, two vertices can have more than one edge between them and hence, the probability of contracting them the disjoint sum of the probability of contracting any of the edges between them which is the number of edges between them over the total number of edges in the graph.


Tight upper bound for forming an $n$ element Red-Black Tree from scratch I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order statistics can be done in $O(lg(n))$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $i$ th order statistic can be achieved in the $O(n)$ time in the worst case.[ where $n$ is the number of elements].
Now I felt like finding a tight upper bound for forming an $n$ element Red-Black Tree so that I could comment about which alternative is better : "maintain the set elements in an array and perform query in $O(n)$ time" or "maintaining the elements in a Red-Black Tree (formation of which takes $O(f(n))$ time say) and then perform query in $O(lg(n))$ time".

So a very rough analysis is as follows, inserting an element into an $n$ element Red-Black Tree takes $O(lg(n))$ time and there are $n$ elements to insert , so it takes $O(nlg(n))$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.
I tried to attempt a detailed analysis as follows (but failed however):
Let while trying to insert the $j=i+1$ th element the height of the tree is atmost  $2.lg(i+1)+1$. For an appropriate $c$, the total running time,
$$T(n)\leq \sum_{j=1}^{n}c.(2.lg(i+1)+1)$$
$$=c.\sum_{i=0}^{n-1}(2.lg(i+1)+1)$$
$$=c.\left[\sum_{i=0}^{n-1}2.lg(i+1)+\sum_{i=0}^{n-1}1\right]$$
$$=2c\sum_{i=0}^{n-1}lg(i+1)+cn\tag1$$
Now
$$\sum_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+...+lg(n)=lg(1.2.3....n)\tag2$$
Now $$\prod_{k=1}^{n}k\leq n^n, \text{which is a very loose upper bound}\tag 3$$
Using $(3)$ in $(2)$ and substituting the result in $(1)$ we have $T(n)=O(nlg(n))$ which is the same as the rough analysis...
Can I do anything better than $(3)$?

All the nodes referred to are the internal nodes in the Red-Black Tree.

To construct a red-black tree on $n$ elements you need to spend time $\Omega(n \log n)$, if you are only allowed to compare the elements' keys.
To see this notice that an in-order visit of any BST visits the nodes in increasing order of their keys.
If you were able to construct a red-black tree in time $t(n) = o(n \log n)$ then you'd also be able to sort $n$ elements in time $O(t(n) + n) = o(n \log n)$, contradicting the lower bound on sorting for comparison-based algorithms.
On the other hand, if the elements are already sorted then you can build a red-black-tree in time $O(n)$: just recursively build a balanced BST, if the last level is incomplete color its nodes as red, and color every other node black.
This requires linear time since the time complexity of the recursive algorithm can be described by the recurrence equation $T(n) = 2T(n/2) + O(1)$.


Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$? Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel like I am not getting the big picture. Right now I am just trying around until I find something that seems plausible.

Here is what I have tried so far:

Problem: Prove that $T(n) = \theta(n^2)$ where $T(n) = \frac{n(n+1)}{2}$

My Approach: I know that T(n) is $\theta(n^2)$ if $T(n) = O(n^2)$ and $n^2 = O(T(n))$ both apply, if I can prove both, the statement is therefore true.

In order to proof  $T(n) = O(n^2)$, I check if $\lim\limits_{n\to \infty}\frac{T(n)}{n^2}$ exists, which it does: $\lim\limits_{n\to\infty}\frac{n(n+1)}{\frac{2}{n^2}} =\lim\limits_{n\to\infty} \frac{\frac{1}{2}n^2+\frac{1}{2}n}{n^2}=\lim\limits_{n\to\infty}\frac{1}{2}+\frac{1}{2n}=\frac{1}{2}$
To prove that $n^2=\theta(T(n))$ I argue that  $n^2 \le 2 * \frac{n(n+1)}{2}=n^2+n$
and that therefore, for all $c =2>0$ and for all $n \ge n_0 = 1:n^2 \le c *T(n)$ applies $n^2 = O(T(n))$

It follows from the definitions that $f(n) = O(g(n))$ iff $g(n) = \Omega(f(n))$, in the same way that $a \leq b$ is equivalent to $b \geq a$. Therefore in order to prove $f(n) = \Theta(g(n))$, it suffices (and necessary) to prove $f(n) = O(g(n))$ and $g(n) = O(f(n))$.

The "quick" way to prove that $\binom{n}{2} = \Theta(n^2)$ is
$$
\binom{n}{2} = \frac{1}{2} n^2 + O(n) = \frac{1}{2} n^2 + o(n^2) = \Theta(n^2),
$$
where the last equality is a general result: $cf(n) + o(f(n)) = \Theta(f(n))$.

In practice, we take the following fact as well-known: if $P$ is a polynomial whose leading coefficient is positive then
$$ P(n) = \Theta(n^{\deg P}). $$
Using this, you can immediately deduce $\binom{n}{2} = \Theta(n^2)$.


Stochastical algorithm We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$.
We want to generate a uniform distribution on the set S = $\{0, 1,..., n-1\}$.

Which algorithm gives with probability $1/n$ the value $i\in S$. And how many bits are needed.

If $n$ is a power of two, then you can simply determine the value $i$ by determine bit per bit in the binary representation. So if $n=8$ then you ask your source 3 times. Suppose you get as result $1,1,0$ then you would map this event to the event that you have selected $i\leftarrow\text{bin}(110)=6$. Clearly you need $\log n$ bits.

If $n$ is not a power of two, then things a are more tricky You can definitely can get an approximate uniform distribution, if you follow the method above. Say you sample $k$ bits, and you get the $k$-digit binary number $b$, then you can pick
$$i\leftarrow \frac{b}{2^k}n.$$

The more bits you sample, the closer you approach the uniform distribution. I am sure there are more involved methods for case wehere $n\neq 2^k$


When an algorithm says Summation this, and Integral that, what does it mean in coding terms? I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me.

I'm currently reading GPU Gems by nvidia and I have a question. It uses Sigma, as in summation, and integral a lot, but when look at the implementation of some of these algorithms, for example, Perlin noise, I can't find any sort of "summation" i.e.:

sum = 0
for i in range(x):
    sum += f(i)

They just convert the Sigma's formula to code. As for integral, I was never very good at them so I have a very weak foundation in them --- Therefore I can't even close to imagine how to convert an integral from an algorithm to code. I know integrals are two things: the area beneath the curve, and the reverse of the derivative --- But how can you derive an algorithm?

For example, this is from the Worely noise algorithm. How do you translate it to code, like Python, or anything?

I'm not asking for code, just explanation. And I hope this is the right place. Thank you.

You are probably looking at a rather mathematical sketch of an algorithm. There are two general roads to implement non-trivial mathematical expressions such as series, integrals, and differential equations.

If you want exact, potentially symbolic results you have to simplify "complex" expressions into closed forms on paper, and/or employ computer algebra.
If you are satisfied with numerical, potentially approximate solutions, you want to employ numerical algorithms, including error estimations.


Multivalued, partial evaluation Everybody says that Valuation is a truth value assignment to all variables in the formula.

How do you call the valuation when some (neither single yet nor all) variables are
assigned a value?
Truth value implies that variables are binary. How do you call the multivalued
case?
I know that Haskel uses the term "partial application". If "partial application" is supplied with optimization, they call it "partial evaluation". I am not sure whether boolean valuation falls into the application or evaluation or second category?

ps, Dec 2013

Is it right that single variable assignment is called Restrict operation? I read Restrict(Function F, variable v, constant k) is defined as "Shannon cofactor of $F$ w.r.t. $v=k$" in Berkly lectures.

Here's what I'd use:

partial valuation
value
"partial evaluation" means something different; for instance, if you have the expression (3+x)*y and you learn that x=5, transforming it to 8*y would be an instance of partial evaluation.  Partial evaluation is a technique; it is not a special kind of a valuation.


Bounded occurrence 3D matching problem It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching.

Informally, Given a set of triples $F$ of elements such that each element occurs exactly in two triples, Is there a subset of $F$ such that each element occurs in exactly one triple?

  Is this decision problem solvable in polynomial time? Is it $NP$-complete?

It is solvable in polynomial time.

Convert an instance of Bounded Occurrence 3DM to a cubic graph.

For each triple, create a vertex

For each element, there are exactly two triple containing it. So, there are exactly two vertices corresponding to these two triples. Connect these two vertices by an edge.

Now, a solution to your problem is an independent vertex cover.

A graph has an independent vertex cover iff. it is bipartite. Checking for bipartiteness can be done in polynomial time.


Greedy approach suggestions for assigning objects Suppose there are three categories of people.
Type X, Type Y, Type Z.
In each type, there are two objects of subtype Type 'a' and type 'b'.
For example.
X: a1 , a2 , b1 , b2
Y: a3 , a4 , b3 , b4
Z: a5 , a6 , b5 , b6
Each object of type 'a' should be assigned with an object of type 'b'. But it is desirable not necessary to assign a type 'a' with type 'b' from different classes (X, Y, Z).
In this example, the optimal solution would be:
a1 with b5 ,
a2 with b6 ,
a3 with b1 ,
a4 with b2 ,
a5 with b3 ,
a6 with b4 .
Non -optimal solution would be :
a1 with b5 ,
a2 with b6 ,
a5 with b1 ,
a6 with b2 ,
a3 with b3 ,
a4 with b4 .
(Non -optimal because a3 and a4 are assigned with b's of same type Y)
If we generalize, there can be n- number of Types (X,Y,Z, .....and so on) with different number of a's and b's in each (but total number of a's = total number of  b's).
How to find an optimal solution?

This problem reduces to finding a maximum matching in a bipartite graph, which can be done easily by e.g. the Ford-Fulkerson algorithm. You construct the graph as follows:
Take all elements of type $a$ on one side and all elements of type $b$ on the other. Then, for any two elements $a_i,b_j$, draw an edge between them if they do not belong to the same category.
If there is a matching in the set with only, say, $k$ pairs belonging to the same category, then we can find a matching in our graph on $m-k$ edges, where $m$ is the number of a's (or b's).


Pseudocode algorithm to check encoding of Turing machine My question goes like this:

  Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is correct, that $\delta(q_a,a)$ is undefined for every symbol $a$, etc.

Unfortunately, I got no idea how to tackle it. I have a clue that induction might be needed, but it didn't help me. Any help will be appreciated. Thank you!

The encoding $\langle M \rangle$ of a TM, has a specific structure. All you need your algorithm to do, is to verify that the input string $w$ possesses the "correct" structure of a valid encoding.

Note, that there are many possible ways to define the encoding $\langle M \rangle$. For instance one possible such encoding, for $M=(Q,q_0,F,\Gamma,\Sigma, \sqcup, \delta)$ is
$$ 1^{|Q|}01^{|\Gamma|}01^{|\Sigma|}0\delta_100\delta_200 \ldots \delta_{last}000$$
where each $\delta_i$ is one line of the transition function, such that if, for instance $\delta(q,a) = \{ p, b, d\}$ we encode it as $1^q01^a01^p01^b01^d$ with $d$ being the direction where the head moves, say Left=1, Right=2, Stay=3.

Remember that other encodings are possible, it depends on your definition!

However, assuming the above definition, I think you should be able to come up with an algorithm to verify if the encoding is valid or not.

For instance, is the input $w=0000000$ valid ?

   no, because it contains no states $Q$, etc.

What will you need to check for validity? Basically, only the following

   0. that the formatting looks correct (no extra characters, ends with 000, etc,)
 1. that all the sets exist (and behave correctly, e.g., $|\Gamma|>|\Sigma|$)
 2. that $\delta$ is well defined (think, what does this mean)...


How can you find all unbalanced parens in a string in linear time with constant memory? I was given the following problem during an interview:

Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.

I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.
Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)
I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.
Can anyone clarify the solution she suggested?

Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $\Theta(\log(n))$ memory to store an index into a string of length $n$.

You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.

  using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren

So what does this stack contain? It's never going to contain () (an opening parenthesis followed by a closing parenthesis), since whenever the ) appear you pop the ( instead of pushing the ). So the stack is always of the form )…)(…( — a bunch of closing parentheses followed by a bunch of opening parentheses.

You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.

If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.

If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $\Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.

In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.

The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.

Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).

Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.


MSB and LSB in floating point number What is MSB and LSB in significant of a floating point number? If I have a significant for example 0011010000 (half-precision) but 1. bit is implicit what is MSB: 0 or 1? In this case LSB is 0, because it is on the end of significant?

In the whole floating point number the MSB is a sign bit and LSB is in the mantisa (last bit).

In all floating point formats with exception of 10 byte IEEE real the mantissa MSB of normalised number is not stored because it is implicitly set to $1$ (and used in calculations).

So in the case of your significand (mantissa) $0011010000$ the MSB is $1$ (implicit) and LSB is $0$ (explicit).


design cache system using queuing theory If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS  & a cache size will have a count). How can one use queuing theory to estimate the best possible cache size ?

You first need to establish the access speed of the cache, depending on the cache size (usually larger cache -> slower speed, because of physics). You also need to determine the energy consumption of a larger cache, which will lead to increased heat, which will lead to lower clock speed (again, because of physics). Then you need to find the cost of a larger cache - if I can gain more for less money using different methods than increasing the cache size, I'm not going to increase the cache size (because of economics).

Histograms of existing applications are of limited use, since there are plenty of algorithms that adapt to the cache size - with a cache four times the size you would have completely different access patterns. So you are going to use simulations.

I wonder why I didnt't mention queuing theory here.


Positioning items to maximize separation Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \le r_i$. My problem is: given a specific item s, how do I compute the maximum gap possible to the right of s? By maximum gap to the right of s I mean the distance between s and the next item to its right.

Mathematical Description:

More formally, given $s \in [n]$, and $(l_i,r_i)$ for $i\in[n]$ I want to find
 $$f(s) = \max_{p_1,\dots,p_n} p_t - p_s$$ subject to
\begin{align*}
1)\,& l_i \le p_i \le r_i\, \forall\,i \in [n] \\
2)\,& \forall\,i\ne s,t, \text{ either } p_i \le p_s \text{ or }p_i \ge p_t \text{ (there is no item between s and t)}
\end{align*}

In the absence of the second constraint the problem would have been a linear program. The second constraint makes it difficult.

I know how to model this question as an integer program (see https://bit.ly/2Jhf7kJ), but I am interested in an actual algorithm.

Given a specific item $s$, how do I compute the maximum gap possible to the right of $s$? By maximum gap to the right of $s$ I mean the distance between $s$ and the next item to its right.

This is much more useful than the mathematical description.

First note that items that are to the left of $s$ don't hurt us in any way, so if it is possible to put an item to the left of $s$, do so. Then we note that if an item can't go to the left of $s$ we want it as far to the right as possible.

The conclusion? Each item is always at either its left or right boundary, with the exception of $s$. And once you know the position of $s$ you'll also know all the other positions.

So just loop over each interesting position of $s$, discard all items that can go on the left, and then choose the closest item on the right. Out of these closest items, which ever is the furthest is your answer (or well, it's associated position of $s$).

Now what are the interesting positions of $s$? Well it's each time you can put another item to the left of $s$. So it's all the left boundaries (plus one epsilon) of items that fall within $[l_s, r_s]$, and $l_s$ itself.


Does a verifier means decidability If, for example, there is a problem B which have exponential time verifier - a verifier that verify on exponential time - Does it 100% means that B decidable?

On one hand I thought - If there is a verifier - why can't I just decide for each input - using the verifier? On the other hand - from what I know - if it doesn't halt we wouldn't know it...

Thanks.

I'll start with an intuitive explanation as to why $B$ is decidable. Given input $x$, we can start trying every possible witness $y$ and check whether the verifier $V$ accepts $(x,y)$. This is a semi-algorithm, since it doesn't necessarily halt.

However, we note that since $V$ has exponential running time, then considering witnesses that are "too long", i.e. so long that $V$ won't be able to read all the witness, is irrelevant. So we can in fact stop after a bounded number of witnesses, which makes our procedure a halting algorithm.

Now let's formalize this.

Let's assume that the language $B$ has a verifier $V$ that runs in time $f(n)$ for some function $f$ (in your question, $f$ is an exponential function, but this is not important). A crucial property of $f$ is that it's computable. That is, given $n$ we can compute $f(n)$. It is easy to see that functions such as polynomials and exponentials are computable.

Since $V$ is a verifier for $B$, then we have can write the following:
$$B=\{x: \exists y \text{ such that } (x,y)\in L(V)\}$$
where $V$ has the property that given input $(x,y)$, $V$ halts in time at most $f(|x|)$.

We now make the following key observation: if $V$ accepts $(x,y)$ for some $y$, then there exists $y'$ such that $|y'|\le f(|x|)$ such that $V$ accepts $(x,y')$. That is, if there is a witness, then there is also a "short" witness.

This observation is correct since if $y>f(|x|)$ then $V$ cannot read more than $f(|x|)$ letters of $y$, so it's enough to consider a prefix of $y$.

From this it is easy to see why the procedure we described above works.


Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.

Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in V$) and a finite set of equalities of the form $x=a$ (where $x \in V$ and $a \in \{0,1\}$), is there an assignment of values from $\{0, 1\}$ to the variables satisfying all the inequalities and all the equalities?

How can I start to resolve the proof?

Hint: Directed reachability is NL-complete.


Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if the input is ‘l’ then 1,j,!,/,I,t would be characters considered similar looking and should have a higher probability than other letters. Is there a way to do this without hard coding a distribution for every character?

The reason for this is I'm trying to create an algorithm that noises human names similar to the noise you'd expect in a dataset that are due to human error. For example, "Frank" could be noised by a person to be like "Fr4nk" (maybe they quickly doubled checked their work and they mistook the '4' for an 'a') or something like "Dell" could easily be miss inputted by a person as "De11" or "DeII"(These are actually capital i's rather than l's). I'm trying to create an algorithm to replicate this accurately.

I will assume, based on the way you presented the problem, that you only care about errors where single characters are replaced with other single characters—as opposed to merging two adjacent characters into a similar-looking single character, splitting a single character into two similar-looking adjacent characters, etc.

One option would be to build a table of confusion likelihood by using an existing OCR algorithm on an MNIST-style dataset of supervised character images. This does not eliminate the lookup table of probabilities, but it avoids having to construct the table by hand.

As I'm guessing you already know, each entry in this type of dataset is an image together with a label for which character that image supposedly represents. A typical neural network trained for this dataset can output, for any image, a score for each possible character that represents the algorithm's confidence that the image represents that character.

Given an image and the OCR algorithm's score of each possible output character, what you want to do is look at the score of each of the wrong outputs, i.e. the scores assigned to characters other than the one listed on the image's label. An image of a lowercase letter L is likely to have a high score not only for lowercase L but also for uppercase letter I, the digit 1, etc. You can average this information over all the images in the dataset [*] to form a score for each character pair $(a, b)$ of "probability of guessing character $b$ when it was actually supposed to be character $a$".

The dataset and OCR algorithm you choose will obviously affect your results. You will probably get different results using a dataset with handwritten letters in plain white on a black background than using a dataset of Street View house numbers (besides the fact that the house numbers only contain digits).

[*] If you are using an ML model that was trained on the same dataset you are using for building the table, you might want to only use the test dataset for building this table rather than also including the training dataset. Even though you would only be using the scores from the wrong outputs here, you want to avoid any possibility of things getting skewed somehow by overfitting.


Soon to be computer science major with some questions I'm going to apologize in advance for this wall of text, and if you're looking for me to ask technical questions about the field, that isn't what this post is going to be. So this Fall I'm going to be starting my degree for computer science. To be honest I'm not sure what to expect. I've done research and some people say that the degree will be far more math heavy than it needs to be for a lot of fields, while others disagree. The problem, besides there not being a very helpful answer, is that none of these people seem to even be in the field. What will I be learning besides programming? My goal is to actually be a video game programmer, but I'm getting this degree because I know that could change, and I also like the idea of a degree that isn't quite that niche. So is that a wise choice? I began teaching myself to program some with online resources and such, and have focused mainly on Python as a starting point. However, when I see some of the things people on this site and other places, I have no clue what's going on half the time. Is this a bad sign, or should I just quit stressing? Any advice is greatly appreciated.

Firstly, is CS going to be Math heavy?
It's not a very easy question to answer as it depends on quite a few factors. How good are you in Mathematics and how strong are you with the basic concepts? If you were comfortable with the Math you have done so far, then you won't have any problem. If not, then there is nothing that some hard work cannot solve. Plus CS is definitely not he most heavy of all the majors in engineering or sciences. I believe Mechanical, Aeronautical, etc to involve a lot more advanced Math in them.

Secondly, what will you be learning?

You will be learning Algorithms, various programming languages and there pros and cons, maybe artificial intelligence, operating systems, networking, database theory, some electronics I believe, and maybe sensor networks,etc.

Thirdly, should you quit stressing?

Definitely Yes. If you have decided to become a Computer Science major then I am guessing that you have interest in the field. If that is true you should be able to grasp the concepts just fine.

My Advice, pick an area like Artificial Intelligence or Networking or Operating System etc, which ever field you like best, early, and try and master that field. That will help you tons in the future.

I have a PhD in CS and seen quite a few young guys go through the same phase as you. It's very natural to feel nervous about the unknown, specially when it's about your career and the rest of your life. Just try and make smart decisions whenever you have to. Plus, there will be lots of people around to help you when you are unsure.

So, Good Luck and have Fun.


When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables? When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable.

What I wonder about is if I can use this technique to remove variables i don't care about while leaving the truth values of the variables I care about untouched in the final model I get from the sat solver.

Yes, you can.  Any satisfying assignment for the simplified formula can be extended to a satisfying assignment for the original formula, by setting appropriate values to the eliminated variables (but not changing the values of the remaining variables), and vice versa.


How to create a model which predicts the radius of a circle? My training set is made up of 2d images with one imperfect but broadly circular shape in them (plus plenty of noise).  I wish to train a model to predict the "radius" (obviously it's a somewhat subjective concept here) of the shape.

Let's say that I know the approximate center of the shape.

What approach would you use?  Have each input to the model be one of the pixels including that pixel's distance from the center, as well as its colour?

What if I also wanted to predict the volume of the shape, and it was less regular?

Finding reasonably-regular shapes in noisy data? I'd try classical techniques first, like RANSAC or a Hough transform.

Why machine learning?


More efficient DFS on trees Lets say for simplicity sakes I have a simple balanced binary tree of height h  and I am doing Depth First Search. I generally do the following skeletons:

def dfs(node root):
    //Pre actions
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

    // Post actions

Now when I look at this code I know its worst case asymptotic bound is O(n). But perhaps I can do better in some cases. So I want to ask a few things and see if you guys agree:

If the last level of the tree is very sparse. We will still make all those recursive calls when node->left and node-> right is null. these will be $2^h$ checks. Would I be correct in arguing that we should place an additional check in the pre conditions check to avoid at least some of those $2^h$ extra calls?

`

if not node.left and not node.right:
    return

or go even further and add an additional check:

 if not node.right.left and not node.right.left:
     // Do some book keeping
     return
 if not node.left.left and not node.left.right:
     // Do some book keeping
     return

IOW is it legit to argue that in cases where the last level is mostly empty, calling dfs recursively is less(much less in certain languages?) performant vs doing the above additional checks at that last level and though we will still be worst case O(n) time bound(we visit everything), we can be better in such cases?

Do compiler optimizations render my point (1) moot in certain cases. What are those cases?

If you want to cover the entire tree then your algorithm must run in $\Omega(n)$, assuming $n$ is the number of nodes in the tree. You are right, however, that you could optimize the code by checking that the child is non-empty before calling the function. This is an optimization that the compiler probably wouldn't do on its own. This optimization could improve your algorithm, but its running time will still be asymptotically $O(n)$ (assuming $O(1)$ processing per node); at most you improve the constant.


How to find upper and lower bound without using formula I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful.

Prove the following sum is $\Theta (n^2)$ (we have to find $O(n^2)$ and $\Omega (n^2)$)

$P(n)= 1+2+3+4\cdots + n$
$P(n) = n+(n+1)+(n+2)+\cdots +2n$

Note you cannot use any formula you have to do it my algebraic manipulation.
This might be simple but I am not getting any clue right now and I dont have solution of it.

Another approach:

$n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}_{n \text{ times}} = n^2 $
$n^2= \underbrace{n + n +\cdots + n}_{n \text{ times}} \le n+(n+1)+\cdots + 2n \le \underbrace{2n + 2n +\cdots + 2n}_{n \text{ times}} = 2n^2 $


Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint? For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

My attempt to prove this was using a contradiction argument, supposing there was a common edge across 2 different min-cuts. Also, there is an edge in one min-cut that does not exist in the other, and idem for the other cut. Name these e1 and e2.

I managed to prove that the common edge must be an edge on a path between an end-point of e1 and one of e2.

There is a figure I drew to understand the situation better:

Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

There is no "why" here since 2 different edge minimum-cuts in an undirected multigraph can have one edge in common.

Here is an example. Edge set $\{AB,AC\}$ is a minimum cut.
Edge set $\{AB,BC\}$ is another minimum cut. They have edge AB in common.

  For the proof of a maximum of $\binom n2$ min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

I do not think we need that (non)-fact. The random contract algorithm will find each min-cut with a probability of no less than $\frac1{\binom n2}$. Since that algorithm only find one min-cut each time, there are at most $\binom n2$ min-cuts.

Here are several exercises to enhance our understanding of the intersection of two min-cuts.

(Exercise 1). Find an undirected multigraph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 2). Find an undirected simple graph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 3). Given a positive integer $n$, find an undirected simple graph in which 2 different edge minimum-cuts have $n$ edges in common.


cardinality of recursive/r.e/not r.e languages? I was just looking into properties of languages and wondered about the cardinality of them

are all recursive languages countable or can they also be uncountable
(can u have a recursive language which is uncountable?)
can r.e languages be countable and uncountable?
(can u have a r.e but not recursive language which is uncountable?)
are all non r.e languages uncountable?
(can u have a non r.e language which is countable?)

an explanation would be nice but i am not necessarily looking for a proof. thanks!

I assume you're talking about the cardinality of the sets $R$, $RE$, and $\overline{RE}$, as the set of all words in a language is always countable.

$R$ (the family of recursive langauges) is countable, because there the set of Turing Machines is countable, and there is at least one TM for each $R$ language.
$RE$ is countable, by the same logic, since there is a TM semi-deciding each $RE$ language.
The set of non-$RE$ languages, $\overline{RE}$, is not countable, then by process of elimination. The set of all languages, $\mathcal{L}$, over an alphabet $\Sigma$ is $\mathcal{P}(\Sigma^*)$ i.e. the powerset of the set of all words.
This set is uncountable, since $\Sigma^*$ is countable, and the powerset of a set always has higher cardinality.

$\mathcal{L} = RE \cup \overline{RE}$, and $RE$ and its complement are disjoint, so since $RE$ is a countable subset, there must be an uncountable number of words in $\overline{RE}$.


TCP congestion problem Consider an instance of TCP’s Additive Increase Multiplicative Decrease(AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a time out occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.

I am bit confuse in this concept.
What I know :

Slow start and congestion avoidance are different.
Slow start is used in conjunction with congestion avoidance.

Window size for 1st transmission = 2 MSS
Window size for 2nd transmission = 4 MSS
Window size for 3rd transmission = 8 MSS
threshold reached, increase linearly (according to AIMD)
Window size for 4th transmission = ?? MSS
Window size for 5th transmission = ?? MSS
time out occurs, resend 5th with window size reduced to half (according to AIMD)
Window size for 5th transmission =  ??? MSS

What will be the Window size for 4th transmission ? 9 MSS or 10 MSS
It means i want to ask you after threshold window size should increase linearly means it  should increase by 1 MSS or 2 MSS  ( 2 MSS is given in example ) ?

What will be window size for 5th transmission ? Will it be 1 MSS or 2 MSS ?

Please clear my concept. I am so confused.

This is a home work problem.
By the way the problem is ambiguous.
For concept see       3.6 pg259 of kurose 6th edition.

As for the solution normally what AIMD do is after the time out the it set window size to 1 in the next slow start phase
In sort the window increase in this manner 2,4,8,9,10,1,2,4,5,6
So after 10th transmission window size will be 6
But in question says the slow start phase start with 2 MSS So to consider that the window will Grow this way
2,4,8(threshold reached additive increase),9,10(time out& set threshold to 5),2,4,5(threshold reached additive increase),6,7


Find the nearest sum to a given number of two elements in sorted matrix Given a sorted  $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach  is $\mathcal{O}(n^4)$  brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c_1\leq c_2\le \cdots \leq c_{k}$ and $d_1\leq d_2\le \cdots \leq d_s$ and we need to find a sum of the form $c_i$ + $d_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays:
$$
c_1\leq c_2\leq \cdots \le c_{k}; \ \ q-d_s\leq q-d_{s-1}\leq \cdots\le q-d_{1}
$$
in one array.
So to solve the problem we can iterate the set of row-pairs  of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

  My question. How can we do this more effectively?

Try something like binary search since it is sorted
i.e. check a[n/2,n]+a [n/2 +1,1] if equal done
-smaller check the lower half
-greater check the upper half
(Keep the last checked value to compare how close with the next one)
Probably O ( log n2)


How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum? For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{denominator sum}}$ is maximized. As in this case, selecting $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$ will result in $\frac{4+2+1}{2+3+2}$ = 1 which is maximized.

How can I select $k$ fractions which will always result in the maximum $\frac{\text{numerator sum}}{\text{denominator sum}}$ value?

Edit:

Attempt 1: Sorting fractions in descending order. This passes a few test cases but that it's. This can also be proven by example that it is not the optimal solution. Let's say we have a list of 3 fractions sorted in descending order, $\frac{1}{2}$, $\frac{20}{59}$, $\frac{1}{3}$ and $k = 2$. The optimal solutions is $\frac{1+1}{2+3}$, not $\frac{1+20}{2+59}$.

For a list of fractions, define the ratio as (sum of numerator) / (sum of denominator).

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

We have obvious lower and upper bounds for r (the k-largest and the largest value of any fractions). With binary search we can easily find a list with maximum ratio.

Responding to some comments: What I presented is the basic idea. There is plenty of room for improvement.

For example "we pick the k fractions where x - ry is largest" - that can easily be done without sorting the array, much faster than n log n. Start like Quicksort, but only process subarrays that you need to determine the k largest values.

And it's not just binary search, because each time you actually find a list of fractions and can update the lower or upper bound for r or both. (For example if the lower and upper bound were 6.0 ≤ r ≤ 10.0, you look for a list with ratio 8.0 and only find one with ratio 7.6, then in the next search you know 7.6 ≤ r < 8.0 is possible).

Since the lower bound for r is one that was actually achieved, you can also check which is the smallest eps for which you would have put a different fraction in the top k list of fractions.


Pumping Lemma for regular language I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as -

Let # of states in the FA be n & I select the string w = a^2n
Now let xyz = w
xy = a^n
y = a^m | m is odd number
now x(y^2)z = a^(n-m)(a^2m)(a^n)
= a(2n+m) does not belong to L

which says this regular set doesn't satisfy pumping property. Please let me know if I am doing something wrongly.

Thanks in advance.

The pumping lemma says that every (long-enough) string in a regular language can be divided in some way such that it can be pumped (subject to the other stated conditions).

Note that the statement is that every string has at least one way of dividing it up. Not every division of a string necessarily works. As you have shown, some don't work, however there is a different division (any one where $m$ is even) that does work. So the language does satisfy the pumping lemma.


Is this pumping lemma proof correct? $$ L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\} $$

I say it's not regular. Proof by pumping lemma:
Find a string $xy^iz$ that is not in $L$ (respecting the constraints).
Let $w=x^py^pz^p$.

Let $i=2$.
$x^p(y^py^p)z^p$ is not in $L$.

Thus $L$ is not regular.

Is this proof correct?

The proof is not correct nor complete. You have to show that for every possible splitting of the string to be pumped, where the constraints of the lemma hold, the pumped string does not belong to the language.

You have only showed for one case that the string does not belong to the language and hence that the language is not regular.

But what about this case:

$$ z = x^py^pz^p, take \ i = 0 \ , uv = x^p, \ then \ z = uv^0w \ does \ not \ belong \ to \ the \ language, \ the \ condition \ i+ k > j \ is \ violated $$

You have to show that for every possible splitting of the string to be pumped, where the constraints hold, for some i, the string does not belong to the language.


How do I work out the recurrence relation of the given function? I am looking to find the recurrence relation of the following function:
int fnA(int[] array, int low, int high) {
  if (low >= high)
    return array[low];
  else {
    int gap = floor((high - low) / 5);
    return (fnA(array, low, low + 2 * gap) +
            fnA(array, low + gap, low + 3 * gap) +
            fnA(array, high - 2 * gap, high));
  }
}

The problem I am having is that I don't understand what is happening to $n$ in the recurrence relation.
Note: I am not looking for the answer per se, but rather how I should be going about problems like these.

In the following I won't pay much attention to floors, celings, and "off-by-one" errors since they won't ultimately matter in the analysis of the recurrence relation. However all of the following calculations can be made precise.
If $n = \texttt{high} - \texttt{low}$ then $\texttt{gap} = n/5$ and the algorithm will perform three recursive calls:

The first on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}$ and $\texttt{low}+2\texttt{gap}$.
The second on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}+ \texttt{gap}$ and $\texttt{low}+3\texttt{gap}$.
The third on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{high}- 2 \texttt{gap}$ and $\texttt{high}$.

Also notice that when $n = O(1)$ then the time complexity of the algorithm is constant, and that the time spent in the non-recursive parts of the algorithm is also $O(1)$.
The recurrence relation is then:
$$
T(n) = 3T\left( \frac{2}{5} n \right) + O(1),\\ \quad T(1)=O(1)
$$
which can be solved...

 using the Master theorem to yield $T(n) = O(n^{\log_{5/2} 3}) = O(n^{1.1989\dots})$.


How to represent text for a program to add punctuation to a block of text? I want to try and make a program where I remove the punctuation from a block of text and it then inputs it in the correct places.
I have started with a simpler element of just using text and spaces, no commas, full stops etc.
The first angle I have been taking this is with machine learning, neural networks and simpler word count probabilities.
However the thing I am struggling with is the representation of the block of text. At the moment I give it a block of text and it reads say 20 letters then breaks it into test based on where it thinks a word is. This is ineffective though because it may just cut off half a word at the start/end of the block.
Just wondering if anyone had an idea of a way to use the block of text in this way in a better way to do this task!
Many thanks

I am making two assumptions here about things that, to me, are not quite clear from your question

When you say you removed punctuation, you actually meant whitespaces as well.
You tried neural networks, but not in a sequence-to-sequence fashion.

What's nice about your problem is that you can generate training data as much as you want just by taking a proper piece of text and removing all the punctuation.

This being said, I suggest you engage your problem as a machine translation task where you want to predict the proper text given the one without punctuation.

Today, the best way to do this is by sequence-to-sequence learning with deep neural network (just pick a few machine translation papers from last ACL (= Annual Meeting of the Association for Computational Linguistics) conference to learn more about that.

Concerning you actual question, how to represent the input, I'm not quite sure if you have to limit the size of your input beforehand or not. In any way, you could choose the size of your input window so that any block of text that you possibly want to put in would fit (if you know beforehand how long your paragraphs will be). Or it might be that you can just cut your input sequence at an arbitrary letter and your model will learn to make sense of it anyway (I am not an expert in neural machine translation).

So, as you can see, my answer is maybe not completely on the spot but I hope it is helpful to you anyway.


Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$ how can I find the regular expression for this intersection  ?
I've tried to find words but it did not help too much..
$$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$

Any word can be written as a concatenation of runs. For example,
$$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$
Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.
The regular expression $(a+b)^*c^*(a+b)^*$ captures all words with at most one $c$-run. Similarly, the regular expression $(b+c)^*a^*(b+c)^*$ captures all words with at most one $a$-run. Therefore the intersection consists of all words with at most one $c$-run and at most one $a$-run.
Since the only other possible run is a $b$-run, we get that the intersection is
$$
b^*a^*b^*c^*b^* + b^*c^*b^*a^*b^*.
$$


Number of divisors of a number - in NP? I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.

The input (m,n) is in binary.

The non-deterministic Turing machine for the language would be:

1) Guess the prime factors of m.

2) Verify that ∏i(di+1)=n.

The problem is that I can't find a way to factorize in polynomial time (in the input) the number m.

If stage 1 takes m steps then it would be m=2 ^ log(m) and the whole algorithm would run in exponential time.

How can I prove that verifying that m has exactly n divisors is in NP ? Perhaps not via factorization but somehow else. I've run out of ideas.

A number with k binary digits has at most k prime factors. That's because the smallest number with k prime factors is 2^k.

So given a number m with k binary digits you can easily be given a list of the prime factors of m. You can check that the product of these prime factors is indeed m in polynomial time easily. You can easily calculate the number of factors from the prime factors in polynomial time.

But what you also need to do is that the purported list of prime factors is actually a list of primes. Here comes another theorem that shows for every prime p, there is an easily verifiable proof that p is indeed a prime.

The oracle should contain a list of the prime factors, and for every item in the list an oracle for proving that it is prime.

For being in NP, there is absolutely no need that you are able to provide the oracle in polynomial time. You only need to be able to check it in polynomial time.


What would a language look like in which precise GC was implementable as a library? Suppose you have some programming language with manual memory management. What features does this language need to have in order to be able to implement precise garbage collection as a library, and not as a fundamental language construct?

By a precise GC I mean one where only pointers to the heap are traversed to ascertain which variables are or are not live.

Some additional considerations:

C and C++ have the Boehm garbage collector, but I don't count this since it's not a precise GC. The Boehm collector assumes that anything on the stack that could be a pointer, based purely on memory alignment requirements, is a pointer. For example, any integer k such that (k % 4) == 0 looks at a bit level like a pointer, since pointers must be 4-byte aligned.
magpie transforms existing C code to use a precise garbage collector. The generated C code has a lot of stubs for garbage collection, i.e. stuff for registering any stack pointers into the heap with the collector. I don't count this because no one could ever be expected to write code that way; it's more of a compilation target for other languages.

I imagine that such a language would need to have:

Macros or some form of metaprogramming, for encapsulating all of the extra code needed to do things like register GC roots.
Some reflective mechanism that allows you to inspect structs or unions; you need to determine which members are pointers.
Some reflective mechanism that allows you to examine the stack frame layout. This sounds a lot harder than 2.

I hope this isn't too vague or opinion-based but I've been wondering about it for a while.

I think it is possible to implement a garbage collector in C++ without changing the language itself. But in order to use the garbage collector, one must restrict the programmer from using arbitrary language constructs. In particular, all memory allocation requests must be done through the allocation APIs given by the garbage collector, and all the access must be done through references that is managed by the garbage collector.


If L is regular language then each equivalence class is also regular? L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular?

The equivalence relation is, from Wikipedia: "Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y."

Given a DFA $D$ and a word $x$, let $D(x)$ denote the state of $D$ after reading $x$.

Let $D$ be a minimal DFA for $L$ and $x,y \in \Sigma^*$.
If $D(x) \neq  D(y)$ then $x$ and $y$ have a distinguishing extension.
Indeed, if $x$ and $y$ had no distinguishing extension, it would be possible to construct a DFA $D'$ with one less state by merging the states $D(x)$ and $D(y)$ of $D$.

On the converse, if $D(x)=D(y)$ then $x$ and $y$ have no distinguishing extension (since the states reached by $D$ from $D(x)$ and $D(y)$ after reading any string $z$ must coincide).

Then, $x$ and $y$ are in the same equivalence class iff $D(x)=D(y)=q$, for some state $q$ of $D$.

Given a state $q$ of $D$, the language of all the words $x \in \Sigma^*$ such that $D(x)=q$ is regular. To see this, consider the DFA obtained from $D$ by changing the set of final states to $\{q\}$.


How turing machine can be used as enumerator Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an enumerator. I have studied the formal definition of enumerators that have no input. But I am unable to realize how a Turing machine can work as an enumerator for the language $L=\{a^nb^n:n\geq0\}$. Any help would be greatly appreciated.

As your language $L$ is decidable ( lets its decider be $D$ ), you can build an enumerator $E$ for it ( which disregards its own input ). $E$  gives strings  ( with alphabet being $\sum =\{a,b\}$ ) in increasing order ( lexicological order, which is possible as $\sum^{*}$ is a countable set ) to $D$ and if $D$ accepts an input $E$ prints it, if $D$ rejects an input $E$ does not print it. If your language is undecidable but  recognizable
  this method won't work for making an enumerator for such a language.
EDIT

If $L$ is a recognizable but not a decidable language we can build an enumerator for it in the following way. Let $R$ be the recognizer for the language and $E$ the enumerator. The strings in $\sum^{*}$ are denoted as $s_1,s_2,....$ ( again in lexicological order ).

i = 1
while ( True )
  j = 1
  while ( j <= i )
     Give the string s_j as input to R and let R run for i steps,if R halts on
     s_j in at most i steps and accepts it, E prints the string s_j

     j = j + 1
  i = i + 1

Note with above method if a string belongs to $L$ it may be printed several times ( which can be avoided ). But unlike a decidable language there is no way to guarantee that strings are enumerated in lexicological order.


Zigzag concatenation of two languages Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular:
$$
\{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \Sigma,a_1\ldots a_k \in A, b_1\ldots b_k \in B\}.
$$

However I simply do not understand how I'm supposed to do this. Simply put, my confusion is what $w = a_i b_i$ means. Is it concatenation? Does it mean that the word $w$ is the concatenation of $a=a_1\ldots a_k$ with $b=b_1 \ldots b_k$?

Since languages $A$ and $B$ are regular, we can assume there are DFAs
$$
M_A = \{Q_A, \Sigma, \delta_A, s_A, F_A\} ~~\text{and}~~ M_B = \{Q_B, \Sigma, \delta_B, s_B, F_B\}
$$
that recognize them, respectively.
Let's call the zig-zag lanuage $Z$. It is easy to see that the alphabet of $Z$ is $\Sigma$.

We will construct a DFA, $M_Z = \{Q_Z, \Sigma, \delta_Z, s_Z, F_Z\}$, for $Z$.

Set of states

$M_Z$ must be such that it will alternately apply $\delta_A$ and $\delta_B$ each time it reads a character from the input string. For that, it must be able to track all possible combinations between states of $M_A$ and $M_B$, as well as which of the two transition functions it should apply on the next transition. We will use 0 to represent that the next transition should be a $\delta_A$-move and $1$ for a $\delta_B$-move. Altogether, we have $Q_Z = Q_A \times Q_B \times \{0,1\}$.

Initial state

Clearly, the initial state of $M_Z$ is $s_Z = (s_A, s_B, 0)$.

Accepting states

For a state $q_f = (q_A, q_B, i)$ of $M_Z$ to be accepting, both $q_A$ and $q_B$ must be accepting states of $M_A$ and $M_B$, respectively. This is to satisfy the conditions $a_1\ldots a_k\in A$ and $b_1\ldots b_k\in B$ in the definition of $Z$. In addition, the last transition before reaching $q_f$ should be a $\delta_B$-move, therefore the next transition (if there is one) is expected to be a $\delta_A$-move, represented with  $i = 0$. So, the set of accepting states is $F_Z = F_A\times F_B\times\{0\}$.

Transition function: Here is where the alternating behavior of $M_Z$ is constructed.

If the DFA is in a 0-state, then it should perform a $\delta_A$-move, leading to a 1-state. The DFA still needs to remember the (non-active, for now) state of $M_B$.
A similar behavior, but with 0 and 1 switched, is adopted for transitions from 1-states.
\begin{align*}
\delta_Z((q_A, q_B, 0), x) &= (\delta_A(q_A, x), q_B, 1)\\
\delta_Z((q_A, q_B, 1), x) &= (q_A, \delta_B(q_B, x), 0)
\end{align*}


tightest upper bound on binary search tree insertion? The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced
What will be the tighter upper bound on this,will it become O(logn)
I have read that tighter upper and lower bounds are often equivalent to the Theta notation.

For a binary search tree of $n$ nodes ,
Maximum height $=h_{max}=n-1 = \Theta (n) =O(n)$
which happens in the case of skewed binary search tree as below if all elements of a binary search are either right-skewed or left-skewed

So in worse case , to add a new node in to an existing skewed binary search tree , it takes $n$ comparisons (comparison at each level).
So, time taken $= h_{max}+1=n=\Theta\ O(n)$

Minimum height = $h_{min}=\lceil \log_2{(n+1)}\rceil-1=\Theta(\log(n))=O(\log(n))$
which happens in the case of complete binary search tree as below if all levels contains all elements except last level (Last level may be not contain all elements).

Now, number of comparisons $= h_{min}+1=\lceil \log_2{(n+1)}\rceil=\Theta(\log(n))=\ O(\log_2(n))$
Which may be the tightest upper bound you are asking for .
So, you can use either $\Theta$ or $\ O$ notation here. $\Theta$ is tighter .
Whenever you use $\Theta$ you can replace it with $\ O$ but not viceversa .


Prove that A is non-regular using K-Complexity Non regularity theorem Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$

Given $A \subseteq \Sigma^*$ has the following property, then it is not regular
For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A_{x,n}$ exits and K-Comp $C(Y^A_{x,n}) > c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity

$A=\{0^{2n}1x∣n∈\mathbb{N}, x∈\{0,1\}^∗$, and $|x|=n\}$ Prove that A is non-regular using KCR
All we have to do is to pick a $x$ and $y$ s.t the concatenation $xy \in A$.
If I let $x = 0^{2n}1$ and let $y = x$, then we build the set $Y^A_{x}$ given the $x$ and $y$ from above $Y^A_{x,1} = 001(01)$ and next element in the set $Y^A_{x,2} = 00001(0101)$.
Here is where I get stuck since I know I need to show $C(Y^A_{x,1}) > c + log(1)$ would this suffice to show that because of that this language is not regular? What is the best way to split the language for $x$ and $y $

Suppose that $A$ is regular. Then there exists a constant $c$ such that for all $x \in \Sigma^*$ and for all $n$ such that $Y^A_{x,n}$ exists, $C(Y^A_{x,n}) \leq \log n + c$.

Let us take $x = 0^{2m}1$. Then $Y^A_{x,n}$ exists as long as $n \leq 2^m$ – in fact, $Y^A_{x,n}$ is just the $n$th binary string of length $m$. Therefore
$$
C(\text{$n$th binary string of length $m$}) \leq \log n + c.
$$
In particular, choosing $n=1$, we get
$$
C(0^m) \leq c.
$$
Clearly this fails for large enough $m$. This contradiction shows that $A$ is not regular.


How many layers should a neural network have? Are there any advantages of having more than 2 hidden layers in a Neural Network?

I've seen some places that recommend it, others prove that there is no advantage.

Which one is right?

One very good resource is the Neural Network FAQ. The question depends a lot on your problem. If the problem is linear in nature, there is no reason to have any hidden layers. If the problem is non-linear, often a single hidden layer with around 10 hidden neurons will do the trick.

There is a very similar question (with a very similar answer) at CrossValidated: How to choose the number of hidden layers and nodes in a feedforward neural network?)


Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$ With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$

I need to:

  run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can derive the word $baabb$ from the context.
  write the left derivation.

My try:

$1.$

$$
\begin{array}{c|lcr}
i\bigg/j &  1 & 2 & 3 &  4 & 5 \\
\hline
1 & \text{C,S} & \text{B} & \square& \square &\square \\
2 & \quad\blacksquare & \text{A} & \text{A} & \square & \square \\
3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \square \\
4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\
5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\
\end{array}
$$

$S\Longrightarrow BA \Longrightarrow CAA \Longrightarrow bAA\Longrightarrow bAACC\Longrightarrow baabb$

I'm stuck here in the table construction. How should I fill in the empty squares?

Watch this video and you should get:

$$
\begin{array}{c|lcr}
i\bigg/j &  1 & 2 & 3 &  4 & 5 \\
\hline
1 & \text{C,S} & \text{B} & \text{B,S} & \text{A,B,C} & \text{B,C,$\color{red}{\text{S}}$,A} \\
2 & \quad\blacksquare & \text{A} & \text{A} & \text{B,C,A,S} & \text{A,B,C} \\
3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \text{A,S,C} \\
4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\
5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\
\end{array}
$$

Since S is in the left and higher corner so we can derivate the word $baabb$ from the context


Priority queue with a buffer for delayed insertion and other tweaks I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.).

One possible optimisation is to delay insertions until the next extraction.  The inserted elements can be kept in a buffer (a simple stack) until the next extractions, and then inserted with some kind of optimised "bulk insertion" method.

Another possible tweak is to check if the element to be inserted has a higher priority than all the waiting ones, and if so, to store it in a second stack, which is to be used for the subsequent extraction.  If the priority of the element to be inserted is not the highest but higher than the priorities of all the elements in the heap, then the elements from the second stack can replace the elements at the top of the heap, while the replaced elements are moved to the buffer for delayed insertion.  This tweak however would add a noticeable overhead, so it is not clear if it would be an optimisation in any scenario.

Has such or similar modifications of (heap-based) priority queues been studied or used in practice?

There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg & Silverstein.


Dynamic Programming Subset Sum Problem with twist Question:  You are given an input , which is a sequence of positive integers $w_1, w_2, . . . , w_n$ with parameters $W, ∆. $We wish to find
$S ⊆ \{1, 2, . . . , n\}$ such that $\sum_{j \in S} w_j$ is as large as possible, subject to the constraints that (a)$\sum_{j \in S} w_j≤ W$,
and (b) for all $i, j ∈ S$, if $i \neq j$ then $|w_i − w_j | ≥ ∆.$

Here is the recursive formula I came up with (which is incorrect).

$$OPT(i,w) =
 \begin{cases}
OPT(i-1, w) & : \text{if  } w < w_i  \\
w_1 & : \text{if   } i = 1 \text{and  } w_1 \le W\\
OPT(i, w) = max(OPT(i-2, w), OPT(i-1, w), w_i + OPT(i-2, w-w_i)) & : \text{if  } |w_i - w_{i-1} | < \Delta\\
OPT(i, w) = max(OPT(i-1, w), w_i + OPT(i-1, w-w_i)) & : otherwise
\end{cases}$$
A
The problem with the above formula is that it only checks if the $i-1^{st}$ weight is compatible with the $i^{th}$. It doesn't check if the $i^{th}$ weight is compatible with all the weights in the optimal solution. For example, if $\Delta = 2, W = 6, w_1 = 3, w_2 = 1, w_3 = 2$ then the recursive formula returns 5 instead of 3.

I would appreciate any help. Thanks.

Hint: Arrange the weights in increasing order. You might also need to make other changes, but sorting the weights is a good first step.


Explanation of Grammar Ambiguity Consider now the grammar G

S -> (S + S)
S -> (S * S)
S -> a

Is it ambiguous?

Answer: No because there are disambiguating parentheses and so no left or right
recursion.

Can someone explain how the parentheses are disambiguating. I could understand if they were "[" and "(".

Appreciate the help

A grammar $G$ is non-amgibuous if every word in $L(G)$ has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (here $L(\alpha)$ is the set of all words that can be generated from the sentential expression $\alpha$); given this, an easy induction shows that $L(G)$ is non-ambiguous.

It is clear that $L(S + S)$ and $L(S * S)$ are disjoint from $L(a)$. To prove that $L(S + S)$ and $L(S * S)$ themselves are disjoint, you can prove by induction that each word generated by $S$ is either $a$ or of the form $(w)$, where $w$ is a well-parenthesized expression (parenthesis close each other correctly), and this gives you a rule for identifying the first and the second $S$ in word generated by $L(S + S)$ and $L(S * S)$; the symbol in between determines whether the word belongs to $L(S + S)$ or to $L(S * S)$.


Regular vs LALR(1): what is faster Supposing we have two grammars which define the same languge: regular one and LALR(1) one.

Both regular and LALR(1) algorithms are O(n) where n is input length.

Regexps are usually preferred for parsing regular languages. Why? Is there a formal proof (or maybe that's obvious) that they are faster?

I believe the reason for favoring regular expressions over LALR(1) grammars for accepting simple grammars stems from the time needed to build an LALR(1) automaton. Let $m$ denote the size of the grammar which is used to build the automata for accepting the language defined by said grammar. If you need to build up the accepting automaton during runtime you will probably want to use regular expressions because building up an LALR(1) automaton will take $O(m\cdot 2^m)$ which does not include the necessary testing if the input grammar even is LALR(1) ($O(m^3)$). Regular expressions instead can be build up quite easily, the check can occur during conversion (see [1] , re2post).

Adding to the speed gained when building up different regular expressions during different program runs modern regular expressions, mostly PCRE, are NP-Complete, thus very powerful (see for instance [2]). Additionally, with most languages supporting regular expressions there also is an interactive environment to check if the regular expression really expresses your intention, which is more efficient from a programmer's perspective than to write the grammar, generate the parser and do a test and then reiterate the process. I believe this to be the main reason for using regular expressions over LALR(1) grammars.

If you are interested in the implementation and runtime aspects of grammars [3] might also be of interest to you.

[1] http://swtch.com/~rsc/regexp/

[2] http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

[3] Gerhard Goos, William Waite, Compiler Construction, Springer, Jan 1984 ( symbolaris.com/course/Compilers/waitegoos.pdf)


Time complexity of combinations of n pairs of parentheses I have the following code snippet for combinations of n pairs of parentheses.

def parens(n):
    if n <= 0:
        return ['']
    else:
        combinations = []
        helper('', n, n, combinations)
        return combinations

def helper(string, left, right, combinations):
    if left <= 0 and right <= 0:
        combinations.append(string)
    else:
        if left > 0:
            helper(string + '(', left - 1, right, combinations)
        if right > left and right > 0:
            helper(string + ')', left, right - 1, combinations)

What's the reasonable estimation of the time complexity of it?

My trials:

(2n)!/n!n! since it's permutations of multisets with more limitations.
Resolve recurrence: T(n) = 2T(n-1) => O(2^n).

Actually, for every combination of parenthesis, your algorithm performs $\Theta(n)$ amount of work (to build the string and append it to your list of combinations).

The number of valid combinations of $n$ pairs of parenthesis is the $n$'th Catalan Number $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Thus, your algorithm runs in $\Theta(nC_n)$ which is also equal to $\Theta(\frac{4^n}{\sqrt{n}})$, because $C_n$ grows as $\Theta(\frac{4^n}{n^{3/2}})$ (see the linked Wikipedia article).


A simple clarification on $\#P$ closure properties What does $\#P$ closure under addition and multiplication mean?

Does it mean given $NTM$s $N_1$ and $N_2$ we can create in deterministic polynomial time an $NTM$ $N_\times$ and $N_+$ such that for every input $x$ we have $$\#N_\times(x)=\#N_1(x)\#N_2(x)$$ $$\#N_+(x)=\#N_1(x)+\#N_2(x)$$ accepting paths?

Yes, that's exactly what it means. Closure under addition can also be phrased as follows: if $f(x)$ and $g(x)$ are $\#P$ functions, then $h(x)=f(x)+g(x)$ is also a $\#P$ function. As an exercise: How do you construct the machines $N_+$ and $N_\times$? Check that these definitions mean the same. $\#P$ has extraordinary closure properties, for example if $f\in \text{FP}$ and $p\in\#P$ then

$$\sum_{y=0}^{f(x)}p(y)$$

is also a $\#P$ function. We say that $\#P$ is closed under exponential sums.

In general, to say that some set $O$ is closed under an operation $\triangle$, means that if you take $a,b\in O$, then $a\triangle b\in O$. In other words, you can't "get out of $O$" by applying $\triangle$ to elements inside $O$. For example, $NP$ is closed under set intersection, because $L,K\in \text{NP}\implies L\cap K\in\text{NP}$ (why?).


How would I design an NFA that recognises the language of all strings that don't end in a certain sequence? How would I design an NFA that accepts all strings don't end in a certain sequence over the alphabet {0,1}.
Designing a DFA that does the job is fairly straight forward, but I can't find out how to make my Automata Non-Deterministic.

Any DFA is also already a NFA, so you've already answered your question.


Paging: Does the page table of a process also gets swapped out when the process gets swapped out from main memory? Does a process's page table too gets swapped out to secondary storage from main memory when the process gets swapped out to secondary storage from main memory? And gets swapped back in when the process is swapped in?

I tried to find the answer in text books and online, but none is clear.

Also, it would be helpful if you can tell me if the PCB (process control block) of a process also gets swapped out when the process is swapped out.

The below article include the answer of your questions, apparently this is possible using multi level page table.

https://www.8bitavenue.com/page-table-vs-inverted-page-table/


What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms? I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary.  The standard binary golden ratio notation works but is horribly space inefficient.  The  Balanced Ternary Tau System (BTTS) is the best I've found but is quite obscure.  The paper describing it in detail is A. Stakhov, Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic, 2002.  It is covered in less depth by this blog post.

BTTS is a balanced ternary representation that uses $\phi^2 = \phi + 1$ as a base and 3 values of $\bar 1$ ($-1$), $0$, and $1$ to represent addition or subtraction of powers of $\phi^2$.  The table on page 6 of the paper lists integer values from 0 up to 10, and it can represent any $\phi$-based number as well.

BTTS has some fascinating properties, but being ternary, I didn't think I'd be able to find a compact bit representation for it.

Then I noticed that because of the arithmetic rules, the pattern $\bar 1 \bar 1$ never occurs as long as you only allow numbers $\ge 0$.  This means that the nine possible combinations for each pair of trits ($3^2$) only ever has 8 values, so we can encode 2 trits with 3 bits ($2^3$, a.k.a octal).  Also note that the left-most bit (and also right-most for integers because of the mirror-symmetric property) will only ever be $0$ or $1$ (again for positive numbers only), which lets us encode the left-most trit with only 1 bit.

So a $2^n$-bit number can store $\lfloor 2^n/3\rfloor * 2 + 1$ balanced trits, possibly with a bit left over (maybe a good candidate for a sign bit).  For example, we can represent $10 + 1 = 11$ balanced trits with $15 + 1 = 16$  bits, or $20 + 1 = 21$ balanced trits with $30 + 1 = 31$ bits, with 1 left over (32-bit).  This has much better space density than ordinary golden ratio base binary encoding.

So my question is, what would be a good octal (3-bit) encoding of trit pairs such that we can implement the addition and other arithmetic rules of the BTTS with as little difficulty as possible.  One of the tricky aspects of this system is that carries happen in both directions, i.e.
$1 + 1 = 1 \bar 1 .1$ and $\bar 1 + \bar 1 = \bar 1 1.\bar 1$.

This is my first post here, so please let me know if I need to fix or clarify anything.

--Edit--

ex0du5 asked for some clarification of what I need from a binary representation:

I want to be able to represent positive values of both integers and powers of $\phi$.  The range of representable values need not be as good as binary, but it should be better than phinary per bit.  I want to represent the largest possible set of phinary numbers in the smallest amount of space possible.  Space takes priority over operation count for arithmetic operations.
I need addition to function such that carries happen in both directions.  Addition will be the most common operation for my application.  Consequently it should require as few operations as possible.  If a shorter sequence of operations are possible using a longer bit representation (conflicting with goal 1), then goal 1 takes priority.  Space is more important than speed.
Multiplication only needs to handle integers > 0 multiplied to a phinary number, not arbitrary phinary number multiplication, and so can technically be emulated with a series of additions, though a faster algorithm would be helpful.
I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
I need to eventually convert a phinary number to a binary floating point approximation of it's value, but this will happen only just prior to output.  There will be no converting back and forth.

I'm going to try to answer this myself, in the hope that my answer will give others a better idea of what I'm after and lead to better answers than mine.

I found that framing the problem in terms of the original golden ratio base helped me to think about a binary encoding more effectively.  I want to note however that there is no difference between BTTS and phinary except the length of the representation.  Both number systems represent the same set of numbers, save that BTTS more easily encodes negative numbers.  Just as 3 bits can theoretically represent 2 trits of BTTS, they should also be able to represent 4 bits of phinary (which is what 2 trits encode).  Keep in mind that in standard base-$\phi$ all instances of $011_\phi$ are replaced with $100_\phi$ and $1_\phi + 1_\phi = 10.01_\phi$, with a carry both one place to the left and two to the right.  The following table is my best attempt thus far:

Phinary  |  Binary | Octal
0 0 0 0  |  0 0 0  |   0
0 0 0 1  |  0 0 1  |   1
0 0 1 0  |  0 1 0  |   2
0 1 0 0  |  0 1 1  |   3
0 1 0 1  |  1 0 0  |   4
1 0 0 0  |  1 0 1  |   5
1 0 0 1  |  1 1 0  |   6
1 0 1 0  |  1 1 1  |   7

There are some benefits to this encoding. One is that $0_\phi$ and $1_\phi$ are the same as for binary.  Another is that a carry in the forward direction works as expected automatically:

$1010_\phi + 1_\phi = 1011_\phi = 1100_\phi =  1\ 0000_\phi$, and $111_2 + 1_2 = 1\ 000_2$.

Another advantage is that addition almost works as is:

$0101_\phi + 0010_\phi = 0111_\phi = 1001_\phi$ and $100_2 + 010_2 = 110_2$.

As far as I can tell, the only places addition breaks down are for $2_8 + 2_8$, $5_8 + 7_8$ and $7_8 + 7_8$.

$0010_\phi + 0010_\phi = 0020_\phi = 0100.1_\phi$, not $0101_\phi$.
$1000_\phi + 1010_\phi = 2010_\phi = 1\ 0020_\phi = 1\ 0100.1_\phi$, not $1\ 0101_\phi$.
$1010_\phi + 1010_\phi = 2020_\phi = 2100.1_\phi = 1\ 1000.1_\phi$, not $1\ 1001_\phi$.

All other additions work (excluding right carry logic).

We can handle right carries by looking at how they are produced. I'll be using octal for brevity.

1, 4, and 6 produce a right carry of 3 to the previous 3 bits when they are added to themselves or each other.
2 and 7 produce a right carry of 5 added to the previous 3 bits when added to themselves or each other.
4 + 3 gives a right carry of 3 and 5 + 7 gives a right carry of 5.

That's all we need to check for (I think) with the exception of also testing for 2 + 2, 5 + 7, and 7 + 7 and subtracting 1 from the result.

So basically we are taking advantage of the redundancy in a 4-bit phinary representation ($011_\phi = 100_\phi$) to represent the same numbers without redundant cases in 3-bits of binary.
A $2^n$ bit number can store $\lfloor 2^n / 3\rfloor * 4 + 1$ phinary bits.

I'm sure there are clever bit-hacky ways to do this better, but I'm hoping that this will clarify my intent and provide a starting point for both myself and anyone else wanting to tackle this.


Basic Binary search tree query Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?

If the height is $0$ it is true.
Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST.
Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the given tree, the node $x$ is listed after all nodes of its left subtree. Since its inorder is sorted, then $x$ is not smaller than any node of its left subtree. Likewise, $x$ is not larger than any node of its right subtree. Therefore, the tree is a BST.
Hence, by induction on the height of the binary tree, all binary trees for which inorder is sorted are BST.


Time complexity - least upper bound I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not stated everytime anyone attempts to explain time complexity or Big $O$ - the fact we're looking for the least upper bound of the running time.

Correct me if I'm wrong, but $O(n!)$ is known to be the highest complexity - much worse than exponential. If I have an algorithm whose running time is $O(n)$, then it is also $O(n^2)$, $O(n^3)$, $O(2^n)$, and $O(n!)$, because they are all upper bounds of its running time (I know that, because it's $O(n)$).

So is it possible to find the least upper bound of the running time? If I read an algorithm has complexity $O(2^n)$, does it mean it has been proven this is the least upper bound? Or is it just the smallest upper bound that has been found so far?

If you want to state that $O(f(n))$ is the best bound on the complexity that you can get, then you can use big Theta instead: $\Theta(f(n))$ stands for a function – in this case worst-case time complexity – that is asymptotically equal to $f(n)$ up to constants. That is, if the worst-case time complexity $T(n)$ satisfies $cf(n) \leq T(n) \leq Cf(n)$ for some $0<c\leq C$, then you can state that the (worst-case) time complexity of the algorithm is $\Theta(f(n))$. This implies both the upper bound $O(f(n))$ and the matching lower bound $\Omega(f(n))$, showing that the upper bound is best possible.