texts: Complexity of finding a Eulerian path such that the image under a bijection is also a Eulerian path

texts:
Problem input: undirected graphs $G$, $H$ and a bijection $f: E(G) \to E(H)$
Question: Is there a Eulerian path $p: \{1,\dots,|E(G)|\} \to E(G)$ in $G$ such that $f \circ p$ is a Eulerian path in $H$?
Is this problem in $P$, $NP$-complete or maybe equivalent to some other well-known problem that isn't known to be either yet?
The problem turned up as a special case of a more general problem first in the Bachelors thesis of another student last year and now in mine as well (I was improving some of the results of the other thesis). All other cases of the problem are now known to be either NP-hard or solvable in polynomial time, but neither one of us managed to make any progress on that case. On the other hand it feels like a much more "natural" problem than the other cases, so I think we may have missed a simple proof.
If undirected graphs are replaced by directed graphs in the problem statement there is a simple polynomial time algorithm (find a Eulerian path in the graph with vertex set $V(G)\times V(H)$ and edge set
$$\{((v_1, w_1), (v_2, w_2)) | (v_1, v_2)=e \in E(G), f(e) = (w_1, w_2)\}$$
ignoring isolated vertices). The analogous graph for the undirected case contains 2 edges for each edge in $G$, so just finding a Eulerian path is no longer enough.


texts: Reducing the halting problem to the uniform halting problem

texts:
As stated here https://books.google.cz/books?id=dwpeNRgjK68C&pg=PA57&lpg=PA57&dq=uniform+halting+problem&source=bl&ots=qsbv_672W9&sig=NDcebhxrwcYdF-P15dor565l8Jc&hl=en&sa=X&ved=0ahUKEwj5mpG-zNTJAhUH6A4KHSB_DOI4ChDoAQgpMAI#v=onepage&q&f=false
Uniform halting problem is variation of Halting problem and asks the question if TM will halt on every input.
I'm little bit confused about the reduction and I'd like some insights whether I understood it correctly or not.
I'd like to approach this somewhat informally. This is how I understand it:

Let's suppose we got TM - M which solves the HP for input w
Then we have TM - M' which should solve the UHP
M' is constructed like this: takes it's input - y and erases it from the tape and then writes w on it
Next it simulates M on the tape (which now contains w)

So M should halt on w, if M halts then M' will halt on any input (because it erases it anyway and it halts on w and w is indeed a valid input) if M will not halt, then M' will not halt on any input. Since we know M cannot know for sure if it will halt on w the UHP is undecidable as is HP.

Couple of things I'm not sure about.

y is the input I should decide whether it will halt on and x is input for M which M halts on (supposing M solves HP) ?
Wouldn't it be easier to just say if I can't halt on one input I for sure can't halt on every/all inputs? In other words if HP is not decidable how can UHP be anything else but undecidable??


texts: Is It possible to change the side of 0 and 1 in Huffman tree?

texts: When we are constructing the Huffman tree to get the Huffman codes, Is it possible to give "1" to left side and "0" to right side rather than giving "0" to left side and "1" to right side of the tree?


texts: What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

texts:
I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of
$$
O\left(n^{2.376}\right).
$$
How much easier is it to simply determine whether the same system has any solution?

More precisely, given a system of $m$ equations and $n$ unknowns, what is the complexity of establishing whether it has any solution?


texts:
The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet check liveness properties.

Today, TLC is able to check liveness properties. I want to know:

What liveness properties is TLC able to check?
How does TLC check liveness properties?

Any references?


texts: Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)

texts:
I'm looking for a reference to an algorithm that does the following. Given n, and a range [min, max], generate a random ascending stream of n integers i_1, i_2 .. i_n such that min <= i_1 < i_2 < ... < i_n <= max. And this should be done in constant space.

(So I'm looking for a more efficient alternative to the following simple approach: First generate n random numbers in the desired range, then sort them, and then go over the sorted list in order. This needs O(n) space.)

I could swear I saw a paper describing an algorithm that does exactly this. But I can't find that paper again, no matter what I search for. Am I misremembering? Can you help me?


texts: Does graph connectivity being NP-complete imply NL=P?

texts:
I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly).

However, my supervisor claims that actually, connectivity being NP-complete implies that NL=P=NP. I can't see why this would be the case; the only additional information we're assuming is that there is a polynomial-time reduction from any NP problem to an NL problem, which does not imply that there exists a corresponding log-space reduction. Wikipedia also mentions

  Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions.

... which seems to support my argument.


texts:
Trying to answer this question:

A factory produces chocolate and candy. In order to produce 100 kilograms of chocolate, the factory has to use machine A for 1 hour, machine B for 4 hours, and machine C for 2 hours. In order to produce 100 kilograms of candy, the factory has to use machine A
for 2 hours, machine B for 1 hour, and machine C for 1 hour. The factory will earn 5 pounds for each kilogram of chocolate it produces and 3 pounds for each kilogram of candy it produces. Machine A and machine B belong to the factory and can be run for free 24 hours a
day. However machine C is rented from a different company and can only be run up to 16 hours a day and costs 20 pounds for each hour it is run. Write down an LP model to maximize the factory profit per day. Explain what each of the variables in the LP formulation means.

Initially I had

$max z = 5x_1 + 3x_2$

$x_1 + 2x_2  \leq 24$ // machine A

$4x_1 + x_2  \leq 24$ // machine B

$2x_1 + x_2  \leq 16$ // machine B

$x_1, x_2, x_3 \geq 0$

However, I then realised that machine C costs £20 for every hour it is used, which affects the objective function. Been looking at this for a while and still can't figure out how to formulate this, any ideas? Would be highly appreciated.

edit: Should the objective function have something like $-20x_3$ at the end? Where $x_3$ is the number of hours machine C runs for


texts: Software or program, what is the difference?

texts: I am a CS student.  When I first came to school, I thought that programming was to make a software.  Now I found I was wrong.  Now I want to know what the difference is, and what is the difference between a programmer and a software engineer. I hope people can give me some advice.  (forgive my broken English)


texts: Converting a algorithm to a runtime function

texts:
I need to find an upper limit for the runtime of $f(n)$.

f(n):
{
 g(n,1)
}

g(n,k):
{
 if n<=0 return;
 for(i=1; i<=n; i++)
 {
  print "I love data structures!";
  k++;
  g(n-1, k);
 }
 return;
}

I tried to think of it this way:

for(i=1; i<=n; i++) $\rightarrow (n+1)c_2$

g(n-1, k) $\rightarrow ng(n-1)$

$$f(n) = g(n,1) + c_f = c_1 + (n+1)c_2 + nc_3 + nc_4 + ng(n-1) + c_f$$

I am not sure about the recursion runtime analysis:

g(n-1,k) $\rightarrow ng(n-1)$

Thank you!


texts: Find largest $k$ numbers in Max Heap in $O(n\log k)$

texts:
I have a data stream with $n$ numbers and I want to find the largest $k$ of them ($k \ll n$). I want to use a priority queue with max heap of size $k$, so I will have space complexity $O(k)$, which is space efficient. The algorithm that I will use work with the following way:

Insert the first $k$ elements to the priority queue
Find their minimum
While there is more data in the stream:

If the new element is larger than the current minimum, replace the current minimum with the new element, and find the new current minimum

I have found in various posts that with this way I can have time complexity $O(n \log k)$. But when I want to find the new minimum, I will need $O(k)$ in the worst case, and I am confused about what I can do.


texts: Can a turing machine calculate word's length?

texts:
I want to understand how a turing machine that will accept only words of length bigger than 100 will look like.
My idea: it will copy a word and move to the right 100 times.
If non of the cells was empty it will accept.
Furthermore if it is true I can also conclude that it is decidable .

If there is no problem with my assertions so far, how will a turing machine that prints the number of letters in a word will look like? is it possible as well?


texts: Minimise simultaneous equation remainder

texts:
I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this:
I have a vector for example:
v = [1,4,5,6,3,1,4,5,6,7,...7]

and I have a set of other vectors for example:
a1 = [0,0,0,0,0,1,2,3,0,0,...0]
a2 = [0,0,0,0,1,2,5,0,0,0,...0]
a3 = [0,0,0,2,2,3,0,0,0,0,...0]
a4 = [0,0,1,1,1,0,0,0,0,0,...0]
...
an = [0,0,1,1,1,0,0,0,0,0,...0]

I want to find out what linear combination of the vectors is closest to v. I define the distance of two vectors to be the sum of the absolute differences of each of its elements. For example the distance between [1,2,3] and [2,2,2] is abs(1-2) + abs(2-2) + abs(3-2) = 2.

Does such an algorithm exist? If it doesn't exist, are there any algorithms that could get me close to a solution?

Ideally I would like an integer multiple of each vector, does such a solution exist with integer multiples?


texts:
For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable?
I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(accepted or rejected) for each and every string input.
So we can decide whether it accepts strings or not.


texts: How to show that Language is not Context Free?

texts: There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the snapshot of the answer which I could not figure out. Could anybody correct it so that the puzzle could be solved?


texts: Tips for improving implementation of Wagner-Fischer-algorithm

texts:
So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a number of different 'misspelled' words w1, w2, ... , wn and a dictionary D compute the editing distances between all words wi and all words di in the dictionary and, for every wi, output the word(s) in the dictionary with the smallest editing distance from wi.

At the moment this is how I've implemented my algorithm;

main():
  minDistance = 1000 // arbitrary large number
  Let D be the dictionary
  Let W be the set of words that needs ‘correcting’
  For every w in W:
    For every d in D:
      dist = distance(w, d)
      if dist < minDistance:
        minDistance = dist
        Make a linked list minList and add d to it
      if dist == minDistance:
        Add d to minList
    Output minDistance aswell as minList

distance(w, d):
  Make a matrix M with dimensions (m,n)
  If the last d and this d has any p (start)-letters in common => use M(m, p) from last computation (no need to compute it again)
  Fill the first row and the first column with their respective ‘index’ //Look at table on Wiki
  For col = 1 to m:
    For row = p to n:
      wagner-fischer(w, d, col, row)

wagner-fischer(w, d, col, row):
  res = M(col-1, row-1) + (1 if w have the same letter at index col-1 as d at row-1)
  addLetter = M(col-1, row) + 1
  deleteLetter = M(col, row-1) + 1
  if addLetter < res:
    res = addLetter
  if deleteLetter < res:
    res = deleteLetter
  return res

Does anyone have any tips on how to optimize my implementation further? I'm really struggling at this point and I don't really know how to improve it further. I've done it in Java if that's of any importance.

EDIT: The online challenge says as follows;

"The input consists of two parts, the first being the dictionary (max 500 000 words) and the second being the words to be corrected (max 100 words). Each word can be max 40 characters long."


texts:
I'm trying to understand how oblivious RAM works, specifically
path oblivious RAM. While I understand how this technique offers protection when reading data - multiple randomly distributed reads obfuscate the access pattern of the data actually requested - I can't tell how that helps protect against an attacker who is interested in the users write access.

Surely multiple randomly addressed writes would potentially overwrite critical data that is later required by the program. Similarly, while batching the writes would stop an attacker knowing exactly which addresses were written to at a given time, this would not stop them discovering which addresses were written to, nor the presence of those writes.


texts: Post's Correspondence Problem - BFS or DFS?

texts:
This question has recently occurred to me as I was working on an implementation of the (Bounded) Post's Correspondence Problem. Basically, which method is generally best for PCP? Breadth-first or depth-first search? Or is this question, well, undecidable?

I understand the basic difference between the two approaches, but I am not on their benefits with regards to PCP. I imagine BFS is good for simple instances, and DFS is good for hard instances. But again, how do we KNOW if a given instance is hard in the first place?


texts: Using Myhill-Nerode to prove that language is not regular

texts:
L = {$xy ∈ \{a, b\}^∗ : |x| = |y|$ and x contains the substring aa}

I am trying to prove that this language is not regular using MyHill-Nerode theorem but I am unable to find equivelance classes of this language.
Thanks.


texts: Cover $n$ points in the plane with $k$ circles of radius $1$

texts:
I am studying for an algorithms exam and ran into this example problem.

  A circular disk with radius $2r$ can be covered by $7$ circular disks with
   radius $r$; in the following you can use this statement without proof.

  Suppose that we are given a set $S$ of $n$ points in the plane, and we want
  to cover all points in $S$ by a minimum number of circular disks of radius $1$. Let $k$ be the optimal number of disks needed. Propose a polynomial
  time algorithm to produce a covering with at most $7k$ circular disks of
  radius $1$.

I do understand the question but I have no idea where to begin or how to approach this. Should a reduction be used? Or is there a simple and obvious answer? How do you cover $n$ points that you know nothing about? Maybe calculate the distances between them?

I do realize that if the distance between all points is greater than $2$ units, then $k = n$ since every circle of radius $2$ can only cover a single point.

I mainly want to understand the problem so that I can attempt a solution on my own, but a solution to the problem would also be nice, so that I can check my answer later.


texts: Are CPU architectures biased towards procedural runtimes?

texts:
Are there any changes that could be made to CPUs to make them perform better for concurrent runtimes like Rust?  For instance, are there changes to branch prediction implementations or cache sizes that would help concurrent runtimes?

I have the impression that current CPU designs might be optimized more for procedural runtimes like C.  If we were instead going to optimize for concurrent runtimes, how would CPUs look different?

For isntance, branch prediction was implemented based on generalizations drawn in research papers analyzing procedural codes. I'm wondering if the concurrency abstraction will add a significant working-set to the runtime that adversely impacts existing branch prediction algorithms. For example, predicting in a for loop is one thing, but when the target of the branch is always some new portion of memory (graphic, text, etc), it'll always be a cache miss, and there'll never be branch history for it-- because neither have touched it yet.

This is probably a silly question because the content, though it might always be in RAM, will be branched to an order-of-magnitude less than it'll be used (once it's been loaded to cache)...but still, there should be an observable temporal-boundary to the contexts stored in the cache and branch predictors in a procedural runtime, that would be manifest as an abstraction-boundary in a more parallelized environment.  So I'm wondering... Have these boundaries been observed?  Have any research papers have analyzed this?

Are CPU architectures biased towards procedural code over concurrent code; or are modern CPUs sufficiently general-purpose that a highly concurrent language doesn't suffer?


texts: How do you sketch a B-spline basis function?

texts:
I'm presented with the question on the practice exam:

  Sketch the curve and control points for the cubic B-spline basis
  function N^3_2 over the knot sequence with 8 knots, full multiplicity
  at the ends, and simple knots in between.

There is almost no information about it in the book. I understand what a cubic B-spline curve is, but I'm not sure I understand the basis function. In the "N^3_2", I'm assuming the "3" is the degree, but I don't know what the "2" represents. The knot sequence should be something like:

|||-----|-----|-----|||

As I understand it, but what is the final sketch supposed to be?

This is for one of my Computer Science classes, but if someone knows of a better forum, please let me know.


texts: DFA for a language that accepts the addition of multiple of 2 and multiple of 5

texts:
I am trying to draw a DFA that accepts the following language:

$L=\{a^{2i+5j} : i , j \geq 0\}$

I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is correct.


texts: Proving non-confluency and adding an equation to make it confluent and terminating

texts:
I currently have a system that has {f(a) = b, f(f(x)) = x} (part of an exam question - look at page 5 - exercise 1).

To start off with proving non-confluency, I am thinking along these lines:

f(f(x)) and f(a) can be unified by using {a -> f(x)}.

Then we can rewrite:

f(f(x)) = x                 [eq.1]
f(f(x)) = b                 [eq.2]

The above two cannot be reduced any further, and do not have any common ancestor or successor. Therefore the system is not confluent.

To make this confluent, we can add a third equation to the system:

x = b

This way, the equation will both be confluent and terminate. Another alternative would be:

f(x) = b

Is there anything I have missed? Or is this pretty much the gist of it?


texts: How does a hard drive knows what bit is the beginning of of a byte/word?

texts:
I'm guessing I could replace the words "hard drive" with "random access medium" but let's be more specific here. Also for the sake of this question, let's not consider SSDs. Just plain old hard-drives with heads and magnetic discs.

I'd guess that the hard drive doesn't care about things as bytes and receives instructions from the OS on about where to move it's head, but that'd assume that the OS has knowledge of sectors, cylinders or whatever physical properties of the drive and it's stored data so that doesn't feel right.

So, how does this work?


texts: Advantage of Stack-Based Allocation for Local Variables

texts:
While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics - 3rd Edition):

  Even in a language without recursion, it can be advantageous to use a stack for
  local variables, rather than allocating them statically. In most programs the pattern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local variables of currently active subroutines is seldom as large as the total space across all subroutines, active or not. A stack may therefore require substantially less memory at run time than would be required for static allocation.

I would appreciate if anyone could explain how stack allocation would save memory when used for allocating local variables. I tried reading this many times. But I can't understand the author meant.


texts: Clarification in the proof for the Bellamn-Ford algorithm

texts:
While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:

  After k (k >= 0) iterations of relaxations, for any node
  u that has at least one path from s (the start node) to u with at most k edges, the distance of from s to u is the smallest length of a path
  from s to u that contains at most k edges.

We prove this lemma using mathematical induction as follows:

Base case: After 0 iteration, all distance values are infinity,
but for s the distance is 0, which is correct!
We assume the lemma is true for k iterations and now we have to prove it for k+1 iterations!
Before k + 1th iteration, dist[u] (which is the distance of u, from s) is the smallest length of a path from s to u containing at most k edges. Each path from s to u goes through one of the incoming edges (v, u). Relaxing by (v, u) is comparing it with the smallest length of a path from s to u through v containing at most k + 1 edges -- this proves it!

Now, I have doubt in the 3rd point. Let us say that in the k+1-th iteration the node u has got a new distance after some edge relaxations, now according to the above lemma, this distance must be the shortest of the distances of all the paths with at most k+1 edges from s to u. Now, consider another node w, that has an edge to it, from u. Now, the length of the path form s to w via v will have at most k+2 edges, but if this edge is relaxed to reduce the dist[w], then in k+1-th iteration itself, we will have included a path (to w) that has almost k+2 edges right? Is it not a contradiction? Can it not happen?

To be more precise I am unable to reason the fact that, the lemma holds true throughout the k+1-th iteration -- I am not convinced with the 3rd step of the proof.

If someone can explain to me the 3rd step or whole proof more clearly, it would be really helpful! If someone can share a proof that does not use mathematical induction will also be really helpful!


texts: Properties of bounded minimum and average degree graph

texts:
Let us have a weighted graph $G$. We are interested in a subgraph, $H$ of $G$ where each vertex has a degree at least a natural number $b(v)$. I am interested in a subgraph where the sum of the edges of the subgraph is minimized. This problem is known as $b$-edge cover. The optimization formulation is as follows.
\begin{align}
\min\ & w(e)x(e) \\
st & \sum_{e \in \delta(v)} x(e) \geq b(v) \\
& x(e) \in \{0,1\}
\end{align}
Here $\delta(v)$ is set of adjacent edges of $v$. Let $\beta_1 = \max_{v} b(v)$, $\beta_2 = \min_{v} b(v)$
It is easy to see that subgraph $H$ has a minimum degree $\beta_2$. I believe the average degree of $H$ is also bounded by $O(\beta_1)$. In this model, I want to know the properties of the subgraph $H$, e.g., the connectivity, degree distribution, clustering properties, e.t.c. Are there any references that discuss this class of graphs?


texts: Resolving NP problem with a deterministic turing machine

texts:
Im studying Complexity Theory and i have a question.
What principle establishes that every NP problem can be solved by a deterministic turing machine in a exponential time ?


texts: Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

texts:
Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
For example, modern machines do overflowed arithmetic by the rules of modulo $2^{32}, 2^{64}$, etc arithmetic.
So why is there rarely a discussion of a theoretical machine that works on finite groups or just integer quotient groups brought to some power which is the memory length (number of "words").
I think a lot can be done with math to solve algorithmic questions, but when one first approaches the subject, there is very little workable mathematics.
Recursive functions are nice, but mathematically they can be very hard to deal with.  Since every recursive algorithm has an iterative counter-part, I wish there were a paper that had operators like $\sum_{i=1}^{g(n)} f(i)$ which mimic a for-loop with bound dependent upon $n$ and that essentially evaluates $f(n)$ every loop.
Why can't we have this type of more traditional mathematics describe algorithms, or can we?  Do you have a definition you're working on?
If so, please share it in an answer to this question.


texts: FM-index and pattern search with wildcards

texts:
in one of my algorithm courses i'm studying the FM-Index.

In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* (where * indicates any character) using backwards search (see here).

How could this be possible? It seems to me that the algorithm already returns all the possible patterns of the form w* (because the starting range in which the search start is $0 - |T|$).And what kind of modification requires the procedure to search pattern in which for example one char is *, for example www*ww?


texts: Get count of longest zigzag sub-sequences

texts: I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to obtain that?


texts: Name for pattern of addressing items by sequence-of-creation

texts:
I'm looking for the name of a particular pattern, and/or resources (articles) on its usage.

The context of the pattern is a journalling system to operate on some collection, as in the example given here:

We could model an webstore using patterns from event-sourcing. In such a model, we would have a collection (e.g. a set) of products. Manipulation of the set would be modeled as a stream of events; typical events to manipulate the set could be "add" "remove" and "change".

All manipulation happens using the events; the resulting collection is constructed simply by replaying the events.

Given the linear nature of the stream of events, we can address each of the items in the set a using unique natural number, being the number of items that were added before it.

I.e. the first added item would be numbered 0, the second added item 1 etc.

Deletion does not affect the amount of added items, so it does not affect the next-used number. Of course, it does lead to "gaps" in the sequence. If we were to start with an empty set, add an item and then delete it, the index 0 points to no (currently existing) item, and the next item to be added will be addressed using 1.

Such an addressing scheme could be useful in a distributed context, where a shared view exists for the history up to a certain point, but the histories diverge from that point onwards. Using the addressing scheme, the various parts of the distributed
mechanism can unambiguously refer to elements from the set.

Is this a well known pattern in the literature?


texts: According to this Wikipedia article on unary language every unary language has a binary variant. My question is that given a unary language is there an equivalent binary language in P that is P-Complete.


texts:
I wonder whether the following language is a context free language:
$$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$
where $\#_x(w)$ is the number of occurrences of $x$ in $w$.
I can't find any word that would be useful to refute by the pumping lemma, on the other hand I haven't been able to find a context free grammar generating it. It looks like it has to remember more than one PDA can handle.

What do you say?


texts: A better upper bound to a recursive function

texts:
it's my first answer here.

I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available.

I've ended up with an algorithm with a complexity function $T(n) = 1 + nT(n - 1)$.

Opening the recurrence relation ends up in:

$T(n) = 1 + n T(n - 1)$

$T(n) = 1 + n[1 + (n - 1)T(n - 2)]$

$T(n) = 1 + n + n^2 T(n - 2) - n T(n - 2)$

$T(n) = 1 + n + n^2[1 + (n - 2) * T(n - 3)] - n T(n - 2)$

$T(n) = 1 + n + n^2 + n^3T(n - 3) - n T(n - 2) - n^2T(n - 3)$

Because of the subtractions, I'm not able to reach good upper-bound for $T(n)$. Any tips ?

Before asking the question, I've managed to state that $T(n) \in \mathcal{O}(n^n)$. Which is 'loose' upper bound, but I'm neither able to figure out a tighter upper bound.


texts:
Consider a graph $G = (V,E)$ and the following operation

$\text{neighbour}(v_1,v_2)$: returns true if the vertices $v_1$ and $v_2$ are adjacent, and false otherwise.

I now consider two standard data structures:

Adjacency Matrix. Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.

Adjacency List. Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.

My question is the following:

  How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)

Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?


texts: What is the optimal way to solve the following optimization problem

texts:
You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.

We need to compute the function $F(L)$ using the least number of transformations/steps.
Computing $F(L)$ is not the main goal. Computing it in the fastest possible way is the goal.

Following rules are allowed to be applied to this function.

--> If $L$ has only one element say $x$, then the $F(L) = x$;

--> If all elements in $L$ are even then $F(L)=2F(L')$, where $L'$ contains all elements in $L$ divided by 2.
For example $F(4,8,10)= 2*F(2,4,5)$

--> If some elements in $L$ are odd and some are even, then $F(L)=F(L')$, where $L'$ has same odd elements as L, but the even elements in $L$ are made odd by removing the factor 2.
For example $F(6,9,20)=F(3,9,5)$

--> If any of the integers in the list is 1, then $F(L)=1$;

--> If two or more integers in $a_1,a_2\ldots a_n$ are same, then we can remove the copies and keep only one of them.
For example $F(4,5,6,5)=F(4,5,6)$

--> For any pair $a_i$ and $a_j$ where($a_i<a_j$), you can replace $a_j$ with $a_j-a_i$

$F(4,7,8)=F(4,(7-4),8)=F(4,3,8)$

It is easy to notice that this process terminates, because at each step, either the value one of the operands is reduced or the number of operands is reduced.

Given $L$ can there be a DP to optimize the number of operations needed to solve $F$, or is there a greedy strategy that is optimal or constant approximate of the optimal?

For example

Consider the following instance

$F(15,30,45)$

Depending on your choice, you can compute this value in several ways.

\begin{align*}
F(15,30,45)& =F(15,30,45-30)=F(15,30,15)\\
& =F(15,30)\\
& =F(15,30-15)=F(15,15)\\
& =F(15)=15
\end{align*}

which takes 4 iterations.

Another way is

\begin{align*}
F(15,30,45)& =F(15,30-15,45)=F(15,15,45)\\
& =F(15,45)\\
& =F(15,45-15)=F(15,30)\\
& =F(15,30/2)=F(15,15)\\
& =F(15)=15
\end{align*}

which takes 5 iterations.

I want an algorithm which finds the optimal solution.


texts: How to decode multiple-digit gamma codes and get the gap sequence?

texts:
How to decode gamma code ($\gamma$ code):

1110001110101011111101101111011

and get the gap sequence?

Detailed information about Gamma codes ($\gamma$ codes) with a brief example of decoding can be found here.

But in their example there is only one case when gamma code ($\gamma$ code) consists of one digit only, how to deal with multiple digits binary string?


texts: Can the decision version of an optimization problem in NP, be in P?

texts:
It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore could check whether a a tour exists which costs at most $K$.

Lets assume we are talking about an optimization problem which is either NP or NP-hard. Can the corresponding decision problem ever be in P?

NB: What I am trying to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time?


texts: What is the asymptotic complexity of the following code snippet?

texts:
for (i = 2; i < n; i = i * i) {
  for (j = 1; j < i / 2; j = j + 1) {
    sum = sum + 1;
  }
}

I know that the outer loop can run for a maximum of $n^2$ times and the inner loop will run for $\frac{n^2}{4}$ times.


texts:
The "function" type $\rightarrow$ is predefined in Agda. But how would one define it if it was not predefined?  Specifically I am talking about $\rightarrow$ in:

data Nat : Set where
     zero : Nat
     Suc : Nat -> Nat


texts: Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

texts:
I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 .

$n$ : number of nodes in the tree

$Z_{n,k}$ : Indicator random variable that activates when rank of the root  is k

$X_n$ : random variable denoting height of BST

$Y_n$ : random variable denoting $2^{X_n}$

In the video, it is said that $Z_{n,k}$ and $max(Y_{k-1} , Y_{n-k})$ are independent events.

But how they are independent? If we have $k=1$, then the max height can go till n. And when we have $k=n/2$ , max can go till $n/2$ only. Therefore the choice made by $Z_{n,i}$ affects the possibilities for $Y_{k-1}$ and $Y_{n-k}$


texts: Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints

texts:
Show that any $S \in NP$ has 2 different polynomial-time verifiers $V_1, V_2$ such that, for all $x,y$, the following conditions hold:

If $V_1(x,y)=1$ then $V_2(x,y)=0$
If $V_2(x,y)=1$ then $V_1(x,y)=0$

I show a guideline that say to define $V_i(x,y)=1$ if $y=p(|x|)+i$ and there exists a prefix $y'$ of $y$ such that $V(x,y')=1$ but I'm confuse to find how it help to find the solution.


texts: Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP?

texts:
I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and couldn't think of a way to disprove it to myself. Perhaps it

Obviously, the algorithm described in the title would have to iterate 2^n times to print all numbers from 1 to 2^n. As a result, this algorithm would never be able to be done in polynomial time and P is indeed a proper subset of NP. What is the error in my reasoning here? Is it that this problem is not in NP?


texts: Why are computable functions continuous?

texts:
I am working on writing an easy to read document about denotational semantics of the lambda calculus. For that I introduce CPOs, monotonicity and continuity.
A CPO is a set $M$ with a partial order $\leq$ and a bottom element $\bot$, requiring $\bot$ to be the smallest element in $M$ and the existence of the least upper bound ($\bigsqcup$) for every chain $d_0 \leq d_1 \leq d_2 \leq ...$ in $M$.
A function $f$ between two CPOs $M$, $N$ is monotone, if for all $a, b \in M$ the following holds:

$$a \leq b \implies f(a) \leq f(b)$$

A function $f$ between two CPOs $M$, $N$ is continuous, if it is monotone and for all chains $d_0 \leq d_1 \leq d_2 \leq \dots$ we have

$$f(\bigsqcup_{i \in \mathbb{N}} d_i) = \bigsqcup_{i \in \mathbb{N}} f(d_i).$$

I want to give my readers a good intuition about the meaning of these definitions. However, I don't have one I could write down.
Following Glynn Winskel in his book »The Formal Semantics of Programming Languages« (1993), $a \leq b$ has to be read as $a$ approximates $b$ (page 72), meaning $b$ has at least as much information as $a$. This leads to monotone functions reflecting more information about the input in more information about the output (page 122).
This is somewhat understandable for me. However, the explanation of continuity is not clear for me:

  As we shall see, that computable functions should be continuous follows from the idea that the appearance of a unit of information in the output of a computable function should only depend on the presence of finitely many units of information in the input.

(page 73)

This is still unclear to me after reading the stream example in section 8.2 (pages 121–123), or this answer.

So my final question is: How do I convince my readers that computable functions are continuous? Why is there no computable function which is not continuous?

It would be nice if you can give me answers/examples which do not require the rigorous introduction of computability or fix-point theory, since I do not want to focus on those things.
Also it would be great if it is not necessary to know the lambda calculus and its denotational semantics in advance, because I want to (and have to) introduce monotonicity and continuity before them.

EDIT:
By computable I mean Turing-computable. Please correct me if I misunderstand Winskels definition of computable on page 337, since it is not explicitly defined as Turing-computable but in an equivalent (at least in my eyes) manner.

Also I want to point out another source I found which tries to explain my problem. But still I don't understand its example, since it is basically the same as the stream example from Winskel.

EDIT 2:
It would also be a good start in helping me to understand the matter to show that every computable function is monotone, i.e. there exists no non-monotone computable function.


texts: Amdahl's law of processors (infinite processors to test limits of speedup)

texts:
My processor noted that an infinite number of processors will allow me to test how much speedup I can achieve.

I am not exactly sure how this applies.

For instance, let's say I have a program that takes $1000$ seconds to execute and is broken into 4 phases(A, B, C, D). If two of the phases are $50%$ parallelizable and the other $2$ are not parallelizable at all, how can I apply the concept that I have infinite available processors to figure out how much maximum speed up I can achieve?

I attached numbers to my example, but a generic one would be just as helpful.

If I am to strictly just apply Amdahl's law, I'd say the answer is just $1/(1-0.5) = 2$ times faster.


texts:
I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$.

I saw some books suggest that we can use the mastere theorem for formulas like:
$T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)$

How is that possible?

My guess: We use it separately. Once for $T(n) = T(\frac{n}{5}) + O(n)$ and once for $T(n) = T(\frac{7n}{10}) + O(n)$ and join between.

Thanks!


texts: Explain better this new inventory for Word Sense Disambiguation

texts:
My question is about CSI (Coarse Sense Inventory), described in the paper CSI A Coarse Sense Inventory for 85% Word Sense Disambiguation (C Lacerra, M Bevilacqua, T Pasini, R Navigli).

Before the question, let me quickly describe the new CSI using phrases taken from the above paper.

CSI is a "a resource that avoids sense distinctions that are
too ﬁne-grained for WSD, while maintaining a granularity that is still meaningful for the task".

CSI is "obtained by linking WordNet concepts to a new set of 45 labels".

The comparison between WordNet and CSI is given in table 7:

Question: What is a semantically-empty prediction? (The paper doesn't explain well what is a semantically-empty label)


texts: I can obviously tell by inspection that it is not true but I cannot figure out how to prove it with witnesses (C and k). Thanks!


texts: What is "dynamic" about dynamic programming?

texts:
One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called like that. That is hard for me to believe.

Does it refer to the fact that the subproblems are solved during run-time and used in reaching the final goal? Like dynamic memory allocation that happens during run-time?

[ANSWER]

I should have read this wiki article before asking the question, sorry.


texts: Undecidable problems with efficient heuristics

texts:
Are there some undecidable problems for which there are efficient heuristic algorithms, that succeed on a sufficiently large subset of inputs to be worth using?

The one application that comes to mind is program static analysis: clearly undecidable (assuming infinite memory – I believe that it is PSPACE-complete if memory is finite but no practical algorithm I know of makes use of this, other than to bound the values of pointers), but in some cases it is possible to prove that a program satisfies a certain property.


texts: Why is Big $O(X^3)$ instead of Big $O(X^2)$ for this algorithm

texts:
The is the running time of an algorithm : $0.5 X^2 + 3X$ ,

Q1) i dont understand why my lecturer says that the Big O is $O(X^3)$, shouldnt it be $O(X^2)$ as it is bounded by the quadratic power of $X$.

Who is correct , me or my teacher ???

Q2) Why is the Theta of the equation : $X^2$, i cant understand why


texts: Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

texts:
I fail to understand why cut off value would be system dependent, and not a constant.

From Princeton University website

  Cutoff to insertion sort. As with mergesort, it pays to switch to
  insertion sort for tiny arrays. The optimum value of the cutoff is
  system-dependent, but any value between 5 and 15 is likely to work
  well in most situations.

Would it be safe to assume that optimal cut off value is equal to optimal set size for Insert sort?


texts: A Formula For Generalized Josephus problem

texts:
There is a formula in wikipedia for the general case of josepus problem

Josephus Problem

But there is no reference for it, I don't know where it came from and I need too find out...
Maybe Donald Knuth's Art of Programming?


texts: Is there a crossover operator to cross sections of specific phenotype genes?

texts:
For example, I've a chromosome with 10 genes, the first 5 genes represent a specific property of phenotype and the last 5 genes represent another property of phenotype.

So, I need a crossover operator that performs the cross considering this configuration, where the parent1's first 5 genes are cross with parent2's first 5 genes and the same for the last 5 genes.

Is there any paper or description of a crossover operator to perform cross in this kind of chromosome?


texts:
I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length)  and I have a query string(P) (or set of strings) that needs to find similar strings former set. My implementation is the following (assuming length is 64 and similarity is defined as hamming distance less than 15)

  Divide each string in T into 16 parts and store each part in a hash table  where key is the hash value and value is a vector
  containing the indices of strings. Ex < 198675, {2, 7, 8, 456}> [I
  have 16 such hash tables for each portion of the string]
  For a query string P, divide it into 16 parts and for each part collect the set of indices(if present) from each hash table and
  then take the union of all. That becomes a small search space.
  Calculate the hamming distance between the query and the resulting set of strings.

I have implemented in C++ and it's working fine, but I am still wondering how could I make it more faster. Any suggestions would be appreciated.


texts: Is this language Recursively Enumerable or Not RE?

texts:
$L = \{\langle M, k\rangle  : M\;\text{is a Turing Machine and } |\{w \in L(M) :  w \in a^*b^*\}|
 \geq k \}$

My Interpretation of language is that $L$ is a language which contains Turing machine whose language contains string greater than equal to $k$ and also strings belong to $a^* b ^*$.

My Analysis : Using Rice's Theorem,

$T_{yes} = L$ and $T_{no} = a^*b^*$

By rice's first theorem we can say that this language is Undecidable and by using rice's second theorem we can say this it is not even recognizable because $T_{yes} \subset T_{no}$.

My intuitive approach : As we know language $L$ is a set of TM which accept a set of strings length greater than or equal to k and are a subset of $a^* b^*$ then for language $L$ to be Recursively Enumerable there must be yes cases for turing machines which are fulfilling the requirement and for no cases it might halt and reject or might stay in loop but the issue here is there might exist a string in $a^*b^*$ which might get accepted later and there are infinite such strings so turing machine can never give yes cases. Yes cases can only happen if TM checks all strings of ab and rejects which are not a part of language but this will not happen as there are infinite strings.

This is not a proof but just my intuition.

Hence by using Rice's theorem we got to know that $L$ is not even Recursively Enumerable but I've been told that my interpretation of language itself is wrong and $L$ is Recursively Enumerable.


texts: Similarity based document classification compared to the user profile ratings

texts:
I need to understand a distinction to check if I understood a document classification problem right.

Given a training set of documents with ratings, that a user has given, let's say rating $r_{k} \in \{"like", "not \ like"\}$ of documents $ d_{k}$ with the features $f_{i} \in d_{k}$ (words, with their frequencies).

Do I now create two vectors $Training_{like} = <..., <f_{i}, |f_{i}|>, ...>$ and $Training_{not\ like} = < ... >$ in a user's profile and add up the $f_{i}$ term frequencies of all documents according to $r_{k}$ in two giant vectors and compare then a new document $d_{j}$ with both vectors $Training_{like}$ and $Training_{not\ like}$:

$similarity(Training_{like}, d_{j})$ and $similarity(Training_{not \ like}, d_{j})$
and then take the closer vector or do I need to store and compare all single $d_{k}$ in the Training sets and compare each documents individually in each class with $d_{j}$ ?

The similarity function is:

$sim(d_{i}, d_{j}) = \frac{\sum\limits_{k} w_{ki} \cdot w_{kj}}{ \sqrt{\sum\limits_{k} w_{ki}^2} \cdot \sqrt{\sum\limits_{k} w_{kj}^2} }$, with $w_{k,i} \in d_{i}$ and $w_{k,j} \in d_{j}$

Whereby the two documents $d_{i}, d_{j}$ are, instead user profile and document features:

$sim(Training_{like}, d_{j})$ and $sim(Training_{not\ like}, d_{j})$


texts: Capacity of channels: Why do we need Blahut-Arimoto algorithms?

texts:
The capacity of a noisy channel $\mathcal{E}_{X\rightarrow Y}$, where the channel is given as a conditional probability distribution $p(y|x)$, is

$$C = \max_{p_X}I(X:Y),$$

where $I(X:Y)$ is the mutual information and $p_X$ is the input probability distribution. This optimization problem is concave. The Blahut-Arimoto algorithm is commonly used to find the solution of this optimization problem.

My question is, why was this algorithm developed? Since the problem is a convex optimization problem, why can we not use standard methods such as gradient descent to solve it? Is it that the Blahut-Arimoto algorithm is more efficient or something else? I have read the original paper of Arimoto but it doesn't compare their method to standard convex optimization problem techniques.


texts: Lower bounds for space with some probability of error

texts:
There is an  information theoretic lower bound of $\log_2 {U \choose x}$  for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$.  We can in principle use this representation (perhaps inefficiently) as a data structure to test if any query is part of this subset.

How can you show a similar information theoretic lower bound if we are happy to have false positives with some probability $p$?


texts:
So we have the following table of processes , where A, B and $\Gamma$ are the resources.

Here is a pic that i drew with the processes and the resources.

So the exact question is this: Using banker's algorithm, calculate the minimum values of $x$ and $y$ in order the system is Deadlock free.

I have done pretty much huge paper work and found that $x,y$ should be the numbers 2 and 3. But in order to find this I run the algorithm on paper several times ; for $[x,y] = [0,0],[0,1],[1,0],[1,1],[1,2]$ etc. until I found that for pair $[x=2, y=3]$ the system is deadlock free!

So, I think that I am missing the point. All this took me like 1 hour or so. Is there a simple method with less paperwork?

Thanks a lot in advance!


texts: Longest Repeated (Scattered) Subsequence in a String

texts:
Informal Problem Statement:

Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right yields the same result as reading only the blue letters.

In the example we could colour them like this: $A\color{blue}{C}\color{red}{CAB}B\color{blue}{AB}$

Therefore, we say $CAB$ is a repeated subsequence of $ACCABBAB$. It is also a longest repeated subsequence (which is easy to check).

Can we compute longest repeated subsequences efficiently?

Formal Question:

Is it NP-hard to decide for a string and some $k$, whether a repeated subsequence of length $k$ exists in the string?

If so: Which problem can be reduced to this problem?
If not: What is an efficient algorithm? (obviously, this algorithm can then be used to compute a longest repeated subsequence)

Bonus Question:

Will their always be a repeated subsequence of length $n/2 - o(n)$ if the size of the alphabet is bounded by a constant?

(This is known to be true for binary alphabets.)

Edit 2: The negative answer to the Bonus Question is already known for alphabets of size at least $5$. In fact for alphabets of size $Σ$, there are strings with longest repeated subsequences of a length of merely $O(n · Σ^{-1/2})$. Random strings suffice to show this. The result already existed, but I overlooked it.

Edit:
Note:

Some people mean "substring" when they say "subsequence". I don't. This is not the problem of finding a substrings twice.


texts:
Are there any compression algorithms outside of entropy encodings that yield a significant compression ratio for memoryless sources (not the Markov kind, but this kind)?

More concretely, if a million ASCII characters, each generated from the same probability distribution that is not necessarily even but where the probability of each ASCII character being chosen is non-zero, what compression algorithms outside of entropy encoders (such as arithmetic, huffman) would yield decent compression ratios?


texts: Why the proof of the hyperbolic bound for rate-monotonic scheduling works?

texts:
Recently I'm trying to prove the hyperbolic bound for rate-monotonic scheduling (RMS).
[original paper] http://retis.sssup.it/~giorgio/paps/2001/ecrts01-hb.pdf
[more formal paper] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1214341&tag=1
The two papers above start with Liu & Layland's result (1973) and derive the hyperbolic bound for the RMS utilization test. However, the proof seems specific to the task set that fully utilizes the processor and achieves the minimum total utilization possible. How is the proof able to extend this multiplicative inequality to all the task sets?
I've googled and checked some handouts, but all of them seem to directly refer to the two papers above and provide no details.


texts: How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?

texts:
I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following:

We're given $(\langle M \rangle, t)$ where $\langle M \rangle$ is the encoding of a Turing machine $M$ and $t$ is a natural number given in unary. Claim: one can tell whether $M(\langle M \rangle,t)$ accepts within $t$ steps using only $O(n \log(n))$ steps where $n$ is the size of $(\langle M \rangle, t)$.

I can buy that this is possible for any fixed $M$. But the claim also needs to hold if $t$ is fixed and $M$ varies. Or if either vary. At this point I'm getting a lot more skeptical. Here's Sipser's proposed solution $D$:

  We can think of $D$'s single tape as organized into tracks. One way to get two tracks is by storing one track in the odd positions and the other in the even positions. Alternatively, the two-track effect may be obtained by enlarging $D$'s tape alphabet to include each pair of symbols, one from the top track and the second from the bottom track. We can get the effect of additional tracks similarly. Note that multiple tracks introduce only a constant factor overhead in time, provided that only a fixed number of tracks are used. Here, $D$ has three tracks.
  One of the tracks contains the information on $M$'s tape, and a second contains its current state and a copy of $M$'s transition function. During the simulation, $D$ keeps the information on the second track near the current position of $M$'s head on the first track. Every time $M$'s head position moves, $D$ shifts all the information on the second track to keep it near the head. Because the size of the information on the second track depends only on $M$ and not on the length of the input to $M$, the shifting adds only a constant factor to the simulation time. Furthermore, because the required information is kept close together, the cost of looking up $M$'s next action in its transition function and updating its tape is only a constant.

(Emphasis mine)

The highlighted passages seem very suspect to me. These operations are only constant if $M$ is kept fixed. They are not constant if $M$ is allowed to vary. Is there a simple fix to this argument?


texts: Circular Doubly Linked List find length with single pointer

texts:
I have pointer to circular doubly linked list with random values of 0 or 1.
Example: [{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]
I have a single pointer to the first item of the list.
I need to find the length of the list without to create any additional pointers.
In addition, I can change the values of each node between 0 to 1 or 1 to 0.

I thought about Josephus Circle algorithm - with no success.

My main problem is that I don't even know what end of a circle/circular list is.
If you think about that, you will understand it is not an easy question.


texts: What is the current definition for HPC systems - do they include both GPUs and MIMD Supercomputers?

texts: I have seen several definitions across the internet and this question still bugs me.


texts:
So, i would like to know the time complexity of the following codes:

x = (float) rand() / rand();   // T(4)

while (x >= 0.01)   // T(?)
{
    x *= 0.8;  // T(?) x T(2)
}

Assuming that all the basic operations are perfomed once, is the best case T(1) - constant time? Since, that might only happen when the random x generated is <= 0.01.

What about the average case? Is it T(?) x T(1) / 2?

Thanks a lot!


texts: top k selection in fixed size priority queue with dynamically changing values

texts:
My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a long running online top k selection

I imagine that operating systems do this all the time, but not being a systems guy, I don't know what terms to search for. Thanks in advance.


texts: Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)?

texts:
I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. The final state that I would like to achieve is: to select an object and have a relevance list from the most relevant objects, that correlate to the one that I've selected, to the least relevant ones.
Ex.: I have a list of events such as event A that represents a fork-lift accident in x_c=5, y_c=7, 22:10:59, tag["Crash"]. event B (fork lift speeding at x_c = 3, y_c = 5, 22:10:11, tag["Speeding"]). Event C (overheating on fork-lift 22:01:44, x_c=-4, y_c=-1, tag["Mechanical Issue:Overheating"]). Now I select event A and then I get a list of the most relevant events related to event A, usually when you crash the fork-lift is because of high-speed, and they tend to be spatially and timely near each other. Therefore, by selecting event A in my list of relevant events I get event B before event C in my list. The issue for me is that by encoding the tags I don't know if I'm keeping them relevant for my model, and they are suppose to be very relevant.
*Edit -> I believe it's also important to point-out the multi dimensional factor of the time attribute: both time difference between events and the time of the events are significant to their correlation. What do I mean? Some types of events are more likely to be correlated at certain times of day than others. For instance, fork-lift speeding and crashing happens more often in the morning rather than in the evening.
The two different approaches that I used to achieve this goal were:
Multi-linear regression to create a correlation function between the objects. This works to a certain extent, the problem is to encode the tags in a way that doesn't negatively influence the correlation.
Unsupervised learning, utilizing clustering and utilize the inertia between points to establish the relevance between the objects: low inertia=high relevance. Same issue here with the encoding, I must encode both labels and time-stamps (HH:mm:ss).
Please share your thoughts and let me know if there is any better approach or more optimal way of executing the approaches that I'm already using (I've wrote the scrips in python, so it's easy and fast to make changes before implementing the final version in a different platform).


texts: Spacial complexity of an $O(2^N)$ time-complexity algorithm

texts:
For the following code sample:

int f(int n) {
    if (n <= 0) {
        return 1;
    }
    return f(n - 1) + f(n - 1)
}

I understand that the time complexity is $O(2^N)$. However, what I don't understand is how the space complexity is $O(N)$. The argument I have heard for this is that although we have $O(2^N)$ nodes in the tree total, only $O(N)$ exist at any given time. What does that mean, how is that so? If the recursive calls are going to be made until the base case is reached, then don't we have $O(2^N)$ calls to make instead of $O(N)$?


texts: Time complexity ( $\Theta$ ) of function

texts:
Let f be the function with one argument - positive integer n

function f(n)
  j = 1
  for i=1 to n:
    j = 2*j
    k = j
    while k > 0:
      k--
      print *

My approach:

let n = 6
breakdown the for cycle
breakdown the while cycle -> when i == 1, we print two *, when i == 2, we print four *, etc.

 So I've assumed that it can be $\sum_{i=1}^n 2^i$ what gives me $\Theta(2^n)$.
Am I right or did I something wrong?


texts: Is there research into associative/commutative optimizations?

texts:
While playing around with optimization sets in LLVM, it occurs to me that the order in which optimizations are run matters greatly since, in general, A(B(src)) is not equal to B(A(src)) where A and B are some optimization of type source -> source and src is of type source.

Are there optimizations for which that property holds? Are there projects or research that attempt to formalize or otherwise create these types of optimizations?


texts: Is longest-path with a specific source and destination impossible in polynomial time?

texts:
The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a given origin and destination in a graph. Is it possible to find a longest
path from a source vertex to a destination vertex in polynomial time?


texts: I'm wondering if there is a standard way of measuring the "sortedness" of an array?  Would an array which has the median number of possible inversions be considered maximally unsorted?  By that I mean it's basically as far as possible from being either sorted or reverse sorted.


texts: Deterministic pushdown automaton for a given language

texts:
I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:

$\ L=\{0^n 1^m a^i b^j \ /\  m,n,i,j > 0 \ and \ m+n=i+j \} $

Thanks!


texts: I have a space with obstacles I wish to find a path through. What I can do is discretize the space into a grid and use A* (or D* or whatever) to find a path through it. I wish to now add orientation to the algorithm. So the node location now becomes a 3d vector (x, y, phi). You can go from one node to another one only if they belong to an arc (both positions are on a circle and are oriented along the tangent lines). How do I discretize the space so that angles don't explode in a sense that by traversing the graph, the set of possible angles becomes finite?


texts: What is known about this independent set generalisation?

texts:
An applied problem I am working on could be modeled as the following problem on graphs:

Given an undirected graph $G=(V,E)$ and an integer $k>0$, find the largest set $S\subset V^k$ such that for each $A\in S$ the induced subgraph $G[A]$ is connected and such that no two $A_1, A_2\in S$ are adjacent in $G$.

For $k=1$, this is just the independent set problem, but for $k>2$ there doesn't seem to be any material on this generalisation.  Is this a known problem?  If yes, what is it called?
I am also interested in the case where instead of a single $k$, we have a multiset $K=\{k_1, k_2, \ldots, k_n\}$ and we want to decide if an $S=\{A_1,A_2,\ldots,A_n\}\subset2^V$ with the aforementioned properties exists such that $|A_i|=k_i$ for $i=1,2,\ldots,n$.


texts: What is the difference between exhaustive search & combinatorial search?

texts:
I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper!

What is the difference between  exhaustive search & combinatorial search ?


texts:
I have recently learned about radix sort.
I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort.
Radix sort runtime is $O(d(n+k))$ where $d$ is the number of digits in the numbers, and $k$ is the base.
So shouldn't there be a permanent ratio between $d$ and $k$ so that the runtime is optimized?
How should I choose the base in any other way?


texts: Math term for Associative arrays/Maps/Dictionaries

texts:
What would be the equivalent math concept for associative arrays/maps/dictionaries?

EDIT: Disregard mutability. FYI,off topic, the reason why I ask this question, is that I want to calculate the distance(or similarity) between two maps given that I have a distance function for each entity(or key) in the map.


texts:
I'm reading Operating System Concepts by Avi Silberschatz(9thE), in section 11.4 File-System Mounting, the author explains the steps of filesystem mounting as follows:

  The operating system is given the
  name of the device and the mount point—the location within the file structure
  where the file system is to be attached.
  Next, the operating system verifies that the device contains a valid file
  system.
  Finally, the operating
  system notes in its directory structure that a file system is mounted at the
  specified mount point.

I'm confused with the final step, since to the best of my knowledge, the directory structure is stored somewhere on the disk, which records the files' information -- such as name, location, size, and type. Then what does the author mean by directory structure in operating system? Is it the same directory on disk?

Additionally, which part finishes the conversion from file name to physical address on disk? Is it the disk driver or the disk controller or done by processor with memory?


texts:
Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?

My guess is that the original syntax (concat, | and *) is, but the Perl-style syntax is not (backtracking). As the newer syntax recognises non regular languages they must also generate non regular languages. If a DFA could recognise a non regular language then there would be a problem...


texts: If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?

texts:
In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds?
i take as granted that both of f(n)=o(h(n)) is true and f(n)= O(g(n)) (from THETA) then i need to show
g(n) < c h(n) given that i have f(n) <= d g(n) and f(n) < c h(n) how one would proceed from there?


texts: Finding an element in array, whose index number and element value same

texts:
Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?


texts:
In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said "I know it when I see it." It struck me that this was a pretty good description of recursive enumerability (recognizability): he was asserting that he was a recognizer for the set of all creative events, broadly construed, that were pornographic. By saying that he wouldn't, and perhaps couldn't, define pornography, he was saying that as far as he was concerned, pornography was not recursive, in that while he could answer "yes" to the question "is this work pornographic?" he couldn't correctly answer "no" in all cases, saying, in effect, that the set of pornographic events wasn't recursive (decidable). In short, he claimed, metaphorically, the set PORN was in $RE\setminus R$.

Pedagogically, this metaphor might work well as an aside when I introduce $RE$ and $R$ to my students, but I'm not entirely happy with it, since it seems feasible that another jurist might very well assert that s/he could indeed determine, for all possible creative events, $e$, whether $e$ was not pornographic. The question is, is there a "tighter" real-world metaphor, where we could agree that determining whether $e$ is a member of $P$ is obviously possible, but determining that $e\notin P$ for all $e$ is obviously impossible?


texts:
Is there a name for a counted set (multiset) that is ordered?

For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the items were added to the cart unless an item of the same type was already added in which case a number associated with item is incremented.

Is this a well studied data structure or just a specialized multiset? I imagine it could be represented with an internal data structure of a dictionary and an array.


texts: Checking whether two paths are intersecting in a tree

texts: The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint paths or not ? The solution I thought was that the LCA of (u1 and v1) should be the ancestor of u2 or v2 or vice versa . But this is a wrong solution since it does not always work out correctly .


texts: How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism?

texts:
I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem.

Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the Hamiltonian Cycle - Subgraph Isomorphic connection, @Luke Mathieson says that "Hamiltonian Cycle to Subgraph Isomorphism is really just rephrasing what it means for a graph to have a Hamiltonian cycle" - but I don't get it.

How does one transforms from Hamiltonian Cycle to Subgraph Isomorphism?

I read Reducing from Hamiltonian Cycle to Subgraph Isomorphism and https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem and couldn't understand how should a proper reduction look like, how to build one that proves the subgraph problem?

Your help in simplifying the problem(s) will be very appreciated.


texts: Does Heapsort work in time o(n log n) in the best case?

texts:
Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs?

For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible.  What about Heapsort? I tried to find an input array such that Heapsort will be working in $o(n\log n)$.

I ask you is it possible? Some permutation? The same elements?


texts: One-dimensional k-center problem. Finding minimum distance

texts:
This is a follow-up to this question: Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be
$$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

Which algorithm should i use to get minimal possible value of $d(X,Y)$?

I tried do develop dynamic programming algorithm but didn't succeed. In my previous question i was told that this problem is known as unweighted one-dimensional k-center problem. I've looked through some papers on the net but all of them offered the ways to find some particular $Y$. But my current problem seems to be easier: i need only the optimal value of $d(X,Y)$. So i expect the solution to be rather standard and rather easy.

Thanks in advance.

P.S. The original problem is taken from here:
http://www.e-olymp.com/en/problems/3208


texts: Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals?

texts:
I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations)

This is an example

I was wondering, is it guaranteed that a tree generated would be unique? Or rather, can multiple trees be generated satisfying the two traversals?

I am pretty certain that there will only be one tree that satisfies two traversals, because that is how everyone treats the problem, and it seems somewhat logical, but I have never seen it written explicitly anywhere.

Any sources that answer theoretical questions like this about Binary Search Trees would be helpful as well.


texts: is conflict possible In accepting state of LR(0)?

texts:
Consider the following grammar:

Stmts -> Stmt | Stmts;Stmt

Stmt -> Var =E

Var ->id[E] | id

E-> id | (E)

in accepting state we get

S' -> stmts .

stmts -> stmts . ;stmt

isn't it a conflict ?


texts:
I have been looking into vpn (virtual private network). And I wanted to know more about the theory, how does it work really:

what does it do with the packages?
why is it secure? (or why can it be unsecure)
how does it work on the internet?
how can it simulate you're coming from another country?

It feels so mainstream nowadays (sole available directly from the browser), that I wanted to understand better what happens when you use one.


texts:
I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement

The Frog is in an two-dimensional maze represented as a table.
The maze has the following characteristics:

Each cell can be free or can contain an obstacle, an exit, or a
mine.
Any two cells in the table considered adjacent if they share a
side.
The maze is surrounded by a solid wall made of obstacles.
Some pairs of free cells are connected by a bidirectional tunnel.

When the frog is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don't contain an obstacle in it. If this cell contains a mine, the mine explodes and the frog dies. If this cell contains an exit, then the frog escapes the maze.

When the frog lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won't fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)

It's possible for the frog to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.

So I get input as

The first line contains three space-separated integers n, m and k
denoting the dimensions of the maze and the number of bidirectional tunnels.

The next n lines describe the maze. The i'th line contains a string of length m denoting the i'th row of the maze.
The meaning of each character is as follows:

# denotes an obstacle.
A denotes a free cell where the frog is initially in.
* denotes a cell with a mine.
% denotes a cell with an exit.
O denotes a free cell (which may contain an entrance to a tunnel).

The next k lines describe the tunnels. The i'th line contains four space-separated integers i1,j1, i2, j2. Here (i1,j1) and (i2, j2) denote the coordinates of both entrances of the tunnel. (i,j) denotes the row and column number, respectively.

So for 1st use case input is

3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

Answer for this is 0.25. Total possible path could be frog gets stuck (1,1) cell + can die two times (2 mines) + Exit. So probability is 1/4

But for below use case am not able to deduce the correct probability.

7 7 2
O**%**O
OOOOOOO
OOO*OOO
**OA###
OOOO#OO
O*OO#O%
OOOO#OO
1 1 7 7
6 4 6 6

Answer should be 0.13344359
my answer is 0.2

I wrote a DFS to calculate all the end state a frog could be. In this case 2 exit + 8 mines + 0 stuck.

prob = Double.valueOf(maze.exit.size())/Double.valueOf(maze.exit.size()+maze.mines.size()+maze.stuck.size());

private static void dfs(Vertices v, Maze m, Vertices[][] edgeTo) {
        m.setMark(v.x, v.y, true);

        if(!m.neighbours(v).isEmpty()) {
            for (Vertices w : m.neighbours(v)) {
                if (w!=null) {
                    edgeTo[w.x][w.y] = v;
                    if(!m.marked(w.x, w.y)) {
                        dfs(w, m, edgeTo);
                    }
                    if(w.state.equals("%")) {
                        m.addExit(w);
                    } else if(w.state.equals("*")) {
                        m.addMines(w);
                    }
                }
            }
        } else if(!v.state.equals("*") && !v.state.equals("%")) {
            m.addStuck(v);
        }
    }

can someone help to explain the correct probability in this use case?


texts: Random forests on monotone training set yields a monotone classifier?

texts:
Suppose I train a random forests classifier on a monotone training set.  Is the resulting classifier guaranteed to be a monotone function?

Suppose I apply the ID3 algorithm (the greedy algorithm) to learn a decision tree on a monotone training set.  Is the resulting decision tree guaranteed to be a monotone function?

I can formalize this a bit more precisely.  Recall that a function is monotone if $x \le y$ implies $f(x) \le f(y)$, where we define $\le$ on $\{0,1\}^n$ by pointwise comparison ($x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,n$).

Suppose we have a monotone boolean function $f:\{0,1\}^n \to \{0,1\}$, and suppose that we build a training set as some set of pairs $(x_i,y_i)$ where $y_i=f(x_i)$.  In other words, the training set is consistent with some monotone function, with no errors.

Now train a random forests classifier on a training set of this form.  This will learn a classifier that can be thought of as a map $g:\{0,1\}^n \to \{0,1\}$.  Is it guaranteed that the learned classifier will be a monotone function?  Alternatively, suppose we apply the ID3 algorithm on this training set.  (The ID3 algorithm is the obvious greedy algorithm for recursively building a decision tree that is consistent with the training set.)  Is it guaranteed that the learned decision tree will form a monotone function?


texts:
Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars:

production = lhs '=' rhs.
lhs = nonterminal.
rhs = nonterminal | terminal |rhs_rest.
rhs_rest = nonterminal rhs_rest | terminal rhs_rest | null.
nonterminal = char chars.
chars = char chars | null.
terminal = '"' char chars '"'.

Note that I intentionally didn't account for spaces. Now consider the input string:

abc = abc"def"aa aa bb "ab""bc"

so abc"def"aa contains three objects, nonterminal+terminal+nonterminal, even though a space is not separating between them. However abc must be interpreted as a single object, not for example ab+c. So we require to have a space between two nonterminal expressions, but not between two terminals or two subsequent nonterminal and a terminal. This would've been easy if we had only pairs, but the rhs may contain many nonterminals and terminals. How to write a grammar that correctly accounts for required and non-required spaces?


texts: Are 'zero-one' jigsaw puzzles NP-complete?

texts:
I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed adjacent to each other iff the symbol on one tile's facing edge is $k$ and the symbol on the other tile's facing edge is $\bar{k}$, for some $k\in\{1\ldots n\}$.  Then, given a set of $m^2$ tiles, can they be placed into an $m\times m$ square (rotating but not flipping the tiles) with all edges matching correctly?  (There's also a variant on this problem in which four $1\times m$ 'framing' edges are provided and the pieces must fit correctly into that frame).

I know this problem is NP-complete for sufficiently large $n$, but the bounds that I've seen on $n$ seem to be fairly large; I'm interested in the problem for small values of $n$ and in particular for $n=1$, the 'zero-one' case (where every edge is labeled either $0$ or $1$ and edges with a $0$ must be matched to edges with a $1$).  Here there are (with rotational symmetry) just six tile types (the all-zeroes tile, the all-ones tile, the tile with three zeroes and a one, the tile with three ones and a zero, and two distinct tiles with two zeroes and two ones, '0011' and '0101'), so a problem instance is just a specification of $m$ and a set of five numbers $T_{0000}$, $T_{0001}$, $T_{0011}$, $T_{0101}$, $T_{0111}$ and $T_{1111}$ (representing the count of each type of tile) with $T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$.  The problem is obviously in NP (with $m$ given in unary) since a solution can simply be exhibited and then checked in polynomial (in $m$) time, but is it known to be NP-complete, or is there some dynamic programming algorithm that can be applied here?  What about the 'framed' case where the problem specification also includes the four edges of the square that are to be matched?  (Obviously if the unframed case is NP-complete the framed case almost certainly is as well)


texts: How do you rank the strings represented by a regular expression?

texts:
This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption.

I understand format preserving encryption but I don't understand how regular expressions can be used to get an integer that is the input of an encryption algorithm.

Referring to this video https://youtu.be/MT5ketZ-jLw?t=24m44s at time stamp 24:44

According to the process described - In order to encrypt a string  to a ciphertext of some agreed upon format, you need to rank all the possible strings it can be - then using your FPE function encrypt the integer that represents the input plain text to an integer in the same set - unrank the output integer to a ciphertext.

I don't understand what is being ranked?  Are they actually obtaining all possible string representations of the regular expression and ranking those?  Or are they ranking something else?  Where does the DFA come to play - because I can see a brute force way you can do this without bothering with the DFA - or even regular expressions to define the format.

EDIT:

I have already most of the paper that use ranking in regular languages for encryption such as these ones

Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers
Selected Areas in Cryptography, pages 295-312. Springer-Verlag, 2009 (online, see sec 5 p 10 "FPE for arbitrary RLs")
Daniel Luchaup, Kevin P. Dyer, Somesh Jha, Thomas Ristenpart and Thomas Shrimpton To appear in the proceedings of USENIX Security 2014

Anyway I'm just looking for a 'laymans' explanation of how this works as I cannot find any working examples online.  This would be useful to understand the overall procedure.  All examples I have found regarding regular expressions involve creating the DFA, and most of them end there.  What happens next?

The closest I could find was this post which I think is asking the same thing

https://cstheory.stackexchange.com/questions/18589/algorithm-for-ranking-members-of-a-regular-language


texts: Do Kernel-Mode Windows Services Considered Part of Kernel?

texts:
I learned that there are two types of services in Windows , one called -service- which is in user-mode , other is called -driver service / device driver- which is in kernel-mode.

What I wonder is , do kernel-level services considered as a part of the kernel? If so , does writing kernel-mode services mean extending Operating System?

My lecturer accepts the definition of OS as , it is solely the Kernel. So I wonder if kernel-level services are included in his OS definition.


texts:
Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$.

How can $f(K)$ be a finite set?
Why if $B$ is recursive, is $f^{-1}(B)$ also recursive?


texts: Lowest cost path(s) between source and destination that collects required items

texts:
I have an undirected graph where each vertex is given some items from a set of items. My goal is to find the lowest cost path from my source vertex to destination vertex while collecting all such items.

The added constraint is that I may split my path once at a node once to collect items from some other path and reach my destination some other way and the total cost would be the minimum of the two paths.

I have been stuck at this for days now and can't seem to figure out an algorithm to solve this..


texts: A* algorithm how to choose $h(n)$, a heuristic estimation of the cost of node n

texts:
I'm trying to understand the A$^*$ search algorithm. I read in wikipedia that A$^*$ chooses nodes based on their cost, calculated as $f(n)=g(n)+h(n)$, where $h(n)$ is a heuristic estimation of the cost to reach the target from node $n$. But I don't understand how to determine its value.

Thanks for your help.


texts:
I have been trying to solve this problem.

Convert the DFA to a regular expression.

I extracted these following equation.

$q_1 = q_2a$

$q_2 = q_1a + (a+b)q_3$

$q_3 = q_1b + q_2a $

Also,the solution is
$a(aa)^*+a^*b((a+b)a^*b)^*+a^*b((a+b)a^*b)^*(a+b)(aa)^*$

Can somebody tell me how to get to this answer??


texts: Where can I find the data of the computer experiments in the book "Neural Networks and Learning Machines"?

texts: The book "Neural Networks and Learning Machines" by Simon Haykin has many computer experiments to which many exercises are related. But there seems to be no data for these experiments available online. Where can I find them?


texts: Does the databus size matter for determining the range of the memory addresses?

texts:
If you have byte addressable memory, does it matter if you have a 32 bit or 64 bit databus for the range of the memory addresses for the words of the memory?

E.g.
: Assume a 32-bit word. If you have a processor connected to a byte addressable $2^{32}$ byte memory,

Would the address of the lowest word be 0 and the address of the highest word simply be $2^{32}-4$  (0xFFFFFFFC), regardless of whether your databus size is 32 bit or 64 bit?

What difference would it make when you assume a 64-bit word or a 16-bit word?


texts: Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

texts:
On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets.  This question is somewhat different.

It asks whether the fact the halting problem applies to all TMs can be decided by a TM. I believe the answer is no, and wish to check my reasoning.

Define the meta-halting language $L_{MH}$ as the language composed of TMs  that decide whether a TM halts.

$$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$$

$L_{MH}= \emptyset$ due to the halting problem.

Thus, the title question more precisely stated: is it decidable whether $L_{MH} = \emptyset$?

Per Rice's theorem, it is undecidable whether an r.e. language is empty.
In both cases, if $L_{MH}$ is or is not r.e., it is undecidable whether $L_{MH} = \emptyset$.
Therefore, it is undecidable whether $L_{MH} = \emptyset$.

This proves a TM cannot decide whether the halting problem applies to all TMs.

Is my understanding correct?

UPDATE:
I am trying to show that a TM cannot "prove the halting problem" for some definition of "prove" that seems intuitively correct.  Below is an illustration of why I think this is correct.

We can create a TM $M_{MH}$ that generates $L_{MH}$ in the following way.  The TM takes a tuple $(M_i,M_j,w_k,steps)$.  It simulates $M_i(M_j, w_k)$ for $steps$ iterations. If $M_i$ accepts all $(M_j, w_k)$ pairs that halt, and rejects all others then $M_{MH}$ accepts $M_i$.  Otherwise, it rejects $M_i$ if $M_i$ decides incorrectly or fails to halt.

$M_{MH}$ does not halt, because it must evaluate an infinite number of pairs for each $M_i$.  Additionally, all the $M_i$s will fail to halt.  $M_{MH}$ will be unable to accept or reject any $M_i$ as it will not know from the simulation that all $M_i$s will fail to halt.  Thus, the language it defines is not r.e. and not decidable.

$M_{MH}$ captures my intuition of what I think it means for a TM to prove the halting problem.  Other suggestions, such as $M_{MH}$ rejecting all $M_i$ or outputting a known proof give $M_{MH}$ prior knowledge that the halting problem applies to all $M_i$.  This cannot count as $M_{MH}$ proving something since the $M_{MH}$'s premise is the conclusion it is proving, and thus is circular.


texts: Number of grid points in d-dimensional sphere of radius r

texts:
Given integers $d$ and $l$, compute the number of grid points $x \in N^d$ that satisfy $\sum_i x_i^2 \leq l$ (i.e. $||x||_2^2 \leq l$). (Think of $l$ as $r^2$).

The problem is obviously in #P. Is it in P or a smaller class? What if in place of $l_2$ we use $l_p$?


texts: What does starvation freedom exactly mean?

texts:
Galvin offers the following definitions of starvation:

Indefinite blocking, or starvation, a situation in which processes wait indefinitely within the semaphore.

A major problem with priority scheduling algorithms is indefinite block-ing, or starvation.A process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low priority processes waiting indefinitely.

What I understand from this is, starvation happens whenever a process has to wait indefinitely to get resources, the waiting may be finite, but you cannot specify the time limit. So by definition, starvation freedom must be definite waiting.
Michel Raynal defines starvation freedom as following:
If a process wants to execute the critical section code, then that process eventually executes it.
My question is, does starvation freedom mean a given process will have to wait for a specified finite time(definite waiting, according to Galvin) or does it mean that a process must wait for some unknown finite time(eventually executes it, according to Raynal).


texts: Relationship between Independent Set and Vertex Cover

texts:
Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.

Does this imply that the complement of the independent set problem is the vertex cover problem?


texts: What is the formal way to prove this is still a minimum spanning tree?

texts:
I don't get the formal way of proving the following cases:

Suppose I have a minimum spanning tree $T$ in a graph $G(V, E)$, with positive edge weights $w$, I want to prove the following:

1) If I increase the edge weight of an edge that is not in $T$, then my resulting tree is still the minimum spanning tree.

This obviously makes sense since none of the edges of $T$ have been modified, and even so, the new edges will only have weights higher than $T$. Is there a way I could put this in a formal way?

2) If I decrease the edge weight of an edge that is in $T$, then my resulting tree is still the MST.

Again, this is very intuitive since the minimum weight of my MST is already the minimum, any reduced amount will still make it minimum. Again, the problem is putting this into formal proof.

3) After adding a new edge $e$ with a unique weight $w(e)$ in $G$, the tree will still be an MST.


texts: Designing a different grammer that generates same expression

texts:
I've a set of grammar rules like this:

$$
\begin{align*}
&S \to AbB \\
&A \to aA|\epsilon \\
&B \to aB|bB|\epsilon
\end{align*}
$$

The grammar generates the following words:
$$
\begin{gather*}
AbB \to a^2AB \to a^3AB \to \cdots \to a^nAB \to a^nB \to \\
\to a^nB \to a^nbB \to a^nb^2B \to \cdots \to a^nb^mB \to a^nb^m,
\end{gather*}
$$
so if I did things right, $L(G) = a^n b^m$.
I think that $G$ is a type 1 grammar.

Now I need to design a more restrictive type of grammar that generates the same expression, and I'm stuck. Any help is much appreciated.

My attempt according to the collapsar's answer:

$$
\begin{align*}
&S \to aSA|b \\
&A \to a|b \\
&
\end{align*}
$$


texts: Algorithm for grid with obstacles and movement restriction

texts:
We are given an $n \times n$ grid with some of the squares darkened.

Our goal is to move from the bottom-left to the top-right corner with the following constraints:

1) We cannot step on a darkened square.

2) Each move must be up or to the right.

3) We cannot move in the same direction consecutively four times.

Design an algorithm that runs in $O(n^2)$ time and outputs the set of all squares that can be reached from the bottom-left corner.

My thoughts: We can convert the grid to a graph in $O(n^2)$:  each square (darkened or not) becomes a node, and adjacent squares correspond to edges; each edge is directed either rightwards or upwards. We can then remove the nodes that correspond to darkened squares. At this point, we can BFS or DFS from the top-left node, but we must keep track of condition 3 somehow, with some sort of "cost" array.

Another idea is to "chop off" (this can be formalized) a triangle from the upper left and lower right, which are "too high" and "too right" respectively. But then, the existence of the darkened squares causes some additional squares to be unreachable.

Any help would be appreciated.


texts: About computer science and category theory

texts: I read that Category Theory has alot to do with how programs and information can be organised.Can Category theory simplify various programming strategies? If a specific Category is represented as a directed graph is this similar to flow charts used in programming?


texts: Relation between Hamming distances of columns and rows

texts: You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true for instance that there are two distinct rows $R_k$ and $R_l$ that satisfy $d_H(R_k,R_l)\lt n-t$?


texts: How to construct Context Free Grammar of words with equal number of 0's and 1's

texts:
i am trying to find a cfg for this cfl

L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$

is there a way to count the number  of 0's or 1's in the string?


texts: why we have the coefficient 2 in the feasibility interval for asynchronous constrained deadline systems

texts:
For synchronous constrained deadline tasks the feasibility interval is :  [0, max{Di| i = 1, … , n})
while Di are the tasks deadlines
For (synchronous) arbitrary deadline tasks the first busy period is the feasibility interval
But for For asynchronous constrained deadline systems, [Omax, Omax+ 2P), I don't understand why we have the coefficent 2 beside P.(P is the hyper-period)
Thank You


texts: Do we know how to make a "voice print" and use it for computer generated voice?

texts:
Well everything is in the title.

After all Siri voice was made from someone, so can I
use software to make a computer generated voice sound
like my voice or anybody else?


texts: Decomposing the search problem into several small problems

texts:
I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either:

Searching through the original graph. or
By decomposing it into several subset of problems $P_1,P_2, \dots,P_n$.

Ideally $sol(P )=sol(P_1)\cup sol(P_2)\cup \ldots \cup(P_n)$ with no preprocessing (i.e the union of the subproblems correspond directly to the solution of the problem).

I have no constraint; though prefer the underlying graph to be a DAG and the problem to be a reachability problem. Google seems to fail on finding such papers.


texts: Amortized analysis for dynamic array - how to come up with a potential function?

texts:
I learned about amortized analysis and the potential method, I also
leaned an example of a binary counter which I think I understand well.

In the case of the binary counter I understand the choice of the potential
function - we are paying in advance for a transition from one to zero
that must be made in the future when  a bit changes from zero to one
so the potential function is how much I payed that I haven't used
already.

I got an exercise to find a potential function for a dynamic array
with only inserts. I understand why a dynamic array have an amortized
time of $O(1)$ on inserts - either the array have sufficient size
and there is a simple insert costs $O(1)$ or the array is of size
$k$ and it is full and in that case we spread the cost of the $O(k)$
is costs to insert the element with the last $k/2$ elements of the
array (the new elements), the amortized cost is somewhat of $O(k)/(k/2)=O(1)$.

However I can't come up with a potential function, I don't see a methodical
way of taking this understanding and making it formal with the potential
method.

I have found online a potential function $\Phi=2n-m$ where $n$ is
the number of current elements in the array and $m$ is the size of
the array, I do see a factor of $2$ maybe relating to the $2$ in
the $k/2$ above, but I can't manage to get to the above $\Phi$ myself.

I would appreciate help in understanding how to take my argument and
derive $\Phi$ from it