texts: Maximal majoritarian program under incomplete voting

texts:
I have conducted two surveys on French political preferences. As half of each sample (of ~1000 persons) gave a satisfactory margin error, I have randomly displayed (or not) several questions. Now, I have an incomplete dataset of the preferences of the sample over many political propositions (I can provide it if needed). For the sake of simplicity, let us assume that for each proposition of reform, either the respondent agrees for a change (True), or not (False), either the question was not asked to him-her (NA).

I am looking for a political program (i.e. a set of propositions) which gathers a majority of adhesion: I call this a majoritarian program. For a program to be majoritarian, we need that a majority of the respondents agree jointly with all the propositions of the set. As the dataset is incomplete, we need to check that any subset of propositions in the program gathers a majority (i.e. gathers more True than False). Indeed, it could be that only 5 respondents have voted to all the propositions in the program, by chance all favorably; then, we could still not deduce that this program is majoritarian because one of its proposition could have failed to obtain a majority itself.
Finally, I am looking for the maximal majoritarian program, i.e. the largest one (in terms of number of propositions).

Does anyone have an idea on how to solve exactly this computational problem? Any insight on the question is welcome, including broader reflection on optimizing over the subsets of a big set.

So far, three methods have come to my mind to solve this problem:

Brute force
I have optimized an exact algorithm (which I can provide). With my (rather small) dataset (a hundred propositions), it works if I restrict the number of propositions I analyze to 47, but it is way too computationally demanding if I try to analyze all propositions. Indeed, the number of potential programs of size k grows exponentially: it is $2^k$.
Completion of data I haven't try this because I don't know the theory of imputing missing data. If such an imputation proves always reliable, then the problem may be solved. Indeed, a friend have shown me a way to reduce my problem to linear optimization as long as the dataset is complete.
Machine learning By defining appropriate an weight on each answer, that depends on the examined program, we can train a neural network to find the best ordering of propositions so as to form our program with the adequate number of highest-ranked propositions. (The gain function values individual adhesion to the program as well as its size.) However, this method is just an heuristic for the problem, and its solution is simply a proxy for the real answer. Indeed, the necessary check of the potentially maximal program may take too long a time (as we need to examine each subset of propositions in the program). Nonetheless, I will implement this method soon.


texts: Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

texts:
A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges.

Because the HC has an extra edge we could say that in general, the weight of every Hamiltonian cycle of a connected graph will be more.

If we take an edge of every Hamiltonian cycle we will find an MST and by that, the MST weight will be always lower than HC.

There is a way to prove this where MST tree not necessary belongs to the HC?
There is more definitive proof for this?


texts: If $L_1,L_2\in \mathrm{NP}$ and $w\in L_1$ or $w\in L_2$ then can $L_1\cup L_2=L$'s verifier use the same certificate $c$ for $w$?

texts:
I read the following solution for Showing that $\mathrm{NP}$ is closed under union
and they used the same $c$ for both the verifies $V_1$ and $V_2$. Why is it correct?

Let $L_1$ and $L_2$ be languages in $\mathrm{NP}$. Also, for $i = 1, 2$ let $V_i(x, c)$ be
an algorithm that, for a string $x$ and a possible certificate $c$,
verifies whether $c$ is actually a certificate for $x \in L_i$. Thus, $V_i(x,c) = 1$ if certificate $c$ verifies $x \in L_i$, and $V_i(x, c) = 0$ otherwise.
Since both $L_1$ and $L_2$ are both in $\mathrm{NP}$, we know that $V_i(x, c)$ terminates
in polynomial time $O(|x|^d)$ for some constant $d$. To show that $L_3 = L_1 \cup L_2$ is also in $NP$, we will construct a polynomial-time verifier $V_3$ for $L_3$. Since a certificate $c$ for $L_3$ will have the property that
either $V_1(x, c) = 1$ or $V_2(x, c) = 1$, we can easily construct a
verifier $V_3(x, c) = V_1(x, c) \lor V_2(x, c)$. Clearly then $x \in L_3$ if and
only if there is a certificate $c$ such that $V_3(x, c) = 1$. Notice also
that the new verifier $V_3$ will run in time $O(2(|x|^d))$, which is
polynomial. Therefore, the union $L_3$ of two languages in $\mathrm{NP}$ is also in $\mathrm{NP}$, so $\mathrm{NP}$ is closed under union.

taken from here.
$M_1,M_2$ TM which accept $w$ can accept $w$ for different reasons so we can't claim that $c_1=c_2$
Questions:

Is it legal to use the same certificate for both $V_1,V_2$ in the answer? Why?

Is a verifier by definition is deterministic TM?

In the above answer, does $V_3$ runs $x,c$ on both $V_1$ and $V_2$ in the worst case?


texts: If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

texts:
If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time?

Intuitively this sounds correct, as BFS does not visit a node twice, and it only traverses from vertex $v$ to vertex $u$ iff it hasn't visited $u$ before, such that there aren't going to be any cycles, and if $G$ is connected it will eventually visit all nodes. Since the weight of all edges is equal, it doesn't matter which edges the BFS chose.

Does my reasoning make any sense?


texts: How to write a recursive function that with certain time complexity

texts:
I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

public void run(int n)

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.


texts:
I think it stores the address of the current instruction. And if this instruction is completed the program counter is incremented by 1, to get the next instruction.
But now my question is, how do you increment the program counter by 1? It would mean you increment an address by 1, how does this work?


texts: Finding all pairs of points with no point in between

texts:
Suppose there are $n$ points $p_1,p_2,\dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If there are $k$ pairs with the described property, design an algorithm with $O(n\log k)$ that uses idea of divide and pruning.

I think if we check all points we can solve this problem, but running time will exceed $O(n\log k)$.
I think for solving this problem we can use projective geometry duality, but I am stuck. Any help would be appreciated.


texts: Determine saving moves for a checked king

texts:
In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and keep those that remove the king from check in a list.
Not like it's particularly expensive computationally-wise with a board of 8x8, but just for the sake of knowledge - is there a more efficient algorithm to calculate the saving moves?


texts: algorithm to delete nodes that completely removes connectivity

texts:
This is a distributed systems problem, but perhaps the graph theory gurus can help me.

I need an algorithm that that tells me which nodes to remove from the graph to completely remove connectivity.

See example:

The most intelligently thing to do would be to remove the bcasts nodes:

Can you help me? One way to solve this would using a SAT or ILP solver, but I want to if there are any other algorithms for this kind of task.


texts: How can I find the center character of a two-tape Turing Machine in n transitions?

texts:
The problem I have been given is to find a two-tape ND Turing Machine over {a,b,c} that only accepts odd length strings with a c in the middle position. The problem with this is that the question specifies that it must be done in n+2 transitions.

I can figure out how to do it in 1.5 * n transitions, by iterating over the tape and writing every other character to the second tape, then reversing at a space input and going back the same number of characters that are on the second tape. There are some other methods I thought of, but the lowest number of transitions I can get to is 1.5 * n which is not low enough.

This is homework so I am not looking for a full resolution or a walkthrough, but if anyone can point be in the right direction I would be very grateful as this has been irritating me for half a day now.


texts: Computation Complexity of stream algorithm

texts:
I want to analyze a clustering algorithm that clusters data stream.
Since the stream can be unbounded, I cannot write O(N^2), or explicitly denote the size of the stream. How can I use the arrival rate of the data for the computation complexity? Do you have any other idea for correct analysis of stream computation (for clustering problems)?

Thank's


texts: Does iterated PSPACE trace equal ELEMENTARY?

texts:
I have the following feeling (I wouldn't even call it a conjecture yet) which I'd like to ask whether it's true in some form.

Take the class of all programs running in polynomial space.

Surprisingly or not, they can still output an exponentially large output: at each step of their running they may output something, and since they may perform 2^poly(n) steps, they may output such a large output as well.

Now suppose we take this output and feed it again to a PSPACE machine, and so on. It can also be seen as inputing to one PSPACE Turing machine the trace (if we don't like the idea of outputting outside of the tape) of the running of another PSPACE Turing machine, which again might be exponential in size wrt the original input's size.

By that, do we cover the whole ELEMENTARY complexity class? If not, then any known class? It seems to me obviously beyond PSPACE and EXPSPACE or even n-EXPSPACE if we allow n+1 such iterations.

As per D.W.'s request, here's a more precise formulation of the question.
Consider the class consisting of all possible pairs of PSPACE Turing machines. We consider running the pair of machines as follows. One machine takes an input and runs, and the second machine takes as input the trace of the running of the first machine. Which complexity class would this capture? It seems to me like EXPSPACE. Similarly if we took a triple of machines, two as above, and the third taking the trace of the second, it'd look to me like 2-EXPSPACE. Is that the situation indeed? What would be the computational power (in terms of complexity classes) of such iterated two (or more) different machines, one taking as input the trace of the other?

I guess that if this is correct and two iterated PSPACE machines capture EXPSPACE or beyond, then it'll prove that P!=PSPACE. So either it's all wrong and one can show me why it's wrong, or maybe even if it's right it doesn't actually imply P!=PSPACE.


texts: How do I calculate the probability of a PCFG rule in a parser?

texts:
I'm quite struggling with calculating the probability of a rule for a PCFG.

I've been looking for examples online and more information, but I am none the wiser.
Here is an image of the slides. I cannot understand how the numbers are calculated on the left. From what I understood, I have to take a rule and see how many times it's been used in the tree and then divide it. However, then the numbers that I get do not match this example at all. I feel like I'm missing something small and I've been starting at this for a few hours now and I'm going crazy.

Thank you!


texts: Decidability of a language and inclusion between two other languages

texts:
I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer:

"Let L₁, L₂ be decidable languages.
For every language L s.t. L₁ ⊆ L ⊆ L₂, L is decidable too

My first idea was to use the Halting Problem Language as L and show that is not decidable to prove the statement is false.

I tried to ask the Professor and he confirmed me that the assignment is false but he gave me a hint about explicitly describing the two languages L₁ and L₂, but I don't know which one would fit for this scope.

Thank you!


texts: How do I prove that SPACE($n^{555}$) $\neq$ NP?

texts: I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.


texts: Printing The Longest Path from Root to Leaf in Binary Tree

texts:
I am stumped as to how to print the longest path from the root of a binary tree to a leaf, essentially traversing the height of the tree. I've got the following for finding the height of a binary tree:

if (root == null) {
    return -1;
}

return 1 + (Math.max(heightOfTree(root.leftNode), heightOfTree(root.rightNode)));

This easily finds the height of the tree but doesn't lend itself to actually figuring out which nodes should be printed out. I could go about finding the nodes's value that is at the leaf, and then do a find for that particular node, but that seems inefficient.

        A
      B   C
    D  E F  G
             H

For example, the height of this binary tree is 3, and I would ideally like to know the path to take, in this case it would be A, C, G, H. I know that I most likely need to keep an array for the path, but I just can't seem to find a solution that isn't terribly inefficient.


texts: Does exploiting a spatial Locality in Cache always leads to a lower miss rate?

texts:
I've read that, incorporating many words(spatial locality) per cache blocks leads to lower miss rate. Is it the case always?
One possibility of such approach is to make a single cache block of size equal to the size of the cache, but that would be meaningless as far as benefits of memory hierarchy are concerned. Isn't it so?


texts:
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.

int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

"In each iteration, the outer loop executes $\frac{n^{2}-(2i-1)n-i+i^{2}}{2}$ operations from the inner loop for $i = 0, \ldots, n-1$."

Can someone please explain this to me step by step?

I believe the formula above was obtained by using Gauss' formula for adding numbers... I think...


texts: Static access pattern in Distributed Databases

texts:
The access patterns of user requests may be static, so that they do
  not change over time, or dynamic. It is obviously considerably easier to plan for
  and manage the static environments than would be the case for dynamic distributed
  systems. Unfortunately, it is difficult to find many real-life distributed applications
  that would be classified as static. The significant question, then, is not whether a
  system is static or dynamic, but how dynamic it is. Incidentally, it is along this
  dimension that the relationship between the distributed database design and query
  processing is established.

What does it mean for an access pattern to be “static”? Could you show a practical example of a static access pattern?


texts: Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages

texts:
How can I prove this identity of languages?

My aproach is the following:

Let A, B and C to be languages, and let x to be an arbitrary string.

(A ∪ B) ⇒ x ∈ A ∨ x ∈ B

How do you proceed?


texts: Data structure for a single elimination tournament and its implementation

texts:
I want to implement a tournament managing software , something like challonge(https://challonge.com/) and am currently stuck at the data structure to be used. I read up on tournament trees and a format like this, https://i.stack.imgur.com/UOMVI.png . The problem I am facing is in balancing it.

The method works very well for a power of 2 number of players but when the number of players is not a power of 2, it was suggested somewhere that I make it as the next highest power of 2 and fill the empty places with dummies with whom the opponent always gets a win ( basically a by) but then issue comes in inserting values. To explain my issue assume that are 100 players so we will have to use a 128 leaf node tree but the issue then is that if I do perform linear insertion in the tree leaves , the fourth quadrant of the tree will be almost empty with only 4 players. This basically would lead to that person going to the semis with two matches .

Is there some tree implementation that takes care of this issue where the leaf values can be evenly spread out so that we don't get a scenario like this. Any other method of implementation of this Problem is also good, as long as the data can be stored in a SQL database.


texts: Why can't DFA's have 0 exiting arrows for some input symbols?

texts: Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an exiting arrow for input 0 from this nonaccepting state, which is just redundant. Why not draw no arrows at all for 0?


texts: Recurrence relations and induction: guessing the right bound

texts:
I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$
This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-1)+n$$ and $$T(n)=T(\sqrt{n})+1$$ because they were both easier to solve.
Does it makes sense to guess an upper bound for the original recurrence relation (and try to confirm that guess through induction) based on the complexities I obtained for both for these (i.e. use the one with larger order of growth for example)?
If not then what are some ways to find/guess an upper bound for such a relation?


texts: Show that the regular languages are closed against taking "the second half"

texts:
Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the creation of such NFA proving it is regular.

However, what if you wanted to prove the 2nd half string is regular, not the 1st half of a string.  That is,

$$\mathrm{2HALF}(L) = \{ x\mid yx\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

Compare this to the standard

$$\mathrm{HALF}(L) = \{ x\mid xy\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

I struggled on a solution, trying to use the same method as used on $\mathrm{HALF}(L)$ but can't seem to wrap my head around it.


texts: Selection of dates respecting delay constraints

texts:
I encountered an issue at work that can be derived approximatively to this problem.

Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) possible triggering times per day.

I have to select exactly 5 times per day (between 00:00 a.m. and 12:00 p.m) to respect the following constraints:

a minimum delay between two selections (for instance 2 hours)
a maximum delay between two selections (for instance 10 hours)

The delay between the last selection of the day and the first of the next day also has to be considered for constraints.

I need an algorithm that find one solution or if there is no solution.

Until now, I did not have the constraint on the maximum delay. Thus, I solved it greedily, day after day, picking the soonest possible date until 5 times are selected. At any moment if no times was available for the day, the problem had no solution.

So does this maximum delay constraint make the problem NP-complete ? Or is there a polynomial algorithm that can solve it ?


texts:
The Dual of a Boolean function $F(x_1, x_2, ..., x_n)$, written as $F^D$ is the same expression as that of $F$ with $+$ and $.$ swapped. $F$ is said to be self dual if $$F=F^D$$

How can we count total number of self dual function with $n$ Boolean variables.

I know For $n$ variables total $2^n$ minterms or maxterms are possible and any boolean function can be expressed as combination of minterms or maxterms. But what else is required to count all self dual functions of $n$ variable.


texts: How can feature structures be applied to text summarization?

texts:
I'm looking for innovative ways to create text summaries and I was
wondering whether feature structures can be used for such a task.

Is it possible to create subsume and unification methods that
allow one to model text summary tasks using feature structures?


texts: What do queues and stacks correspond to in math?

texts:
Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, ....

As abstract data types, what do queues and stacks correspond to in math?
For example, some special paths in graph theory?

Have stacks and queues been treated mathematically and, if so, how are they usually treated within mathematic?

What mathematical concepts form the basis for stacks and queues?

Are there references that introduce data structures as models of monoids and other algebraic concepts? (Raphael said  data structures are)


texts: What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

texts: I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult.  Can anyone provide me concrete examples of what it means for something to be $\prod_x^y$-complete or $\sum_x^y$-complete, and when we can say that a problem is undecidable for some $(x,y)$?


texts: Are those definitions of universal hash family equivalent?

texts:
I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.

Definition 1:

$H$ is a universal hash family if and only if $$\mathbb{Pr_{h \in H}}[h(k) = h(l)] = 1/m$$

where $k \neq l$ and $k,l\in Key$ and $m$ is the Size of the Hashtable

Definition 2:

The same as above just substitute the equals sign with a less or equal sign.

Well, i think those definitions are equivalent, because i think the probability for a collision can't possibly be strictly less than 1/m or am i missing something?

P.S.
I'm assuming that the cardinality of Key is bigger than the size of the hashtable m


texts: Complexity as it relates to verifiers of languages

texts: So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time verifiers". Is there an analog statement that can be said about a P-class verification complexity? Because P is a subset of NP, I understand that the statement of NP still applies to P. Still, my intuition is that there is something more that can be said about a verifier for P that relates to oracles. Is there more that can be said?


texts: Efficient way to get integral points of segment from two points in grid

texts:
I have two lattice (grid) end points of the line, how can I generate intermediate points of the line segment between them?
One way is iterate through all the x points or y points and check (solve line equation) if the coordinates we get each time are integral solution or not.


texts:
Each of n distinct values is equally likely to be put into pile 1 or in pile 2, independent of each other. These piles are then sorted from smallest to largest. The two sorted piles are then merged into a single sorted pile by comparing the smallest values of each pile, putting  the smaller of these two into a new pile, and then repeating with the new smallest remaining values in each pile.

Whenever one of the piles is empty, the remaining ones from the nonempty pile are then put into the merged pile in their sorted order.
So the question is how to find the expected number of comparisons that are needed to merge the two sorted piles into a single sorted pile of all n items.

Answer:-At most,Mergesort requires  number of comparisons < $n\log n$. But I want to know how it is computed when n is odd, using the two inequalities

[1] $\log (x+1)\leq\log(x)+1$

[2]$\log(x+\frac12)+\log(x-\frac12)\leq 2log(x)$


texts:
Suppose that a stream of data is arriving like $(4,5) (5,6), \cdots ,(7,8)$, where for each particular tuple $(a,b)$, we have $a \in [n]$ and $b \in [k]$. I want to store this stream. In my setting $k = O(n^2)$, and there are no duplicates, so the stream has at most $nk$ pairs.

I want a data structure that supports three operations:

Insert$(a,b)$, for $a \in [n]$ and $b \in [k]$, adds the pair $(a,b)$ to the stream
Search$(a,b)$, for $a \in [n]$ and $b \in [k]$, checks whether the pair $(a,b)$ is in the stream
Delete$(a,b)$, for $a \in [n]$ and $b \in [k]$, removes $(a,b)$ from the stream.

I don't need to preserve the order of the stream.  I'm looking for a data structure where each operation should take $O(1)$ time.  Also I want the space usage to be at most $O(n)$ bits of space.  It is OK if the data structure is probabilistic.


texts: Why is "accepted by Turing Machine with even number of states" a trivial property?

texts:
$$
L = \left\{ \left< M \right>~\middle|~
\small{
\begin{array}{l}
L(M)\text{ is recognized by a Turing Machine} \\
\text{having even number of states}
\end{array}
}
\right\}.
$$

Isn't $L$ same as asking if $L\left(M\right)$ is recursively enumerable (RE)?  How is it trivial?

I know what it means for a property to be trivial, but I don't understand how the above property is trivial and decidable.


texts: What is the difference between a prime attribute and a proper subset of the candidate key?

texts:
I am taking DBMS classes and am currently studying the various normal forms. The following is the definition of a Prime Attribute I learned in class:

A prime attribute belongs to the set of attributes which compose the candidate keys.

For example, if R(ABCDEF) is a relation with the functional dependencies given as:

F = {AB -> C, D->E, C->F}
then,
Candidate Key will be ABD
and
the Prime attribute set will be {A,B,D}
and
the Prime Attributes are A,B and D.

The proper subset of a candidate key defines itself. For the above example, proper subsets of the candidate key for the relation R(ABCDEF) is:

{{A}, {B}, {D}, {A,B}, {A,D}, {B,D}}

From the above definitions, apart from the number of elements in either sets, it seems that a prime attribute and a subset of a candidate key are pretty much the same. Both of these terms are being brought up simultaneously while explaining Third Normal Form and Transitive Dependencies, which is confusing me. It would be nice if somebody clears the difference between them.


texts: Blum complexity measure for lambda calculus

texts:
Is there a formal complexity measure for lambda expressions which satisfies the Blum axioms and measures the complexity of reducing the expression to its normal form?

I assume that the complexity measure would have to operate on the Godelization of the lambda expression, as in "Gödelization in the Untyped lambda-Calculus" (Mogensen, 1999).


texts: How can I fill bookcases with shelves of books using the least number of bookcases?

texts:
Sorry for layman's term question, my background in computer science is weak.

What I have is a list of shelves with books of varying height.  Each shelf stores a value that describes how many shelves (of that height) can fit on a bookcase.  The bookcases have adjustable shelves so that we can maximize the usage of each one.

What I have been trying so far is sorting the shelves from shortest to tallest and filling in each bookcase, but what happens is that there are remainders which could be filled in with the small shelves.

I should mention that an additional complexity is that we want to place the tallest shelf on the top of the bookcase (because it would be more efficient).

I am not expecting a full on answer for how to do this... but I would very much appreciate a book or article on the topic.  I just need a little direction and I think I would be able to pick it up.

Thanks for your help!


texts: Concrete practical examples for discrete time markov chain with transition rewards

texts:
Can anyone show examples for discrete-time markov chains with associated transition rewards?

I am searching for examples of industrial usage of markov chains where their expect and variance or covariance of accumulated rewards until reaching some goal state subset are of practical interest.

I am searching for examples as concrete as possible, in the optimal case i.e. a concrete markov chain or a series of markov chains, so that I can run special algorithms (calculating variances/ covariances) on them in order to measure runtime of these algorithms.


texts: Where/how did a $\log(n)$ factor disappear from well-known algorithms?

texts:
Consider the binary search problem on a sorted array containing $n$ integers on
16 bits. Everybody agrees that the binary search needs $O(\log(n))$ time,
because it makes at worst $O(\log(n))$ steps. But: at each step it needs to
calculate a midpoint. The first midpoint is $[n/2]$. The next midpoint could
be $[n/2]+[n/4]$. If the searched number is placed in the second half of the
array, the midpoint at each step is no less than $[n/2]$. Each calculation of
a new midpoint involves at least a number with $O(\log(n))$ bits, hence each
midpoint calculation requires $O(\log(n))$. I obtain a more precise complexity
of $O(\log(n)^2)$. Where is the error?

The same problem could appear on countless algorithms that use arrays or
matrices. Take the most well-known dynamic programming algorithm for the
knapsack problem. Everybody agrees it takes $O(nW)$ time (e.g., the
wikipedia article on the knapsack problem), where $n$ is the number of items and
$W$ is the capacity. But at each step, it needs to compute a difference of
weights/capacities, which should account for an additional factor of
$O(\log(W))$. Where is the error?

Where/how does this $O(\log(n))$ complexity factor disappear? If we had needed
it, it would have appeared in many algorithms.

ps. A very similar problem arises in the questions asked here and here, thanks Ariel, Raphael and ryan for pointing this out.


texts: Prove the Droid Trader Problem is NP-complete

texts:
This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos.

A player in the game controls a spaceship and is trying to make money
buying and selling droids on different planets. There are $n$
different types of droids and $k$ different planets. Each planet $p$
has the following properties: there are $s(j, p) \geq 0$ droids of
type $j$ available for sale, at a fixed price of $x(j, p) \geq 0$
each, for $j = 1, 2, \dots , n$, and there is a demand for $d(j, p) \geq 0$ droids of type $j$, at a fixed price of $y(j, p) \geq 0$ each.
(We will assume that a planet does not simultaneously have both a
positive supply and a positive demand for a single type of droid; so
for each $j$, at least one of $s(j, p)$ or $d(j, p)$ is equal to $0$.)
The player begins on planet $s$ with $z$ units of money and must end
at planet $t$; there is a directed acyclic graph $G$ on the set of
planets, such that $s$-$t$ paths in $G$ correspond to valid routes by
the player. (G is chosen to be acyclic to prevent arbitrarily long
games.) For a given $s$-$t$ path $P$ in $G$, the player can engage in
transactions as follows. Whenever the player arrives at a planet $p$
on the path $P$, she can buy up to $s(j, p)$ droids of type $j$ for
$x(j, p)$ units of money each (provided she has sufficient money on
hand) and/or sell up to $d(j, p)$ droids of type $j$ for $y(j, p)$
units of money (so I'm assuming you can make multiple buy/sells at
each planet). The player’s final score is the total amount of money
she has on hand when she arrives at planet $t$.

I'm trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the 'hardness' of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don't know many NP-complete maximization problems other than quadratic assignment.
My thought process is that the droids have to represent something, for example choosing vertices of a graph. Then the price of the droid reflects the 'value' in some way; for example in a vertex cover reduction, the droid representing vertex $i$ would have a sale price equal to the degree of vertex $i$ for example.
Something that worked well for me for the previous 30 exercises was to consider a very simple version of the problem. So in this case, I considered cases where the planets were just a line graph, or there are only two types of droids, or each planets sells exactly 1 type of droid and buys 1 type of droid (so you can force the player to buy/sell instead of just holding on to their cash). I try to simplify in this way and see if it starts to resemble other NP-hard problems, which is why I suspect that it should be a vertex-cover or 3-sat reduction.
Any hints would be appreciated such as what problem X should I choose to reduce to Droid Trader Problem, or how should I view this problem (e.g. 3-SAT can be viewed as choosing one out of $2^n$ choices and then checking that the choice satisfies some set of contraints)


texts: What are applications of alphabetic trees?

texts:
Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as

  Alphabetic trees are Huffman trees with the additional constraint on
  order, or, equivalently, search trees with the modification that all
  elements are stored in the leaves. Faster algorithms exist for optimal
  alphabetic binary trees (OABTs).

From this, I understand that an alphabetic binary tree will produce shorter paths from root to element for elements that have been inserted into the tree more times than elements that haven't, and the alphabetic property would be described the same way for a ternary tree.

I haven't been able to find a lot of discussion about applications for the alphabetic property outside of Huffman coding but it is not a requirement to implement the algorithm.  Are there any applications where the alphabetic property would be a requirement, and if not, are there any benefits to guaranteeing the alphabetic property that justifies increased implementation complexity?


texts: Get the running time of forest disjoint sets

texts: If you have a forest implementation of disjoint sets, and have the union by weight/rank heuristic where you append the smaller one. Then why is the worst case running time Θ(m log n)? (m is the number of disjoint sets and n is the number of Make Set operations.)


texts: How to determine if a black-box is polynomial or exponential

texts:
I have a problem which essentially reduces to this:

You have a black-box function that accepts inputs of length $n$.
You can measure the amount of time the function takes to return the answer, but you can't see exactly how it was calculated.
You have to determine whether the time-complexity of this function is polynomial or exponential.

The way I did this was by running thousands of random sample inputs of varying lengths through the function, then plotting them on a scatter plot with times on the y-axis and input length on the x-axis.

What are some metrics and methods I can use to determine if these points best fit to a polynomial curve or to an exponential curve?

(Similar question asking how to draw polynomial/exponential best fit lines in Python on Stack Overflow: https://stackoverflow.com/questions/23026267/how-to-determine-if-a-black-box-is-polynomial-or-exponential)


texts: How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver?

texts:
As a homework we had to prove a set of upper bounds on a given probabilistic algorithm to find a satisfying assignment for a satisfiable 2-CNF formula. The problem is reproduced below. I'm sorry for all the incorrect language; English is not my native language and scientific language is especially difficult for me.

  Observe the following algorithm:

    input: A 2-CNF formula $F(x_1,\dots,x_n)$ with $n\ge1$ where each clause contains two literals.

    Choose an arbitrary assignment $a$ for $x_1,\dots,x_n$
    while $F(a)=0$ do
     select a clause $C$ from $F$ with $C(a)=0$
     select a literal $l$ from $C$
     flip the value of $l$ in $a$

    output: $a$

  Let $F$ be a 2-CNF formula in $n$ variables (let each clause have two literals without loss of generality) and let $h$ be an assignment that satisfies $F$. Show that the expected runtime of the aforementioned algorithm is bounded above by a polynomial.

  Hint: Show that the following bounds for the expected number of loop iterations $t(i)$, where $i$ is the number of variables in which the initial assignment $a$ differs from $h$, hold:

  $t(0)=0$ and $t(n)\le t(n-1)+1$,
  $t(i)\le1+\frac12t(i-1)+\frac12t(i+1)$ for $i=1,\dots,n-1$,
  $t(i)\le i(2n-i)$ for $i=0,\dots,n$.

It was easy for me to prove upper bounds (1) and (3), where (3) was proved using (1) and (2), but I wasn't able to prove (2). In fact, I believe that (2) might be incorrect.

The idea behind (2) is that when a clause $C$ is chosen in step 3, either one or both literals in $C$ are assigned incorrectly (i.e. not like in $h$) because if both were assigned like in $h$, $C(a)=1$ and $C$ would not have been chosen. Thus, the probability $P$ for increasing the number of correctly assigned literals is greater or equal to $0.5$.

Boundary (2) would work for a probability of exactly $0.5$, but I don't see how this follows. If $t(i)$ would be monotonous, this would be easy to see, but $t(i)$ might not be monotonous. For instance, construct a 2-CNF formula where $h$ and $\bar h$ (where $\bar h$ is $h$ with the value of all literals flipped) are the only satisfying assignments. Obviously, $t(0)=t(n)=0$ and $t(i)>0$ for all $i=1,\dots,n-1$.

Can anybody help me with this proof? I handed in the assignment last Thursday without a conclusive proof for (2), but it bothers me that I was unable to find a solution for (2).


texts: Baseline approaches for likes prediction

texts:
I have a small user-item matrix (25k x 1.8k) describing how users liked or disliked some of the items. Users don't have any attributes but items have several features.

I would like to be able to predict, using this dataset, some of the hidden likes and dislikes.

I don't have experience in the field and am not particularly sure, which approaches should I use as baselines and what should be the measures of effectiveness.

Any advice on the following topics is much appreciated:

1). Since I have a small data set, should I use content-based filtering instead of collaborative filtering? If so, what approaches would you try first? What measures of similarity between items can I use?

2). What approach should I use for collaborative filtering? Can I simply factorize the matrix and multiply the factors to get an estimate?

3). Should I use as a test and validation set a subset of rows (and predict the likes of unseen items) or a random subset of likes, different items for different users?

4). What would be a good measure of effectiveness? RMSE?

Thanks in advance!


texts: Finding rainbow cycle in digraph colored with $\log n$ colors

texts:
Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors.
Describe an algorithm determining if there exists a simple cycle in $G$ of length $k$ visiting exactly one vertex of each color.
Time complexity should be $O(n^3)$.

I couldn't think of any efficient solution.


texts: Nested Function stuck on iteration update

texts:
I want to solve the Sparse Extended Information Filter Slam described by Dr. Sebestian Thrun in Probabilistic Robotics.I stuck in some nested function.

The algorithm is described in page 309 in this book at Table 12.1

Algorithm is like that:

1.Algorithm SEIF_SLAM_known_correspondence($\xi_{t-1}$,$\Omega_{t-1}$,$\mu_{t-1}$,$u_t,z_t,c_t$):

It has four steps:

1.Motion Update

Measurement Update
Update state estimation
Sparsification

Motion Update:

Algorithm SEIF_motion_update($\xi_{t-1},\Omega_{t-1},\mu_{t-1},u_t$)

.......  Algorithm body.....

Return $\bar\xi_{t},\bar\Omega_t,\bar\mu_t$

Measurement Update

Algorithm SEIF_measurment_update($\bar\xi_{t},\bar\Omega_t,\bar\mu_t,z_t,c_t$)

Algorithm body.....

Return $\xi_t,\Omega_t$

Now as per algorithm in motion update of SEIF the return value is called in measurement update. I want to know when this type of situation occurred means one function return value is called by a other function Is that call is iterative? If the function body of motion update iterate in a loop then after execution of 1st iteration calling function (measurement update) call this or after full execution of motion update function then measurement update call it?


texts: What happens when there is a branch mispredict and an interrupt occurs?

texts: There is a branch mispredict and while executing the false code, an interrupt occurs (for example a keyboard interrupt). The EPC (register that holds the return address) now holds the wrong return address (after the interrupt handler has finished, it would return in code that wasn't even meant to be executed). How do CPUs deal with this problem?


texts:
Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$

This question looks weird to me because itself is a TM.  In general, when we say a problem is in NP, we can give an instance of that problem and using NTM to guess and verify. However, since $T_{NP}$ is a NTM, can we simply say using $T_{NP}$ itself to guess and verify in polynomial time?

Also, for the reduction part, I'm not sure but I think 3SAT is reducible to $T_{NP}$ because each clauses in 3SAT formula $\phi$ is true iff each step in $T_{NP}$ is valid.But I'm still stuck on the detail proof and argue the correctness at this moment. Any suggestion?


texts:
I have a big problem with converting GNF example.

This is my CFG

$
S \to AS\mid BS\mid \lambda\\
A \to aC\mid BCA\mid c\\
B \to AB\mid b\mid \lambda\\
C \to S\mid d
$

I simplified the CFG by removing redundant, $\lambda$-production, unit production.

$
S \to AS\mid BS\mid BA\mid CA\mid AB\mid BCA\mid aC\mid a\mid b\mid c\\
A \to BA\mid CA\mid BCA\mid aC\mid a\mid c\\
B \to AB\mid BA\mid CA\mid BCA\mid aC\mid a\mid b\mid c\\
C \to AS\mid BS\mid AB\mid BA\mid CA\mid BCA\mid aC\mid a\mid b\mid c\mid d\\
$

Then I removed left recursion for the first step to convert to GNF.
I made new non-terminals $N_1$ and $N_2$.

$
S \to AS\mid BS\mid BA\mid CA\mid AB\mid BCA\mid aC\mid a\mid b\mid c\\
A \to BA\mid CA\mid BCA\mid aC\mid a\mid c\\
B \to AB\mid CA\mid aC\mid a\mid b\mid c\mid ABN_1\mid CAN_1\mid aCN_1\mid aN_1\mid bN_1\mid cN_1\\
N_1 \to AN_1\mid CAN_1\mid A\mid CA\\
C \to AS\mid BS\mid AB\mid BA\mid BCA\mid aC\mid a\mid b\mid c\mid d\mid ASN_2\mid BSN_2\mid ABN_2\mid BAN_2\mid BCAN_2\mid aCN_2\mid aN_2\mid bN_2\mid cN_2\mid dN_2\\
N_2 \to AN_2\mid A\\
$

Then the problem came that I tried to remove front non-termials such as $B \to AB$, I substitude $A$ into $B$ but the result is $B \to BAB\mid CAB$ and so on, so it produces mored front non-termials.
I'm stuck in here for a long time. Can someone give me a hint to solve it?

In addition, I'm not sure but I thought it may need a CNF form so I converted to CNF.

$
S \to AS\mid BS\mid BA\mid CA\mid AB\mid BCA\mid X_aC\mid a\mid b\mid c\\
A \to BA\mid CA\mid YA\mid X_aC\mid a\mid c\\
B \to AB\mid BA\mid CA\mid YA\mid X_aC\mid a\mid b\mid c\\
C \to AS\mid BS\mid AB\mid BA\mid CA\mid YA\mid X_aC\mid a\mid b\mid c\mid d\\
X_a \to a\\
Y \to BC
$


texts: Random Teams based on Positions in Sports

texts:
I have tried to find an answer to this but haven't found exactly what I'm looking for.

I am trying to develop a way in which I can have a random team selected based on skill set (1-5 with 5 being the strongest skilled player) as well as by position (Forward of Defense) so that the algorithm can organize the players based on skills  and position.

I know I can easily do one to randomly assign based on one criteria, but whats the best way to add the second criteria at the same time?


texts: Can a language be context free and not have a BNF grammar?

texts:
Leslie Lamport claims that TLA+ is too complex to be described in BNF.
Does that mean TLA+ is not a context free language?
What is the relationship between the set of context free languages and the set of languages that can be described by BNF grammars?


texts:
Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$.

It looks like I need to find a very small growing function $g$ that will satisfy
$$\lim_{n\to{\infty}} \frac{1}{g} = 0 $$
and also
$$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{g}}} = 0 $$

My first attempt was $g(n) = \log n$
but according to wolfram alpha, the second limit was not satisfied,
I then tried $g(n) = \log\log n$ which according to wolfram does the trick.

But I'm not sure how to prove that
$$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{\log\log n}}} = 0 $$

Im looking for a way to prove this, or find a simpler solution than $f=n^{1/\log\log n}$.


texts: Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$, Show that $L\notin RE$

texts:
Let $ L = \{  \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$

Determine whether $ L\in RE, \space L\in R, \space L\in co-RE$, or none of the above.

I tried to show a reduction function from $L_{\Sigma^*}$ to $L$ to prove that $L\notin RE$ , here is my attempt:

$\forall M\in L_{\Sigma^*} : f(M) = M'$, where M' is a Turing machine which works as follows:

$\forall w\in \Sigma^*: $ if $w=\epsilon$ accept w; Otherwise run M on w and answer as M.

I manged to show that if $X \in L_{\Sigma^*}$ than $f(X)\in L$, but the other direction ($X \notin L_{\Sigma^*}$ than $f(X)\notin L$) seems to be more problematic and I'm not sure that reduction will even work.

I will appreciate any direction.

Btw, I'm new to reduction so please try to be patient and understanding.

Thanks!


texts: How to write a theorem corresponding to an algorithm's proof of correctness?

texts:
Let $X$ be an algorithm whose correctness supposed to be proved. What is the best practice to write the corresponding theorem?

For example:

Theorem: Algorithm $X$ correctly computes its output.


texts: Closed form solution for a single layer linear perceptron

texts:
Let f be a one-layer neural network which is linear (ie. no activation function). Let it have $p$ inputs and $q$ outputs. These are fully connected by weights $W$. We have $n$ inputs $x \in \mathbb{R}^d$ and $n$ outputs $y \in \mathbb{R}^{d'}$. We arrange these (column) vectors into matrices $Y$ and $X$, and the weights into a matrix, so that we can express the computation of the network on the whole dataset as $WX = Y$ (that is, if we could find the perfect $W$). Just to clarify, the network contains no hidden layer, just the input and output layers.

Training the network is a matter of choosing $W$ to minimize $e_W = \sum_{i=1}^n||y_i - Wx_i||^2$.

It seems to me that this problem should have a closed form solution that can be solved by a linear solver in some way. Unfortunately, my linear algebra is lacking. Is there a closed form solution? If not, where is the difficulty?


texts: maximizing absolute value in linear programming

texts:
I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I wish to solve the following optimization:

$max(ax_1)$
subject to
$x_1 = |x_2-x_3|$

where $a$ can be both positive and negative.

I tried to set up the a "Big-M" method based Binary LP (The bounds are well known and reasonably small.) by using the following constraints:

$x_1+(x_2-x_3)\leq M*p$

$x_1-(x_2-x_3)\leq M*(1-p)$

$x_1+(x_2-x_3)\geq -M*p$

$x_1-(x_2-x_3)\geq -M*(1-p)$

where p is binary.

The bounds are
$0 \leq x_1 \leq U$, where $U << M$; $-\infty \leq x_2 \leq \infty $; $-\infty \leq x_3 \leq \infty$

But this did not work. Is my above approach correct? Am I doing something wrong because of non-convexity and because of lack of closed-form solutions (as explained in Linear programming with absolute values)?

If yes, are there any alternatives? I am stuck!

This is the theoretical part.

In practice, I am having an issue with the following problem.
$max(x_1(1)+x_1(2)+x_1(3))$

such that

$x_1(1) = |x_2(2)-x_2(1))|$

$x_1(2) = |x_2(3)-x_2(2))|$

$x_1(3) = |x_2(4)-x_2(3))|$

the bounds are $0\leq x_1(1) \leq 4$, $0 \leq x_1(2) \leq 12$, $0\leq x_1(3) \leq 11$. for $x_2(1,...,4)$, the bounds are [-inf inf].

I expect the fval to be 27 so that I get x_1(1,...,3) = 4, 12, 11. but I get fval to be 4 and x_1(1,...,3) = 4, 0, 0.

I suppose I am making a big blooper somewhere, but I cant figure out where...!


texts: How to realize a distributed queue with unreliable participants?

texts:
I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol.

I found the distributed queue dual-bus algorithm, but I think it only works with reliable participants.

Is there an algorithm/protocol that can be used in this scenario?


texts: 'Stable' multi-dimensional scaling algorithm

texts:
I'm looking for a way to position nodes on a 2-dimensional plane in such a way that the distances between the nodes, which are entered exogenously, are represented visually in a way that as good as possible communicates the logical distance between those nodes. Basically, I have a set of nodes A, B, C etc. and between some of them I have a distance: A is 10 from B, 20 from C etc. Some nodes are not connected at all. The distances are not internally geometrically consistent: A may be 10 from B, and 10 from C, but B and C may be 100 from each other.

I want to do this in a way that is 'stable' - i.e. generates the exact same layout each time the algorithm is run. Multi-dimensional scaling algorithms seem to be the way to go about this, but I'm having a hard time finding practical properties of the various MDS algorithms that exist, and the one I've tried is based on iterating from a random start position and therefore doesn't generate the same result every time. It also cannot handle not-connected nodes, afaik.

The practical application for this, and more detail on what I've tried, is described in this question: https://stackoverflow.com/questions/20263829/stable-multi-dimensional-scaling-algorithm

(Original post:
I'm not sure what the etiquette is on this (repost question here or just link), but I asked a question on Stackoverflow that I was advised might fit better here. The question is here: https://stackoverflow.com/questions/20263829/stable-multi-dimensional-scaling-algorithm . I can repost here if that is the custom, but I thought I'd err on the side of fewest fragmentation and duplication. Thanks.)


texts: generating strings from this formal grammar

texts:
Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive grammar? Thank you.
$G=(\{S, L_x,R_x,W_x \},\{a,b\},P,S) \\
P = \{
\\S \to \lambda \mid L_x R_x, \\
L_x \to x \mid L_xyW_y, \\
W_xy \to yW_x, \\
W_xR_y \to R_yx, \\
R_x \to x  \\\} \\
x, y ∈ \{a,b \} \text{ this means that } x=y  \text{ but also  it can be  } x \neq y
$


texts: Origins of the term "distributed hash table"

texts:
I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came from. (I know it is not rocket science to just derive it from distributing a hash table, but somebody somewhere must have come up with it).

Most papers I read referred to the original paper on consistent hashing and one of the first algorithms making use of it (e.g Chord). I know that there was a lot of research on distributed databases in the 80s, so I figure that the term, or maybe the idea behind it, should be older than ~15 years.

The motivation behind this question is that knowing an earlier date and maybe another term for a similar idea would possibly widen the range of useful information I could gather for my research. For example, what have others done that is similar to what I want to do and where have they failed. Etc. etc.

I tried to find more on this subject using Structured Overlay Networks as a search keyword, but the resulting definitions/papers are also quite young, which leaves me with the impression that the research topic might not be so old after all.

Does anybody of you know of earlier research (maybe pre-90s?) in the topics of distributed hash tables and/or structured overlay networks? I'd be glad to hear some keywords which could lead me to more historic papers.


texts: If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the LinkedList now is not and advantage, so why you should use a LinkedList, and why is this a useful data structure?


texts: I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly this language and nothing else or it can recognize possibly some other words not in the language?


texts:
While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first

  $$L = \{1^n :n \in \mathbb{Z}\}$$

Where $\mathbb{Z}$ is a set of integers.

Question :I am not able to understand the string that belong to the given set will look like.

I know if input alphabet is $\{0,1\}^*$ then string 0101 (5 in decimal).


texts: Hoare's monitor - what happens after a "signal"

texts:
Assume I have producer and consumer in a monitor.

The code of the consumer signals the producer and then does something else.
I know in a Hoare-style monitor, after signaling, the thread that is signaled wakes up and is is now schedule.
What about the other instructions in the consumer after the signal? When will the consumer continue?
What if the consumer sends the signal before the producer does the wait?   Will the producer be stuck forever?
If there is a context switch will the mutex of the monitor be released?


texts: Why is this sequence of recurrence relevant?

texts:
I am learning how to solve the time complexity for the recurrence relation

$$
    T(n) = 2T(n - 1) + n^2\text{, where }T(1) = 1
$$

The solution notes that I should begin by considering the following sequence:

$$
    \text{Define }T^k(n) = T^{k - 1}(n + 1) - T^{k - 1}(n) \\
    \text{and let }T^{(0)}(n) = T(n)
$$

How is the sequence $T^k(n)$ relevant to solving my original recurrence relation? This just seems to be complicating the problem by defining an entirely new sequence.


texts: Why is word-addressable the exception, not the rule?

texts:
As stated on Wikipedia:

  Most modern computers are byte-addressable

instead of word-addressable. Why is this case? Since the CPU processes words (of predominantly 64 bits or 8 bytes) now, wouldn't the word-addressable approach be more efficient?


texts: Understanding how convolution of images work in cnn

texts:
I'd like to understand convolutional neural network.
Consider this quote from Stanford CS notes on Convolutional Neural Networks for Visual Recognition (CNNs/ConvNets):

  Example Architecture: Overview. We will go into more details below, but a simple ConvNet for CIFAR-10 classification could have the architecture [INPUT - CONV - RELU - POOL - FC]. In more detail:

  INPUT [32×32×3] will hold the raw pixel values of the image, in this case an image of width 32, height 32, and with three color channels R,G,B.
  CONV layer will compute the output of neurons that are connected to local regions in the input, each computing a dot product between their weights and a small region they are connected to in the input volume. This may result in volume such as [32×32×12] if we decided to use 12 filters.
  RELU layer will apply an elementwise activation function, such as the $\max(0,x)$ thresholding at zero. This leaves the size of the volume unchanged ([32×32×12]).
  POOL layer will perform a downsampling operation along the spatial dimensions (width, height), resulting in volume such as [16×16×12].
  FC (i.e. fully-connected) layer will compute the class scores, resulting in volume of size [1×1×10], where each of the 10 numbers correspond to a class score, such as among the 10 categories of CIFAR-10. As with ordinary Neural Networks and as the name implies, each neuron in this layer will be connected to all the numbers in the previous volume.

I don't understand why the result of applying convolution to the 32by32by3 input image is not of size 32 by 32 by 3 by 12?  From what I understand, we there are 12 filters and we apply each filter to each of the 3 channels of the image to get 3 new images for each filter.

Suppose the result of the first convolution is really 32 by 32 by 12, I don't understand how you get them.

Also, what happen when we do a second convolution? Say we do a second full convolution with 5 filters, then the result of the second convolution is 32 by 32 by 3 by 12 by 5?


texts: How is equation 1 simplified to equation 2 as shown below

texts:
In CLRS (Intro to algorithms) on page 362, it says eqn(1) :

can be simplified to this equation(2):

I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal proof but one that makes logical and intuitive sense. (General arguments or assumptions that lead to this simplification are also welcome). Any effort is much appreciated. (Thanks)
Update
I want to know how the second equation is valid if we are not considering the optimal revenues on both sides but only the optimal revenue of the right-hand piece as suggested by the second equation. I.e. in the second equation, we use the price of the left piece and then add it to the optimal revenue of the right-hand piece.


texts: Constructing regular expressions with given substring requirments

texts:
I'm having trouble with this question about regular expressions:

  Let $L_1$ be the language of passwords containing at least one
  lowercase letter, at least one uppercase letter, and at least one
  number. Write down a regular expression that describes $L_1$.

This is my answer, but I'm not too sure about it. I let $\mathcal{A}$ be the alphabet, and attempted to cover all permutations. I think my answer is correct, but is there a simpler way to go about it?
\begin{equation*}
 (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*) \cup
 (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*)\cup
 (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*)
\end{equation*}

I'm really stuck on this second part:

  Let $L_2$ be the language of "good" password. It is related to L1 by:
  \begin{equation*}  L_2=\{w\in L_1 : w \text{ has length } \geq 8\} \end{equation*} Specify a regular expression that describes $L_2$,
  without writing it down in full. What is the length of this regex?

I'm not sure about how to construct a regular expression using my answer for $L_1$. I thought it might be similar to the first part, where I could specify all the permutations.


texts: Is there an FPRAS for the number of min st cuts in general graphs?

texts:
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get a Fully Polynomial Randomized Approximation Scheme for it?

[1] Provan, J. Scott, and Michael O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12.4 (1983): 777-788.


texts: How can I solve this constrained assignment problem?

texts:
The assignment problem is defined as follows:

  There are a number of agents and a number of tasks. Any agent can be
  assigned to perform any task, incurring some cost that may vary
  depending on the agent-task assignment. It is required to perform all
  tasks by assigning exactly one task
  to each agent in such a way that the total cost of the assignment is
  minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

  Each task belongs to exactly one 'category'. Each 'category' has an
  associated maximum number of tasks that can be assigned. Enforce this
  constraint on the earlier definition.

For a layman's example, consider this -

  A restaurant serves n customers (agents), and has on it's menu m
  possible dishes (tasks), with m > n. Each customer gives his
  preference for each of the m dishes, which is the cost for this
  particular assignment problem. Find a solution which minimizes cost
  i.e. which gives each customer a dish that is as high on their
  preference as possible.

  Additionally, each dish belong to a certain cuisine (category). The
  restaurant can only make a certain number of dishes per cuisine.
  Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.


texts:
Its generally agreed that wait free queues have a consensus number of 2.
But what about this following code for a consensus protocol for a queue.
How is it that this does not go against the idea above?

(Im going to have a wild guess and say this code is not wait free?)

lets say we have a queue with 3 elements, and there are 3 threads. The top element about to be popped from the queue is 1, the rest of the values in the queue is -1

class ConsensusQueue()
   queue = new Queue()
   queue.enqueue(-1)
   queue.enqueue(1)
   queue.enqueue(1)
   atomic_reg = new AtomicRegister()

def decide(value):
    d = queue.dequeue()
    if d == -1:
       atomic_reg.set(value)
    return atomic_reg


texts: Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$

texts:
I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(\sqrt n)$ hold true?

I suspect $k$ would need to be a function of $n$. Because if it were a constant $C_1$, we could always find a larger constant $C_2$ that makes the previous statement false.

This is what I have tried.

$\log^k n \in \Omega(\sqrt n)$

$\log^{2k} n \in \Omega(n)$

$\log(\log^{2k}n) \in \Omega(\log n)$

$2k \log\log n \in \Omega(\log n)$

From here, I can see that if $k$ is $\log n$, then $2\log n \log\log n \in \Omega(\log n)$ is true.

However, I doubt this is a tight bound.


texts: When scheduling intervals across multiple resources, why sort?

texts:
I am reading this book and am at a point when the Interval Partitioning Problem is discussed. The pseudocode they provide for it is the following:

Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2, ..., I_n denote the intervals in this order
For j = 1, 2, 3, ..., n
    For each interval I_i that precedes I_j in sorted order and overlaps it
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

Here n is the number of intervals and d is the depth of the intervals (the maximum number of overlapping intervals)

What I don't understand is why sort the intervals in the first place. I think the algorithm would work even without this step. In other words, it would work no matter the order of I_1, I_2, ..., I_n. Am I correct? Is there something I am missing?

EDIT: Doesn't the algorithm below also produce an interval partitioning, but with the advantage of being faster because no sorting is performed?

Let I_1, I_2, ..., I_n be an arbitrary ordering of the intervals.
For j = 1, 2, ..., n
    For each interval I_i where 1 <= i < j which overlaps with I_j
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor


texts:
I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems.

How would one approach simplifying the following regular expression:

(01(11)* (10+0)+00+1)* 0(11)*

Thanks in advance,

Erik


texts: Algorithm for maximizing the number of same-sized groups

texts:
Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the goal is that you want to maximize the number of same-sized groups.
There can be multiple correct answers, and you can add to different groups (i.e. you can add 2 to one group, 3 to another, etc.)
Examples:
group sizes:[1,1,1], able to add 7 objects
Answer: 3, every group already has the same amount
[3,0,2,2,1], able to add 3 objects
Answer: 4, you can add 2 objs to the group with 0, and 1 obj to the last group that has 1.
So you maximize the 2's.
[5,4,1,3,4], able to add 2 objs
Answer: 3, you can either add 1 obj to the group with 3, creating 3 4's, or you can add 1 to each of the groups of 4, creating 3 5's.
I can easily solve this using brute-force (for each number 1...n, where n is the max amount able to be added, try all possible combinations of adding to current groups and adding the number of newly created ones to the original total) but I am confused as to where the algorithmic optimization is.  Have a nice day, thanks!
edit: put some example code of what I've tried.
#include <iostream>
#include <vector>
#include <map>

int maxCountOfEqualGroupSize(const std::vector<int>& groups, int objsToAdd) {

int maxGroupCount = 0;
std::map<int,int> groupSizeToGroupCount;
for (const auto& i : groups) {
  groupSizeToGroupCount[i]++;
}

//edge case - all groups already have the same size
auto iter = groupSizeToGroupCount.begin();
int firstVal = iter->second;
bool foundDiff = false;
for (; iter != groupSizeToGroupCount.end(); ++iter) {
  if (iter->second != firstVal) {
    foundDiff = true;
    break;
  }
}

if (!foundDiff) {
  return groups.size();
}
//end edge case

//find biggest value and get that key
//Then advance that key one by one to the right
//for each iteration: start at that key, and start moving left
//filling groups in, once you run out of objs to fill with,
//terminate.
int maxKey;
for (const auto& p : groupSizeToGroupCount) {
  if (p.second > maxGroupCount) {
    maxGroupCount = p.second;
    maxKey = p.first;
  }
}

auto startIter = groupSizeToGroupCount.find(maxKey);
auto lastIter = groupSizeToGroupCount.rbegin();
auto firstIter = groupSizeToGroupCount.begin();

for (; startIter->first != lastIter->first; ++startIter) {
  int objCounter = objsToAdd;
  int runningGroupCount = startIter->second;

  auto startPoint = --startIter;
  ++startIter;
  for(auto goingLeft = startPoint;
     objCounter >= 0;
     --goingLeft) {

    int diff = startIter->first - goingLeft->first;
    int groupsToFill = goingLeft->second;
    int amountToAdd = groupsToFill * diff;
    if (amountToAdd > objCounter) {
      //add up to what we can, since we can't fill all the groups
      while (objCounter >= diff) {
        ++runningGroupCount;
        objCounter -= diff;
      }
    } else {
      objCounter -= amountToAdd;
      runningGroupCount += groupsToFill;
    }

    if (goingLeft == firstIter) {
        break;
    }
  }
  maxGroupCount = std::max(maxGroupCount, runningGroupCount);
}
return maxGroupCount;
}

int main() {
  std::vector<int> ttt = {1,1,1};
  std::vector<int> tt = {3,0,2,2,1};
  std::vector<int> t = {5,4,1,3,4};
  std::cout << maxCountOfEqualGroupSize(t, 2) << std::endl;
  std::cout << maxCountOfEqualGroupSize(tt, 3) << std::endl;
  std::cout << maxCountOfEqualGroupSize(ttt, 2) << std::endl;

}


texts: Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

texts:
The detailed question is:

Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to proofe this question (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?


texts: Split in AVL tree with complexity $O(\log n)$

texts:
Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.

The split operation divides the AVL tree into two derived AVL trees, based on key. One of the derived trees should contain all the vertices in which all keys less than the original key, and the second the rest.

I know this can be done in $O(\log^2 n)$ time.  Here's a link to implementation with complexity $O(\log^2 n)$:
https://code.google.com/p/self-balancing-avl-tree/

I also know how to merge two AVL trees, such that the keys of one tree are all smaller than the keys of the other, in $O(\log n)$ time.
Here's an implementation with complexity $O(\log n)$:

def Merge(l, r) {
    if (!l || !r)
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}


texts: relation between $\forall$ and implication in intuitionistic logic using curry-howard and propositions as types

texts:
I am currently trying to wrap my head around intuitionistic logic and its interpretation using the curry-howard isomorphism and propositions as types.

I came about this explained relation between $\forall$ and $\rightarrow$:

  A function type $s \rightarrow t$ is actually a function type $\forall
 x:s.t$ where the variable x does not occur in t. [..] Moreover, if we
  have a type $\forall x:s.t$ where x does not occur in t, we can omit x
  and just write $s\rightarrow t$ without losing information.

I do not get how this can work as I understand a $\rightarrow$ basically as "give me a proof of s and I give you a proof of t" - a mapping function. However, a function that maps needs a parameter, in this case the x which is a proof of s : $f(x):s\rightarrow t$. How can I still have a mapping if I am 'not allowed' to use x and thus any information contained in it anymore?

If I use an example: e.g. proof that every $\mathbb{N}$ is $\mathbb{R}$ I need to use the information contained in the proof that a given number is in $\mathbb{N}$ to show that $\mathbb{N}$ is more restrictive than $\mathbb{R}$ and thus any $\mathbb{N}$ has to be $\mathbb{R}$. However, I do not have 'access' to those information as x (the proof that the number is in $\mathbb{N}$) does not occur in my proof that the number is also $\mathbb{R}$.


texts: largest bitwise-or subset with a maximum number of on bits?

texts:
Suppose I have the following set of bit sets:

 [1,]    0    1    1    1    0    1    0    1    0     0
 [2,]    1    0    1    1    0    0    0    1    0     1
 [3,]    0    0    1    0    1    1    0    1    1     0
 [4,]    1    0    1    0    0    0    0    1    1     1
 [5,]    0    1    0    1    0    1    0    1    1     0
 [6,]    0    1    1    1    1    0    0    1    0     0
 [7,]    1    1    0    0    0    1    1    0    0     1
 [8,]    1    1    0    1    1    1    0    0    0     0
 [9,]    0    1    1    0    1    1    0    0    0     1
[10,]    0    1    1    1    0    0    1    1    0     0

How would I go about finding the largest set such that the bitwise-or of that set does not exceed n bits in the "on" position.

For example, if I or rows 1 & 10...

 [1,]         0    1    1    1    0    1    0    1    0     0
[10,]         0    1    1    1    0    0    1    1    0     0
[1 or 10,]    0    1    1    1    0    1    1    1    0     0

This gives me 7 bits in the "on" position.

Now suppose my limit was 8 bits... how would I go about finding the largest set?

Edit:  I know how to do this as a mixed-integer-linear program, but I'm assuming there's a nifty graph approach.


texts: Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.


texts: How do I "tell" a simple perceptron/adaline neural netrork its output can't be negative?

texts:
I have made and trained a simple neural network which now seems to produce outputs reasonable  in all the aspects but one: it gives negative values from time to time even though the outputs are always either 0 or 1 (positive) in all my treaining samples (the actual neural outputs show to be more or less close to the answer most probable but never actually reach them, I consider this ok). Won't "telling" the network what output values are just impossible improve its performance.

Perhaps my mistake is in choosing activation functions. As far as my input values domain is (-1, 1) I use TANH for input neurons, but I have no idea what is the logic to choose hidden and output neurons activation functions and so I set the same (TANH) for all of them (update: I have just noticed that I have mistakenly chosen linear activation function for the output layer while inpit and hidden layers use TANH).

Clearly a negative value means "the answer is very probable to be zero" in this case and it works just fine from the practical point of view but it still gives me a sense that I am doing something wrong.


texts: How generate n equidistant points in a n-1 dimensional space

texts:
As said, i want to build a program to generate n equidistant points in an euclidian space.
From what i know

1d : all couple of points
2d : all equilateral triangles
3d : all equilateral tetrahedra
up to 3d : i suppose it's called an equilateral hypertriangle

So my problem is as follow, in a n-1 euclidian space, giving a defined point build the n-1 other in order to have an equilateral hypertriangle with a distant d between each points.

I suppose that we can start as follow with for example a 3d space.

p1 = (x1,y1,z1) fixed
p2 = (x2,y2,z2)
p3 = (x3,y3,z3)
p4 = (x4,y4,z4)
d

We start to fix p2 knowing d and p1

$d²=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2$

We have 3 variables x2,y2,z2.
We can fix randomly two of them and determine the third without problem.

Then for the second point we have now 2 equations to defined it :

$d²=(x_1-x_3)^2 + (y_1-y_3)^2 + (z_1-z_3)^2$
$d²=(x_2-x_3)^2 + (y_2-y_3)^2 + (z_2-z_3)^2$

As previous, i presume that we can fix 2 variables to determine the third.

For the last point we now have 3 equations which defined it.

So for a n-1 dimensional space we have n-1 equation to defined the last point.

I don't know how to solve this kind of system composed of quadratic equation with one variable and if the process which consist to fix n-1 dimension to determine the last one lead to an equidistant hypertriangle. Moreover it exist maybe others methods with an smaller complexity and easier to implement.

I hope i was clear enough and i thank you for your help.


texts: Applicability of Machine Learning on Images.

texts:
I am trying to use machine learning to detect and locate an object in a greyscale image. I have about 700 images which are 360x360 pixels in size.
See below for an example of the object and image:

In the first image, the object is indicated by the red arrow. In the second image, the object doesn't exist. Additionally, the object can occur anywhere along the X-axis (labelled theta) with a very slight bias towards the central pixels.

I tried to reduce the number of features by collapsing the image to a 1D array, like so:

array = numpy.sum(numpy.absolute(image), axis=0)

This ensures that I don't discard information that is crucial to my objectives (detecting and locating).

I now have a 1D array which is whiter at indices where the object is located and no noticeable brightness when the object is absent. So I created a training set of 500(samples) x 360(features) with 200 other samples reserved for cross-validation, and trained an SVM on it. The results on the cross-validation samples reported an accuracy of about 66%, and this doesn't seem to change with the number of training samples.

So I have 4 questions for the community:

Does the outlined problem have an acceptable solution in Machine Learning, or does it seem incredibly absurd to apply Machine Learning at all?
I can look for more images, or even synthesise new images from existing ones (by arbitrarily shifting the image left or right). Can I, however,  expect the results to get any better?
With the number of features that I have, what is the number of samples that I must typically have (as a very rough guess, given that you have seen what kind of images I'm dealing with).
The digit recognition problem in Machine learning houses an issue which is relevant to my case -- the algorithm performs poorly when the digits are written off-centre. In my case, the pattern that I am looking for in the 1D array (a bump) is independent of the location so that any one particular group of pixels shouldn't have disproportionate weights. What is one way to work around this limitation? (I'm thinking auto-correlation)

Thank you for your time and help!


texts: Find the minimal tank capacity to be able to travel from any city to any other

texts: There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $O(n^2\log n)$.


texts:
I am pretty new in λ calculus. And I am now trying to understand Alpha equivalence. Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one? Here is one example:
 (λx.(λx.x(λy.x)x)x)x

And by applying alpha equivalnce I can rewrite it to:
  (λw.(λz.w(λy.z)z)w)x

Is my understanding correct ?


texts: Algorithm: turining a fraction into a decimal expansion string

texts:
I already asked this question over on Mathematics and got the suggestion to ask it here.

So I'm basically implementing a number type that can represent all fractions and was working on an algorithm to compute the decimal expansion for said fractions.

Let's say we have the reduced fraction $\frac{n}{m}$. For converting it into its decimal expansion I now have two algorithms.

The first algorithm is simply long division to calculate the decimal expansion up to a given number of decimal places.

The second is:

Let $a \in \{1,2,\ldots\}$ be a specifier for accuracy.

Calculate:
$$
\begin{align}
p &= \lceil \log_{10}(m) \rceil + a \\\\
f &= \lfloor \frac{10^p}{m} \rfloor \\\\
v &= n \cdot f
\end{align}
$$
Then in $v$ insert the decimal comma at the correct place or add 0. with leading zeros.

Which works well but it is hard to control the accuracy with $a$.
For example if I have the fraction $\dfrac{884279719003555}{281474976710656} \approx \pi$ then I get:

 a | dec. exp.
---|--------------------------------
     v acc 0
 1 | 3.0949790165124425
       v acc 1
 2 | 3.13919300246262025
        v acc 1
 3 | 3.14096156190062736
             v acc 7
 8 | 3.14159264580768862709685
              v acc 8
 9 | 3.14159265288192637912529
                  v acc 12
10 | 3.141592653589350154328134
                  v acc 12
11 | 3.141592653589350154328134
                  v acc 12
12 | 3.141592653589350154328134
                     v acc 15
f  = 3.1415926535897931159979634...

pi = 3.1415926535897932384626433...

So its seems I can control with $a$ that at least $a-1$ decimal places are correct.

But I'm not sure if this will always be the case.

Also, I benchmarked both algorithms, and the second is more than 5 times faster. So I really want it to be controllable.

| Method |       Mean |    Error |   StdDev |
|--------|-----------:|---------:|---------:|
|  first | 4,929.2 ns | 24.34 ns | 20.33 ns |
| second |   848.8 ns |  4.00 ns |  3.54 ns |

So my question basically is: does anybody have suggestions on improving the algorithm or maybe another algorithm that does the job even better (a.i. fast)?


texts:
Is there an algorithm to decide whether a closed-form expression over integer variables using, say, $\{+,-,\times,\div,\text{^},\lfloor\text{lg}\rfloor,!,()\}$, or some other useful set of operators, is everywhere zero?

For example, is $(jk)^2 +k!-2j$ always 0 when $j,k$ are integers (obviously not)? If some of the operators make it impossible, is it possible with just a subset, for example if one removes factorial?


texts: What is an oracle separating IP and PSPACE?

texts:
I saw this link on cstheory:

https://cstheory.stackexchange.com/questions/6634/is-there-an-oracle-that-separates-two-complexity-classes-known-to-be-equal

but it did not provide specific details.  Can anyone tell me what the specific oracle is (or direct me to a paper which does)?  Also on a meta-level why does this not call into question the legitimacy of oracle Turing machines- if two classes coincide, how can they be separated?  Thanks.


texts: How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

texts:
I am reading a proof that the Subset Sum decision problem is NP-complete.
I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$.
Also, for this specific problem the size/length of the input is $(n+1)\log{W}$, with $n$ and $W$ being two integer variables ($n$ is the number of available elements in the set and $W$ is the sum we are seeking).
However I am having some trouble when trying to understand the terminology be linear/polynomial in the input size, specifically with these two lines:

The input length is (n + 1) log W, and the running time of O(nW) is
not polynomial in this input length.

and

takes O(n log W) time, linear in the input size.

How can I mathematically prove the above two lines? Or what is the mathematical reasoning behind those two statements?
I don't have this conceptual problem when there is only one variable. For example, let's say I have an algorithm with a complexity of $O(x)$ and an input size of $\log_2{x}$. Then, I can express $x$ in terms of the problem size like this: $O(2^{size})$. Now, I can see that the complexity is exponential in the size (in bits) of the problem.
But I don't know how to do this when there are two or more variables in the complexity function (in this case $W$ and $n$).


texts: Finding all solutions to an integer linear programming (ILP) problem

texts:
My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this problem near the end, but I'm interested in knowing if there is a proper and efficient algorithm or method for solving this kind of problem.

There is no objective function, but the constraints for this ILP are

$$
\begin{equation}
0 \leq -2x -y \leq 8 \\
0 \leq 1-x+3y \leq 5 \\
0 \leq 2+x-y \leq 2 \\
x,y \in \mathbb{Z}
\end{equation}
$$

Since this ILP has two variables, I can visually inspect the solution region by graphing the lines formed by the constraints, which are

$$
\begin{align}
y &\leq -2x \\
y &\geq -2x-8 \\
y &\geq \frac{1}{3}x - \frac{1}{3} \\
y &\leq \frac{1}{3}x + \frac{4}{3} \\
y &\leq x + 2 \\
y &\geq x
\end{align}
$$

By inspection, there are 6 integer solutions for $(x, y)$: $\{ (0,0), (-1,1), (-1,0), (-2,0), (-2,-1), (-3,-1) \}$.

However, my current method is to use linear programming with non-negativity relaxed and integers from branch-and-cut. I've tried using a set of four objective functions: minimize $x$, maximize $x$, minimize $y$, and maximize $y$. These give a smaller search area as

$$
\begin{equation}
-3 \leq x \leq 0 \\
-1 \leq y \leq 1
\end{equation}
$$

I then iterate over all valid integer tuples in that smaller area and filter it for tuples that satisfy the original constraints. The tuples that remain are all valid integer solutions.


texts: What is the growth rate of a complexity $O{n\choose n/4}$

texts:
I found an algorithm that enumerates k-subsets of length n/4 for a input set of n length, having a time complexity $O{n\choose n/4}$, the algorithm fits well a problem I'm looking to solve, but I'd like to double check if I understood well its time complexity.

I plotted it for different increasing N and looks exponential (but not as bad as $2^n$ exponential)

As I don't want to do curve fitting... it is possible to simplify that expression in a way that makes possible to get a better sense of what will be its growth?


texts: Closure properties of undecidable languages

texts:
I know that the decidable are close under: complementation, union, intersection and concatenation?

What about the undecidable languages? I think they are close under complementation, but not under concatenation, union and intersection. But I don't know how to prove it...

My prove

  "Lets say L is undecidable lang. Because L is undecidable lang we know
   one of the following:

  there is a word w1 from L that there is no TM that stop for this
   word
  there is a word w2 in L that stopping in reject state in every TM
  there is a word w3 Not from L that stopping in accept state in
   every TM

  L' is the complementation lang of L

  If 2, the word w2 that stopping in reject state, will stop in the
  accept state for every TM, but w2 not in L' so L' is Undecidable.

  If 3, the word w3 that stopping in accept state, will stop in the
  reject state for every TM, but w2 is in L' so L' is Undecidable.

  If 1, so all the TM are not stopping for w1 so L' is Undecidable???? "


texts: How to design Hash Functions for the problem of Set Intersection?

texts:
This is a specific question about [1].

Before the question, I must explain and organize some topics:

1) In section 3.2, during the "Pre-processing Stage", a hash function maps an element to a bit-string.

2) In the Appendix B, the authors explain the COMPRESSION stage of those bit strings.

Question:

Is it possible to design a specific hash function to make the Compression stage more efficient?

[1] Fast Set Intersection in Memory

http://arxiv.org/abs/1103.2409


texts:
There seems to be a sense of competition in creating the fastest computer in the world, and I feel like technically you just have to continue increasing the core number to gain more flops, which is exactly what some countries are doing, so how would you really bench mark the technological level of a supercomputer

for example

United States currently have two supercomputer on the top list with similar performance, however one has significantly less core than the other

Titan     has 560000 cores    17590 Rmax Tflops   with   8000 kW of power

Sequoia   has 1570000 cores   17173 Rmax Tflops   with   7800 kW of power

Does this mean that Titan is a much superior supercomputer than Sequoia as it only uses 1/3 of cores to reach a similar performance, and if it does, this will also imply that judging supercomputer by flops is completely meaningless?

Is there something I am missing here? Such as the increasing complexity of software as the amount of core gets larger and the synchronization of overhead to assign task to each core gets more sophisticated?

Any info would be much appreciated


texts: Largest N squares that fit in a rectangle

texts:
I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:

Problem: Given N equal-sized squares and a rectangle with width W and height H, find out the maximum size of the squares L such that the squares fit inside the rectangle in such a way that their sides are orthogonal to the rectangle sides.

So far, I think we have a O(sqrt(N)) solution, in which we assume W>H, start by trying to place all squares in a single row, then in two rows and so on, until we get to O(sqrt(N)). For formally, let nRows be a variable from 1 to sqrt(N), nCols = ceil(N/nRows) and then do L = min(H/nRows, W/nCols).

I'm not completely sure the idea above is optimal. I was also wondering if we can solve this problem in O(1)?

I've tried looking for orthogonal square packing, but the problem seems a bit different (or could we easily reduce on to another?)


texts: A more rigorous proof on a Bellman-Ford's corollary

texts:
The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"

Corollary 24.3
Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$
and a weight function $w: E \to \mathbb{R}$. Then, for each vertex $v
> \in V$, there is a path from $s$ to $v$ if and only if BELLMAN-FORD
terminates with $v.d < \infty$ when it is run on $G$.

I have an intuition for the corollary and would formulate its proof as following:
$\rightarrow$: Suppose there are paths from $s$ to $v$, we call the shortest path $p$. The path $p$ is shortest and therefore simple and hence has at most $|V| - 1$ edges. Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can concluse, that $v.d < \infty$ after the algorithm terminates.
Another argument may also include the "Path-relaxation property", which states $v.d = \delta(s, v) < \infty$ after relaxations of all edges of $p$.
$\leftarrow$: Suppose there is no path from $s$ to $v$ but Bellman-Ford terminates with $v.d < \infty$. This would be a contradiction with "No-path property", which states $v.d = \delta(s, v) = \infty$.
I am self-studying the book and there is a lack of feedbacks from tutor, so my question is: would my proof be sufficient in this case?


texts: Substituting "remaining variables" during partial evaluation?

texts:
In "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler" Yoshihiko Futamura wrote:

  "[Some] portions of a computation process [...] are not evaluated at
  partial evaluation time, but the values are only substituted for the
  remaining variables."

on page 388 in the paper
(I considerably shortened the quote and I think that in order to answer my question you have to be familiar with the topic or read the paper anyway.)

Note that Futamura uses the term "remaining variables" to describe variables other than "partial evaluation variables", whose values are known - or can be calculated from other variables and constants - at partial evaluation time.

Now, the sentence would make perfect sense to me if the last occurence of "remaining variables" was replaced with "partial evaluation variables". After all, we can easily replace those with the values we know. But how should we be able to fill in the values for "remaining variables" when (of all things) they are the ones we don't know the values for (yet, i.e. at partial evaluation time)?

Could it be an error?
Do I read the sentence wrong?


texts: What is my error in reasoning about the complexity class $n^{o(1)}$

texts:
I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

Certainly the limit of $n^{1/n}$  is 1.

But it can't mean that, because the next question (and yes, this is homework) is to find a function in $n^{o(1)}$ such that its limit is infinity.

So clearly I'm making an error in my reasoning. What am I doing wrong?


texts: Is there a clear definition of "computable" for models of computation which are not turing complete?

texts:
This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", but according to some papers I read, the definition is also not really clear when it comes to models of computation weaker than turing machines because of the encoding of the input and output.

The typical definition of turing computable is as follows:

  Definition 1: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called turing computable iff there is a turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as strings.

The definitions differ in what exactly is a suitable encoding is, but most refer to binary encoding, unary encoding or decimal encoding as the one fixed and suitable encoding. It is also possible to show that fixing one encoding is required for the definition of turing computability. But what makes, say, binary encoding of natural numbers special so that we can axiomatize it as the one suitable encoding? Probably because it fits the intuitive notion of what computability means coincidentally.

Now what if we look at weaker models of computation than turing machines? For example, let's consider the set $M_c$ of "crippled" turing machines with the alphabet $\{0,1\}$ which may only move to the right, and a definition of crippled turing computable which is consistent with that of turing computability:

  Definition 2: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called crippled turing computable or computable in $M_c$ iff there is a crippled turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as a string.

If we define "suitable encoding" as "binary encoding", then the function $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$ is not computable in $M_c$. If we axiomatize "suitable encoding" as "unary encoding", then $f$ is computable in $M_c$. This seems awkward given the fact that everyone may fix one of the infinitely many intuitive encodings at will. It should be clear if a computation model can compute $f$ or not without referring to some specific encoding - at least I have never seen anyone mention what encoding is used when stating "loop programs are weaker than turing machines".

After this introduction I can finally phrase my question: How would one define "suitable encodings" and "computability" for arbitrary models of computation which do not coincide with the intuitive notion of computability? Is this possible within the framework of turing computability?

Edit: I shortened the introduction, it didn't add to the question.


texts: Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant

texts:
So i came upon this question where:

we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way:

first we convert the base of these numbers to $n$ in $\mathcal{O}(n)$, therefore now we have numbers with maximum 3 digits.

now we use radix sort and therefore the time is $\mathcal{O}(n)$

so i have three questions :

is this correct? and the best time possible?
how is it possible to convert the base of n numbers in $\mathcal{O}(n)$? like $\mathcal{O}(1)$ for each number? because some previous topics in this website said its $\mathcal{O}(M(n) \log(n))$?
and if this is true, then it means we can sort any $n$ numbers from $0$ to $n^m$ in $\mathcal{O}(n)$?


texts: Is there any algorithm can solve the following equations efficiently?

texts:
$$ x_1 + x_2 + \cdots +x_n = c_1 $$
$$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$
$$ \cdots $$
$$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$

$c_1,\cdots,c_n$ are known constants. $x_1 \cdots x_n$ are the unknown variables to solve.


texts: Efficient algorithm for simple constraint satisfaction problem

texts:
There are

$k$ Boolean variables $x_1, x_2, \dots, x_k$.
$m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., one of $m$ constraints may be $x_1 + x_3 + x_5 + x_6 = 1$.
$n$ arbitrary subsets of these variables such that sum of each set is at least $1$ (i.e., at least one of the variables should be $1$). E.g., one of $n$ constraints may be $x_1 + x_6 + x_8 \geq 1$.

The solutions are not necessary, but I want to know how many solutions exist.

What is an efficient way to calculate the number of solutions?