texts: How can I compress data that represents a number's change over time?

texts:
I have a value that increases by unknown increments at unknown times.  Given a time, I need to check how much it has increased between that time and now.

I could simply store every time/increase pair whenever the value is increased, but this would be too much data to reasonably store.

For example:

DATA:
Value = 0 @ 0:00
Value = 2 @ 0:04
Value = 7 @ 0:05
Value = 52 @ 0:07 (Current time)

RESULT:
1 Second: 52
3 Seconds:  2 + 7 + 52 = 61

I am not sure what I am trying to do is even possible.  But, is there a way I can store the increments such that I can keep the file size reasonably small, and still find a decent approximation of the increase in the value?  It does not need to be exact - a margin of error less than 5% would be acceptable.


texts: Issue triangulating a font glyph for a specific scenario

texts:
I am trying to triangulate TTF glyphs for drawing in opengl. The below image shows an example glyph (Taken fron FontForge application). The X represent control points of a bezier spline, circular and square points represent points on the glyph but they can also be the start / end points of the bezier splines.
I have a triangulation process that can take all these points and render them in opengl, I'd like to render the bezier curves in a shader, I have something that does this and it works. They way I split things up is to take the control points, the start points and end points of the bezier spline and pass those to the bezier shader. For the curves that curve out side the shape I need to remove the control points from the triangulation routine (because I don't want to fill in these triangles completely, I leave that to the bezier shader). For the control points that curve in to the shape I keep them for the opposite reason to above.

For the example above I have shown some additional red lines showing what the new outline would look like with the outer control points removed. That can be seen below.
This shows an example of the issue I am having, I can no longer triangulate this because the red lines at the bottom cross outside the shape and then back in again.
Is there a better algorithm I can use to do this to avoid situations like this?


texts: Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

texts:
I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\{w\mid\#_{a}(w)=\#_{b}(w)\}$ and non-regular (simple proof using pumping lemma) implies that the language $L$ can therefore not be regular!
The proof sounds alright initially but it got messy as I thought more on it!
I read in the books that the subset property of a regular language is not closed under regular languages. So, how can the proof be correct because for all I know L is a regular language that a non-regular language $a^{n}b^{n}$ as its subset. How does it say anything more?

I do know ofcourse that $L$ here is not regular and can draw production rules for it(CFG)! But, I need to clear this confusion I have above! Some help me here.


texts: The language of TMs accepting some word starting with 101

texts:
I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language

$$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has 101 as a prefix} \}. $$

I have made an attempt at showing decidability of $L$:

On input $\langle M, w\rangle$ (where $M$ is a TM and $w \in \sigma^*$):

Simulate $M$ on $w$.
If $M$ rejects and halts, reject. If $M$ accepts and halts, accept.

However, I'm not sure about moving forward after this. I do not want a solution, but I want some ideas/techniques as to what else I can prove about $L$.


texts: Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?

texts: Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w that are in the language of G? And can I get parse trees for those substrings? What would be the time complexity for these things?


texts:
Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following:

1) Minimax with Alpha-Beta Proning

2) A Neural Net

3) Machine Learning

My program has one second to make a move, so I can only branch out 2 moves ahead with Minimax. Which solution would best perform under 1 second?

I looked around the web, but couldn't find anything relevant.

Also, are there any other additional resources you suggest I have a look at?


texts: What unusual property does this finite automata yield?

texts:
I'm asked to construct a finite automata for a given task. The Automata should accept the values zero or one. In the starting state its output is 1. The output doubles with every one as input and is split in half with every zero as input. The maximum value for the output is 4. Another one as input will put the automata in an error-state and it will stay there regardless of the input. An input of zero in the initial state will bring the automata in the error state as well.

I was able to construct this automate and give the transition table. It looks like this

State        Input     Subsequent State
I (001)      0         E (111)
I (001)      1         A (010)
A (010)      0         I (001)
A (010)      1         B (100)
B (100)      0         A (010)
B (100)      1         E (111)
E (111)      0         E (111)
E (111)      1         E (111)

The next short question asks

  What unusual property does this automata yield?

At this point I'm stuck. The only thing I notice, that the error state is kind of a fix point of the automate. Once the error state is reached it stays there regardless of the input. It this the wanted answer? I don't notice anything special in particular..


texts: Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$

texts:
I was told that exponential time always beats polynomial time but doesn't this not work for:
$n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$?
If we take $log_2$ on both of them we get:
$\frac{1}{2}log \,n > \sqrt{log \,n}$
which seems that what I was told is incorrect.

Did I not hear the caveats?
Have I mislabelled exponential and polynomial functions?
If this view is wrong. What's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \,n}}$? How would you show it?


texts: Comparing the complexity of algorithms for listing k-cliques

texts:
Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the graph. http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J053.pdf

We have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$.
In practice, on real-world graphs (which have a small arboricity), our algorithm performs much better than the one of Chiba and Nishizeki. We now want to show through theory that it is better.
So the question is, how can we show that $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is better than $O(m \cdot a^{k-2})$?
Note that we are interested in instances of small $k$, say 10 or less. Is the big O notation relevant here? Or should we work with upper bounds and lower bounds on the number of operations (quantifying the constants in the big O)?


texts:
I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff $I_1=f(I_2)$ is an Yes-instance of $\Pi_1$.

What if I find a (constant sized) family of reductions $f_i()$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff at least one $f_i(I_2)$ is an Yes-instance of $\Pi_1$? Is this enough? Is there a way of translating this one in the "classical" definition? How to formalize this?

I know that in the second situation I can say that I can't solve $\Pi_1$ in polynomial time unless P=NP, but I'm no sure that is equivalent of saying that $\Pi_1$ is NP-hard.


texts:
I've recently begun studying reductions in my algorithms class. All the reductions I've seen have been from decision problem $\to$ decision problem.

Is it possible to do reductions with non-decision problems?
Can NP-hardness be shown in that way?


texts: Duplicate elements in Queue for BFS Maze Algorithm

texts:
I'm fairly new to studying data structures and algorithms.

I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and 0s (spaces), marking visited positions with 3.

However, I notice that there are duplicate values in the Queue. I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains? Will the algorithm still work if I do so?

As far as I know I have implemented the following algorithm:

Create a queue for positions yet to explore, and enqueue the entrance (0,0)
While the list is not empty
     dequeue
     If it is the goal position,
            exit displaying position and success message
     Otherwise,
            mark the position as visited, and enqueue all valid neighbors (not walls and not visited)
If the list is empty and the method has not returned, there is no path

Some sample output is below:

Enqueueing (0,0)
Queue contents: [(0, 0)]
Press Enter to continue:
Dequeueing
Current position: (0, 0)
Marking (0, 0)
[3, 1, 1, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 1)]
Press Enter to continue:
Dequeueing
Current position: (0, 1)
Marking (0, 1)
[3, 1, 1, 0]
[3, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 1), (0, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 1)
Marking (1, 1)
[3, 1, 1, 0]
[3, 3, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 2), (2, 1), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (0, 2)
Marking (0, 2)
[3, 1, 1, 0]
[3, 3, 0, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 1), (1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (2, 1)
Marking (2, 1)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
Marking (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
Marking (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
Marking (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(3, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (3, 3)
Goal reached at (3, 3)


texts: "Compressing" rationals given error bounds

texts:
I'm working on implementing some exact real arithmetic operations for fun. I've got the rough outline of how I want to do things as well and have figured out how to write most of the important algorithms (though I have not properly implemented them just yet).

Going against the "pre-mature optimization is bad, m'kay" philosophy I am wondering about a few things. So reducing fractions is one way to reduce the size of rationals, sure, but it isn't perfect. If you knew you only had to be within a certain range you could do better by changing the value. For instance say I need to add $1$ and $\frac{1}{8}$ to with in $\frac{1}{2}$. I don't need to full precision, I can just return 0 in fact. More beneficially say I had something like $\frac{2^{16}+1}{2^{32}}$, if I only need say something like $\frac{1}{2^{15}}$ precision, I can approximate this rational as $\frac{2^{16}}{2^{32}}$ and then reduce that to $\frac{1}{2^{16}}$.

This are some contrived cases but I think there is a generally useful optimization to be done here. Are there algorithms which, given an error bound, can find the smallest (in bits) rational number within the specified bounds of another given rational number?

Most of my algorithms tend to produce rationals with power of two denominators so I am particularly interested in that case.


texts: How many bits are needed? Advantages/disatvantages of this configuration?

texts:
So the question is:

Assume we had 15 CPU instructions and, for each instruction, we were trusting one particular component of the kernel to handle it. How many modes do we need to support (including the user mode), and how many bits we had to use to represent these modes? What is an advantage and a disadvantage of using this scheme instead of the kernel/user mode scheme, where one kernel component is trusted to handle all 15 instructions?

Is it 16 modes (1 kernel mode for each component, then the 1 user mode) or is it just the regular 2 modes?

Would it be 4 or 1 bit(s) for 16 modes or 2 modes respectively?

I want to say an advantage are that 15 components would be more powerful, but I feel like I should be able to explain more.
I think a disadvantage would be power and memory allocation.

Is that somewhat in the right direction?


texts: Algorithm to find the probability of a given text to be about a large topic

texts:
I want the conditional probability for each topic (being the word that we give as input). For example, the text being

  have seen and reviewed your requirements you posted here.  If you can
  give me the fix criteria/category of your data mining then I can do
  this job. If you want me to define and allot criteria and categorize
  it in then charges will be extra for per categorization included.

  I have seen and reviewed your requirements you posted here.  If you can give me the fix criteria/category of your data mining then
  I can do this job. If you want me to define and allot criteria and
  categorize it in then charges will be extra for per categorization
  included.

Assume that I give a word called research as an input, I want to know

What is the likelihood/probability that the text relates to research?

What algorithms we should create to get the above?


texts: How are image files, sounds, data, etc. compiled/linked in to a single file?

texts:
I'm both asking for me & future readers as to how pictures, sounds, textures, assets, and such are compiled and linked in to one binary/program, and how that process works.

I have seen this in standalone programs I have downloaded on Windows, and I'm fairly certain any OS can implement this. It appears that, instead of keeping the data stored separately as individual files within the filesystem, all data is converged in to one file. When you run the program, it's as if the data could have just, instead of requiring multiple scattered files through the drive, directories, subdirectories, etc., been bound to one program with everything in it; no need for fragmentation, missing files, etc.

So, to sum this question up, let me first illustrate some key points:

I had originally thought that, since all files on the computer are basically high-and-low voltage sources at the lowest level, files can be converged together, being similar to "zipping/unzipping files." Using this common ground, it's easy to see how the data of a file, any file, could be bound/binded together with other data, and act, from the scope of the filesystem and GUI, as "just a file." But many things are actually in it that don't have to only represent just a typical idea of a "program" with some people's view of it as only instructions like adding, moving data around, etc.

I am not sure of this, but I have a good sense that it's similar, so this why I'm asking for clarification.

When you see a standalone program from one file that contains external assets when you run it (texture files, video data format, image data, sounds, other resources, etc.),  it's clear that the single executable file has all the data necessary "packed" in to one somehow, or the such.

How does the compiler/linker do this, how would the program/library/etc. access the data converged in it as opposed to differing from separate "files" independently, and how are compiler's/linker's settings adjusted to do this in any general sense?

NOTE: Programmers, StackOverflow, Superuser, and few others deny this question, and give no reason why, so I figured this area might see it fit.


texts:
Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".

Even though B-trees are a generalization of BSTs, I have not seen much of anything say they are used to create ordered data structures. Wondering if programming languages could/should B-plus trees to create a sorted array, or does it use BSTs. So part of the question is, can B-trees, and B-plus trees be used to create associative arrays and sorted arrays and other list data structures (or should they). The other part of the question is which data structure is optimal for all three sorted list operations (search, insert, delete).

I have heard of skip lists as well, but don't understand them yet. I haven't implemented any sort of BST so I don't have a great deal of knowledge about them but I roughly understand how they work. I have read B-plus trees are best for disk storage solutions (not sure exactly why) because high fanout / low depth. But I am more wondering for purely in-memory sorted arrays, what is the optimal data structure for maintaining it:

Binary Search Tree
Red-Black Tree
B-Tree
B-Plus Tree
Skip list
Other


texts: show doubly connected graph is NL complete

texts:
The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (You may use the fact that PATH is NL-complete.)
PATH = {: G is a directed graph with a path from s to t}

My attempt:
to show DCG is NL complete first we need to show it is in NL. then We need to show that PATH log space reduces to DCG.
to show DCG is in NL we need to define a nondeterminstic Turing Machine that decides DCG in logn space. Here I have a question, what is n? The length of the string  which encodes the graph? Can I think of it as if G has x vertices and y edges then the amount of things I can store in memory in the TM I define is log(x+y)?
since Path is in NL let M1 be a nondeterministic TM which decides PATH in log space.
define M2 (which decides DCG) as:
given input
for every pair of nodes (x,y) in G:
    run M1 on
    if M1 accepts (do nothing just continue the program)
    if M1 rejects then reject
accept

M2 decides DCG, does it do so in logn space? I am guessing yes, because the only space we need is to keep track of what pairs of nodes we have gone through, but that could be represented as a single number if we are given an enumeration of all the pairs of nodes. Like if the enumeration was part of the encoding of the graph. But if our TM M2 has to store that enumeration then M2 doesnt use log space. M2 also uses space to run M1 on each pair, but M1 uses log space, and after each call to M1 we can forget/overwrite the space we used for running M1 on a previous pair.

now we want to show PATH log space reduces to DCG. We assume that there exists a deterministic TM M that decides DCG in log space. We want to use M to define a deterministic TM N which decides PATH in log space. Also given G,s,t we want to convert it into a graph G' such that G' is doubably connected (for every x and y in G' there is a path from x to y and a path from y to x) iff G has a path from s to t.
Define G' as: the graph like G except, for every node x other than s and t, there is an edge from x to s, and an edge from t to x. Then G' is doubly connected iff there is a path from s to t in G.
Define N as:
given input
run M on G' if M accepts then accept, if M rejects then reject

then N decides PATH. Does it do so in log space? M only uses log space, but perhaps there are too many edges in G' so that storing G' uses too much space

If I made any mistakes please correct me. Any additional feedback is very appreciated. In particular, helping me understand some of those questions I had about the space usage. Also I am looking for a tutor in this subject. We could perhaps discuss questions over facebook or something, and I send the money over e-transfer or something.


texts: Would it ever be possible for computer viruses to evolve new "genes" to allow them to perform their job?

texts:
As an A-level Biology student, I have thought a lot about the links with Biology and Computer Science, and something that often comes to mind are the links between Immunology and Computer Security/Viruses. For example, I (through reading about how the anti-virus programs work) decided that the way the immune system handles viruses is very similar to anti-virus programs (both contain a database of virus definitions (be it, $\beta$ memory cells or virus signatures) and both contain a method of extrapolation). The natural progression for me was then thinking about natural evolution of viruses compared to computer viruses. So on to my question:

Would it ever be possible for computer viruses to evolve into new strains which possess new "genes" to allow them to perform their job?

It seems like this sort of thinking could only really apply to viruses, I mean your regular old calculator is never going to be subject to "natural selection". But as far as I know viruses do mutate themselves, in order to avoid anti-virus programs, but presumably these are rather controlled, so that the virus wouldn't gain non-beneficial mutations that might otherwise render it useless. If the true random nature of nature could be applied to viruses, would they ever be able to evolve new functionality, like for example becoming a retro-virus that takes over an anti-virus program, or mutating to include new code that allows it to bring down a firewall? Would they be involved in some sort of computational natural selection, where the strongest viruses survive and pass on their beneficial genes?


texts: Why N-Queens Problem is not used as experiment in CSP thesis?

texts:
I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems.

If so,when I do master thesis in CSP,it is reasonable to experiment algorithms with N-Queens.

How can N-Queens problem be changed CSP parameters like Tightness,Constraint Density to experiment?

I wonder why many researchers test their CSP algorithms with Zebra problem, sudoku ,random CSP but why not N-Queens problem? Is N-Queens problem with CSP does not give better results?


texts: Who (and when) first defined interval graphs?

texts:
I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949.

So, I'm trying to track down the original paper introducing interval graphs for citation, but it's been rather elusive so far.


texts: What is the importance of the condition "| xy | < p" in pumping lemma?

texts:
Let L be a language. w $\in$ L , and w could be broken in xyz.

Then if L is regular, there exists a pumping length p such that:

|y| $\gt$ 0
|xy| $\le$ p
$\forall$ i $\ge$ 0, xy$^i$z $\in$ L

I understand that this lemma is based on pigeon hole principle and proof by contradiction.

For conditon (1), I understand that the string we are pumping should be $\ge$ 1.

But I don't understand the significance of condition (2). Why should the legth of xy be equal to or smaller than p . Will not it work otherwise?


texts: Combinatory interpretation of lambda calculus

texts:
According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says:

  The combinatory interpretation of the lambda calculus is known to be
  imperfect, because it does not satisfy the $ξ$-rule: under the
  interpretation, $M = N$ does not imply $\lambda x.M = \lambda x.N$ (Barendregt, 1984).

Questions:

What kind of equivalence is meant here?
Given this definition of equivalence, what is a counter-example of the implication?


texts: Find all edges in a tree whose removal doesn't separate color classes

texts:
Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Also, for the reference, there’s $O(n \log n)$ approach to solve this task, which doesn’t seem to be optimizable. Let’s store in the vertice the count of all vertices of each color (now the edge is separator if in subtree there’re either no occurrences, or all occurrences of each color), but it’s a quadratic solution. Now we use small-to-large approach (merge these arrays to the one that belongs to the largest child, and pass the reference to that array to the parent), and it becomes $O(n \log n)$.


texts:
So I'm having some discrete elements X1,X2,...,Xn with positive weights Wi (all weights sum up to 1). The weighted average is an element Xk that:

What I want is an algorithm to calculate that Xk in O(nlogn) time with the use of sorting algorithm.

Any ideas to give me a boost? I don't want the whole solution, just something to get it started.

Thanks


texts: Do problems that have unary encodings automatically become unary languages?

texts:
This problem has confused me a lot, can any of you help me out.
Thank you.


texts: Role of weak entities in avoiding inconsistencies

texts:
My material on database claims that:

  Weak entities help to avoid data duplication and inconsistencies arising due to duplicating the key of the strong entity.

My question is how can a strong entity key even be duplicated? This would make the key lose its uniqueness property.

Can anyone please help? How is the statement provided in the material justified?

Thanks in advance!


texts: Problem on probability given frame sizes and their error correction probabilities in a wireless system

texts:
I am stuck trying to solve the following question for a while

Bit error rate after demodulation in an wireless system = 1.0e-03.
The system has 4 possible frame sizes – 48 bytes, 96 bytes, 72 bytes
and 36 bytes with probabilities = 0.4, 0.25, 0.2 and 0.15
respectively. An error correction scheme is implemented on frames with
probabilities of correcting an erroneous frame = 0.6, 0.75, 0.7 and
0.5 respectively.
a) Find the average residual frame error rate.
b) Find the probability that, no frame has error after correction in a
series of 25 frames.
c) If a frame is in error after correction, find
the probability of its size being 48 bytes.

The main problem I am facing is understanding the role of the given bit error rate in this question.
I will lay down what I tried so far, I will start with
(c)

P(48F) = 0.4, P(96F) = 0.25, P(72F) = 0.2, P(36F) = 0.15
the probabilities of correcting an erroneous frame given the frame sizes are    P(C|48F) = 0.6, P(C|96F) = 0.75, P(C|72F) = 0.7, P(C|36F) = 0.5
so the probabilities of not correcting an erroneous frame given frame size is 48 is
P(E|48F) = 1 - 0.6 = 0.4, same for others
probability of not correcting erroneous frame
P(E) = P(E|48F)*p(48F) + P(E|96F)*p(96F) + P(E|72F)*p(72F) + P(E|36F)*p(36F)
using naive bayes,
p(48F|E) = P(E|48F)*p(48F)/P(E) = 0.448

This is where I am getting lost
b)

Probability of no frames having error
P(C) = 1 - P(E)
so    P(no error in 25 frames) = P(C)^{25}

a)

average frame size = 48 * 0.4 + 96 * 0.25 + 72 * 0.2 + 36 * 0.15 = 63 bytes
so the average frame error rate should be = 63 * 0.001/8

This is what I tried, my problem is understanding how to use the bit error rate for finding the given probabilities


texts:
What is the meaning of lambda here:
$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.

I know that lambda is used in the context of NFA?

Let's suppose we break down the expression to:$$(b+c)^*(a+\lambda)(b+c)^*$$

and to:$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$

How the above would generate an empty string?
Somebody please guide me.

Zulfi.


texts: Estimating memory footprint of a C program (and programs in a scripting language using bindings to a C library)

texts:
I wanted to test the feasibility of an idea that might be part of a small project, and I'm trying to set up a quick prototype using Python (with bindings to a C library). If any of this is sufficient for any interesting application, I might make this the main topic of my thesis.
I was able to plot how much memory this prototype uses (sort of experimentally) using psutils and randomly generated problem instances, but I would like to know if there's a more principled/enigineer-like approach to memory profiling (I want to start learning about these topics, because I would like to make reliable estimates in order to better plan ahead).
I'm looking for literature suggestions and practical advice.
Thanks in advance!


texts: Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

texts: There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do # on an element i of the ring, element i-1, i and i+1 will be toggled. (toggled => X->O and O->X).


texts: What is the difference between "Decision" and "Verification" in complexity theory?

texts:
In Michael Sipser's Theory of Computation on page 270 he writes:

  P = the class of languages for which membership can be decided quickly.
  NP = the class of languages for which membership can be verified quickly.

What is the difference between "decided" and "verified"?


texts: Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata?

texts:
I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?


texts: Describe a Monte Carlo algorithm for the Triangle Packing problem

texts:
Book: Parameterized Algorithms by Marek Cygan (free to download legally)
Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19:
Describe a Monte Carlo $2^{3k}n^{O(1)}$ - time polynomial-space algorithm for the Triangle Packing problem: given a graph $ G $  and a number $ k \in N $, decide whether $ G $ contains
$ k $ disjoint triangles (subgraphs isomorphic to K3).
Hint 10.19 in Page 354: Use a similar approach as in the $2^{k}n^{O(1)}$ -time algorithm for $k$-path from this
chapter (Page 333).
I tried to solve the problem using the hint, but without success unfortunately, there are solutions to the book? I would be happy to get help if it can be solved even without official solutions of the book but it is important to solve it using the hint they brought in order to use the tools learned in the same chapter.
Thanks in advance.


texts: Populating a vector of numbers to expose an error in a function implementation

texts:
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect on specific inputs. In fact I might do this for all vector sizes under a certain size, but I would never enumerate all possible values, just all possible vector sizes.
It occurs to me however that it might be possible to populate the values of the vector such that I can still verify every possible vector under a certain size as long as I make a certain assumption about the implementation of the function under test.
Say I have a function $f : \mathbb{N}^n \to \mathbb{N}$ such that $f(x) = \sum_{i=1}^nc_i\prod_{j=1}^n x_j^{e_{ij}}$ for some $e$ and $c$ such that $e_{ij} \in \{0,1\}$ and $c_i \in \{0, 1\}$. I want to see if this is equal to some known golden function $g$ but I'll have to manually work out $g$ for specific inputs. I belive it to be true that there exists an input $r$ such that $f(r)$ uniquely determines $f$. This makes testing to see if a particularly implementation of $f$ is the one we expect trivially easy.
for $n = 2$ the possible values of $f(3, 7)$ are the following:
0,
1,
x = 3,
y = 7,
xy = 21,
2,
1+x = 4,
1+y = 8,
1+xy = 22,
x+x = 6,
x+y = 10,
x+xy = 24,
xy+xy = 42
So if I make the assumption that a partiuclar function I'm testing has the above from characterized by $c$ and $e$ then I only need one input to fully test an implementation of $f$.
A good heuristic for generating these inputs is to start with the first prime higher than the number of terms you have, and then try successively higher primes for each next input until you work out the few kinks that remain. The intuition is that no two products will be the same because you chose primes and that each unique product will be spaced out by so much eventually that the sums will also all be unique as well.
Is there an algorithm to generate an input to such a function that makes all possible such functions result in unique values? What if we're willing to be probabilistic in some sense such as "the expected output is probably unique for this input"? Are there other forms of functions for which this question has been studied?


texts: If NP is easy on average then does it mean P=NP?

texts:
If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have $NP=RP\implies P=NP$?

This problem asks directly a point with respect to a remark in a paper.

I do not blindly ask if np=rp then is p=np. I ask about a comment in a paper.

I think essentially I am asking is $RP\subseteq Avg-P$?


texts: Why Not To Take B8ZS with encoding 7 digit?

texts: I have a simple question. In signal encoding we have B8ZS (Bipolar with 8 zeros substitutions) technique which encodes every 8 sequencial 0 bits with 000+-0-+ or 000-+0-+ depends on previous voltage level. Can we do this with 7 seven bits like 0+-+0-+- and 0-+-0+-+ in order to decrease number of 0s and to prevent from dc signal? (Can anybody open a data-communication category for this question? I could not because of the reputation thing, thanks)


texts: What is the decidable language in $P/poly$ but not in $P$?

texts: Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$


texts: Algorithm to position samples minimizing error

texts:
We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the x position for these points so the polyline approximates f(x) with low error (not necessarily optimal but if it was, then even better)?

What algorithms are available to solve this problem? What are their trade-offs?

Example: the following two polylines have the same number of points but the second one approximates better the curve.


texts:
I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction.
In fact the reduction build a bipartite graph, the edge $(x_1,c_1)$ exist if the variable $x_1$ is in the clause number 1, the costs on that edge are dependent on the truthfulness of the variable $x_1$, cost 1 if $x_1$ is true and 0 elsewhere. My question :is it permitted in a reduction or should i have the entire graph instance independent from values taken by the variables ?

Thank you all!


texts:
In unification, given a set of equations, a standard problem is to compute a most general unifier (mgu). I am interested in a somewhat reversed problem. Imagine having a set of equations that do not have an mgu, like this one:

x = a
x = b

x here is a variable, whereas a and b are terms. I am interested are there any algorithms that could find a possible replacement for a and b such that the resulting equations have mgu? In the above example, that would be a -> y, b -> y, y being a variable. Lets call this a fix. I am particularly interested in most specific fixes. I could not find anything so far, but this seems like a natural problem, or not?


texts:
I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.

I encountered a sub-problem that requires me to break up sums of numbers which are power of 2, i.e. how to find combinations of these numbers that sum up to a certain value. The sum and the combination size are given. Also only 4 power of 2s can be present in a combination: 2,4,8,16.

Lets suppose I have a sum of 8 and I need to break up into a set of 3 numbers. The result would invariably be [2,2,4].

If I need to break up 20 into 3 power of 2s, I could have [2,2,16] or [4,8,8].

Naturally larger sets will result in many possible combinations.

My aim is to write an algorithm that obtains all possible combinations as efficiently as possible. I'm not looking for the algorithm itself, but some leads into how to partition the number.
What are some properties of power of 2s that I need to use to partition a sum into a possible combination?


texts: is this language regular and why pumping lemma doesn't work?

texts: I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?


texts: Particles-based models - Discrete or Continuous, why?

texts:
I have a theoritical question about particles-based simulator (Reeves,83). I don't know if my question is relevant and I apologize if not.

On each frame, the system generate particles and attribute to it properties and behaviour (speed, velocity, etc), some of them will die (disappear) after X seconds.

Is because the render is genereated on each frame, that we can classify this type of simulation as discrete ? if yes, I think that performant simulators that seems to produce "continuous" simulation, are produced things like video so 24-27 frames/s.
Is it a question of frame, or a number of frame ?

Thanks a lot


texts:
I have a problem with an exercise, I have to analyze the following
For-Loops

Then I have to write down the explicit notation, my problem is that I don't know how to get the right m.
I tried this
but now I have no idea how to get the m, because I thought that m defines the diffrence between i and j and so I became m = n + 2 but that was wrong.
(This is the form in which it has to be)

I would really appreciate your help thx for your efforts in advance.

Kind Regards


texts: Can Deterministic Context free Grammars be ambiguous?

texts:
I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars.

But I wanted to know if there can be an instance that deterministic context free grammar is ambiguous.


texts: What is the grammar for language $L={a^nb^m : n \neq m-1}$?

texts:
What is the grammar for language $L = \{ a^nb^m : n\neq m-1\}$?

I only know I have to write grammar for both $ n<m-1 $ and $ n>m-1 $, so this is what I wrote:

for n<m-1
S->Abb
A->aAb|lambda

for n>m-1
S->aaA
A->aAb|lambda

Yet I can not mix them and get a correct grammer for it.


texts:
Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$.
Hint:  Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a padding argument.

I proved that $L'=\{x\#1^{|x|^{\log|x|}}\mid x\in L\}$ is in $\mathsf{P}$ but I'm not sure how to conclude that $L\in\mathsf{P}$, or how do I get the contradiction to the assumption.


texts: Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?

texts:
I have having trouble with the following question:

  Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.


texts: Uniform Sampling on Intersection of Faces of Simplices

texts:
I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints
$$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{0} \ \ and \ \ \sum w_i = 1,$$
I want to sample $\vec{w}$ uniformly. $A$'s dimension is about $100 \times 10000$. A concrete example will be:
$$A = \begin{bmatrix}
    1 & 1 & 1 \\
    0 & 1 & 2
\end{bmatrix}, \
b=\begin{bmatrix}
    1  \\
    0.7
\end{bmatrix}$$,
sample $\vec{w}$ uniformly from $Aw=b$ subject to $\vec{w} \geq \vec{0}$ and $\sum w_i = 1$ (This makes the sampling space bounded). Below is a graphical representation of the problem -- to sample uniformly from the red intersection line.

I am well aware that rejection-sampling and MCMC sampling can theoretically solve this problem. However, I have already implemented both approaches in programming, and neither of these two methods performs well enough. This is because the dimension of my sampling space usually goes up to 10000, and rejection sampling simply throws away too many points and MCMC is taking forever to converge. Therefore, I'm desperate to try new methods. Many thanks in advance!! (please do not provide answers using rejection sampling; methods that already have open-source programming implementations are favored)


texts: Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

texts:
Assuming $\Sigma  = \{  0, 1\}$..

Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$?

So it is the same as showing that $\overline{L}\in NP$, but I'm not really sure on how to prove this.

Does anyone have an idea?


texts: Symbolic Math Systems As Speculative Optimization For Numerical Software?

texts:
Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations?

Real world numerical applications of mathematical software frequently must take days to complete a computation while leaving vast computational resources idle due to the complexities of problem partitioning.  Worse, manual attempts at symbolic math to speed this up can waste specialized human labor if symbolic solutions fail after long periods of time.

Automatically partitioning between symbolic and numeric computation seems straight-forward. For instance, entering expressions including integrals, differentials, etc. could promptly launch the speculative search for symbolic solutions on some cores but not assume they will be found prior to the demand for numeric answers.  If the numeric computation takes longer than the symbolic optimization, the symbolic optimization would be incorporated into other cores to see if they can beat the unoptimized numeric computation.


texts: Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

texts:
Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

So far, this is the solution that I have been able to come up with, though I am not sure how accurate it is:

$$\begin{align*}
S &\to aSa \mid X \\
X &\to bX \mid a \mid \varepsilon
\end{align*}$$

I worked this out from outside first, which gives me the first and last a's and then used the second rule to get the b's or a's after.

The reason I came up with that answer, I thought the grammer need to start and end with "a" and then have b's in between those a's.

So for each letter with different power we need to have a rule? That is, for $a^i$ we need a rule and for the $n$ power we need another one ?


texts: Why do I only need to reduce from one problem in NP to prove NP-Hardness?

texts:
Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ?
Consider for instance the following situation:

Here, I have my set NP of problems, where problems $A$ and $B$ were proved to be NP-Complete through direct proof, and problems $C$, $D$, $E$, and $Q'$ were proved to be NP-Complete through reduction. I reduce from $Q'$ to $Q$, then later show $Q$ is in $P$. I agree that I then would be able to claim that problems $Q'$ and $B'$ can be claimed to also be in $P$, since we can just reduce them to $Q$. However, why can we make the same claims about $C$, $D$ and $E$ ? there is no (known) way of reducing from them to $Q$, we merely know that they may be "at least as hard" as the unlabeled problem and problem $A$, but can't it be possible that they are harder?
This is why intuitively, it seems to me like we should be showing ways to reduce from all "leaf" problems in NP, to show that $Q$ is also NP-Hard, even if I am told that this is not needed.


texts:
I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book.

Please give a semi-detailed proof of this. I have found a paper which has this proof(by Chandra, Kozen et al.) but found it too hard to understand.


texts: if $\delta(q, a) = q$ for all symbols $a$, show that $\delta^* (q, w) = q$ is true for all strings $w$

texts:
Let $A$ be a DFA and $q$ a particular state of $A$, such that
  $\delta(q, a) = q$ for all input symbols $a$. Show by induction on the
  length of input that for all strings $w$, $\delta^* (q, w) = q$.

I'm completely new to the subject. But this is what I have done. Can someone please tell me if this is the correct solution?

For the basis of the induction $|w|=1$, $\delta (q,a)=a$ is already correct by definition.

Let $n = |w|$, the number of symbols in the string $w$. Let $\delta^*(q,w)=q$ be true for some $n \gt 1$ (hypothesis of induction). Now I should prove it for $n+1$ using the hypothesis of induction. Let $z=wa$.

$$
\delta^*(q,z) = \delta^*(q,wa)
$$

It follows that:
$$
\delta^*(q,wa) = \delta^*(\delta^*(q,w),a)
$$

From the hypothesis, I know that $\delta^*(q,w)=q$, so if I substitute this in the above equation:

$$
\delta^*(q,a)
$$

and this is equal to $q$ according to the base case. So, I conclude that $\delta^*(q,w)=q$ is true for every $n$.

Is the above so-called "solution" correct?


texts: Data structure choice for a query-update-delete problem

texts:
Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive.

At any given point, there are two possible actions:

1) Query-Delete: Given a value s as query, find all such keys in the set that have have the (globally) minimum p and satisfy (q >= s), and delete these keys.

2) Insert: Add a new key k' = (u, v) to the set.

I was wondering what would be the best data structure to represent the above.

My first approach is to simply sort the original set in a linked list (or array) and return the appropriate tuples when queried, and if inserted, use linear search to find the position, but the worst-case insertion then becomes O(n), while query-deletion involves checking the first element, and has the complexity O(number of distinct q values).

A second approach is to use a red-black tree with the p values as its key, storing (p, q, r) in each node, where r is the biggest q value found at that level or below in the tree.

For example, given a set (10, 4), (20, 2), (30, 2), (40, 3) the tree looks like:

        (20, 2, 4)
       /          \
 (10, 4, 4)        (30, 2, 3)
                     \
                      (40, 3, 3)

where each node is of the form (p, q, r).

This approach has the benefit of being able to early exit during the query search if (r < s) in the node. Insertion remains O(log n) like in red-black trees, but may face problems with sets of the form {(p, q1), (p, q2), ...}.

Could anyone please suggest modifications or propose a better approach? Thanks.


texts: Partitioning planar graphs without minimizing edge cuts

texts:
I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions:

Creates balanced (within some margin) $k$ partitions of $V$ according to node weight.
All partitions have to be connected.
It cannot minimize communication volume, or edge cuts.

My graphs are planar, all vertex weights are positive integers, and the reason that I want #3 is that I need to be able to generate $n$ distinct partitions from the graph that I have. I have found that if I use GPMetis, no matter what options and seed I pass it (currently using -seed=40 -ctype=rm -iptype=random -ptype=kway). The options have an impact only if I scale up the number of vertexes (on my graphs that have less than 100 nodes, it always gives the same answer).

Are there algorithms that exist to create balanced partitions by vertex weight that meet these conditions? It doesn't need to ignore edge counts/weight entirely, so long as I can still make the result different via some seed. Willing to take either a research paper, or fully functional code.

As background:

I know that a vertex separator can be found in polynomial time for planar graphs, but I need all my vertices.
There are several edge cut algorithms that also run in near polynomial time, but these have the problem listed above of not being able to inject sufficient randomness.


texts: How to identify the z-ordering of objects in a computer vision or image processing scene?

texts:
Given that there is an image with objects in it, is there any method in computer vision to determine the z-ordering of objects. For an ideal image of three circles overlapping, I can determine that it is three circles overlapping and determine which is the closes to me in this image.

Therefore for any given image, is there any method in computer vision to determine the z-ordering of segmented parts?

To clarify, I don't mean for only clean geometric objects such as circles, I mean for any objects which have been segmented.

I have a particular application of this in mind, I want to be able to reverse engineer images into layers, then I can pass the image split into layers into photoshop to speed up some of what we do practically with photoshop which is splitting images into layers. Also layers which are partially hidden can then be filled in automatically by the computer, layers can be moved on top of each other.


texts: How will I calculate the time and space complexity for this pyramid algo?

texts:
This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345":

    1
   121
  12321
 1234321
123454321

Code:

void buildPyramids(string str) {
    size_t len = str.length();

    size_t i, j, k, m;

    for(m=0; m<len; m++) {
        for(i=len-m-1; i > 0; i--) {
            cout << " ";
        }
        for(j=0; j<=m; j++) {
            cout << str[j];
        }
        for(k=1; k<j; k++) {
            cout << str[j-k-1];
        }
        cout << endl;
    }
}

What's the correct way to calculate the space and time complexity for the same?

Could you also guide me to some resources for a deeper understanding of the same?


texts: Comparison of Swarm Intelligence Algorithms with Constraint Violations

texts:
I want to compare swarm intelligence algorithms in a optimisation problem. As far as I understand, a typical approach is to perform several runs of each algorithm (say 30 independent runs, with different random number generator seeds)  and compute the average performance of best-of-run individual for each algorithm. Then one can conduct a statistical test, in order to compare the averages of the two variables (say m1 and m2, the average performance of best-of-run individual for algorithms 1 and 2).

Now imagine that in our optimisation problem we are only considering one objective function. What if this function is constrained and, for one run (or possibly more) of one algorithm the best solution it can find violates the function's constraints. If, in a given run, the algorithm is unable to compute a solution that lies within the problem's constraints how should I proceed in order to compare the performance of this algorithm with another one? Initially, I was considering assigning a NaN or a value like MAX_INT to all solutions that violate the problem's constraints, but if I do that then I won't be able to compute the algorithm's average performance nor perform the statistical tests.

What should I do in such a scenario? Do people tend to just perform more runs until they get 30 best-of-run solutions that do not violate the problem's constraints? How can I compare the performance of my two algorithms experimentally?


texts: Batching multiple nearest surface queries: Is it faster? Are there better algorithms?

texts:
I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out there on speeding up these queries. My gut tells me that partitioning the set of query points in a voxel grid or something, and doing them in batches could be a speedup, but I can't quite see how I could efficiently use that. Also I'm not sure if the time cost of partitioning would balance the search speedup. Is running N independent queries really the best way?
I found that there are papers and research for the all-knn algorithm, but that's for searching within a single set. And then, those speedups take advantage of the previously computed neighbors or structure within the single set, so I can't use them. It feels close though.
Any help is appreciated.


texts: Can a TM recognize whether another TM recognizes a non-empty language?

texts:
Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$
Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?

My attempt:

I wanted to study reachability the same way one does with DFA/NFA. However although a transition might be defined between $q_i$ and $q_j$ for $ x \in \Gamma  $ is no guarantee that the configuration is possible.


texts:
I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before.

$L = \{w\in\{a,b\}^{*} : 3\#_{a}(w) \leq 5\#_{b}(w) \leq 4\#_{a}(w)\}$

Could I get some pointers on how to tackle such a problem like this so I can be more familiar with the approaches here.


texts: Solving a maze with DFS vs "wall following"

texts:
Consider a problem where a "robot cleaner" is placed on a room modeled as a grid. Each cell in the grid can be empty or blocked and all accessible cells are connected, meaning, all empty cells will be accessible by the robot regardless of its starting position.

We are told that the robot cleaner can only take one of four actions:

move forward
turn left (90 degrees, without moving)
turn right (90 degrees, without moving)
clean the current cell in the grid

We are asked to design an algorithm for the robot to clean the entire room.

My question is: Can this problem be framed as a maze solving problem? I mention this because a common strategy (if the maze is simply connected) for maze solving is to be a "wall follower" (e.g. always try right, or always try left), and I wonder if wall following would work here.

More generally, why would "wall following" be a good strategy for either problem? Isn't it enough to do DFS (with backtracking) even if we pick an arbitrary order of directions that are "left to explore" from each grid position? (or explore directions at a given position in any order?)


texts: How to fill cell-network partition matrix of a function?

texts:
I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 1), but I can't make it past the first paragraph:

Consider the $x_l … x_{k - 1} | x_k$ partition matrix of a function $f(
x_1, x_2, …, x_k)$, as shown in Fig. 1, where $C_0$ and $C_1$
represent the $x_k = 0$ and $x_k = 1$ columns, respectively. Let $0$
and $1$ represent the columns of all 0's and all 1's, respectively.
Let $X$ denote a column with at least one 0 and at least one 1,
and $\overline{X}$ its complement. The concatenation of two columns
will represent a complete partition matrix. Thus, for example,
$01$ represents $f(x_1, x_2, …, x_k) = x_k$ and $XX$ represents a
function independent of $x_k$, but dependent on at least one of
the remaining variables.

I'm trying to build something like a Karnaugh map, but the result I'm getting doesn't make sense.

For example, here's what I made from $f = x_1 \times x_2 \times x_3$ (with digital logic "&" for boolean times):

The first column ($C_0$) I would call $0$, from the author's definition, but the second column ($C_1$) doesn't seem to be a $0$, $1$, or $X$. What am I doing wrong?


texts: Finding a minimal subset of strings whose bitwise OR is the all ones string

texts: Consider we're given a set $S\subset \{0,1\}^n$ and we want to find a minimal subset $A \subset S$ under the property that if we bitwise OR all of the strings in $A$ we get the all ones string $1^n$. I have been having trouble finding a polynomial time algorithm for this or finding evidence that one doesn't exist (e.g.- by showing this problem to be NP-Complete). Does anyone have any ideas or references which may help answer my question?


texts:
A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the constraints $g_i(x) \leq 0$ are relaxed, and we could instead solve the problem of
$\min_{x,d} d$
$g_i(x) -d \leq 0, \forall i$
However, I don't really understand the approach to how this is done here (which corresponds to the above mentioned problem when $x$ is two dimensional), in the function linearProgram3, line 518:
https://github.com/snape/RVO2/blob/main/src/Agent.cpp
The method there seems to directly convert the 3d problem to a 2d one, using the lines where $d$ is the same for both lines. A quick summary of my understanding of what happens:
Suppose we have three oriented lines that form a triangle and assume the "normals" (suppose they are pointing in the direction of feasibility, not outside of it) point outside and so the problem is infeasible.
The algorithm would see that once it adds the constraint of $l_3$, the problem is infeasible, and use a different approach. It does the following:
For $l_1$ and $l_2$ we create lines $\tilde{l_1}, \tilde{l_2}$ where $\tilde{l_1}$ passes through the intersection point of $l_1$ and $l_3$, and it bisects the angle between $l_1$ and $l_3$. Similarly for $l_2$.
Then,
$\min_{x,d} d$, where $\tilde{g(l_1)}(x) \leq 0$, $\tilde{g(l_2)}(x) \leq 0$
is solved. In the inequality above, $\tilde{g(l_1)}(x)$ corresponds to the constraint of $x$ being on the "correct" side of $\tilde{l_1}$.
I can intuitively see that this approach will work, but I'm not able to justify it formally. Would someone please explain why it will work, or perhaps refer me to a text that would explain this technique?


texts: Can we represent all computer programs as graphs?

texts:
I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an abstract syntax graph.

It occured to me that perhaps any computer program can be represented as one of these graphs + evaluation semantics attached to it.  I'm curious if anyone knows if this is universally true for a turing machine (I assume you can get a potentially infinite graph, but this is math so that's OK).  I've been pondering on it and a lot of things like strong type systems and such fit well in this abstraction (they impose structural constraints on the graph).  You might even be able to consider the type system its own program and represent that as a different graph + evaluation semantics operating on the program graph...

Just curious if this is a known equivalence or not.


texts:
a 2  sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat instance?? and optimization problem is that: find the minimum number of variables to remove to make the 2  sat instance satisfiable. I want to use reduction to show this problem is np-hard but I don't know which np-hard problem should be used. I appreciate if anyone could help me by the reduction or introduce me a reference (I searched but maybe I don't know the name of problem exactly)

please notice that this problem is different from maximum 2-sat, in this problem each clause can even contain one literal and we reduce 3-sat to show it is np-hard.


texts:
I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4.

However, I would like to know if there is a similar result in the case for the number of clauses is small. For example, for < 20 clauses?

For example, if you had 8 clauses and you took a clause/variable ratio of 4, then you would have 2 variables, but this would be quite trivial to solve.

Do there exist heuristics for generating difficult small instances, or is it a simple matter of testing to see what works?


texts: NFA: each block of five consecutive characters contains at least two 0's

texts: How can I find an NFA for such a language, considering the alphabet to be {0, 1}. I've tried deriving it from the DFA (@Steven) and the regular expression (@Yuval Filmus), but no luck.


texts: What's the difference between the rank and the degree of a type function?

texts:
1 Context

Near pg. 184 of Lambda Calculus and Combinators, the author is discussing the theory of dependent types. In particular, we are extending the lambda calculus to look at terms of form

$$
\Pi x : \sigma . \tau (x)
$$

Now terms of this form denote type functions with degree and ranks, unless I am mistaken.

2 Textbook Passage on Degrees vs. Ranks

Here is what the textbook states:

  The definition assumes that we are given a set (possibly infinite) of
  atomic type constants, $\theta^n_i$, each with a degree $n$. Each atomic type constant with degree $n$ will represent a type function
  intended to take $n$ arguments, the value of which is a type.

and then later:

  Definition 13.7 (Type functions and types) Type functions of given degrees and ranks are defined in terms of proper type
  functions, which are defined as follows.

  An atomic type constant of degree $n$ is an atomic proper type
  function of degree $n$ and rank $0$.
  If $\sigma$ is a proper type function of degree $m > 0$ and rank
  $k$ and $M$ is any term, then $\sigma M$ is a proper type function of
  degree $m - 1$ and rank $k$.
  If $\sigma$ is a proper type function of degree $m$ and rank $k$,
  then $\lambda x . \sigma$ is a proper type function of degree $m+1$
  and rank $k$.
  If $\sigma$ and $\tau$ are proper type functions of degree $0$ and
  ranks $k$ and $l$ respectively, and if $x \notin FV(\sigma)$, then
  $(\Pi x : \sigma . \tau)$ is a proper type function of degree $0$ and
  rank $1 + k + l$.

  A type function of degree $m$ represents a function of $m$ arguments
  which accepts types as inputs and produces types as outputs. THe rank
  of a type function measures the number of occurrences of $\Pi$ in the
  normal form of the term representing it.

3 Question

Question: I am totally confused between the notion of a type function's degree versus its rank.

The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?


texts: How to prove that a polynomial of degree n is θ(x^n)

texts: How can I prove that if $T(x)$ is a polynomial of degree $n$ then $T(x) = \Theta(x^n)$.


texts:
I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well).

I have two sets of points in the plane:
 $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and $Q=\left\{ q_{1},q_{2},\dots,q_{M}\right\} $.

Each point has a value/weight, i.e there is a function $v:P\cup Q\rightarrow\mathbb{R}$ which assigns a weight/value to each point.

I want to find a pair of points, one in $P$ and one in $Q$, which maximizes the function $f:P\times Q\rightarrow \mathbb{R} $,$
f\left(p,q\right)=v\left(p\right)+v\left(q\right)-\alpha\cdot d\left(p,q\right)
$

where $d$ is the Manhattan distance between the points.
So on one hand I want points with a high value, on the other hand I want them to be close together. $\alpha$ is just a constant which I will determine according to the specific application and it assigns a "relative importance" of the distance relative to the weights.

The choice for Manhattan distance is because I want to use this with actual geographical points which are connected by actual road networks.

Does anyone have a suggestion how to solve this without an exhaustive search over all pairs? even an approximation or heuristic suggestion would be helpful.

Thank you!


texts: How is a compiler related to the runtime system?

texts:
A quick search on the role of compiler brings up the following:

  A compiler is a special program that processes statements written in a
  particular programming language and turns them into machine language
  or "code" that a computer's processor uses.

However, I also read that every language needs to have a target runtime system and programs written in that language execute in the context of the runtime system.

Adding up the two, it appears that a compiler converts programs into bits understandable by the runtime system and the runtime system acts as the agent interpreting the bits, translating them to the processor intructions. Is this correct? If not, how else are compiler and runtime system related?

And if the above is correct, it would imply the following:

two executables compiled from programs with identical logic written
in different languages would not be identical
with people typically installing several programs from disparate sources, an average machine would have to have dozens of runtimes which doesn't seem to be the case.

What am I missing here?


texts: What do we know about covering the edges of a graph by disjoint paths?

texts:
Two related things I have heard/know of are,

(1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?)

(2) That its NP-complete to decide if $k$ vertex disjoint paths can cover all the vertices of a graph.

Are there edge analogues of these results?
Does using the dual graph translate these results into their edge versions?
If the line graph is a edge-to-vertex-dual then is there a vertex-to-edge-dual? (which will may be convert the question of finding a vertex cover by k vertex disjoint paths into a question of finding an edge cover by $k$ edge disjoint paths?)


texts: What constitutes one operation/cycle/move in the RAM model?

texts: I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, it is relevant how much time the program needs to spend on one action. Say you want to read one integer symbol from the read tape, add it to an integer from a memory register, and then squish the result into the write tape cell, and then move the read head one to the right and the write head one to the left. How much time or how many moves did I just waste?


texts:
Help would be much appreciated.

"Receive a number and reorder it from the largest to the smallest.
Input: 13252
Output: 53221
Cant use arrays...
Only while, for, if/else  ...

any idea? i'm clueless.
Thanks for the help.


texts:
This question started with a quiz question from my university:
Consider a big-endian computer system with an addressable cell size of one byte. The values in memory cells 372 to 375 are shown in the table below. What 16-bit two's complement value (expressed as a decimal number) is stored at address 374?

Address    Value
372        0xC5
372        0x5E
374        0x7F
375        0x23

One thing I'm not clear about is what exactly does "addressable cell size of one byte" mean?


texts: How to find the optimal assignment using the Kuhn-Munkres algorithm?

texts:
I managed to get through the Wikipedia article until the last step and I have implemented an algorithm that can reach the optimum.
Unfortunately the article does not say anything about how can I make the optimal assignment after completing the last step.
What is the best way to make such an assignment?


texts: An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

texts:
Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane of the polygon, and I know the order (in a right-hand sense with respect to the normal) in which the vertices go around the polygon.

I also have a polyhedron, which is in general non-convex, and the surface of which is made of triangles. It is a triangle mesh like the one shown here. It describes a completely enclosed volume (no holes in the surface). I know the coordinates of all the vertices of all the triangles that make up the polyhedron. For a given vertex, I know the list of which triangles it is a vertex of.

One other thing I know, which may or may not be useful, is that the polygon lies "in the vicinity of" a particular pair of vertices of the polyhedron, say the ones with indices $i$ and $j$. So if there were to be some kind of a search of the surface of the polyhedron, that would be the place to start.

My task is to find the area of the intersection between the polygon and the polyhedron. I believe this is a well-defined quantity. I need an algorithm to calculate this, hopefully efficiently but at this point I'll take anything.

My thoughts:

I can classify each polygon vertex as either inside or outside the polyhedron. I've written a ray-casting algorithm that computes this fairly accurately and efficiently. That means that each edge of the polygon can be classified as either "both vertices inside", "both vertices outside", or "one in, one out." I can calculate the point of intersection between a given polygon edge and the polyhedron by checking a bunch of nearby triangles.

But that's not enough. For instance, just because both vertices of an edge are inside doesn't mean the whole edge is inside. A "finger" of the polyhedron might intersect an edge without touching either of its endpoints. Furthermore, the polyhedron might intersect the polygon in such a way that it doesn't touch any of the edges at all. Clearly, one must also calculate the intersections between the triangles' edges and the polygon as well.

It gets a bit too complicated for me at that point, and I'm wondering if there is some established algorithm for this?

Perhaps something like: Project the polyhedron onto the plane containing the polygon and then... I don't know.


texts: If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive

texts:
The theorem says: If $R(x,y)$ is a recursive relation, then  there exists $y\leq2$ such that $R(x,y)$ is recursive.

Here is my attempt of proof:

Since $R(x,y)$ is recursive, we can construct a partial recursive function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ be such that $f(x,y)=1$ if $(x,y)\in R$ and $f(x,y)=0$ if $(x,y)\notin R$.

Let $y=2$. Then either $(x,y)\in R$ or $(x,y)\notin R$. So we can just construct a partial recursive function $f'$ that fixes $y=2$ and takes an input $x\in\mathbb{N}$ and runs $f$ on $(x,2)$.

Is this enough? Can I generalize this for any values of $y$ or does this only apply for when $y\leq 2$?


texts:
I shall call this the "Curtain Hook" problem.

Please excuse my lack of formal maths notation as it has been over 20 years since I have needed it.

A standard pencil pleat curtain has L number of loops on the back (evenly spaced along the width) with which to hang the curtain.  The curtain pole will come with H number of hoops to hang the curtain upon.
The problem is how to distribute - with as uniform as possible gaps between - the hooks across the loops.

For example, if I have 15 hooks (per curtain) and each curtain has 38 loops where should I hang the 15 hooks?

By hand I came up with:
HoHooHooHooHoHooHooHoHooHooHoHooHooHoH
Which is not evenly spaced. (H being a hook, o being an unused loop)

Is there an evenly balanced solution for this combination?
Is there an algorithm that can be used to describe where to place the hooks evenly?

Ps. Not homework, just someone with a curious analytical mind who had to put up some curtains recently.  I was thinking of creating a web page to help others if a general solution/algorithm could be found.

Thanks

Craig


texts: Function minimization as genetic algorithm stop condition

texts:
I have implemented genetic algorithm for a problem where I have an objective function which I need to minimize:

Cost = ax + by + cz -> min

The genetic algorithm should have found the optimal solution if objective function is satisfied.

The function will never reach 0 or below, so I just need to minimize it. Now, since there are no objective values to be reached, how do I know whether the objective function is satisfied or not?


texts: What usage is the delta defined in the polynomial hierarchy?

texts:
At the Wikipedia page, the polynomial hierarchy also defines the following:

$\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$

However, the only usage of this anywhere else on the page is the following set of inclusions:

$\Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Pi_{i+1}^P$.

What usage does this $\Delta_i^P$ class have?


texts: Hardness of approximation for Disjoint Group Steiner Tree

texts:
Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group?

The (intuitive) reduction from Set-Cover seems to fail in that case, and it also feels easier. It seems to me you could solve this if the underlying graph is a tree in polynomial time. Is this case still NP-hard to approximate within a constant factor for general graphs?

I've searched for partition/non overlapping/disjoint Group Steiner Tree etc. But I can't find anything, so I imagine this particular variant might have a specific name.

Group Steiner Tree is the following problem:

Instance: a weighted graph $G=(V,E)$, a collection of vertex sets (groups) $S_1,...,S_n \subseteq V$.
Find: a minimum-cost connected subgraph of $G$ that contains at least one vertex of every group $S_i$.

What I am interested in is the special case where there is some set $W \subseteq V$ such that $S_1 \bigcup \cdots \bigcup S_n = W$ and $S_i \bigcap S_j = \emptyset$ for all $i\neq j$.


texts: In the book, Algorithm Design Manual by Steven S. Skiena, he states "Becoming familiar with many different algorithmic graph problems is more important than understanding the details of particular graph algorithms." Unfortunately, I don't quite understand this phrase, as this is my first experience with Algorithm Designs. Can anyone explain the difference between the two above statements and use a real-world example where this would be true?


texts: Hint(s) please: Maximum Subarray O(n) solution CLRS Exercise 4.1-5

texts:
I've been stuck on this problem for some time, and I don't want to just look at an answer. I'd like a hint(s) so that I can get myself thinking in the right direction so that I might gain more insight into solving similar types of algorithm problems. This exercise is actually from CLRS on the section on Divide-and-Conquer algorithms, soon after it introduced what recursion is.

I figured out the pseudocode for (easier) then coded up an n^2-time solution (though I thought it should be n(n-1)/2-time since I thought there were exactly n Choose 2 possible subarrays, but I guess that's a different issue), and I understand the provided O(nlogn) recursive solution.

Here's the problem-statement from CLRS 4.1-5:

  Use the following ideas to develop a nonrecursive, linear-time
  algorithm for the maximum subarray problem. Start at the left end of
  the array, and progress toward the right, keeping track of the maximum
  subarray seen so far. Knowing a maximum subarray of A[1..j], extend
  the answer to find a maximum subarray ending at index j+1 by using the
  following observation: a maximum subarray of A[1..j+1] is either a
  maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1 <= i
  <= j+1. Determine a maximum subarray of the form A[i..j+1] in constant
  time based on knowing a maximum subarray ending at index j.

Also, of course, the input is A[1..n].

Ok, so I think I understand why the hint makes sense by supposing not then choosing a counter-example (i.e., the following array: [-|+|+|-|neg_1|anything|neg_2|anything|anything] where A[-] represents some non-positive number and A[+] represents some positive number, and A[neg_1] and A[neg_2] are negative; suppose A[neg_1+1..neg_1+1] is a current maximum subarray up till that index, then we find that |A[neg_2]| > A[1..neg_1+1], but A[neg_2+1] > |A[neg_2]| so then the current maximum subarray is A[1..neg_2+1] up till that index. This example shows why the hint makes sense, and it also finds a fault in my attempted O(n)-time solution):

Inside a loop from 1 to n:

we call the maximum-sum interval "interval"
we call the soonest negative number after the max-sum interval "neg"
If sum_from_neg > neg, take {interval[1], j+1} as "interval"
Otherwise, if sum_from_neg > max_sum take that interval (A[neg+1..j+1]).

This idea doesn't quite work, as I tried to illustrate with my example array from above.

Edit: @ryan's comment (the first comment to this post) didn't really help me much. Anybody have other hints?


texts: What is the fastest algorithm for multiplication of two n-digit numbers?

texts:
I want to know which algorithm is fastest for multiplication of two n-digit numbers?
Space complexity can be relaxed here!


texts: Reducing Zero-One Integer Linear Programming problem to SAT

texts:
I want to find a reduction from Zero-One Integer Linear Programming problem to Boolean Satisfiability problem (SAT), that is, to find a polynomial-time transformation $T$, such that:
$$IP \leq_P SAT$$
$$IP(in_{IP}) = 1 \iff SAT(T(in_{IP})) = 1$$
where $in_{IP}$ is an input for the IP problem and $T(in_{IP}) = in_{SAT}$ is a boolean formula (input for the SAT problem).

First, I have considered a particular case for IP, where
$$x_1 +x_2 + \cdots +x_n \leq p$$
$$x_i = 0 \ \text{or} \ x_i = 1, \ \forall i =1..n, \ \forall p \geq0 $$
Translated into boolean language, the transformation will construct a formula where at most p variables must be set to true for the formula to be satisfiable.

Next, I've considered a concrete example, constructing the following ROBDD that allowed me to express the following inequality: $$x_1 + x_2 + x_3 \leq 2$$
$\hskip 2.5in$

where continuous arrow means 1 and dotted arrow means 0. I have also invented the variabiles $x_i\_$ that somehow mirrors the behaviour of $x_i$ sub-component (i.e. swaps routes).

Now, is there a way I can formalize this whole process, that is, express the concept of at most in boolean algebra language? I think this is the key to find the actual transformation.


texts: Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

texts:
Show that the following language $L$ is regular by describing it using a regular expression.
  $$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\} $$

My (apparently incorrect) answer:

Given $w ∈ \{0,1\}^*$ , we can rewrite $L$ as:  $1^n(0\cup1)^*1^n\ for\ n ≥ 0$

However, since the language specifies that the number of leading and trailing $1$s must be the same - this language is not regular.

My justification:

For every regular language, there is (by definition) a finite automaton that accepts that language
The given language $L$ requires an equivalent count of leading and trailing $1$s
Finite automata are not capable of maintaining a count.

Since no finite automata can accept the language $L$, $L$ is not regular.

Can anyone explain to me why this language is regular?  I'm completely stumped.  I can see that it could be pumped using the Pumping Lemma (thereby proving regularity), but my brain just refuses to recognize that an FSM could accept this language.


texts:
I've been using kernel ridge regression. My problem requires predicting some values which I know to be integers. By rounding the results to the nearest decimal, I get excellent results.

However, If there's potential for more improvement - I'd like to try it!

I recalled that the $l_1$ penalty usually results in fewer small errors (possibly at the expense of large errors becoming larger). That is:
$$ \min_w \lVert Xw-y\rVert_1 +\frac 1 2w^Tw$$

Might have fewer small errors (or smaller small errors).

However, aside from the lack of a closed-form solution for this problem, I'm actually looking for more small errors, at the expense of large ones, since I can round them off and hopefully get something better.

I figured taking a higher power for the error could do what I want, but then I'd lose the closed-form solution. One of the problems would be that the problem will no longer be quadratic, which means no closed-form minimum.

I can't see a way to get what I want, but I'm hoping there might be one.

A quick overview of Ridge regression (just in case):
Ridge regression is a regularized least-squares problem:
$$ min_w \frac 1 2 \lVert Xw-y\rVert ^2_2 + \frac 1 2 w^TQw $$
where $X$ is a matrix, with each line representing a different sample, $y$ is a vector of desired values, and $Q$ is a symmetric positive definite matrix.

Deriving by $w$ yields $$X^T Xw-X^Ty  +Qw =0$$
This yields $$ w= (X^TX+Q)^{-1}X^Ty$$
As a closed-form solution (Since $Q$ is positive definite, so is $(X^TX+Q)$, meaning it is invertible).


texts: Why is the vulnerable time in pure aloha twice the frame time?

texts:
The time required to send a frame is called frame time.
Vulnerable time is the time during which no transmission should be done to avoid any collision.

My question is what kind of problem will be created if vulnerable time was equal to frame time?


texts: Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

texts:
PATH = {(X,R,S,T) | exists an x in S that is admissible}
Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell.
An x element of X is admissible if it is in T or if there is two elements y z both admissibles, where (x,y,z) is in R.

So, is there any logspace reduction from CVP or HORN-SAT to this problem, so I can prove that PATH is P-Complete?


texts: Does Second chance Page replacement algorithm suffer with Belady's anomaly?

texts:
In Second chance Page replacement algorithm(clock algorithm), if all the Reference bits are set to one, then the algorithm behaves just as FIFO.

Considering this case, can we conclude that Second chance algorithm also suffers from Belady's anomaly?


texts:
One question from the Grokking Algorithms book:

Implement a max([]int) function, returning the biggest element in the array.

Here's my solution in Golang (adapted from the Python solution in the book):

func maxNumber(arr []int) (r int) {
    // base case
    if len(arr) == 2 {
        if arr[0] > arr[1] {
            return arr[0]
        } else {
            return arr[1]
        }
    }

    // recursive case
    subMax := maxNumber(arr[1:])

    if arr[0] > subMax {
        fmt.Println("arr[0] > subMax")
        return arr[0]
    } else {
        fmt.Println("arr[0] < subMax")
        return subMax
    }
}

It works, but I can wrap my head around it. How is the third block called if every time maxNumber(arr[1:]) is called it executes the function again, passing the array with one last element? If so, at some point in time it will hit the first block (base case) and return or the first element or the second.

I know the function works, but I'm missing the how.

Could someone help me around, explain like I'm 5 styles haha

Thanks!


texts: Understanding definition of epsilon closure and finite automata states

texts:
I am going through the book , introduction to compiler design , by Torben Ægidius Mogensen.

It provides the following definition  of an epsilon closure :

Given a set M of NFA states, we deﬁne $\ \epsilon $-closure($\ M $) to be the least (in terms of the subset relation) solution to the set equation $\ \epsilon $-closure($\ M $) =$\ M $ $\ \cup $ {$\ t $|$\ s $ ∈ $\ \epsilon $-closure($\ M $) and $\ s^\epsilon t$∈T}, where T is the set of transitions in the NFA.

Initially , it defined the notion $\ a^b c $ to mean that  a transition from state $\ a $ to $\ b$  takes place when a symbol $\ c $ is encountered .

But in the above definition  $\ s^\epsilon t $ , $\ t$  is an element of the set of transitions , not the set of states .

This has resulted in a bit of confusion as to what exactly does an epsilon closure mean .

One more terminology word-play that wanted to be clear about is , the exact meaning of a sentence of the following sort :

"We extend the set of NFA states  with those  you can reach  from these by using only epsilon transitions ."

But in  a set of NFA states  , the epsilon transition would direct one state to another which would be already included in the set of NFA states. So , how is it possible to extend the same set with the elements already contained in it ?


texts: Stepping through a sequence of grouped logic gates

texts:
I'm performing a simulation of protein-protein interactions. I'm using Python to code logic gates as functions to model protein interactions.
My model is basically a series of groups (g0 to g4) containing logic gates (see image). Initially, I set up a list containing my groups, and then for each group a dict that contains proteins (nodes) with their starting values (their so-called seedValues, which are the starting parameters for the network at $t=0$).

My question is this: is there some way of iterating through my groups (and their logic gate functions), that begins at group 0 (g0 in the image) at t, and that at t=t+1 executes groups g0 and g1 synchronously, then executes the three groups g0, g1 and g2 at t=t+2, and so on until t=m, where m is the number of iterations wanted?

Image notes: A and B are switches (the program is supposed to change them, as a way of studying perturbations), C is a constant (never changed). J is the output (mostly for show). D and F are built that way to oscillate, whenever A = 0.

I've understood that threading might be the solution to my problem, but before I dive into that I'm interested in finding a simpler way of solving this.

Because I don't know how to formulate this in Python, I attach some extremely messy pseudocode:

    #setting starting conditions
    #g is starting group
    #m is max number of iterations
    #t is time
    #u is the number of nodes
    #v is the number of groups

g = m = t = 0
u = x (where x is the number of nodes in the model)
v = y (where y is the number of groups in the model)

#implement node iterator
nodeChecker():
    timeStep():
        t = t + 1
    nodeExecute(p):
        #p is the number of groups to execute over, in the interval 1 <= g <= v (p=1 is group 1, p=2 is group 1 and 2, ...)
        execute all nodes inside selected group(s)
        timeStep()
    printResults():
        print results of execution of nodes at time of execution
        print state of unexecuted groups (minus current group(s)) #print the seedValue states of network before execution
    at time t, execute nodes in g
        nodeExecute(1)
        printResults()
    at time t+1, execute nodes in g and g+1
        nodeExecute(2)
        printResults()
    ...
    at time t = m, execute nodes in group g, g+1 ... g+(u-1)
        nodeExecute(g+(u-1))
        printResults()
    stop execution

Code note: 1 <= g <= v is the interval $1 \leq$ g $\leq$ v. x and y aren't code variables; the notation is supposed to indicate u = $x$ and v = $y$.

My ambition is to output something like:

    t   0   1   2   ... m
node1   0   1   0       1
node2   1   1   0       0
node3   0   0   1       0

Thank you for your time.


texts: Understanding exponential computation by digit recurrence

texts:
I've met in a book the following algorithm that computes the exponential:

Input: $t, n$ ($n$ is the number of steps)

Output: $E_n$

$\begin{array}{l}
\mbox{define $t_0 = 0$ ; $E_0 = 1$} \\
\mbox{build two sequences $t_i$ and $E_i$ as follows} \\
t_{n+1} = t_n + ln(1 + d_n 2^{-n}) \\
E_{n+1} = E_n(1 + d_n 2^{-n}) \\
d_n = \begin{cases}
      1 & \mbox{if $t_n + ln(1 + 2^{-n}) \leq t$} \\
      0 & \mbox{otherwise}
\end{cases}
\end{array}$

It is taken from this book. My question is not theoretical (it resembles the restoring division, or square root, or reciprocal) but implementative. To me it looks like that such algorithm requires a LUT that stores the values of $ln(1 + 2^{-n})$ while the others algorithms i mentioned don't...
Does the algorithm actually requires a LUT to be implemented? or could be somehow exploited the fact that $ln(1 + 2^{-n}) \approx 2^{-n}$?


texts: Color coding to get an FPT algoirthm for $k$ disjoint triangles

texts:
Consider the following problem:
Input: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?
Assume we want to use color coding to develop an FPT Algorithm for that, as done here (starting from slide 60).
The reference material proposes the following method:

Choose a random coloring $V \rightarrow [3k]$
Check if there is a colorful solution where the $3k$ vertices of the $k$ triangles use distinct colors.

For 2. it proposes this, amongst others, this method:
Try every permutation $\pi$ of $[3k]$ and check if there are triangles with colors $(\pi(1), \pi(2), \pi(3)), (\pi(4),\pi(5),\pi(6), \dots)$
I don't understand why we have to check every permutation $\pi$ of the colors. Wouldn't it be enough to just to check each triple of vertices, see if there are a triangle and if so, only count this triangle if it only uses colors we have not seen before? So like so:

For each triple $x,y,z \in V$:

If $x,y,z$ form a triangle and colors ${c(x),c(y),c(z)}$ not in colors_seen_so_far:
2.1 colors_seen_so_far += $\{c(x), c(y), c(z)\}$
2.2 num_triangles += 1

where we initialize colors_seen_so_far = $\emptyset$ and num_triangles = $0$


texts: What does the leading turnstile operator mean?

texts:
I know that different authors use different notation to represent programming language semantics.  As a matter of fact Guy Steele addresses this problem in an interesting video.

I'd like to know if anyone knows whether the leading turnstile operator has a well recognized meaning.  For example I don't understand the leading $\vdash$ operator at the beginning of the denominator of the following:

$$\frac{x:T_1 \vdash t_2:T_2}{\vdash \lambda x:T_1 . t_2 ~:~ T_1 \to T_2}$$

Can someone help me understand?
Thanks.


texts: Formal construction of PDA intersecting a DFA

texts:
Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$
and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$

What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$

I don't understand what the intersection of these two FAs represent, and my only guess at what the 6-tuple is would be something along the lines of: $P'=(Q,\Sigma,\Gamma,\delta,q_0,F)$ such that:

$P=Q_P$ x $Q_D$
$\Sigma = \Sigma$
$\Gamma =..?$
$\delta =..?$
$F =..?$

The only other resource on this site I found that is remotely similar to this question is:
Cartesian construction of PDA and DFA

However, I didn't find the answer to be sufficient.


texts: Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

texts:
I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$.

The following recurrence describes the best-case time complexity of Quicksort:

$$T(n) = \min_{0 \le q \le n-1} \left(T(q) + T(n-q-1) \right) + \Theta(n).$$

But I have difficulty in proving that $T(n) = \Omega(n \log n)$ using the recurrence above.

So how to solve this recurrence?


texts: Proof emptiness for PDA is $\mathcal{O}(n^3)$

texts:
It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is easier.

Do you maybe have a book or paper I should investigate?

EDIT: This looks interesting but a formal proof from a book or paper would be great!


texts: Showing Maximum Independent Set is $NP-hard$

texts:
I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$.
I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that the most straight forward reduction? Is it can also be shown directly from Clique problem?


texts: Isn't every polynomial time problem an NP problem?

texts:
See here. Knapsack problem -- NP-complete despite dynamic programming solution?

The only reason Knapsack problem is NP-complete is because input comes as binary numbers so n is actually 2^n. Since the weight is an axis of the DP array.

Then for every single problem, for example one that requires an O(n) loop through an O(n) sized array, if we consider the array to actually be 2^n bits long or something towards that effect that actually makes sense, aren't all of those problems actually NP-complete?

This seems to me like the original "feeling/intuition" of relatively middling test cases for NP problems not even working, is thrown off because then almost every algorithm ever is NP.


texts:
Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm.
I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual bound is improved at every step.
Can you explain me ? Thanks


texts: How precise to be when describing a Turing machine?

texts:
I'm kind of new to the theory of computation and I was working on this problem:

  We say that a Turing machine $M$ uses $k$ squares of tape for an input string $w$ if and only if there exists a configuration $(q, u\underline{a}v)$ of $M$, such that starting with input $w$, $M$ yields $(q, u\underline{a}v)$ and $|uav| \geq k$.

  Now show that the following problem is solveable: Given a Turing machine $M$, an input string $w$ and a number $k$ does $M$ use $k$ squares of tape with input $w$?

So the solution I came up with is this:

If it is solvable there has to be a Turing machine $M^*$ that decides $$U = \{\ll M\gg\ll w \gg \ll k\gg\ :M\ \text{uses}\ k\ \text{squares of tape with input}\ w\}$$

And I describe such a machine:

$M^*$ writes in it's tape $w$ and starts operating as $M$ would. After each step of $M$, $M^*$ counts the number consecutive squares of tape from the start of the tape until it finds an empty square, and if that number is $\geq k$ it goes into an accept state and halts. If not, it continues its operation as M would. If $M$ halts without having used at least $k$ steps, $M^*$ goes into a reject state. So $M^*$ decides $U$, and thus the problem is solveable.

So my questions are these:

Is my solution correct?, and

Is my description of $M^*$ precise, or say, good enough?


texts:
I have an MxN matrix where each element contains a positive numeric value.

I need to find those elements in the matrix that add up to the "maximum value". The caveat is that each row and column can be used at most once in calculating the total.

I have a brute force algorithm for doing this bit it's ugly. I was wondering if there is a well-known algorithm for accomplishing this.


texts: Formula for returning the size of a circular array

texts:
I've come across a way of implementing a circular array that represents a double ended queue.

Let the circular array have the following instance variables:

int[] array;
int front = 0;
int rear = -1;
int size = 0;
int capacity = x;  // where x is a parameter in the constructor

The operations of the queue are:

dequeue - return array[front], increment front by 1,

enqueue - increment rear by 1, set array[rear] = value.

I have come to the conclusion that it is not possible to get the size of this queue by using the formula (front - rear + 1) % capacity. However, it is said that it's possible to get the size of the array using the same formula if we let the constructor set the capacity by:

BoundedQueue(int capacity) {
    this.capacity = capacity + 1;
}

With this technique the array will never actually get full and the formula for giving the size of the queue should work (it is said).

However I can't figure out how these modifications to the queue would result in the formula returning the correct size of the queue? We're only making the array one size bigger than it actually is, and we're always leaving at least one element unused. Could someone with a better insight explain to me why these modifications will lead to (rear - front + 1) % capacity giving the correct size of the queue?

Thanks in advance!