texts: What operation is the algorithm performing?

texts:
unsigned int input = 0xC116D9B5709FED85 unsigned int output = 0
while (input > 0 )
{
if (( input mod 2) == 1)
{
output += 1
}
input = floor(input / 2)
 }
 return output

I understand how the algorithm is working and using mod to break the input and then counting the number of times input is modded by 2 where it resulted 1. Basically checking if the number is odd. My question in the first place is howcome we can even store a huge hex like the one in question in an unsigned int. Doesn't it exceed the size limit of unsigned int. Secondly, if someone can help me understand the question would help alot.


texts: Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?

texts:
Goldbach's Conjecture says every even integer $>$ $2$ can be expressed as the sum of two primes.

Let's say $N$ is our input and its $10$. Which is an integer > 2 and is not odd.

Algorithm

1.Create list of numbers from $1,to~N$

2.Use prime-testing algorithm for creating a second list of prime numbers

3.Use my 2_sum solver that allows you to use primes twice that sum up to $N$

for j in range(list-of-primes)):
  if N-(list-of-primes[j]) in list-of-primes:
   print('yes')
   break

4.Verify solution efficently

if AKS-primality(N-(list-of-primes[j])):
    if AKS-primality(list-of-primes[j]):
        print('Solution is correct')

5.Output

yes 7 + 3
Solution is correct

Question

If the conjecture is true, then the answer will always be Yes. Does that mean it can't be in $Co-NP$ because the answer is always Yes?


texts: What is the best you can do with a noisy message?

texts:
You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.

In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.

You receive your friend's number, but, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.

What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?

EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?


texts: Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

texts:
In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented.

For its analysis, $T(n)$ is a random variable denoting the time required on an input array $A[p \cdots r]$ of $n$ elements and $X_k$ is an indicator random variable $X_k = I \{ \text{the subarray } A[p \cdots q] \text{ has exactly } k \text{ elements (due to the pivot)} \}$.

It has been claimed that $X_k$ and $T(\max(k-1, n-k))$ are independent (page 187 in the 2nd edition and page 218 in the 3rd edition). However, I find it quite counter-intuitive to understand. How to verify it?


texts: Finding the element that occurs more often than the other

texts:
I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.

Example : $aaaaaabbb$

Here $a>b$.

I have to find an constant time algorithm. Is it possible? The only thing I could come up with was using stack. Push all $a$'s and pop them with $b$. But it takes $O(n)$ operations. Any better approaches? Need a hint (no solution).


texts: Does every procedure have a structural equivalent?

texts:
Suppose I have a basic mathematical function like:

$ f(x) = x^2 + 2$

implemented in typed pseudo-code as:

int f(x) {
  return x*x + 2;
}

If we were to break out this procedure into a step-by-step sequence of actions, we have the following:

f: procedure(int x) returns int:
  set int(temp)         as multiply(x, x);
  set int(temp2)        as add(x, int(2));
  set int(return-value) as temp2;
  return;

However, say we have an equivalent "function" that is not a procedure but is equivalent in functionality (as in, it describes the same mutations, just differently--by structure):

f: function(int x) returns int:
  define(return-value
    add(
      2
      multiply(
        x
        x
      )
    )
  )

This is essentially a mathematical expression written as a tree of operators and  operands, Lisp-style.

It is very clear that the two are equivalent and describe the same mathematical expression: one by procedure, and the other, by structure/definition.

But why is it possible to know the two are equivalent? This mapping between procedure and functional is not always very clear. For even this pair of constructs, they are not equivalent simple "because they are." There must exist some sort of algorithm or procedure to describe how to map a procedure to a function (and, hopefully, not simply enumerating all of the possible values of output from a procedure and comparing it to a function).

Now, suppose we have a procedure as such:

g: procedure(Vector<{int red, int blue, int green}> screen,
             Vector<{int red, int blue, int green}> buffer) returns void:
  for-each {int, int, int} pixel, screen-pixel in buffer, screen:
    copy screen-pixel into pixel;
  return;

Is there a system in which a structural/functional equivalent for $g$ can exist?

Generally; for a set of procedures, does there exist a system in which each procedure has a functional/structural equivalent?

Semantics-wise, we usually know what a string of actions/instructions coupled with a set of data will do. For example, for-each will usually loop over a set of data performing some sort of sequences of instructions for each element in a set. However, the actual implementation of for-each can often differ, which means that proving that several implementations are equivalent in functionality can be non-trivial unless there is a universal way of mapping several procedures to their functional/structural form that all exist in a common system.

Generalized, if every procedure has a structural equivalent that share a common system for description, it may be possible to compare each procedure by value and then prove each are equivalent to a single function or not. This is the justification for why I am asking this question.


texts:
I am currently learning about a CPU's status register and was confused about the difference between the carry flag and the overflow flag. Then I found article [1] which explains it very well, but I stumbled across one paragraph I don't really understand:

  The rules for two's complement detect errors by examining the sign of
  the result.  A negative and positive added together cannot be wrong,
  because the sum is between the addends. Since both of the addends fit
  within the allowable range of numbers, and their sum is between them, it
  must fit as well.  Mixed-sign addition never turns on the overflow flag.

Let's look at 1111 and 0111. Both are valid 4-bit two's component values with a different sign. If I add them, I the carry-flag is turned on because the result of this addition is a 5-bit value.

The author says that errors in twos complement calculations can be found just by looking at the overflow bit. The overflow bit in this example would not get turned on, but in my opinion, this is an error. Why does the author claim this then? Why does the author tell the reader multiple times to ignore the carry bit when doing twos complement calculations?

[1] http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt


texts: Can a Big-Oh time complexity contain more than one variable?

texts:
Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct families. Would it be acceptable to call the complexity of an algorithm $O(n * m)$ or $O(n + m)$ (depending on if we use a naive or an optimized algorithm)?

On a similar vein, let us presume the algorithm we choose actually requires two stages - a setup phase on the first string which allows us to process any number of other strings without incurring that initial cost. Would it be considered appropriate to say it has a $O(n)$ construction followed by any number of $O(m)$ calculations?

Would it be appropriate to just call them $O(n)$ because both calculations are linear?


texts: What is the name of this problem (the dual of the asymmetric k-center problem)

texts:
I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse.

In this problem, the number of warehouses is fixed to $k$, and the goal is minimizing the maximum distance between any city to it's the nearest warehouse.

But, if we want to find a minimum number of centers to meet the demand of having maximum distance from any cities to it's nearest warehouses be fixed (less than) to $t$, what known problem is defined.

Actually, instead of minimizing the distance, I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?


texts:
From Wikipedia,

On Linux systems, vmlinux is a statically linked executable file that contains the Linux kernel

Does that mean vmlinux is a virtual machine that runs Linux? I am really confused.


texts: Optimizing neural network on small training set

texts:
I'm in the process of optimizing my neural network.  I'd like to optimize on a small training set (1000 rows) as opposed to my full training set (100K rows) for speed reasons.

Will the optimal hyper-parameters (i.e. my learning rate, dropout prob, regularization parameter, # of hidden units, etc...) for my small training set also be optimal for my large training set?  In other words, which parameters can I optimize on my small training set, and which must I try to optimize on my large?

Thanks--


texts: Running Floyd-Warshall algorithm on graph with negative cost cycle

texts:
I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, or 1. Suppose that G is strongly connected, with at least one u-v path for every pair u,v of vertices, and that G may have a negative-cost cycle. How large can the final entries A[i,j,n] be, in absolute value (n denotes number of vertices). Choose the smallest number that is guaranteed to be a valid upper bound?
There is the following answers:

+∞
n^2
n - 1
2^n

I have ruled out 3. (n-1) and 1. (+∞) since if a graph has a negative cost cycle, the absolute final value of a path including a negative cycle can be increased further than n-1. The answer also cannot be +∞ since the algorithm stops after a finite number of steps. But I am having trouble between answers 2. and 4. I am more inclined to 4. since I have run some test cases, and final values seemed to comply to an exponential growth. But I cannot find a proof for it.


texts: Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

texts:
I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching.

However, I am using python-graph-tool, which only has max-cardinality max-weight matching, which from what I understand, only finds the max-weight matching of the max-cardinality matchings. However, it may be the case that a truly max-weight matching will not always be a max-cardinality matching (this is especially true on graphs that can have negative edge weights).

Are there any tricks I could use to still get what I need? For example, could I transform my graph $G \to G'$ so that by obtaining a max-card-max-weight matching on $G'$ I could obtain a max-weight matching on $G$? Or will I have to find another algorithm? Are there any good algorithms suited to the task?


texts:
I am aware that the general rectangle packing problem is NP-hard.  I am trying to form an estimate for a version of the problem with constraints.  Consider fitting rectangles of smaller size into a larger rectangle:

I am currently using the second method on the following webpage: https://cgi.csc.liv.ac.uk/~epa/surveyhtml.html : Next-Fit Decreasing Height (NFDH) algorithm and measuring the height of the smaller rectangles along the side and dividing it by the height of the overall rectangle.  The measure that I am finding is not as accurate as I would like.

For my problem specifically, I have the following constraints that differ from the original:

The size of all the boxes is known.
The width will only ever be 2 rectangles wide (there will never be 3 in a row in the width direction).
The rectangles placed together will ideally take up the greatest width possible.
They are always packed such that a rectangle is placed as to take up the least length first.  It will only be rotated to take up more space in the length direction if it is not possible to fit a smaller rectangle beside it.
There will be no more than 30 rectangles added.

I am trying to optimize the following measure:

Estimate = (length of boxes on left side + length of boxes on right side) / (larger box length * 2)

(an average of the length of the boxes along either side)

Is anyone aware of an algorithm or can suggest an algorithmic approach to produce a more accurate estimate?

Thank you!


texts: mapping reduction for every recursive language

texts:
how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$

I can do a reduction $A \leq_m B$?

[EDIT]
My try:

$A$ is decidable therefore it has a turing machine that decides it - $T_A$

For every x, we can check whether $T_A$ accepts x or not, if it accepts then we run over the alphabet and try to find words that are in B.

$B \notin \{ \emptyset , \Sigma^* \}$ therefore there exists words that are in B and words that are not.

if $T_A$ accepts x then we return a word that we found that is in B else if x is not in A then we return a word that is not in B.

This can be done only because $A,B \notin \{ \emptyset , \Sigma^* \}$
And because A and B are decidable


texts: How to determine if a language is deterministic context-free language?

texts:
I have the following question to solve : DCFL means Deterministic Context-Free Language.

Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $f(L)$ is a DCFL. Explain your answers.
(a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)
(b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

I tried to find a counterexample to the problem, however I didn't find anything. So I am thinking that it is deterministic.
I am wondering how I should approach these kind of questions? and how to determine a language is deterministic?


texts: Graph data structures - Why is topological sorting so efficient?

texts:
Topological sorting on a graph seems like an immensely powerful operation:

No matter whether the algorithm ends in success or failure, we obtain an important information about the topology of the graph, i.e. whether it is cyclic or not.
If it ends in failure, we can trivially find the cycle that let the algorithm end in failure, and if it succeeds, we get a working linear ordering on the graph.
And all that is possible in asymptotic linear time! (It's in $\mathcal O (n+m)$; $n,m$ are the vertices and edges of the graph)

While I've seen the proofs and algorithms, and yes, it works, it still baffles me how exactly this is possible.

Looking at another way, a topological sorting a combination of all partial orders   of the graph into a single linear order, which still maintains all the original partial orders. So e.g. even if we're given a set of partial orders, we'd still turn it into a graph, and probably be faster than any alternative.

Why exactly is topological sorting so fast?

I think I've found an answer that suffices for me.
Generally, I'd say the complexity of an algorithm derives from the diversity of possible inputs and the structure properties (constraints) that you have to take care of.

Graphs are insanely diverse, the range of problems they can be applied to alone shows this. And then, a graph has quite a lot of structure as well. So, unless you can somehow abuse its structure, I'd think problems on graphs would be fairly difficult.

However, for the algorithm, we can use the structure property that every acyclic graph has a node with no incoming edges. So, instead of having to care about the whole graph, we just have to observe it locally. As therefore the topology of the graph as whole turns irrelevant, the diversity of graphs (that we care about) greatly diminishes as well, and thus we achieve such a high time efficiency.

I guess what had put me off so much was that the statement that makes all this possible is so simple (and easy to deduce).


texts: I am interested in the applications for set covering. On Wikipedia and this thread, I read that it is used in antivirus programs, random testing in software, and personnel scheduling. Does anyone know where to find or access set covering benchmarks that represent those problems (or any other problem for that matter)? Most set covering benchmarks available online are randomly generated and do not have a strong link with a "real" problem.


texts: Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

texts:
I'm reading through the RMIT course notes on state space search.
Consider a state space $S$, a set of nodes in which we look for an element having a certain property.
A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.

$h_2$ is said to dominate (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.

In Luger '02 I found the explanation:

  This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory.

But I didn't quite get it.


texts: Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

texts:
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.

This question is a simplification of this dynamic programming question:

  It’s Tushar’s birthday today and he has N friends. Friends are
  numbered [0, 1, 2, …., N-1] and i-th friend have a positive strength
  S(i). Today being his birthday, his friends have planned to give him
  birthday bombs (kicks :P). Tushar’s friends know Tushar’s pain bearing
  limit and would hit accordingly. If Tushar’s resistance is denoted by
  R (>=0) then find the lexicographically smallest order of friends to
  kick Tushar so that the cumulative kick strength (sum of the strengths
  of friends who kicks) doesn’t exceed his resistance capacity and total
  no. of kicks hit are maximum. Also note that each friend can kick
  unlimited number of times (If a friend hits x times, his strength will
  be counted x times)

  Example:

  R = 11, S = [6,8,5,4,7] Ans = [0,2]

Clearly, the maximum number of kicks = R/ min_element(S) = 11/4 = 2

So the question reduces to find the lexicographic smallest order of 2 elements in the Array such that the total of N elements is less than or equal to 11.

I am having a tough time thinking about a solution for this. Any leads/ ideas would be appreciated!


texts: $\overline{SAT}$ vs. $UNSAT$, Is it the same?

texts:
I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?


texts: If problem is coNL-complete, is it NL-complete

texts:
We know from Immerman-Szelepcsényi theorem that $coNL=NL$. But, what about:
If problem is $coNL\text{-}complete$, is it $NL\text{-}complete$? And why?


texts: I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?


texts:
I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained:

If I have a multilevel cache, L1/L2/L3/Ln:

1) what decides what level of this hierarchy a block fetched from memory initially gets put in?

2) If I evict a block from L1, does that mean it gets moved to L2 (replacing a block from L2 depending on the replacement policy), and so forth for L2 to L3, and L3 to Ln, until the block evicted from the last level cache gets written to memory?

PS And yes, I have searched for this, so don't downvote assuming I haven't :)

Update

After the answer given below, I went back to the video course and found this.  It seems to suggest that data is initially fetched into the L2 cache, then "fed" to the L1 cache.  This also shows how, without the inclusion bit set, L1 and L2 can become "out of sync".

3) Is this generally what happens in all caches?  IE if I have a 7 layer cache, will the block be fetched into L7, then fed L7->L6, L6->L5 ... and finally L2->L1?  This seems like a lot of work...

4) Except in the situation shown in the linked video (if the caches get "out of sync" then certain data will only be available in one cache even though it started out in both caches), it seems that having the same data in multiple levels of the cache all the time (i.e. when the inclusion bit is set) is a waste; we have to copy it amongst all the levels.  This can't be the case though, so what am I missing?


texts: What can be a Zero Knowledge Proof of a working SAT Algorithm?

texts:
Me and my colleague are exploring new ideas to solve SAT efficiently (i.e. in polynomial time) and it's the case that there is a candidate algorithm.

Unfortunately, neither of us can write scripts well (to test more examples to prove its correctness) or more accurately ... have the sufficient mathematical maturity to write a Research Article about it.

We want to contact some researcher in the field to help us formally describe the algorithm and prove that it works for all inputs (if it holds).

We have tested a few instances of (sat,unsat) and it works (relatively small instaces but not related to DPLL).

In addition, the description of the algorithm matches the concept of nondeterminism (i,e. parallel computations, gussing phase and verification phase,etc.) can be stated / defined precisely.

Given that it is SAT, most reasearchers would consider an attempt to solve it as something invalid, how can we convince someone that this might acutally work ?

What can be a Zero Knowledge Proof (ZKP) for $SAT$ to prove that it works from the tested examples ?

Will a description of some Phases / Techniques used in the algorithm along with the solutions of tested instances suffice ?


texts: Shortest Path in a Directed Acyclic Graph with two types of costs

texts:
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$. I am also given two nodes in $G$, node $s$ and node $t$.
The goal is to find a path from $s$ to $t$ that minimizes the following cost: $$\sum_e w(e) + \max_e \{p(e)\},$$ where the sum and maximum are taken over all edges of the path.
Standard dynamic programming methods show that this problem is solvable in $O(E^2)$ time. Is there a more efficient way to solve it? Ideally, an $O(E\cdot \operatorname{polylog}(E,V))$ algorithm would be nice.

This is the $O(E^2)$ solution I found using dynamic programming, if it'll help.
First, order all costs $p(e)$ in an ascending order. This takes $O(E\log(E))$ time.
Second, define the state space consisting of states $(x,i)$ where $x$ is a node in the graph and $i\in \{1,2,...,|E|\}$. It represents "We are in node $x$, and the highest edge weight $p(e)$ we have seen so far is the $i$-th largest".
Let $V(x,i)$ be the length of the shortest path (in the classical sense) from $s$ to $x$, where the highest $p(e)$ encountered was the $i$-th largest. It's easy to compute $V(x,i)$ given $V(y,j)$ for any predecessor $y$ of $x$ and any $j \in \{1,...,|E|\}$ (there are two cases to consider - the edge $y\to x$ is has the $j$-th largest weight, or it does not).
At every state $(x,i)$, this computation finds the minimum of about $\deg(x)$ values. Thus the complexity is $$O(E) \cdot \sum_{x\in V} \deg(x) = O(E^2),$$ as each node is associated to $|E|$ different states.


texts: Techniques to prove a language is not DCFL

texts:
I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL.

Are there any other techniques that will help me to prove a language L is not DCFL?


texts: Choosing $n$ points to get the closest sum

texts:
Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, $y$, i.e. minimising
$$
f(J) = \left[y - \sum_{j\in J}x_j \right]^2 s.t. ~J \subset \{1,2,...,N\} ~\mathrm{and}~ |J| = n
$$
To get the exact solution, I think this is an $NP$ problem, so is there any random algorithm to find the (approximate) solution reasonably fast?


texts: Given a set of solutions, find an IP formulation with the same solution set

texts:
Input:

A list of integer variables $x_1, ..., x_n$.
A finite set of feasible solutions $S \subset \mathbb{Z}^n$.

Task:
Find an integer linear program (IP) on the integer variables $x_1,...,x_n$ such that the solutions to this IP equals S. One may introduce additional variables.
Objective: Find an IP formulation that can be quickly solved e.g. with CPLEX. This means the formulation should minimize both number of constraints and number of additional variables.

My toughts so far:

$S$ may not be convex, so introducing additional variables is probably necessary.
One can cover $S$ exactly by a set of convex polygons $P_1, ..., P_m$. By "exactly" I mean that no other integer point in $\mathbb{Z}^n \setminus S$ is covered by these polygons. For each polygon, one can find an LP description.
By adding $m$ additional binary variables and using the big-M notation to model implications, we can force that at least one of these LP descriptions is fulfilled in the solution to our IP.
For this approach to work one would need to find $P_1,...,P_m$ which I don't know how to do.
In my application $S$ contains several million elements. However, the number of variables and their range is quite small ($n \leq 20$, $x_i \in [0,1,...,30])$
I expect that the points in $S$ are somewhat clustered and a corresponding IP can be quite small.


texts: Algorithm to compute decomposition of a union of sets to a disjoint union of intersections

texts:
A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets.

This clearly generalizes. If we want to calculate the disjoint pieces, we have to compute $2^n$ intersections, where $n$ is the number of sets.

However, if our sets were nested, i.e. $A_1 \subseteq A_2 \subseteq ... A_n$, we need only to compute $n$ intersections of the form $A_i \cap A_{i+1}^c$. The point is if we did our original exhaustive "binary search" computing $2^n$ intersections we would find that most of these intersections are empty, so we are wasting computations.

My question is, what if we had $n$ sets where the vast majority are nested, but a few aren't and we don't know which. Can we compute an $O(n)$ number of intersections to find the disjoint pieces?


texts: Simple algorithm for IEEE-754 division on 8-bit CPU?

texts:
IEEE Std 754-2008 is the modern definition of Floating-Point Arithmetic. It requires that division (among other operations) performs

  as if it first produced an intermediate result correct to infinite precision (..), and then rounded that intermediate result, if necessary, to fit in the destination’s format.

I ask for a simple algorithm performing that operation, tailored to 8-bit CPUs with 8x8->16 bit multiplier; speed is a second(ary) criteria.

For simplicity I restrict to binary32 type

Image credit: wikipedia

and positive "normal" input with exponents such that no overflow or underflow occurs (so that we can ignore any sign or exponent consideration beyond some limited final exponent adjustment according to the result of the division), and rounding to nearest even:

  the floating-point number nearest to the infinitely precise result shall be delivered; if the two nearest floating-point numbers bracketing an unrepresentable infinitely precise result are equally near, the one with an even least significant digit shall be delivered.

I ask because I strongly suspect that the AVR libc implementation of float division (typically used on the Arduino Uno) deviates from the standard beyond being locked to roundTiesToEven, and I wonder how hard it would be to fix that. The current code seems to be divsf3, which invokes divsf3x to perform the division to apparently 40-bit mantissa, then rounding with fp_round. Isn't that very sketch doomed, BTW?


texts: Calculating traversal position of a node in a full binary tree, given its path

texts:
Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in the preorder traversal. In other words the $i$th node in the preorder traversal will end up with at this node.

Obviously something better than brute force would be nice.


texts: Landau Notation, Definitions: Limits vs. Corman's

texts:
When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.:

$$o(g(n))=\{ f(n): \forall c>0:\exists n_0>0:\; 0\leq f(n) < cg(n): \; \forall n\geq n_0 \}$$

and some texts use limit based definitions such as:

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0\Rightarrow f(n)\in o(g(n))$$

Is there any inherent advantage to one definition or the other?  Or is it more a matter of the author's personal preference?


texts: Asymptotic analysis of a real-valued function involving complex numbers

texts:
I have an algorithm which computes the size of maximum independent set of a graph $G(V, E)$. Let $n=|V|$ be the number vertices, $m=|E|$ be number of edges, and denote the size of maximum independent set of the graph $G$ as $\alpha(G)$ .

Now, I want to estimate the worst-case running time the algorithm needs to compute $\alpha(G)$. I have come up with the following recurrence relation
$$T(n) \leq T(n-1) + T(n-4) + O(n^2)$$
where $T(n)$ denotes the worst case running time. I also assume that the graph has in worst case $n^2$ edges. This algorithm makes two recursive calls and so I have $T(n-1) + T(n-4)$.

My approach is to solve the following inhomogeneous recurrence relation

$$a_n=a_{n-1}+a_{n-4} + n^2, \text{ where } a_0=a_1=a_2=a_3 = 1$$
This relation has two particular solutions
$$a_n^* = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n$$
where $z_1,z_2,z_3,z_4$ are characteristic roots of the characteristic equation $z^4 - z^3 - 1 = 0$
and
$$a_n^+ = B_2n^2 + B_1n + B_0$$
which gives the following general solution
$$ a_n = a_n^* + a_n^+ = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n + B_2n^2 + B_1n + B_0$$

My problem is that two of the roots $z_1,z_2,z_3,z_4$ are complex, one is real positive, and one is real negative, and I do not know how in general we estimate the rate of growth of functions having complex numbers like in this case. I would like to know if there is any general approach widely used in computer science and math to deal with such functions.


texts: Does two system's clock synchronises to communicate with each other?

texts: If two computer system's has to do some kind communication like data transfer or receiving should its clock sync to do that?If not then how they transfer bytes without having syced clocks?


texts:
Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space.

The original problem appears here,
however the solution uses $\lg n$ space.
A problem in my course required adjusting the algorithm such that we use constant space.

I thought of the following algorithm:

MyAlgorithm(root, num)
    min<-findMin(root)
    max<-findMax(root)
    while(min.key <= max.key && min != max)
        if((min.key + max.key)=num) return true
        if((min.key + max.key) < num)
            min<-successor(min)
        else
            max<-predeccessor(max)
    return false

According the CLRS book both predeccessor() and successor() functions time complexity depends on tree height which is $O(\lg n)$ in our case since red-black tree is balanced.

However, we have the while loop which theoretically can run almost n times.

For example, because the algorithm above is equivalent to searching for the number num in a sorted array, say we have this array and num<-3:
$$
1,2,3,4,5,6,7,8,9,10
$$
In this case we'll call predecessor(max) $8$ times which is almost $\Theta(n)$ or $\Theta((n-2)\lg n)=\Theta(n\lg n)$ asymptotically.

Am I wrong in my conclusions? How can I prove that the time complexity is indeed $\Theta(n)$?


texts: Given family of grammars, determine if LR(k)

texts:
Parsing family of grammars, determine if LR(k)

I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him personally. So I apologize, but I do have to ask for your help!

Would it be enough to show that the formula works for n = 2, n = 3 (by drawing the automata) and deduct that it must work for any n?

As for the second question, could I follow the same strategy?

Thank you for you time.


texts: 3D registration for reconstructed surface

texts:
I use Meshroom (based on the framework AliceVision) to reconstruct a scene based on photographs (e.g. a bottle on a table in a room). The software captures the bottle, but also the table and the whole room, so I have a huge model in the end. I also a have a ground truth model of the bottle.

My goal is to align the whole reconstructed surface to the ground truth model so that the coordinate system and the scale will be known. I managed to do it "manually": Meshlab has an alignment feature which uses ICP, but I need to provide input to the algorithm (clicking on arbitrary points on the reconstructed surface and clicking on the same points on the ground truth model, like here). However, I'd like to automate the process. One of the biggest challenges is that the reconstructed model contains many details which are irrelevant to the alignment (like the table, walls of the room, etc.).

Can you suggest a way to perform this alignment without any user input?


texts: What is the effect of operating systems on execution speed?

texts:
I'm using a Raspberry Pi 2 which works with 900MHz. (Asked this question there and they think it belongs to cs)

My question is: since it also runs an operating system in the background, I expect this would take some of the processing power.

So, how significant is the speed reduction due to operating systems? If I run a single code for example, what execution speed should I expect on average? Is it still close to 900MHz, or is it significantly lower?

Furthermore, is there a specific operating system or programming language that I can use to make it run faster?


texts: How can I prove that there is a decidable language which is not in P?

texts:
Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$:

It will only take a input which has a form of a Turing machine $\langle M\rangle$ (the description of $M$) and simulate $M$ on $\langle M\rangle$. If it halts in polytime and accept, reject. If it halts in polytime and reject, accept.

If $A$ is in P, there must exist a Turing machine $M'$ that decides it in polytime. However, if I run $D$ on the input $\langle M'\rangle$, the result will be converse to the simulation. Contradiction! So $A$ should not be in P.

The problem is that I don't know whether a turing machine will halt in polytime or not. Polytime can be $n^2$, $n^3$, $n^4$, ...


texts: What advantages does Block Programming Environment have over High Level Programming Language

texts: What advantages do block programming environments like App Inventor have over high level programming languages like Python or Java?


texts: how to generate all spanning trees from one spanning tree

texts: If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must also be spanning trees of the graph.


texts: Finding the base case for T(n) = T(n - a) + T(a) + cn

texts:
I was solving the recurrence using Recursion tree method:
$$ T(n) = T(n - a) + T(a) + cn$$
When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the form of:
$$h*ca$$
But I could not figure out on how to solve the base case.
I know that $T(n-a)$ would be at base case when $n=a$.
But how to compute the height $h$ of the recurrence.
I know the base case can be defined as:
$$n-ia=0$$
I have seen the previous examples in the book Introduction to Algorithms which quotes:

The subproblem size for a node at depth $i$ is $n/4^i$ . Thus, the
subproblem size hits $n=1$ when $n/4^i=1$ or, equivalently, when $i = \log_4 n$

For the recurrence: $T(n)= 3T(n/4)+ cn^2$
So, coming to the point what would be the base case such that the sub-problem size hits $n= ?$ like in the above example.
Would it be $n=a$?
Please correct me if I am wrong.
Thank you.


texts: Uniformly sampling from cycles of a graph

texts: I was wondering if, given an arbitrary cycle basis (that's complete, e.g. every cycle in the graph can be expressed as the $\mathbb{Z}/2\mathbb{Z}$ sum of elements from the basis) of some graph $G$, is there some way of sampling all cycles uniformly? I'm not able to find papers on it, and I was wondering if anyone had any results on this.


texts: How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$?

texts:
I already saw this answer. But I didn't understand totally.

So I found the solution to this equation $T(n)=4T(n/2+2)+n$.

Here is the recursion tree. But I can't compute the height as $lgn$ from this tree.

How to compute height? (Image is from solution)


texts: Why is DCFL not closed under kleene star?

texts: I honestly haven't an idea how to proof that eventhough I can understand the background, could someone help me?


texts: Why does merging two sorted arrays take 2N - 1 comparisons?

texts:
A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons

  Prove that merging two sorted arrays of N items requires at least 2N-1 comparisons.

 /*
 * An example program that merges two arrays to prove that merging two
 * sorted arrays takes 2N - 1 comparisons.
 */
public class MergeComparisons
{
    private int comparisonCounter;
    public MergeComparisons(){
        this.comparisonCounter = 0;
    }
    public int[] merge(int[] a, int[] b) // MERGE TWO ARRAYS
    {
        int[] arr = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
        {
            comparisonCounter++;
            if (a[i] < b[j])
                arr[k++] = a[i++];
            else
                arr[k++] = b[j++];
        }
        while (i < a.length)
            arr[k++] = a[i++];
        while (j < b.length)
            arr[k++] = b[j++];
        return arr;
    }
    public int getComparisons(){
        return comparisonCounter;
    }
    public static void main(String[] args){
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 7, 8, 9, 10};
        MergeComparisons ms = new MergeComparisons();
        //N = 10 because we have 10 elements.
        //Comparisons should be 19.
        int[] merged = ms.merge(a, b);
        System.out.println("After merging two arrays: ");
        for(int i=0; i<merged.length; i++){
            System.out.print(merged[i] + " ");
        }
        System.out.println("\nUsed " + ms.getComparisons() + " comparisons");
    }
}

I wrote the code above to try and test the statement but it does not show. Here is the output

  After merging two arrays:  1 2 3 4 5 6 7 8 9 10  Used 5 comparisons

I was assuming it should be at least 9 comparisons from the way the question was posed.


texts:
There is a lot of information available on the subject of Pairwise Comparisons but I haven't found any guidance on how to optimize pair measurements that have confidence values attached to them.

Imagine that an AI black box has been trained on many pairs of objects in order to predict the distance between the objects in novel pairs. All objects are colinear. The black box also provides a confidence level for each distance. Here is a simple example of outputs based on a set of 5 objects ($a$ to $e$):

Pair, Distance, Confidence

a-b,  5,        0.4
a-c,  9,        0.7
a-d,  -3,       0.9
a-e,  2,        0.6
b-c,  6,        0.8
b-d,  -10,      0.7
b-e,  -2,       1.0
c-d,  -6,       0.5
c-e,  -2,       0.6
d-e,  7,        0.9

So, the distance between $a$ and $b$ is predicted to be 5 units ($b$ is to the right of $a$) and the black box's confidence in that measurement is 0.4 (0.0 = no confidence and 1.0 = perfect confidence). The distance between $a$ and $d$ is -3 units ($d$ is to the left of $a$) and the confidence is 0.9.

I would like to understand the process for deriving the solution, which is the optimization of the four distances between these objects given the predicted distances and their associated confidence levels.


texts:
I've been searching around for definitions of intractability, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is not formally defined.

I'm currently writing a report in which I characterize some problems as intractable (in my context, they are intractable because their output size can be exponential w.r.t the input size), and I need to feel 'comfortable' about what intractability is in order to write coherent stuff in the report.

The way I understood it is the following: a problem is intractable if it cannot be solved reasonably fast, with reasonably big instances.

This leaves a lot of space for human appreciation of what a reasonable execution time is, and what a reasonable input size is. This also allows to describe some problems in P as intractable (if it runs in O(n^150) for instance) , and even in some cases, to eventually describe some NP-complete problems as tractable (many MILP problems can actually be solved fast with reasonably big instances).

My questions:

Is there a better/more elegant/more precise way to define intractability ?
Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?


texts: Finding the minimum vertex cover of planar graph given the planar representation

texts:
The minimum vertex cover problem is $NP$-hard for the planar graph of degree at most $3$. However, the minimum vertex cover can be easily found in some certain types of planar graph, given the planar representation. For example, the planar graph that every face boundary is a cycle of even length.

Is there any proof that shows the $NP$-hardness of the minimum vertex cover of the (general) planar graph, given its planar representation as an auxiliary input?


texts: How can repeated addition/multiplication be done in polynomial time?

texts:
I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in polynomial time ($O(n^2)$) via the algorithm we all learned in grade school.

However, how can we add up or multiply say $i$ numbers together in polynomial time? After we add up 2 numbers together, we get a bigger number that will require more bits to represent. Same with multiplication.

How can we ensure that these extra bits do not produce exponential blowup?


texts: If $A \le _m B$, then $A$ decidable $\not\Rightarrow B$ decidable

texts:
I'm currently reading up a bit on Turing decidability reductions as I'll take a more in-depth course about the topic next semester. While reading up on some older course material I asked myself the following question which leaves me a bit puzzled:

Let $A, B$ be languages, and $\le_m$ be the mapping reduction for languages.

For mapping reductions a central statement is

  If $A \le _m B$, then $B$ decidable $\implies A$ decidable

I'm now wondering about is whether the implication also works the other way around:

  If $A \le _m B$, then $A$ decidable $\implies B$ decidable

I strongly suspect that this is not the case as $A \le _m B$ does not even imply the existence of a mapping function from $B$ to $A$, however I'm struggling to find a good counterexample for this.


texts: Why are non-relativizing proofs preferred to relativizing ones?

texts:
I apologize, but even after these two other posts: here and here
I'm still having trouble understanding oracle TMs and relativization.  This question comes at the issue from a different angle:

Why are non-relativizing proofs considered more valid than arguments based on relativized results?

For example, we have a non-relativizing proof of IP = PSPACE, but couldn't we just as well say an argument for the opposite by the fact that there exists an oracle separating them (I realize from an answer to a question I previously asked that this oracle exists due to a structural difference between the two complexity classes, but I see that as even more evidence that the classes are different in important ways and may not be equal).

On the flip side, why do we conclude from the fact that there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B \neq NP^B$ that non-relativizing techniques will be needed to resolve P vs. NP and not just resolve that oracles lead to inherent contradictions since we cannot have both P = NP and P $\neq$ NP?  Again, I realize from a previous post that we can view oracle TMs as different models of computation that can solve problems ordinary TMs cannot, but I see this as similar to the "theory of types tactic" used in Principia Mathematica which, according to my understanding, Godel (through the Incompleteness theorems) proved to be insufficient to resolving issues of the completeness and consistency of axiomatic systems.


texts: $\mathsf{co\text{-}NP}$ and Cook reductions

texts: Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to Cook reductions. Does this imply that if it is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\text{-}NP}$ and if so, why?


texts: How BDI agent architecture is connected with PSI agent architecture?

texts:
How BDI (Beliefs-Desires-Intentions) agent models is connected with PSI agent model http://cognitive-ai.com/ (and https://en.wikipedia.org/wiki/Psi-theory)? Is one of the models the generalization of the other? PSI model seems to be more sophisticated but it may lack (at present) all the logical foundations and reasoning services that are available for BDI agents. From the other side - PSI models can be path forward in the development of BDI agents.

Is PSI model acceptable as agent implementation for the serious study projects and research efforts in computer science? Or should I remain with BDI models for the present?


texts: Why is automated theorem proving impossible?

texts:
As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output.

Why is it so?


texts:
If Manufacturer manufactures electronic equipment, then manufacturer generates e-waste.

I have generated the triple.

However how to represent the if-then statement in DL?

manufactures(manufacturer, electronic eqpt)
generates(manufacturer, e-waste)


texts: What are constraints on some new logic programming language and system?

texts:
As I understand, everyone can create logic programming language and system by declaring that the valid program of some logic programming language is the set of statements in the form: body->head, where body is arbitrary expression of boolean type and the head is set of expression that, in some cases, can change the current valuation function (function for some logic that assigns values to the variables of this logic), e.g. by assignment operations. There is no need to prove any properties of such programming system, because one can expect that such system is Turing complete and hence there is no important properties (e.g. termination) to prove. Practical termination can be achieved even by very rude methods (e.g. as in Drools), e.g. by allowing to declare that no more than e.g. 10 rules can be fired in one execution step. Am I right? Does the definition of new logic programming system/language for scientific and practical purposes ineed allow such great freedom without any constraints and duties to prove some properties of this system?

Of course, some works on logic programming tries to prove stable model properties but I am interested (and practice usually requires) in non-monotonic logic programs (as almost any program used for business purposes change the state and hence the valuation function of variables) and they can not have such stable models.

There is such background for my question: I am aware of the logic programming system for agent modelling http://jason.sourceforge.net/wp/ Jason AgentSpeak. I am not satisfied with the expressibility of the base logic used by AgentSpeak. I have reason to state, that special kind of linear logics can be more appropriate base logic for agent modelling. That is why I am trying to create my own new logic programming system that is based on special kind of modal linear logic with actions. So - can I simply form the set of expressions of the type body->head from the language of modal linear logic and announce them as logic programs in modal linear logic? I am required to prove anything?


texts: Dealing with truncation errors when performing Gauss-Jordan elimination

texts:
When using Gauss-Jordan elimination to convert a matrix to an upper triangular matrix, truncation errors can drastically change the answer.

For example, when performing row operations with excel, with the following matrix:

Is reduced to:

The value in the red cell is a truncation error and should be zero.
The next step in the algorithm would be to divide the 2nd last row by a constant to make the red cell equal to 1. If no truncation errors had occurred then this cell would have a value of zero. This drastically changes the final matrix. How could I correct for this?


texts:
We are given an array and a number K. Partition array into K subsets such that

let MaxSum be the maximum sum of among subsets.

We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$

Is this problem polynimial time solvable?


texts: Solving recurrence relation t(n) = t(n/2) + log2(n), such that T(1)=0

texts:
I get how to solve recurrence relations for t(n)= t(n-1) etc etc.

But how would you solve the recurrence of t(n) = t(n/2) + log2(n), such that T(1)=0? I don't understand how the log would behave in this situation.


texts: Can't find a mistake in reduction from RE language to a non-RE language

texts:
In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I tried a reduction from a Universal Turing machine language(which is RE) and it also seemed to work. Since a language can't be both RE and non- RE, there is a mistake and I can't figure out where. Please help!

My reduction from Lu (univeral TM) to Lm (infinite language TM):
The input to Lu is (M,w).
Build a new TM M' with an input x as follows, let it simulate a string w on M and if it accepts, then M' goes to states where it accepts a language 0^n, n>1, and accept its input x. If M rejects w or doesn't halt, then M' never accepts its input x. Then take the description of this machine M' and feed it into Lm. Therefore, if M accepts w, M' accepts an infinite language and Lm accepts it. If M doesnt accept w, then M' only accepts ∅ language, which is finite, hence Lm rejects.


texts: How to convert $(0.11001100...)_2$ to a decimal number

texts:
I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number.
But I have a hard time finding an algorithm for converting a binary number with infinite bits to a decimal number.
I will like to convert $(0.11001100...)_2$ to a decimal number.


texts: What is the difference between a scripting language and a normal programming language?

texts:
What is the difference between programming language and a scripting language?
For example, consider C versus Perl.

Is the only difference that scripting languages require only the interpreter and don't require compile and linking?


texts: Where to put the state in a two-stack push down automaton?

texts:
theoretically, the state is between the two kleene-stars of the work-alphabet
gamma* q gamma*

where q is the current state and each gamma* is the content of one of both stacks. But where is "the middle" with the state? Regarding the one tape of the classical Turing Machine it is obvious.
Yours,
von Spotz


texts:
These are the instructions I been given :

  What does the array look like at each step when inserting "2" into the
  following min-heap?

  Give your answer as comma-separated numbers, with a space after each
  number, eg., 0, 2, 3, 4

  The heap starts at entry 1 (second entry) of the array, so begin with
  "0,..." for the unused entry.

and I need to write down the array at each step like

Immediately after item is added: for this step I got 4 6 8 7 2

After first sift up step: 4 2 8 7 6

but that is wrong apparently? I'm not sure why also I'm not sure where and why I'm suppose to put a 0.. is there a different way to write it?


texts: Online approximation algorithm for median?

texts:
Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$?
The scenario is: I have a stream of numbers, and at any point in the streaming process I should be able to query for the (approximate) median in the last $k$ elements.
Thanks!


texts: Which architecture do modern computers use?

texts:
Is it one of:

Harvard
Modified Harvard
von Neumann

Or are they antiquated models that modern computers are only loosely based on?

If you asked Intel or AMD what would they say?


texts:
I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages.

Question: Let
$
A = \{ ww \ | \ w \ \epsilon \ \Sigma^{*} \}
$.

Show that any language $L$ is Turing-decidable if and only if $L$ is many-one reducible to $A$.

Where I am so far:

Language $A$ is not context-free, but the complement of $A$ is context-free.
Both $A$ and the complement of $A$ are decidable.

So, that means I can prove one direction of the iff statement fairly easily:

If $L$ is many-one reducible to $A$ then since $A$ is decidable from statement (2) above, also $L$ is decidable.

The other direction is giving me problems. This is all I have  gleaned so far:

If $L$ is Turing-decidable, then $L$ is a regular language.

Is there some relation between regular and context-free languages with respect to reductions that I am missing? Or should I be making a different logic jump in this part of the proof?


texts: How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

texts:
Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular:
  $$
G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } 01 \text{ with }\$\$ \}
$$
  For example, if $10112\in L$ then $\$1\$\$12\$\in G$.

I think this can be solved using closure properties of regular languages.

1) Let $H=\$L\$$. $H$ is also regular because it's concatenation.

2) Let $h:\Sigma\to \Sigma^*$ be defined as follows:
$$
h(\$)=h(0)=h(1)=\$
$$
Then:
$$
G=h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$
$$
which is regular because $h^{-1}$, intersection and regular expressions are closed in regular languages.

I wonder if my proof using closure is correct or automaton should be built in this case? In addition if I managed to think of a regular expression to describe $G$ then this alone would've proved that $G$ is regular?


texts:
I read now several articles about RISC and CISC architecture. Most are rather exuberant enumerating all the differences between these architecture, but not necessarily why things are the way they are.

One point that struck out to me the most was about the RISC's feature of using hard wired parts in its processor and in particular so called "Random Logic" . According to wikipedia one might best view it as a "simple" decoder from "high level logic" to hardware features like AND and OR gates.

Unfortunately I didn't find more about "Random Logic", so I am a bit at a loss of its concept, design, purpose and why it is needed.

So I hope someone could go into more detail or simply provide references to read up on that topic online.


texts: Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states?

texts:
As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can DFA have more than $2^n$ states?

I think it is, and this is trivially. However Wikipedia seeems to write that it is not possible to have more than $2^n$ states. So comes the question.


texts: Why there is a probability in the completeness part?

texts:
Interactive Proof System : An interactive proof system for a language $L$ is a two-party game between a verifier and a prover that interact on a common input in a way satisfying the following properties:

The verifier strategy is a probabilistic polynomial-time procedure (where time is measured in terms of the length of the common input)
Correctness requirements:
Completeness: There exists a prover strategy $P$, such that for every $x ∈ L$, when
interacting on the common input $x$, the prover $P$ convinces the verifier with probability at least $\frac{2}{3}$.
Soundness: For a false assertion, no convincing proof strategy exists (in the case of NP, if $x \notin L$ then no witness $y$ exists).

My Question : In the completeness part why there is a probability comming into picture?


texts: Genetic algorithm crossover technique for solving graph colouring problem

texts:
I am trying to develop a genetic algorithm to solve a graph colouring problem.

The problem is the standard graph colouring problem, given a graph $G = (V,E)$ where $V$ is the set of vertices $V=\{0 \dots n-1\}$ and $E$ is the set of edges, colour the vertices such that no two adjacent vertices are the same colour and the objective is to minimise the number of colours used.

the way i have represented it is in the following way:

a population of individuals is established, each represented by an array of $n$ randomised integers in the range $0...m$ where $m$ is a number (representing the number of colours used) generated between $1...n$
fitness is determined according to the following objective function:

$min \sum_{i=1}^m(2|B_i||C_i|) - \sum_{i=1}^m|C_i|^2$

where,

$B_i$ is the set of edges which have two vertices coloured with colour $i$,
$C_i$ is the set of vertices coloured with colour $i$

the intuition behind this funciton is to minimise the number of violations while maximising the size of the colour classes (and hence minimise the colours used)
once the individuals are ranked by fitness, parents are selected to mate in the following manner:

parent_1 (m=6): [1 3 5 4 2 1|0 0 5 2]
parent_2 (m=4): [2 0 1 3 0 1|0 2 1 3]

* crossover applied at "|" *

child_1: [1 3 5 4 2 1 0 2 1 3]
child_2: [2 0 1 3 0 1 0 0 5 2]

my problem now is that a 1 in the first subset of child_1, does not necessarily correspond to the same colour as the 1 in the 2nd subset of child_1. This does not matter before the crossover, because the values are just class labels, and are interchangable - but after the crossover has been applied, it will create relationships that weren't there and lose those that were.

in an instance where the first subset of the vertices are highly connected, and the second subset are also highly connected without many connections across the crossover point, this would not be so much of a problem as it is more or less a case of connecting two disjoint graphs. but in the instance where many of the edges span the crossover point eg. (1, 8), (4, 6), etc. this becomes a large problem as the initial colour assignment matters.

can anyone suggest a way to design the crossover operator such that it retains these relationships? or is this just a fundamental property of genetic algorithms, and they are not necessarily very effective for these types of problems with dependencies between variables?

i just chose this problem because it seemed interesting and i wanted to get some practice implementing genetic algorithms, but maybe i should choose a more suited problem?

Edit:
I will use a very trivial example, just to be more explicit about my problem.

for the graph $G = (V,E)$ where $V = \{0 \dots 3\}$ and $E = \{(0,1),(0,2),(0,3),(1,3)\}$

two equally valid, equally optimal colourings would be:

parent_1 (m=3): [0 1|1 2]
parent_2 (m=3): [0 2|2 1]

after applying crossover, the following children are generated:

child_1: [0 1 2 1]
child_2: [0 2 1 2]

leaving vertices 1 and 3 the same colour for both offspring and therefore less fit than the previous generation. i understand that the stochastic nature of GAs can sometimes produce this kind of result, but this feels more like random search than any kind of metaheuristic behaviour where it is keeping the good features of the previous generation.

applying some sort of lexicographical ordering of colour labels before mating would solve this problem for this particular very small example, but my intuition is that this wouldn't really help for larger problems as the dependencies would be much more complex.

any ideas?


texts: Why is big omega of peak finding Omega(lg n)?

texts:
Why is big omega of finding a peak in an unsorted array Omega(lg n), not Omega(1)?

I understand that peak finding is O(lg n), because in the worst case, we find a peak in the last possible step, so when drawing a decision tree, the height of the tree (lg n) would be the worst case situation. However, in the best case, can't we get "lucky" and find a peak in the first try?


texts:
I have a task to teach a classifier for some specific data:
There are rows that consist of lengths of distances to some objects (for example, 10 columns with distances values). For each row objects could be not the same (so there is info only about distances). Info in rows is sorted ascending. Dataset also is labeled for each row as true/false. In theory, the bigger the distance value, the more likely the object will be labeled as false.
The question is, what classifier I should use for this case? (maybe linear resgression or something better...)


texts:
I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)$ and $H(xa)$ for any letter $a\in A$. In practice one can assume that $A$ is for example the set of $8$-bit integers.

In other words, a hash function for strings that can quickly be extended in both directions. I'm only interested in hash functions that actually distribute the data well and which are very fast to compute in practice.


texts: Multiple neural networks or multiple outputs?

texts: Suppose you have data of the form input a matrix A, and output a matrix B, where each row of each is one datapoint. Should you create multiple neural networks, one for each column of B, or one NN with multiple output neurons, one for each column of B?


texts: Language of binary strings divisible by 7

texts:
There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is :

1) Recognizable by a finite-automaton.

2) Recognizable by a Non-deterministic finite-automaton.

3) Recognizable by a deterministic Pushdown Automaton.

4) Recognizable by a Non-deterministic Pushdown Automaton.

5) Not recognizable by any of the above.

I'm curious to know the answer and its reason.


texts: Can a Boolean circuit be considered an algorithm?

texts: Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single OR gate for a depth two circuit. Now change the AND gates to XOR gates, is it correct to say that I now have a different algorithm for any given input?


texts:
I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined score (i.e. a fantasy football formation) within a $50,000 budget, where a lineup must consist of the following formation:

Goalkeeper x1
Defender x2
Midfielder x2
Forward x2
Utility x1 (can be any position apart from GK)

Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one not already used non-goalkeeper as a "utility" (from the 100 - 18 = 82).

Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.

What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment (i.e. there are trillions of possible combinations)?


texts:
How can we prove that:

$$
L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\}
$$

is not context-free?

The language defines $w_1$ as a sub-string of $w_2$, and they are separated by a $\#$. This is easy with the CFG pumping-lemma for a slightly different language with $|w_2| \ge |w_1|$ by using the special case of $|w_2| = |w_1|$ (i.e. $w_1 = w_2$).

But here, $w_1$ is a proper sub-string of $w_2$ so I can't do the same. I fail to push the string out since we can always pump, for example the first symbol of $w_2$.


texts: Have these graphs with a mindegree and weight condition been studied before?

texts:
Consider a weighted undirected graph $G=(V,E)$ with $n$ nodes. We call $G$ a $(\tau,k,n)$-graph if for every node $v \in V$ has at least $k$ neighbors and each edge has weight at least $\tau$.

Have these kind of graphs been studied in the literature in any context?


texts: How to test for overflow when multiplying floats

texts:
I am trying to implement a 3-term recurrence relation:
$$
p_{n+1} = ap_n + bp_{n-1}
$$
This can be implemented as

  p0 = P0 // starting value p_0
  p1 = P1 // starting value p_1
  loop n = 2,...,N
    pn = a*p1 + b*p0
    p0 = p1
    p1 = pn

Depending on $(a,b)$ and also the stopping point $N$, this can sometimes overflow, and I would like to detect such a failure. I believe it is bad form to simply let the loop run to completion and then use something like isfinite to check the final value.

A more elegant method would be to somehow test whether the term a*p1 + b*p0 will exceed the floating point maximum (DBL_MAX = 1.7976931348623157e+308) prior to computing it. I could not find much information about this online, so does anyone have suggestions?

One idea I had, was suppose we are just dealing with the first term $a p_n$. Then we could test:
$$
\log{|a p_n|} > \log{\textrm{DBL_MAX}}
$$
or
$$
\log{|a|} + \log{|p_n}| > \log{\text{DBL_MAX}}
$$
It seems that this test would work even if $a p_n$ is not representable as a floating point number. I'm not sure how to extend this test to the general case $a p_n + b p_{n-1}$, or even if this test will account for all possible failure cases in double precision.


texts: NP-hard or not: partition with finite irrational input

texts:
Original Problem

Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset whose sum is $x_*$, where $x_*$ is a known fixed irrational number and $x_*\approx 0.52$.

I proved its hardness by the following arguments.

Instance

Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

$a_1,...,a_n$ are positive and rational
$\sum_{i=1}^n a_i = .02$
$a_{n+1}=x_*-0.01$
$a_{n+2}=0.99-x_*$

determine whether we can find a subset of $N$, such that the sum of the subset is $x_*$.
.

NP-complete

Since ∗ is irrational, the desired subset cannot contain both of the last two numbers.
Since the sum of any subset not containing the n+1st element is smaller than ∗, the desired subset must contain the n+1st element.
The remaining question is to find a subset of the first n numbers whose sum is .01

So the original problem is NP-complete.

My problem

Someone argued that since $x_*$ is irrational, I can't store irrational numbers in a machine properly and my proof is not correct.  How to address it?


texts: Fastest algorithm for transforming points into graph

texts:
Given a set of $n$ two-dimensional points in the plane
$$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$
and a real number $M$, I want to transform this set of points into a graph with the points as vertices with an edge between points $A$ and $B$ if the distance between $A$ and $B$ is at most $M$.

What is a fastest algorithm that can perform this task?


texts: Weighted Average of Neural Networks with Cross Entropy Cost Function

texts:
What is the best way to create an ensemble of neural networks utilising weighted averaging when these networks were trained to minimise cross entropy error function?

The literature I found (e.g. [1]) seems to be talking only about weighted averages of neural networks that employ mean square error (MSE) cost function. Anything other than that seems to require a modification of the training algorithm. Is there an analytic extension of [1]'s generalized ensemble method (GEM) algorithm to compute neural networks' weightings when cross entropy error function is used? Or some entirely different algorithm would be required? Or maybe it can only be done by numerically estimating those optimal weightings?

[1] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.


texts: Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular

texts:
I have looked up a question like this online and found this solution.
I couldn't understand what the new NFA A' looks like.
Could anyone give me an example of NFA A'?


texts:
I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals:

  Basis: if $A \rightarrow \epsilon$ is a production, $A$ is nullable.
  Induction: if $A \rightarrow X_1X_2\ldots X_n$ is a production, and $X_1, X_2, \ldots, X_n$ are all nullable, then $A$ is nullable.

Intuitively, this algorithm seems correct. But I don't see how it could properly show $B$ to be nullable in the following grammar:

$$A \rightarrow a$$
$$A \rightarrow \epsilon$$
$$B \rightarrow B A$$

How does the algorithm deal with these recursive productions that are nullable? If not, what changes must be made to make it correct?

My second question is whether the following grammar is nullable, or whether it's even a valid context-free grammar at all.

$$S \rightarrow S$$


texts: Upper bound complexity for a tree's particular property

texts:
I want to determine if

  in a given binary tree whose nodes are integers, left subtree's
  (let's call it L) nodes are multiples of (at least one) right
  subtree's (R) node(s).

I only require that every integer in L must be a divisor of some number in R, but not the reverse (for every number in R, it is a multiple of some number in L).

Speaking with other words: if $a$ is in L, then it is multiple of at least a number in R. (e.g. $R=\{4\}$ then L can only contain $4k,k \in \mathbb{N}$ ).

What is an upper-bound for related algorithms? I want to use the model in which operations on integers always take O(1). I can't use extra space (i.e. I can't build other trees). The tree isn't ordered in any way (it isn't a BST). My goal isn't to construct the tree but to verify that a given tree satisfies the property.

My thinking was: let's pick a complete balanced tree of n nodes. L nodes are n/2, as R nodes. If I have to verify that the content of a L node is multiple of R nodes, in the worst case I have to compute (L node) mod (every R node), hoping one of them is zero. For every node I have to make as many computations as the number of R nodes (-> n/2). To check the property for every L node the computations are (n/2 * n/2), so I would assume $n^2$ as an upper bound.

Is it correct?


texts: CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }

texts:
$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$

$\bullet $ #$_b$ denotes the number of $b$'s in $w$

$\bullet $ #$_c$ denotes the number of $c$'s in $w$

I have some trouble designing a CFG for the language above. How can I do this?


texts: Provide some help regarding the "Dining Philosophers Problem"?

texts:
I have an assignment based on operating systems and the question is divided into two sub-questions.

The first is: Prove any seating arrangement of lefties and righties, with at least one of each avoiding deadlock.

The second: Prove any seating arrangement of lefties and righties with at least one of each avoiding starvation.

I understand the concept behind this problem and that I can use semaphores, or monitors etc. but the resources I have found online mainly explain in coding, but I need help understanding which is the best way to answer this question in theory by choosing one of the ways to prevent deadlock and starvation.


texts: Is there a relationship between "sound and complete" in logic and "type safety" in PLs?

texts:
I've been wondering if there's a connection between "good logics" and "good programming languages". It seems that logics are shown to be "locally sound and complete" whereas programming languages are shown to be "type safe" (preservation and progress).

If there's a relationship could you please explain it and give some references so that I can follow up on it.


texts:
I am learning Big O and Big theta notation and confused the certain case.
I have two functions,
function 1(f1)
$$ n * n^{1/2} $$
function 2(f2)
$$ 1.001^n $$

in smaller cases (10,000) f1 is much faster than f2, however, it is vice versa for bigger case (10,000,000). For the smaller case, I can say
$$ f2 = O(f1) $$
In the bigger case, I can say
$$ f1 = O(f2) $$
and I think this case is,
$$ f1 = \theta(f2) $$
(If ^ this is wrong, please let me know)
At this case, can I say ??
$$ f1 \equiv f2 $$


texts: How to implement polymorphism in a turing complete environment?

texts:
I'm currently programming in an unnamed turing complete language which has support for pointers, primitive data types, structures, closures, and garbage collection, among other things.

I'm trying to use this language to implement an object oriented design pattern. So far, I have implemented the following algorithm:

make object (base class) subroutine:
    create data structure
    associate structure as an 'Object'
    return data structure

make shape (extends from object) subroutine:
    call make object
    associate data structure as a 'Shape'
    add 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

make circle (extends from shape) subroutine:
    call make shape
    associate data structure as a 'Circle'
    add 'getCircumference' as subroutine to data structure
    re-define 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

output shape area subroutine
    assert shape is a Shape
    print, call shape.getArea

This so far has worked great. Sub-classes correctly inherent the fields of their super-classes.

However, I am no longer able to take the extended classes and 'treat them as their super-class forms' anymore. For example, I can no longer treat a Circle specifically as a Shape, because when it was made into a Circle it was augmented with Circle member functions like getCircumference. I cannot typecast it to be strictly a Shape or an Object, as its now been defined with sub-class functionality.

In Java terms, I can do this:

Fruit a = new Fruit(); // eat()
Apple b = new Apple(); // removeSeeds()
b.removeSeeds();
b.eat();

But I cannot do this:

Fruit a = new Apple();
a.removeSeeds(); // undefined

How can polymorphism be implemented in this sense?


texts: What is the relation between the compatibile features and the state features in Actor Critic Algorithm?

texts:
According to Actor-Critic algorithm, $\psi_{\theta}=\nabla_{\theta}\ln \mu_{\theta}(s, a)$ where $\mu_{\theta}(s, a)$ is the policy followed by the actor and $\psi_\theta$ is the compatibile features space.
The updates for the actor and critic parameters are as follows:

For critic with the parameter w:
$w_{t+1} = w_t + \beta_t\delta_t^{\mu_{\theta}}\phi(s_t)$
where $\phi(s_t)$ is the feature vector of state $s_t$
For actor with the parameter theta:
$\theta_{t+1}=\theta_t + \alpha_t\delta_t^{\mu_{\theta}}\psi(s_t, a_t)$
where $\psi(s_t, a_t)$ is the compatible feature vector of state $s_t$, with action $a_t$.

I am trying to understand the relation between $\psi(s_t, a_t)$ and $\phi(s_t)$, any pointers would be appreciated.


texts: Generating regular expressions not containing abc

texts:
Let sigma = {a,b,c}. How do I generate a language L that does not containg abc?
Any guidance is appreciated!


texts: Clarification on NP-hardness and hardness of approximation results for set cover?

texts:
I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.

I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.

Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m < n$ or $m > n$?


texts: Where can I find someone that will sit with me and explain the analytics reports from my iPhone and computer?

texts:
This may seem like a dumb question to most people, BUT PLEASE READ THIS!! I AM BEYOND DESPERATE to get rid of a hacker that is digitally stalking me and terrorizing me. I picked your forum because there is so much of the same code writing that I see on my phone. This has been going on for over a year now and I have only found 1 computer forensics website on online. They are a company in Denmark and do not work for consumers, so they wouldn't even help me. The hackers are my now ex-roommate and 2 other women that are continuously in  our phones. For instance the other day I turned on Voice Memo on my husband's phone and it showed the location to be at a  completely different location a couple of miles away from my real address. Then, on my phone, I went to my maps app to get directions to a place and it said that I was at a college campus in a completely different city than where I live.
  I NEED SOMEONE THAT CAN READ CODE and explain to me what is system operations and what is from the hacker. I have become obsessed with this problem, which just adds to the problems the hackers have created. I find myself going down worm holes (many, A LOT) because of some piece of information I found on the phone or computer and I feel that it is NOT PART OF THE NORMAL OPERATING SYSTEM FUNCTIONS. Since March of this year I have had no Wi-Fi, no cable, no data until about 3 weeks ago when I had it turned back on because I need it to my job, no debit cards, and no social media. I think they are intercepting the signal at the tower that is in the middle of a field way out in the country. Also, I think I found some of their portals/backdoor/link that they have been using to get into my devices.
They are relentless, methodical and cruel. They are 50% responsible for my son getting fired from his job because they spoofed his number to call the owner of the company and a couple of other employees at 2am and hang up on them.
They track me, all of my text messages are forwarded to someone, my phone calls are recorded, and they turn microphones on to listen to whatever is going on. They are also trying to convince me my husband is having an affair. There is so much that has happened over the last year that I cannot even remember them all.
I AM ON MY KNEES BEGGING FOR SOME KIND OF HELP. We can do a remote login or whatever it takes. I have a new job, my dream job at that, and I cannot afford for them to be in the company laptop computer. It is a new company so there isn't an office yet, which means I am working from home or the library until we get an office.

I NEED A WIN, PLEASE. It is not in my disposition to just let someone get away with this. Plus they are constantly doing things to my phone, like changing my settings, to let me know they are still there.
Thank you for your time and reading this. Any advice and/or help given will be GREATLY APPRECIATED.

TY


texts: How to model conditionals with first-class functions?

texts: Since languages with recursible first-class functions are Turing-complete, they should be able to express anything expressible in any other programming language. Therefore, it should be possible to model conditional expressions (i.e. if-statements) with first-class functions. Could someone illustrate how to do this?


texts: Cormen RB-DELETE_FIXUP(T,x) when x has no siblings

texts:
I am working on chapter 13 of CLRS. I am studying how to fix the colors on a red-black tree after deleting a black node.

Suppose we want to delete the node 2. This is a black node. He will be replaced by his rith child in the RB-DELETE algorithm. Because we removed a black node and the node replacing it is black (all NIL are black) then we enter the loop in RB-DELETE-FIXUP. Now this loop immediately asks for x's sibling w to enter different cases. But w in this case would just be 3's right child which is T.nil. It gets even worse from here because we start asking about 3's right child children in case 3 or 4. What's supposed to happen when x does not have siblings?
These are the relevant algorithms:
RB-DELETE-FIXUP(T,x)
1 while x different from T.root and x.color == BLACK
2   if x == x.p.left
3      w = x.p.right
4       if w.color = = RED
5          w.color = BLACK // case 1
6          x.p.color = RED // case 1
7          LEFT-ROTATE(T, x.p)/ // case 1
8           w = x.p.right // case 1
9       if w.left.color == BLACK and w:right:color = = BLACK
10         w.color = RED // case 2
11         x = x.p // case 2
12      else if w.right.color == BLACK
13              w.left.color = BLACK // case 3
14              w.color = RED // case 3
15              RIGHT-ROTATE(T, w)/ // case 3
16              w = x.p.right // case 3
17           w.color = x.p.color // case 4
18           x.p.color = BLACK // case 4
19           w.right.color = BLACK // case 4
20           LEFT-ROTATE(T, x.p) // case 4
21           x = T.root // case 4
22    else (same as then clause with “right” and “left” exchanged)
23 x.color = BLACK

RB-DELETE(T,z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4      x = z.right
5      RB-TRANSPLANT(T, z, z.right)
6 elseif z.right = = T.nil
7        x = z.left
8       RB-TRANSPLANT(T,z,z.left)
9 else y = TREE-MINIMUM(z.right)
10   y-original-color = y.color
11   x = y.right
12   if y.p = = z
13      x.p = y
14   else RB-TRANSPLANT(T,y, y.right)
15           y.right = z.right
16           y.right.p = y
17   RB-TRANSPLANT(T,z,y)
18   y.left = z.left
19   y.left.p = y
20   y.color = z.color
21 if y-original-color == BLACK
22   RB-DELETE-FIXUP(T,x)

```


texts:
I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. One of the most common examples to show this is regular language being $p^*q^*$ and CFL being $p^n q^n$.

Now if I promote regular language to CFL according to Chomsky hierarchy as all regular languages are context free languages, then the question changes to CFL intersection CFL which is not closed and hence we cannot say that the resultant language is surely a "CFL".

Why are the results different using both the methods?


texts: How is the environment designed for testing a reinforcement learning algorithm?

texts:
I'm working on a project, and have a candidate algorithm which I'd like to test. Before I go any further, I need to get the hang of how to code the "structure" of the environment in which my system is embedded, like what the relevant signals are, how they interact with each other, how they evolve with time, and so on.

I'm looking for resources on design of the environment, for artificial intelligence problems, as I don't want to reinvent any wheels. Any information would be welcome, especially introductory to intermediate level. Thanks!


texts: Predict language from given expression $(b^* (aaa)^* b^*)^*$

texts:
I want to predict language from the given regular expression.

Regular Expression: $$(b^* (aaa)^* b^*)^*$$

As per my assumption language may be like:

Let the string contain alphabet $\{a,b\}$ where every string contain number of $'a'$ divided/multiply by $3$.

Let me know whether my assumption is correct or not.

Thanks


texts: Is the language $L$=$\{ | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?

texts:
I came up with an algorithm to decide this language, but not sure if it is correct?

for every string w over {0,1} of length at most n1 x n2:
    if D1 accepts w and D2 rejects w:
        REJECT
ACCEPT

Where n1 and n2 are the number of states in $D_1$ and $D_2$.


texts:
One way to define indexed monads is as a type of enriched category.
class (forall a b. Functor (m a b)) => IxMonad m where
  ixpure :: x -> m a a x
  ixjoin :: m b c (m a b x) -> hom a c x

This is mostly a curiousity but if an indexed monad can be viewed as a  type of category the question arises: what is a functor f of an indexed monad m? I feel like this should be useful for mapping over an indexed monad and better handling them. Maybe one could even define a monoidal functor of an indexed monad?
I can think of a few different definitions.
As an action
fmap :: m a b (f a) -> f b

"Uncurried" which seems to suggest actions on an indexed monad should themselves be monads.
fmap :: m a b x -> (x -> f a) -> f b

As a map to a category c
fmap :: m a b x -> c (f a) (f b) x

I don't really see how these definitions relate unfortunately or how to generalize further.


texts: Is Breadth First Search Space Complexity on a Grid different?

texts:
Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:

For example, the flood fill question is described here:

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

The flood fill algorithm using breadth first search (queue) has space complexity: O(number_rows + number_cols).

Why? Suppose you start at the top left corner (or coordinate (0,0)). Going to the right we will get at most O(number_cols) in the queue. When we reached the end of the column we can then start going down from coordinate (0, 0) giving us O(number_cows + number_cols) in the queue.

Then, is it the case that many of the questions where we use breadth first search on a grid we will get space complexity of O(number_rows + number_cols). For example:

Flood Fill question above,
Maze where we have to find the shortest
path from start to exit,
Finding number of islands (reference below)

But for 3) finding the number of islands, it looks like some people are saying the space complexity is O(number_rows * number_cols) from : https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode

On the other hand, I would assume that the space complexity of dfs on a grid is O(number_rows * number_cols)

The questions are as follows based on the above:

Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
Is the space complexity of depth first search on a grid: O(number_rows * number_cols)?

Other references:

https://stackoverflow.com/questions/21054959/time-and-space-complexity-for-breadth-first-search

https://stackoverflow.com/questions/4261112/time-and-space-complexities-of-breadth-first-search


texts:
How can one calculate the winding number of a polygon given as
a list of vertices in some (counter-clockwise or clockwise) order?

The complexity of the algorithm must be linear time.


texts: I want to go RD parsing with Shunting Yard for expression (for the sake of  easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?


texts:
in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be. And let the Wordproblem be  $ L = \{ \langle M, w \rangle | M  \space is \space TM  \space and  \space w \in L(M) \} $ and Halting Problem $ L = \{ \langle M, w \rangle | M  \space is \space TM  \space and  \space M \space halts \space on  \space w\} $
Ok for word problem: since there exists a sequence of $M_i$ I would start with $M_1$ and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all $w_i$ to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on for a sequence of computable words $w_1, w_2,.. \in \Sigma^*  $ Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while... Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?
Greets,
Felix


texts: How to prove that Bellman-Ford algorithm detects a negative cycle?

texts:
I have read that if we run the outer-loop of the Bellman-Ford algorithm for |V| times (where |V| is the number of nodes in the graph) and check if any distance has changed in the |V|th iteration (i.e. the last iteration) then there exists at least one negative weight cycle in the graph. But why does this work? Why only run for |V| times, why not more than that?

I am looking for a mathematical proof on why a change in the value of the distance of a node during the last iteration (|V|th iteration) implies that there is a negative weight cycle?

Can we detect all the nodes that are either reachable or are parts of the negative weight cycles after the |V|th iteration (can this also be proved mathematically)?

It would be helpful if someone can either provide the proofs and explanations or direct to the relevant resources.
Thank you.


texts: Monetary computations theory (manual/textbook)

texts:
My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some fraction (percentage), and I have to round the results to cents. Then I have to match the sum of what I calculated to the total amount (the sum of all chunks) multiplied by the same fraction (to make sure that precision loss didn't cause a lot of damage to the "big picture"), and if I have an error, I put it into the last (or first?) calculated value. Then I have to "balance" all the amounts for every start date I have (and, probably, for an end date too).

Example: $A_i$ is a monetary amount that is associated to a date $D_i$, $i\in [1, n]\subset\mathbb{N}$. I need to calculate commissions for every amount. I know the commission rate $cr$. Every commission amount should be rounded. So, I have $n$ commission amounts $CA_i$. The problem is that after rounding off the amounts, I get that ($\lceil x\rceil$ is the rounded value of $x$ in what follows):
$$\sum_{i=1}^n \lceil A_i*cr\rceil \neq \left\lceil\biggl(\sum_{i=1}^n A_i\biggr)*cr\right\rceil$$

Let's assume that I correct this error by adding the difference to $AC_n$. Now, I might have another problem: let $\{d_j\}_{1\leq j\leq m}$ be the set of all (distinct) dates $D_i$. So, I have that
$$\sum_{k=1}^? \lceil B_k cr\rceil \neq \left\lceil\biggl(\sum_{k=1}^? B_k\biggr)*cr\right\rceil$$
where $B_k = \{A_i \text{ such that } D_i = d\}$, for some date $d\in \{d_k\}$.
In other words, if I group the rounded results by date, there will still be an error compared to the total commission for this date. So, I should balance across every date (not forgetting about the total amount!)

This balancing is a very intuition-based approach, which might work or not. I've been looking for some formalization on the internet, but All I got was either the classic numerical analysis (after some brief introduction to floating point representation errors and rounding errors, it immediately goes to linear equations etc.) or just "Don't use floating point to represent money" articles. Are there any accessible sources on the specific topic of monetary calculations?


texts: Is this push-down automaton non-deterministic, as JFLAP states?

texts:
There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.
In this example it is detecting non-determinism in state q0:

The first symbol in the transition represents the symbol read as input; the second symbol represents the symbol extracted from the stack; and the third symbol is the symbol pushed to the stack. λ represents the empty symbol, so this is an empty transition without checking the stack or pushing anything to it.
I am surprised, as that state seems to fulfill the conditions for determinism for push-down automatons (if only because it only contains a single transition!). I would expect the next state to be q1 under any circumstance.
In comparison, JFLAP doesn't find any non-determinism here:

Mind you, the transition is the same, it only changes that this one adds something to the stack. Am I missing something or is JFLAP wrong in the first instance?


texts:
I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone provide some better explanation, analogy or an example to relate with some real world compiler?

Some notation first. By
$LSN=$
 I mean a compiler for language $L$
written in language $S$ that produces output language/machine code $N$.
This is a tombstone or T-diagrams.

  Compiling a Compiler

  Suppose we have cross-compiler for a new language L
     in implementation language S generating code for machine N.

  $LSN=$

  Suppose we also have an existing S compiler running on machine M
     implementing code for machine M:

  $SMM=$

  Run LSN through SMM to produce LMN

  Compiler Construction

  $LMN = LSN + SMM$


texts: "Insensitive" CNF/DNF SAT always satisfying same number of clauses

texts:
I came across this paper, which mentions an interesting variation on SAT:

  We call a CNF formula F insensitive if every total assignment α satisfies the same number of clauses of  F.

I hadn't come across this before. You can easily define the same property for DNF formulae as well.

Which brings me to the following question:

Given either a DNF or CNF formula, how hard is it to tell if the formula is insensitive?

It is clear that the decision problem "is this formula insensitive?" for both DNF and CNF is in co-NP, because two assignments satisfying different numbers of clauses serve as a "no" certificate. Its complement, which is "is this formula sensitive?" is in NP. But are these problems complete in their respective classes?

I suspect the answer is "yes," because most variants of SAT turn out to be NP-complete. But I don't know how to prove this, and I cannot find any information on "insensitive" formulas outside of this paper. Does any info on this exist?