texts: How to find the maximum independent set of a directed graph?

texts:
I'm trying to solve this problem.

  Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$.

I have to find the Maximum independent set and the size of this set.   The size can be found by König's theorem. But how can I find the Maximum Independent Set (i.e. which vertex are part of the set).

I did some search also and found something here:

If removing a vertex does not change minimum path cover then I can get the desired  result without that vertex.

But I don't understand the underlying theorem. Any help will be greatly helpful.


texts: Books on finite languages and automata theory with examples, problems and solutions

texts:
Can you suggest me a good book with illustrative examples and problems with solutions for finite languages and automata theory?

I tried Hopcroft's but it has mostly theory and not many problems with solutions.

Thanks! :)


texts: time complexity when power is involved in iteration

texts:
How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * <something>. I Just don't know what that <something> is.

public void timeComplexity(int[] arr){
    int n = arr.length;
    int sqrt = (int) Math.sqrt(n+1);
    for(int i=2; i<sqrt; i++){
        for(int k= (int) Math.pow(i,2); k < n; k+=i){
            //do some constant time work
        }
    }
}

Also consider the following two variations:

k starts at i (k=i or k=3) instead of k= (int) Math.pow(i,2).
k is incremented by some constant k++ instead of the variable i k+=i


texts: Find non-overlapping scheduled jobs with maximum cost

texts:
Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum.

Now I'm not sure if a greedy algorithm will do the trick. That is, sort by cost and always take the next job that doesn't intersect and with max cost between the two.

Is this equivalent to a knapsack problem? How could I approach it?


texts:
What is the simplest example of a rewriting system from binary strings to binary strings

$$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$

that can perform universal computation? Binary string rewriting systems in general can compute any computable function, but I have trouble finding particular instances that can by themselves compute any computable function given an appropriate input.  I've seen statements that a class of rewriting systems (e.g., the set of cyclic tag systems) is Turing-complete, but I'm looking for a single rewriting system that is universal.

I was thinking a self-modifying bitwise cyclic tag system might be a candidate, but I'm not sure how to interpret the output of such a system.


texts:
I am asked the following:
def myRemove( str, ch ):
 # Return a new string with the first occurrence of ch removed.  If there is none, return str.

Sample run
>>> myRemove( "abcdabcd", "a")
'bcdabcd'
>>> myRemove( "abcdabcd", "x")
'abcdabcd'
>>> myRemove( "abcdabcd", "d")
'abcabcd'

I have tried a few different methods but have not been able to figure the problem out. Here is my attempt:
def myRemove( str, ch ):
    for num in range (0, len(str)):
        if (str[num] == ch):
            return str[0:num] + str[num + 1:]
        else:
            return str

There is also an extension to this problem which asks : Return a new string with all occurrences of ch removed. If there are none, return str. However, since I have not been able to solve the first part, naturally I was not sure how to solve the second. Would appreciate any guidance.


texts: Unification algorithm that directly finds multiple substitutions?

texts:
Systems of formal logic generally have inference rules that
require certain expressions to be syntactically the same
in multiple steps.  Typically two steps are involved, as
for modus ponens, where the rule works with two steps of
the form "A" and "A => B", where A and B are arbitrary
boolean terms.  Such systems also generally allow substitution for free
variables of a proved statement.

Unification algorithms are described as finding a single substitution which can then be applied to both of the (let's say two)
proved statements to make appropriate parts the same after the substitution.  Careful presentations though require the two sets of free variables of the two proved statements be made
to have no names in common, a process
sometimes referred to as "uniqueification".

In this case the resulting substitution can be split into two disjoint parts, one with the substituted variables from the first statement and the other one with the substituted variables from the second statement, since substituting for a variable that is not present in a term has no effect.

So: Are there practical algorithms that work directly on the given
input terms without requiring the "uniqueification" step?  In my case it is desirable to keep the original variable names for presentation purposes.  It is also natural to present the result of the matching
as multiple substitutions, one into each of the statements
being matched. Hopefully such a unification algorithm would
directly yield two substitutions.

I am presuming that two substitutions are always enough for rules
that work on two input statements, but conceivably this is mistaken.


texts: When to dynamically compute data vs. when to use variables and update on demand?

texts:
Two scenarios:

Function is called and data is computed and returned.
Data is saved in variable, updated when required, data is retrieved from variable.

So I was wondering in what kind of scenarios one would be beneficial over the other?


texts: Trace dependents & precedents of a program in an imperative language

texts:
We have some programs in a very basic imperative language, the programs contain some basic features: assignment, condition, loop, scalar variables, 1-dimensional arrays and 2-dimensional arrays... Note that a variable or an array may not be initialized (or already hold a value before the execution of a program).

My question is... is there some existing work to identify all the dependents and precedents of a program by static analysis of the syntax, without executing the program? Or, is it very trivial to do that?

Without giving a formal definition of dependent and precedent, I illustrate these 2 notions by the following program:

a[2,2] = 0;
i = 1;
While i <= 10 do {
  a[2,2] = a[2,2] + a[i,1];
  i = i + 1
}

Just from the syntax of the program, we can say, the script precedes a[2,2], because the value of a[2,2] is totally determined by the execution of the program. Also, we can say, the script depends on a[1,1] to a[10, 1], because the values of a[1,1] to a[10, 1] determine the running of the program.

I guess roughly we can say, if a variable is on the right side of the first assignment containing it, the script depends on it; if a variable ever appears on the left side of an assignment, the script precedes it. A variable can be both precedent and dependent for a script at same time.

So, is it really that trivial? Which elements may complicate the issue? Is there some existing research?


texts:
The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that none of these subarrays can overlap.

Example: for an array [1, 2, 3, -2, 3, -10, 3], if $m = 2$, then the subarrays we take are [1, 2, 3, -2, 3] and [3], and their total sum is 10.

If $m = 4$, given the same array, then the subarrays we end up taking are [1, 2, 3], [3] and [3] and their total sum is 12 (we don't need the 4th subarray here).

Anyone has a solution?

--Edited
I do have a dumb solution.
First, write a helper function maxSum() that finds the max sum subset within an interval of the array using Kadane’s algorithm (linear runtime).

Then, construct a dp[] array with size $n$, where dp[i] stores the largest value of sum of contiguous subarray within the interval $[0, i]$.

dp[i] = maxSum(0, i)

Lastly, repeat this step for $m - 1$ times:

for each i: 0 <= i < n:
  for each k: 0 <= k < i:
    dp[i] = max(dp[i], dp[k] + maxSum(k + 1, i))

This solution is $O(n^2  m)$ in runtime and $O(n^2)$ in space if we store results from maxSum() in advance, and $O(n^3  m)$ in runtime $O(n)$ in space if we do not store it in advance. I believe there is definitely a way to do better.


texts: Representing Negative and Complex Numbers Using Lambda Calculus

texts: Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?


texts: Why we need to read memory on a write-miss?

texts: I noticed that in write-back caches, when the cpu wants to write to a block, it fetches the block from memory and then updates it. If the block is going to be overwritten and changed by processor, why does the cpu need to read that block from memory?


texts: Completeness and first order logic with Least fixed point operator (LFP)

texts: Is there any result about the extension of first order logic with least fixed point operator, being complete (as logic in general on infinite structures too) or not? In other words does the Goedel completeness theorem of first order logic extent to such FO-LFP logic ?


texts: Which fingerprinting/hashing algorithms support compounding?

texts:
The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as:

  Some fingerprinting algorithms allow the fingerprint of a composite file to be computed from the fingerprints of its constituent parts.

I suspect compounding is not a commonly used term for describing this capability. I have failed to find any other algorithm that allows

hash(x + y) = hash(x) + hash(y)

Wikipedia is not always the most reliable source of information but the article for fingerprinting seems to imply that there are algorithms other than Rabin's fingerprinting method that support compounding. I'm probably not using the right terms for search but I could not find any.

So are there any hash functions (or fingerprinting algorithms) out there that supports this property?


texts: How does RAMDAC get notified about framebuffer write?

texts:
I'm learning computer graphics, and I read this course lecture in order to understand how graphics I/O works under the hood. But the following explanation was not very clear to me:

  The values in the framebuffer are converted from a digital (1s and 0s
  representation, the bits) to an analog signal that goes out to the
  monitor.  A video card’s RAMDAC performs this operation, once per
  frame.  This is done automatically (not controlled by your code), and
  the conversion can be done while writing to the framebuffer.

How does RAMDAC get notified about the framebuffer write? Is there an IOCTL required from OS? or there is a circuitry somewhere that maps the write to RAMDAC input?


texts: Best and worse case inputs for heap sort and quick sort?

texts:
So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?

Heap sort:
best case - nlogn
worst case - nlogn

Quick sort:
best case - nlogn
worst case - n^2

Where I get confused on these two is:

heap- Since the best and worst case are the same does it not matter
the input order? The number of comparisons and assignments will
always be the same? I imagine in a heap sort it may be the same since
the real work is done in the insertion, but the sorting only uses the
removal of the max/min heap? Is that why?
quick sort- This one I don't know for sure. I'm not sure what the
best case and worst case situations are for this. If its a already
sorted list of 10 strings for example wouldn't we always have to
choose the same amount of pivots to get complete the recursive
algorithm? Any help on this explanation would really help.


texts: Is the halting problem a matter of an encoding scheme ?

texts:
I was reading about the halting problem recently, there is a video on youtube where it tries to explain the halting problem easily (since it is complicated to explain).

So, (A,C & H) have different inputs, if we suppose that we can run the three inputs on a machine (x) using one encoding scheme (i.e encoding for chess = arthemtic), would that solve the halting problem ?

Is it a problem of encoding different forms of inputs to the machine itself, or is it a problem of always getting the right answer to the input ?


texts: Digraph problem relating in- and out-degrees

texts:
Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d_{D'}^+(u) \leq d_{D'}^-(v)$ holds for every arc $(u, v) \in A'$ in the subgraph $D' = (V, A')$, i.e. the out-degree of $u$ is not larger than the in-degree of $v$? Note that the degree constraints should hold in the subgraph $D'$.

This seems like a straight-forward problem, alas I am unable to connect it to some more familiar graph problem. I am mostly interested in its complexity.


texts:
I have the following problem:

given

a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds) is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=[a,b]$ for some $a\in \mathbb{Q}_0^+,b\in \mathbb{Q}_0^+\cup\{+\infty\}$ and $a\leq b$,
two vertices $s,t\in V$ and
an integer $h$ encoded in binary,

we have to decide whether or not there exist

a path in $G$, possibly with repeated vertices and edges, $v_0 \cdot v_1 \cdots v_{n-1}\cdot v_n$, with $v_0=s$ and $v_n=t$ and
a list of values $d_0,\ldots,d_n\in\mathbb{Q}_0^+$,
such that $\sum_{i=0}^n d_i = h$ and for all $i=0,\ldots, n$, $d_i\in d(v_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE.
We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Is this problem in NP?


texts: Is polynomial over x with real roots decidable?

texts:
Today while I'm looking at definition of Algorithm from Sipser's textbook, he defined the following language:
$$D_1 = \{ p \mid\ p\text{ is polynomial over }x\text{ with integral roots}\}$$.
This language is decidable since we can bound the integral roots between two values and we can try all possible values between these two numbers.
Now, I'm thinking about a the following language:
$$D_{1}^* = \{ p \mid\ p\text{ is polynomial over }x\text{ with }\mathbf{real}\text{ roots}\}$$
Is this language $D_{1}^*$ decidable? I don't think so since we have an infinite number of solutions between any two numbers in real numbers. Is my argument correct?


texts: Finding the regular expression equivalent for the given finite automaton

texts:
This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression.

On inspecting the given automata, I started deducing the expressions that it accepts and tried to find a pattern, and this is what I was able to figure out -

The automata makes the following transitions to a final state upon said input -

$q_1 to \ q_3$ on input of a single symbol $b$, $a^*b$, $ba^*$, or $a^*ba^*$.
Traversing through the cycle $q_1,q_3,q_2$ (and so on repeating) on input of  $(a^*b^4a^*)^*$, a  $((a^*b)^4)^*$.

Now the equivalent regular expression must be the sum of all these expressions,

R = $b + (a^*b) + (ba^*) + (a^*ba^*) + (a^*b^4a^*)^* + ((a^*b)^4)^*$.

Is there a better, concise expression for this or am I missing something? If not, How do I approach the simplification process of this expression?


texts: Maximum I/O Data Transfer if DMA is used

texts:
I was reading lecture notes of Universiti Malaysia Perlis when I am came across following question:

  A computer consists of a CPU and an I/O device $D$ connected to main
  memory $M$ via a shared bus with a data bus width of one word
  $(16-bits)$. The CPU can execute a maximum of $10^6$ instructions per
  second. An average instruction requires $five $ processor cycles,
  $three$  of which use the memory bus. A memory read or write operation
  uses $one$  processor cycle. Suppose that the CPU is continuously
  executing “background” programs that require $95$% of its
  instruction execution rate but not any I/O instructions.  Now very
  large blocks of data are to be transferred between $M $ and $D$.

  Estimate the rate if DMA transfer is used.

P.S. Assume that one processor cycle equals one bus cycle.

The answer says:

$$10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6$$

Can someone explain the reasoning behind the answer ?

I could understand that $0.05$ is percent of time devoted by CPU
and $0.95$ is the percent of time devoted by DMA, but what about $5$ and $2$ ?
If it has something to do with cycles, then I did not understand the logic.


texts:
The Eulidean distance function $d$ of $x$ and $y$ is given by:

$
d(x,y)=\sqrt{x^2-y^2}
$

Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. We could even assume that $x,y$ have precision $n$ decimal digits. Any facilitating representations of rational or real values $x,y$ that carries "enough" information is good. $x,y$ could also be assumed to be only positive.

Can the Euclidean distance function be computed using only XOR's? If this cannot be achieved, what other boolean functions would be needed?


texts: Stuck in converting finite automata to its corresponding regular expression

texts:
I'm trying to convert the following finite automata (DFA) to its corresponding regular expression using state elimination algorithm.

For this I'm following this link. The answer of that question has following example.

But in this sample automata, there is no state between the two looping transitions. For example there is no state between transition q to r and back r to q. But in my question, there is three such cases as mentioned in the above 1st diagram. For example there is a state IV between the transition III to V and back V to III, via a. For another example, there is three intermediate states between transition I to V and back V to I via b.

I've tried to search such case on INTERNET, but can't found such issue. I've tried to attempt this question and could eliminated the II state, as following:

I'm stuck in eliminating state I, III and IV. Suppose I remove state III, than where should the transition from V to III via a can be placed? If I eliminate state IV, what will happen to transition IV to I?

Is there any general method for this type of cases? Any help will be appreciated.

Thank you very much in advance!


texts: Is VHDL a description language for a Boolean circuit or are both concepts unrelated

texts:
I am looking for a way to translate basic c programs (subset of c or java or some declarative programming language) to a Boolean circuit.

I know that Turing machines are reducible to Boolean circuits in theory, so this should be possible.

However, rather than re-writting things, I know that most EDA tools such as Vivado or ModelSim can take C code and generate VHDL or Verilog... even C++ code.

So would the VHDL code be equivalent to a Boolean circuit?


texts: Is there a OSI model equivalent for describing the abstract layers present in performing a computation for an operating system?

texts:
In describing where a system vulnerability exists, I often find a need for a model that partitions a operating system and its components into abstraction layers. Similar to how the Open Systems Interconnection Network Stack Model (OSI Stack) does for computer networks and communications.

Does something like this already exist?

I can not find anything like it online. Neither was it taught to me in my schooling. Maybe I am searching for the wrong things.

As a first pass of what I am expecting, I imagine the layers possibly involving:

Physical Layer
System bus (Bus Layer)
Device controller (Controller Layer)
Application Binary Interface (Hardware Interface Layer) (Hardware side of the boundary)
Hardware Abstraction Layer (HAL)(Software Interface Layer) (Software side of the boundary)
Device driver (Driver Layer)
Kernel (Kernel Layer)
Applications (API Layer)


texts: Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

texts:
I need help with the following:
Let $k\in \mathbb{N}$, define:
$L^k=DSPACE(O(log^k(n)))$
$NL^k=NSPACE(O(log^k(n)))$
and:
$PolyL=\bigcup_{k=1}^{\infty}L^k$
$PolyNL=\bigcup_{k=1}^{\infty}NL^k$

I need to prove, disprove or to determine if it is an open question:
1. For every $k\in \mathbb{N}$ it holds that $NL^k\subseteq L^{2k}$
2. There exist $k\in \mathbb{N}$ s.t. $L^k=L^{k+1}$

The first one is easy, since it is almost immediately the result of Savitch's theorem.
The second one I'm not sure...  I'd love to get some lead there.


texts: Reordering similar elements together within an array

texts:
I have a requirement where I need to group similar elements together within an original list.
For example:
I/P array:
[1, 2, 3, A1, B1, 4, B2, 5, 6, C1, B3, B4, 7, 8, 9, 10, A2, A3, 11, 12, A4, C2, D1]
Now I would like to group the elements starting with an alphabet such that all the elements belonging to a specific alphabet are together and would be placed right after the first occurrence of that alphabet.
O/P array:
[1, 2, 3, A1, A2, A3, A4, B1, B2, B3, B4, 4, 5, 6, C1, C2, 7, 8, 9, 10, 11, 12, D1]
One trivial solution that I came up with is to maintain a HashMap denoting the alphabets and its elements, Map<Character, Queue<Element>> and do the following steps:

Iterate through the list and if an alphabet is encountered, do one of the following:
1.1 If the alphabet doesn't exist in the map, add it to the map with an empty queue, map.put('A', new LinkedList<>())
1.2 If it exists in the map, then remove it from the original list and add it to its corresponding queue in the map, list.remove(element) and map.get('A').add(element)

Iterate through the original list again and when an alphabet is encountered, add its corresponding queue from the map right after it.

I think this solution would work but I am not sure if it might fail for an edge case or if it is an optimal one(even though its complexity is O(n)).
Can anyone suggest a better alternative?


texts: How does mathematical software evaluate symbolic sums?

texts:
Wolfram alpha is able to compute this sum:
$$ \sum_{j=1}^n \binom{j}{2} = \frac{1}{6}(n-1)n(n+1). $$

How can Wolfram alpha do it? What kind of algorithm does it use?


texts:
Offline Problem

  I have a graph $\mathcal{G} = (\mathcal{D} \cup \mathcal{A},
\mathcal{E})$. Each edge $e \in \mathcal{E}$ between the two vertex
  sets $\mathcal{D}$ and $\mathcal{A}$ has an associated weight $w_e$.
  Also, each vertex in $\mathcal{A}$ has a quota $Q$ i.e. each vertex in
  $\mathcal{A}$ can match with at most $Q$ vertices in $\mathcal{D}$. I
  need to find a matching between $\mathcal{D}$ and $\mathcal{A}$, such
  that the sum of weights is maximized.

Online Version

  The vertices $\mathcal{D}$ arrive one-by-one and upon arrival, all the
  corresponding weights to the vertex set $\mathcal{A}$ is revealed. On
  each arrival, I need to match the vertex in  $\mathcal{D}$ with a
  vertex in $\mathcal{A}$, which cannot later be revoked. Again, note
  that each vertex in  $\mathcal{A}$ can be matched $Q$ times.

What I thought

Splitting approach: Split each vertex in $\mathcal{A}$ into $Q$ vertices such that:

The weights from a vertex in $\mathcal{D}$ is duplicated for each of the $Q$ vertices.
While matching, any one of the $Q$ vertices with same weights is chosen arbitrarily.

Thus, it turns into a one-to-one matching problem.

From this paper, the online version of such a problem can be solved with an algorithm with a competitive ratio of $2n-1$ where $n$ is the number of vertices. However, this splitting approach leads to an increase in the size of $n$ i.e. $n = |\mathcal{A}| Q + |\mathcal{D}|$, which leads to poor performance if quota $Q$ is large.

Is there a better alternative approach?
I will be grateful anyone can point me towards any relevant resources.


texts:
I am learning compiler in my Uni. I have been through all major compiler techniques like top-down parsing, bottom-up parsing, Lexical analyzer, Symbol table, etc. I have a good understanding of them, but I am still confused about the course.

What is the point of learning all these things? What are their applications? Where these applications are used? The main point is, if someone asks me, Why Compiler? What is the benefit of taking this course?


texts: How to Optimize Algorithm for Many Queries

texts: I'm approaching the following problem: Given some input array $A$ of length $n$, and integer tuple $(j,k)$, I want to determine if there exists a contiguous subarray of length $j$ with all elements greater than $k$. The $O(n)$ algorithm is straightforward, but becomes inefficient when confronting a modified version of this problem, which involves an input array A and a series of $n$ inputs $(j, k)$. How can I find an algorithm for solving this modified problem that performs strictly better than $O(n^2)$?


texts: Show that regular languages are closed under Mix operations

texts:
Let $L_1, L_2$, two regular languages and the operations:

$$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in L_1 , b_1b_2\ldots b_n\in L_2\}$$

$$Mix_2(L_1, L_2) = \{ x_1y_1x_2y_2\ldots x_ny_n | n\ge 0 \land x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n\in\Sigma^* , x_1x_2\ldots x_n\in L_1 \land y_1y_2\ldots y_n\in L_2\}$$

  Prove that regular languages are closed under $Mix_1$ and $Mix_2$ operations.

So for the first operation:
Let $D_1, D_2$, two DFA's accepting $L_1, L_2$, respectively. We define $D = (Q,\Sigma, \delta, q_0, F)$.

Where $Q = Q_1 \cup Q_2$. The transition function, $\delta$ will behave as $\delta_1$ and $\delta_2$. But in addition, Let's define $n = \left|\Sigma\right|$, then we make $n$ transitions from every $q_i\in Q_1$ to $q_j\in Q_2$ (and vice versa) for every $\sigma \in \Sigma$.

So it's pretty easy to see that $D$ accepts $Mix_1(L_1, L_2)$.

Question:
How can I show that regular languages are closed under $Mix_2$?


texts: Using 2-opt Heuristic in a Genetic Algorithm for TSP

texts:
I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf) and I saw in the same paper that he uses the 2-opt heuristic (and the 3-opt one) on every new child, so I went ahead and did the same.

Using this definition of the 2-opt (https://en.wikipedia.org/wiki/2-opt) I implemented their following pseudo-code:

  repeat until no improvement is made {
       start_again:
       best_distance = calculateTotalDistance(existing_route)
       for (i = 1; i < number of nodes eligible to be swapped - 1; i++) {
           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
               new_route = 2optSwap(existing_route, i, k)
               new_distance = calculateTotalDistance(new_route)
               if (new_distance < best_distance) {
                   existing_route = new_route
                   goto start_again
               }
           }
       }
   }

The problem with my class is that it takes way too much time when tested on a 51 cities instance (not to mention that 1 generation takes more than 20 minutes in the a280 instance)..

Is there a better approach to this algorithm? A faster/more robust way of improving the new children?


texts: Avoiding loops in Bellman-Ford algorithm

texts: If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not more than once so effectively avoiding loops? I would appreciate if an answer will contain a link to a paper.


texts:
It's said that constant references within a program are replaced by the value at compile time, where as, variable references will need to be looked up at run time - making them slower.

Yeah, it sounds faster, but won't they ultimately both be locations in memory (that will have to be looked up), with the difference being that the variable can be altered?


texts: SAT for positive CNF clauses with exactly half of the variables being true

texts:
I am focusing here on positive even SAT problems, that is a CNF for which all literals are positive, and in which an even number  n of variables occur. This is obviously trivial : just set all variables to true and all clauses are satisfied. The same if we look for an assignment that would have all but one variables being true (unless the problem is 1-SAT, which is also trivial)

But I am wondering if we could find an algorithm that searches for some solution (or proves the absence of solutions) with exactly half of the variables being true, the other half being false.
Have you an idea of how to create this algorithm ? And what could be its complexity ?


texts: Distributed systems according to Lamport?

texts:
I need some clarification over the following quotation of Leslie Lamport:

  A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.

I see how a distributed system can be modeled as the product of several particular sequential state machines.

I understand that by totally ordering input requests, one can duplicate a given sequential state machine over several computers, and make sure that all input requests are processed in the same order at every computer, and thus ensuring that the individual local states are coherent.

What I don't understand is how this mechanism is sufficient to implement ANY distributed system. At least it's sufficient to duplicate a sequential state machine, but isn't that a very particular case of a distributed system?


texts: Counting substrings that belong to a regular language

texts:
Given a regular language $L$ and a string $x$ give an efficient algorithm to count the occurrences of substrings $x[i,j] \in L$.
More in particular, I am looking for a linear time algorithm in the length of the string $|x|$, for a given deterministic automaton $M$ accepting the language $L$.
This question is meant to generalize the question of counting substrings where each symbol occurs an even number of times, asked before here.


texts: How do I find an upper bound on this recurrence

texts:
$f(n)=f(n-\sqrt{n})$

I believe $f(n)\in O(\sqrt{n})$

However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks then does anything change?


texts: Hardness of a special case of maximum matching

texts:
Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$  is the probability $p_{u,i}$ of $u$ purchasing the product $i$.
  Task: Assign each user exactly $k$ products so that the following objective function is maximized:
  $$\sum_{i \in I(U)} ({1-\prod_{u\in U(i)}{(1-p_{u,i})}})$$
  Where $I(U)\subseteq I$ is the set of products assigned to some user, and $U(i) \subseteq U$ is the set of users to whom a product $i$ is assigned.

Question: Is this problem NP-Hard?


texts: What is meant by "solvable by non deterministic algorithm in polynomial time"

texts:
In many textbooks NP problems are defined as:

  Set of all decision problems solvable by non deterministic algorithms in polynomial time

I couldn't understand the part "solvable by non deterministic algorithms". Could anyone please explain that?


texts: Finding a class of graphs for which vertex coloring is NP-hard

texts:
We know that for general graphs vertex coloring problem/ minimum clique cover problem are NP-hard and for perfect graphs, they can be solved in polynomial time. There are classes of graphs which are perfect, e.g., bipartite graphs, chordal graphs, linear graphs, etc.

My question is that:

Are there any families of graphs that we know for them vertex coloring problem/ minimum clique cover problem are NP-hard? I appreciate if someone can give the name of some of them or any reference for them (in case they exist).

I have a problem and I want to show that it is hard and I want to find such a family of graphs and use them as an instance for my problem.


texts: Students in classroom problem - Flow in network

texts:
I have room, which is opened some days in week, in different hours each day.

I have multiple students, each has time some days in week, in different hours.

Each student have to visit the room exactly once in the week, for exactly 50 minutes.

Room is unusable for 20 minutes after 2nd student the day, it means, that after the 2nd student have to be at least 20 minute break before 3rd. So something like this:
7:00-7:50
7:50-8:40
(20 mimutes break)
9:00-9:50
There is no break after 4th, 6th, ... student. Only after 2nd one.

How can I find best solution to this? I want to position all (or the most I can) students.

I've thought of using flow in network (see image). Groups (G1, G2, ...) group times (7:00, 7:05, ...) that are within 50 minutes of each other. Pairing student (S1, S2) with time would instantly disable any groups, that contains the time. But that would require to flow going IN->Student->Time-> to split into multiple groups ->Group1+Group2->OUT. How can I achieve this? How should I modify maximum flow search algorithms to do so?

Or is there better way how to do what I'm trying to accomplish?


texts: Find an infinite set of strings that are compressable better than in $O(\log n)$ space

texts:
The task is to find an infinite set of strings $a_1,a_2\ldots$, where $|a_{i+1}|>|a_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a_i)|=o(\log_2 |a_i|)$ with $i\to\infty$.

I have considered a set of strings with minimal entropy: $a_1=b, a_2=bb$, etc. The optimal compression algorithm for these strings is $f : a_i\mapsto |a_i|$, but this compresses each string only to $O(\log i)$ space.


texts: Efficient algorithm for determining if $\pm c_1 \pm c_2 \dots \pm c_n = 0$

texts:
Suppose that we're given $n$ integers $c_1, c_2, \dots, c_n$. We want
  to know if there is any assignment of $+$ and $-$ signs such that

  $$ \pm c_1 \pm c_2 \dots \pm c_n = 0. $$

Does anyone know of a polynomial-time way to do this? Since there are $n$ integers, there are $2^n$ assignments of signs to consider, which grows rather quickly.

I've tried to phrase this problem in such a way that I can make use of dynamic programming, but DP usually lends itself to optimization sorts of problems, and this problem does not fall into that category (at least as stated).


texts: Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and evaluates $n$ expressions to optimize each entry.


texts:
In my theoretical computer science book I have the following statement regarding the space complexity of $f(n)=2^n$:

$$\log(n) = O(f(n))$$

I can't understand how this is true, any help will be greatly appreciated.


texts: Can there be a strict transaction that is not 2Phase?

texts: I am confused about the definition of a strict transaction. What is the difference between a transaction that is strict and a transaction that is both strict and 2 phase?


texts:
In Types and Programming Languages by Pierce,

  The level of types contains two sorts of expressions.

  First, there are proper
  types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited
  by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true
  does not.)

  Then there are type operators like Pair and λX.X→X, which do not them-
  selves classify terms (it does not make sense to ask “What terms have type
  λX.X→X?”), but which can be applied to type arguments to form proper types
  like (λX.X→X)Nat that do classify terms.

Is →  a type operator? →  seems to me to take two types as arguments and return a function type.

Does it   belong to some kind?

I might miss it, but does TAPL say anything about it?

Similar questions for

x (for pairing two types, e.g. T1 x T2, c.f. Ch11).
∀X. in universal type ∀X.T in Figure 23-1 of Ch23 on p343
{∃X,} in existential type {∃X,T} in Figure 24-1 of Ch24 p366
λX:: . in type operator abstraction λX::K.S (c.f. Figure 29-1 in Ch29 on p446)
Space  in type operator application T1 T2 (c.f. Figure 29-1 in Ch29 on p446)

Thanks.


texts: Could anyone prove that this is a context free language or not?

texts:
Possible Duplicate:
  Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free

Can anyone prove that the following is a CFL? or not? why?

$$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ does not equal $w_2$}\}$$


texts:
I've been given a solution, included below and I do not see how it would reject a string where i=j.

The example given should reject an input string such as aabbcc where there are an equal number of a's an b's, so i=j, however I don't see how it would reject it. Wouldn't it just push 2 a's, transition to state 2, pop 2 a's, epsilon transition to state 4, read in the two c's without popping or pushing and then accept? Is the given solution wrong or am I missing something?


texts:
I am trying to learn haskell and could not configure it out, why following code snippet can not get compiled:

*Uncurry> applyTwice f x = f f x

<interactive>:14:20: error:
    • Occurs check: cannot construct the infinite type:
        t ~ t -> t2 -> t1
    • In the first argument of ‘f’, namely ‘f’
      In the expression: f f x
      In an equation for ‘applyTwice’: applyTwice f x = f f x
    • Relevant bindings include
        x :: t2 (bound at <interactive>:14:14)
        f :: t -> t2 -> t1 (bound at <interactive>:14:12)
        applyTwice :: (t -> t2 -> t1) -> t2 -> t1
          (bound at <interactive>:14:1)

This would be fine:

applyTwice f x = f (f x)

In haskell function application is left associative, the first code snippet would be apply like:

(f f) x

why (f f) x it is wrong?


texts: Smallest number with in a larger number with a certain length

texts:
I have a number with $n$ digits. I want to keep only $m$ digits out of it. What is the smallest possible $m$ digit number which can be generated from the larger number so that order of digits is retained.

Ex: 3422509739

I need the smallest 3 digit number by removing 7 digits with order retained which will be 039.


texts: Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

texts: One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there algorithms that are intended exactly for finding power of matrix and that are more efficient than sequential execution of matrix multiplication? I am particularly interested in parallel algorithms.


texts:
Is there any way to make recursion tree that satisfies the height
$h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?


texts:
I was asked in an interview to create a knapsack of only even items in n*C time, c being the capacity, n being the number of items to choose from. I tried approaching it with a third dimension, where it would be of height n and signify at each ij whether the knapsack with these maxes contains even numbers or not, but I think its incorrect and I can't code it.

Any suggestions?


texts:
Question : To show that any language $L \in NP$ is many one reducible to HP.

Let $L$ be a language in NP, it means there exist a non-deterministic Turing machine for $L$. Let $x$ be a input string to this non-deterministic Turing machine, now I have come up with $f(x)$ such that $x \in L \equiv f(x) \in $HP and $f$ should be computable function. $f$ will be a function which takes $x$ string as an input and gives $M.y$(. means concatenation) as output, where $M$ the encoding of an Turing machine and $y$ is just a string.


texts: Define the time complexity of Kruskal's algorithm as function

texts:
I am trying to define the time complexity of Kruskal's algorithm as function dependant on:

the number of vertices V
the number of edges E
the time complexity of verifying, whether two edges don't form a cycle Ec(V)
the time complexity of connecting two sets of vertices Vc(V)

The edges are unsorted and I know the time complexity of sorting edges, which is Big O(E * log E).

I don't really know, how to solve this problem and I would be grateful for any help. Thanks!


texts: Finding the shortest path in a n-dimensional grid

texts: I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at a time. Is there an algorithm for this or at least one I can refer to?


texts: Separate Chaining hashing: time complexity of successful search

texts:
In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to determine it.

I tried to calculate the cost of access of each node in the list and to divide it by the number of elements of the list, but it doesn't seem correct.
$$1+\frac{m}{n}\cdot \sum _{i=0}^{\frac{n}{m}}\frac{n}{m}-i=1+\frac{n+m}{2m}$$


texts: What is the difference between the fundamental matrix and the essential matrix?

texts:
Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision?

How are they different, and how can each be used in computing the 3D position of a point imaged from multiple views?


texts: Is there an approximation algorithm for the three-person stable roommates problem?

texts:
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", is NP-complete.
I'm wondering if there's an approximation algorithm. This is for a specific use case - grouping people into tables for conversation, based on their preferences - and it doesn't need to be perfect.
While it would be interesting to know if such an article has been described in an academic paper, I'm primarily looking for an implementation of such an algorithm (in any language).
An algorithm for a foursome roommates version would also be interesting.


texts: How can I embed a Knowledge Graph in a vector space?

texts:
I am interested in embedding a Knowledge Graph in a vector space jointly with logical rules.

Through Google, the best work I have found about that is Tim Rocktäschel's paper Injecting Logical Background Knowledge into Embeddings for Relation Extraction.

The problem is that there is no throughly explanation about the matrix factorization in the paper or in Tim Rocktäschel's thesis or lectures.

My question is: What is the meaning of the rows of the matrix P x k and the columnns of k x R?


texts:
For example $-\tfrac9{16}$.

$$\tfrac{9}{16} = \tfrac{1}{16}+\tfrac12 = 0.1001\,,$$
which when normalised becomes $0.1001\times 2^0$. Can its mantissa be $0.0001001$ in 8 bits?

If so, as $-\tfrac9{16}$ is negative, twos' complement is done to make its mantissa $1.1110111$.
How do we normalise that?


texts: Maximum number of steps a Turing machine makes

texts:
Given the Turing machine $M = (  \{q_0, q_1, q_2. q_3,q_4\}, \Sigma= \{a, b, c \}, \Gamma = \{a, b, c, \}, \delta, q_0, , \{q_4\} )$
where $q_0$ is the start state, $q_4$ the end state and  the blank symbol. $\delta$ is defined as:

Let $w$ be any word of length $n$ accepted by the Turing machine $M$. Is it always true, that $M$  will reach $q_4$ in maximum of $1.5 \cdot
 (n+5)$ steps?

Is there a general strategy for this or do we just try different inputs until we find a contradiction? If none is found, how do we go about proving such a statement?


texts:
As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation problem) is the puzzle of defining the shortest possible regular expression that accepts every word in set A and no word in set B.  Norvig's post includes an algorithm for generating a reasonably short candidate, and he notes that his approach involves solving an NP-complete Set Cover problem, but he's also careful to point out that his approach doesn't consider every possible regular expression, and of course his isn't necessarily the only algorithm, so his solutions aren't guaranteed to be optimal, and it's also possible that some other assuredly polynomial-time algorithm could find equivalent or better solutions.

For concreteness' sake and to avoid having to solve the optimization question, I think the most natural formulation of Regular Expression Separation would be:

  Given two (finite) sets $A$ and $B$ of strings over some alphabet $\Sigma$, is there a regular expression of length $\leq k$ that accepts every string in $A$ and rejects every string in $B$?

Is anything known about the complexity of this particular separation problem?  (Note that since I've specified $A$ and $B$ as finite sets of strings, the natural notion of size for the problem is the total lengths of all strings in $A$ and $B$; this swamps any contribution from $k$). It seems highly likely to me that it is NP-complete (and in fact, I would expect the reduction to be to some sort of cover problem) but a few searches haven't turned up anything particularly useful.


texts: How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

texts:
I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.
If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$, how do I prove the language is not regular using pumping Lemma?
Also what is a pumping length, how do i know to assign a pumping length to the language stated above?


texts: A matrix rank problem over finite fields

texts:
I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here.

Let $M|\mathbf w$, where $M$ is a matrix and $\mathbf w$ is a subset of the column indices, denote the matrix formed by selecting columns $\mathbf w$ from $M$.

Problem:

  Input: Positive integers $m$ and $n$, and a collection $\mathcal W=\{ \mathbf{w}_i \subset \{1,\cdots, n\} | i=1,\cdots,k \}$ of column indices.

  Output: Find a matrix $A=\left[ a_{ij} \right]_{m \times n}$, $a_{ij} \in \mathrm{GF}(p^q)$ such that for each $\mathbf{w}_i$, $i=1,\cdots, k$, rank of $A|\mathbf{w}_i$ is $|\mathbf{w}_i|$ or print IMPOSSIBLE if no such matrix exists.

For the case $m \ge n$ (i.e., matrix $A$ has more rows than columns), solving the problem is simple: just assign random numbers from the finite field to the elements of matrix $A$, and you get a full rank matrix with probability more than $1-\frac{2}{p^q}$. Any full rank matrix works in this case because any subset of the columns of matrix $A$ is also full rank.

For the case $m < n$ (i.e., matrix $A$ has more columns than rows), the problem seems different.
A full rank matrix $A$ is not sufficient (nor necessary too).

A difficult case is described here:
let $w$ be a positive integer. Let $m=w$ and let $n$ be arbitrarily large.
Let $\mathcal W$ contain all the subsets of the column indices of size $w$, so $k=|\mathcal W|=\theta(n^w)$.
It means that any column contributes to $\theta(n^{w-1})$ of $\mathbf w_i$'s.
In other words, any assignment to a column should avoid collisions to $\theta(n^{w-1})$ subsets of $\mathbf w_i$.
I guess that it means a random assignment to the whole matrix $A$ does not give a guaranteed constant probability.

If $\mathbf w_i$'s are not overlapping, one solution is to solve one $\mathbf w_i$ at a time. Because each $\mathbf w_i$ can be solved in poly-time, the whole thing can be solved in poly-time too. But what if $\mathbf w_i$'s are overlapping?


texts: Computing the intersection of N sets over an M-element universe

texts:
Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$.

1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$?

2.) I am also looking for a good parallel and a good distributed algorithm.


texts: Correctness of algorithm to find maximum in array

texts:
I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction.

ans=-infinity
for (i=0; i<n; i++)
    ans= max(ans, A[i])

where A[0:n-1] is array and max is the function to return maximum of its two arguments.

What I am doing:

Base case: i=0, ans= max(-infinity,A[0])=A[0], as only one element has been processsed, it is maximum.

Induction Hypothesis: i=k<n-1, assume the algorithm correctly find maximum upto k iterations.

Inductive Step: i=k+1, let ans_{i} denote maximum element obtained by algorithm upto i steps and let ans'_{i} denote another maximum element from array A[0:i-1].

Then from induction hypothsis, ans_{k} = ans'_{k}

Now, for the sake of contradiction, assume ans_{k+1} < ans'_{k+1}

Now, how should I proceed to show this contradiction ?

Any suggestion? Should I change this approach ?


texts: Why does attempting to estimate the entropy of text by randomly choosing chars in it and counting how often they are equal give wildly wrong results?

texts:
Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are equal, give wildly wrong results? Here is a MatLab program that exemplifies that, also available on my blog:
% Ovo je MatLabski program koji uspoređuje rezultate koje daje moj algoritam
% procjenjivanja entropije s rezultatima koje daje Shannonov algoritam.
suglasnici = 'bcdfghjklmnpqrstvwxyz';
testni_stringovi=cell(100 - length(suglasnici) + 1, 1);
for koliko_cemo_staviti_b_ova = 100 - length(suglasnici) + 1 : -1 : 1
  for i = 1 : koliko_cemo_staviti_b_ova
    testni_stringovi{koliko_cemo_staviti_b_ova} = [
      testni_stringovi{koliko_cemo_staviti_b_ova} 'b'
    ];
  end
  for i = 1 : 100 - koliko_cemo_staviti_b_ova
    testni_stringovi{koliko_cemo_staviti_b_ova} = [
        testni_stringovi{koliko_cemo_staviti_b_ova} suglasnici(int32(floor((i - 1) / (100 - koliko_cemo_staviti_b_ova) * (length(suglasnici) - 1))) + strfind(suglasnici, 'c'))
        ];
  end
end
samarzijine_entropije = [];
shannonove_entropije = [];
for i = 1 : length(testni_stringovi)
  str = testni_stringovi{i};
  samarzijine_entropije = [samarzijine_entropije samarzijina_entropija(str)];
  shannonove_entropije = [shannonove_entropije shannonova_entropija(str, suglasnici)];
end
sgtitle('Usporedba Shannonove i Samarzijine entropije generiranih stringova');
subplot(1,2,1);
plot(shannonove_entropije, samarzijine_entropije);
xlabel('Shannonova entropija');
ylabel('Samarzijina entropija');
subplot(1,2,2);
plot(shannonove_entropije);
hold on;
plot(samarzijine_entropije);
xlabel('Broj b-ova u stringu');
ylabel('Entropija (bit/simbol)');
legend('Shannonova entropija', 'Samarzijina entropija');
function ret = shannonova_entropija(str, suglasnici)
  apsolutne_frekvencije = [];
  for i = 1 : length(suglasnici)
    apsolutne_frekvencije = [apsolutne_frekvencije 0];
  end
  for i = 1 : length(str)
    znak = str(i);
    apsolutne_frekvencije(strfind(suglasnici, znak)) = apsolutne_frekvencije(strfind(suglasnici, znak)) + 1;
  end
  relativne_frekvencije = apsolutne_frekvencije / length(str);
  ret = 0;
  for relativna_frekvencija = relativne_frekvencije
    if relativna_frekvencija > 0
      ret = ret - log2(relativna_frekvencija) * relativna_frekvencija;
    end
  end
end
function ret = samarzijina_entropija(str)
  broj_pokusaja = 10000;
  broj_pogodaka = 0;
  for i = 1 : broj_pokusaja
    prvi = int32(floor(rand() * length(str) + 1));
    drugi = int32(floor(rand() * length(str) + 1));
    if str(prvi) == str(drugi)
      broj_pogodaka = broj_pogodaka + 1;
    end
  end
  omjer_pogodaka = broj_pogodaka / broj_pokusaja;
  ret = -log2(omjer_pogodaka);
end

Here is what outputs:

So, what is going on here? I would expect the curve on the left to be approximately a y=x straight line, and the curves on the right to be approximately identical. But obviously, they are not. My algorithm for estimating the entropy gives close-to-correct results (or slightly overestimates them) when the entropy of the string in question is high, but it severely underestimates entropies of low-entropy strings.


texts: BSS-model Computational complexity of finding the roots of a polyomial

texts:
I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial with real coefficients.

Now, what exactly are the implications for my problem?

It is well-known that there is no formula that describes the roots of a polynomial of degree $\geq 5$ and, as far as I know, there is no general algorithm that computes the roots exactly. But are there results stating that the problem is computationally intractable in general? Or is it a common assumption? My question is not aiming at existence results or approximation algorithms but at the computational complexity of the problem and possible implications for my problem.

Note: My algorithm works in the Blum-Shub-Smale model, so the possibly infinite representations of the solutions don't bother me.


texts: At what tier does consistent hashing get implemented?

texts: Where does the code for consistent hashing reside? I have read how it is implemented (at a high level), but am unsure if it is exposed as a microservice between the web server and the app servers or on each app server (would seem unlikely).


texts: Beam search in the context of Genetic Algorithm

texts:
As per Machine Learning, Tom M. Mitchell, Indian Edition, pp. 249-262, it is mentioned that "genetic algorithms employ a randomized beam search method to seek a maximally fit hypothesis".

I have searched Wikipedia for the term beam search. I could understand that it is a variation of the breadth-first search method. I couldn't relate it to the concepts mentioned in the chapter of GA in the said book.

Please explain what is the beam search method in the context of GAs?


texts: Why does Lamport clocks increment on both message received and sent?

texts:
According to wikipedia, Lamport clocks need to be incremented when sending a message (time = time + 1) and when receiving a message (time = max(time_stamp, time) + 1).
In my implementation, Increment() is used when sending and Witness() is used when receiving, each of them following the previous rules.
I can't understand why not only Increment() actually increment the counter, that is why Witness() does not simply do time = max(time_stamp, time) instead of time = max(time_stamp, time) + 1.
The source of my confusion is the following scenario:

clock start at 1
a message is sent, clock is at 2
this message is seen locally, clock is now at 3

In this scenario, the clock incremented twice for the same message. Ideally it would just be one. Did I break something by witnessing the clock within the same process? Did I get something wrong?


texts: Can agent be autonomous without having consciousness?

texts:
My intuition is that 1) self-awareness (modeled through epistemic modal logics); 2) goal reasoning (e.g. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12292) and 3) consciousness (e.g. Integrated Information Theory) are the necessary and sufficient features for agent to be truly autonomous. Especially - consciousness is the key feature of autonomy. So - can truly autonomous (human-level autonomy) agent exist without consciousness?

Of course, I am thinking about autonomy not ultimate freedom. E.g. every agent can be autonomous but it will be bounded by 1) scarcity of resources; 2) ultimate goals and values which will be inscribed into agent by the humans.


texts:
My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question:

http://i.stack.imgur.com/RoPYG.png
(need a high reputation to post image)

From the above information can anyone tell me how I'm supposed to slot in values in order to work out the following practise question:

Sixteen-bit messages are transmitted using a Hamming code. How many check bits are needed to ensure that receiver can detect and correct single-bit errors?

Answer given to us is "5 check bits for a total of 21 bits".

Can anyone help me out with this please, as I expect it will come up on the exam, bu with another bit message size.


texts: Solving the recurrence of recursive insertion sort

texts:
I have solved that the recurrence of running time of the algorithm given as

$$
T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases}
$$

So the question is that solve the recurrence that I have solved above.

So this is my answer.

Case 1

Show that $T(n) = \Theta(n)$

Guess $T(n) \le dn^2 $

$T(n) \le d(n-1)^2 + cn$

$ = d(n^2-2n+1)+cn $

$ = dn^2 - (2d-c)n + d $

it solves when $d \ge (2d-c) n $, which is same as $ \frac{d}{2d-c} \ge n $

When $ \frac{d}{2d-c} \ge n $ , then $T(n) = O(n^2) $

So this process is equally in Case 2 which is showing $T(n) = \Omega (n^2)$.

Can you please check whether my approach is right?

Thanks for your help.


texts: Assigning $m$ balls to $n$ buckets - recursive algorithm

texts:
I came across the following problem and the answer to that problem:

Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, $(1,2,3)$ and $(3,2,1)$ are considered the same.
As an example, if $m = 3$ and $n = 2$, you should return 2, since there are two possibilities: $(1,2)$ and $(3,0)$.

Here is a recurrence which seems to work:
$$
f(m,n) =
\begin{cases}
1 & \text{if } m = 0 \text{ or } n = 1 \\
f(m,m) & \text{if } n > m \\
f(m,n-1) + f(m-n, n) & \text{if } 1 < n \leq m
\end{cases}
$$
This solution seem to work. However I don't understand how $f(m,n-1) + f(m-n,n)$ works. Why is it considering $m-n$ balls into $n$ bins?


texts: Find the fastest duration for a certain distance in a walk

texts:
I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic problems.

I'm looking for an algorithm that is able to find a answer to the following question:

If I ran 10 km this morning, how can I find out how fast my fastest kilometer was? (=searching for duration of fastest km)

My "run" datastructure consists of a list of data records, where each entry contains the following information:

timestamp in milliseconds
distance since start in meter

The data structure is arranged chronologically.

I already got a pretty straight forward solution to the problem, but I guess I would end up with a poor performance on this one:

start with the last entry of the list (i=size) and stop if available / remaining distance data[i] is smaller than 1km
search backwards in the list and calculate the distance delta for each entry until the delta for the distance is >= 1km OR (if we got a duration candidate from a previous iteration) the current calculated duration is already exceeding out current best.
if duration is too high start all over with i=i-1 until end condition is met
if a duration candidate is found remember this candidate decrease "i" and proceed with 1)

I really believe there must be an algorithm or better approach out there that can be applied to this question. Does anyone have an idea or can steer me in the right direction?


texts: Problem in Papadimitriou's "Computational Complexity" seems odd

texts:
I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition.

On page 66, we have:
3.4.1. Problem: For each of the following problems involving Turing machines determine whether or not it is recursive:

(a) Given a Turing machine $M$, does it halt on the empty string?
(b) Given a Turing machine $M$, is there a string for which is halts?
(c) Given a Turing machine $M$, does it ever write symbol $\sigma$?
(d) Given a Turing machine $M$, does it ever write a symbol different from the symbol currently scanned?
(e) Given a Turing machine $M$, is $L(M)$ empty? ($L(M)$ denotes here the language accepted by the Turing machine, not decided by it.)
(f) Given a Turing machine $M$, is $L(M)$ finite?
(g) Given two Turing machines $M$ and $M'$, is $L(M)=L(M')$?
Which of the non-recursive languages above are recursively enumerable?

Now, what puzzles me about this problem is that very little of the information it provides needs to be used in order to solve it. It is easy to see that all seven items describe non-trivial properties of Turing machines (that is, they are true for some Turing machines but not others) and, according to Rice's Theorem described on page 62, this means they cannot be recursive. There is barely any need to think at all about the properties described.

It seems a little odd that the author would go through the trouble of describing several different languages in some detail, when those details barely matter. It makes me wonder if my reasoning about Rice's Theorem is correct.

So my question is: is my reasoning correct that, according to Rice's Theorem, none of these described languages are recursive?

Incidentally, I think the last question in the problem is more interesting and does require more thinking about the individual languages. However, it sounds like a very secondary question, so it still makes me wonder about my answer to the main question.


texts: Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$

texts: Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.


texts: Showing that the class of regular languages are closed under merging / modified shuffle

texts:
Consider $ab$ and $cd$ which are two words. We merge these two into 6 possibilities: $abcd, acbd, acdb, cabd, cadb, cdab$

So in general, a merge of words/sequences $x, y ∈ Σ∗$ , is a word of length $|x| + |y|$ with both $x$ and $y$ as disjoint subsequences in it.

For two languages $L1$ and $L2$ their merge is defined as the set of all possible merges of two words $x ∈ L1, y ∈ L2$.

So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $ab$ and $cd$ example, as $b$ could not come before $a$).

I was thinking of just connecting the states of all $L1$ and $L2$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.

What's a basic idea on the construction I could do to prove this?


texts: m-functions in Turing's paper "On Computable Numbers and applications..."

texts:
I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem".

I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing uses a new way of writing a computation table for a machine. I am totally lost here. I don not understand the examples he gives (starting from page 236) to explain the idea of skeleton tables.

I need help with understanding how skeleton tables are to be read, and what they mean.


texts: Does infinite length strings lead to uncountable languages?

texts:
This answer says:

  We can have uncountable languages only if we allow words of infinite length.

So does that means any (finite / infinite) language or any (finite / infinite) set of languages over any (finite / infinite) alphabet will be uncountable of words have infinite length?

Let me simplify this by asking specifically for the simplest language of infinite length string:

  Does the language of "finite" number of words, each of which can be of "infinite length" and are based on "finite" alphabet is uncountable?


texts:
OS Book written by Galvin et all states that if page size is 4KB and size of virtual space is 32 bits then 2^(32-12) page entries would be required which is too huge to store in memory!!

Therefore it recommends to break it down by paging the inner page table as well. Now my question is how does that reduce memory requirements? Shouldn't inner page table and outer page table both be in memory and just the computational requirements reduce because inner page table can now be indexed quickly with the help of outer page table??


texts: Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

texts:
I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R".

I don't understand this because as it is called recursively, before performing any operations, the entire array is still split log(n) times. When following the binary tree diagram representing the recursion, we see (if n=16) it splits into 2x8, 4x4, 8x2, 16x1.

Since all of these splits occur prior to any merging, why is the auxiliary space O(n) and not O(nlog(n))?


texts: Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

texts:
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

  Which of the following statements is true?

  Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
  Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not
  correctly compute the optimal (i.e., minimum sum of edge lengths) tour
  of this instance.
  Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the
  cost of the optimal (i.e., minimum sum of edge lengths) tour.
  Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming
  Assignment #5). Deleting a vertex and all of its incident edges cannot
  increase the cost of the optimal (i.e., minimum sum of edge lengths)
  tour.

I argue as follows:

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.

However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?


texts: Solving recurrence $T(n) = T(n - 1) + n$ with substitution method

texts:
How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method?
I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$:
$$T(n) \leq O(n^2) \\  \leq c(n-1)^2+n \\ \leq cn^2+c-2cn+n$$
How can i continue?


texts: Origin of the terms "safety" and "liveness" for concurrent algorithm properties?

texts:
Properties of concurrent algorithms are usually divided into two categories:

Safety - something must not happen.

Properties in this category are for example partial correctness and sometimes deadlock-freedom (the latter depending on the author).
Liveness - something that must happen eventually.

Properties in this category are for example termination and starvation-freedom.

Which publication introduced these terms?

The oldest reference I was able to find is "Proving the Correctness of Multiprocess Programs" by Leslie Lamport, dated March 1977:

  To prove the correctness of a program, one must prove two essentially different types of properties about it, which we call safety and liveness properties. [...]

It does, however, not claim to introduce these terms.


texts: Prove/disprove - reverse topological sort transpose graph

texts:
I need to prove or disprove the following statement:

"Let $G$ be a directed acyclic graph, and $v_1v_2...v_k$ a topological sort of $G$.
Then $v_kv_{k-1}...v_1$ is a valid topological sort of the transposed graph $G^T$."

(The algorithm used is the one presented in CLRS 22.4)

I think the statement is correct.

My logic is that for every two vertices $v_i,v_j$ s.t $v_i<v_j$ in the sorting of $G$, one of two conditions hold:

A) $v_j$ is a decedent of $v_i$ in $G$, so in every topological sort of $G$, $v_i$ will be before $v_j$ in the sort.

B) or there's no path from $v_i$ to $v_j$ or the contrary, so $v_i$ and $v_j$ can switch places in the sorting, depending on the order that the DFS run on $G$.

From here, if condition A held then in the sorting of $G^T$, $v_j<v_i$, because now there's a path from $v_j$ to $v_i$, and if condition B held, then the order $v_j<v_i$ is valid for some topological sort of $G^T$. And so the sorting $v_kv_{k-1}...v_1$ is valid sort of $G^T$.

Something still doesn't feel right about this... would appreciate any help or comment.


texts: Best algorithm to find highest possible number of points from unique cards

texts:
I am looking for the optimum algorithm for the following:

10-15 players
Each player has between 20 and 40 cards.
Each card can have one of up to 200 possible characters, and a separate numerical rating (higher is better). Card's characters may duplicate between players, or in players hands. Ratings are highly unlikely to exactly duplicate, though they may be close.

I need to select 5 'active' cards from each players' hands to meet the following criteria:

All characters must be unique - no duplicates in any of the 'active' cards of any of the players, or across all players.
The total of the players' active cards' ratings must be as high as possible.

Right now I:
1) go through all players and find the highest rated card still available;
2) mark it as active for the player whose card it is; and
3) mark that character as used for all other players (so it doesn't get used again).

Repeat 1-3 until all players have 5 characters
This gives a pretty good result. But what if we had the following:
Player A:
Character 1, rating 100
Character 2, rating 99
Character 3, rating 98

Player B:
Character 1, rating 97
Character 4, rating 2
Character 5, rating 1

For the sake of the example, assume we only need two active cards per players.
If Player A uses Character 1 per my algorithm then:

Player A: Character 1 + 2 = rating 199
Player B: Character 4 + 5 = rating 3
Total rating 201

Instead if Player A doesn't use Character 1 then:

Player A: Character 2 + 3 = rating 197
Player B: Character 1 + 4 = rating 99
Total rating 296

So my algorithm does not produce the best team total rating.
Can anyone suggest a better algorithm, other than just brute force trying all the possible combinations to find the highest total rating? I wonder, for example, if there's something about finding the optimum ratings for each player and then adjusting them to avoid duplication with other players; or perhaps something completely different.


texts: Why do public key systems involve private keys?

texts: I read up the definition of a public key cryptosystem. It mentions there is a public key and a private key. That's confusing. Why is it called a "public key" system if it involves a private key as well?


texts: Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

texts:
Let f and g be two functions with integer range 0..m-1. They may keep state and interact with the world (for example setting a seed or reading the current time), calling them multiple times may produce different results. f and g can see each other's state, but cannot modify the other's state.

Assume at least one of f and g is a cryptographically secure pseudorandom number generator, but it is unknown which one. Is it possible to create a function h that uses f and g and behaves as a CSPRNG? h is not allowed to set or read external state directly, the only way it can modify or read state is by calling f and g and observing their results. h should work for any given f and g.

Of course, h is not allowed to use any "true" source of randomness, and ideally the construction should not involve passing randomness tests.

As a related problem, I believe that if f and g were perfectly random, then f + g (mod m) would also be perfectly random. But I think in this deterministic case, it's always possible to create a g such that it "cancels out" f in h. Not sure how to prove this.


texts: $2$-partition reduction for weighted completion time in scheduling

texts:
I've read about the reduction from $2$-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my understanding is at least in the right direction.

First, my understanding of the problem is that we would like to complete the jobs that have high weight the earliest possible, but since there isn't any preemption and given the release dates it's hard to figure out which jobs to do first.

So in order to prove $NP$-hardness in the weak sense, I construct an instance of $2$-partition as follows,

set task weights to $1$, set $r_j = 0$ for all tasks and add an extra task with $r_j = B$, and deadline $B+1$ and a processing time of $1$, weight $0$. We add this task to split the two subsets(as required by $2$-partition). Therefore if we can solve this problem in polynomial time we can also solve $2$-partition in polynomial time.

Is my intuition correct? Also I don't expect an answer, just maybe an explanation of what I'm doing wrong


texts:
In the scope of my scheduling research, the question has been raised on whether distance-preserving permutations can be constructed easily.

Suppose that our domain is the set of natural numbers up until $n$, that is: $D=\{1,2,...,n\}$ where $n\geq 1$.

A permutation $\pi$ is a distance-preserving permutation in my context is one that has the following property: $|\pi(i) - \pi(j)| = |i-j|$.

For example, the most trivial distance-preserving permutation I have come up with is the following: $\pi(i) = n-i+1$, which is the permutation that maps $1$ to $n$, $2$ to $n-1$, etc. It can be easily shown that $|\pi(i) - \pi(j)| = |i-j|$.

My intuition says that there are no more distance-preserving permutations, since if we draw this as a graph where the $x$-axis is the numbers in $D$ and the $y$-axis is the values $\pi(i)$ then we will have a $90$-degree cornered triangle with the corner facing north-east, its' equal edges being the distances $|i-j|$ and $|\pi(i) - \pi(j)|$.

Are there distance-preserving permutations other than the above trivial one?


texts: Can every two languages in $RE$ be reduced?

texts:
If $L_1,\, L_2 \in RE / R$, must there exist a (computable) many-one reduction between them?

I can prove that for every two languages in $R$ exists a reduction between them. A possible reduction $L_3 \leq L_4$ where $L_3,\, L_4\in R$ goes as follows:

given an input $x$ to $L_3$, run $M_3$ (it's TM), if it accepted, return an input that is in $L_4$. Else, return one that isn't (this works assuming $L_4\neq \emptyset,\, \Sigma^*$).

The above idea will not work in $RE$ because $M_3$ might not halt.

Is there a different way to construct a reduction $L_1\leq L_2$ where it us known that $L_1,\, L_2\in RE / R$?  Or is such a general reduction something that cannot be always achieved?


texts: What is the point of selection step in a genetic algorithm?

texts:
I'm reading about genetic algorithms, and I'm not sure I understand the point of selection step.Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

From what I understood till now we select a number of chromosomes (I still don't know how many should we select) and let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ? I'm not sure I got it right.Someone can clarify this for me ?

Thank you !


texts: Neural network to detect connected parameters

texts:
I have a list of configurations. Each configuration contains a number of parameters. The parameters have the same name but sometimes different values.
I now want a neural network, that can detect, which Parameters always have the same value when Parameter 1 has value 'A'.
I want to find out which Parameters are "related", so which parameters always change together and have always the same pair of values.


texts: Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

texts:
Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$   and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $.

I´ve made a program to check this statement and it seems that for any given $c>0,\forall n\geq16$  it holds, however i don´t know how to formally proof this ,because i can´t find any simplification for $t_b$.

I know that i must prove $ \exists c
 : \forall n \geq N:t_b(n) \leq c *t_a(n)$ using big-O-Notation.

A hint/solution-idea would be really great.


texts: Implications of truncation of numbers when converted into binary

texts:
I have been posed with a question whereby a computer truncates numbers to x number of digits. Due to this, if this computer is trying to store a decimal number which has a binary equivalent greater than x, it truncates the remaining digits producing a different binary number. However, this binary number is still an 'approximation' of what it should be, but of course is the equivalent of a different decimal number (close to what we were trying to store initially).

What problems can occur due to this incorrect storage of data?


texts:
I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive)  start with 0 and using a DFA. The operations are as follow:

increment x+1 and if x+1 is larger than 15 then x+1 goes to 0
decrement x-1 and if x-1 is less than 0 then x-1 goes to 15
multiplication: 2*x and if 2*x is larger than 15 then we take 2*x - 16
division: we simply take the floor of (x/2)

My initial though of the solution was as follow:

1) number the states as follow q0,q1,q2,...,q15 where q0 is the initial state. So the state represent the result of the arithmetic operations

2) the transitions between the states represent the arithmetic operations.

However, soon after I remembered my teacher saying that the DFA return a string of transitions.

My question is can we make the DFA return the final state only (so in my case if it returns qN then the result is N) ?
if not how should I solve this problem?


texts: Need resources to learn about Graph Spanners

texts:
I'm trying to learn about Graph Spanners. I have searched for it but unfortunately, I couldn't find any solid helpful resource related to this very topic.

I would highly appreciate if anyone can suggest me any specific book or online material which explains about Graph Spanners in detail.


texts: Selecting optimal order of questions to minimize total time

texts:
Suppose there is a tutorial session at a university.
We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$
students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be
the set of questions that a student has a doubt it. Assume that
$\forall 1 \leq j \leq n: Q_j \neq \phi$ and
$\bigcup_{1\leq j\leq n}Q_j = Q$.

Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time
taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the
time spent by $s_j$ in the tutorial session. We want to find out an
optimal permutation $\sigma$ in which questions are discussed
$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $\Sigma_{1\leq j \leq n}t_j$ is minimized.

Intuitively it seems that we can greedily discuss the question that the
most number of students (in the current iteration) have a doubt in.  Is the greedy algorithm correct?

Sidenote: By the way, I thought of this question after an actual tutorial
session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!


texts: Difference between Recursion Tree & Binary Tree

texts: What's the difference? is a Recursion tree private case of Binary tree?


texts: Why not polynomial-space reductions for $PSPACE$-hardness?

texts:
A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$.

Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$.

Why does we use time reductions instead of space reductions in this situation?


texts: Can a node of Radix tree which represents a valid key have one child?

texts:
Wikipedia says:

  a radix tree is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

Now they are situations where the parent of the child represent a valid key in the data set like this example:

from this answer. Obviously you can't merge "smiles" into "smiled" and "smile" or you are going to lose valid entries in your data set.

Here as much as I understood suggests, as seen in the image,:

that for a one child parent with valid key like "organ" to add a child which has the same value (but it is not a parent). When the parent gets two children then that auxiliary child can be removed.

This implementation however for example doesn't seem to care about breaking the "no parent with one child" rule, while adding a child node to a leaf.

So my question is that whether "no parent with on child" rule is coined into the definition of radix tree and if so what is the computational/space advantage of it. It seems to me the 4 solution to keep up with the rule leads  in both space and computational efficiency lost. If not then is it safe to say that Wikipedia definition need to be corrected?


texts: Adjust FCM algorithm with size constrains

texts:
I want to cluster a list of property addressed based on distance and limit the size of each cluster.

The properties are currently assigned to modules by discretion of managers. But I hope to develop a system to assign properties automatically based on minimized distance to module center and limit the size of properties and units in each cluster.

The number of clusters are predefined.

I found this article with the algorithm I'm looking for.

Clustering with Size Constraints

Please bear with me since I new to clustering and algorithm design. I get the idea of the algorithm in the article. But since I have very basic math and programming background, there're some details I'm not quite clear about.

So for the equation (4) in FCM Algorithm part, I don't understand what it means..

And for equation (8), I don't understand how it's obtained and what it's referring to in the description.

If anyone can help me with any of these, I'd much appreciated. Thanks!


texts: Can LOOP-Programm stop when its value goes below 0?

texts:
I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$.

The definition only says "Execute $P$, $x$ times" for the above program.

IT is perfectly clear for $x = 0$. However, I believe in order to keep the language simple the definition doesn't extend to the case $x < 0$.

If it were possible, then it would for instance basically shorten a $x_1\ div\ x_2$ operator to just one line:

x_0 = 0;
LOOP x_1 DO x_1 = x_1 - x_2; x_0 = x_0 + 1; END

If it is not possible, is there any other reason except for reasons of convention?


texts: Interesting problems that can be solved with algorithms

texts:
I need to write a blog post on a problem that can be solved algorithmically. I need to do two things:

1) I need to decide what the naive brute force method would be and touch on it's time and Space complexities.

2) I need to come up with a more elegant/ideal method to solve the problem, then discuss tradeoffs with the ideal method's time and space big O

Does anyone have ideas for an interesting topic I can cover? I'm not looking for the answers, just the topic to cover

Here is an example of something I could write about: https://medium.com/@hannahsquier/two-algorithms-for-solving-vigneres-cipher-in-ruby-77bf0b37507a#.go43z5vas


texts: Splitting a group of numbers into $k$ sorted groups

texts:
I have this first task:
You have a set of numbers $S =\{ \dots \}$  of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$
Your task is to write an algorithm (pseudo-code) that splits $S$ into $k$ sets (which have the same length each): $S_1 , S_2 , \dots, S_k$  such that all the numbers in $S_i$ are smaller than all the numbers in $S_{i+1}$ for all $1 \leq i \leq k-1$ in time complexity of $O(n \cdot k)$  (end of task 1)
The second (another question, but related to the first one) task is the same, but suggesting a faster algorithm - psuedo-code (time complexity -wise)
For example:
For $S = \{11,5,2,7,1,13,15,16 \}$ and $k = 4$ I would return (right to left):
$\{16, 15 \} , \{13, 11 \} , \{5, 7 \} , \{1, 2\}$
notice the order of the numbers inside these sets does not have to be in any particular order.
My go:
What have I not tried.. god:

I thought of doing a bucket sort.

Maybe choose a random pivot and do a select for each group.

Make $k$ empty sets of length $\frac{n}{k}$ each ("in advance") and then choose the $k$-th smaller elements each iteration.

make $k$ empty sets of length $\frac{n}{k}$ "in advance" and then putting each number in the first one, and once we come across a bigger number we move the smallest of them to the next set like this for the example above (explicit details below):

This is the algorithm I have so far (number 4):
First we have an empty $k=4$ sets of length $\frac{n}{k} = \frac{8}{4} = 2$  and then comes $11$, then $5$ :
$\{11 , 5 \}, \{ , \}, \{ , \}, \{ , \}$ and then $2$ comes but it's smaller than $5$ or $11$ so $\{11 , 5 \}, \{2 , \}, \{ , \}, \{ , \}$ then comes $7$ and it is larger than $5$ so it replaces it and moves the $5$ to the next set:
$\{11 , 7 \}, \{2 , 5\}, \{ , \}, \{ , \}$ etc...
it should work but I am not sure what is the running complexity. For each set ($k$ times) I have to run $\frac{n}{k}$ iterations (the length of each subset)
Nothing works if I understand it correctly. Nothing here gives me time complexity of $O(n \cdot k)$ ...
I did not even start thinking about the second solution.. because I can't get pass the first one..
I would appreciate your help!


texts: If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something else?


texts: Compiler design: How are the initialize conditions for data-flow problems set?

texts:
Consider a typical data-flow problem, for example, reaching definitions or available expressions.

I am struggling to understand how $IN$ and $OUT$ of the basic blocks are initialized. For example, for available expressions, we initialize $OUT[B] = U$ for all $B$, that is we assign each $OUT[B]$ all expressions, while we assign $OUT[B] = \emptyset$ for the Reaching definitions initialization. Why do we assign $OUT[B] = U$ for available expressions? This seems kind of counter-intuitive given that for a basic block with no code, no expression is available?

Edit

To give more detail on what I mean by "Reaching definitions" and "Available Expressions".

Reaching definitions: Determine a set of definitions reaching the entry and exit of each block of the control flow graph, where a definition $d$ reaches a point $p$ if there is a path from the point immediately following $d$ to $p$, such that $d$ is not redefined along that path.

Available expressions: An expression $e$ is available at program point $p$ if $e$ is computed on every path to $p$ and the value of $e$ has not changed since the last time $e$ is computed on $p$.

Reaching definitions is a forward problem where the meet operator is union, while available expression is a forward problem where the meet operator is intersection.


texts: does mathematical function set in Genetic Programming can have two input values?

texts:
I create an individual in GP by using the full method. My individual trees have the same shape and size. I use a binary tree with all the leaves in maxdepth.

The problem is, I can not use the mathematical function set because it accepts two values. therefore I changed mathematical function set like sin (val1) to sin (val1+val2), sin (val1-val2) etc. in order to receive two values. ex

sin() become sin(+), sin(-), sin(/), sin(*)
round() become round(+), round(-), round(/), round(*)
sqrt() become sqrt(+), sqrt(-), sqrt(/), sqrt(*)

Is this allowed? If you can please show me the journal using this method.


texts: Applying dynamic programming to a simple two-person game of perfect information

texts:
A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to

I)  Subtract 2 from n
II) Subtract 3 from n
III)    Subtract 5 from n

We call the player who begin the game Adam and the other player Berta. The players alternate by applying on of the three rules to the number 0 or a negative number his/her opponent. If a player manages to produce the number 0 or a negative number he/she wins the game.

Here is an example of a game played by Adam and Berta (for n=15)

15 is given to Adam. He decides to subtract 5 leaving 15-5 = 10 to Berta
10 is given to Berta. She decides to subtract 3 leaving 11-3=8 to Beta
8 is given to Adam. He decides to subtract 2 leaving 8-2=6 to Berta
6 is given to Berta. She decides to subtract 2 leaving 6-2=4 to Adam
4 is given to Adam. He decides to subtract 5 producing -1 a negative number, Adam wins!

b) we define a one dimensional array X(1), X(2),X(3),..,X(n)

i)  X(j) =1 if Adam has a method to win when given the number j
ii) X(j)=0 if Adam has no method that guarantees that he wins when the given the number k

Calculate X(1),X(2),X(3)….,X(23),X(25)

What is X(8), X(13) and X(24)?     Answer should be of the form
boolean boolean boolean  so if X(8)=0 , X(13)=1 and X(24)=1 the correct answer is 011
Thus the correct answer is one of the following 000 001 010 011 100 101 110 111

My attempt is

n=8
Adam: 8-5=3
Berta: 3-3 =0
Berta wins  0

n=13
Adam=13-5=8
Berta: 8-3=5
Adam 5- 5
Adam wins 1

I get really stuck with 24, so far I have 01

Is there a method for this type of problem, i have been stuck on it for ages now.
Thanks in advance


texts: Efficient Algorithm to determine highly composited numbers

texts:
Im writing an algorithm to determine highly composited numbers.
But it's very unefficient with $\Omega(f(n)) = n³$.
Does someone know how i can make my code more efficient. Is my approach ok?

Here is my code:

import tools.Tools;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.TreeMap;

public class HighCompositeNumbers {

ArrayList<Long> hcnList = new ArrayList<>();

public HighCompositeNumbers(){
    hcnList.add(1L);
}

public TreeMap<Long, Long> primeFac(long n){
    final long limit = n;
    TreeMap<Long, Long> map = new TreeMap<>();
    for (long i=2; i<=limit/2+1; i+=1){
        long counter = 0;
        if (n % i == 0) map.put(i, 0L);
        while (n % i == 0) {
            n /= i;
            counter++;
        }
        if (counter != 0) map.put(i, counter);
    }
    return map;
}

public long numberOfDivisors(long n){
    TreeMap<Long, Long> map = primeFac(n);
    long divisors = 1;
    for (Long l : map.values()){
        divisors *= (l + 1);
    }
    return divisors;
}

public boolean isHighlyComposite(long n){
    long numOfDiv = numberOfDivisors(n);
    for (long i = n-1; i>=hcnList.get(hcnList.size()-1); i--){
        if (numberOfDivisors(i) >= numOfDiv) return false;
    }
    return true;
}

public static void main(String[] args) {
    long max = Tools.nextLong("max: ");
    HighCompositeNumbers hcn = new HighCompositeNumbers();
    //Tools.printHashMap(hcn.primeFac(max));

    for (long i=2L; i<= max; i++){
        if (hcn.isHighlyComposite(i)) hcn.hcnList.add(i);
    }

    System.out.println(hcn.hcnList);

}
}


texts: What is the complexity of timing a turing machine?

texts:
I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$.
It returns yes if $F(i)$ halts in less than $n$ steps, otherwise it returns no.
What is the time complexity of this problem in terms of $n$, is it $n\log n$ as it is similar to a universal Turing machine, or does the counting each step mean it takes longer.


texts: Which fields of Computer Science are involved in knowledge-based and text-based dialog systems?

texts:
One of my future goals is to know in depth about building a text-based dialog system to answer questions about a specific topic (say, Tolkien's legendarium), assume that I have a large body of article-formed facts about that topic (say, Wikipedia). Excluding the "Computer Engineering" part of the problem, I have a question:

Which (narrow enough) fields of Computer Science are involved in the problem, and how deep is the involvement of each of them? With my knowledge right now, I can only pinpoint the field of Natural Language Processing (NLP), but I don't know how deep it's involved in the problem and whether we can narrow it more. Also, I just feel that Information Retrieval (IR) and Knowledge-based System (KBS) are involved, but actually I don't know them too well. That's all I have for now.

Addition: I'll use the example of the Tolkien's legendarium to make sample facts and a sample question. Sample facts: "Melkor (known in Sindarin as Morgoth), the evil Vala, corrupted many Maiar into his service. These included Sauron, the main antagonist of The Lord of the Rings, and the Balrogs, his demons of flame and shadow" (from the Wikipedia page of Maia). The sample question: "List all named Maiar who were tempted and served under Morgoth."


texts: Do I have the right definition of VC dimension?

texts:
I am having some trouble understanding the notion of the VC dimension. The definition I have is the following:

  The VC dimension of a set of hypothesis functions $H$ is the cardinality of the largest set which $H$ can shatter. We say that $H$ shatters some set $S \subseteq \mathcal{X}$ if we can realise any labelings on $S$ using functions from $H$.

To me, this means that for any (countable) set of labels $L \subseteq \mathbb{Z}$, there is some $h \in H$ that provides a surjection $h: S \mapsto T$, where $T \subseteq \mathcal{X}$ with $|T| = |L| \leq |S|$. (There is then a trivial bijection from $T$ to $L$.)

Is this the correct interpretation?

The reason I ask is because the above interpretation leads me to think that the singleton set $H = \{h\}$ has $VC(H) = 1$, since it always sends a single point to a single point, so we can get any labelling we like on this single point by a trivial bijection.

That is, suppose we wanted to label the point $x \in \mathbb{R}$ as $l$, then $h: y \in \mathbb{R} \mapsto 0$ will do since we can just change the name of 0 to $l$. Note that this chosen $h$ does not shatter a two-set from $\mathbb{R}$, since we can only label the points in one distinct way.

However, I have read that the VC of a singleton is 0. I don't understand this.

(I see hypothesis functions $g: \mathcal{X} \to \{1, \dots, n\}$ as belonging to an equivalence class of functions that sends $\mathcal{X}$ to any set of size $n$. Please correct me if this is the wrong intuition.)


texts: Time Complexity proof for Segment Tree implementation of the ranged sum problem

texts:
I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.

However I'm not able to prove that the querying time is indeed $\mathcal{O}(\log n)$. This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is $4$ and so $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

But how do we prove this, perhaps by contradiction?

And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?

For example,
I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.