texts: Find every path that passes through certain edges

texts:
I'm faced with the following problem:
Given

Directed and unweighted graph, where each edge E has two attributes

Goal

Find every path through the 3 (or more) given edges in a specific order

Questions

Is it NP-hard?
Is there already an algorithm for this?
I was thinking about placing a node in every edge and than run Dijkstra algorithm to find the shortest path from A to B and then from B to C. Although, this complicates my graph. Any other ideas? Thanks


texts: Compiler instructions to sync core caches: are they really needed?

texts:
I have read reviews of this book, and quote the following from one of the reviews (emphasis mine):

  Other than straining your eyes with old-styled C++, you can read such
  misconceptions in the book like "Since Boolean values are generally
  atomic, setting and checking can be done simultaneously without risk
  or requiring a mutex." Which ignores the facts that, the compiler
  doesn't necessarily have to generate instructions to resync the value
  in register with the one in memory. And even if it does, the hardware
  doesn't have to resync the cache lines.

I have also followed all of the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube) and learned about cache coherency protocols.

From what I have learned, modern processors will use the write-invalidate protocol; when one core writes to a block, any other cores that share this same block will learn of the change via an invalidation message sent on the bus so they will have to go and get the new value from memory instead of using their cached copy.

With this in mind, what is the author of this comment talking about?  It seems the coherency protocol is doing everything for me, hence there is no need to use synchronisation?  Are they wrong or am I missing something?

PS Yes I know I mention C++ but I feel this is more hardware related hence me asking it here.

PPS If I've missed something, please post a link to the information before just downvoting; a downvote without explanation is useless.

Update

If a boolean b was being used in two threads, each one on a different core, what would making the variable atomic/using a sync variable do regarding the cache coherency that doesn't happen with a none-atomic var/no use of a sync variable?  (I think this is the problem in my understanding - I am believing that the cache coherency protocol fires off "for free" (is this right?); or do I need to use some special instruction to "start it off" (that is, trigger the sending of the invalidation message on the bus) for want of a better phrase?)

Update 2

Write Invalidate Snooping Coherence - Georgia Tech - HPCA: Part 5 talks about how the caches of different cores operating on the same block are synchronized.

My confusion stems from the fact that the comment I quote seems to state that boolean values are not guaranteed to be synchronized between caches on different cores, and that some sort of atomic operation or synchronization primitive (eg mutex) is needed to do this.  The video I link to however mentions nothing of the sort; it suggests (to me at least) that the caches are updated automatically by virtue of the coherency protocol, not by any special instructions (such as those generated for atomic operations or synchronization primitives) in the code.  This is what I am asking for clarification on.


texts: Can nfa consume more than one letter at a time

texts:
If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.

like the example shown


texts:
The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are

LL(1)
LR(1)

I guess they can't be LL(1) because of left recursion, but how do we prove that they are LR(1) if so.


texts: Predicting next action to take to reach a final state

texts:
Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data?

For example, a robot starts at a certain state, then takes an action to get to another state. This occurs continuously for many iterations (imagine the robot is randomly exploring a room). If the robot is at a specific starting state, and I desire the robot to end up in a different state, is there an algorithm that could recommend the best next action (or set of next actions) to take to reach that final desired state?

One approach I've tried is to use a neural network with the current state and the next state being the input and the action to get from the current state to the next state being the output. The network would know for a single state how to get to a next desired state that is one action away. The issue is, what if the desired state is many actions away?


texts: Has the concept of using a hand checked simple theorem prover to validate more complex theorem provers been explored before?

texts:
More specifically, has anyone used a chain of theorem provers to validate a highly evolved theorem prover, starting with a very simple hand checked prover such that each new theorem prover is used to validate a somewhat more complex theorem prover, rinse repeat?

This would be something along the lines of induction, I guess. In that you'd have just as much confidence in the complex prover at the end as the hand checked prover you started with.

If it has been explored (wouldn't be surprised), a pointer towards more resources would be welcome.


texts: Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?

texts:
Let us say we have $m$ bins and $n$ balls. Every bin $i$ has capacity $c_i$ which is the number of balls that can be put into bin $i$. We have $c_i\geq1$ for all $i$. For each bin $i$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$. Each $X_j\in S_i$ is the set of balls that can be put into bin $i$. We have $|X_j|\leq c_i$ and $\emptyset\in S_i$ for all $i$.

For example, for $m=2$ and $n=3$, with $c_1=1$ and $c_2=2$, say we have $k_1=4$ and $k_2=5$. Say we have $S_1=\{\emptyset,\{1\},\{2\},\{3\}\}$. $S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\}\}$. This means that ball $1$, $2$ or $3$ can be each assigned to bin $1$. Also, each ball can be assigned to bin $2$. Further, balls $2$ and $3$ can be together assigned to bin $2$. We might have an instance with $k_2=6$ and $S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\},\{1,2\}\}$ for example.

We want to assign the maximum number of balls into the bins. Is this easy or hard?


texts: Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$

texts:
Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$.
Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that contains $e$ such that for every $e' \in C, e'\neq e$  :  $w(e')\leq w(e)$.

I thought maybe because the weights are bounded I can run Kruskal multiple times and each time delete edges with a specific weight, and that without changing the complexity.
Would appreciate your help:)


texts:
I am to arrange the following 30 functions in terms of increasing order
( all the lg (log) are to the base 2.log* represents iterated logarithm.)

Here's my answer (the functions on the same level are of the same order):
1 ,
lglg*n
lg*n,      lg*(lgn)

 ,
 ,
 ,

,

I am not sure where to insert (logn)!. I know (logn)! = o((logn)^logn) and logn = o((logn)!), isn't it. But where exactly would it fit. Can anyone help me with that. Also I would really appreciate if someone could verify that my arrangement is right or not.
Thank you.
EDIT : I MEANT TO ASK THE POINT OF INSERTION OF (LOGN)! IN THE ABOVE LIST SORTED IN TERMS OF INCREASING ORDER. Simple.


texts: What does a proof that Co-NP =P entail for the NP versus Co-NP question

texts:
What I wonder is what exactly would it entail. Would it,for instance imply that P=NP or would there be different consequences,I haven't found any assorted consequences so far in my research.
Thank You,
Akash


texts:
I have a loop:
for(int i = 1; i < N; i*=5) {...}

where {...} is some statement.

I'm trying to understand its run time. So, far I know that:

We start with $i = 1$
We finish when $i > n$
$i$ is incremented by being multiplied by 5.

So, would the run-time be $\log_5(n-1)$? The reason I'm not sure it's because I thought when analyzing algorithms we had to use base 2 log functions. If the latter is the case how would I got about converting $\log_5$ to $\log_2$?


texts: Beginnings of multiptogramming and compilations for it

texts:
I want to know how the first programs to be able to execute more than one programs within a common time span were like . I went through the history of the topic and
it seemed like Strachey was the first one to work on multi-programming . Hence , i thought of reading his paper "Time sharing in large and fast computers"

Where can I find this paper ?

Is it so that in multi- programming , two addresses are stored in a memory location and the program counter is sequentially switched between the values in the two locations and after the execution of instructions the value in the corresponding register is incremented ? So basically for a language to support multi-programming the keyword or function ,it should use to create concurrent programs or to make two programs run in parallel , should translate to a machine code having conditional jump instructions .

For example , a version of AlGol 60 ,  used "cobegin" and "coend" keywords to mean the parallel execution of two streams of instructions as follow :

Cobegin :

process 1 Begin :..... End

process 2 begin .......End

Coend

So , is it so that cobegin and coend translate to a machine code which stores the addresses of the machine codes obtained from translation of process1 and process 2 to two different registers , and use jump instruction to  sequentially switch between the present values in the registers which are incremented as the programs get executed .

P.S : It would also be  of great help , if someone can point towards a link where the code for the OS used by Burrough's written in ALGOL60 is available provided such a link exists .


texts: Injectivity not required for unification algorithms?

texts:
When learning about a general unification algorithm, we learned the rule decompose, which states unifying

$$G \cup \{f(a_0,...a_k)=f(b_0,...,b_k)\} \Rightarrow G \cup \{a_0=b_0,...a_k=b_k\}.$$

The question of, "What if $f$ is not injective?" stood out to me. Say $f$ is not injective, and we traverse that branch of computation where $f(a_0,...a_k)=f(b_0,...,b_k) \Rightarrow \{a_0=b_0,...,a_k=b_k\}$ and lead to failure. Is it possible that there's another way to assign $a_0,...,a_k$ to $b_0,...b_k$ such that it's unifiable?

I was thinking maybe of an example to demonstrate what I mean. This may not be a good example, but say we consider $f(x,y) = x+y$, and we want to unify $f(h(a),g(b)) = f(g(c),h(d))$ then we would fail by assigning $\{h(a) = g(c), g(b)=h(d)\}$ by decompose, but succeed in unification if instead we first switch the arguments of $f$ (valid since $f(a,b)=f(b,a)$), which will yield $\{a \mapsto d, b \mapsto c\}$.

I was reading a bit about it in this paper on page 6 where they discuss the idea of strictness in terms of decompose, but I don't quite understand it, and more generally how we can perform this unification step of decompose on a general $f$ without somehow backtracking on failure.


texts: Number of n-node binary trees containing an m-node binary subtree

texts:
In a paper I see the following lemma about unlabeled binary trees:

  If $s_1$ and $s_2$ are both m-node binary trees, then the number of n-node binary trees containing $s_1$ as a subtree is the same as the number of n-node binary trees containing $s_2$.

It goes on to use this to show that if you want to compute the number of n-node binary trees that have m-node as a subtree, it doesn't matter what m-node tree you use.

I feel like I'm either misinterpreting this or missing something obvious. But isn't the following setup a contradiction to this lemma:

Nodes 2a and 6a produce the same tree, so tree 1 is only the subtree of 5 4-node trees while tree 2 is a subtree of 6 4-node trees.


texts: Determine whether a sorted array contain at least 4 distinct elements in O(log n) time

texts:
On one of my previous courseworks, I was faced with the following problem, which I think is unrealistic when using a direct / straightforward approach that usually algorithms have by leveraging certain data structures like dictionaries, etc.

Design an O(log n) algorithm whose input is a sorted list A. The algorithm
should return true if A contains at least 4 distinct elements. Otherwise
the algorithm should return false.

My lecturer came up with the following solution:
def ThreeDiff(A):
  if A[0]==A[len(A)-1]:
    return -1

  minind=0
  maxind=len(A)-1

  while maxind-mind>1:
    midind=int((minind+maxind)/2)
    if A[midind]>A[minind] and A[midind]<A[maxind]:
      return midind
    if A[midind]==A[minind]:
      minind=midind
    else:
     maxind=midind
  return -1

def FourDiff(A):
  midind=ThreeDiff(A)
  if midind==-1:
    return false
  return ThreeDiff(A[0:midind+1])!=- 1 or ThreeDiff(A[midind:len(A)]) != -1

Is there a cleaner or better way to solve this problem?


texts: Can Barrington's Theorem be used to speed up computation of some function ? How?

texts:
How can Barrington's Theorem be used to obtain faster programs ? Assuming, I want to evaluate function greater than gt between two bits x and y, defined as $gt(x,y)=xy+x$, equal with $1$ when $x$ is greater than $y$. Now, let's say I have two numbers on $N$ bits and the problem expands.

Can Barrington theorem be applied to speed up computation ? Or not necessary speed the computation, but reduce the number of multiplications of the boolean circuit implementing the greater than function for two numbers on $N$ bits ?


texts:
Assume that I need to determine the reliability of a service. The service includes component a (software reliability=0.95) and component b (software reliability=0.98). I have 2 computers: Computer A (hardware reliability=0.99) and Computer B (hardware reliability=0.99).
I have two following cases:

Case 1: Deploy both a and b on computer A. For this case, the service
reliability is around 0.923.
Case 2: Deploy a on computer A, and b on computer B. For this case, the service reliability is around 0.912

I really wonder why the service reliability in case 2 is lower than in case 1. The thing is A and B have the same hardware reliability. Can someone clarify that?


texts: Johnson's vs Floyd-Warshall for dense graphs

texts:
I often read that Floyd-Warshall is a good fit for dense graphs and Johnson's for sparse ones.  While it's easy to see why Johnson outperforms Floyd-Warshall on sparse graphs, I'm noticing that Johnson's with Fibonacci Heaps does no worse than Floyd-Warshall in terms of asymptotic runtime.

More specifically, from what I see, for dense graphs we have:

Floyd-Warshall runs in $O(V^3)$
Johnson's algorithm with a Fibonacci Heap runs in $O(VE + V^2\text{lg}V$) which for a dense graph would also be $O(V^3)$

If so, what are the exact benefits of Floyd-Warshall over Johnson's? Is it runtime differences in practice? Space complexity? Something else?

To put it more bluntly (at the risk of oversimplifying this matter) could one say e.g. "Always use Johnson's over Floyd-Warshall"?.


texts: What are the general applications of Computer Science in the field of Psychology?

texts:
I am keenly interested to do a project in Computer Science that can aid to address the problems in the field of Psychology. Now I want to know what are the most general and research-oriented issues or problems areas in Psychology that can be solved through computation or at least aid to be solved via Computer Science.
Looking for authentic answers. Thank you


texts: What is the purpose of k in the transitive closure method?

texts: When converting a DFA to a regular expression using the transitive closure method, what is the significance of state $k$ and what values $k$ takes? If $k$ represents the intermediate states then what are the values for $k$? That is while applying the method, for which value of $k$ should we stop finding the regular expressions?


texts: What is the best way to merge cycles to minimise total weight?

texts:
Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $c=(v_1, v_2, \ldots, v_n)$, where $v_n=v_1$. Each edge $e=(v_i,v_j)$ has a positive weight $w(e)$. The weight of a cycle $w(c)$ is the sum of its edge weights: $w(c) = w(v_1,v_2)+\ldots+w(v_{n-1},v_n)$. The total weight of $S$ is the sum of all its cycle weights.

Naively I want to merge all the cycles in $S$ into a single cycle with the smallest total weight. I also want to somehow preserve most of the edges of the original cycles. I am not looking for an optimal solution, just an efficient heuristic.

I can merge two cycles by removing an edge from each one and connecting them up with new edges. For example, suppose I have two cycles $c=(v_1, v_2, \ldots, v_n)$ and $c'=(v'_1, v'_2, \ldots, v'_k)$. I can remove edges $(v_a,v_{a+1}), (v'_b,v'_{b+1})$ and add edges $(v_a,v'_b), (v_{a+1},v'_{b+1})$ to form a single cycle $(v_1, \ldots, v_a, v'_b, \ldots, v'_{b+1}, v_{a+1}, \ldots, v_1)$. This move is somewhat similar to 2opt and there are O(nk) such moves possible. I can continue merging cycles in this fashion until I reach a single cycle. Essentially I am building a minimal spanning tree that spans cycles.

Although the above procedure works in giving me a single cycle, it rarely gives me a cycle with a small weight. I can enhance this procedure by merging 3 cycles at once in a move similar to 3opt, but then I have to perform significantly more computations.

So here are my questions:

Is this a well known problem?
Can I improve the efficiency of this approach?
Is there an efficient heuristic that produces a cycle of small weight?

Attached are some examples. In the left figure a 3opt move is optimal, while in the right figure a sequence of 2opt moves is best.

Here is a numeric example that I constructed. Using the optimal merging method we get a weight of 43, while the greedy algorithm gives us a worse solution of weight 50. Even if we join the bottom cycle by removing the new edge we added (weight 10) we would still get a worse solution (I didn't draw it for clarity).


texts: Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$

texts: How can I produce an automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only accepts strings where the number of $a$'s and $b$'s are multiples of $2$ and there is one occurrence of $b$ between $a$ and $c$? Any help is greatly appreciated, thanks.


texts: SICP: applicative or normal order evaluation

texts:
I'm trying to solve Problem 1.5 from SICP book.
Consider the following definitions:

(define (p) (p))
(define (test x y) (if (= x 0) 0 y))
(test 0 (p))

The question is, what would happen if (test 0 (p)) is interpreted in applicative vs normal order.

(Applicative: evaluate all the arguments and then apply the operand. Normal: fully expand the expression and then evaluate it.)

I intuitively feel that the answer must be that one of the two gets into an infinite loop, while the other stops due to the fact that if is a special form, which does not evaluate the else-branch if the then-branch is already evaluated.

Question is: will this happen? And which one will not get into an infinite loop and why?

My reasoning is the following:

Applicative: tries to evaluate all the arguments first.

(test 0 (p)) evaluates 0 to 0 and (p) to (p).

Thus the next step:

(test 0 (p))  --> same as above, we are in an endless loop.

Normal: fully expands the expression

(test 0 (p))  --> expanded to:

(if (= 0 0) 0 (p))  --> expanded to:

(if (= 0 0) 0 (p))  --> ... (it got in an infinite loop too)

OR: does it stop at this point, because if is a special form? (Even though this is true, if we stop now, we did not really expand everything first, as we were supposed...)


texts:
I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:

  If a $\Theta(\log_2{n})$ algorithm requires 20 seconds to execute on an input of one million elements, approximately how long should it take on an input of two million elements?

The answer it gives is 21 seconds and I'm stuck on how they come up with that number.


texts: Asymptotic complexity of $-\log(c^{1/n} - 1)$

texts:
What is the asymptotic complexity of
$$f(n) = -\log(c^{1/n} - 1)$$
for some constant $c > 1$? I conjectured $O(\log n)$ and checking WolframAlpha does give $$\lim_{n\to\infty}\frac{f(n)}{\log(n)} = 1,$$ but I haven't found a proof yet.


texts: Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?


texts: How can you find all unbalanced parens in a string in linear time with constant memory?

texts:
I was given the following problem during an interview:

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

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


texts: Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?

texts:
The worst case time complexity of a given algorithm is $\theta(n^3logn)$.
Is it possible that the worst time complexity is $\Omega(n^2)$?
Is it possible that the worst time complexity is $O(n^4)$?
The average time complexity is $O(n^4)$?
IMO it is possible as long as you control the constant $c$, but then what's the point of mentioning any other bound than the tight bounds?


texts: Is there a high-level framework from which all known search and optimization algorithms can be derived?

texts:
The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations.

I'm mainly talking about heuristic algorithms such as evolutionary search, particle swarm, simulated annealing, and their many, many variants.

Is there some high level grammar that can describe all these algorithms and, conceivably, any possible future search algorithm such that it would be very hard to create an optimization method that can't be derived from this framework?


texts: Undecidability of TMs recognizing a decidable language

texts:
The language $L = \{ \text{M} \mid \text{M  is a TM and the set of words w such that M halts on w is decidable} \}$ is given.

I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it should be similar to prove to the Rice Theorem, using a reduction. However, this hint isn't very helpful to me.


texts:
There are x digits and y boxes where y is between 1 and x inclusive. I have to print all the possible digits in boxes (combinations) in any order.

For examples, if x = 5 and y = 2 we can have the following 4 combinations:

1234 5
123 45
12 345
1 2345

Similarly if x = 5 and y = 3

123 4 5
12 34 5
12 3 45
1 234 5
1 23 45
1 2 345

if x = 5 and y = 5 then there is only 1 combination

1 2 3 4 5

Both x and y are variable and I can't figure out even a brute force way of doing this. I have tried using three nested for loops but have no luck.


texts: dynamic programming exercise on cutting strings

texts:
I have been working on the following problem from this book.

  A certain string-processing language offers a primitive operation which splits a string into two
  pieces. Since this operation involves copying the original string, it takes n units of time for a
  string of length n, regardless of the location of the cut. Suppose, now, that you want to break a
  string into many pieces. The order in which the breaks are made can affect the total running
  time. For example, if you want to cut a 20-character string at positions $3$ and $10$, then making
  the first cut at position $3$ incurs a total cost of $20 + 17 = 37$, while doing position 10 first has a
  better cost of $20 + 10 = 30$.

I need a dynamic programming algorithm that given $m$ cuts, finds the minimum cost of cutting a string into $m +1$ pieces.


texts: Is every problem with an output's size that grows polynomialy np?

texts:
I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$?
My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic Turing machine. (Wikipedia)
Moreover, consider a non-deterministic algorithm, that takes in input an integer $n$ and an integer $k$. This algorithm randomly outputs  an $n^k$  bits combination. For example $(2,2)$ could output $0101$
Intuitively, this algorithm as a polynomial complexity.
A problem with an output's size that grows polynomialy could be solved by this algorithm.
Therefore, a problem with an output's size that grows polynomialy could be solved by a non-deterministic algorithm in polynomial time.
Therefore, every problem with an output's size that grows polynomialy is $\textsf{NP}$.
I do not know, if my thinking is correct.


texts: Characterizing cycles in a directed graph with optional edges

texts:
Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of these graphs may be acyclic while others contain cycles.

For example, consider the graph with vertices $\{1, 2, 3, 4\}$ and edges $\{1 \rightarrow 2,\ 2 \xrightarrow{?} 3,\ 3 \rightarrow 1,\ 2 \xrightarrow{?} 4,\ 4 \xrightarrow{?} 1\}$ where the optional edges are the ones marked with a question mark.

This defines a family of eight different graphs with the same vertices but different sets of edges. If we denote the presence or absence of an edge between vertices $u$ and $v$ as $E(u \rightarrow v)$, then the following Boolean expression describes whether a particular graph in this family in cyclic: $E(2 \rightarrow 3) \vee [E(2 \rightarrow 4) \wedge E(4 \rightarrow 1)]$

Given a particular graph containing some optional edges, I'd like to be able to describe compactly the combinations of optional edges that must be present for the graph to be cyclic without having to specify the entire original graph. In particular, I'd like to know if there is a description whose length is polynomial in the number of optional edges rather than the total number of edges.

More formally: Is there a pair of (ideally efficient) algorithms $P$ and $Q$ such that $P$ takes in a description of a directed graph with $N$ optional edges and produces an "encoded" string whose length is polynomial in $N$, and Q can read in that encoded string and a subset of the $N$ optional edges and determine whether, with those edges present (and the other optional edges removed), the original graph would be cyclic?


texts: Is Terra the only system programming language able to compile code at runtime?

texts:
I stumbled across Terra last year, and the most similar language I can think of is Julia. Terra is inspired by and uses Lua for templating/metaprogramming instead of being derived from e.g. the Lisp or ML families, but like many JITted language implementations it blurs the line between compile-time and run-time.
Are there any other low-level (no VM, small runtime, etc.) programming languages I'm missing that can compile and run code at runtime (besides assembly)? Maybe Forth-likes, or Extempore's xtlang? Terra calls this (multi-)staged programming.


texts: Generating context-free grammar from language

texts:
I need to give a context-free grammar for each of the examples:

$L_1=\{a^hb^ka^mb^n  :  h+k=m+n\}$

$L_2=\{a^ib^ja^k  :  (i=j \,\,\,\, and \,\,\,\, k≥0) \,\,\,\, or \,\,\,\, (i\ge0 \,\,\,\, and \,\,\,\, j>k)\}$

I've done many simple examples and have improved on my skills to generate CFGs from grammars. I normally start off by solving for the simplest case, then building up from there. However, I'm confused as to where I can start to find the solutions to these problems.

Edit: This post has been marked as a duplicate and linking to here. However, my question is not about how to prove that a language is context free. It's about generating a context-free grammar from a given language.


texts: Counting arrays with Euclidean distance at most 2 from a given binary array

texts:
I have a binary array like this:

$$A = [0,1,0,0,1,0]\,.$$

I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array.

So, how many arrays of length 6 exist where

$$\sqrt{\Sigma(A_{_i} - B_{_i})^2}\leq 2\,?$$

I'm trying to find or create a formula that takes an array like above and outputs a count of how many possible binary arrays exist that fit the conditions of the above formula.

I've looked online for a formula without success.


texts: Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

texts:
For an undirected graph $G$, let us denote $\gamma(G)$ the chromatic number of $G$. Let us define for positive integer $n$, the language
$$
L_n = \{\langle G\rangle : \gamma(G) = n\}.
$$
This is the language of undirected graphs with chromatic number $n$.
I think $L_n \in \mathrm{P}^{\mathrm{NP}}$, for any $n$.

My argument is the following. We can look at the language,
$$
\mathrm{CHROMNUM} = \{\langle G, k\rangle : \gamma(G) \leq k\}.
$$
It is clear that $\mathrm{CHROMNUM} \in \mathrm{NP}$, since we can verify an instance just by displaying an at most $k$-coloring of $G$.

Thus, consider oracle Turing machine $M^{\mathrm{CHROMNUM}}_n$, which on input $G$, simply checks that $\langle G, n \rangle \in
\mathrm{CHROMNUM}$ and that $\langle G, k \rangle \not \in \mathrm{CHROMNUM}$ for all $k \leq n$.

I've just read about $\mathrm{P}^{\mathrm{NP}}$, so I wanted to be sure that this kind of argument is correct.


texts:
A computer has a cache memory and a main memory with the following features:

-   Memory cache access time: 4 ns
-   Main memory access time: 80 ns
-   The time needed to load a line in cache is 120 ns.
-   Write-through policy.
If the hit ratio in this computer is 95 % and the 90% of the memory accesses are read operations, what is the average access time?

It seems a bit weird to me since I have read through this site calculate the effective (average) access time (E AT) of this system but I still do not know how to do it.
I would appreciate any help. Thanks!


texts: Is properly quantified 3SAT complete for PSPACE and all PH levels?

texts:
I know 3SAT is NP-complete and QSAT is PSPACE-complete. However, is it true that

$$\exists X_1 \forall X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

is complete for $\Sigma_k$, the existential side of level $k$ of the polynomial hierarchy if each clause in $\varphi$ has at most 3 literals (or some other constant size bound)? Similarly for

$$\forall X_1 \exists X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

in relation to $\Pi_k$, and the quantified version with unbounded alternation in relation to PSPACE, once again with each clause of $\varphi$ having at most 3 literals (or some other constant number)?


texts: I would like to learn more about Amdahl's Law and other similar topics.  In what branch of computer science would one place Amdahl's law?  Could someone point me to a textbook or further reading (aside from Wikipedia or other sites that are found on the first page of a Google search) that discusses it?


texts: Machines for context-free languages which gain no extra power from nondeterminism

texts:
When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.

For the first and last levels1 (regular languages and recursively enumerable languages), it makes no difference to the power of the model whether we consider deterministic or nondeterministic machines, i.e. DFAs are equivalent to NFAs, and DTMs are equivalent to NTMs2.

However for PDAs and LBAs, the situation is different. Deterministic PDAs recognise a strictly smaller set of languages than nondeterministic PDAs. It is also a significant open question whether deterministic LBAs are as powerful as nondeterministic LBAs or not [1].

This prompts my question:

  Is there a machine model that characterises the context-free languages, but for which non-determinism adds no extra power? (If not, is there some property of CFLs which suggests a reason for this?)

It seems unlikely (to me) that it would be provable that context-free languages somehow need nondeterminism, but there doesn't seem to be a (known) machine model for which deterministic machines are sufficient.

The extension question is the same, but for context-sensitive languages.

References

S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.

Footnotes

Side question for the comments, is there a reason for the levels (ordered by set inclusion) of the Chomsky hierarchy to be number 3 to 0, instead of 0 to 3?
To be clear, I'm talking about the languages that can be recognised only. Obviously questions of complexity are radically affected by such a change.


texts: Lower bound on size of proof that a list of integers is sorted

texts:
Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order.

Such a proof might look (informally) like: "2 < 3, and 3 < 5, and ... and 71 < 79, so the list is sorted."

It would seem such a proof must have length $\Omega(n)$ where $n$ is the length of the list of integers, as you could use the same kind of argument that is used to show that comparison sorting is $\Omega(n \log n)$; roughly, if the proof was any shorter than $n$, it would have missed one of the integers on the list.

Is this the case, or have I missed something?  Is there a clever way to construct an asymptotically shorter proof?

Edit: As Gilles and Yuval Filmas point out below, a specific answer can only be given if we have some constraints on the language in which the formal proof is written.  For the purposes of this question, suppose that no matter what particular proof language is used, the proof must be written such that it can be verified in time at most polynomial in the length of the proof.  This excludes proofs of the form "for all elements of the list, ..."  (I realize this constraint may make the question more difficult than if a particular proof language was chosen, but it really is closest to what I was thinking when I asked the question.)


texts: Linear programing, objective function. variable depending on the sign of another variable

texts:
I have the variable Si. How to express a variable Di in LP that satisfies:

Di=100*Si if Si>=0
Di=-200*Si if Si<0

The objective function would be Min{Sum(Di)}


texts: Are Algebraic types just the combination of case classes and pattern matching?

texts:
On this page describing the precursor to the Scala language - the pizza language - they refer to it having both case classes and pattern matching - and then imply that these taken together provide algebraic types.

Is this the case? To provide algebraic types - do you combine case classes and pattern matching?


texts: Understanding of SPACE in non deterministic Turing Machines

texts:
Let's consider the following situation.
We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$.
I am trying to solve some problem and I am going to:

Generate every word using non-deterministic Turing Machine. And, for every generated word make a computation $C$. that uses only constant space and linear time. So, it seems that we have to remember (for a moment) generated word. I mean the situation that we have to generate word $w$ and then make a computation $C$ on $w$.

The scheme of Turing machine looks like:

The question is: Is my Turing machine NPSPACE? I have a problem with thinking about space complexity when it comes to nondterministic TM.


texts: What does the notation co- mean when prefixing co-NP, co-RE (recursively enumerable), or co-CE (computably enumerable) ?


texts: Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only one edge for 2 vertices. Correct?


texts: sort array using oracle computes number of elements in one partition that are smaller than given element in O(1)

texts:
excuse me for the long title. My goal is to find an algorithm to sort an array of n elements, with an oracle, which must be used O(logn) times.
Given a partition of our array (resulting in two subsets, A and B), this oracle can tell us how many elements in B are smaller than a given element in A in O(1).
A naive approach would be partitioning the array to an element and a subarray of n-1 elements, and using the oracle to determine the position of our single element. Doing this n times would sort the array in O(n).
However I cannot think of any algorithm that would perform better than O(n), and I am beginning to question whether or not this is possible?
thanks in advance!


texts: Is it decidable whether a Turing Machine will visit every non-end state from input x?

texts:
L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once}

I believe this problem is undecidable.

My proof would consist of me reducing L to a Halting Problem; however, the structure of these proofs seem incosistent and inconclusive. I would appreciate if I could have some constructive feedback.

My understanding of the proof:

Create R which decides L
Construct algorithm S, which decides Atm (which we reduce to L)
Contradiction because Atm is undecidable

This is the skeleton to most Turing Machine dicidibility related  proofs I have read on the internet.


texts: Boyce-Codd Normal Form vs. 3rd Normal Form

texts: Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?


texts: Extremal related question regarding Intersection of neighbourhood of vertices

texts:
What is the maximum number of edges that a simple directed graph on $n$ vertices can have, if the graph has the following restriction.

Size of Intersection of Neighbourhood of any pair of vertices is at most $k$?

Neighbourhood is defined as follows.
If a vertex $v$ has directed edges towards exactly three vertices $a$, $b$ and $c$, then $\{a,b,c\}$ constitutes the neighbourhood of $v$.

My hunch is $O(kn)$ but I am not able to prove it?
Its easy to create such a graph which has $O(kn)$ edges, and has maximum intersection of neighbourhood to be at most k.

Simply create an empty graph on $n$ vertices say $v_1,v_2\ldots v_n$. Then for each $v_i$ give their neighbourhood to be $v_{i+1}$ to $v_{i+k}$.
This gives a graph $O(kn)$ edges.

Can you show that this is the best which can be done?


texts: Using Generalized Rice's Theorem to Prove Decidability

texts:
I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to determine if L(M) is decidable, semi-decidable (computably enumerable) or undecidable.

Using Rice's Theorem, I believe I can prove that L(M) is not decidable:

  P is the property of a language where the language has infinitely many strings that start with one symbol and finitely many strings that start with another symbol. P is non-trivial and is a property of languages of TMs. Therefore, according to Rice's Theorem, M = {⟨M⟩∣L(M) has has infinitely many strings that start with 1 and finitely many strings that start with 2 and Σ = {1,2}} is undecidable.

But I'm struggling to prove whether it's semi-decidable or completely undecidable. This post mentions using an Generalized Rice's Theorem to prove that a language is recursively enumerable (aka semi-decidable) but I'm having trouble understanding their approach.

Can anyone shed some light on this approach and/or if I'm heading down the right path? Many thanks in advance.


texts: Are there deterministic and/or non-interactive zero-knowledge proofs?

texts:
The Wikipedia page on zero-knowledge proof says

  Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.

Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?


texts: Problems solvable in time $f(n)$ but not in time $o(f(n))$

texts: Suppose I have some (increasing, nice asymptotics) function $f(n)$. Does there exist a complexity theoretic problem (e.g. PATH, 3-SAT, GO etc.) that can be solved in time $\Omega(f(n))$ on a deterministic Turing machine. In other words is there a problem proven to be an element of $\mathsf{DTIME}(f(n))$, but not $\mathsf{DTIME}(g(n))$ for any function $g$ such that $\frac{f(n)}{g(n)} \to \infty$ as $n \to \infty$?


texts: Number of referee nodes required in distributed leader election algorithm

texts: I know the reason as to why $O(\sqrt{n\log n})$ referee nodes are required. What I don't understand is how to arrive at that value, when I have $7\log n$ candidate nodes. Please forgive me if this is common knowledge, I am new to the field.


texts:
So I have this code:

  done <- false                                     [1]
  n <- 0                                            [1]
  while (n < a) and (done = false)                  [(n+1)(1+1+1)]
    done <- true                                    [n]
    for m <- (a- 1) downto n                        [n(1+1+1+1)]
       if list[m] < list[m - 1] then                [n]
         tmp <- list[m]                             [n]
         list[m] <- list[m-1]                       [n]
         list[m - 1] <- tmp                         [n]
         done <- false                              [n]
       n <- n + 1                                   [1]
  return list                                       [1]

Am I doing this right? My conclusions are that the inne for-loop runs (n^2 + n) / 2 times and the outher while-loop runs n+1 times. I don't know how to properly argue for that the bubble sort has the complexity O(n^2)


texts: Is there any real difference between a compiler and an assembler?

texts: Is there any difference between the two?  As per Ullman's book, compilers  convert one language to another (usually low level) language, and so does an assembler. How are the two different?


texts: Why is f(n) of class O(g(n)) in this graph?

texts:
There is a lot of explanation about big O, but I'm really confused about this part.

Acoording to the definition of Big-O, in this function

$$f (n) \le c  g(n), \quad \text{for } n \ge n_0$$
$f (n)$ is   $O(g(n))$.

But a description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

So for example  34 is a upper bound for the set $\{ 5, 10, 34 \}$.

So in this graph, how is $f(n)$ in $O(g(n))$ because if I get the upper bound of $g(n)$ function its value would be different than what is mentioned here for $n\ge n_0$.


texts: Policy dependent on initial state distribution in finite horizon MDPs

texts:
Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition probabilities, $\mu$ the initial state distribution, and $\lambda$ is the discount factor.
Let the decision horizon be finite. The expected discounted return under a given policy $\pi = (\pi_1,\ldots,\pi_{T-1})$, where each $\pi_t:S\to A$, is defined as
\begin{align*}
F(\pi,\mu) = E_{\pi,\mu}\big[\sum_{t=1}^{T-1}\lambda^tR(s_t,a_t,s_{t+1}) + \lambda^TR(s_{T-1},s_T)\mid s_1\sim \mu\big]
\end{align*}
where $a_t = \pi_t(s_t)$ and the expectation is taken with respect to the probability distribution on the states induced by the initial state distribution $\mu$ and the policy $\pi$. An optimal policy is defined as $\pi^*\in\arg \max_\pi F(\pi,\mu)$.
It seems to me that the math says that since we are only maximizing over $\pi$, there is still a residual dependence of the optimal policy on $\mu$, i.e., mathematically it should be written: $\pi_{\mu}^*\in\arg \max_\pi F(\pi,\mu)$.
Question: Are optimal policies in MDPs dependent upon the initial state distribution? If not, what conditions allow us to rule out this dependence?


texts: Top-down typing strategy - is there a name for this?

texts:
In most statically typed languages, each expression has an intrinsic type. E.g. in Java, 3 is an int, 3.0 is a double, 3+3.0 is also a double. Types do not depend on the context of the expression.

However, in the CSS type system described in the spec, some expressions have a type depending on the context. For example, the red token can be a <color>, a <custom-ident>, or an <attr-name>, depending on the context in which it is used.

I want to build a type system for a CSS-based programming langauge. In this type system, I want to use a typing strategy that does not go from the bottom up (starting from the leaves in the AST), but top down (starting from the root of the AST).

For example, when the compiler needs to derive that the linear(red, yellow) expression inhabits the <bg-image> type, it would do the following derivation:

we want to derive that
  linear(red, yellow) :: <bg-image>
<bg-image> is defined as <url> | linear(<color>, <color>), so
  linear(red, yellow) :: <url> | linear(<color>, <color>)
let us try the second branch
  linear(red, yellow) :: linear(<color>, <color>)
let us check sub-expressions
  red :: <color>
  yellow :: <color>
everything fine, OK

Can you point me to scholarly articles where this kind of typing strategy is discussed?

P.s. I don't know of other languages where a type of the expression depends on the context, except for Perl. In Perl, ("a","b") can be interpreted as either a list or an integer (its length), depending on the context:

print ("a","b") # => ab
print 0+("a","b") # => 2


texts: Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

texts: Mahaney's theorem states that the existence of $\mathsf{NP}$-complete sparse language would lead to $\mathsf{P = NP}$. Is there any result result regarding the same for the complexity class $\mathsf{PSPACE}$, like "if there is a $\mathsf{PSPACE}$-complete sparse language, $\mathsf{PP = PSPACE}$" or the same for any other complexity class within $\mathsf{PSPACE}$?


texts: Basic questions about network flow calculations

texts:
Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to each edge $e$ of the graph a capacity $c_e$ is assigned (which can be defined as a function vertex properties of the endpoints of an edge), and in analogy to flow of water through pipes for example, a net flow is assumed to take place from the source towards the sink. That is the net flow out of the source, is equal to the net flow entering the sink:
$$
\sum_{u\in O(s)} f(s,u)-\sum_{u\in I(s)}f(u,s)=\sum_{u\in I(t)} f(u,t)-\sum_{u\in O(t)}f(t,u)
$$
where $O(s)$ denotes the set of vertices, that $s$ is incident on, and $I(s)$ denotes the set of vertices that are incident to $s.$
Now often, one is interested in computing the maximum possible flow in the graph, which leads to using Menger's theorem, which relates maximum number of distinct paths (between $s$ and $t$) to the minimal cut-set, or in a general setting, it relates the maximum flow to minimum cut capacity (summing the capacities of the minimum cut, that disconnects source from sink).

There are many algorithms that allow computing the maximum flow rather efficiently, for a given digraph. But my questions are (sadly) rather basic, but are solely related to computing maximum flow:

Assuming the capacities of all the edges are known, why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities? or am I wrong?
How are then the individual flows $f$, through each edge $e$ (where $f_e\le c_e $), calculated when we are estimating the maximum flow? Do we set all flows equal to respective capacities (i.e. $f_e=c_e$)?  Or is the individual flow, a function of the minimum capacity ($\text{min}(c_e)$ for all edges $e$) of the graph?
Of course it is possible that I'm completely wrong here, in which case, the question becomes: how is the flow decided for each edge (knowing at least that $0\le f_e \le c_e$ for all edges), when we are interested in estimating the maximum flow through the graph?


texts: Total number of calls during insertion into binary tree

texts:
The problem:

Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree level-by-level. Leave your answer in the form of a sum.

code for INSERT function:

procedure INSERT(x: elementtype; var A: SET);
begin
    if A = nil then begin
       A -> .element := x;
       A ->.leftchild := nil;
       A ->.rightchild := nil;
    end;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then
        INSERT(x, A ->.rightchild);
    end;
end;

The main confusion for me here is with leaving my answer in the form of a sum. I'm not all that great at sums (haven't taken Calc 2 yet), so I don't really know how to set them up or extract information from them all that well. Any help here would be greatly appreciated.

For clarity: This is a review problem where the answer is:

Let $2^k \leq n \leq 2^{k+1}$. Then $k = \log n$ and the number of calls equals,

$$
\sum_{i = 0}^{k - 1} (i + 1)2^i + (k + 1)(n - 2^k + 1)
$$

I'd like to know the process behind getting this answer. Thank you.


texts: Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

texts:
Here is my approach

First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

Let's suppose the longest subsequence has $L$ elements. Then if $L < N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.

Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.

I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?


texts: programs compatible with different processors

texts:
Ok, I've been told for years that during the old days, a program written on a certain machine would run only on that machine but now, programs run on multiple types of computers.

What does this really mean? I mean, does it mean that programs were written for certain instruction sets of the processor and would not run in different instruction sets? If so how did they overcome this problem?

Is it due to the standard x86, AMD64 or ARM architectures that most programs are written for these types of processors and they are abundant in the world?

Please enlighten this lost kid.


texts: Can you pipeline a pure Von Neumann architecture based CPU or do you need seperate data and instruction caches for this? If you include seperate instruction and data caches (then it isn't a von neumann CPU anymore, it's a modified Harvard), how do you unify the data of these caches so that they get stored in a single memory?


texts: If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the mapping function to map the index of Lower triangular matrix Aij in 1D.


texts: Can a perfect matching always be found by a picking sequence?

texts:
There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference graph (encoding the "like" relation).

In some cases, this may be done using a picking sequence: order the people in a queue and let each person in turn pick a single item he likes. For example, suppose that:

$A$ likes $\{1,2\}$
$B$ likes $\{2,3\}$
$C$ likes $\{3\}$

Then, $\langle C,B,A\rangle$ is a good picking sequence, since $C$ necessarily picks $3$, then $B$ picks $2$, then $A$ picks $1$ and we get a perfect matching. On the other hand, $\langle C,A,B\rangle$ is not a good picking sequence, since after $C$ picks $3$, it is possible that $A$ will pick $2$, and then $B$ will remain without an item.

So, my question is: If a perfect matching exists, can it always be found by a picking sequence?


texts:
Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot exist a program which can itself examine any arbitrary program and tell the user whether the program being examined will halt.
However, the thought experiment involves programs that were, frankly, designed to act in a way no sane programmer would ever want. Programs that are intentionally designed to halt without producing any useful output, programs that are designed to run indefinitely without halting. As addressed in the answers to the question Is there a subset of programs that avoid the halting problem, the halting problem doesn't apply to all programs. In the extreme case, the following programs would be trivial to analyze:
// Program 1:

while true {}

// Program 2:

print("I really can't tell with this one")

Rather, the halting problem merely indicates that there will always be some programs that can't be analyzed for halting. Those that can be analyzed fall into a certain class of programs that is reasonably well-researched and well-understood, and seems to align quite neatly with the class of useful programs. As for the original proof, while the logic holds, the programs used therein are poor indicators of code a human would actually write, and beg a certain question:
Is it possible that the halting problem only applies to useless programs?


texts: I know that the height of a red-black tree is at most 2 lg(n + 1). However, what is the mathematical proof of this? I searched various sites, however I couldn't find a good proof. I already know the properties of a red-black tree.


texts:
I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code.

The result must also be indistinguishable from random. It should not be possible to detect the presence of error correction from the result.

Is it possible? And if so, how?

PS: Related: https://crypto.stackexchange.com/questions/80890/error-correcting-codes-that-are-indistinguishable-from-random


texts:
Are the undecidable languages closed under complement?
How can the answer be proved?


texts: Using master theorem to solve recurrence with log

texts:
I'm not sure how to solve apply the master theorem in order to solve this recurrence:

  $$  T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$

The master theorem I have been shown is normally used to solve recurrences of the slightly different form
$$  T(n) = aT(n/b) +O(n^d),\text{ where }T(1) = 1.$$


texts: Can there be a context free language that is not recognizable by a PEG?

texts:
This is related to this question. Essentially, I want to know whether my reasoning is correct.

We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: Valient 1975, backward: Lee et al. 2002), and the latter has a lower bound of O(n^2) for arbitrary matrices.
If so, then there should exist a context free language $L$ such that any context
free grammar that can represent it would take $O(n^2)$ for matching a string.
This is because say there existed a grammar $G_n$ that allowed matches
faster than $O(n^2)$ for any given CFL, then that grammar would allow faster multiplication for
the corresponding Boolean matrices. Since Valient et al. and Lee et al.
together shows that multiplication of BMs are same as parsing with a CFG, any
BM can then be multiplied faster than $O(n^2)$, which is lower than the lower
bound by theory.

So there should exist a context free language $L$ such that it takes at least O(n^2) time for checking membership in $L$.

PEGs are known to require only linear time (Birman and Ullman 1970), (Loff et al. 2019).

If there exist a PEG for $L$, it would be a recognizer that checks the membership in linear time, and hence, can solve matrix multiplication in linear time.

Hence, there does not exist a PEG for $L$.
Where am I going wrong?
Valient 1975

context-free recognition, for $n$ character input strings, can be
carried out at  least as fast as multiplication for $n \times n$ Boolean
matrices

Lee et al. 2002

Any CFG parser with time complexity $O(gn^{3-\epsilon})$, where $g$ isthe size of the
grammar and $n$ is the length of the input string, can be efficiently
converted into an algorithm to multiply $m\times m$ Boolean matrices in
time $O(m^{3-\epsilon/3})$.

Loff et al. 2019

In fact, the only method we know to prove that a language has no PEG is
by using the time-hierarchy theorem of complexity theory:
using diagonalisation one may construct some language $L_2$ which is
decidable,say, in time $n^2$ (by a random-access machine), but not in
linear time, and because PEGs can be recognised in linear time using
the tabular parsing algorithm of Birman and Ullman [2] (or packrat
parsing [32,33]), there will be no parsing expression grammar for $L_2$.


texts: Efficiently inserting into list keeping number of inversions minimal

texts:
Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u.

I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u).

Basically I would like to insert objects into a list while keeping it "as sorted as possible" while keeping the order of the first list.

Example:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

As you can see there is no unique optimal solution.

I'd be glad for any sort of ideas or direction to look into.


texts: How to find closed form solution of linear recursion using recursive tree method

texts:
I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this

$$T(n)=\begin{cases}
    1         &\text{if }n=1,\\
    T(n−1)+3n &\text{if }n>1.
\end{cases}$$

However, I am confused about how to plot a tree. I know how to find runtime using tree if problem is divided into half. But here problem is just reduced by one. How does it work?


texts: Grammar/Chomsky-Type for $L = \{ww \mid w \in \{a,b\}^*\}$

texts:
I've been given the following task and have tried a few things, but none seem to result in what is required.

$L = \{ww \mid w \in \{a,b\}^*\}$

What Chomsky-Type is $L$? Provide a grammar fulfilling that Type.

It can't be context-free, since that wouldn't allow us to force that we write each symbol twice at the right place. Also it shouldn't be Type-0, since I suspect that rules that satisfy context-sensitive should be fine(namely all rules fulfill $u \rightarrow p$ with $\mid u\mid \leq \mid p\mid$)

Now I've tried to find a working grammar that fulfills Type-1, but I fail at getting the right order of $a,b$ in the second word.

How could I go about this and am I even right with suspecting to be able to find a Type-1 grammar?


texts: Relation between CLR Grammar and Ambiguity

texts:
I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous?

Is it possible that a grammar which is unambiguous can't be parsed using CLR Parser?


texts: SAT formula and satisfying assignment yield another different satisfying assignment

texts:
Given P=!NP

Is there a polynomial time TM such that for an input of formula and a satisfying assignment will yield a different satisfying assignmentif such exist?


texts: Prove $\varphi(x)$ to be primitive recursive

texts:
Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation}
 f(x_1,\ldots, x_n) =
 \begin{cases}
  g(x_1, \ldots, x_n) \;\;\;\;\;\text{ if } P(x_1, \ldots, x_n)\\
  h(x_1,\ldots,x_n) \;\;\;\;\;\text{ otherwise}
 \end{cases}
\end{equation}
Then $f$ belongs to $\mathcal C$ because $$f(x_1, \ldots, x_n) = g(x_1, \ldots, x_n) \cdot  P(x_1, \ldots, x_n) + g(x_1, \ldots, x_n) \cdot \alpha(P(x_1, \ldots, x_n))$$ where

\begin{equation}
 \alpha(x) =
 \begin{cases}
  1 \;\;\;\;\;\text{ if } x = 0\\
  0 \;\;\;\;\;\text{ if } x \neq 0
 \end{cases}
\end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation}
 \varphi(x) =
 \begin{cases}
  2x \;\;\;\;\;\;\;\;\;\;\;\text{ if } x = t \cdot t \\
  2x+1 \;\;\;\;\;\text{ otherwise}
 \end{cases}
\end{equation}
hence $$\varphi(x) = 2x \cdot  P(x_1, \ldots, x_n) + (2x+1) \cdot \alpha(P(x_1, \ldots, x_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?


texts: Level Ancestor Query long-paths algorithm complexity of sqrt n

texts:
Can someone explain why the complexity of a query for LA is √n when we only decompose the tree into long-paths? How can we show/prove that?
How can we prove that the number of paths can be as high as O(√n) ??? Please help, I've been struggling for a couple of days now.
Stage 1: https://en.wikipedia.org/wiki/Level_ancestor_problem#Naive_methods
Long-path decomposition of a Tree

This is a recursive method that decomposes a given tree into paths. This stages starts off by finding the longest root-to-leaf path in the tree. It then removes this path by breaking its ties from the tree which will break the remaining of the tree into sub-trees and then it recursively processes each sub-tree. Every time a path is decomposed, an array is created in association with the path that contains the elements on the path from the root to the leaf. The base case of this recursion is when the tree is a path in which case its removal leaves an empty graph. Each vertex v has a unique ladder which is the ladder containing it and we call it the "v's ladder". However, after this pre-processing stage, the queries cannot be answered quickly. In fact in order to answer a level ancestor query, the algorithm needs to jump from a path to another until it reaches the root and there could be Θ(√n) of such paths on a leaf-to-root path. This leads us to an algorithm that can pre-process the tree in O(n) time and answers queries in O(√n). In order to reach the optimal query time.
I only need to know how to show that the number of paths can be O(√n) in the worst case.


texts: Prove Undecidability Without Using Rice's Theorem

texts:
Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known.

I tried solving this problem by trying to reduce the "Acceptance Problem" i.e. the problem where we have to check whether a TM $M$ accepts a string $w$ or not.

One idea I had was that we can modify the input $M$ to $M'$ such that $M'$ simply increases the length of the string to become greater than $k$ but that is wrong since by input we strictly mean what was provided and any thing that the TM does cannot be considered as part of the input.

How can I solve this?


texts: Efficiently compute the sum of edge weights product of all possible path in a DAG

texts: I thought of using Depth First Search (DFS) to find all possible paths in O(|V|+|E|). However, computing the product of all the edge weights for a path is O(2^N). Is there any way to compute this more efficiently?


texts: Which optimization algorithm would you recommend for this small multidimensional problem?

texts:
Which algorithm would be suitable for finding or estimating the vector
$$\mathbf{s}_{opt}=\begin{bmatrix}
s_1 & \cdots  & s_N
\end{bmatrix}=\arg\max_{\mathbf{s}}\sum_{n=1}^{N}p_{s_n,n}$$
under the constraint
$$\sum_{n=1}^{N}l_{s_n,n}\leq L_{max}$$
given known values for the integer $N$, the vector
$\mathbf{p}_n=\begin{bmatrix}
p_{1,n}\\
\vdots \\
p_{M_n,n}
\end{bmatrix}$, the vector
$\mathbf{l}_n=\begin{bmatrix}
l_{1,n}\\
\vdots \\
l_{M_n,n}
\end{bmatrix}$, the integer $L_{max}$ and all integers $M_n$?

Here are some restrictions showing that the size of the problem isn't very big:
$$N\:\epsilon\:\mathbb{Z}\:|\:0<N<50$$
$$p\:\epsilon\:\mathbb{R}\:|\:0\leq p_{m,n}\leq 1\:|\:p_{1,n}=1\:|\:p_{M_n,n}=0$$
$$l\:\epsilon\:\mathbb{Z}\:|\:0\leq l_{m,n}\leq 30\:|\:l_{M_n,n}=0$$
$$M_n\:\epsilon\:\mathbb{Z}\:|\:2\leq M_n \leq 20$$

Another circumstance which may be of interest is that the problem will be solved repeatedly. In the first iteration $N=1$ and then for each iteration $N$ will increase as per the sequence $N=1,2,3,...$. The vectors $\mathbf{p}_n$ and $\mathbf{l}_n$, as well as the other inputs, will remain unchanged for all iterations $N=1,2,3,...$, meaning that the same problem just grows slightly step by step.

I am planning to implement this algorithm in JavaScript.

Edit: Real-world case

The mathematical optimization problem above has its origin in a real world (however, stupid) problem. Assume you need to communicate a text of $N$ words, but you have a limited total amount of characters to use, $L_{max}$. For each word $n$ you have found $M_n$ number of alternative representations (such as acronyms and synonyms) each with a probability of the reader to understand approximated to $p_{m,n}$. Now the goal is to choose which representation $s_n$ of each word should be chosen in order to maximize the probability of the receiver to understand the text. This probability can be approximated to the mean value all individual word probabilities.


texts: Turning an unsafe state into a safe state - Banker's Algorithm

texts: I have included an example in my question. I know this state is unsafe as there are no full sequences in the process. However, is there a way to arrive at a safe state from it at all?


texts: Two way communication using asymmetric encryption

texts:
According to image 1, for two way communication, each person needs to generate a pair of keys. However, according to image 2, only one pair of keys is required for two way communication. Thanks to anyone who can settle my confusion.

Source 1

  If a two-way communication is required between all five workers, then they all need to generate their own matching public and private keys. Once this is done, all users then need to swap public keys so that they can send encrypted documents, files or messages between each other. Each worker will then use their own private key to decrypt information being sent to them.

Source 2

  the other key is known as the private key. Data encrypted with the public key can only be decrypted with the private key, and data encrypted with the private key can only be decrypted with the public key. Public key encryption is also known as asymmetric encryption. It is widely used, especially for TLS/SSL, which makes HTTPS possible.


texts:
Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.

Computation 1
\begin{align}
f(x)\leq \exp(-x^2/2)&=\exp(-O(\log m))\\
&=\exp(-O(\log O(n^{c+1/2})))\\
&=\exp(-O(\log n^{c+1/2}))\\
&\leq \exp(-K_1\log n^{c+1/2})))\\
&=n^{-O(1)}
\end{align}
where $K_1>0$ when $n$ is sufficiently large (i.e. there exists $K_1>0$, $n_0$ such that when $n\geq n_0$, $\exp(-O(\log n^{c+1/2}))\leq  \exp(-K_1\log n^{c+1/2})))$. The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions (see accepted answer in this post).

Computation 2
$$
f(x)\frac{m}{n^{1/2}} \leq n^{-O(1)}\frac{m}{n^{1/2}}=\leq n^{-O(1)}\frac{m}{n^{c+1/2-c}}=O(1)??
$$


texts: Is the language of Turing machines that calculate a given function $f$ in RE or coRE?

texts:
For a function $f$, consider the language $$L=\{\langle M\rangle\mid M\text{ computes }f\}\,.$$

Where does the language above is and how do I prove it?
To me it seems that it's not in RE nor coRE but I struggle to prove so.
what I have so far is reduction from HP to $L$ as follows:

$$R(<M>,w) = <M'>$$
$$
Define \ M': \\ M(w) \\
\qquad \qquad \qquad Write \ x \ on \ the \ tape$$

$$ 1. \ Run \ M \ on \ W \\
   2.\ write \ x \ on \ the \ tape $$

But I can't prove that this language is in RE.

So how do I proceed from here ?


texts:
My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:

1- First navigate to the leaf *L* where it belongs.
2- If the *L* is at least half full if you can simply delete it.
3- If it contains d-1 elements then you need to redistribute and merge.

If you see the below image, here I want to delete 19 and 20 from the B+ Tree.

After deleting 19 and 20 from the B+ Tree.

Question:

I am confused why the redistribution and merging is required here at all? If you just simply delete 19 and 20 from the leaf nodes without any distribution it should work right? Why redistribution is performed here? Could anyone explain?

  Is it because the left pointer of 24 is pointing to 20 but no 19.
  Thats why redistribution is required for 20 but not 19.


texts:
I'm studying The Algorithm Design Manual and I was having some difficulty in the proof exercises,
so I asked a question here.
Based on the answer I got in that question(which was not the a complete proof),I came up with a proof.
Prove the correctness of the following sorting algorithm.
    Bubblesort (A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

1.Base case:
    An array of length 1 which is by definition sorted.

2.Inductive hypothesis:
    We'll assume that for all arrays of length (0 <= m) one iteraion of the outer loop with "n" being the length of the array,
    the array gets permutated in such a was  that the last element in the array is the biggest.

3.Inductive step:
    We want to prove that if our assumption is true for lists of length (0 <= m), then it is also true for lists of length (m)

    Let A = a[0], a[1], ..., a[m] (of length m+1)
    After (m-1) iterations of the inner loop based on our assumption, in the list A[0:m-1], a[m-1] is the biggest element.
    At this point,as (j < m),we have one more iteration to perform.
    Before this, j was equal to m-2 and j+1 was equal to m-1. After this loop, j will be equal to m-1 and j+1 will be equal to m.
    If A[m-1] and A[m] satisfy the if statement, that is, A[m-1] > A[m], they will swap.If not, then that would mean that A[m] is
    the biggest element in the list.
    In either case, the last element of the list will be the biggest after one iteration of the outer loop, which was what we were
    trying to prove.  ▮

I'm not really sure of it's correctness,so I would really appreciate if you could review it and tell me whether its correct or not.
Also please note any inadequacies it may have or things I could've done better as I'm quite new to inductive proofs.


texts: How Does Populating Pastry's Routing Table Work?

texts:
I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify.

Disclaimer: I'm not a computer science student. I've taken precisely two computer science courses in my life, and neither dealt with anything remotely complex. I've worked with software for years, so I feel I'm up to the implementation task, if I could just wrap my head around the ideas. So I may just be missing something obvious.

I've read the paper that the authors published [1], and I've made some good progress, but I keep getting hung up on this one particular point in how the routing table works:

The paper claims that

  A node’s routing table, $R$, is organized into $\lceil \log_{2^b} N\rceil$
  rows with $2^b - 1$ entries each. The $2^b - 1$ entries at
  row $n$ of the routing table each refer to a node whose nodeId shares
  the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th
  digit has one of the $2^b - 1$ possible values other than the $n + 1$th
  digit in the present node’s id.

The $b$ stands for an application-specific variable, usually $4$. Let's use $b=4$, for simplicity's sake. So the above is

  A node’s routing table, $R$, is organized into  $\lceil \log_{16} N\rceil$ rows
  with $15$ entries each. The $15$ entries at
  row $n$ of the routing table each refer to a node whose nodeId shares
  the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th
  digit has one of the $2^b - 1$ possible values other than the $n + 1$th
  digit in the present node’s id.

I understand that much. Further, $N$ is the number of servers in the cluster. I get that, too.

My question is, if the row an entry is placed into depends on the shared length of the key, why the seemingly random limit on the number of rows? Each nodeId has 32 digits, when $b=4$ (128 bit nodeIds divided into digits of b bits). So what happens when $N$ gets high enough that $\lceil\log_{16} N\rceil > 32$? I realise it would take 340,282,366,920,938,463,463,374,607,431,768,211,457 (if my math is right) servers to hit this scenario, but it just seems like an odd inclusion, and the correlation is never explained.

Furthermore, what happens if you have a small number of servers? If I have fewer than 16 servers, I only have one row in the table. Further, under no circumstances would every entry in the row have a corresponding server. Should entries be left empty? I realise that I'd be able to find the server in the leaf set no matter what, given that few servers, but the same quandary is raised for the second row--what if I don't have a server that has a nodeId such that I can fill every possible permutation of the nth digit? Finally, if I have, say, four servers, and I have two nodes that share, say, 20 of their 32 digits, by some random fluke... should I populate 20 rows of the table for that node, even though that is far more rows than I could even come close to filling?

Here's what I've come up with, trying to reason my way through this:

Entries are to be set to a null value if there is not a node that matches that prefix precisely.
Empty rows are to be added until enough rows exist to match the shared length of the nodeIds.
If, and only if, there is no matching entry for a desired message ID, fall back on a search of the routing table for a nodeId whose shared length is greater than or equal to the current nodeId's and whose entry is mathematically closer than the current nodeId's to the desired ID.
If no suitable node can be found in #3, assume this is the destination and deliver the message.

Do all four of these assumptions hold up? Is there somewhere else I should be looking for information on this?

Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems by A. Rowstrong and P. Druschel (2001) -- download here


texts: Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other?

texts:
Consider 2 DFAs both determining a language $L$. Both DFAs have the same number of states $n$. Can I then conclude that these two DFAs are isomorphic?

I think the answer is yes, because if I'd make an $MN(L)$ relation with $n$ equivalence classes and map it to a $DFA$, there'd only be one result (at least I believe so). Thus both of the DFAs map to the same $MN(L)$ relation.

Is this reasoning correct?


texts:
I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I'm missing why the following machine doesn't turing recognize the complementary of SAT:
Given a turing machine M that recognizes SAT, the following turing machine recognizes coSAT:

Run M on the input word w.
If M accepts - reject.
If M rejects - accept.

Because coSAT is the language of all unsatisfiable formulas, a formula is unsatisfiable if it doesn't have a satisfiable interpretation, which is exactly the opposite of what M outputs.
What am I missing in here?


texts: Algorithm and Formalism for Most Remote Vertices

texts:
In the graph below, N and M are most remote, and H is also an extremum.

Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the subject? Does an algorithm exist for finding the most remote edges of a graph?

Please note that I am not asking you to invent an algorithm, but I'm asking for information.


texts: Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?

texts: Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this set contain a recursively enumerable non-recursive subset?


texts: What are the flaws in this encryption algorithm?

texts:
Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the second).
$$
I \times A \times A = B
$$

Provide $B$ and $I$ to the recipient. To create encrypted message $E$ from unencrypted message $M$:
$$
E = M \times A \times A
$$

Send $E$ to the recipient. The recipient will solve for $M$ using:
$$
M = E / ( B / I)
$$
My question is:

Will the recipient be able to decode the message?
If an attacker knows $E$ and $I$, can they efficiently solve for $M$?
Is there a simple way to make it nonlinear?

I accepted an answer but am still waiting for #3.


texts: Closure of regular languages under "inverse second half"

texts:
Theorem. Show that if $L$ is regular, then so is
  $$
\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\right\}
$$
  Proof. Let $L$ be a regular language. Because $L$ is regular, there exists a DFA $M$ that accepts it. We construct out of $M$ a $\lambda$NFA $M'$ whose language is $\varphi(L)$.

  We can think of a computation of $M$ as moving a token across the states of $M$. The machine $M'$ will reuse the states of $M$, but will use three tokens: white, red and blue.
  Initially, the blue token is put on $q_0$ (the initial state of $M$), and the white and red tokens are put on a nondeterministically guessed state (both tokens on the same state).

  Describe the transitions of $M'$.
  Describe the acceptance condition of $M'$.

Could someone please help me with that? I research regular expressions, DFAs, NFAs, and conversions between all of theses, but I still don't know how to solve this question.


texts:
I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it resulted in too many false positives while reading.

I have a huge web corpus containing web content of billions of URLs. I need to process the web content of URLs satisfying certain criteria: the URL should have appeared in web search results in the past 7 days at least 5 times. This is represented by a list of 208 million URLs. Joining the list directly with the web corpus is not feasible because of volume. So I am considering creation of a bloom filter out of the list and then using the bloom filter to prune out unnecessary URLs from the web corpus.


texts: Modified Max Product dynamic solution very inefficient

texts:
The modified max product problem is as follows: given integer string $z_1\ldots z_n$, and an integer $k \leq n - 1$, what is the maximum product that can be formed by placing $k$ multiply signs in between the numbers, in the best possible configuration.

This has ${n-1 \choose k-1} = \frac{n!}{(n-k)!k!}$ configurations...so if $k$ is somewhere around $n/2$, then it should be a very large search space...so maybe some complexity makes sense.  However, I think I screwed up (aside from any indexing errors).

I have an $O(n^5)$ algorithm...

maxprod(z,n,k):
    for i = 1 to n:
        for j = 1 to n:
            T(i,j,0) = Z[i ... j] as an integer

    for s = 2 to n:
        for i = 1 to n - s:
            let j = i + s-1

            for a = max(0,k-n-s-1) to s-1: (all sizes of a)

                T(i,j,a) = max(...

                    for v = i to j: (splitting i and j)
                        for b = max(0,a-(j-v-1)) to min (a-1,v-1):
                            T(i,v,b)*T(v+1,j,a-1-b)
                  )
    Return T(1,n,k)

And I created it using a recursion,

$
T(i,j,a) = \mathop{max}\{T(i,v,b)\times T(v+1,j,a-1-b)\}
$

Where $v$ is varied from $i$ to $j$ and $b$ is varied from the minimum value it needs to be to the max it can be (for the multiplies needed in the substring such that exactly $k$ multiplies are used).

Is this even properly implemented?  Is there a faster solution? Where am I going wrong?  For some reason, I am struggling with dynamic programming...(only three or four dp problems solved so far though).

But then, I am thinking: I only do a max across two dimensions, inside the three for loops necessary to fill out a 3d array. This is essentially the fastest I can possibly do it in terms of $O(.)$ with my recursion.  Where am I screwing up, conceptually? This problem can't be as difficult as I made it...


texts: Why is "encoding" important in time complexity?

texts:
I read many writing about the time complexity of 0-1 knapsack problem.

(https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668)

In conclusion, the time complexity of knapsack problem is O(nW) but it is pseudo-polynomial

because the size of W in binary encoding system is logW.

if it is unary-encoded, it is polynomial.

But my question is why we need to think like this?

in this https://stackoverflow.com/questions/10422000/encoding-of-the-input-time-complexity/10422079,

the knapsack problem algorithm consumes same amount of time regardless of its encoding system.

When increasing W value from 10, 11, 12, ..., the consumed time for algorithms is also increasing according to the W value.

Why do we have to consider its encoding system and why is it important?

It seems that we have to think in the view of computer but I don't know exactly.


texts: What is the relation between NC and P/poly?

texts: I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)


texts: Approximate time for selection operation using index when equality is on nonkey

texts:
In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b_s + b_t)$ where $b_s$ is disk seek time and $b_t$ is disk transfer time (assuming one level of indexing), because one seek and transfer time will be needed for finding the index and another one will be for the actual data.

But what will happen if the equality is on a no- key value? Since now we cannot search in the index, don't we have to do a linear search?


texts: Shortest path when allowed to reverse an edge

texts:
We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the wrong direction.

If we insist on using all edges in the correct direction, we can solve this using BFS algorithm with $O(|V| + |E|)$ complexity.  There's a brute-force solution by reversing each edge in turn and using BFS on each resulting graph, but that takes time $O(|V|\,|E|+|E|^2)$, which is rather inefficient. Is there a faster solution?  I Googled and couldn't find something similar, thanks for your attention and help.

I cannot provide any source URL, because it seems that it is a an example of "oral folk arts".


texts: Confused about how to exactly determine the complexity of an Algorithm

texts:
Let's take this algorithm as an example.

$PATH$ = {$G$, s, t | $G$ is a directed graph that has a directed path from s to t }.

Prove that $PATH \in P $.

Ok, I know the basic algorithm is to start from node s, place a mark on it, and then look over the rest of the edges and place a mark from node s to node x if there exists a edge from node s to node x. If you place a mark on node t, then accept; otherwise, keep doing this until you run out of nodes, which implies you reject.

I'm getting caught up in implementation details, really. I can most likely envision a turning machine that can do this in polynomial time, but I don't know if this is the right way to go about it,per say. In Sipser, it seems like a very "hand wavy proof." When I encounter an algorithm should I first figure out a way to implement it on a reasonable Turing machine? Or is there a better way to do this. Thank you.


texts: LET REC recursive expression static typing rule

texts:
I'm taking a programming languages course and had a question regarding the typing rules for a recursive let rec expression in a static typing system.

To be more specific, we're using the textbook Essentials of Programming Languages (3e) - Friedman & Wand.

To give some rough background, here's how the author describes the typing rule for a normal let binding expression:

To briefly describe it for anybody unfamiliar with the notation, type-of is a function used to evaluate the type of the given expression.

According to the typing rule, we evaluate exp1 first, which would give us type $t_1$. Then we extend our current environment so $var$ is mapped to $t_1$. Using this new environment, we evaluate the $body$ of the expression which gives us our final type.

Here's a typical let binding example in the OCaml programming language:

let func (x) = x + 1 in (func 3);; (* Outputs -: int=4 *)

let func = fun (x -> x + 1) in (func 3);;
(* Equivalent but better aligned with given typing rule. *)

Here's how a let-rec recursive binding's typing rule is defined:

The main problem that I'm having is how to understand the order of evaluation. According to the typing rule, it seems as though we're extending the environment first with $var$ and $p$, but where are we getting the types to map them to from?


texts: Minimal spanning tree with degree constraint

texts:
I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of minimal spanning tree in which the degree of vertex 1 is at most $k$ (we don't care about other vertices' degrees). We can assume that such a tree exists.

Can someone give an idea how to approach the solution?

What I've already tried:

1) I know how to find essential edges from vertex 1. We can use dfs and start from a random edge of vertex 1. When we return to vertex 1 we can check if this edge (another vertex 1 edge) has lower weight than the previous one. If yes, than the previous one is not essential.

2) After that I wanted to use Kruskal's algorithm (adding in the beginning of the algorithm all essential edges). But the problem is that sometimes we should not take an edge with minimal weight to construct the required tree.

For example: 9-node undirected graph, $k = 3$

(vertex1 vertex2 weight)
1 2 1
2 3 5
3 4 6
4 5 7
5 1 1
1 6 1
6 7 8
7 8 9
8 9 10
9 1 2

So essentials will be (1,2) and (1, 6) (or (1, 5) and (1,6)). Kruskal will take (1,5) (or (1,2)) anyway. And the weight will be 41, but the correct answer is 39.
So I don't know how to use Kruskal's algorithm here.

(The same example visualized, vertex 1 = vertex A)

I thought that we may construct a minimal spanning tree without constraints and after that try to transform it to the required one, but I don't know how to do this (how to transform without brute force).


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

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

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

Thanks


texts:
I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$?
Is there a specific way to find number of 2-3 trees of depth $n$?

Thanks!


texts: What is the relation between Time Sharing operating systems and Round Robin CPU scheduler?

texts:
So i have asked this before, but i still didn't get my answer so I'll try to make my question more clear this time :

Based on my O.S book, Time sharing operating systems switch between processes very fast using a time slice and it uses interrupts when the time slice ends and switches to another process, so isn't this the definition of round robin CPU scheduling algorithm? so are they saying Time sharing O.S uses Round Robin cpu scheduling or what?

if not, then what is the relation? for example what happens if our O.S is time sharing and uses Round Robin cpu scheduling vs when it uses another algorithm like FCFS?


texts: Is there any other computation theory besides the one in automata theory?

texts:
I'm a bit confused at a fundamental level.

In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, security, or automata theory for example). Of course, there are also calculus and nonlinear mathematics in Computer Science, but it seems to me that that doesn't matter in the subject Theory of Computation.

Theory of Computation is supposedly for machines. In Theory of Computation, the object of interest is languages and one-dimensional strings/sequences of symbols.

But why is it that it's only for linear, one-dimensional sequences of symbols? The natural phenomenon is also more to analog than digital (take a look at physics, waves for example). Does it mean that Theory of Computation or Theory of Automata is restricted only to machines/computation that is using one-dimensional strings/sequences of symbols?

In general, not only in Computer Science, is there any other object of interest for computation, other than languages and strings? Since languages and strings of symbols are discrete. What about nonlinear mathematics, dynamical system, and wave for example? They are not strings of symbols, right? So, what about their Computation Theory? Is it still restricted to automata, grammars, Turing machine, or are they totally something different?

Are all things can be represented with languages/ strings of symbols? Are languages/string of symbols enough to represent any thing/phenomenon?

What is computation theory exactly for things other than languages/ strings of symbols (if any)?

Sorry that I don't know how to phrase all these better. Can somebody please enlighten me, or provide any keywords that I can search for? Thank you very much!


texts: Virtualization: overcommitment and vCPU scheduling

texts:
I am currently writing a paper about lock-holder preemption with multiprocessors in virtualized enviornment. But I have two questions: one about overcommitment of CPU resources and about scheduling the vCPUs:

I know that an overcommitment of CPU happens, if the total amount of all virtual machines vCPUs $n$ is greater than the amount of physical pCPUs $m$. But what happens, the hypervisor holds only one single VM, which has $n > m$ vCPU configured? Is there any situation in which this configuration would make sense? Because there will be always $m - n$ vCPUs which can't do anything at any point of time.
The vCPUs are assigned the pCPUs, such that the virtual machine works pseudo-parallel. If VM A and VM B have each 4 vCPUs configured and the physical machine has only 4 pCPUs, can the scheduler of the hypervisor take 2 vCPUs from each VM and run them? This means, each machine has 2 vCPUs that are not running in this moment. Or does a VM can only run if every vCPUs are assigned to the pCPUs? If this happens, VM B would be seem like "dead" at this point of time, wouldn't it?


texts:
This is the task: I have a unitary target matrix $T$, to decompose using matrices from a fixed (finite) universal set $\{M_i\}$, e.g. $T = M_6M_3M_9M_0$. The set is universal in the sense that one can reach any unitary with by combining its elements appropriately.

I wrote an RL algorithm with a policy network that I feed with the target $T$ and with the current "state" (i.e. the current product of the matrices that the policy chose), which returns the index of which matrix to pick next. In pseudocode, this is what I wrote:

reward = 0
 state = Identity_matrix
 chosen_indices = []
 for(i=0,max_episode_length,i++):
    prob_dist = policy(state,T)
    k = random_int(prob_dist)
    state = state * M[k]
    reward -= 1
    if ||T-state|| == 0:
        reward += 100
        end_episode()
loss = discounted_rewards * cross_entropy([prob_dist],[one_hot(k)])
minimize(loss)

I repeat this loop for several random examples of $T$ of which I know the decomposition. But, even if I limit $T$ to be a single matrix from the set, the policy learns a couple of them and then it stops learning, i.e. when I pick a new $T$, the average episode reward remains around zero.

I tried fiddling with the learning rate, the discount factor, the width of the policy network, nothing seems to make things work. What am I doing wrong?


texts: What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

texts:
Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR.

Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the hierarchy is valid for language as well as grammar i,e if a grammar is LL1 then it must be LR(1); If a language is LL(1) then it must be LR(1).

Language theoretic comparison of LL and LR grammars

In the above link there is mention about two type of hierarchy. One for grammar, another for language. The two hierarchies are different at some points.

For e,g for grammar hierarchy $LALR(1)\subset LR(1)$ but for language hierarchy
$LALR(1)=LR(1)$. I accept the grammar hierarchy. But the language hierarchy confuses me. Basically this hierarchy says that LALR(1) language set is equal to LR(1) language set.

How could this be true?

There are some grammars which are LR(1) but not LALR(1). So the language produced by these grammars should be LR(1) but not LALR(1) thus violating the language hierarchy.

I must be making some kind of mistake. please someone point that out?


texts:
So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it.

I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's my turn. I pick another node in X (must be a new one that hasn't been used before) that is also connected to the node in Y you just picked. We continue playing in this manner, until someone cannot pick a node (i.e. all edges out of the current node have already been used). When that happens, the person who cannot pick a next node loses.

I'm supposed to find a polynomial time algorithm to decide which of the two players (you or me) can force a "win" for a given bipartite graph.

I'm stumped. I've approached this in many different ways, including the following two:

1) 1) each node in the xy "path" played will use two edges, except for the first and last nodes which will only use one edge. Idea: add one new node on each side of the bipartite graph, and connect to all opposite nodes. Then check for a perfect (or maximal) matching twice, removing the edges used in the first perfect (maximal) matching when finding the second one. I don't think this really helps us with the problem, though, as there are many different nodes you could visit next given a current node.

2) A second idea was to work with alternating/augmenting paths (as we "zig-zag" between the two sides). I again got stuck since at any given node there are many possible nodes to visit next.

Does anyone have any suggestions for this problem? I'm thinking it has to do with matching, but I could be wrong.

Thanks in advance!