texts:
I tried to solve this exercise:

Discuss the normal forms (CNF or GNF) of a grammar with productions:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | \epsilon$

Same request with the following grammar:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | c$

I applied the rules to convert a grammar into its normal form and I think that both are CNFs.

For the first grammar:

$S\rightarrow BC | CB|C'B|c$

$B\rightarrow C'B | c$

$C\rightarrow C'C | c$

$C'\rightarrow c$

For the second grammar:

$S\rightarrow BC | CB|TB|c$

$B\rightarrow TB | c$

$C\rightarrow TC | c$

$T\rightarrow c$

Is that correct?


texts:
I am trying to implement a natural language query preprocessing module which would, given a query formulated in natural language, extract the keywords from that query and submit it to an IR (information retrieval system) system.

At first, I thought about using some training set to compute TF-IDF values of terms and use these values for estimating the importance of single words. But on second thought, this does not make any sense in this scenario - I only have a training collection but I dont have access to index the indexed IR data. Would it be reasonable to only use the IDF value for such estimation (is IDF enough to establish weight of a term in general)? Or maybe another weighting approach?

Could you suggest how to tackle this problem? Usually, the articles about NLP processing that I read talks about training and test data sets. But what if I only have the query and training data?


texts: 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

texts:
I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the question:

  In MAX-3-COLOR you are given a graph $G=(V,E)$ and your goal is to
  find a coloring of the vertices with only 3 colors $c: V \rightarrow
 [3]$ that maximizes the quality function $q(c)$ - The number of edges
  whose endpoint vertices are colored with different colors:

  $\sum_{(i,j)\in E} (1_{c(i) \neq c(j)})$

  Give a probabilistic $3/2$-approximation algorithm. (i.e $q(c)\geq 2/3 \cdot OPT$
  with probability at least $1-\frac{1}{e^{k}}$ for any $k \in \mathbb{N}$

OK so up until now the textbook only talks about one probabilistic algorithm which fits the requirements - MAX-3-SAT. The textbook gives a probabilistic $8/7$ - approximation algorithm for it (for every literal, toss a fair coin and decide whether to set it to $True$ or $False$).

I also found several other sources which prove that the 3-COLOR is NP-Complete by reducing it to the 3-SAT problem. Thus I am pretty confident that MAX-3-SAT is the way to go.

According to this thread: 3 Colorability reduction to SAT I thought about doing the same thing:

  For every $x \in V$ create three literals: $x_1, x_2, x_3 \in \{{True,
 False}\}$ where each literal denotes if said vertex $x$ is colored
  with color $i$.

  Then for every edge $e =(x,y)\in E$ create the following
  3-CNF formula $\varphi$:

  $ \varphi_e = (\urcorner x_1 \vee \urcorner y_1 \vee \urcorner y_1)
 \wedge (\urcorner x_2 \vee \urcorner y_2 \vee \urcorner y_2) \wedge
 (\urcorner x_3 \vee \urcorner y_3 \vee \urcorner y_3) \wedge (x_1 \vee
 x_2 \vee x_3)$

  And the final formula $\phi$ is:

  $\phi = \bigwedge_{e \in E} \varphi_e$

Every 3-CNF formula for an edge makes sure that the two endpoints are not of the same color and that one of them is either color 1, 2 or 3.

The thing is I don't see how this would help me. This gives me a MAX-3-SAT problem since I have a 3-CNF formula for every edge and one big 3-CNF formula for the whole graph. So technically I could use the same algorithm that was given in the textbook before

But wouldn't using the same probabilistic probabilistic $8/7$ - approximation algorithm for the MAX-3-SAT give the exact same approximation? whereas I wish to achieve a $3/2$- approximation

Thanks to anyone who helps!


texts: Sampling perfect matching uniformly at random

texts: Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am okay with a distribution that is close to uniform, but not quite uniform, then is there an efficient algorithm?


texts: Some basic questions on halt and move in Turing machines

texts:
Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.

Firstly i define an operation as follows:

Operation (Op)

Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:

replace color $C$ with $0$ or $1$. (at current position of tape head) move
tape-head (change its position).
change state $S$ with $0$ or $1$ (at new position).

For each operation:

In general does a TM only have only one halting-operation?
(i.e. can only one operation promote the halting or can more than one operation do that?).
Can the tape-head also stop at a fixed position? (i.e. not move its head).
Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?

My last question is basically the same as the last question..

Can the tape-head move more than one unit to the left or right?

The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.

Example

If something was unclear I can try this example:

  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*

Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.

The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:

  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*

Recap

So can more than one operation perform the halting operation?

Can we move the tape head more than one unit to the left or right, or can it stand still?


texts: Difference between approximation scheme and approximation algorithm?

texts:
What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?


texts: B2B integration modelling tools and standard suggestions

texts:
This question might be too broad, but I really need help with this. I am required to choose a standard or notation to model an integration between two business processes, one of which is external.

The question is - are there any standards/notations than can compete with UML Activity Diagram or BPMN. If there are, which should I choose (including the two mentioned)?

Thanks in advance.


texts: What is the formal name for an "entry" in an ontology?

texts:
I am trying to wrap my head around ontologies and their related counterparts (RDF, OWL, etc.).

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

If that's true, I'd imagine ontologies lend themselves as perfect candidates for NOSQL graph DBs.

Either way, after all my initial reading, I still haven't found what the formal/official name is for a single "entry" in an ontology. Any ideas? Ditto for what the official names of their attributes and other relationships are. Thanks in advance!


texts: Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

texts:
I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3):

  The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters has exactly 2n−1 steps.

I could get how $2n$ comes since there are only 2 variables on the R.H.S of each production but couldn't get how the expression $−1$ came in $2n−1$.


texts: Interactive proofs for coNP languages proof clarification

texts:
I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the paper can be found at http://lance.fortnow.com/papers/files/conpipl.pdf.

My question concerns the second part of the proof (the last paragraph), in the case we have a prover which makes $V_i$ accept with probability 2/3: I am not sure why there must exist an oracle query $x$ of length $N_i$ that appears in at most $p_i/2^{N_i}$ computation paths. Shouldn't there be $2^{M_i}$ computation paths where $M_i = poly(N_i)$ is the number of random bits? So then some $x$ must appear in $p_i*2^{M_i}/2^N_i$ paths, which is not clearly small.

For reference, I am reproducing the proof below:

We want to prove that there exists an oracle A and a language $L \in \mathrm{coNP}^A$ such that $L \not\in \mathrm{IP}^A$.

For any oracle $A$, let $L(A) = \{ 1^n : \text{$A$ contains all strings of length $n$}\}$. It is clear that $L(A) \in \mathrm{coNP}^A$ for all oracles $A$. We will create $A$ in stages. At each stage we look at some finite set of strings. For each string in this set, we decide whether to include or exclude this string from A. In stage $i$, we choose the set of strings so that $L(A)$ does not have an interactive protocol with verifier $V_i$. Thus, after the construction, $L(A)$ cannot have an interactive protocol and we have proved our statement.

Stage $i$: Pick $N_i$ large enough so $2^{N_i} > 3(N_i)^i$ and no oracle queries of length $N_i$ have been asked in any previous step. Let $p_i = (N_i)^i$. We will determine some strings of $A$ such that either $1^{N_i} \in L(A)$ and no prover can convince $V_i$ to accept $1^{N_i}$, or $1^{N_i} \not\in L(A)$ but there is a prover that will cause $V_i$ to accept. Every time $V_i$ makes an oracle query which hasn't been previously answered, we answer yes.

If there aren't any provers $P$ such that $P$ and $V_i$ accept on input $1^{N_i}$ with probability at least 2/3 then we put in the oracle $A$ all strings of length $N_i$ and every other previously unset string that $V_i$ asks about for any prover. This completes step $i$. Note that $V_i$ can only make queries of length less than $p_i$ so will will always be able to find $N_{i+1}$ in step $i+1$.

Otherwise we have some prover $P$ such that $P$ and $V_i$ will accept $1^{N_i}$ with probability at least 2/3. On any computation path (which is determined by $V_i$'s coin tosses), $V_i$ can ask at most $p_i$ oracle queries of length $N_i$. Since the same number of coin tosses are used during each round, the probability of each computation path is identical. There is some oracle query $x$ of length $N_i$ that appears in at most $p_i/2^{N_i}$ of the computation paths of $V_i$. By the way we chose $N_i$, this means that the oracle query $x$ appears in fewer than one-third of the computation paths of $V_i$. We put all the strings of length $N_i$ except for $x$ in the oracle A, and also place in the oracle every string queried by $V_i$ on every possible communication with $P$. $P$ will convince $V_i$ to accept with probability greater than one-third since more than a third of the computation paths are the same as before. So we are done with step $i$.


texts: Python 3 multiprocessing stacktrace CUDA failure?

texts:
I am working on a data processing script and trying to use multiprocessing so that it runs faster. Whenever I run the python script, I get the following error:

2020-12-24 18:30:22.679414457 [E:onnxruntime:, sequential_executor.cc:165 Execute] Non-zero status code returned while running ArgMax node. Name:'ArgMax' Status Message: /onnxruntime_src/onnxruntime/core/providers/cuda/cuda_call.cc:97 bool onnxruntime::CudaCall(ERRTYPE, const char*, const char*, ERRTYPE, const char*) [with ERRTYPE = cudaError; bool THRW = true] /onnxruntime_src/onnxruntime/core/providers/cuda/cuda_call.cc:91 bool onnxruntime::CudaCall(ERRTYPE, const char*, const char*, ERRTYPE, const char*) [with ERRTYPE = cudaError; bool THRW = true] CUDA failure 2: out of memory ; GPU=0 ; hostname=- ; expr=cudaMalloc((void**)&p, size);

It seems like the error is out of memory, but I am pretty confused as to how this could be the case since I am only using 5 processes and I've used 5-10 with other scripts before on the same computer. I am pretty new to multiprocessing and not the best at Python, so does anyone have any ideas on how to solve this problem? I am unable to provide the code at the moment (but can provide it shortly soon if needed).


texts:
I've stumbled upon this Question:

We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every
$ w\in A $, s.t  if $ |w| \geq n \ than \ |f(w)| < |w| $. Also, $A,B \notin \{\Sigma^*,\emptyset \} $. Prove there is such a reduction which is also polynomial-time reduction from any languages $ A,B \in P $.
This was my approach: Take $ w' $ to be the shortest word in $B$ and define $f(w) = w'$ for every $w \in A $.
I'm pretty sure the idea is correct because we simply choose $n = |w'| + 1$
and then obviously for every $w \ s.t \ |w| >= n \ we \ get \ |w| > n-1 = |w'| = |f(w)| $

So my question is, can I really choose a word $ w' $ to be the shortest word in $B$?

Also, am I correct with my approach?

Thanks!


texts: Is there a system behind the magic of algorithm analysis?

texts:
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis).  Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made.

On the other hand, the answers to another general question explain the larger picture (in particular regarding asymptotic analysis) with some examples, but not how to get your hands dirty.

Is there a structured, general method for analysing the cost of algorithms?  The cost might be the running time (time complexity), or some other measure of cost, such as the number of comparisons executed, the space complexity, or something else.

This is supposed to become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!


texts: Influence of edge number and priority-queue implementation on the runtime of Dijkstra

texts: When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations of minimum priority queue that help us find out the running time of the algorithm?


texts: Terms and definitions for regular language and NFA

texts: let's say L is a regular language,what term does L should uphold so that there is an NFA without  epsilon moves,in which for every accepting state δ(q,σ)=Ø?I can think of some terms like that the last letters can't hold a power,but I was wandering if there is a formal definition?


texts: How to make a Post Machine for $a^nb^n$?

texts:
I have tried to make a Post machine for that all words of the form $a^nb^n$ by the following steps.

add a marker '#'
read first 'a'
read next 'a's and add them
read first 'b'
read next 'b's and add them
read '#' (that we added in the first step)

repeat steps while input tape is not empty

but this algorithm also accepts words of the form $(ab)^n$ e.g abab, ababab
I want to make a Post machine that only accepts words of the form $a^nb^n$
How to do that?


texts: Why can't we replace Dijkstra's priority queue with a regular queue?

texts: I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority queue. However, the runtime will still be O((E + V) log V). However, with a queue, that runtime will be O(E + V). Can anybody find a simple example of where Dijkstra's would fail if we used a queue instead of a Priority Queue?


texts:
Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, alternatively, as a variant of this problem, in the same order) is equal to $g$, i.e. $g_{i_1} \circ g_{i_2} \circ \cdots \circ g_{i_k} = g$.

This is actually a subset sum problem, but for symmetric group $(S_n, \circ)$ instead of $(\mathbb{Z}, +)$.

The questions are:

Is there a known solution in polynomial time?
Otherwise, is this problem known as NP-complete?

I've found a paper on knapsack problems in groups, however, these results seems to be not applicable for symmetric group.


texts: Breadth-first traversal: difference between generation and expansion

texts:
The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names.

Some ground-rules: we're traversing in alphabetical order. And traversal must stop once the goal node has been generated, not expanded. This last part is where I feel like I'm not completely understanding what is being asked.

So the solution given is: Arad, Sibiu, Timisoara, Zerind, Fagaras, Bucharest.

What I think the solution is as follows: we're at A so A has been "generated". And then we expand A, giving us: A, S, T, Z. Since the goal node hasn't been generated we start with S. Expanding S gives us F and R (no goal node yet) and then we expand T giving us L following which Z is expanded giving us O.
So far we have A, S, T, Z, F, R, L, O. Now, going alphabetically, we go to F for expansion. This gives us B and this is where the traversal should stop.

So my solution is A, S, T, Z, F, R, L, O, B.

Can you tell me where I'm going wrong and why the given solution (as opposed to my solution) is correct?


texts: What algorithm for feedback control to maintain heart rate

texts:
I am writing an application that will maintain heart rate within a specified range by adjusting the resistance on a turbo trainer.
I could cobble together something that would gradually increase resistance until heart rate reached the right level but I imagine reaching the desired heart rate quickly, not overshooting and maintaining it might not be a trivial exercise.
Sadly I did not study computer science but I imagine that this problem has been solved many times before and I was hoping for a relatively simple algorithm that I can implement without spending a long time fine tuning and improving it.


texts: How to find time complexity of this pseudocode

texts:
Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$.

Then I formulated following algorithm to carry out that task:

  We do inorder traversal of BST ($sum = 0$ in start)
  But whenever we encounter any node having value strictly less than $low$ than we don't visit it's left subtree. We only traverse it's right subtree recursively in same manner.
  In same manner if we find any node having value strictly greater than $high$ than we don't traverse it's right subtree.
  If value of node falls in given range then we increment $sum$ by 1.

I think this algorithm correctly solve above problem in time complexity $O(m+lg(n))$ where $m$ is number of nodes having value in given range.

My reasoning for that time complexity is that we traverse at most $O(lg(n))$ nodes(This statement I'm not able to prove) which don't get added and we traverse $m$ nodes that gets added into $sum$. Which gives above time complexity.

At least any hint regarding how to prove this time complexity would be great.

Thanks.


texts:
I am working on a type system supporting overloading. I have a rough idea of how type inference is usually implemented in such a scenario, but I am wondering how - after type inference is completed - the correct implementation of an overloaded operator can be chosen. Or, in other words, how the inferred type can be passed back down the syntax tree to the operator.

For a small example, consider the expression (x + y) + 1 where x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N. :: stands for type of, and a | b stands for type a or type b.

The way, I assume, type inference would now work, is to traverse the syntax tree, and for each node return a type constraint:

(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

a & b in this example stands for unifying the types a and b, [a=T, b=U] is a set of equality constraints for type variables.

As expected the return type of the given expression is inferred as N[a=N], that is N where the type variable a is expected to be N.

Therefore, of the two provided implementations for the + operator (N -> N -> N, S -> S -> S), N -> N -> N should be used. In the given example, the resulting type is inferred, but not the type of the overloaded operator. My question is if there is a common pattern that is used to inform the + node in the syntax tree of the used implementation.


texts: Question about growth rates of functions involving n and logn

texts: I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $o$, $\omega$, $\Theta$ that would best describe the relationship between two functions $f(n) = (\log n)^{100} + n^{0.01}$ and $g(n) = (\log n)^{50} + n^{0.05}$. Intuitively, it seems like $f(n) \in o(g(n))$ because the extra $n^{0.04}$ in $g(n)$ grows much faster than the $\log^{50} n$ in $f(n)$. However, I am not really sure how to prove this using first principles. Could anyone provide any suggestions? Thanks in advance.


texts: Finding all unique paths from a source to a sink in a specially-formed DAG

texts:
Let $G$ be a directed, acyclic graph of order $n$, such that:

$G$ has exactly one source vertex $s$;
$G$ has exactly two sink vertices $t_1, t_2$;
The out-degree of any non-sink vertex in $G$ is exactly 2; and
The longest path from $s$ to either of $t_1,t_2$ has length $k$.

What is the most efficient way of finding all unique paths from $s$ to $t_1$ (or $t_2$, doesn't really matter in this case) in $G$? What would the time complexity of this algorithm be? It is acceptable to use $k$ as a parameter if that would produce a better analysis.


texts:
In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that

If M is deterministic, then the
graph has out-degree one, and if M is nondeterministic, then the graph has out-degree
at most two.

In the configuration graph, a directed edge is placed from the configurations $C$ to $C'$ if we can obtain $C'$ from $C$ via a single transition. Also, the authors assume we are working with two tape Turing machine with one read-only input tape and one read-write work tape. Here, the authors define a configuration by

A configuration of a TM M
consists of the contents of all nonblank entries of M’s tapes, along with its state and head
position, at a particular point in its execution.

I understand that the out-degree for a deterministic machine must be 1, but I do not see why the out-degree for the non-deterministic machine can be at most 2. Given that the authors assume that $\Gamma= \{0,1\}$, I would assume that the number of possible configurations reachable from any given configuration would be $|\Gamma||Q||\{L,R\}^2|$ for a two tape Turing machine, where $Q$ is the set of states and one head is on a read-only input tape. Why would the out-degree of this graph be at most $2$ instead?


texts: Computer Security versions of the Halting Problem

texts:
I'm plenty familiar with the Halting Problem for Turing Machines. It occurred to me after reading several posts on this site that it would be interesting, educational and useful to start a list of equivalents to the Halting Problem in terms of Computer Security. I think this might help students of computer science and allied areas come to appreciate the true depth and application of the Halting Problem in whatever their application area.

So, I ask that the proposed (or actual) equivalent problem be:

(1) One that makes sense in the domain of computer security. This can be from information management, Cryptography, hacking, or programming (ideally with a security bent, since there are plenty of Halting equivalent problems already well known in the world of programming languages and compilers).

(2) One stated with a reference to literature on that subject if possible, and maybe even (although I wouldn't require it) a proof if you know of an elegant one.

Example: I have an antivirus software on my machine, and I want to know
whether it will ever execute malicious code. As far as I can tell, this is the Halting problem in disguise.


texts: Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?


texts: Unbounded, 2-dimensional knapsack problem

texts:
I have the following problem:

There is rectangle with fixed $W > w_i$ width and $H > h_i$ height.
Given a set of item types, where each type has some $w_i$ width, $h_i$ height and $v_i$ value.
I would like to maximize the value of the items placed in the rectangle.

An item can be placed as many times as needed. Not every type has to be present in the optimal solution. Two items can not overlap.

Is there any literature available for this (or a similar) problem? Is there a name for this problem? I didn't have luck with finding info on optimizing inside a 2-D region.


texts: Where does the CPU get its first instructions from?

texts:
In order for the BIOS code to matter, it must be evaluated by the processor. However, the processor itself needs to do work to actually get access to the BIOS code, since the CPU only performs instructions that are given, something must give the instructions to the CPU (since I can't imagine a way for instructions to just "flow" from BIOS to the CPU without anything in between).

Where are the instructions for loading BIOS and passing control to it stored, and who passes these instructions to CPU so that CPU can preform them?


texts: Is undecidable(complement of R) a subset of NP-hard?

texts: Is there an undecidable problem which is not NP-hard?


texts: Natural RE undecidable problems but not Turing-complete

texts:
The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not reduce the Halting problem to it.

What is the most natural undecidable RE problem which is not Turing-complete?


texts: Shifting and adding to get multiplication values?

texts:
multiplying by 33 --> $2^5 + 2^0$
is same as (num << 5) + 1

and by 65599 as (num << 16) + (num << 6) - (num << 0)

How do you get these numbers though i.e. 16,6?? I know log can be used but Is there any other quicker way to do this?

EDITED___________________

what I need to do is create a hash function such that I have to recursively multiply with numbers like 65599 or 33... hence the shift might be a better option


texts: Area of the union of rectangles anchored on the x-axis

texts:
I am trying to solve the following computational geometry problem.

Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis.

What is (an upper bound on) the combinatorial complexity of the union $K$ of the rectangles in $S$?
Give an efficient algorithm for computing the union and its area.

I suggest using sweep line algorithm for the purpose of computing union of areas.
First we should consider queue of events. Events are just the leftmost and the rightmost $x$'s of rectangle. As in standard interpretation all $x$'s should be sorted.
Start iterations on event queue (like in standard algorithm). On every new event we can compute an area we've already covered. When two or more rectangles intersect (can be identified by data structure) we should pick the rectangle with the biggest $y$-coordinate until the next event.
That's a general idea. The main difference from the classic sweep line algorithm is that we don't have to compute intersection and inserting them to queue.  All we are interested in is intersection of rectangles which occur on vertical lines of leftmost $x$ and rightmost $x$.
I am not completely sure that the solution I presented is the correct one. This exercice was marked with high complexity grade. Maybe I missed something?
In addition, I don't know how to answer the first question.


texts: How to give a context free grammar for any given language ie: a^n (ba)^m a^n

texts:
i am trying to understand Context free grammar and generate a CFG for any given language.

when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow to help you create a CFG for any language? is there ways of breaking down the language to make it simpler so that it helps you generate the CFG.

for example if i was given  L={a^n (ba)^m a^n | n,m >=0 }

does that mean i need to have equal number of a's on both side, and have zero or more ba in between  the a's ?

S---> aSa |ε

X---> baX |ε

any helps is appreciated.


texts: Algorithm to sample high-dimensional parameter space of expensive cost function

texts:
I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to evaluate.

By expensive to evaluate I mean that one can only do O(1) evaluations per second on a modern computer.
By efficiently I mean that the algorithm should learn to avoid regions where there are no solutions: the evaluation of the cost function may fail for certain sets of parameters.
Still under the aspect of efficiency, the algorithm should yield a set of samples that represent a (ideally unbiased) coverage of all solutions in the whole parameter space within a reasonable number of samples.
The parameters are continuous numbers within predefined bounds.
The cost function is "mostly well-behaved".

I am not so much after importance sampling, so I guess I am looking for an improved random sampling that is adaptive in the sense that it learns which parts of parameter space to avoid.
Background information:
I am looking into a specific physics model where from ~20 input parameters a set of outputs (masses and decay probabilities) are computed. This is the bottleneck CPU-wise. My goal is to identify allowed ranges for the input parameters for which the outputs fulfil certain constraints that are implemented in terms of a cost function. Not all possible combinations of input parameters give meaningful physics, therefore a large (but acceptably so) fraction of calculations will fail.
At the moment I am successfully using parallel simulated annealing to find solutions (input parameters) that come very close to the known minimum of the cost function. So finding a (nearly) optimal solution is "easy".
What I would now like to improve is the coverage: sampling from the whole input parameter space (e.g. below some threshold of the cost function).
This would allow projections onto 1-D or 2-D subspaces of the input-parameter space to be done to see where valid models lie.
In this example

the yellow bin holds most of the samples because the cost function depends on this particular output such that it ought to be close to 125. The interesting part though is the dependence of the output on the input. One can guess from the plot that lower values of the input would also give the desired output, and below ~ 1000 we see some structure, where the input apparently is too low to achieve the desired output. However, the statistics is very low. Therefore, I am looking for another algorithm which yields a sampling that covers input-parameter space more evenly (subject to the constraint that invalid input parameter sets should be avoided).


texts: Proving the language which consists of all strings in some language is the same length as some string in another language is regular

texts:
So I've been scratching my head over this problem for a couple of days now.  Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose length is equal to some string in $B$ is a regular language.

In equation form:

$$L = \{x \in A \mid \exists y \in B \text{ s.t. } |x| = |y| \}$$

My initial thought was to try and come up with some DFA for both languages $A$ and $B$ and map the two states to each other and hopefully get a 1:1 ratio that way I can generate a new DFA which proves that $L$ is regular.  But then I realized that $A$ and $B$ don't have to be over the same set of symbols.

I think the correct way to solve this is to use the closure properties of regular language, but I'm not sure of how to begin/use the properties for "lengths" of strings instead of strings themselves.

Could someone point me in the right direction?


texts: Why does the substitution {x/f(y), y/z} work this way?

texts:
There is an example of applying a substitution to an expression, and I am having a problem with it.
Let $\theta = \{ x/f(y), y/z \}$, and $E=p(x,y,g(z))$,
then $E\theta = p( f(y),z,g(z) )$.

Why is $y/z$  not applied to $E$ after using $x/f(y)$, so that the answer would be $E\theta = p( f(z),z,g(z) )$?


texts:
Consider the following grammar, where $ [ \ ] \ | \ , \ $ are terminal symbols

$
\begin{eqnarray}
L \rightarrow [ \ ] \qquad(1) \\
L \rightarrow [ \ H\ T\ ] \qquad(2) \\
H \rightarrow L \qquad (3) \\
H \rightarrow L\ ,\ H \qquad (4) \\
T \rightarrow |\ L \qquad(5) \\
T \rightarrow \epsilon \qquad (6)
\end{eqnarray}
$

I went over the step to create the DFA for that grammar, and then building parsing table.

However, after creating those things, I cannot parse the string $ [\ [\ ]\ |\ [\ [\ ]\ ,\ [\ [\ ]\ ]\ |\ [\ [\ ]\ ]\ ]\ ] $
Here is the DFA:

Note: In state 11, the only lookahead is $

I think my problem is that I determined wrong lookahead for some DFA states. But I still don't know what's wrong here.

Can anyone give my some idea?


texts: When you do a remote desktop connect to another pc which pc's processing power do you have?

texts: Are you just accessing the data and things on the PC you are connecting to or, if it had a better processor/ram/etc, are you able to take advantage of that?


texts: Why are there only NOR and NAND flashes?

texts: According to my lecture and wikipedia NOR and NAND flashes are the most common used. However there isn't really explained why people decided to use these logic gates instead of others. Can someone explain me, what are the factors deciding which gates to use and show how these gates match those properties best?


texts: NP complete language having no Polytime decidable superset

texts: Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?


texts:
Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background.

Huffman Code is the binary-code induced from a binary tree, constructed by Huffman's Algorithm.
Hu–Tucker Code is the binary-code induced from an alphabetical search tree.
According to Wikipedia (see the paragraph on Optimal alphabetic binary trees (Hu–Tucker coding)):

  In the standard Huffman coding problem, it is assumed that any
  codeword can correspond to any input symbol. In the alphabetic
  version, the alphabetic order of inputs and outputs must be identical.
  Thus, for example, $A = \left\{a,b,c\right\}$ could not be assigned
  code $H\left(A,C\right) = \left\{00,1,01\right\}$, but instead should
  be assigned either $H\left(A,C\right) =\left\{00,01,1\right\}$ or
  $H\left(A,C\right) = \left\{0,10,11\right\}$. This is also known as
  the Hu–Tucker problem, after T. C. Hu and Alan Tucker, the authors of
  the paper presenting the first linearithmic solution to this optimal
  binary alphabetic problem, which has some similarities to Huffman
  algorithm, but is not a variation of this algorithm. These optimal
  alphabetic binary trees are often used as binary search trees.

My question is, what are the applications of such trees? (alphabetic binary tree)
I tried to search online, but couldn't find a satisfying answer.
I also read the introduction in Hu & Tucker's paper on the subject:
Optimal Computer Search Trees and Variable-Length Alphabetical Code, but I couldn't figure out exactly the use of such tree from their example.

I can very well understand the need of a compact, optimal prefix code, induced by an optimal tree (i.e. Huffman Code); this can be used for compression, but what is the use of alphabetical binary trees?


texts: Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

texts:
Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free.

From my understanding, we want to prove that all 3 conditions of the pumping lemma hold. This will not guarantee that the language is context-free. However, I have found a case where it breaks

Let the string be $abbccc$

If $u = \lambda$,
$v = a$,
$x = aa$,
$y = a$,
$z = bbccc$.

Therefore, when we pump the string for $i = 2$, we get $aaaaaabbcccccc$, which is NOT in the language because we have the same number of $a$'s and $c$'s. How is this possible?


texts: Would there be any advantage to using transitors of more than two states?

texts:
Binary is the result of using the simplest possible building blocks to hold memory, transistors, entities that can be switched between two states, on or off. We took that idea and ran with it, and it works very well, but I was wondering:

What if we replaced transistors with entities that could transition between more than two states. A memory building block of > 2 possible states which was simple, small, fast, cheap, etc. Would there be an advantage, such as multiplying storage per unit exponentially? Are there any failed attempts at this which could be cited?


texts: Is there a term for the psychological issue of "code loss" for programmers?

texts:
I am a programmer. I have just deleted a huge amount of code which I painstakingly researched, thought about, coded, then improved and fixed as bugs popped up for a long time.

All of that code, which took me a ridiculous amount of time, effort and general "mind work", has now been replaced by a very small number of lines which basically leverage PHP's built-in "ICU" features to properly output numbers, money sums and date/time in the correct manner for every combination of language, locale, currency and timezone imaginable.

Previously, I did not know that this already existed, so I basically replicated a lot of it myself, and I now realize how far from perfect it was. But still, I did it, and that code had in my mind "hardened" or "settled" as "gold code" which I never thought I would touch again...

Basically, I mourn my now useless, superseded, obsolete code chunks. I'm annoyed by myself for doing all that unnecessary work and it took a lot of mental wrestling to finally convince myself to go through with it.

Is this common among programmers, and does it have an established term? Such as "code loss" or "code mourning"?

Basically, even though I have really improved my application/library/framework to an extreme degree, it still feels like I've "lost all that work" because the numbers of lines are slashed so much in one go. It's not a nice feeling.


texts:
If I have the following pieces to a train set:

(12) Curve
(4) Straight

Such as this train set.

I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. It's not as simple as just creating a list , such as the following, where s=straight and c=curve, and creating all permutations, since the pieces are reversible:

sssscccccccccccc

For example, a Curve piece can either curve left or curve right. I thought about doubling the number of curve pieces and calling them 'cr' and 'cl' and then doing permutations on a list such as:

ssssclclclclclclclclclclclclcrcrcrcrcrcrcrcr

However, I think that is introducing more problems, so I'm thinking of creating a tree structure as such:

Each level of tree represents adding a new piece, where cl=Curve Left, s = Straight, cr = Curve Right.

I would then traverse each path in tree structure and determine if it forms a 'solution'. A solution would be defined as starting point = ending point, however, that is a different problem/algorithm as it requires knowing the lengths and arcs of the pieces. The algorithm would need to account for solutions that consist of all pieces (16 in this case), 15, 14 ... down to 8 (as that would be the smallest number to make a circle from the trainset in the picture). To solve those solutions, I would just create paths to all the nodes at a given level. Does this seem reasonable or other thoughts?


texts: show that language $L'$ is regular (given $L$ regular)

texts:
I am working on the following question:

  $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular.

Firstly I show my idea. When you accept it I will try to formalize it.
Every automata can has an equivalent automata with exactly one accept state. So let the automata for language $L$ have exactly one accept state $q_{accept}$.

And now we start in two places - in the normal start state $q_0$ and $q_{accept}$.
From $q_{accept}$ we guess symbol. For one symbol we do two steps. From $q_0$ we go according to symbol - one step.
A state is accepting is when two "starts" meet in one state.

Am I on the right track with this idea?


texts:
I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem:

  Suppose we have a 5 elements array to be sorted using Insertion sort.
  Time complexity will depend upon the particular arrangements of
  elements in the array. Usually, when algorithm's time complexity
  depends upon the particular ordering of elements or different instances of same
  problem size n, then different cases (i.e. best, average and worst)
  occurs. In the above example there are 5!=120 possible instances of
  problem size 5. For a instance, when elements are already sorted,
  algorithms takes lowest time, and that will be best case. For another
  instance, when elements are reverse sorted, it takes longest time, and
  that will be worst case. there are still 118 instances left. For
  average case time complexity, we should take average of running
  times for all possible input instances (including 118 left and 2
  others). That means we should take average of all 120 running time for
  different 120 instances.

Why probability distribution plays a role while computing average case time complexity? Why don't we just take a simple average of running times for all possible input instances of same problem size?


texts:
Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique.

Consider the language:
$L=\{\langle G,t\rangle \mid \text{the graph \(G\) contains a \(t\)-sized almost-clique}\}$.
Prove that $L$ is NP-complete.

Obviously, it is solved by polynomial reduction, but is it from Clique or 3SAT?
And how?


texts: How can I analyze the time complexity of this Dynamic Time Warping algorithm implemented in MATLAB?

texts:
I have a rough idea that the time complexity is O(mn) where m and n are based on the length of signals, as per this http://en.wikipedia.org/wiki/Dynamic_time_warping.

How can I determine the time complexity of the following code (source)

function [Dist,D,k,w,rw,tw]=dtw3(t,r)
%
% [Dist,D,k,w,rw,tw]=dtw(r,t,pflag)
%
% Dynamic Time Warping Algorithm
% Dist is unnormalized distance between t and r
% D is the accumulated distance matrix
% k is the normalizing factor
% w is the optimal path
% t is the vector you are testing against
% r is the vector you are testing
% rw is the warped r vector
% tw is the warped t vector

[row,M]=size(r);
if (row > M)
     M=row;
     r=r';
end;
[row,N]=size(t);
if (row > N)
     N=row;
     t=t';
end;

d=((repmat(r',1,N)-repmat(t,M,1)).^2);

D=zeros(size(d));
D(1,1)=d(1,1);

for m=2:M
    D(m,1)=d(m,1)+D(m-1,1);
end
for n=2:N
    D(1,n)=d(1,n)+D(1,n-1);
end
for m=2:M
    for n=2:N
        D(m,n)=d(m,n)+min(D(m-1,n),min(D(m-1,n-1),D(m,n-1)));
    end
end

Dist=D(M,N);
n=N;
m=M;
k=1;
w=[M N];
while ((n+m)~=2)
    if (n-1)==0
        m=m-1;
    elseif (m-1)==0
        n=n-1;
    else
      [values,number]=min([D(m-1,n),D(m,n-1),D(m-1,n-1)]);
      switch number
      case 1
        m=m-1;
      case 2
        n=n-1;
      case 3
        m=m-1;
        n=n-1;
      end
    end
    k=k+1;
    w=[m n; w];
end

% warped waves
rw=r(w(:,1));
tw=t(w(:,2));
end


texts: Speaking of "randomness" in computing terms, to what sense can any extant digital processor make "random" results?

texts:
From a very strictly adhering sense to the hardware and circuit-level operations of any standard (non-specialized, DSPs, or supercomputing systems, etc.) microprocessor follow very similar, almost exact in some ways, operations.

The typical role of the (main) processor in a computer, integrated with other hardware circuits or not, and excluding DMA is to have a memory subsystem fetch byte(s) for it to "process" in whatever way. To have a processor "randomly" selective something can be abstracted and seen from a data algorithm HLL-type point of view, but on the circuit-level the operations can only get so complex. I know some Assembly of x86, so I can demonstrate further on the details of what I'm asking.

If you fetch a byte, or series of bytes, and then use some schematic to cycle through potential jump offsets, that is the only way to do randomness? Are their other ways?


texts:
I am searching a fast pseudo-random permutation function with the following requirements.
Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset in order.
In more detail, we need an $n$-length ordered value set $V$ splitted to $k$ (contiguous) partitions. Partitioning is represented by (1) the function $part(v): V \to N$ wich returns with the partition index of the value $v$, and (2) the function $rng(p): N \to V_2$ ($p \in N$, the partition index) which returns with the bounds of the partition associated to $p$. In the same time we need the permutation function $perm(v): V \to V$, where partitions are stable:
$$v_1 < v_2 ~ ~ \land ~ ~ part(v_1) = part(v_2) ~ ~ \implies ~ ~ perm(v_1) < perm(v_2)$$
Partition number is predefined, there can be empty partitions. Permutation and partitioning must be key based: with a different key we get totally different results.
We are searching for such a $part(v)$, $rng(p)$ and $perm(v)$ (and $perm'(v)$, if possible)
It would be nice if partitions could be predefined, or at least controlled in some way (e. g. binomial distribution). It would be also nice if v (∈ V) could have an arbitrary length. The algorithms should be as fast as possible. Cryptographical secureness is a nice-to-have.
Here is an example visualization:

Where (indices from $0$):

$part(3) = 0$
$part(C) = 2$
$rng(1) = [4, A]$
$perm(4) = 1$
$perm'(4) = C$


texts:
I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles or project that have done this and that you can link to me?
Thank you in advance!


texts: Lexicographic sorting algorithm for n items labeled with R,V,B

texts:
Let A be an array A[0..n-1].

The array has n items.

Each item is labeled with one of these letters: {R,V,B}.

For example, A[0].label=V, A[1].label=R, etc.

What is the best algorithm for sorting items of A in lexicographic order? What is its time complexity?

I don't know if I could apply counting sort, because each element is in a range [0..k] with k=2, supposing that we can give an integer value to each letter (B=0, R=1, V=2).


texts: Advantage of MTZ problem formulation of TSP

texts:
In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP).  MTZ is a way of formulating the TSP as an integer linear programming instance.

I understand how MTZ works, but I'm confused why MTZ is considered a better algorithm for checking for sub-cycles and rejecting them as answers than just keeping a list of connected nodes.

I can imagine a look-up table of each node along with a corresponding boolean that defines whether a node is connected or not. Consequently, the running time of checking if a connection is valid would be O(1). If it isn't a run-time consideration, what is the reason that MTZ is preferred?


texts: Is there a Data Structure like Binary Decision Diagrams for Non-Binary Functions

texts:
Binary Decision Diagrams (BDD) take a set of binary variables $x_1, x_2,..., x_n$ as input.
Is there a data structure similar to BDDs where each variable takes more than two values? Each variable's values should be independent of every other variable. For example, $x_i$ could be assigned the three values $\{0,1,2\}$ and $x_j$ could be assigned the four values $\{0,1,2,3\}$, where $i \ne j$.


texts: What is the motivation for the defining smooth locally decodable codes?

texts:
I am interested to understand why smooth locally decodable codes were defined historically as they were (I believe it may be because they make for easier analysis in obtaining lower bounds on locally decodable codes but would like to understand exactly how). What is their advantage over locally decodable codes that do not carry a guarantee of smoothness?

N.B. My question concerns relation between locally decodable codes and smooth locally decodable codes in general - the latter is not to be completely conflated with perfectly smooth codes.


texts:
Problem:

You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i  t$ litres of red and $b_i  t$ litres of blue liquid. $t$ need not be an integer. At a time you can only do one job. You can choose some (or all) of the jobs and do it for your desired time. Given such $n$ jobs in the input and their respective $a_i$ and $b_i$ find the lowest total time in which you can get $N$ litres of red and $M$ litres of blue liquid.

How do I solve this problem using convex hull?


texts: Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?

texts:
I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing?
I am asking since this would be another way to show a problem is in NP for in order to make it NP-complete after a reduction from an NP-complete problem.


texts: How to find point of maximum overlap in both X and Y Axis?

texts:
I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a point (x.y)].

I need to write an algorithm that finds a point in the P array that appears in the largest amount of rectangles from the R array. Complexity required is O(n*logn) I know about the concept of point of maximum overlap but this refers only to the x-axis i.e. http://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/

How do I find a point of maximum overlap that fits both axis?

I thought about using a sweeping line, but I don't know how it fits the required complexity.

any ideas?

Thanks.


texts: What do we gain by having "dependent types"?

texts:
I thought I understood dependent typing (DT) properly, but the answer to this question: https://cstheory.stackexchange.com/questions/30651/why-was-there-a-need-for-martin-l%C3%B6f-to-create-intuitionistic-type-theory has had me thinking otherwise.

After reading up on DT and trying to understand what they are, I'm trying to wonder, what do we gain by this notion of DTs? They seem to be more flexible and powerful than simply typed lambda calculus (STLC), although I can't understand "how/why" exactly.

What is that we can do with DTs that cannot be done with STLC? Seems like adding DTs makes the theory more complicated, but what's the benefit?

From the answer to the above question:

  Dependent types were proposed by de Bruijn and Howard who wanted to
  extend the Curry-Howard correspondence from propositional to
  first-order logic.

This seems to make sense at some level, but I'm still unable to grasp the big-picture of "how/why"? Maybe an example explicitly show this extension of the C-H correspondence to FO logic could help hit the point home in understanding what is the big deal with DTs? I'm not sure I comprehend this as well I ought to.


texts: Is there any merging procedure for multiple scenes taking from RGB-D to avoid noise?

texts:
To avoid the noise as much as possible, I'm planning to take multiple scenes from RGB-D then try to merge them ....

so is there any research papers , thoughts , ideas , algorithms or anything to help


texts:
Bucket sort algorithm lets you sort an array of $n$ elements in expected $O(n)$ time, supposing the elements are equally distributed in the $\lbrack 0,1 )$ interval.

Is there a way to modify the bucket sort in order to sort in expected $O(n)$ time an array of $n$ elements distributed in $\lbrack 0,1)$ according to the Gaussian distribution?


texts:
I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function  $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle with weight $\leq k$ which passes, once, through every vertex? (The weight of the cycle is the sum of the weights of the edges). The second problem is finding a Hamiltoninan Cycle (a cycle that passes through every vertex only once).

I know both are $NPC$. I am interested in finding reduction between both these problems. The first reduction $HamCycle \leq TSP$ is quite easy: for every edge in the original graph you give a weight $0$ and for every pair of vertices who did not have an edge you give a weight of $1$. Then you ask whether the agent can travel with sum of path $\leq 0$. The correctness of this follows pretty quickly.

However, my question if for the reduction the other way around: $TSP\leq HamCycle$. I could not come up with an idea for such. I am aware that since both are $NPC$ there exists a reduction through Cook-Levin Theorem and $SAT$, but I am wondering if there is a direct reduction $TSP\leq HamCycle$?


texts: Lemma 2 in Knuth's "Notes on Open Addressing"

texts:
I'm trying to read Knuth's Notes on Open Addressing, and I don't quite follow the proof of Lemma 2.

The set-up
We're thinking about hashing $k - 1$ keys into a size $N$ array, with collision resolution via linear probing. In particular, we're considering sequences of hash values $a_1, ..., a_{k-1}$ ($1 \leq a_i \leq N$). All we keep track of is variables $X_1, ..., X_N$, where $X_i = 0$ if the $i$th entry of the array is open, and $X_i = 1$ if the $i$th entry of the array is storing a key.

Example
Suppose that $N = 5$, $a_1, a_2, a_3 = 1, 4, 1$. Then $X_1 = 1$, $X_2 = 1$, $X_3 = 0$, $X_4 = 1$, $X_5 = 0$.

Definition
$\begin{bmatrix} n \\ k \end{bmatrix}$ is the number of sequences $a_1, ..., a_k$ ($1 \leq a_i \leq n$) such that no overflow step occurs. The overflow step is when a key hashes to an index near the end of the array, but because $X_{\text{hash}} = X_{\text{hash} + 1} =  ... = X_N = 1$ already, we have to try to insert the key at the beginning of the array $X_1$.

In Lemma 1 Knuth proves that, for $0 \leq k \leq n + 1$, $\begin{bmatrix} n \\ k \end{bmatrix} = (n + 1)^k - k (n + 1)^{k - 1}$.

Definition
$Q(N, k, t)$ is the number of sequences $a_1, .., a_{k - 1}$ ($1 \leq a_i \leq N$ satisfying (*): $X_{N - t - 1} = 0$, $X_{N - t} = ... = X_{N - 1} = 1$, $X_N = 0$.

Proof of lemma 2
Lemma 2 states that
$$Q(N, k, t) = \begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix}
\begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

If $a_1, ..., a_{k-1}$ satisfies (*), then there is a subsequence, of length $t$, which falls into the range $X_{N - t}, ..., X_{N - 1}$. The complementary subsequence, of length $k - 1 - t$, falls into the range $X_1, ..., X_{N - t - 2}$. Knuth counts the number of each such subsequence, and the number of combining these two subsequences together to produce $a_1, ... a_{k - 1}$.

My question
He seems to argue that

$$Q(N, k, t) =
\begin{bmatrix} t \\ t \end{bmatrix}
\begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix}
\begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

But $\begin{bmatrix} t \\ t \end{bmatrix} = (t + 1)^t - t(t+1)^{t-1} = (t + 1)^{t - 1} \not = 1$, so I don't see how the conclusion holds.


texts: Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

texts:
I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:

a complete, connected, weighted graph,
vertices are defined in 3d euclidean space,
relatively low number of vertices (less than 500)
no limits on how many times a node may be visited
a fixed starting vertex
no requirement for which vertex to end at.

I've looked at minimum spanning tree algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I'm suspecting this may be a variant of the traveling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.


texts:
Here is the algorithm:

int sum = 0
for (int i = 2N; i > 0; i = i / 4) {
  for (int j = 0; j < i; j+=2) {
    sum++
  }
}

I figured this would be linearithmic, but it's just linear. I would appreciate seeing a formalized summation and not a qualitative explanation. I have tried doing this but I fail to get linear runtime.


texts: Prove correctness of recursive algorithm

texts:
I have this java function:

public int foo(ArrayList l, int n)
{
  if(n <= 1)
    return l.get(0);

  if(l.get(0) < l.get(1))
    l.remove(1);
  else
    l.remove(0);

  foo(l, n-1);
}

So I figure to show that the algorithm is correct I would use an induction proof. However what I am not so sure about is how to go about doing the proof. Will I fist need to derive some sort of mathematical formula for this function and prove that?


texts: If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?


texts: Structural induction in non-local program transformation

texts:
Assume a functional language and a specialization operation (pulling out sub-expressions):

let f x y = (h 23 x) + (g 42 y)

becomes

(* h and g specialized, results might be mutually recursive *)
let rec h_23 = ... g_42 ...
and g_42 = ... h_23 ...
in
let f = (h_23 x) + (g_42 y)

for reasons, that do not matter, a syntactic category (e.g. the application of integers to functions) shall be evaluated by the compiler. The results might be mutually recursive (which is only detectable during specialization) and thus are bound using one big let-rec.

In such a scenario, how does one prove the correctness of the transformation (w.r.t. "normal" evaluation), when the evaluation is given as a big-step semantics?

A natural approach seems to be structural induction, but I am worried about using the induction hypothesis wrongly.
The correctness property requires the explicit notion of the recursive group (say R), and evaluation of a transformed term will at some point refer to a term in that group, which is clearly not a sub-term. Can I apply the induction hypothesis on terms that appear anywhere in the premise Do I have to read up on co-induction or something completely different?

The structure of the correctness theorem looks (roughly) like this:

R is obtained via specialization
t => v        t specializes to t'
v specializes to v'
--------------------------------
let rec R in t' => v'


texts: Sorts and constructors for modelling classes in a theorem prover

texts:
I have been working in the Welder theorem prover for some time now. But I'm confused in the way they handle data-types. I'm not familiar with the terminology of sorts and constructors. Here is how one defines a list data-type in the system:

val list = mkSort("A")(Seq(cons, nil))
val nil = mkConstructor("A")(Some(list))(_ => Seq())
val cons = mkConstructor("A")(Some(list)) { case Seq(aT) =>
  Seq((head, aT), (tail, list(aT)))
}

So essentially one defines a sort for the abstract class list and then instantiates this sort with concrete classes or constructors. My question is where does this terminology come from?

To finish, would you have an idea how can I model a mathematical field using this notation? I tried:

  val element = mkSort(Seq(zero, one, notZeroOne))
  val zero = mkConstructor(Some(element)) {_ => Seq()}
  val oneADT = mkConstructor(oneID)()(Some(element)) {_ => Seq()}
  val notZeroOneADT = mkConstructor(Some(element)) {_ => Seq()}

But this says that an element has zero, one or a non-zero and not-one element. Someone suggested me to use a natural index as identifier but this would limit me to countable fields.


texts: Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

texts:
In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language will be pairwise inequivalent, i.e. every string is in its own Myhill-Nerode equivalence class.

However, what if we extend this definition to an alphabet $\Sigma$ that contains more than two characters?  Can I still claim any 2 distinct strings in $\Sigma^*$ are still pairwise inequivalent?


texts: Approximation Algorithm for Independet Set Problem: Any Explanation Please?

texts:
I am reading this note on approximation algorithms for independet set problem. I am confused of Theorem 1. and Corollary 3.

Here is the statement of Theorem 1.

Theorem 1 (Hastad [1]) Unless P = NP there is no $\frac{1}{n^{1-\epsilon}}$-approximation for MIS for any fixed $\epsilon>0$ where $n$ is the number of nodes in the given graph.

Here is the statement of Corollary 3.

Corollary 3
Greedy gives a $\frac{1}{\Delta+1}$-approximation for (unweighted) MIS in graphs of degree at most $\Delta$.

I feel like there is a contradiction between Theorem 1. and Corollary 3., no? Or because the graph in Corollary 3. is a special one with degree at most $\Delta$?

[1] J. Hastad. "Clique is Hard to Approximate within $n^{1-\epsilon}$". Acta Mathematica, 182:105{142, 1999.


texts:
All we need to do is guess $k$ vertices. We look at vertex $v_1$, and make sure $v_1$ is not connected to $v_2...v_k$. Then, we "throw" $v_1$, and look at $v_2$. We do this to all vertices.

Meaning that we only need to guess $k$ vertices, and in our working memory (which determinates NL or NP) we only need to keep 2 vertices.

Where is my mistake?


texts: I have trouble translating Turing machine language, can you help me break down language notation to English?

texts:
My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing machine to recognize the language {0n1n | n ≥ 0}.

I have found this guide on a similar problem however I cannot grasp what is going on and what is required from the language statement. Any help in regards to how to read the specified language effectively would be appreciated.


texts: How to pass comma separated values from yacc to cpp file node

texts:
I am writing a compiler in CPP using Flex and Bison and having trouble understanding passing values up the syntax tree in bison.
I have grammar like this below,  'exp' would evaluate to any number.
args_list: exp | args_list comma exp;
array_list: datatype identifier '[' number']' equal '{' args_list'}'{$$ = new array_node($1, $2, $4, $8);}

I wanted to pass args_list to the array_node but not getting how to pass? As you can see user can initialize array with any length but how to pass this list to CPP node?
for example - int a[4] = {1,2,3,4} ; I want to pass something like
new array_node(datatype, a, number, args_list)

in which I am not getting how to pass args_list so that I can have array type.
Or please suggest me another way to pass the array list to the cpp file. or how to pass whole array to cpp file from yacc?


texts: An interesting compression algorithm idea

texts:
I stumbled on this paper about compressing images using a kind of odd, but interesting idea. It seems pretty easy to implement and I was wondering if there is something wrong with it that I haven't picked up.

The main idea is that every possible number combination can be represented by an index in an imaginary list of all possible combinations.

So if we have 4 numbers that range from 0 to 255 e.g. [45, 129, 12, 32], we can pretend that it is a base 256 number, in the same way that [0, 1, 0, 1] is the base 2 number with index 5 (decimal value 5). So if we find the index of our original value then we could use that to represent it and thus achieve compression.

An example is provided where we have four pixels each one able to hold one of 3 possible color values:

So we end up representing 4 integers with just 1 (their index in all possible combinations)

This is an old paper though with no citations that I could find, but the idea seems appealing enough that I would like to test it. Is there anything wrong with the idea in general though? Anything I missed that makes it not actually implementable as a real compression algorithm.

Note: One would obviously have to split the image into windows and work on those segments individually using variable precision arithmetic since the index for a combination of values to low on the table would be huge.


texts:
While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash function, but can be easily reversed.

For example, a function $f$ takes an arbitrary string $x$ and maps it to $y$, where $|y| = c$ for some constant $c$ (i.e. $y$ is always the same length), and collisions are infrequent, so in general, $f(x) = y$.

In this case, I'm wondering if it's possible to construct a function $f$ matching the criteria above, but where $f^{-1}(y) = x$ is as easily calculable as $f(x) = y$, in a computational complexity sense.

In the case of collisions, where $\forall x \in S$,  $f(x) = y$,  $f^{-1}(y)$ might give you either the entire set $S$, some subset of $S$, or even a single element from $S$

In the case that this is not theoretically possible, possibly due to the fact that $f$ allows strings of arbitrary lengths and $|y| = c$, so infinite collisions must occur(?), then what if we only allow $|x| < C$, such that the number of possible collisions are finite?

Obviously, you wouldn't use this kind of function for anything security related, but it might be useful for something like reverse image searching?


texts: Recover boolean vector from dot products

texts:
Question:

I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product of $b$ with a real-valued vector $v \in \mathbb{R}^n$ of my choosing. I.e., access to $b$ is available through evaluation of the map
$$v \mapsto b^T v.$$
How can I recover all of the entries of $b$ using as few of these dot products as possible? (maybe even just 1 dot product?)

Below I detail a couple ideas I had which might work in theory, but which don't work in practice (I think). For concreteness, one may assume that $n \approx 1 \text{ million}$, and arithmetic is done in double precision floating point format. This question arose as a subproblem in a machine learning application.

Idea 1:

One idea I had is to use a vector with fast growing entries. Say, for example, $n=9$. Then we could use the vector
$$v=\begin{bmatrix}1 & 10 & 100 & 1000 & \dots\end{bmatrix}^T.$$
One could then read off $b$ as the digits of $b^T v$. The problem with this solution is that the numbers grow so fast, that in finite precision computer arithmetic it will not work for large $n$.

Idea 2:

Another idea I had was to use a vector with entries that are algebraically independent. Then determining $b$ from $b^Tv$ is a subset sum problem.

For example, if $n=3$ and
$$v = \begin{bmatrix}\pi & e & 1\end{bmatrix}^T,$$
then $b^T v$ will take on one of a finite number of possibilities,
$$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}.$$
We can determine which of these is the case, thereby determining $b$.

But this seems quite combinatorial, and therefore unfeasible for large $n$.


texts: Can a computable function converge to an uncomputable number?

texts:
Does there exist a computable function $f:\mathbb{N}\rightarrow \mathbb{Q}$  such that:

For all $t\in\mathbb{N}: 0\le f(t) < X$
$\lim\limits_{t\rightarrow\infty} f(t) = X$

Where $X$ is an uncomputable real number.

The only reference to this question I have found was the answer to this question: https://math.stackexchange.com/a/1052579/168764, where the function seems that it would hold, but I have no idea how to prove that the limit of this function is an uncomputable real number.


texts: Counting Graphs (Minimum Number of Bits Required To Encode Certain Graphs)

texts:
Background: I am interested in finding succinct data structures for certain types of graph classes, particularly partial k-trees. For general graphs, there are $\binom{\binom{n}{2}}{m}$ graphs on $n$ vertices and $m$ edges, and so the minimum number of bits required to encode a graph is simply the $\log$ of the amount above. In general, a succinct data structure for a combinatorial object is done in $OPT + o(OPT)$ bits, where $OPT$ denotes the optimal amount of bits required for the encoding.

However, I've found out that this is quite difficult for certain graph classes, such as partial k-trees or planar graphs. Namely, I would like to know, for any $k$, how many partial k-trees on $n$ vertices and $m$ edges are there (and the same goes for planar graphs). The reason I ask is because: how does one know if a data structure representation for a particular graph class is succinct if we do not know how many such graphs there are $n$ vertices and $m$ edges (i.e if we do not know what $OPT$ is)? As far as I can tell, there doesn't seem to be an expression for the number of planar graphs on $n$ vertices and $m$ edges... and there is much less work done for the case of partial k-trees.


texts: Relationship between Coloring a graph and its complement

texts:
Let $G = (V, E)$ be a graph and $G^*$ its edge complement (that is, $G^* = (V, E^*)$, where an edge $\{u, v\} \in E^* \Leftrightarrow \{u, v\} \not \in E$).

What is the relationship between a coloring in $G$ and a coloring in $G^*$ ?

I was expecting something like

"If $G$ accepts a $k$-coloring, than $G^*$ accepts a $(n - k)$-coloring"

but I can't prove that.

(Of course, I am dealing with proper coloring)


texts: Definitions of and difference between adaptive online adversary and adaptive offline adversary?

texts:
I recently started learning about randomized online algorithms, and the Wikipedia definitions for the three adversary models are very unhelpful to put it mildly. From poking around I think I have a good understanding of what an oblivious adversary is. From my understanding, the oblivious adversary must determine the "worst possible input sequence" before we even start running our algorithm. Let $I_w$ denote the worst possible input sequence this adversary comes up with. (I.e., the input sequence that produces the greatest gap between the best that can be done and what we expect our algorithm to do.)

We then say that our algorithm is $c$-competitive (for a minimization problem) under this adversary if $$E[Alg(I_w)] \le c \cdot Opt(I_w) + b$$
where $c,b$ are some constants, $E[Alg(I_w)]$ is the expected value of our algorithm on the input, and $Opt(I_w)$ is the cost if we had made perfect decisions. (I.e., if the problem went offline.)

My confusion concerns the adaptive online and adaptive offline adversaries. I neither fully understand their definitions nor the difference between them. I will list my confusions directly below.

As I understand it, both of these adversaries somehow build the input sequences as your online algorithm runs. This says before you create the input at time $t$, unlike in the case of the oblivious adversary, both the adaptive online and adaptive offline adversaries have access to the outcomes of your algorithm at time steps $1, \ldots , t-1$. Then it says that in both cases the adversary "incurs the costs of serving the requests online." The difference being that for the online adaptive adversary, it "will
only receive the decision of the online algorithm after it decided its own response to the
request." Does this mean that the difference is that the offline adaptive adversary can see how your algorithm performs during future steps? Or just the present step? But then why is it still incurring the cost of serving requests online?
This source contradicts the source above. It says that the adaptive offline adversary "is charged the optimum offline cost for that sequence." Like I said previously, the previously source says both incur "the cost of serving the requests online." What does it even mean to incur the cost of serving requests online vs. offline? Which is correct?
This takes a completely different tack and talks about knowing randomness (online adaptive) vs. knowing "random bits" (offline adaptive). Is this equivalent somehow? How so?
How does the definition of the competitive ratio change for these two adversaries? Most sources I looked at just defined the competitive ratio for the oblivious adversary.

A simple example of each to illustrate the difference would be much appreciated. Thanks for the help!


texts: Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary?

texts:
May anyone explain me why $\forall x \in \mathbb{N}\ \Phi(x,x)$ is unary but $\Phi$ is binary?
In my latest exam I wrote that the universal function $\Phi^n(x_1, x_2, ..., x_n,y) = \psi^n_y(x_1,x_2,...,x_n)$ is unary because its $n+1$ parameter is a constant referring to the number of the S-program ($y$), but my teacher corrected me writing: "Pay attention: $\Phi$ is binary (and its second parameter is not a constant), but $\Phi(x,x)$ is."


texts:
From Wikipedia: In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

But the problem is that to get the "appropriate" specification is not a trivial task, and there is no 100% correct method (as far as i know) to get the right one, it just an estimation, so if we are going to take a predicate as a specification just because it "looks" like the "one", why not taking the program as correct just because it "looks" correct?


texts: Issue understanding the reduction of SAT to 3-SAT in poly time

texts:
Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way,

Suppose $C_1$ is $\{x_1, x_2, x_3, x_4\}$. It's equivalent representation in 3-literal clauses is,

$C_{3-SAT} = \{\{x_1, x_2, y_1\},\{\bar{y_1}, x_3,x_4\}\}$

The issue lies here. Assume for $C_1$, all the literals are $False$ except for $x_2$.
For $C_{3-SAT}$, the first clause would indeed be $True$, but the boolean value for the second clause depends on the choice of $y_1$. What if we chose $y_1 = True$? then, $C_{3-SAT}$ will be $False$, yet $C_1$ is $True$, realizing a false reduction.


texts: Was multiple inheritance ever implemented by adding redundant data members?

texts:
In discussions about why most languages which implement inheritance only implement single-inheritance, the question of the precise semantics of overlaps often comes up, and having redundant data members is sometimes given as an example semantic that would be undesirable. Note that this semantic effectively implements inheritance with composition.

Given that "prefer composition over inheritance" seems to be the current prevailing wisdom, having overlaps be redundant doesn't sound as bad as it once did.

So my question is:

Are there any programming languages which implemented multiple inheritance by adding redundant data members? How did that turn out, if so?


texts: What is tight NSPACE complexity of $ALT\text{-}SPACE(a(n),s(n))$?

texts:
According to Ryan Williams's answer $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(a(n)\log n)$.

  Does there exist any better bound (for example something like $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(\log (a(n))\log n)$), or is it tight or an open problem?


texts: Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe?

texts:
In the set cover (SC) problem we are given a universe  $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe. The set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe.

If I add the constraint that $m=n$ to SC, is this new problem still NP-hard?

My attempt is as follows:

To construct an instance of the new problem we do:

If $n=m$, then we are done.
If $n>m$, then we simply add $n-m$ dummy sets to the collection $S$ and we are done.
If $n<m$, then ... (I am stuck). But I think since the union of the $m$ sets is $U$ then we must have that $S$ contains redundant sets. Is this OK?


texts: Which NP-Complete problem has the fastest known algorithm?

texts: In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?


texts: How to remove null production from context free grammar?

texts:
How to remove null production and simply the grammar?
$$
S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A
$$
Can the simplification result in this CFG?
$$
S \to a \mid aBa \\ A \to b \\ B \to b
$$


texts: Not able to prove non regularity using pumping lemma

texts:
$L$ = $0^p1^q0^p$. Where $p, q \geq 0$

Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$

So how do I prove it to be non regular using pumping lemma as there doesn't exist a string $w \in L$ which cannot be decomposed into the form $ux^iv$ for all $i \geq 0$.


texts: Can a process run if there's not enough space for minimum pages?

texts:
I'm studying OS and I came up with this scenario where the OS works with a paging scheme and virtual memory, and a process wants to start running, but in memory, there's not enough space to allocate the minimum pages the process needs.

So I was wondering, will the OS try to allocate the process pages and end up thrashing? Or will automatically discard the process and trap indicating there's not enough space?

I know there are techniques to avoid thrashing but I don't really know how they are implemented and what the system considers appropriate to run in the system.


texts: Generate a uniform random numbers in $O(1)$

texts:
Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.)
How do we generate a uniform random number in $\{0,\cdots,m-1\}$ for $m\leq n$? We require that we can only call $G()$ $O(1)$ times in expectation.
My effort:
Suppose $n=km+r$, where $k$ and $r$ are integers. Call $G()$. If $G()\leq km$, return $G()\mod m$; otherwise, call $G()$ again.
But in expectation, this will call $G()$ $O(\frac{n}{n-r})$ times, and $r$ can be $1,\cdots,m-1$.


texts:
Candy Allocation Problem: Suppose there are $n$ candies, each with a weight $w_i$ gram. There are $m$ kids, and each kid needs to eat at least $\omega$ grams of candies to be full. Candies cannot be cut into pieces. Is there a candy allocation algorithm such that at least $k$ kids can be full?

Is the above problem NP-complete? It has some similarity to knapsack, but not exactly the same. Can someone help me?


texts: Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

texts:
I had this question in my exam. but my answer is wrong(I didn't receive explanations why...)
$$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \cap L(M) \texttt{ if } n>100\texttt{ and }L(M)\cap \left \{ 0,1 \right \}^n \neq\varnothing \texttt{, otherwise undefined}\right \}$$
I answered it is computable.
for input $(\langle M\rangle,1^{n})$ when $n \geq101$
I run the machine on all possible inputs in $\Sigma^{n}$ and output the first result when conditions are
met.
I was wrong and apparently the language is not computable. what did I miss?


texts: Tight upper bound on height of a red-black tree

texts:
"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that

  A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$,

i.e. $h \le 2\log(n+1)$.

Can equality part of the above, $h = 2\log(n+1)$, ever be satisfied?
If not, what is the best known upper bound?

My attempts to assert that are telling me that cannot be the case.

Let's denote black height of a node $x$ as $bh(x)$.

Assume a red-black tree of $n$ internal nodes and height $h = 2\log(n+1)$.
Let's consider $h_\min$, the shortest path to a leaf node. We know that

$$ h_\min \ge bh(root)$$

since path to $h_\min$ can be can either all black or have some additional red nodes; and

$$ bh(root) \ge  \dfrac{h}{2} = \log(n+1) $$

since $\dfrac{1}{2}$ is the smallest fraction of black nodes in the longest path (height).

In the proof of Lemma 13.1 we have that the number of internal nodes of a red-black tree is at least $ 2^{bh(root)}-1 $, so the size $n$ of our tree is
$$ n \ge 2^{bh(root)}-1 \ge 2^{\log(n+1)} - 1 = n + 1 - 1 = n$$
I'm surprised that that lower bound on number of internal nodes actually gives the exact result. But maybe it's just my intuition that is wrong.
The tree up to depth $h_\min$ is a full binary tree (that includes black leaf nil nodes). We want to count only internal nodes, so let's count the number of nodes $m$ at depth one smaller i.e. $h_{min} - 1$
$$ m = 2^{(h_\min - 1) + 1} - 1 = 2^{h_{min}} - 1 \ge 2^{\log(n+1)}-1 = n+1-1 = n $$
We also know that height of the whole tree is
$$h=2\log(n+1)$$
which is twice what we've considered, so there must be some internal nodes at depths larger then $h_\min - 1$, i.e. $ n > m $ but that leads to a contradiction
$$ m = n \land n > m \implies m > m $$
So that suggests that the original assumption, $h = 2\log(n+1)$, cannot be true.


texts: Computability of Kolmogorov complexity in total languages

texts:
It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages?

For example, is the Kolmogorov complexity of natural numbers computable if we work in Gödel's System T? (I suppose not, but I don't have a proof.) Furthermore, is it known what is the strongest computational model in which the Kolmogorov complexity is computable?


texts: Classification of a box relative to a line algorithm

texts:
I'm having trouble understanding the correctness of the following algorithm: why is the choice of the $p_n$ coordinates correct? Also, in figure 3.8 $n$ is pointing left and up, so according to figure 3.7 the vertex we should choose is the bottom right one (instead of the top left one), isn't that right?
I also don't understand how can $p_n$ lie in 4 quadrants, can't be only point up-right (if the slope of the line is negative) and up-left (if the slope is positive), meaning there are only 2 possible quadrants?

Taken from

Computer Graphics From Pixels to Programmable Graphics Hardware By
Alexey Boreskov, Evgeniy Shikin


texts: How to prove NP-completeness of this mail-problem?

texts:
Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the vertices represent the people's houses the mails are brought to. If the graph has an edge from a to b, it means it is an accepted path to travel. Each postman must go from one house a to the next house b and cannot detour to a house c during that time. The post office manager says that a yes instance to this problem means that there exist n cycles so that

Each of the cycles contains a vertex x (represents the post office).
Every vertex except for x only appears once in each n cycle.
Each n cycle is of equal length.

The manager then wonders how to prove that this problem containing 3 cycles (3 equals n, so there are 3 postmen in this case) is a NP-complete problem?
Thank you.


texts:
I'm autistic and I think a bit differently. I have superior memory and visual thinking, but I have a problem with converting real thing to abstract. I'd like to model reality processes with Petri nets. But... when I think of cooking meal or using a coffee vendor machine, I see in my head vegetables, kitchen utensils, cooking books and coffee machines I have seen in my entire life, but no graphs.

I am able to draw for example binary counters, because their graphs look like real things. But I can't see Greek salad as a graph. I need some help. When I see the examples, I should learn it all very quickly, but now I have nothing to start and nobody to ask.


texts: Binary Indexed Trees: Why does i & -i work?

texts:
I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next node is accessed based on the current nodes index according to $i \mathrel{\&} -i$.

I know physically that $i \mathrel{\&} -i$ gives you the highest power of 2 that divides $i$, essentially the least significant set of bits, but I don't see why adding or subtracting this to/from the current index allows you to jump around to get to the wanted node.

Linking this back to the tree representation,

      4
   /     \
  2       6
 / \     / \
1   3   5   7

I see how the left parent of a node with index N is $(N - 2^h)$ and the right parent is $(N + 2^h)$ where h is the height of the subtree from N down (including N), and this seems to be related to why the $i \mathrel{\&} -i$ works.

However, what about the cases like finding the previous node of 5, which according to $5 - 5\mathrel{\&}-5$ is 4? The formula $N - 2^h$ also seems to work except there is no direct link between 4 and 5. How do you prove that it works in these cases too?


texts: Given a set of sets, find the smallest set(s) containing at least one element from each set

texts:
Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible while still meeting this criterion, although there may exist more than one smallest $M$ with this property (the solution is not necessarily unique).

As a concrete example, suppose that the set $\mathbf{S}$ is the set of national flags, and for each flag $S$ in $\mathbf{S}$, the elements are the colors used in that nation’s flag. The United States would have $S = \{red, white, blue\}$ and Morocco would have $S = \{red, green\}$. Then $M$ would be a set of colors with the property that every national flag uses at least one of the colors in $M$. (The Olympic colors blue, black, red, green, yellow, and white are an example of such an $M$, or at least were in 1920.)

Is there a general name for this problem? Is there an accepted “best” algorithm for finding the set $M$? (I’m more interested in the solution itself than in optimizing the process for computational complexity.)


texts: Undergraduate Computer Science Textbooks

texts:
What books would you recommend for someone starting B.Sc in Computer Science?

My Personal Info:
I am currently looking at B.Sc in Computer Science (Games), which is computer science, accept for the last year which is tailored more towards game dev.

I have a fair bit of programming experience with Unity and other things. But as far as CS goes, have little to no experience. I have just finished reading 'Introduction to Computation and Programming Using Python'. But am after something more in-depth and maths based.

My maths experience is quite poor which concerns me, as I have only studied maths up to GCSE level. (GCSE = English, there is no American equivalent. Taken at age 16)

Understanding CS is a broad topic, I was just looking for some reading that could introduce me to some key ideas that could be covered in an undergraduate course at uni.

Thanks for your time,
Magnus :)


texts: Counting the number of connected components in a dynamic plane graph

texts:
I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{V_i \in P} |V_i|$ is maximized. (That is, the partitions are as balanced in size as possible.) This is the balanced connected partition problem on planar graphs, and is known to be NP-complete.

I'm trying to use hill-climbing to solve this problem. Let $C$ be a $|V|$-length array, such that $C[i] = j$ implies that vertex $i$ is in $V_j$. This represents a partition $P_C$ of $V$, such that $V_k = \{i \in V \mid C[i] = k\}$. Let $G_C = (V, E_C)$ be the corresponding graph $\bigcup_{V_i \in P_C} G[V_i]$. Thus, $E \setminus E_C$ is the set of all edges $(u, v)$ such that $u$ and $v$ are in different vertex subsets.

A "move" in this space (for the purposes of hill-climbing) is performed as follows. Let $N(v) = \{w \in V \mid (w, v) \in E\}$ be the neighbors of a vertex $v$ in the original graph. Let $(u, v)$ be an edge in $E \setminus E_C$. For all $w \in N(v)$, if $C[w] = C[v]$, remove $(w, v)$ from $E_C$; otherwise, if $C[w] = C[u]$, add $(w, v)$ to $E_C$. This induces a different partition, one where $v$ is in $u$'s subset.

It's of course possible that the graph induced by these partitions contains more than $d$ connected components. I want to penalize these, proportional to the absolute difference between the number of connected components in the graph and $d$. The problem is that finding these connected components is expensive—$O(|V| + |E|)$ time per step—and I'd like to reduce that.

I did some snooping around in the space of fully dynamic graph connectivity algorithms. For general graphs, Holm et al. (see [1]) achieve $O(\log^2 n/\log \log n)$ insert/delete and $O(\log n/\log \log n)$ connectivity queries (i.e., are $u$ and $v$ connected?) by using Henzinger and King's Euler-tour trees (see [2]). For planar graphs, Eppstein et al. (see [3]) achieve $O(\log n)$ insert/delete/connectivity.

The problem is that I'm not sure that it's trivial to adapt any of these results to my problem, since I'm not sure that transforming connectivity queries into connected-component counts is easy or possible. The other thing is that those results support general edge insertion and deletion, which is good, but I want to know if I can exploit the fact that I know all of the edges that can ever be inserted or deleted ahead of time to do some precomputation and speed up connected component counting.

I've also had the following insight. Let's say we move $v$ to $u$'s subset as described above. Call the original graph $G_1$ and the new graph $G_2$. Then the number of connected components in $G_2$ is the number of connected components in $G_1$, minus the number of vertices $w$ in $N(v)$ that weren't connected to $u$ before but are now (i.e., every path from $u$ to $w$ goes through $v$), plus the number of bridge edges $(w, v)$ for $w \in N(v)$ and $C[w] = C[v]$ (i.e., the number of $v$'s neighboring edges that, upon removal break connectedness of $v$'s original subset).

Does anyone know of any kind of solution to this problem? Or does anyone have any suggestions for papers to read?


texts: I use Princeton's WordNet in NLP applications. I always read that it is "human-curated." But how is it curated? Who decides that words belong in a synset? How does the process work? Wikipedia does not give many details. How does it work?


texts: Different characterization of $\Delta_2^P$

texts:
$\Delta_2^P =P^{NP}$, is the set of all languages decidable by a polynomial Turing machine with access to a SAT oracle. I came across a definition of $\Delta_2^P$ as the set of all languages $L$ such that there exists $L_1\in NP, L_2\in coNP$ where $L=L_1\cap L_2$.

I'm trying to prove that a language in $P^{NP}$ can be expressed by such intersection. Let $L$ be some language in $P^{NP}$, $x\in L$ if $M$ (the machine with access to a SAT oracle) accepts $x$ using some transcript $w$ (the answer of the oracle to the queries raised by $M$). I need to make sure $w$ is a valid transcript (i.e. doesn't lie by giving no answers for satisfiable formulas or yes answers for unsatisfiable formulas). I tried somehow encoding this condition in an intersection of a language in $NP$ with a language in $coNP$, but didn't succeed. Can you give a description of $L\in P^{NP}$ using such intersection?


texts: Unconditionally fair, weakly fair, and strongly fair scheduling

texts:
I am trying to understand the difference between weakly fair and strongly fair scheduling.

For example, what scheduling policy would ensure that a process delayed at its first await statement will eventually be able to proceed?

weakly fair: A condition becomes true and remains true at least until after the conditional atomic action has been executed.

strongly fair: If the condition is infinitely often true, a process will eventually see it as true and be able to proceed.

I feel that it needs strongly fair scheduling because the process is being delayed at its await statement but I am not sure.

If someone could provide a good explanation, something besides temporal logic?


texts: How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction?

texts: The question is already stated in the title.


texts:
Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?
I should probably use Ogden's lemma, but I don't know how to do that in this case.


texts: Understanding the fundamentals of building an in-Memory Distributed Graph

texts:
I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple nodes in a network.

I know basic graph data structure. I googled to know about distributed graph, but what I found mostly is just an info about existing distributed graph databases like titan, FlockDB etc. But I really couldn't find any fundamental guide to building a distributed graph or in general explaining a basic algorithm of building a distributed graph.

Can you please suggest few references where I can get such material explaining the fundamentals.


texts: What does it mean this relation: $BQP^{BQP} = BQP$

texts:
I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following:

  Bernstein and Vazirani [BV97] show that BQP can simulate any deterministic or probabilistic polynomial-time algorithm and Bennett, Brassard, Bernstein and Vazirani [BBBV97] show that  $BQP^{BQP} = BQP$. In other words we can do quantum subroutines and build that directly into the quantum computation.

Now, my question what it means by $BQP^{BQP} = BQP$? For example, BQP is given an oracle to BQP, So I don't see any words that can describe it except that it might mean BQP is closed under its running time, so anything that runs in efficient in quantum computing, calls another an efficient quantum algorithm in quantum computing, then it is always in total an efficient in quantum computing. Does this what it means by  $BQP^{BQP} = BQP$?

Note that I understand 'oracle' or 'relativized world' from Sipser's textbook, For example: we can have the following: $P^A = NP^A$ given that A is an NP-complete language.

Thank you.