texts: Longest path in a cyclic, directed and weighted graph

texts:
I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights.

In my research so far I have found out that you need to generate -G from graph G and then run a shortest path algorithm on it to find the longest path in G. Of course this won't work if -G contains negative cycles. But that's excatly what I need to do. Consider following graph (which I created quickly in paint..):

The red letters are just there for identification. The red numbers are the value of the vertex and the blue numbers are the edge weights.
The edge weights are generated with the following formula:

$$ Weight = \frac{destination}{source} $$

I am looking for the longest path from A to F - but the longest simple path. That means that a vertex must not be visited more than once. By simply looking at it I can see that it is A - B - E - F. But if I tried to generate -G and then run the Bellman-Ford algorithm on it it would fail because there would be negative cycles like B - E - D - B.

I am aware that it is not possible if you look for paths in which a vertex can be visited more than once. But if you look for simple paths only, is it still not possible?


texts: reduction of independence problem and cluster problem

texts:
independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them.
cluster problem is: there is a simple and undirected graph, we are looking for the maximum number of the vertex in which there are proximity every two vertexes ( there is an edge between any two vertexes)
how can I reduct independent problem to cluster problem and vise versa?


texts: What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

texts:
Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently:

$IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$
$ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$

This is easily done by pre-computing the connected components of the graph. Both queries can run in $O(1)$ time.

If I also need to be able to add edges arbitrarily - $AddEdge(N_1, N_2)$ - then I can store the components in a disjoint-set data structure. Whenever an edge is added, if it connects two nodes in different components, I would merge those components. This adds $O(1)$ cost to $AddEdge$ and $O(InverseAckermann(|Nodes|))$ cost to $IsConnected$ and $ConnectedNodes$ (which might as well be $O(1)$).

If I also need to be able to remove edges arbitrarily, what is the best data structure to handle this situation? Is one known? To summarize, it should support the following operations efficiently:

$IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$.
$ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$.
$AddEdge(N_1, N_2)$ - adds an edge between two nodes. Note that $N_1$, $N_2$ or both might not have existed before.
$RemoveEdge(N_1, N_2)$ - removes an existing edge between two nodes.

(I am interested in this from the perspective of game development - this problem seems to occur in quite a few situations. Maybe the player can build power lines and we need to know whether a generator is connected to a building. Maybe the player can lock and unlock doors, and we need to know whether an enemy can reach the player. But it's a very general problem, so I've phrased it as such)


texts: Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?

texts: Equip any complexity classes $C$ and $B$ (to be more specific: any complexity classes that contain only decidable problems) with the same oracle $O$ that solves the halting problem for a Turing Machine. Is $C^O = B^O$ for any $B$ and $C$ that, again, only contain problems decidable by a TM with no access to an oracle (only the empty oracle)?


texts: Edge Constraint satisfaction in a Directed Graph Path?

texts:
Given a directed Graph and two vertices $S$ and $D$ (source and destination) such that each of its edges has a weight of the form:

$A_i+B_ix_i = V$

where $A_0$ is a non negative integer, $B_0$ is a positive integer, $x_i$ a variable that can take non negative integer values (each variable used only once in the graph).

Find a positive value $V$ such that it there exists a path from $S$ to $D$ in Graph such that $V$ satisfies all edges in that path.

Of course the trivial method would be testing each positive integer value of $V$. But this might take an exponential time. Is there something better we can do to achieve the solution in polynomial time, or that is the best we have ?


texts: About the complexity of learning probabilistic graphical models

texts: I guess that one way of measuring the complexity of learning a joint probability distribution is as its "sample complexity" (which is also sometimes known as its "distributional learning complexity"?) I wanted to know if any computation of these measures are known for probabilistic graphical models.


texts: I know that (1 + 0)* is the set of all bit strings; but isn't  1* + 0* the same thing?


texts: Find subsequence of maximal length simultaneously satisfying two ordering constraints

texts:
We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to arrange these fruits in such a way that the sorted list contains prices in ascending order and vitamin contents in descending order.

Example 1: $N = 4$ and $F = \{(2, 8), (5, 11), (7, 9), (10, 2)\}$.

If we arrange the list such that all price are in ascending order and vitamin contents in descending order, then the valid lists are the following:

$[(2, 8)]$
$[(5, 11)]$
$[(7, 9)]$
$[(10, 2)]$
$[(2, 8), (10, 2)]$
$[(5, 11), (7, 9)]$
$[(5, 11), (10, 2)]$
$[(7, 9), (10, 2)]$
$[(5, 11), (7, 9), (10, 2)]$

From the above lists, I want to choose the list of maximal size. If more than one list has maximal size, we should choose the list of maximal size whose sum of prices is least. The list which should be chosen in the above example is $\{(5, 11), (7, 9), (10, 2)\}$.

Example 2: $N = 10$ and $$F = \{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\(90,18), (43,90),(13,100),(78,65)\}$$

The answer to this example instance is $[(13,100),(43,90),(78,65),(87,11),(99,10)]$.

Until now, this is what I have been doing:

Sort the original list in ascending order of price;
Find all subsequences of the sorted list;
Check whether the subsequence is valid, and compare all valid subsequences.

However, this takes exponential time; how can I solve this problem more efficiently?


texts:
Consider the algorithm findMax that finds the maximum entry in an integer array.

Algorithm findMax($A$)
    Input: An integer array $A$
    Output: The maximum entry of $A$

1. m <- A[0]
2. for i <- 1 to A.length - 1 do
3.     if A[i] > m then
4.        m <- A[i]
5. return m

Show that there are constants $c_1,d_1,c_2,d_2 \in \mathbb{N}$ such that $c_1n + d_1 \leq T_{findmax(n)} \leq c_2n + d_2$ for all $n$, where $n$ is the length of the input array.
Argue that for every algorithm A for finding the maximum entry of an integer array of length $n$ it holds that $T_A$$(n)$ $\geq n$.

NOTE: The (worst-case) running time of an algorithm A is the function $T_A: \mathbb{N} \rightarrow \mathbb{N}$ where $T_A$$(n)$ is the maximum number of computation steps performed
by $A$ on an input of size $n$.

My intuition was that $c_1$ and $c_2$ correspond to the number of times the next element of the array is greater than the current maximum, but I don't see how to fit it in the equation.

1 - executed $1$ time
2 - executed $n$ times
3 - executed $(n-1)$ times
4 - executed $c$ times - - - best case: $0$ times / worst case: $(n-1)$ times
5 - executed $1$ time

In the total sum of steps:

Step 1 + Step 5 = 2 times
Steps 2,3,4 $\leq 3n$ times

Therefore, $c_1 = 1$, $d_1 = 2$, $c_2 = 3n$, $d_2 = 2$.

For the second question, would it be enough to show that the best-case scenario (array sorted in non-increasing order) takes at least $n$ steps?


texts: Formally modelling and describing access rights

texts:
Is there a formal theory or framework described in text books that models access rights in a mathematical way. I would expect things similar to the following:

We have data (objects).
We have operations on these objects (CRUD, create, read, update delete)
We have actors (users, principals)
We might model access rights as triples like (user, operation, object) which describe which user can do what to which object.
We have a potential hierarchy of objects: a folder has files, a file has meta data and rights may be inherited according to certain rules down the hierarchy.
We have a hierarchy of actors too.
Rights may be stored more efficiently by creating triples of (user set, operation set, object set) based on attributes of the objects and the users.

Apart from the pure theory I would expect to read about efficient implementation strategies, data structures etc.

EDIT on: Once access rights are modelled, I would like to read about how these are enforced in real code. Where and when must an operation of some data make the decision whether this is allowed in the given context or not.
EDIT off

Further I would expect to see how this maps to real world access control systems in file shares, databases, web applications. Maybe I am just missing the right keywords for a search.

The one paper I found, http://www.sciencedirect.com/science/article/pii/S1877050916301764, is not exactly convincing.


texts: Why is the undecidability of the Halting Problem useful?

texts:
My understanding:

The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way an LBA can loop is by entering a configuration it's already been in, which is easy to check. However, unlike an LBA, a Turing Machine can also loop by entering infinitely many new configurations, none of which accept. So it seems that what the Halting Problem's undecidability really means is that the problem of checking whether a Turing Machine will enter infinitely many new configurations without accepting is undecidable.

My question:

But real computers are LBAs, not TMs. They can't enter infinitely many new configurations. So why is the undecidability of the Halting Problem a useful result?

I've looked at the answers to this and similar questions, and invariably they go something like, "a real computer has a bazillion configurations, and so waiting until you hit a repeat one would take a bazillion years." But as I detailed above, Halting undecidability doesn't seem to tell us anything about that kind of looping; it only tells us about the infinitely-many-new-configurations kind that real computers can never engage in.


texts: Fenwick Tree/ Binary Index Tree Interval location

texts:
I have an array of positive numbers, and when calculating the cumulative sum of this array, want to know which interval a given point will lie in.

I have done this by searching linearly through an array, but want to use Fenwick trees in the hopes the speed up will be noticeable. I've followed tutorials online, and have now implemented construct, update and getsum functions. I'm not sure how to go about determining which interval a point will lie in though (while taking advantage of the data structure).

So for example, if I had the array [1,2,2,1,4,6,7,3], then I could calculate the cumulative sum as [1,3,5,6,10,16,23,26]. If I the  had the number 17, I'd want to know what interval this lies in. So starting indexing at 0, this would be in the interval between the 5th and 6th elements of the array.


texts: Given a tree, find a vertex which maximizes the minimum distance to any leaf

texts:
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.

I am sure this problem has been studied before.
Does anybody know the name of this problem or an algorithm for solving it?


texts: Why is least fixed point (lfp) important in program analysis

texts:
I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on program analysis also focus heavily on finding least fixed point.

More specifically, this article in wikipedia : Knaster-Tarski Theorem mentions that lfp are used to define program semantics.

Why is it important? Any simple example helps me. (I am trying to get a big picture).

EDIT

I think my wording is incorrect. I donot challenge the importance of lfp. My exact question (beginner) is: How does computing lfp help in program analysis? For e.g., why/how abstract interpretation uses lfp? what happens if there is no lfp in the abstract domain?

Hopefully my question is more concrete now.


texts: In instructions pipelining, why does register read/write take up only half clock cycle?

texts:
While studying instruction pipelining in MIPS processor, we make an assumption that registers read/write stages take only a half clock cycle, as this picture shows (half clock cycles are dotted in register operations):

So what is the purpose of this assumption? and why is the fourth instruction in this graph is considered a hazard if we actually wrote the value of $2 in the first half clock cycle and then read it in the latter one?


texts: Could AI be used to detect when a human is picking survey response options randomly?

texts:
Context: I am a clinical psych researcher dabbling in machine learning.
Humans cannot be truly random. Therefore, could machine learning be used to analyze a string of numbers and determine the probability that said string was generated by a human or by a computer? Taking it a step further, could machine learning be used to look at survey responses and determine the likelihood as to whether the participant was answering questions honestly, or whether they "Christmas-tree'd" either part of or all of the survey? If so, would this be dependent on the specific questions that each survey item asked, or simply on the type of survey question (e.g., Likert-type, sliding scale, ruler, yes/no or true/false questions, free response, etc.)?


texts: Hash table where items can fall into multiple buckets. What's the name of the data scrtucture?

texts:
I have a task to search through an array of items. I want to narrow the search down to some partitions. I thought of hash tables, but the difference in my case is that the "hash-function" is not unique; in my case, it rather should be called "partition-function".

Here's a fizz-buzz example:

[-1]:1,2,4,7,8,11,13,14,16
[3]:3,6,9,12,15
[5]:5,10,15

You see, 15 fell into two buckets. It's ok with me.
Since I'm going to look up "all who's divisible by 3" I'll get 15. Same for "all who's divisible by 5".

I see the following problems for the datastructure:

Data is duplicated (more space, it's ok with me)
Inserts/Updates/Deletions are more expensive

The question is:

Is this approach to partitioning a good one?


texts:
The origin problem is here. Now it is deleted.

Suppose I have 3 'available' copies of a, 2 of b, 3 of c, and 4 of d.

I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
Is there an efficient (i.e. $o(k)$) algorithm for computing the $k$-th smallest string of length $l$ in lexicographic order?

For example, The first string of length 1 is a, the second string of length 3 is aab, the 5th string of length 5 is aaacc (following aaabb, aaabc, aaabd, and aaacb), etc.

What kind of algorithm or math can I use to calculate?


texts: How do you determine the inputs to a neural network?

texts:
I'm looking at this tutorial on neural networks. The data that is given from the UCI study includes various attributes, such as "mean x of on pixels", "total # on pixels" etc, which are taken as input to the neural network. However, it seems to me that this choice of input parameters is somewhat arbitrary, and, in this case, would only apply specifically to the black-and-white letter recognition problem, and maybe could be extended to some other image recognition problems.

As a result, my questions are:

How do you determine what inputs you should use for a neural
network?
Are more inputs necessarily better?
Does it matter if inputs are linearly independent?
And, finally.. Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?


texts: Solving recurrence relation for running time of combination formula

texts:
I'm trying to solve the following Time complexity recurrence relation:
$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$
that  come from following code:
int C(n, k) {
  if (k == 0 || k == n) return 1;  // stop recursion.
  return C(n-1, k-1) + C(n-1, k);
}

Unfortunately, I have no idea to solve $T(n,k)$. Any hint that helpful be appreciated.


texts: Prove that a convex combination of admissible heuristics is admissible

texts:
I got this question that's been troubling me for some time.

  If $h_1$ and $h_2$ are admissible heuristic functions, prove that $h_3 = (c-1)\,h_1 + c\,h_2$, $0 < c < 1$, is also an admissible heuristic function.

The thing that I get stuck on, and maybe get a little tunnel-vision, is that $(c-1)$ is negative which prevents me from "building" the inequality starting from $h_1(n) \leq a(n)$, where $a(n)$ the actual cost to the end node. Any help with a mathematical explanation or using an example is greatly appreciated.


texts: Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

texts:
What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$?

Clearly, there are simple exponential time algorithms, but I'm wondering if any algorithms polynomial in $\log n$ are known, or at least polynomial in $i + \max \{a_j | 1 \leq j \leq i\}$. I was thinking along the lines of Yuval Filmus's answer, but could not make it work for the distinct integer case in polynomial time.


texts:
I need to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and $1$ multiplication by $y$. $x$ is restricted to be odd, $d\geq 3$.

$a$-bit arithmetic (for any $a$) is allowed, as this is just a theoretical question.


texts: Pumping Lemma on Language with subtracted length

texts:
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given

$$ L = \{ a^k b a^{m-1} \mid k,m \in \mathbb{N} \} $$

Questions:

How does $m-1$ affect my choice of the word to be pumped? There must be a way to rule out $m=0$ because otherwise my length would be negative.
Would it be wrong to choose $w = a^{n-1}ba^n$ with the intent of pumping down $y = b$?

Every answer is highly appreciated.


texts: find if a string is periodic using a suffix tree, and prove it

texts:
A  string s of  length n is  periodic  if  there  is  a  string $u$ of  length <= n/2 such  that $s = u^ku'$, where  $k$   is an integer >=2, $u^k$ is the concatenation of k copies of  $u$ , and $u'$ is a
prefix of u.

The smallest period of $s$ is the shortest $u$ (largest  $k$) for which this holds.

For example, if s=ACACACACA, then k=4, u=AC, u'=A.

I want a linear-time algorithm for determining if s is periodic.

This SO answer gives a nice lead for a suffix tree solution. I want to use it, but I can't prove that it will work if and only if s is periodic.

Can you sketch it for me?


texts: Egg dropping puzzle - clarification of problem statement

texts:
I was trying to understand the egg dropping puzzle. The problem objective is:

What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

I understand we want to minimize the egg drops, but what does this worst case number of drops infer to. This makes me more confuse. Can anyone explain its meaning.


texts: Strong Uniform Total Order vs Weak Uniform Total Order

texts:
The definition for SUTO and WUTO is the following:

Suto

  If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.

And for WUTO

  If process p and process q both TODdeliver messages m and mʹ, then p TODelivers m before mʹ if and only if q TODdelivers m before mʹ.

I have a hard time getting my head around this. For me, both of them sounds the same...

Any help?


texts:
Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:

  In a man-optimal version of stable matching, each woman has worst
  partner that she can have in any stable matching.

Proof:

  Suppose not. Let $M_0$ be the man-optimal stable matching, and
  suppose there is a stable matching $M’$ and a woman $w$ such
  that $w$ prefers $m = p_{M_0}(w)$ to $m' = p_{M'}(w)$ . But
  then $(m,w)$ blocks $M'$ unless $m$ prefers $p_{M'}(m)$ to
  $w = p_{M_0}(m)$, in contradiction of the fact that $m$ has no
  stable partner better than his partner in $M_0$.

I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying?  From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$.  But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction.  Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.


texts: How can I determine whether a problem is NP-Hard

texts:
So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case?

Suppose I have different groups of people m in a list

M= {m1, m2}

and a list of food they can eat and the respective cost in dollars

Food = {f1:2, f2:3, f3:2}

you have buffet and can choose which food you can offer from the list, you can offer all the options or none. You will be paying for the food in hopes the tip will cover the cost.

each group will tip a certain amount if and only if all the option they like are available in the buffet, otherwise they tip 0.

Liked food = {(M1:f3: tip = 5), (M2:f1,f2: tip=10)}

profit = Tip - cost of food

f1 = 0 - 2 = -2

f2 = 0 - 3 = -3

f3 = 5 - 2 = 3

f1,f2 = 10 - 5 = 5

f1, f3 = 5 -5 = 0

f2,f3 = 5 - 5 =0

f1,f2,f3 = 15 - 7 = 8

Therefore to maximize profit you must purchase all the food and you will profit 8 dollars.

I believe that the question is NP-Hard, my prof says otherwise.

I already can clearly see there is no polynomial time verifier for this question and it's impossible to guarantee the solution is most optimal without trying the other  all the other combos.

This means to show its NP-hard I'd have to do a reduction? Though I'm not really sure where to begin? Is my prof correct in saying its not NP-Hard?


texts: Is there a generally agreed short notation for "a points to b"

texts:
Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately)

a -> b

but I wonder whether a short double right arrow would be better:

a => b

Best of all would be to know, and use, a universally-accepted standard symbol, if there is one?


texts: Can such an operation be done with two stacks?

texts:
Assume a Forth-like environment with two stacks, a main one and an auxiliary one.
The following operations can be done on the main stack: DUP (duplicate the top element), SWAP (swap the top two elements), DROP (drop the top value), PUSH (move the top value to the auxiliary stack) and PULL (move the top value of the auxiliary stack to the primary one).

If the main stack is organized like this (top-bottom): x <x elements> y <y elements> z <z elements>, where x, y and z are integers preceding the corresponding number of arbitrary elements, is it possible to re-arrange it like this: x <x elements> z <z elements> y <y elements> using only the operations described above?

If not, what operations can be added to satisfy this condition?


texts:
Question:
Which of the following languages are in P? which in NP? other classes?

a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment s.t. at most k variables are TRUE.

b. same language but this time in each clause one literal is negated and the other isn't.

c. SAT-2-NAE - every clause has exactly 2 literals, is there an NAE satisfying assignment to the formula

d. mono-SAT-2-NAE - every clause as exactly 2 literals, none of them negated and it has a satisfying assignment

Thoughts:
We tried a lot of reductions from 2SAT and other problems and cannot really determine most of the questions. We'd like to know what is the effect of the "monotone" property on the satisfiability such formulae... We'd also like some hints on how to reduce to these problems.


texts:
I have a problem. I want to know how to solve this in polynomial time (is it possible?).

There are $n$ customers that must be served by single machine. For every customer $C_i$, it has a profit $P_i = a_it + b_i$ where $t$ is the finish time and $a_i<0$. Yes, the profit can be negative. For every customer $C_i$, it has a service time $S_i = c_it + d_i$ where $t$ is the starting time and $c_i>0$. The problem is to find a serving order for these customers to maximize the total profit (the starting time of the first customer is $0$).

For example:
\begin{align}
    &C_1 : P_1 = -0.5t + 35, &S_1 = 2t + 4,\\
    &C_2 : P_2 = -t + 40, &S_2 = 2t + 3,\\
    &C_3 : P_3 = -0.4t + 45, &S_3 = 3t + 6.
\end{align}

The optimal order is $C_2, C_1, C_3$ and the profits are calculated as:
\begin{align}
    &C_2 \text{ is done at time }3\text{ with profit }40 - 3 = 37,\\
    &C_1 \text{ is done at time }3 + (2\times 3 + 4) = 13\text{ with profit }35 - 0.5\times 13 = 28.5,\\
    &C_3 \text{ is done at time }13 + (3\times 13 + 6) = 58\text{ with profit }45 - 0.4\times 58 = 21.8.
\end{align}

The total profit is $37 + 28.5 + 21.8 = 87.3$ (I hope I didn't make  mistake calculation).


texts: What is the state of the art in efficient boolean function operations?

texts:
How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT?  The most up-to-date work that I can find on this subject is about 20 years old (Efficient data structures for Boolean functions).  Which search terms should I be using to explore this question?

Edit:

I am starting from about 200 simple boolean functions.  These are combined with each other using AND, OR, NOT, and XOR to give other boolean functions, which are then also combined using AND, OR, NOT, and XOR.  The process repeats about 3000 times, until a final combination gives me a single boolean expression.  I'm interested in that final expression.

Representing the functions as DNF or CNF makes certain operations (NOT and XOR) slow.  Representing the functions as ROBDDs is an option - are there any drawbacks here?  I'm not sure whether SMT solvers are useful here, because I am interested in the final equation rather than whether the equation is satisfiable.  What else should I be looking at?


texts:
I have a language which is made out of and has a grammar only operating on well parenthesized words or words of one symbol. I want to know if the problem of belonging to this language is decidable.

Example. Consider the following grammar:
$$a \to a(aa) \\ a \to b \\a (a(a(ab))) \to b$$
I'll denote by $L(x)$ the language generated by the above grammar and rule $S \to x$.

Trivially, $b \in L(a)$, using rule 2.
Also $b \in L(a(aa))$ by the sequence of productions $a(aa) \to a(a(a(aa))) \to a(a(a(ab))) \to b$.
However $b \notin L(aa)$ because after applying rule 1 any number of times and then rule 2, symbol $a$ will be repeated $2n + 1$ times and rule 3 can only remove $4m$ of them.

Note, the grammar is actually dealing with trees. Parentheses denote a subtree and symbols denote leaves. Hopefully the notation is clear enough. The language seems much weaker than RE but stronger than context free.


texts: how to express the performance of a policy in policy parameters

texts:
Suppose a leauge of tic-tac-toe playing agents. As the league proceeds, the bad players are kicked out, and better players come in. The problem resides on how to at least approximate the better player.

One way to think of is an evolutionary approach. By random mutation possibly followed by crossovers, you may expect that slowly the players will converge to the optimum.

But I want something more deterministic. Assuming the policy function of each agent is differentiable, there are many methods to speed up the optimization. I will use the term policy as a function that takes the current board as input and ouputs the best move to play. Whatever method I choose, they need the performance as input. One obvious performance metric is the winrate, which usually works fine to approximate the performance itself, but it doesn't contain any parameter from the policy function. To optimize the policy to maximize the performance, things work best when the performance can be expressed in the parameters defining the policy, so that I can take the gradient of the performance with respect to the policy parameters, and update the policy following the gradient; that is, gradient ascent.

So back to the title, what is a good way to express the performance of a policy in policy parameters?


texts: Calculating the runtime for a recursive algorithm

texts:
If the runtime of a recursive algorithm could be expressed as

$T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$

what would be the result of the asymptotic analysis (the Landau class)? $k \in \mathbb{N}, k \neq 0 $ is a constant value.

I would say that $k$ even if it is larger than $n$ is still a constant and therefore $T(n) = O(1) * T\left(\frac{n}{k}\right) + O(n) = T\left(\frac{n}{k}\right) * n $ for $n > c$.

So I would say that the algorithm is $O(n * log_k(n))$. Is this right? How could I prove this (formally correct)?

I have two main problems with this algorithm:

1) What is the runtime of $f(n) = (k + n * k)$? Can the $k$ be ignored so the runtime is $O(n)$?

2) I would like to use the Master theorem. I could see $T(n)$ in the form $a \cdot T\left(\frac{n}{b}\right) + f(n)$ with $a = b = k$. But then I need to check if $f(n)$ is $\in O(log_b a) = O(log_1 1) = ?$ This logarithmus is undefined, so can't I use the Master theorem?


texts: Hash Table: How to Calculate Max Load of a Bucket in Practice

texts:
My question is related to this question I posted in math forum:

https://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example

but I could not get an answer that I need.

Please assume upper bound on set cardinality is $n$ (so the set has at most $n$ elements). A server wants to construct a hash table in away that each bucket would contain at most $d$ elements with a high probability. So for any client having set $S_i$ where $|S_i|<n$, any bucket of hash table would not overflow. In setting, any client can independently insert its elements in the hash table, given the hash table length and hash function; and send the hash table to the server.

I need to know how the server can compute the hash table length (or number of buckets in the hash table), given $n$ and $d$.

In [1,2] it is said $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ is a max load for a bucket with a high probability, where $n$ denotes number of elements and $k$ denotes number of buckets (alternatively we can re-write it as $\frac{n}{k}+C(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$, where $C$ is a constant value). But, I need to know how this works in practice. More specifically how we can compute the probability and constant value, $C$.

[1]. http://www.pinkas.net/PAPERS/FNP04.pdf

[2]. http://www14.in.tum.de/personen/raab/publ/balls.pdf


texts: Address of the Last Byte of Installed Memory

texts:
I'm a university student currently taking an Assembly and Computer Organization class. On last weeks lab we were given a question:

Suppose that you buy a 32bit PC with 16 MB of Ram. What is the 8-hex-digit address of the last byte of installed memory?

From my understanding you multiply MB (2^20) with 16 (2^4) which gives you 2^24 or 16777216. I subtracted 1 from that number and converted to hex which gives FFFFFF. I then padded to 8 digits and got 00FFFFFF.

This is wrong and I was told the correct answer is 01FFFFFF. Can somebody explain what I did wrong and how that is the correct answer?


texts: Complement of $0^n1^n | n \in \mathbb{N}$

texts: I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 \cup1)^*$, but I don't see how $A^* = \sum^*$. Any help would be appreciated!


texts: Are NP problems lower bounded by exponential order of growth?

texts:
My understanding of P. vs NP is quite limited. I can understand P refers to an algorithm with an upper bound (big O) with order of growth $n^c$ for some constant c and variable n. My question is, do NP problems have a hypothesized lower bound order of growth (big Omega) of $c^n$ for deterministic machines? I can't find this stated anywhere and I'm trying to understand if this is something that is assumed or not.
Thanks.


texts:
There are two stacks $S_1$ and $S_2$ of books. Each book in stack has a weight. You are given a net weight $W$ of books that can be picked. You have to maximize the number of books that can be picked. Note that each time you can either pick from $S_1$ or $S_2$ only.

eg: $S_1 = \langle 5, 1, 1\rangle$,
$S_2 = \langle 1,2,6 \rangle$, $W=10$.

So the answer is $5$ (pick $1$ and $2$ from $S_2$, then all elements from $S_1$)

I know this question can be done with a greedy approach by comparing top elements of both stacks, but can we solve it with the concept of trees?

Is there any other data structure that can be used to solve this problem?


texts: How to calculate virtual address space from page size, virtual address size and page table entry size?

texts:
I try to solve an exercise, unfortunately without any success yet.

From the following given information, the virtual address space should be calculated:

Page size is 16 KB
Logical address size is 47 bit
3 levels of page tables; all have the same size
Page table entry size is 8 byte

My idea is to find out how many pages can be addressed. The page count should lead then to the size of the virtual address space, right?

  Virtual address space = page size * page count

As far as I understand is the page count defined by the logical address size. The logical address is split up in 3 levels of page tables plus the offset. Due the page table entry size is 8 byte (2^6 = 64 bit), 6 bits of the logical address are used for each stage to address it. The offset will have the size of 30 bits.

Each page stage can address 64 bit plus the 30 bits offset. So does this result in the page count?

  Page count = 64 * 3 + 30 = 222

With the page size and the page count I get the virtual address space of 3552 KB.

I think this is wrong. It should be much larger. What is not correct? Any help is appreciated!


texts: Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

texts:
in one of my college assignments i came up with the following recursive function which I'm ask to solve:
$T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
I could not use master method on it and it is not an LHR either.
I assume this must have something to do with recursion tree but i cant figure the relation if so.


texts:
In Types and Programming Languages by Pierce, from p257 to p258, about featherweight Java,

The predicate override(m, D, C→C0) judges whether a method
m with argument types C and a result type C0 may be deﬁned in a subclass of D. In case of overriding, if a method with the same name is declared in the superclass then it must have the same type.

I am not sure   what the predicate override(m, D, C→C0) means.
Does the predicate apply only to the case of overriding? (The first sentence doesn't imply so.)
Isn't it always possible to define a method with any name and any type in any class?

In case of non-overriding, that is true.
In case of overriding, that is also true.

Could you   give examples where it is possible and where it isn't?
Figure 19-2: Featherweight Java (auxiliary deﬁnitions) says:

Valid method overriding:
If mtype(m, D) = E→E0 implies C = E and C0 = E0, then
override(m, D, C→C0 )

How can mtype(m, D) = E→E0 imply C = E and C0 = E0?
mtype(m, D) = E→E0 only means that class D has a method m whose type is E→E0.
Why is "mtype(m, D) = E→E0 implies C = E and C0 = E0" a condition for override(m, D, C→C0 )?
Thanks.


texts: Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

texts:
An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:-
122
122
122
222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?


texts: $L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma

texts: How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?


texts: Given an arbitrary TM, can you decide whether it's a LBA?


texts:
It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds:
$$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$
With $\epsilon_n\to 0$ for $n\to\infty$.

The proof is made in Thomas & Cover: Elements of Information Theory (Lemma 12.10.1, page 320 in the linked chapter).

I tried to generalize it to an alphabet of size $k$ by adjust the proof step by step, but I failed. So, my question:

How can I prove that the number $c(n)$ of phrases / tupel of the LZ compression is bounded by
$$c(n)\leq\frac{n}{(1-\epsilon_n)\log_k n}$$
for all words of length $n$ over an alphabet of size $k$ with $\epsilon_n\to0$ for $n\to\infty\;?$


texts: The terms contention and race are used interchangeably when it comes to thread's state(at critical section). Are they same?


texts: Solving recurrence relation with different rules for odd and even n

texts:
Assume $T(1) = 1$, and

$T(n) = 2T(n/2) + n^2$ for even $n$,
$T(n) = T(n − 1) + n$ for odd $n$.

I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly and we got $a = 2$, $b = 2$, $d = 2$, therefore it's the case that $d > \log_b(a)$ and $T(n) = \Theta(n^2)$.
But I'm unsure for the given $n$ is even, does this effect to our final result?

Because I noticed on the second one, for odd $n$ it changed our result from $\Theta(n^2)$ to $\Theta(n)$. Suppose we have
$T(n) = T(n − 1) + n$, we can solve as summation from $0$ to $n$ such $0 + 1 + 2 + \dots + n - 1 + n = n(n+1)/2$, and hence $\Theta(n^2)$. However, if for odd $n$, I'm thinking this naively, we can just sum all odd numbers in the sequence so we have $1 + 3 + 5 + \dots + n = 2n-1$ and hence $\Theta(n)$. Is my assumption accurate?


texts: Data structure for getting the k'th largest element

texts: I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?


texts: Count number of intervals containing a point

texts:
There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al.
where you have to solve the problem of given $n$ intervals, $I$, on the real line, count the number of interval containing a query point $q$. There are several subproblems asking for efficient ways to do this using segment trees and a BST which I have solved, however sub question b asks:

Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.

and for some reasons this seems much harder to me.
Any hints or help with how I can approach this would is appreciated. Note that this is indeed not homework, but the material on these topics are sparse online so I feel going through these exercises works.


texts:
This is problem from my Networks class. It wants us to compute the round trip time of a point-to-point network and I'm just not sure which information is pertinent. The question:

NASA    deployed    its latest  622Mbps point-to-point  laser   link    between Earth   and a
new lunar   base.   The distance    from    the Moon    to  Earth   is  approximately   385,000
km, and data    travels over    the link    at  the speed   of  light   3   x   10^8    m/s.

(a) Calculate the minimum RTT for the link

I'm not sure whether I should be using the 622 Mbps or the distance and speed of light. My initial thought was using distance and speed of light. Meaning, the minimum would be (385,000*1000)m /(3x10^8 m/s)*2  = 2.56666 seconds.

But if you use the 622 Mbps you can compute, for the minimum it would be quickest if you only sent one bit, and the other host immediately responded with one bit meaning that the RTT would be 2*(1/(622*1,000,000)) = 3.215 e-9 seconds.

To me it seems like it should be the former, but if the link is 622 Mbps why would it take longer?

EDIT: to clarify don't tell me which answer is correct, as it is homework. I would like to understand the concepts involved with why RTT is unrelated to Mbps.


texts: Space complexity of directed and undirected graph

texts:
I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then:

$$|E|\text{ close to }|V|^2$$ else if the graph is sparse then:

$$|E|\text{ is much less than }|V^2|$$

According to me the above two relations makes sense in respect of a complete graph where the total number of edges is $\frac{(V)*(V-1)}{2}$ hence, $E = O(V^2)$.

Hence, we choose adjacency list representation where the length of the list is $\text{2|E|}$ for undirected graph and $\text{|E|}$ for directed graph. After that he simple concludes that space requirement for the adjacency list representation is $\Theta(V+E)$. I am really stuck on how he came to this conclusion without any explanation. According to me it should be $O(V*(V-1))$ because for each vertex the maximum possible edge is $V-1$. What I am doing wrong?


texts: Choosing a method for algorithmic problems - is it an art or science?

texts:
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - should I use brute force or greedy search would work better or maybe dynamic programming would do the job? Then I start coding a solution just too find out it does not work and I have to pick another method.
I wonder if there is a way to restate the problem in some abstract way and from there to see what solution technique would work for it?


texts: Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

texts:
In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {V_1, V_2, ..., V_d}$, where each $i$-th dimension in the knapsack must have a value sum greater than threshold $V_i$. I am not so much concerned with the total value sum.
I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem harder than MKD and therefore is NP-hard. But clearly this doesn't constitute a formal proof.


texts: How many times an empty 4-cycle can be counted in an undirected graph?

texts:
I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle have not to be connected).

I know the labels of a generic square in the graph can be permuted in $4! = 24$ ways, but on his paper (pages 33-36) Cohen states that the symmetric group $S_4$ has $S_4 = 8$ elements, and this should allow me to focus only on $24/8 = 3$ distinct cases.

I don't understand this last point. Well, I know he probably means that the suqare has $8$ isometries (four reflections and four rotations), but I don't understand why this leads to the three cases in Figure 7 of the paper.

Thank you.


texts:
A forest is a collection of trees.

Is there a similar notion for paths? e.g., a _______ is a collection of paths.


texts:
Suppose i have the following resource allocation graph with a deadlock cycle, i see why it is a deadlock cycle, what i don't get is how to recover from this cycle

i'm thinking about aborting a process, any process here will lead to non-deadlock situation, but doesn't that cause the other process to not execute and hence the program won't execute as we're expecting it to be, i think this is a correct answer, but is there another way to do such that all processes will eventually run ?


texts: In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

texts: In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex format. can we use $a^n b^n c^n d^n$ format for our guesses?


texts: Encoding a arbitrary stack trace into a fixed length value

texts:
Background
I would like to store the nodes of a Calling Context Tree using in a key value store. I need to be able to directly access a node by it's method name and complete stack trace. In addition in need to access all nodes of a method by only it's name (the key value store supports a loading based on prefix).
Problem
The first idea is to use the method name + an encoded stack trace as key, e.g. the concatenated string representations. Unfortunately this can get quite large and I cannot use keys of arbitrary length.
So the second idea was to encode the stack trace in a deterministic and reversible way.
So my next idea was to encode the stack trace in a 64 bit integer, by adding the 32 bit hash representations of the methods in the stack.
Unfortunately this is not collision free as the traces A -> B -> C and B -> A -> C compute to the same values even though the traces are different.
So my current idea is to encode the traces by:
encodeStacktrace(stack_trace)
1. 64bit current = 0
2. For every method m in stack_trace
3.   current = rotateLeft(current) + hash(m)
4. return current

They key is then method name concatenated with the encoded stack trace value.
Question
Is this implementation collision safe? I think not 100% however I don't know how to compute the probability under the assumption that the method hash computation is a perfect hashing algorithm.
If it is not safe, are there other implementations/directions I can look into?


texts: Compression for set of integers preserving their sequence

texts:
For a given positive number n. Numbers from 0 up to n, are streamed one by one in some order without repetition.

What would be recommended a strategy to store the order of these n numbers in the most space conservative way?

Highest priority is to consume minimal bits to store the order.
Second highest priority is to have minimal effort in adding the incoming number to the current order
Least priority is the computational complexity in retrieving the order.

Retrieval will be done only when all n numbers have been added.

Deletion operation will not be performed.


texts: Is there a language with non-isomorphic minimum-state UFAs?

texts:
For all regular languages L, by the Myhill-Nerode classes, all state-minimal DFAs for L are isomorphic.  On the other hand, "a regular language may have many non-isomorphic state-minimal nfas".  What about Unambiguous Finite Automata?  Every DFA is also a UFA, so every regular language has at least one UFA.  The natural numbers are well-ordered, so in turn every regular language has at least one state-minimal UFA.

Is there a regular language whose state-minimal Unambiguous Finite Automata are not all isomorphic to each other?


texts: Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

texts:
In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. As a substep the algorithm requires sorting a multiset $R$ of values sampled from $S$, where $|R| = \lceil n^{3/4} \rceil$. I'm sure this is a fairly simple, and straight forward question compared to the others on this site, but how is sorting a multiset of this size bounded by $O(n)$?

I assume the algorithm is using a typical comparison-based, deterministic sorting algorithm that runs in $O(n\log$ $n)$. So, If I have the expression $O(n^{3/4}\log(n^{3/4}))$, isn't this just equivalent to $O(\frac{3}{4}n^{3/4}\log(n)) = O(n^{3/4}\log(n))$? How does the reduction down to $O(n)$ proceed?


texts: Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

texts:
Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with "max"; but it cannot update quickly; Means that if we consider max then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How do I solve this problem?


texts: Annotated type system problem about conditional branch

texts:
I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various statements(S). And S maps a state to a state, and may therefore to have type Σ --> Σ where Σ denotes the type of state. So they mentioned a system of axioms and inference rules like below for sequential statements and if-else block:

And later it is explained, an if-else statement in terms of Reaching Definition as below,
Also, I can visualize the sequencing rule seems natural, but they mentioned conditional rule is more dubious. I am not able to understand how this is dubious? As per my understanding reaching definition after after 'if' block execution will may execute then block or else block, then how this is even conflicting? S1 may have different statements and S2 will also have different statements but these two blocks would not execute at same time. I am not getting this scenario, can you please help me with this


texts: Are context-free languages in $a^*b^*$ closed under complement?

texts:
The context-free languages are not closed under complement, we know that.

As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under complement(!?)

Here is my argument. Each CF language $L$ has a semi-linear Parikh image $\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$. Semilinear sets are closed under complement. The set of vectors that represent the semi-linear set can easily be transformed into a linear grammar.

Question. Is there an easily accessible reference to this fact?

Technically these languages are called bounded, i.e., a subset of $w_1^* \dots w_k^*$ for some words $w_1,\dots,w_k$.

My motivation for this question is from a recent question on the context-freeness of $\{ a^nb^m \mid n^2 \neq m \}$. Its complement within $a^*b^*$ seems easier to handle.


texts:
Came across the following tile problem :

Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Recurrence formula is as mentioned below :

count(n) = n if n = 1 or n = 2
count(n) = count(n-1) + count(n-2)

Explanation is as follows :

count(n-1) : If the first tile is placed vertically, then problem reduces to a grid of size "2 x (n-1)"
count(n-2) : If the first tile is placed horizontally, then problem reduces to a grid of size "2 x (n-2)", because we will need to place two tiles horizontally one above the other

But my doubt is, the above recurrence is fine if we always place the tiles at the left most side of grid. What if I place the first vertical tile at center of grid instead of the left most. Should not be covering all the permutation and combinations possible on basis of where we place the first tile?


texts: Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

texts:
I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive.

For example, some problems require loops practically - making 10^100^1000^10000 repeated calculations (even no-ops) is not possible practically as the space necessary to store the code would likely be greater than the number of atoms in the universe, but would be possible theoretically given infinite memory (similar to how current implementations of programming languages only approximate Turing-completeness).

Alternatively: is there a problem which requires Turing-completeness to solve theoretically?


texts:
Consider the following traditional integer knapsack problem:

$\max \sum_{i=1}^k p_i \cdot x_i\\
\text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\
x_i \in \{0,\ldots,k_i\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\{1,\ldots,k\}$ such that for each pair $I_1,I_2 \in \mathcal{I}$ it either holds that $I_1 \subseteq I_2$ or $I_1 \supseteq I_2$ or $I_1 \cap I_2 = \emptyset$. For each of these subsets $I_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum_{i \in I_j} x_i \leq \mu_j$

for some number $\mu_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k_i$ are still not polynomially bounded).
Accordingly, if the maximum amounts $k_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?


texts: Getting output of dynamic programming, (contiguous sub array, box stacking)

texts:
I am attempting to output the largest stack of boxes given an input of a set of boxes.
Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this is the array being operated and changed, I then have another array that also has the values of the boxes going from largest to smallest.

 for(int i = 1; i < array.length; i++) {
     for(int k = 0; k < i; k++) {
          if(array[i].canStackOn(array[k])
             && maxWeight[i] < maxWeight[k] + temp[i].weight()) {
              maxWeight[i] = maxWeight[k] + array[i].weight();
              }
          }

  }

I am absolutely beating my brains out trying to find a way to keep track of each of the items added to the location of the largest sum on the array. Could anyone be so kind as giving pointers to a solution?


texts: Minimax algorithm when all the options are the same

texts:
tl;dr What does the Minimax algorithm do when all its options are the same?

Consider this Minimax tree:
(Green means the ends, orange minimize, blue maximize)

(Source: Myself)

Imagine this is the tree for a game (tic-tac-toe, maybe?). What should the computer do? Pick one at random? Pick the one which on average has the best score (the second one)?

Background

I'm making a program to play Quoridor, and I figure that the Minimax algorithm is the best choice (with some pruning of the really bad ones; otherwise, it would be way too big). The problem is, every choice you can make (the beginning ones in particular) have a chance to loose, and every loss has the same value (-1). So how can I pick the best moves, if all the options are the same?


texts:
I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced.

But I am imagining that in situations in which several paths of a tree have to be explored such as in an R-tree, balance might not always be necessarily desired?


texts: Is There a Programming Language That Embraces Globals?

texts:
All programming languages have globally defined symbols.  While best practices invariably abjure their use as mutable entities the philosophy of what is mutable and what is not mutable is highly context dependent.  Technologies like JIT compilation and type inference generate code on the fly based on the context in which symbols are dynamically referenced.

This makes me wonder exactly how far can this be taken.  Have languages been researched that are oriented around embracing global references?

For an example of what I'm thinking of, in Perl there is a "local" command that allows you to save the value of a symbol that is global to the current dynamic scope, modify the symbol as though global within that scope, and automatically restore its prior global value upon return.  This differs from ordinary concepts of local variables in that the nested dynamic scopes inherit the binding.  It also means that all code references, as well as data references, would be potentially dynamic.

I'm sure features other than a Perl-like "local" would be necessary to make it more wieldy (or less unwieldy for programming in the large, as the case may be).  An example of a more powerful dynamic scoping feature would be Javascript's "with" statement which allows unqualified references (without the object reference itself being repeatedly specified) to the properties of an object within the "with"'s dynamic scope.

The point here is that there are different ways of attacking the problem of programming in the large and some may be more conceptually clean than others in the sense of Ockham's Razor in that there is no escaping global symbols so we may as well make the best of them.

In more abstract terms, Quine suggested a similarly radical approach, at least in spirit, to applying Ockham's Razor in formal logic's use of the "name":

  “Chief among the omitted frills is the name. This again is a mere
  convenience and is strictly redundant, for the following reasons.
  Think of ‘a’ as a name, and think of ‘F(a)’ as any sentence containing
  it. But clearly ‘F(a)’ is equivalent to ‘(∃x)( a = x & F(x))’. We see
  from this that ‘a’ need never occur except in the context ‘a =’. But
  we can as well render ‘a =’ always as a simple predicate ‘A’, thus
  abandoning the name ‘a’. ‘F(a)’ gives way thus to ‘(∃x)(A(x) & F(x))’,
  where the predicate ‘A’ is true solely of the object ‘a’.

  “It may be objected that this paraphrase deprives us of an assurance
  of uniqueness that the name has afforded. It is understood that the
  name applies to only one object, whereas the predicate ‘A’ supposes no
  such condition. However, we lose nothing by this, since we can always
  stipulate by further sentences, when we wish, that ‘A’ is true of one
  and only one thing:

  (∃x)A(x) & ~ (∃x,y)(A(x) & A(y) & ~(x=y) )”

  “(This identity sign “=” here would either count as one of the simple
  predicates of the language or be paraphrased in terms of them.)”

PS:  Part of the reason I ask this question is that I did a multitasking/multiuser OS on the 8088 back in the mid '80s that had a "push and set" macro that I used extensively to create very compact code that, it seemed to me, ran quite fast.  This was a small system -- under 25,000 lines of code -- but it did work well in it specialized function as a 24 user instant messaging/bbs system.


texts: Is machine learning a subarea of expert systems?

texts: My question is short and straightforward: Can be considered "machine learning" a subarea of "expert systems"?


texts:
I have been doing a lot of research into pattern matching algorithms.
For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual patterns I am searching for are of the form 11111, 1*1*1*1*1, 1**1**1**1**1**1, etc, where * is the Don't Care symbol (so either 1 or 0). I think that Boyer-Moore would be quite effective, however I understand that Boyer-Moore string matching can't be modified to work with Don't Care symbols. Is there something with this ability and similar performance?


texts: Is there an existing algorithm for this type of sorting?

texts:
This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted books, and must quickly sort them into alphabetical order.

A number of commenters pointed out that a far more practical method for real-life sorting would be to take the first letter of each book and put it into 26 different piles (an A pile, a B pile, down to a Z pile.) Then use a conventional sorting method (insertion / quick sort etc.) for each of the 26 sub-piles (which would contain around 50 books each, assuming a roughly even distribution of letters. Or you could repeat the same process if the sub-pile is significantly large, sorting the As into ABs, ACs, ADs and so on.

Is there a name of this kind of sorting algorithm?


texts:
I am learning about decision tables and am confused by the colouring in the text book's mark scheme for a question I'm working on. I can not see why some of the columns have been coloured grey. Rather than adding anything to my understanding, the colouring makes me think I'm missing some important point as I can't see a commonality between the columns which have been coloured.

The Questions for which this image is the solution are: i) Complete the decision table and ii) simplify by removing redundancies.

Can anyone please explain the colouring to me?


texts: Is there a way to check if a path in a graph is infinite?

texts:
Edit: Maybe this is not the best title, so few free to change it.

So I'm trying to prove the following statement:

  A finitely branching tree $T$ with infinitely many vertices must have an infinite path.

My proof is loosely like this:

$P = \emptyset$
Start at the root $v_0$
Since there are infinitely many vertices, there must be some vertice
with infinitely successors.

Order the successors of $v_0$ (there is a finite number of them), with the vertices with infinite successors to the left.

$P = P \cup \{v_0\}$

Select $v_1$ as the new root and repeat (3).

What bothers me the most is that I didn't manage to find a deterministic way to do step (3), at first I though BFS would work, since it's complete it would eventually visit all vertices at height $n$ and I could use this to construct an arbitrarily long path $P_n$, however arbitrarily long and infinite are two different things.


texts: Prove/Disprove: NP is closed under "mixed" complexity

texts:
Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:

$\displaystyle x_{i} \in \{0,1\}^{*}$

$\displaystyle x_{1} x_{3} ...x_{n-1} \in S_{1}$

$\displaystyle x_{2} x_{4} ...x_{n} \in S_{2}$

Prove or disprove: if $\displaystyle S_{1} ,S_{2} \in NP$, then $\displaystyle S_{1}°S_{2} \in NP$
I have a feeling it is a proof, simply because I wouldn't know how to disprove it. I know it should come down to finding a certificate $\displaystyle c$ such that $\displaystyle V( x,c) =1$ if'f $\displaystyle x\in S_{1}°S_{2}$, based on the certificates of $\displaystyle S_{1} ,S_{2}$.
The thing is I don't really know what the division of the word $\displaystyle x$ is. So how can I check if part of the word is in $\displaystyle S_{1}$ and the other in $\displaystyle S_{2}$? I could maybe define the $\displaystyle c$ in this way, that it gives you the division, but I don't really know how to define it properly.
Any help?
Keep in mind that's the first time for me studying this subject


texts:
I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki.

  In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree

even most of the definition claims that AVL tree is BST, but is every AVL tree needs to be BST can't it be just BT?

In my point of view, AVL follows an algorithm that balances the Binary Tree, as BST is the subset of the binary tree, then this balancing algorithm can be applied on it.

is there anything that I am missing? Any contradictory example will be highly appreciated.


texts: how does a harddisk work? block / sector

texts:
Can someone explain me the way harddisks work? :/
The size of a block is specified in the filesystem, am I right? As you can see in the picture from wikipedia, the disk is divided into circle sectors. But the blocks on the outer tracks are obviously larger (physically)...

So the "bit-density" on the outer blocks is way smaller than on the blocks near the middle of the disk? I think that I am missing something.... Maybe someone can help me out with another picture / sketch.
Thanks a lot and sorry for the "nooby" question :)


texts:
The  Y combinator expression is as follows:
$$ Y \equiv \lambda  f .(\lambda  x .f(xx) )) .(\lambda  x .f(xx)  ) $$

Now , if I am not wrong , then this expression can be reduced by seeing this as the argument:
$ .(\lambda  x .f(xx))$ hence would lead to the consumption of first bound variable giving:
$$ (\lambda  x .\lambda  x .f(xx) (xx))$$

which is equivalent to $ \lambda  xx .f(xx)  (xx)$

which will yield $ f(xx) $.

But in my book I don't find the Y combinator being reduced to this and it made me feel that something is fishy with the reduction that I am doing .

Is there any mistake in this?


texts:
Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.

These are the things that I would use to start.

As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.
Let $h(L_1) = L_2$ and $h(L_2) = L_1$, then $h(L_1L_2) = L_2L_1$ is regular (we already know that) or $h(L_2) = \epsilon$ and we get $L_1$
By reflexing, $L_1L_2 = (L_2L_1)^{R}$, same result.

But i don't know how to, for example, intersect something that gives me $L_1$ in order to preserve closure and finally $L_1$ be regular.

Any help?


texts: Way to solve 5-dimentional Linear assignment problem

texts:
I faced a problem that looks very hard, the problem is this:

We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person). My job is to  find a cluster of points which contains 3 or more distinct colors. Also, we have some fixed radius $R$, and the distance for each point in a given cluster shouldn't be more than R. Also, there might be points that don't belong to any cluster.

What kind of approach can you suggest? At first, I tried the Multidimensional linear assignment problem, but it seems that this problem is NP-hard, so I want to solve it in a reasonable amount of time (I write code). What kind of solutions can you suggest? Maybe using the fact that this isn't a general problem, I mean we use 2D space where people take action, also there are only 5 people.


texts: Grammars: is there some connection between non-terminals $S$ and $S'$?

texts:
Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.?

$$\begin{align*}
    S &\to aBS'\\
    B &\to b\\
    S'&\to bA
\end{align*}$$


texts: Reducing products in HoTT to church/scott encodings

texts:
So I am currently going though the HoTT book with some people. I made the claim that most inductive types we will see can be reduced to types containing only dependent function types and universes by taking the type of the recuror as inspiration for the equivalent type. I started to sketch how I thought this would work and after some stumbling I came to what I thought was an answer.

$$\cdot \times \cdot \equiv \prod_{A, B, C : \mathcal{U}} (A \to B \to C) \to C$$
$$ (\cdot, \cdot) \equiv \lambda a : A. \lambda b : B. \lambda C : \mathcal{U}. \lambda g : A \to B \to C. g(a)(b)$$
$$ ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. g(pr_1(p))(pr_2(p)) $$

This gives the correct defining equations (defining equations for $pr_1$ and $pr_2$ omitted) but this would mean that $ind_{A \times B}$ would have the wrong type.

$$\text{ind}_{A \times B} : \prod_{C : A \times B \to \mathcal{U}} (\prod_{a:A} \prod_{b:B} C((a, b))) \to \prod_{p : A \times B} C((pr_1(p), pr_2(p)))$$

And there doesn't seem to be a simple fix to this. I also thought about the following definition.

$$ ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. p(C(p))(g) $$

But this just doesn't typecheck.

Another idea I had is to use $uniq_{A \times B}$ to convert $C((pr_1(p), pr_2(p)))$ to $C(p)$ but it's not clear how to make that work. First off I'd have to show how to reduce identity types dependent function types which is proving even harder in my scribblings than products. Additionally $uniq_{A \times B}$ doesn't seem to be definable without the proper form of induction so even if I allowed myself identity types as presented in the book I'd be no closer to having a definition of $uniq_{A \times B}$

So it seems like we can define the recursor here but not the inductor. We can define something that's pretty close to looking like the inductor but doesn't quite make it. The recursion lets us perform logic taking this type to be the meaning of logical conjunction but it doesn't let us prove things about products which seems lacking.

Can we make the sort of reduction I claimed can be made? That is, can we define a type using only dependent function types and universes that has a pairing function and inductor with the same defining equations and types as products? It's my growing suspicion that I made a false claim. It seems like we're able to get so frustratingly close but just not quite make it. If we can't define it what kind of argument explains why we can't? Do products as presented in the HoTT book increase the strength of the system?


texts: Do all programming languages adhere to the IEEE 754-2008 standard?

texts: I am well aware that the float data type's maximum value is approximately 1.8E308, which means that across the various programming languages such as dearly beloved Java, the maximum factorial we can compute with this primitive data type is that of 170. Trying to compute the factorial of 171 and beyond gives errors. Here, PHP behaves the same way. In one of the answers from here, JavaScript also poses problems with factorials greater than 170. I understand that all this happens because that is what the de facto standard defines. My question is, are there non-esoteric programming languages that don't adhere to the IEEE 754-2008 standard? If there are, it would be interesting to see how they deal with factorials.


texts:
I've seen two versions of the cross entropy cost function, and conflicting information about it.
\begin{equation}J(\theta) = -\frac{1}{N} \sum_{n=1}^N\sum_{i=1}^C y_{ni}\log \hat{y}_{n_i} (\theta)\end{equation}
 $$ C(\theta) = - \frac{1}{N}\sum_{n=1}^N \sum_{i=1}^{C}[ y_{ni}\log (\hat{y}_{ni})+ (1-y_{ni}) \log(1-\hat{y}_{ni})]  $$

Some are saying that the second one is equivalent to the first for the case where there are only two classes, which makes sense. But couldn't the second one also be used for more than two classes? For example, say we have three class classification, with the ground truth $\vec{y} =
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}$ and $\vec{\hat{y}} =\begin{bmatrix}
0.7 \\
0.1 \\
0.2
\end{bmatrix} $. Then with the first equation, cross entropy would simply be $-\log(0.7)$. But couldn't we also use the second equation and calculate cross entropy as $-\log(0.7) - \log(0.9)-\log(0.8)?$ When would we use the first equation and when would we use the second one, and why?


texts: How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?

texts:
I'm having a hard time understanding the actual proof of this proposition:

$\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$

The sketch of the proof is on slides 6-8 of this PDF.

So I let $L \in \mathsf{NP}$. That means that there's a deterministic polynomial-time TM $M^1_L$ s.t. $x \in L \iff \exists w. M^1_L(x,w) = 1$. I now need to construct a deterministic poly-time TM $M^2_L$ s.t. $x \in L \iff M^2_L(x) = 1$.

Looking at the proof in the slides above, I realize that given $x\in\{0,1\}^n$, $M^2_L$ needs to somehow find a witness $w$ for $x$ and then simply return whatever $M^1_L(x,w)$ does. But how do I find that witness?


texts: How are quantum computers able to process certain tasks faster than regular computers?

texts:
I've read posts everywhere and watched videos but still I don't understand one part of it. How are they able to process all these operations in parallel.

So based on the landscape example here.

How would a quantum computer be able to check all those areas at once rather than the traditional algorithm to check random areas or process through the entire landscape


texts: How can I find the max degree of concurrency and the critical path of task dependency graph?

texts:
I study Parallel Processing,
and I get stuck into how to calculate the maximum degree of concurrency for task dependency graph.
I know that the max degree of concurrency is the largest number of concurrent tasks, and I have to calculate the sum of their weights, but in this graph, there are no weights and no fixed number of nodes.
can someone explain how can I find the solution for the following graph?
Note: the numbers insides the nodes represent the levels, not the weights.
Thank you all


texts: Dataflow framework for global analysis: Why meet, then apply?

texts:
In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides).  In this framework, an analysis is defined by a set of transfer functions, along with a meet semilattice.

At each step of the iteration, the algorithm works by maintaining two values for each basic block: an IN set representing information known to be true on input to the basic block, and an OUT set representing information known to be true on output from the basic block.  The algorithm works as follows:

Compute the meet of the OUT sets for all predecessors of the current basic block, and set that value as the IN set to the current basic block.
Compute $f(IN)$ for the current basic block, where $f$ is a transfer function representing the effects of the basic block.  Then set OUT for this block equal to this value.

I am confused about why this algorithm works by taking the meet of all the input blocks before applying the transfer function.  In some cases (non-distributive analyses), this causes a loss of precision.  Wouldn't it make more sense to apply the transfer function to each of the OUT values of the predecessors of the given block, then to meet all of those values together?  Or is this not sound?

Thanks!


texts: How is the run time calculated in this insertion sort algorithm?

texts:
I am looking at this algorithm in CLRS page 26:

I am a novice when it comes to these things so please make your explanations as simple as possible.
For the cost column, does c1, c2, c4, etc denote a value the same way n does, or are they just labels? My understanding is an operation takes one time unit (such as j=2 is an operation that writes something once, therefore its one time unit) so does c1 mean one time unit?
Secondly, why does key=A[j] happen n-1 times?
Thirdly, line 3 is a comment therefore does not have an execution, so why does it happen n-1 times?


texts: Can we compute the sum of a range of entries in $O(1)$ time?

texts:
I have encountered a few tests in algorithms which ask for
a data structure which allows to get the sum of all the elements of an array in the range [i..j], in O(1) time.

Is it even possible to do so?


texts: How does one formally show that two lambda functions are $\alpha$ equivalent?

texts:
I was going through the following slides and I wanted to show the following:

$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$

formally. They define a an $\alpha$-conversion on page 15 as follows:

$$ \lambda x . E = \lambda z.(E[x \leftarrow z])$$

however, I wasn't sure how to formally show the statement I am trying to show. Essentially I guess I don't know how to formally show in a proof that two distinct objects actually belong to this same equivalence class. The intuition and idea is clear, but how do I know if I've shown the statement?

In fact if someone can show me how to do the more complicated one too that would be really helpful too:

$$ \lambda x.x (\lambda y . y) \equiv_{\alpha} \lambda y . y (\lambda x. x)$$

how do I know if I've shown what is being asked?

Actually I think page 16 is the one thats confusing me most:

  Using the equation above, one has now the possibility to prove
  $\lambda$-expressions "equivalent". To capture this provability
  relation formally, we let $E \equiv_{\alpha} E^\prime$ denote the fact
  that the equation $E = E^\prime$ can proved using standard equational
  deduction form the equational axioms above (($\alpha$) plus those for
  substitution).

  Exercise 3 Prove the following equivalences of $\lambda$-expressions:

  $\lambda x.x \equiv_{\alpha} \lambda y.y$,
  $\lambda x.x (\lambda y.y) \equiv_{\alpha} \lambda y.y (\lambda x.x)$,
  $\lambda x.x(\lambda y.y) \equiv_\alpha \lambda y.y(\lambda y.y)$.

what does:

  can be proved using standard equational deduction from the
  equational axioms above

mean?

Since there is already an answer that is not helping (because I don't understand the notation) I will add what I thought was the answer but I'm not sure:

I would have guessed that:

$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$

if and only if there is a variable such that if we plug it into the lambda functions evaluates to the same function with the same variables. i.e.

$$ \lambda x. x \equiv_{\alpha} \lambda y . y \iff \exists z \in Var : \lambda x . x = \lambda z. ( (\lambda y . y)[y \leftarrow z] )$$

if we set $z = x$ we get:

$$\lambda z. ( (\lambda y . y)[y \leftarrow z] )$$
$$\lambda x. ( (\lambda y . y)[y \leftarrow x] )$$
$$\lambda x. (\lambda x .x )$$

which I assume the last line is the same as $\lambda x .x$ but I am not sure. If that were true then I'd show I can transform $\lambda y . y$ to $\lambda x . x$ which is what I assume the equivalence class should look like. Where did I go wrong?


texts: Why is a Knapsack problem not an LP problem?

texts:
We know that LP can solve optimization problems that have linear constraints and linear objective functions.

A knapsack problem can be formulated into a linear objective function (because it is just a summation of Pi*Xi) and linear constraints (because it is just a summation of the items weights which should be <= the knapsack weight), so why can't we consider it an LP problem?


texts: Need some guidance on CFG pumping lemma proof

texts:
I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something for this one.
The language I need to prove is not context-free is: $L = \{a^ib^jc^k | i \neq j, i \neq k, j \neq k\}$
So I understand the basic idea of what I need to do: find a string which I can split into sub-strings u,v,w,x,and y such that no matter where I place v and x, they can be pumped to make $i=j$ or $i=k$ or $j=k$.
My strategy I was using was to make i, j, and k different multiples of p (the pumping length). But the problem is that v or x can be any length from 1 to p, and I can't come up with any length for i,j, or k so that all those potential lengths of v/x can be pumped to make i or j or k equal.
I feel like I am overthinking this problem or am overlooking some property of the pumping lemma that will help me.
I am NOT looking for the answer, but rather just some guidance on how to think about this problem, as I think my current strategy is impossible.


texts: I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive functions?


texts: I have searched a lot for this, but apparently there is no result on calculating any bound on the error $||Q-Q^*||$ when I stop Q-learning after say $N$ iterations ($Q$ is the vector of Q-values at current iteration and $Q^*$ is the optimal Q-value). Let's assume that you have visited each state-action pair at least once and you know/store the number of visits. I would really appreciate any pointer to any relevant reference.


texts: What is the best way to algorithmically sort physical boxes?

texts:
I work part time at UPS. Part of my job consists of taking boxes from in front of me, determining if the correct cage (1 of 6 moving cages) is behind me (true about 50% of the time), and then putting the box down either in the cage or back in front of me. There can be 6-20 boxes in front of me at any given time depending on box size (essentially the available storage for the sorting algorithm). Each time a box is removed it is replaced with another random box, if there is room for that box. If the next box is particularly large, 3-4 boxes may need to be removed first (meaning that removing a box does not guarantee a new box will appear unless the total number of boxes is sufficiently small). The number of boxes can be considered infinite (UPS does ship nearly all of Amazon’s boxes, after all).

I’m trying to figure out the best strategy for sorting these boxes, partially to work faster and partially for fun.

A few more details

2 boxes cannot be picked up at the same time (they can be up to 70 lbs). The boxes can, however, be slid sideways. This means a box can be picked up and inserted between other boxes, but two non-adjacent boxes cannot be swapped in a single movement.
Boxes can be stacked. However, the stack still needs to be put into the cages one by one. Stacking can reduce the number of comparisons needed (because you know all boxes in a given stack go to a certain cage), but not the number of movements required.
Boxes must be picked up to be evaluated
1 cage will disappear and a new cage will appear every 10 seconds, in a predictable order
If the correct cage is not behind me, I must either wait for the cage or set down the box on the shelf and select a new box

Computational time (seconds)

Picking up a box: 1
Evaluating a box: 2
Placing a box in its original location: 0
Placing a box in a new location: 1

Examples:

Picking up a box, determining that the correct cage is not behind me, and putting the box back where it came from: 3 seconds
Picking up a box, determining the correct cage is behind me, placing the box in the cage: 4 seconds
Picking up a box from a presorted pile and placing it in the correct cage: 2 seconds
Picking up a box and placing it in a cage without sorting: 2 seconds (plus the time to find a new job)

For context, the current rate is around 700 boxes per hour (5.14seconds/box). So reducing the average time per box by only 0.5 seconds is a fairly significant change.

What is the most time-efficient way to move the boxes from the shelf to the correct cage? Solutions to simplified versions of this problem are also welcome.


texts: How to prove that a stack is equivalent to a queue with reversed inputs

texts: Say I push the values 1,2,3,4 onto a stack. Then popping them, they will come back in the order 4,3,2,1. If I push the values 1,2,3,4 onto a queue then removing from a queue results in 1,2,3,4. However if I push them onto the queue in reverse order, 4,3,2,1, and then pop them from the queue they come out in the same order as a stack. So a queue with its inputs reversed looks a lot like a stack. Are there any formal methods for proving this?


texts:
I need to prove that

$\forall a>0.BPP[{a,a+\frac{1}{n}}]=BPP$

$BPP[a,b]$ definition:

  A language L is in BPP(a,b) if and only if there exists a
  probabilistic Turing machine M, such that

  M runs for polynomial time on all inputs For all x in L, M
  outputs 1 with probability greater than or equal to b For all x
  not in L, M outputs 1 with probability less than or equal to a

I've tried using the Amplifying Lemmas and then Chernoff Inequality, when my sketch of proof was to run the probabilistic Turing Machine on the input $k$, times and then accept or reject according to majority of accepting or rejecting of the simulated runs.

My problem is with the choosing of $k$. No value that I chose could work with the lower and upper bounds.

Am I in the right direction? Could I get a tip regarding $k$?


texts: What would be a good way to prove NP-Completeness of Min-satisfiablity problem

texts: I am trying to prove the NP-Completeness of Min-satisfiability problem which can be defined as: Given a CNF formula (Set of clauses of 1 or more boolean variables) and a number x, there exists a satisfying assignment of those variables such that number of true variables in the assignment is less than or equal to x


texts: Why is Read(Q) timestamp is not checked when a transaction issues a command reading Q?

texts:
Consider a concurrent schedule of two transactions $T_1,T_2$:
$R_x(Q): T_x$ Reads $Q$
$W_x(Q): T_x$ Writes $Q$
$S:R_2(A),R_1(A),W_1(A),W_2(A)$, this schedule is not conflict serializable.However, if we follow timestamping protocol, where $TS(T_1)<TS(T_2)$ S is allowed because $T_1$ can read a variable after $T_2$ has read it, which is not conflict equivalent to schedule $T_1 T_2$ and is contradictory to the fact that timestamping protocol gives a conflict serializable schedule. What am I missing here?


texts: Does this algorithm exhibit the same behavior as Selection Sort?

texts:
This is a homework question. I have been asked to identify what sort this code below implements.

sort(arr of length n, left, right):
  if (left > right): return

  for i from 0 to n:
    if i >= right and arr[left] > arr[i]:
      left = i

  swap(arr, left, right)
  left = right
  right = right + 2
  if (right < n):
    sort(arr, left + 1, right - 1)
    sort(arr, right - 1, left)

sort(arr):
    sort(arr, 0, 0)

After writing the code's trace on paper, I've come to think that it's a selection sort because from the original table [50, 15, 33, 27, 89, 12, 18] after passing one time through it we obtain [12, 15, 33, 27, 89, 50, 18]. We looked for the smallest element in the table and then put it first. this seems like the typical behavior of selection sort.

I want to confirm if I am right or wrong because I do not have access to the solution of the problem.


texts:
So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard.

On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).

Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.

So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard?
Did I miss something else?


texts: Non-primitive recursiveness in real world nonmathematical software?

texts:
Is there a real world nonmathematical example of computer software that isn't primitive recursive?

I'm not interested in examples that are somehow closely related to theory of computation or logic (like automated theorem proving, model checking, compiler design etc.), or examples that aren't primitive recursive in a trivial way (i.e. having unbounded loops that could have been bounded).

The example doesn't have to be an actually existing piece of code (although it would be great if it is).


texts:
QV Le et al. show in Building high-level features using large scale unsupervised learning (2012) how to use unsupervised learning of a deep neural net to recognize faces and cats. Working through this paper, I have a few questions:

1) Their neural net has an input layer (200x200 pixels times 3 channels) and then nine layers on top of it, and I wonder how large these layers are. It is mentioned that each of the nine layers has 8 "maps". Does this mean that the layers all have size 200x200x8? Their pictures seem to suggest that deeper layers are smaller.

2) In section 3.3 on p.3, they say "During learning, the parameters of the
second sublayers (H) are fixed to uniform weights". Does this mean that the second sublayer parameters are never changed and always stay uniform? Or is there a later training phase where those parameters are changed? I suspect the latter, because on p.4 they talk about "distributing the local weights W1, W2 and H to different machines."

3) Their objective function (formula (1) on p.4) contains the term $\sqrt{\epsilon+H_j(W^T_1 x^{(i)})^2}$ which I cannot parse. Do they mean $\sqrt{\epsilon+(H_j W^T_1 x^{(i)})^2}\ $? I would think not, because the pooling layer neurons output the $L^2$-norm of their weighted inputs, and that's not what this formula describes. Maybe they use the notation $(v)^2$ for the vector of squared components of the vector $v$?


texts: How to enumerate combinations in parallel

texts:
I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried to do it with Matlab but it takes too long time specially when $n>20$ and I couldn't find a way how to generate in parallel the $n\choose k$ indices.

I found online a paper titled A Parallel Algorithm for Enumerating Combinations but they didn't provide their code in that paper.


texts: $A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

texts:
Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition:

  Let $\Sigma = \{0,1\}$. If $A$ and $B$ are Turing-recognizable and $A \cup B = \Sigma^*$, then there exists a Turing-decidable language $C$ such that $A \cap \overline{B} \subseteq C$ and $\overline{A} \cap B \subseteq \overline{C}$ (equivalently, $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

So, my current train of thought is as follows.
Because $A \cup B$ is $\Sigma^*$, we have that $\Sigma^*$ is partitioned into exactly three disjoint sets: $A - B$, $A \cap B$, and $B - A$. That is, given $x \in \Sigma^*$, $x$ is in exactly one of these sets.

The basic way I can think of to obtain a decidable language is to enumerate one in lexicographic order (which always yields a decidable language). So one idea would be to enumerate $\Sigma^*$ in lexicographic order, and print a string if and only if it is not in $B - A$, but that poses a problem because we would have to decide membership in $B - A$, but they are merely recognizable.

I've thought about enumerating $A$ and $B$ but since they're only recognizable, the enumerations could be in any arbitrary order, making it impossible to compare them to test for membership in $A-B$ or $B-A$.

Finally, I know that $A$ and $B$ (if they are infinite) have infinite decidable subsets, but I don't think that will help.

I'd appreciate some hints if anyone has any.

Edit: Missed a hypothesis that $\Sigma = \{0,1\}$, which I'm not sure is relevant (I wouldn't think so), but it might be.


texts: Search problem when the effects of actions are not deterministic

texts:
The standard search problem studied in AI contains:

An initial state $A$;
A final (goal) state $Z$;
A set of actions that can change the state; each action takes as input a certain state and returns another state.
A solution to such a problem is a sequence of actions starting at $A$ and ending at $Z$.

I am interested in the following variant:

Each action can return one of several states; it is not known which state will be returned.
A solution is a tree in which each path from the root ends at $Z$.

For example: Suppose we start at state $A$ and do the action "ABRA". This action can return state $D$ or state $E$. In state $D$ we can do the action "DAMA" which returns state $Z$; in state $E$ we can do the action "EAGL" which can return either state $Z$ or state $Y$. In state $Y$ we can do the action "YADA" which returns state $Z$.

The motivation here is automatic construction of algorithms. Every solution is an algorithm for reaching from $A$ to $Z$. For example, the above solution can be read as the following algorithm:

Begin (state=A)
   ABRA
   If D then
      DAMA
      End (state=Z)
   Else If E then
      EAGL
      if Z then
         End (state=Z)
      Else  (state=Y)
         YADA
         End (state=Z)
      End If
   End If
End

MY QUESTIONS:

What are good references that deal with this kind of search problem?
Are there any usable solvers for solving such problems (similar to e.g. planners or solvers for usual search problems)?


texts: Long multiplication school method: number of primitive operations to calculate first partial product?

texts:
Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long multiplication.

I have read in my introductory book (Mehlhörn's 'Algorithms and Data Structures') that each partial product requires 2n + 1 primitive operations.

Now I understand, I think, where the +1 comes from for the first partial product at least, as in there being one extra digit in the result for the first partial product, but I don't understand why it is "2n" + 1, as it seems to me it would be more like n + 1, so I am defintely missing something important here. By 'partial product', I mean the result arising from the first intermediate calculation of the multiplication problem.

I am of course also totally confused about quantifying the rest of the primitive operations required to get the final result/product! But I would just like to understand where the 2n is coming from for now for the first partial product. Just to add my guess from what I have seen in addition: does the 2 in 2n refer to a maximum guiding number, rather than a definitive one?

Here is a link to the chapter in the book I am learning from: http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Appetizer.pdf

I understood primitive operations to mean: addition and multiplication.
The author does write at bottom of pg.1

"...we have two primitive operations at our disposal: the addition of three digits with a two-digit result (this is sometimes called a full adder), and the multiplication of two digits with a two-digit result"

The product of two n-digit numbers when they multiplied together needs then: 3n^2 + 2n primitive operations.

It is the algorithm as per the method taught at school for long multiplication problems.

(All of this is on pgs 1 and 2 of chapter)


texts: create distance (ment is high difference between values) between Vertexes in a list

texts:
Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number in one vertex and higher the one in one of the Vertexes connected to it by 1 in one so called "step". How would an Algorythm works that calculates the minimal number of steps after that every the difference between the number in two neighbor-vertexes is over a certain value?

Here an example since you might not understand what I'm trying to explain:

first a given List of vertexes with numbers in them:

2 5 1 3 4

now a step would look like that:

2 5+1 1-1 3 4
= 2 6 0 3 4

or like that:

2 5 1 3-1 4+1 = 2 5 1 2 5

now just reaching the goal with a min difference of 5 (hope I make no mistakes here):

2 5 1 3 4

1 6 1 3 4

1 6 1 4 3

1 6 1 5 2

1 6 1 6 1

(the list of vertexes at the beginning is random, as well as the result is so symetric in this case)
(since a list is a graph there are these tags)