texts: How is a nondeterminisitic automaton running on an input?

texts:
A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states.

Does the automaton uniformly randomly choose one out of the several states?

So different runs on the same input will give different sequence of states?

Does the automaton have to run in all the possible sequences of states on a given input? Or just one random run?


texts: How to sort a stack using bubble sort? Can use another stack if necessary.


texts: Using "incremental algorithms" to find the $k^{th}$ smallest number

texts:
This is what I vaguely understand of what an "incremental algorithm"  is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the algorithm has seen the elements $x_1, x_2, x_3, ... , x_{i-1}$ it has either,

(1) computed the $k^{th}$ smallest element till then or

(2) it has computed a some other invariant from which the $k^{th}$ smallest element can be computed and this invariant is updated when it sees $x_i$.

How is this different from a "greedy algorithm" ?
Can someone explain actual algorithm for this and what is its worst case and or expected running time?
Further it seems that if the algorithm randomly permutes the given sequence then the expected running time can be upper bounded by $n + O(k \log(n/k))$. Can someone explain what this is?

What does it technically mean to choose a permutation randomly and how is this actually implemented?


texts:
I'm looking for an algorithm that will group players from the same teams together throughout multiple matches.
In my case, every team has up to 4 players in every match.
Teams have subs, which means that it is not necessary that the same players will play in all the matches.
Each team has randomly assigned ID in form of UUID for each match, which means that the same team will not have the same ID throughout the matches.
My goal is to group row by team IDs and then group those groups by players that play in a team.
For this project, I'm using python with pandas library so if you don't know the name of such an algorithm any tips about how one might implement something like this with pandas will be much appreciated as well.
EDIT:
To be more specific I'm looking for such an algorithm (the name if exists). Also, adding the input and desired output of the algorithm for better understanding.
INPUT:
player_name    team_id   att1   attr2   ....
--------------------------------------------
A              1         1      2
B              1         3      5
C              1         9      7
D              1         1      2
E              2         3      5
F              2         9      7
G              2         1      2
H              2         3      5
I              3         9      7
J              3         1      2
K              3         3      5
L              3         9      7
M              4         3      5
N              4         9      7
O              4         3      5
P              4         9      7     <----- last entry for match 1
A              5         1      2
B              5         3      5
C              5         9      7
R              5         1      2     <----- sub
E              6         3      5
F              6         9      7
G              6         1      2
H              6         3      5
I              7         9      7
J              7         1      2
K              7         3      5
Q              7         9      7     <----- sub
Z              8         3      5     <----- sub
N              8         9      7
O              8         3      5
P              8         9      7     <----- last entry for match 2

OUTPUT:
Team 1
player_name    team_id   att1   attr2   ....
--------------------------------------------
E              2         3      5
F              2         9      7
G              2         1      2
H              2         3      5
A              5         1      2
B              5         3      5
C              5         9      7
R              5         1      2
--------------------------------------------

Team 2
player_name    team_id   att1   attr2   ....
--------------------------------------------
A              1         1      2
B              1         3      5
C              1         9      7
D              1         1      2
E              6         3      5
F              6         9      7
G              6         1      2
H              6         3      5
--------------------------------------------

Team 3
player_name    team_id   att1   attr2   ....
--------------------------------------------
I              3         9      7
J              3         1      2
K              3         3      5
L              3         9      7
I              7         9      7
J              7         1      2
K              7         3      5
Q              7         9      7
--------------------------------------------

Team 4
player_name    team_id   att1   attr2   ....
--------------------------------------------
M              4         3      5
N              4         9      7
O              4         3      5
P              4         9      7
Z              8         3      5
N              8         9      7
O              8         3      5
P              8         9      7
--------------------------------------------
```


texts: I'ld like a better algorithm for scheduling tutors to fill a set of shifts

texts:
My problem is as follows:
I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm.
Locations can have a priority.
Skills can have a priority.
Tutors have a set of times when they are available.
Tutors set a minimum and maximum number of hours they want to work for.
Tutors can choose the longest consecutive duration they want to work for.
A tutor's shift should be for at least an hour.
A tutor's shift is preferred to be around 2 hours but filling the schedule is more important than having a shift be an exact number of hours.
Having as many tutors work as possible is preferred to having fewer tutors work more hours.
A tutor can be required to fill a particular shift.
For any shift, prefer assigning a tutor with fewer skills so that shifts that require more advanced skills can be assigned to shifts that need them.
Scheduling needs to keep track of unassigned periods in a shift.
Shifts, skills, and tutors each number at about 100-200.
My approach has been to break the shifts into 2 hour chunks, sort them according to the various priorities, and use a scanline algorithm to schedule tutors for shifts. For each shift chunk, I sort the tutors' availability list by priority, assign the tutor and mark the shift duration used in the availability and shift lists. When this is done, I re-run the scheduling algorithm on unfilled shifts that have irregular hours.
In looking for alternatives, I've glanced at particle swarm optimization, network flow, linear programming, and the assignment problem. I've also wondered if a knapsack or priority queue might work, but I'm not sure how to handle the multiple (sometimes conflicting) priorities.
I'm wondering which algorithms would be more efficient for scheduling without being overly complicated to implement. I feel the current solution has become overly complicated and is beginning to become slow at the current problem size.


texts: Sort complexity expressed via distinct number of elements

texts:
I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified:

Sort A, search each element of B in A and retain it if it appears in A.

It is claimed that if a, b are number of elements in A and B, and $\alpha, \beta$ are the number of distinct elements in A, B then the complexity of this algorithm is $O(a\log\alpha + b\log\alpha)$. My question is, why the sorting of A is only dependent on the number of distinct elements? Is there some kind of algorithm I am not aware of? If so, why the same algorithm could not be used for the second strategy? The second strategy is:

Sort A and B, use merge-like operation to discard duplicates.

For this algorithm the complexity is $O(a\log a + b\log b + a + b)$ which makes sense to me.


texts: Compute the union of two sets between two endpoints minimizing communication complexity

texts:
I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \{a_1, \ldots, a_{N_A}\}$, and $b$ is storing another set of fixed-length strings $B = \{b_1, \ldots, b_{N_B}\}$, with in general $A \cap B \neq \emptyset$.

Now, I would like to run a procedure that, using the communication channel between $a$ and $b$, results in both $a$ and $b$ storing $A \cup B$.

Both $a$ and $b$ can run an arbitrary amount of precomputation (e.g., sorting their sets, indexing them, organizing their elements in a tree...) but I would like the procedure to be as efficient as possible in terms of communication complexity.

The case I am most interested in is the one where $N_A \simeq N_B \simeq N$ with $N$ large and $|(A \setminus B) \cup (B \setminus A)| \ll N$. In that case, it seems to me like having the endpoints send their whole sets to each other should be an highly inefficient solution.


texts:
There is a river which can be considered as an infinitely long straight line with width W.

There are A piles on the river, and B types of wooden disks are available.
The location of the $i$-th pile is $(X_i, Y_i)$.

The $i$-th type of wooden disks has radius $R_i$, and its price is $C_i$ per disk.

Disks can be placed on the river such that for each wooden disk, its center must be one of the locations $(X_i, Y_i)$ of piles. We can only move on the wooden disks.

How to find the minimum cost such that we can cross the river.I am unable to approach questions like these. What would be the best method to approach this one?

I have come to realize that we can use Dijkstra's algorithm here. We treat this as a graph, with piles as the nodes. Start point can be $y=0$. and $y=W$ as the end point. But i am having implementation problems. There are multiple disks which can be used in going from on state to another. How to handle this?


texts: Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$

texts:
$L_1^*∪L_2^*⊆(L_1∪L_2)^*$

I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of words in the right group $[(L_1∪L_2)^*]$ obviously contain all the words from the left group $[L_1^*∪L_2^*]$ and it's also very plain to see, but I have no idea how to formalize it.

Any idea how to formally prove it?
Thanks.


texts: Alternative to CELL+ATOM as "the ultimate data representation form"

texts:
The construct of a cell (an ordered pair with pointers to either another cell or an atom) and atom (an indivisible sequence (of bits) (i.e. a natural number)) is a fundamental data structure for many programming languages. It's also quite a versatile one, with which you can build arbitrary structures - lists, trees (lists of lists), any graphs.
Is there any alternative to that? I.e. another means to represent arbitrarily structured data?
And are there any particular advantages of this cons+atom method? Because in any ways, the structure makes only sense when you start interpreting that data.


texts: The NP completeness proof for a variation of the 3CNF-SAT problem

texts:
There is a variation of 3CNF-SAT which is called 10-3-CNF-SAT = {<$\Phi$>: $\Phi$ is a satisfiable CNF formula with $\textbf{at most}$ 3 literals per clause and every variable occurs in $\textbf{at most}$ 7 different clauses}. We need to prove that 10-3-CNF-SAT is NP-complete.

My idea is that we can reduce from 3CNF-SAT to 10-3-CNF-SAT. Because 3CNF-SAT is NP-complete, we can get 10-3-CNF-SAT as well. However, I am stuck in the process of proving the mapping reducible relationship between the 3SNF-SAT and 10-3-CNF-SAT.

Does anyone know how to do the reduction part?
Thanks in advance.


texts: Overlap between computer science and analytic geometry?

texts:
I would like to know if there are some topics that could be covered in an undergraduate first-term course about analytic geometry, but related to Computer Science.

I know that, for example, the simple equation for the line can be used for explaining linear regression or other topics in elliptic cryptography (too advanced for an initial course).

Any suggestion of topics?


texts: Buffering packets vs. low latency routing

texts:
I am considering strategies to compare the performance of routers with buffers vs. their lower latency counterparts in a simple network setting (N clients communicating with each other randomly through a router). I know that buffered routers should ideally perform better when there are traffic bursts.

My question is regarding my concern which is that I do not know what is a good strategy to pick scenarios and how could I convey that these models are relevant to common real world situations. So the question would be:

How to pick scenarios that are similar to real world situations?
How to convince that these scenarios are indeed relevant to real
world situations.

My main concern is measuring the benefit of buffers vs. an improvement in RRT (lower latency) with varying levels of congestion. Also showing possible disadvantages where the amounts of congestion are overwhelming (buffer bloat) and possibly other patterns.


texts: Bloom filters vs storing hashes as numbers

texts: In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers). This data structure has the same properties as a Bloom filter. You never have false negatives but you can have false positives. Since adding and removal are constant operation I was wondering what advantages do  Bloom filters have over this method and which was is more memory efficient. If there is some formal analysis of both methods Id like to see it :)


texts: What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?

texts:
Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands from me. This vessel has to reach, say, the island of Hainan at the earliest possible moment.

What are the deterministic algorithms for finding a maritime route on a globe?
What is their time and memory complexity?
Can I, for instance, use A* after transforming the map of the globe into a diagram with connected polygons (i.e. Delaunay triangulation on a sphere/ellipsoid) and what are other feasible approaches?

Answers should ideally provide references to papers with discussion of the above-mentioned questions.

As pointed out by Rob Lang, the algorithms must fit the usual criteria: in the absence of time constraints, lead to the shortest path between any two points on Earth's oceans and seas, or indicate pathfinding failure otherwise.

There are interesting sub-topics here (trading pre-computation time/storage for online computations, providing slightly suboptimal routes before a deadline kicks in etc.), but these are ancillary to the main issue.


texts: What does it mean when a computer runs 'faster'?

texts:
If you have two computers with only one thread, a and b.

And computer a runs twice as fast as computer b.

Does this mean that computer a and can do twice as many operations in a given time in comparison to computer b?

To increase the Hertz of a computer, i.e. the speed of the computer and the number of operations it can achieve with in a given time frame, what has to change in the architecture?


texts: Am I doing this correctly? Recurrence Relations

texts:
The function is this:

function max-element
if n = 1
    return A[1]
else
    x = max-element(A[2...n])
    if A[1] > x
        return A[1]
    else
        return x

So to create to recurrence relation i've done this, which i'm unsure of...

T(1) = 2, because the function will only execute the first if and return if n=1

T(n) = T(n-1) + c, and c = 5 when n>1

T(n-1) = T(n-2) + c

T(n-2) = T(n-3) + c

generalized, T(n) = T(n-k) + 5k ... this is where I think i'm going off?

And in the worst-case, k=n-1.....  T(n)=T(1)+5n-5=5n-3

Then T(n) = Theta(n).

Any help?


texts:
I often hear Prefetching as a technique for speeding up, for example, sequential memory access pattern.  The prefetch should occur sufficiently far ahead in time to mitigate the latency of memory access, for example in a loop traversing memory linearly.

According to the famous "What Every Programmer Should Know About Memory" paper by Ulrich Drepper, it is written:

  This prefetching would remove some
  of the costs of accessing main memory since it happens
  asynchronously with respect to the execution of the program

(emphasis mine)

I could not find references on Google or Wikipedia corroborating or proving this. Does anyone know where I can find if this is true?

The only reasoning I can think of is rhetorical: it must be asynchronous b/c otherwise prefetching offers no benefit to sequential access... unless the execution time of prefetching a cache line is less than bypassing prefetch and placing the same cache line from RAM directly into cache.


texts: When problem A reduces to problem B, which problem is more complex?

texts: When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?


texts: Recover the path to a goal state in A* search algorithm

texts: In the A* search algorithm, we use a priority queue with heuristic function to find optimum result with minimum cost. But, how do we get the path after reaching goal?


texts: Can there be 'dead states' in a context-free grammar?

texts:
Can a context-free grammar include "dead states" from an automaton, such as

$$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$

The production rules $B\to C$ and $C\to cC$ will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at some point?


texts: Question about the definition of complexity class oracles

texts:
If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$.  That's what they told me in my Theory of Computation class, anyways.

Per this definition, it seems to me that $P^P$ captures every decidable language.  Here's why I think that:

Let $M$ be a TM that always halts.  On input $x$, construct a new machine $M'$ that: (1) checks to see if the input is equal to $x$, (2) if its input is $x$ then it simulates $M$ on $x$, (3) if its input is not $x$ then it instantly rejects.

This new machine $M'$ runs in $O(n)$ time, so in the class $P^P$, we have an oracle to it.  We can now consult this oracle to find out if $M'$ accepts $x$, and we learn in only $O(n)$ time whether or not $M$ accepts $x$.  So we have an algorithm that decides $M$ and runs in $TIME(O(n))$, given an oracle to some countable set of problems in $TIME(O(n))$ (e.g. every $M'$, constructed with respect to every possible finite bitstring $x$).

What am I misunderstanding?

Here is an attempt to clarify my confusion.

This is the model that I think we are using:

There are three tapes usable by the Oracle Turing Machine: a standard worktape, an "oracle input tape," and an "oracle machine tape."  The OTM can enter a special state where it takes the machine description written on the oracle machine tape, performs a magical 1-step simulation of that machine on input equal to the contents of the oracle input tape, and then writes down a $1$ or a $0$ on the worktape according to the results of the simulation.

Define: A language $L$ is in $P^P$ if there is an OTM that decides L and always halts in $p(n)$ steps on length $n$ input (for some polynomial $p$), and also for every Turing machine description $M$ used by the OTM, there exists a polynomial $q$ such that $M$ halts in $q(n)$ steps on input $M$.

Then my argument is valid, I think: every machine that we write down runs in linear time overall (even though the constant associated with that machine will grow very quickly for increasingly-long inputs).

This wouldn't be a problem if we flipped the quantifiers (i.e. "there exists a polynomial $q(n)$ such that every machine description $M$ used by the OTM halts in $q(n)$ steps).  But I'm not sure that still describes $P^P$...


texts: Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

texts:
Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?

It certainly isn't regular, but is it context free?

I'm having trouble creating a grammar that creates terminal symbols from the outside-in; Is there anything to look for explicitly that tells me it is/isn't CF?

And if it was in fact context-free, how would I go about proving that?


texts: What is the big-o of the function 2 log(log n) + 3 n log(n) + 5 log(n)?

texts:
What is the big-O of the function $2\log(\log(n)) + 3n\log(n) + 5\log(n)$?
Is it just $O(n\log(n))$ for the whole function? I'm not sure how to represent $2\log(\log(n))$.


texts: How many number of nodes we can create under hyperledger fabric?

texts: We are using hyperledger fabric. We have a doubt like, is there any limit, of creating number of nodes while configuring hyperledger fabric?


texts: Why do we need epsilon-transitions in Thompson's construction?

texts:
So as learned every DFA is an NFA. I feel like I understand DFA much better than NFA, so I try to convert my regular expressions to DFA, but I want to understand both sides.

For example a|b (a Union b):

However, are we losing anything if we eliminate the epsilon from these expressions, every DFA is an NFA right so what are we losing if we don't include it?


texts:
I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.
In the introduction part:

Cellular automata can be viewed as either computers or logical universes where computers may be embbed.

What i am trying to understand is, is it always a given Cellular Automaton  is a computer ?
like Elementary Cellular Automata {ECA} rule 110 and rule 90, i know that rule 110 is universal which makes it a computer but what about rule 90 ... what about other ECA rules are they also computers ?

Suppose we have a cellular automaton (x), how do we know that it is a logical universe (as stated by the author), how can we know if it is a logical universe where computers can be embedd in or not and how can we know if it is just a computer ?

I know that logical universes are Cellular Automata, but what dimensions these universes should be to implement a computer easily, 1D like ECA or 2D like Conway's Game of Life ?


texts: Splay trees: why are depths of nodes on the access path halved?

texts:
The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:

  Splaying not only moves x to the root, but roughly halves the depth of every node along the access path.

What is the intuition for this claim? The paper includes some figures (splaying in a tree of all zig-zigs or all zig-zags) and while I can see at a high level that splaying helps other parts of the tree, it's not really clear to me where the halving comes from?


texts: Split graph in two parts, such that most nodes have even number of edges

texts:
We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between nodes of different parts are destroyed and not counted.

All possible splittings are allowed, even the one where all nodes are in one part. Each node should be in one part, we are required to print the nodes of one part.

This given graph has $5$ nodes, and the splitting made here is best because all nodes have even number of edges in the same part.

My idea was to do BFS over the nodes and when we find node with odd number of edges to put one node in the other part, but I can't come up with some strong idea.


texts:
I understand the normal definitions of the P/poly class, but I'm curious how the name came about.

The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly that would use a quotient. Is 'A/B' defined to be something like "the class of problems that would be solvable as efficiently as those in A when given B amounts of advice"?

If the 'poly' in 'P/poly' refers to the polynomial amount of advice, why is it not 'P/P'? That is, why do we have two different abbreviations for 'polynomial'?


texts: Relation between combining factors and disentangling for face recognition

texts:
I've read two interesting research papers on face recognition and I'd like to understand the relation between them.

"Learning to Disentangle Factors of Variation with Manifold Interaction" by Reed et al.
"Tensor Analyzers" by Tang et al.

In Reed et al. they say "Our approach is complementary [...], and is also capable of exploiting correspondence information". By correspondence information, they mean using related data points. For example, two different pictures of the same person's face correspond to each other by identity.

How are the approaches complementary?

Tang et. al seem to be using a purely statistical method which can be thought of as an extensions to Factor Analysis. Basically, instead of having a single latent variable, they have groups of latent variables with gaussian priors. They use the resulting Tensor Loading for classication.

Reed et. al use Restricted Boltzman Machines (RBMs) but put restrictions on the energy function of their latent variables that ensure disentangling.

Regardless, both approaches seem to be trying to find patterns accross corresponding information, but how are they complementary? What evidence is there that they aren't identifying the same things?


texts: Confused about beta-reduction/shifting in untyped $\lambda$-calculus with de Bruijn terms

texts:
In Types and Programming Languages, the family of sets of terms with de Bruijn indices in the untyped $\lambda$-calculus is defined in this way:

Let $T$ be the smallest family of sets $\{T_0, T_1, T_2, ...\}$ such that

$k \in T_n$ whenever $0 \le k \lt n$;
if $t_1 \in T_n$ and $n \gt 0$, then $\lambda. t_1 \in T_{n-1}$;
if $t_1 \in T_n$ and $t_2 \in T_n$, then $(t_1\ t_2) \in T_n$.

The $\beta$-reduction operation is then defined as $(\lambda. t_{12})\ v_2 \rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1(v_2)]t_{12})$, where $\uparrow^d(t)$ is the function to add $d$ to the indices of all free variables in $t$. By the definition of the $\uparrow$ function, if $t \in T_n$, then $\uparrow^d(t) \in T_{n+d}$. Substitution is defined like so:

$[j \mapsto s]k = s\ $if $k = j; k$ otherwise
$[j \mapsto s](\lambda. t_1) = \lambda. [j+1 \mapsto\ \uparrow^1(s)]t_1$
$[j \mapsto s](t_1\ t_2) = ([j \mapsto s]t_1\ [j \mapsto s]t_2)$

I can't seem to get these definitions to work properly in manually reducing the term $((\lambda. 0)\ (\lambda. 0))$ (i.e. the identity function applied to itself). Here are the steps I've gone through in attempting to apply the $\beta$-reduction rule; I'll add a subscript to each term indicating which set in $T$ I think the term is in, so e.g. $(\lambda. 0_1)_0$ is an abstraction of $0 \in T_1$, and the abstraction itself is in $T_0$. I believe that if done properly, $((\lambda. 0_1)_0\ (\lambda. 0_1)_0)$ should reduce to $(\lambda. 0_1)_0$.

$(\lambda. 0_1)_0\ (\lambda. 0_1)_0$
(by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1((\lambda. 0_1)_0)] (\lambda. 0_1)_0)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}([0 \mapsto (\lambda. 0_2)_1] (\lambda. 0_1)_0)$
(by def. 2 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. [1 \mapsto\ \uparrow^1((\lambda. 0_2)_1)]0_1)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}(\lambda. [1 \mapsto (\lambda. 0_3)_2]0_1)$
(by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. 0_1)$

Now I've worked myself into a corner - $\uparrow^{-1}(\lambda. 0_1)$ should reduce to $(\lambda. 0_0)_{-1}$, which is nonsensical. I also haven't actually performed any substitutions, which seems like it must be incorrect. Am I misapplying these definitions somehow?


texts: Big Oh rules - How to argue in case of negative base

texts:
Let us say you have a function $C_n = (-2)^n + 2^n$.
It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.
However, how would I go about arguing this? The rule I had in mind would be that $a^n$ is $O(b^n)$ if $0 < a \leq b$. But since $a$ is $< 0$, this rule cannot be applied. How would one argue the relevancy of the roots in cases like this, where the specific conditions do not hold up?


texts: If adding an edge to an undirected acyclic graph where no new vertex is introduced => cycle?

texts:
I want to know if adding an edge to a undirected acyclic graph introduces no new vertex to the undirected acyclic graph then therefore we can say that adding this edge creates a cycle? I am confident this is correct, but I am looking for a formal proof on this if it is true(preferably a published paper that shows this).

My take is that when you add 1 edge to a undirected  we can...

Introduce 1 new vertex to the undirected  acyclic graph => we still have a undirected
acyclic graph
Introduce 2 new vertices to the undirected acyclic graph  => we have two connected components that are undirected and acyclic.
Introduce 0 new vertex to the undirected acyclic graph => we create a cycle, clearly this adds at least another path to reach the vertices of this edge.


texts: How $N$ qubits correspond to $2^N$ bits?

texts:
I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. This looks to me like infinite bits. How do they choose alpha and beta so that it becomes 2 bits?

Edit: Why is it commonly said that $N$ qubits correspond to $2^N$ bits?


texts: Is intersection of regular language and context free language is "always" context free language

texts:
I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g.,
\begin{align*}
L_1 &= L(a^*b^*)\\
L_2 &= \{a^nb^n\mid n\geq 0\} \quad\text{(which is context free)}\\
L_1\cap L_2 &= \{a^nb^n\mid n\geq 0\}\,.
\end{align*}
But my question is what if the regular language is finite, such as
\begin{align*}
L_1 &= \{ab\}\\
L_2 &= \{a^nb^n\mid n\geq 0\}\\
L_1\cap L_2 = \{ab\}\,.
\end{align*}
Here intersection comes out to be finite and the language generated by intersection of both language is also finite which is regular (I know it's also context-free but regular is a stronger answer here).

What mistake am I making in understanding the concept?


texts:
I am hoping someone can break something down for me in a way I can digest.
I am trying to understand the running time for the median of three partitioning.

What is the goal of median of three partitioning? Is it to eliminate the possibility of selecting the largest / smallest element as the pivot, thus resulting in O(n^2) run time?
What would the run time be of a simple median of three partitioning function? Since there are only 3 possible comparisons, and the comparison operation runs in O(1) time, wouldn't it just be 3O(1) or negligible?

Any assistance would be greatly appreciated. Thus far, I have referenced CLRS and the following three pages for assistance:

Median of Medians Recurrence Relation for 3-grouping
Counting elements that are greater than the median of medians
http://www.cs.fsu.edu/~breno/COP-4530/slides/21-anim.pdf


texts:
Background
I need such an algorithm inside an android app (home launcher) to show the recently used apps. I want to avoid simple LRU / MRU logic by combining those logics (or use an alternative if anyone has a suggestion). I don't want an app that was started 100x before 10 weeks to stay on top until another app was started 100x and I don't want to only show the LRU apps on top. I want something that matches what a human would expect to see in the most recently used section.
Solution
I can of course save every app launch in a database (including its timestamp) and then give each launch a weight based on its age and then sum them up and calc an avarage value. That's a valid solution and would fit my needs. BUT it will grow the database indefinitely.
Question
Does anyone has an idea or does there exist an algorithm for such a problem already that does not depend on a full list of historical data (app launches in my case)? But instead does update values that belong to each app?


texts: How do you represent LISP as mathematical / logical model?

texts:
I asked this in stackoverflow, but the question probably fits here better.

This question arose from the objection that LISP is regarded as a functional language with some simple principles, namely functions, variables, and operators that roughly correspond to predicates, propositional variables, and connectives in logic respectively.

How would you define recursive structure and "data is a function is a data" paradigm central in LISP as a mathematical model? How about list processing feature? Can we derive LISP from simple mathematical foundations starting from propositional logic up to some specific factored logic?

Surely there must be a model, not only for LISP, but many similar "old" languages. So, I'd like to know, what are the necessary concepts of mathematics to define LISP-like language.

Point is not on what paradigm LISP fits the best, but to find out the simplest mathematical model for the language in question.

Lately, I found this paper of McCarthy (1960) which may answer the question: http://www-formal.stanford.edu/jmc/recursive.pdf

Logic, arithemic and automata by Church (1962) also seems a useful source: http://www.mathunion.org/ICM/ICM1962.1/Main/icm1962.1.0023.0058.ocr.pdf


texts:
I'm trying to come up with a CFG for a language: {$0^n1^{2n}01|n\in\mathbb{N}$}

I tried doing:
$A\rightarrow\epsilon$
$A \rightarrow A10$
$S \rightarrow A01$

It only worked for {01, 01101} but doesn't work for the other cases.
Can someone help me?


texts: Count combinations differing by fixed number of elements

texts:
I'll try to formulate my problem through an example.
Lets suppose we have a collection of items of type a,b,c,d,e,f.

a1, a5, a7
b2, b3
c5, c6, c7, c8
d4, d5
e1, e2, e3
f3, f7, f8

If we take one element from each type there are 3*2*4*2*3*3 abcdef lines (combinations).

We have another random line
a1b5c7d1e5f7.

I want to count how many from the combinations lines differ by the current line in exactly 3 elements.
I.e these lines differ only in one (the first) element

a5b5c7d1e5f7
a8b5c7d1e5f7

I want to do that if it's possible without generating and comparing each combination.


texts: Checking equality of integers: O(1) in C but O(log n) in Python 3?

texts:
Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.
def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

But consider what is happening under the surface. Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. In either case this scan is $O(b)$ where $b$ is the number of bits. Since integers have a constant size in bits in C, this is simply $O(1)$.
EDIT: C doesn't compare bit-by-bit see this answer
In Python 3 however, integers do not have fixed size and the scan remains $O(b)$ for the number of bits in the input, or $O(\log a)$ where $a$ is the value of the input in base 10.
So if you're analyzing code in Python, any time you compare two integers, you are embarking on a  surprisingly complex journey of $O(\log n)$ with respect to the base 10 value of either number.
For me this raises several questions:

Is this correct? I haven't seen anyone else claim that Python compares ints in log time.
In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?
Should you notice or care about this distinction in the real world?

EDIT: It is easily verified (and intuitive) that Python cannot compare arbitrarily large ints in constant time. So a better way to ask question 1 above might be "What (if any) is the justification for calling this operation $O(1)$? Because it's pragmatic? Conventional? Implied by the RAM model?


texts: Equivalence between MIN UNCUT and MIN-CSP_XOR

texts:
In this paper

  Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 2005.

Agarwal et al. claim that the following two problems are equivalent.

  Consider boolean variables $b_1,\dots ,b_n$ and a set of constraints of the form $b_i \oplus b_j = 0$ and $b_i \oplus b_j = 1$. The goal is to minimize the number of unsatisfied constraints.

and

  Given a graph $G=(V,E)$ find a cut that minimizes the number of uncut edges.

If constraints were only of the form $b_i \oplus b_j = 1$, the equivalence is straightforward. However, if we also consider constraints of the form $b_i \oplus b_j = 0$, the first formulation seems more general to me.

How are these equivalent?


texts:
I have the following multiple dimensional scaling (MDS) minimization problem in vectors $v_1, v_2, \dots, v_n \in \mathbb R^2$

$$\min_{v_1, v_2, \dots, v_n} \sum_{i,j} \left( \|v_i - v_j\| - d_{i,j} \right)^2$$

which I wish to solve numerically using gradient descent. I know all the values of $d_{i,j}$.

I am confused because the input to gradient descent is just a vector, but for this problem it is $n$ vectors. I've come across scant information about a gradient-matrix and matrix calculus but I don't understand enough to see how this is analgous with vector calculus and hence gradient descent.

Is solving this minimization problem via gradient descent possible and why?
How else could I solve this minimization problem numerically for $v_1, v_2 \dots, v_n$?


texts: What is the difference between object detection, semantic segmentation and localization?

texts: I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic segmentation vs localization is. It would be nice if you could give sources for your definitions.


texts: Problems for which there is no algorithm with smallest time complexity

texts:
Are there any problems where there is no smallest time complexity, so there is a big-$\mathcal{O}$ but no big-$\Theta$?

More formally, I am looking for any problem $p$ where

for any algorithm that solves $p$ in time $f(n)$
there provably exists another algorithm that solves $p$ in time $g(n)$
where $g(n) = o(f(n))$.

An example would be a problem for which there exist algorithms of complexity $\mathcal{O}(n^k)$ for all $k > 0$, but for which there is no algorithm of lower complexity, like $\mathcal{O}(1)$ or $\mathcal{O}(\log n)$.


texts: Is there a known maximum for how much a string of 0's and 1's can be compressed?

texts:
A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that).

This is of course not correct (and it could be that my memory of what he exactly stated is not correct). Understandably it would not be practical to compress any string of 0's and 1's to just two bits because (even if it was technically possible), too many different kind of strings would end up compressing to the same two bits (since we only have '01' and '10' to choose from).

Anyway, this got me thinking about the feasibility of compressing an arbitrary length string of 0's and 1's according to some scheme. For this kind of string, is there a known relationship between the string length (ratio between 0's and 1's probably does not matter) and maximum compression?

In other words, is there a way to determine what is the minimum (smallest possible) length that a string of 0's and 1's can be compressed to?

(Here I am interested in the mathematical maximum compression, not what is currently technically possible.)


texts: Name of BFS variant with multiple queues with different priorities

texts:
Is there a name for the following variant of BFS that operates on trees with non-root starting point?:

Instead of a single queue that all neighbor nodes are added to when processing a node, two queues are used ($Q_A$ and $Q_B$).
Children nodes are added to $Q_A$, and parent nodes are added to $Q_B$.
When selecting the next node to process, $Q_A$ is drawn from, and only when $Q_A$ is empty is $Q_B$ drawn from.

One application for this (and the one that made me think of this) is for ranking "close" documents in a folder hierarchy (based on the leaf-node discovery order of the algorithm). For example in the following hierarchy:

- Root Folder
  - Folder 1
    - Document 1.1
    - Folder 1.2
      - Folder 1.2.1
        - Folder 1.2.1.1
          - Document 1.2.1.1.1
    - Folder 1.3
      - Document 1.3.1
  - Folder 2
    - Document 2.1

If we start our search at Document 1.1 we would like to see the following ranking (which the algorithm produces):

Document 1.1
Document 1.3.1
Document 1.2.1.1.1
Document 2.1

Document 1.2.1.1.1 should appear higher than Document 2.1 since there is a closer common ancestor (Folder 1), even though the former is technically further away (distance of 4 vs. 5).

Some other things I considered that don't actually work:

BFS using a single queue but always enqueuing the parent last. This doesn't work as it's still regular BFS and ranks based on shortest path.
DFS, and always pushing the parent onto the stack first so it's discovered last. This could rank Document 1.2.1.1.1 above Document 1.3.1 depending on the order children are enqueued.

This seems like a pretty standard algorithm, but I couldn't find anything when I searched for it, so I was hoping someone might recognize it and know what it's called.


texts: What is the complexity of Hoffman and Pavley's Nth best path algorithm?

texts:
I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. The implementation is based on QuickGraph's Ranked Shortest Path implementation.

I have been trying to determine the complexity of Hoffman and Pavley's algorithm as well as QuickGraph's implementation, but without any luck -- so basically my question is if someone knows the complexity of the original method proposed by Hoffman and Pavley as well as the complexity of QuickGraph's implementation?


texts: Literature on nonlinear dictionary learning

texts: Can anyone direct me to some literature on learning nonlinear dictionaries? I don't mean sparse dictionaries specifically, but for example learning kernel parameters, or learning $W$ where $y = \phi(Wx)$ and $\phi$ is a fixed nonlinear function. There seems to be fairly well established methods when $\phi$ is linear, but I haven't found much for nonlinear. thanks!


texts: Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

texts:
What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph?

I did some searching and found that the number of hamiltonian cycles on a planar graph with $n$ vertices is $O(\sqrt[4]{30}^n)$ where $n$ is the number of vertices in the graph. For grid graphs, I just found enumerations for small $n$, but no bounds.


texts: Finding prime factors of non-random key generator

texts:
I have been working on a challenge i found on the internet. It is as follows:

  You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random number generator it uses frequently produces the same primes when it is generating keys.

  Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).

  Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d

  Key 2:
   2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f

These seem to be common RSA 1024-bit keys.

My approach to the problem was to implement Pollard's rho algorithm to find factors, then once a factor is found, try dividing the decimal form of the keys by that factor until it is not divisible anymore. Iterate.

Now, i used Pollard's rho and tried to divide until the key is not divided anymore because of the information the problem gave: the keys are not completely random.

But here comes the question: assuming the algorithm generates two primes and multiplies them to get a co-prime, which is the key, the low randomness doesn't help much, does it? I mean, even if both keys share a common factor, finding it the first time would take the regular-impractical-exponential time.

That seems to be the case, as my Python algorithm is running for about 5 hours now and has not found any factor to the second key, which i decided to start with.

As it is a challenge, i assume there is a practical way of finding the answer.
So what im i doing wrong? Is just the algorithm choice wrong, as Pollard's rho is intended mainly for integer with small factors? Is my assumption that i can only use the lack of randomness after i find the first of the four factor, to then try to break the other key with the same factor, wrong?

I would like if someone could just point me in right direction, instead of just giving the answer. Thank you.


texts: Why is empty in this Abstract Syntax Tree?

texts:
I given the following code to write as AST:

 {
       a = 4;
       while (a<10)
         if (a<5)
           a = a+5;
         else
           a = a+3;
 }

Looking up the solution:

                       PROG
                         |
                        SEQ
         _______________/ \_______________
       SEQ                              WHILE
    ___/ \___                    ________/ \________
  EMPTY     EXPR                LT                _IF2_
             |                 / \         ______/  |  \______
           ASSIGN            VAR CST      LT      ASSIGN    ASSIGN
            / \               0  10      / \       / \       / \
          VAR CST                      VAR CST   VAR ADD   VAR ADD
           0   4                        0   5     0  / \    0  / \
                                                   VAR CST   VAR CST
                                                    0   5     0   3

Why is in the left side of the tree we have an EMPTY?

Why is the do we need SEQ why isn't it directly EXPR in the left side?


texts: Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

texts:
I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether
$$AB = C$$
and be correct with high probability.

The algorithm  choose a random $r$ n-bit vector and if
$$A(Br) = Cr$$
then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr[error] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)_{i} = d_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v_i = \tilde r + v_i \;\; (\operatorname{mod} \; 2) \implies r = \tilde r  \;\; (\operatorname{mod} \; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr[A(Br) \neq C] = Pr[Dr \neq 0] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.


texts: Is there a specific methodology for developing mobile applications?

texts: I'm looking for a methodology made specifically for mobile applications development. I have read about Waterfall and Agile but they are more general. Also, I want a methodology for when there is only one programmer. There is one for only one person: PXP, but its problem is that it lacks in documentation, so I would like to know if there is one more rigorous in that aspect, like for example indicating which diagrams should be made. For example, RUP has some preset documentation formats, but obviously it is not an appropriate methodology in this case.


texts: Algorithm for graph with nodes grouped into sets

texts:
I have a weighted graph. The nodes of this graph are grouped into sets, and each node has only one corresponding set (no overlapping). Nodes in the same set do not have edges between them. An edge only connects nodes that are in different sets.

I want to select one node from each set, such that the total weight of the edges between these nodes is minimized. Between two sets, I will only be traversing one edge.

Only some sets are adjacent to each other, they are not all interconnected. But some sets do have multiple neighbours. When one set is adjacent to another, the nodes in these two sets form a complete bipartite graph.

Are there any algorithms to accomplish this? And is there a name for this type of graph?


texts: Why do processor designers allow some pipeline hazards to occure

texts: Actually this is a exam paper question I found during studying pipelined MIPS architecture.My idea is  designers allow to occur hazards because of the cost to make complex design to prevent hazards,so it may be better to allow them than preventing them...It's just my idea..


texts: How to calculate multibit trie storage size?

texts:
I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will exist between root and leaf nodes inclusive: 8-8-8-8). This is just a basic multibit binary trie that doesn't use any form of compression as it is for demonstration purposes only.

How can I calculate the memory storage requirements for a few basic scenarios (this is just to store the IP data, excluding any other data such as pointers to the next branch/leaf node in memory for example);

The worst possible case is to hold all IPv4 addresses as individual /32 subnet entries (so 4.29 billion routes, the tree is "full")?
To store 1.048 million routes (2^20) in the "best" case scenario described below?
To store 1.048 million routes (2^20) in the "worst" case scenario described below?

For 2. above I imagine the best cast scenario in terms of memory requirements to be 1 million routes that all fall under 1.0.0.0/8 for example, they would fit into the IP ranges of 1.[0-16].[0-255].[0-255].

For 3. above I image the worst case scenario in terms of memory requirements is 1 million routes evenly spread out across all possibilities such that many 8 bit nodes are created in the tree with empty space in them. For example, the routes would fall in the ranges of [0-255].[0-255].[0-15].0 (this is ignoring the fact that many devices wouldn't route a packet with 0 in the first or last octect, this is about the memory requirements only).

When trying to calculate the answer to point 1, above I came up with the following sum where k is the stride:

k + (2^k * 8) + (2^k * 2^k * 8) + (2^k * 2^k * 2^k * 8) ==
8 + (256 * 8) + (256 * 256 * 8) + (256 * 256 * 256 * 8) ==
134744072 bits / 8 == 16.34MBs

For points 2. and 3. above I have found and equation on this website: O((2^k ∗ N ∗ W)/k) , N is the number of prefixes and W is the prefix size in bits. However, this seems wrong to me because there will be shared nodes even with 1 million prefix entries: ((2^8) * 1048575 * 32)/8 == 1073740800.

What are the correct formula for these three calculations?


texts: Why do we say that polynomial time is easy?

texts:
For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so.

Intuitively, I can guess what the relation between P problems and easy problems is. Experience tells me that P problems are easy too. However, using only mathematical terms and theoretical arguments, why is P the class of easy problems?


texts: What's the most efficient way to print all paths from root to leaves in a directed graph?

texts:
I have a directed graph created in matlab. I am trying to print all paths from root to leaves. I used stack to implement my algorithm but it seems very slow when I have large number of nodes and edges.

Is it possible to solve this problem in O(nlogn) time ?

%This is my graph:
output =
   edges: {[0 1]  [0 2]  [1 3]  [1 4]  [1 5]  [2 6]  [3 6]  [2 7]  [3 7]  [4 7]}
vertices: [0 1 2 3 4 5 6 7]

%I am traversing with this code
maximal_sets = {};
stack=java.util.Stack();
stack.push(0);
CP = [];
Q = [];
labels = ones(1,size(output.vertices,2));
while ~stack.empty()
    flag = 0;
    x = stack.peek();
    for e = 1:size(output.edges,2)
        if output.edges{e}(1) == x && labels(output.edges{e}(2)+1) == 1
            flag = 1;
            w = output.edges{e}(2);
            stack.push(w);
            CP = union(CP,w);
            break
        end
    end
    if flag == 0
        Q = [];
        % PRECEDES are leaves of the graph
        if any(PRECEDES{end}==x)
            for v=1:size(CP,2)
                Q = union(Q,CP(v));
            end
        end
        if size(Q,2) > 0
            maximal_sets{end+1} = Q;
        end
        for ed = 1:size(output.edges,2)
            if output.edges{ed}(1) == x
                labels(output.edges{ed}(2)+1) = 1;
            end
        end
        labels(x+1) = 0;
        stack.pop();
        CP = CP(find(CP~=x));
    end
end

for i = 1:size(maximal_sets,2)
    disp(maximal_sets{i})
end

%The paths from root to leaves (not including root which is 0) are listed:
 1     3     7

 1     4     7

 1     5

 2     6

 2     7

This works well with toy examples, but when I have 403 vertices, and 6717 edges. It does not stop. I think it is exponential.

The traversing code was taken from [http://drum.lib.umd.edu/bitstream/handle/1903/4638/TR_87-130.pdf?sequence=1&isAllowed=y] and modified.


texts: Why can the construction of a polynomial-sized structure be done in logspace?

texts:
In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, and state this can clearly be done in logspace, which is not that clear to me. It would seem to me that constructing a polynomial-sized graph would only be doable with polynomial space, since how would one store the constructed graph with less space? The wikipedia page on logspace reductions tries to clear up this misunderstanding by stating

  It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space.

which somewhat helps. I'm still missing the intuition behind it though, and am searching for an intuitive example of why the construction of some polynomial-sized structure can "clearly" be done in logspace.


texts: An advice to a self-learner of computational complexity

texts:
I'm a mathematics undergraduate student (going to start my third year very soon). I'm trying to teach myself computational complexity. Sadly, there are no courses provided in my university on the topic and there are no specialists on it (In fact, it seems that my university has no specialists in theoretical CS at all). So, I have no choice to learn the topic except via self-study. I've already gone through the first few chapters of Computational complexity: A modern approach  [ but I did not solve any of the exercises (except two or three in the first chapter exposing what are TM's and Halting problem) ]

I face some problems with the exercises of in the text:

one thing is that I feel that the kind of thinking needed in computational complexity is quite different than that of mathematics that I'm familiar with (There is an emphasize on algorithmic thinking etc and how to reduce problems to other problems and to make a TM simulating another TM etc) which is something I find difficult.

Is there any way do you recommend to help me developing this level of maturity about algorithms, reductions etc?
One reason of difficulty of "1" is that I don't know to what extent should I be rigorous? For example, when I'm doing a reduction or a simulation, it's possible that I can see intuitively that something is clear and can be done but the details would be very very tedious to actually carry out and hence I feel that I don't understand the thing very well. The point is that, I know that there must be a compromise between rigor and intuitive thinking. But since I've no guide nor an instructor, I don't know where this line should be.

when should I carry out all the details if something somehow clear and when should I be satisfied with the intuition? It seems that there are much more details in computational complexity than is usually present in the math I know and hence, where the compromise should be?
I wonder if there exists any source of exercises\problems that are quite easier than those provided in Computational complexity: A modern approach so that I can train myself with the basic notions\constructions etc before tackling more complicated exercises. Also, a source of (quite-detailed) proofs
of the main theorems would be great since many theorems have only a sketch of the proof in the text.

For my background, I've learned basics of programming (I've trained for awhile in python, C and C++) but not much but I'm quite familiar with mathematics specially mathematical logic (up to completeness and Incompleteness theorems), advanced set theory (forcing), Algebra (linear, Abstract, universal algebra and some category theory) and basics of topology and reals analysis. I've taken a course on Discrete mathematics too (combinatorics + graph theory).

I apologise if my question is off-topic but I know no better place to propose those question than here.


texts: Reduction from Partition problem to 3-Partition problem

texts:
I'm trying to show how to reduce the Partition problem to the 3-Partition problem.
I'll first describe the problem using the definitions and notations I'm familiar with (I hope they're legit), and will then ask my question.
So, the Partition problem is as follow:
Given a multiset of integers $X$, we have to decide whether or not $X$ can be partitioned into two sub-sets $A,B$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i$.
In the 3-Partition problem, given a multiset of integers $Y$, we have to decide whether or not $Y$ can be partitioned into three sub-sets $A,B,C$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i=\sum_{x_i\in C}x_i$.

I want to show a reduction $Partition\leq _p 3Partition$,
That is, to show that given $X$ as input for the Partition problem, I can build $Y$ as input for the 3-Partition problem, s.t. $X$ can be partitioned to two iff $Y$ can be partitioned to three.
So given $X$, let $\sum_{x_i\in X}x_i=m$, and define $Y$ as:
$Y=\left \{ x_1, x_2,...,x_n,\frac{m}{2}|x_i\in X \right \}$.

Proof:
The first direction is easy: suppose that $X$ can be partitioned to two sub-sets $A,B$ s.t. the above conditions hold, then $Y$ can be partitioned to three: $A,B,C$, while $C=\left \{\frac{m}{2} \right \}$.
I'm stuck with the second direction: suppose that $Y$ can be partitioned to three, why does that guarantee that $X$ can be partitioned to two?

b.t.w, how can I be sure that $\frac{m}{2}$ is an integer? do I even have to pay attention to it?


texts: Doubts on Definition of Indistinguishable Encryption in the Textbook

texts:
In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as such that for every probabilistic polynomial time adversary A there is a negligible function negl(n) such that

$\Pr[PrivK_{A,\Pi}=1] \leq negl(n)$

where PrivK is the indistinguishability experiment and for the purpose of this question we only need to know that the experiment outcome is 1 iff the adversary makes the correct guess.

My doubts are as follows. Consider a sequence of probabilistic polynomial time adversaries $\{A_i\}_{i>=1}$ whose advantage in the indistinguishability experiment is bounded by the following sequence of negligible functions

$\Pr[PrivK_{A,\Pi}=1] \leq negl_i(n) = \frac{1}{(1+1/i)^n}$

Clearly it is necessary for the above conditions to hold for a indistinguishable encryption. But is it a correct model/condition for real-world applications? For example, in practice we typically choose a sufficiently large n and set up some encryption scheme. However, there is the always some adversary $A_i$ that wins the experiment with probability close to one. So what's wrong?


texts: The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)

texts:
By the definition of L=DLOGSPACE or of NL=NLOGSPACE (or any sublinear space class) there is an extra tape (for the Turing machine): the input tape, which is only for reading  - but for arbitrary reading. The machine can read the first 10 cells and then maybe go back to read the 1st und 2nd cell.

My question is: If we restrict the way of reading that every cell is read only one time (in one direction: the 1st, 2nd, 3rd,... to the last cell of the input - and then nothing can be read of the input tape!), will we get same classes L and NL or will we lose some languages?


texts: Adaptive Radix Tree - Question regarding child indexing

texts:
i have to write an exam in a course given by one of the contributing professors of this paper: http://www-db.in.tum.de/~leis/papers/ART.pdf

Of course this could also be a possible topic in the exam. Now i understand the basic advantages and structure of this tree, but i just cannot fathom some details. Maybe someone here can help me with that:

So Node4 store up to 4 partial keys (of 1 byte each) and up to 4
child pointers. The child pointer used is determined by the position
of the partial key, right?
Starting at Node48 the child pointer is indexed by using the partial key itself as index into the "key"-array and using that value as index into the child-pointer array, right? But why do we have a 256-element array for the key-bytes although there are only 48 child pointers?
Node256 is just an 256-element array indexed through the key byte.

And at last what are those red numbers depicted in this image?

Thanks a lot!


texts: Set relationship between Big-Oh and Theta notations

texts:
I was reading "Introduction to Algorithms" by CLRS and it says that:

We write $f(n) = O(g(n))$ to indicate that a function $f(n)$ is a member of of the set $O(g(n))$. Note that $f(n) = \Theta(g(n))$ implies $f(n)=O(g(n))$, since $\Theta$-notation is a stronger notion than $O$ notation. Written set-theoretically, we have $\Theta(g(n)) \subseteq O(g(n))$.

Q1: What do the authors mean by strong notion? What is strong notion, when we use it, how does it help us (here) knowing one implication is stronger than the other and how does it affect when creating implication.

Q2: It seems contradictory in a sense by saying that $\Theta$ is stronger notion than $O$ and then writing $\Theta(g(n)) \subseteq O(g(n))$.How to deduce and then interpret the second sentence from the first?

I would appreciate your answers.


texts:
Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely?

I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. And I can detect all faces easily too. But when I start to move vertices of the graph it can happen that the graph is no longer valid.

Am I forced to reconstruct my whole graph from scratch every time I move one of vertices, because I could screw the topology of the graph?

Or is there any better data-structure for this purpouses?


texts: Is this variant of set cover NP-complete?

texts:
Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\{S_1,\ldots,S_m\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ or less", then this is NP-complete.

Now suppose that I add the following:

$|S_1| \gt |S_2| \gt \ldots \gt |S_m|$.

Is this still NP-complete?

I guess that, given 1., we know that the sets $S_i$ are all distinct and then the only cover for $U$ is $S$ but I am not sure about this.


texts: Computer vision methods without "pre-training"

texts:
I'm new to computer vision and I have a common question that I couldn't figure out with Internet or books.
As I understood, in general, there are two main approaches in modern computer vision: neural networks based methods and more "classical" methods that use feature extration (edges, keypoints, gradient and etc), like edge detectors, HOG, SIFT and others.

In case of neural networks everything is clear: we have a networks and we use datasets to train it. In other words, we can't use neural networks without previous training it (I call it "pre-training").

And as I understood, we have a bit different situation with features based methods. All examples and techniques that I have already seen consist of two steps. At first, we extract features (maybe with scene pre-processing), and then we use a classifier to recognize the object by those features. If we want classifier to work, we need to train it. So, again, like in case of neural network, we need pre-training.

My question is: are there any computer vision methods that don't need pre-training? Of course, maybe we can use something like a custom, or sometimes "naive" algorithm for certain situation, but are there more common methods? And another related question - are there any methods that can tell us just if the scene contains object, without telling were is it and what kind of that object class is it, again, without pre-training?

Thanks for all answers!


texts: Multilayer Perceptrons for solving variational problems

texts:
Can we use a multilayer perceptron to solve variational problems?

By variational problem I mean something we might encounter in the calculus of variations, for example the geodesic problem: given two points A and B in the plane, find the curve of shortest length going from A to B. This is of course not the most interesting problem since the answer is just a line segment, but I'll use it anyways. The mathematical version of the constrained geodesic problem would be:

Find $y(x)$ defined on $[0,1]$ such that $y(0)=1, y(1)=0$ and for which the functional $L[y(x)]=\int_{0}^{1}\sqrt{1+y'(x)^2}$ is minimized.

For pattern recognition problems we might train an MLP with some training patterns and adjust the weights and biases so as to minimize and error function, which measures how accurately the net outputs come to the desired outputs for the training samples. We can do this for example by gradient descent. It is well known that multilayer perceptrons (MLP) can approximate any function we want, so if our algorithms work well we should be able to make the error function as small as possible.

Idea: Instead of using an error function based on training data, can we use a neural net to minimize a functional $L[y(x)]$ by gradient descent? The net would have one input $x$ and one output $y(x)$, and some hidden neurons and the goal would be to tweak the weights and biases until the functional is minimized.

Is there any merit to this?


texts:
I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other.  In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that $AB=BA=\text{Id}$.

Is there an efficient way to do this?  Can we do it with expected running time approaching $O(n^2)$?

Assume we are working with $n\times n$ boolean matrices (all entries 0 or 1, arithmetic done modulo 2).  I am fine with an approximate algorithm (say, it samples from a distribution exponentially close to the desired distribution).  My motivation is solely curiousity; I have no practical application in mind.

The obvious approach is to generate a random invertible matrix $A$, compute its inverse, and set $A=B^{-1}$.  This has running time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant -- something in the vicinity of $O(n^3)$ in practice.  Can we do better?

An approach that occurred to me is to choose a set $T$ of simple linear transformations on matrices such that, for each $t \in T$, we can apply the modifications $M \mapsto tM$ and $M \mapsto Mt^{-1}$ in $O(1)$ time.  Then, we could set $A_0=B_0=\text{Id}$, and in step $i$, sample a random $t$ from $T$, set $A_{i+1}=tA_i$ and $B_{i+1}=B_it^{-1}$, and repeat for some number of steps (say $O(n^2 \log n)$ iterations).  However I'm not sure how we would prove how quickly this approaches the desired distribution.


texts: Proof of equivalence of parse-trees and derivations

texts:
Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa.

Is this intuition correct? If so how can I formalize and prove such a thing?


texts: Help with figuring out if MAX(L) is a CF language

texts:
We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as:

$MAX(L)$ = {$w_1 \in L $| $w \notin L$ so that $w_1$ is a true prefix of $w$}

prove (or disprove): If the language L is CF then the language $MAX(L)$ is CF.

I think that the correct direction here is to disprove.
The question is, how do I disprove it for a general $L$?

I know how to use the pumping lemma to disprove a certain language, but I'm not sure if it can work for a general $L$?

Am I going in the right direction or am I completely wrong?


texts: Count numbers that can be generated by flipping bits according to position intervals

texts:
We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $[L,R]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can apply each operation any number of times and in any order. We have to calculate the number of $M$ bit numbers that can be formed thus.

for Example if $N=3$
and our ranges are : $[0,0]$, $[1,1]$, $[2,2]$.
Now if we need to find number of three bit numbers that can be formed using the above restrictions, our answer would be 8, since we can form everything from 0 to 7.

Example 2: if we have 3 bits and two ranges $[0,1]$, $[1,2]$, we can form $4$ distinct numbers : $0 (000)$, $3 (011)$, $6 (110)$ and $5 (101)$.

I was thinking of doing something like if we could just obtain the $i^{th}$ bit as $1$ after performing some operations we could simply take $2^X$ for all such bits and that many numbers can be formed. But this approach doesn't seem to work in general.


texts: What if SAT Turing-reduces to a problem?

texts:
To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove.

The reduction we need is polynomial time reduction.

But If I take known NP-hard problem and reduce it to some unknown problem by Turing reduction then what I can say about the unknown problem?

I am sure that I can't say it is NP-hard, as the reduction is Turing.


texts: Why are the two farthest points vertices of the Convex Hull?

texts:
I read that in a 2D space, the two points farthest away must be in the convex hull (CH).

Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point that is outside the convex hull (contradiction). I know that a vertex of CH has two adjacent edges that converge at that point, which is of further distance from any other vertex or point within CH, than  the non-vertices beside it. What I mean is shown in the image below: a vertex (p) with two adjacent edges,

Problem is, I don't see how I can prove this more formally.  I am looking for a more concrete proof.

Thank you in advance.


texts:
We know error correcting codes are parameterized as (n,k,d) codes. I wanted to know the values of these parameters for some commonly used error correcting codes in computer memories or in DRAMs, etc.

I just wanted to see some values for these parameters, used in real life applications.


texts: Proving some subsets of a regular languages to be regular languages

texts:
I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can divide the words of L in two parts and get it, since regular languages are closed under concatenation, I dont know if this is correct.
And the other one:
b) $NONEXTENSION(L)=\{u \in L / $ $u$ is not a prefix (not $\epsilon$ or $u$) of any element of $L \} $ is regular
In this one I've no idea how to begin.
Any help would be pretty apreciated. Thanks!


texts:
Koopman, P., & Chakravarty, T. (2004, June). Cyclic redundancy code (CRC) polynomial selection for embedded networks. In Dependable Systems and Networks, 2004 International Conference on (pp. 145-154). IEEE.

In this paper authors compare performance of different CRC polynomials in terms of minimum Hamming distance of two codes with the same checksum.

The naive method of doing this would require enumerating all codes that have the same checksum. This is computationally intractable for 2048 bit long data words that authors consider - so they must have used some more more efficient technique.

I did not find a mention in the paper on how the authors computed it. But it would be interesting to know the method as it would allow to numerically verify optimality of used CRC polynomials on given data word size.

What algorithm authors used to compute minimum HD for given CRC polynomial on long data words?


texts: Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

texts:
I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why would the following not work:

As we insert, for instance, a new node to the tree, we check whether we insert into the left or right subtree. If we insert into the left, we rotate the result RIGHT, and vice versa for right subtree. Recursively it would be sth like this

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

That should avoid the whole "splay" procedure, don't you think?


texts: What should I first learn in computer enginerring?

texts: I am struggling right now, and I need help.


texts: Decreasing runs of inner loop in outer loop

texts:
I am trying to determine the worst case runtime of this program:

while n > 1
  for i = 1,..,n
    m = log(n)
  n = n/2

Obviously the outer loop runs log(n) times, because n is halfed after each step.

But the inner for loop is dependent on the decreasing n and I am not quite sure how to deal with that.

A simple bound for it would be n, so the whole thing runs in at most log(n)*n, but I am sure the inner loop is faster than that.

If I look at each step of the outer loop, I see that the inner loop runs n,n/2,n/4,..,2 times. So I would say all together the inner loop runs at most 2n times which is in O(n).

Can I just deduct from that fact that the overall runtime is O(log(n)+n) = O(n)?

I am unsure because I am not multiplying anything, which I feel like I should when dealing with multiple loops.


texts: Formal grammar with variables for consistent substitutions

texts:
In a rewriting system, suppose the production rule S→xAyAz (or <S>:=xyz, in BNF), where S and A are nonterminal symbols and x, y, z are any string.

This rule produces the string xa1ya2z, where a1 and a2 are strings substituted by the nonterminal symbol A. The substitutions a1 and a2 may be equal or different strings.

But what if I want to a1 and a2 to be the same string; that is, if the nonterminal A be substituted by the same instance in both its occurrences in that production rule?

I used a kind of BNF I created informally for such purpose, with <v:A> instead of : a kind of "typed variable", whose type is a nonterminal symbol and the variable is the same substitution for all its occurrences. Thus, <S>:=x<v:A>y<v:A>z, and <v:A> is substituted for the same string in its both occurrences.

What is the name of such a grammar that uses variables for consistent substitution of a nonterminal? And there is a grammar formalism for it?


texts:
The Clay paper gives a short proof on this in page 2:
http://www.claymath.org/sites/default/files/pvsnp.pdf

However,

Where does it come from that these are inclusive sets and not separate? Or that $|P| ≤ |NP|$?


texts:
Below I am using a DFA transition function that is extended to accept words instead of just symbols. Let's say it is given that the following information is true:

$$\delta(q_0, 0^3) = \delta(q_0, 0^6)$$

Using this information it can easily be proven that:

$$\delta(q_0, 0^6) = \delta(q_0, 0^{15})$$

is also true.

However let's say we have the same information about a NFA and not a DFA, so that in a NFA we know that the following is true:

$$\delta(q_0, 0^3) = \delta(q_0, 0^6)$$

The question is:

Given that I cannot extend the transition function to accept words in an NFA, (because in an NFA the transition function produces a set)

how do I go about proving that

$$\delta(q_0, 0^6) = \delta(q_0, 0^{15})$$

must also hold true for this NFA?

Is defining a new transition function that takes a set of states and a word and returns another set good way to do so?


texts: Set of all rational numbers less than given computable real number is decidable

texts:
Prove that set of rational numbers less than given computable real
  number is decidable

This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another try.

Same problem can be stated in this way:
Construct an algorithm, which answers the question: Is our given rational number less or greater than their(fixed) computable number?

Here's my poor try so far.

Since it's analysis related problem, I used the $\epsilon - \delta$ definition of computable number, which is:
$\exists f$ computable function, such that $\forall \epsilon > 0, \epsilon \in \mathbb{Q}, f$ gives us $\delta > 0, \delta \in \mathbb{Q}$ such that$|a - \delta| \leq \epsilon$ holds for given computable number $a$

Let $p \in \mathbb{Q}$ be our input, and let $f$ compute for us 2 rationals $q_1$ and $q_2$. It is well known that $|q_1 - q_2| < 2\epsilon$

Now let's choose $\epsilon = \frac{1}{2^{i}}, i = 0,1,2,...$
For each $i$-th step I compute $f$ twice and get $q_{i_{1}},q_{i_{2}}$. I think that our given rational $p$ should hold some condition with both $q_{i_1},q_{i_2}$ which will help me to finish the algorithm, but I couldn't figure this out. I believe there are finitely many checks for each step which will let me know that for example $p < a$ just like in picture below.

What do you think about this problem? Maybe there's more straightforward way to prove this. Thank you.


texts:
Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under $\pi$ we have $\mathsf{P}=\mathsf{NP}$.

This is a homework question I had. My current sketch is: for a language $L_1 \in \mathsf{NP}$, define another language $L_2\in \mathsf{P}$ based on $L_1$ such that deciding $\pi(L_2)$ helps decide $L_1$. Here $\pi(L_2)$ is decidable as $\mathsf{P}$ is closed under $\pi(\cdot)$; $L_1$ being decidable infers that $L_1\in \mathsf{P}$ and thus $\mathsf{P}=\mathsf{NP}$.

I think my sketch is in the right direction but I'm struggling in defining the appropriate $L_2$ here. Any hint would be appreciated!


texts:
How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1.

x + x * y = x
x + x * y = (x * 1) + (x * y)
          = x * (1 + y)
          = x * 1 [THIS LINE]
          = x

thanks


texts: Equivalent expression in English: Set Notation $\{0,1\}^K$

texts:
I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\{{0,1}\}^k$ stands for? Im looking for an explanation in English like what I did below.

$K_e = \text{Encryption Key} $
$K_d = \text{Decryption Key}$
$\mathcal{E}_K(M)$ = Encryption using Key with Message M

$D_K(C)$ = Decryption using Key with Ciphertext

$K \oplus M$

Right now I think $K$ is just the word length of the string. Meaning the key could be either $0^k$ or $1^k$ which corresponds to the key being $0$ or $1$ being repeated $k$ times. e.g. $0^3 = 000$ or $1^5 = 11111$. I believe this is wrong though.


texts:
Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that neither the source or the destination is an obstacle.

I need to, provided a starting node (a square), find any path that visits every single node that is reachable, without visiting any node twice.  If there is no such path, then any path that would visit as many nodes as possible.  In other words, I'm looking for an algorithm to find a Hamiltonian path in such a graph.

I am not looking for the shortest path.

The most important factor is the time the algorithm takes to complete (complexity).

I have searched Google and this site, and I only find variants of the travelling salesman, or algorithms for shortest path visiting all nodes, which won't work in my situation. My algorithm needs to find a path of any length visiting as many nodes as possible while never visiting a node twice. The path can end anywhere.

Does anyone have any tips? I've tried to do this with a variant of A*, but I couldn't make it work. I've succesfully done it by brute-forcing, but as the graph can be rather large, I need something a faster than O(n!).

It would be even better if the algorithm was non-deterministic, which means that if there are multiple possible solutions, we wouldn't always get the same one with the same graph and starting location. I have no idea how to do this without slowing it down though, and speed is more important.


texts: Satisfying assignments, twice-3SAT NP complete

texts:
I wanted to solve the following problem about 3SAT . The question is
1. to show if the problem is NP-complete and
2. whether the problem has two different satisfying assignments.

"TWICE-3SAT Input: A propositional formula ϕ in conjunctive normal form, such that each clause consists of exactly three literals (as in 3SAT). Question: Does ϕ have at least two different satisfying assignments?"

I understand that we have to use reduction of a known NP-complete problem (such as an independent set) to the problem asked. But I can't go further. I would appreciate your help. I have been working on this for almost a week but I cannot go further.


texts: Which one of these two sequences is random, and which one is not?

texts:
We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$:

$$
B_k(\alpha_1\ldots\alpha_k) =
\begin{cases}
1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1
\\
0 \text{ otherwise}
\end{cases}
$$

Then we define two sequences:

$$B_3(\alpha_1\alpha_2\alpha_3)B_3(\alpha_4\alpha_5\alpha_6)B_3(\alpha_7\alpha_8\alpha_9)\ldots$$
$$B_4(\alpha_1\alpha_2\alpha_3\alpha_4)B_4(\alpha_5\alpha_6\alpha_7\alpha_8)B_4(\alpha_9\alpha_{10}\alpha_{11}\alpha_{12})\ldots$$

Which one of these two sequences is (algorithmically) random, and why? I should note that apparently there is an obvious measure-theoretic fact that gives away which one is not random.


texts: Number of Retransmission in case of Go Back N

texts:
While Going through Exercise problem of " Computer Networking  A Top-Down Approach" by Kurose and Ross, i encountered this problem.I am giving my approach and the point where i am stuck at.
Question

Suppose Host A sends 5 data segments to Host B, and the 2nd segment
(sent from A) is lost. In the end, all 5 data segments have been correctly
received by Host B.How many segments has Host A sent in total and how many ACKs has Host B sent in total for Go Back N

Given Answer

GoBackN:
$A$ sends $9$ segments in total. They are initially sent segments $1, 2, 3, 4, 5 $and later resent segments $2, 3, 4, $and $5$. $B$ sends $8$ ACKs. They are $4$ ACKS with sequence number $1,$ and $4$ ACKS with sequence numbers $2, 3, 4,$ and $5.$

My Approach /Doubt
I agree with the number of transmission of data segment by Host $A$.But i have doubt regarding the Acknowledgement by Host $B$.
Why?

We know that GBN has sender side window size=$N$ while reciever side as only$1$ which is the reason that it cannot  recieve Out of order packet.

Now When Host $A$ sends entire packet $1,2,3,4,5$  where $2^{nd}$ gets lost then Host $B$ which is expecting Sequence number $1$.On recieving sequence number $1$, it will send ack as $2$i.e expecting sequence number $2$.As Sequence number gets lost , host $B$ will recieve sequence $3,4,5$ for which it will discard the packet as it is not the packet it is expecting.
On recieving again sequence number $2,3,4,5$(retransmitted packet), Host $B$ will send the Acknowledgement.
Total Acknowledgement i am getting is $5$ i.e ACk no for sequence number $1,2,3,4,5$ not $8$.
Please help me out where i am wrong ??
Thanks


texts:
In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I will give here the basics of the proof, after which I will ask my question regarding this proof.

The authors reduce Exact Cover to DTSP, by adapting Papadimitriou's reduction from Exact Cover to Euclidean TSP (ETSP). This is done by first noting how Papadimitriou's proof makes it so Exact Cover has a solution if and only if the optimal ETSP tour has length no more than some $L$. Le Ny et al. note however that if Exact Cover admits no solution, then the optimal ETSP tour has length at least $L + \delta$, not just $L$, for some defined $\delta$. Next, they note that the optimal DTSP tour length has the following relation with an optimal ETSP tour length : $DTSP \leq ETSP + Cn$, for some $C$ (proven by Savla et al.). Le Ny et al. then go on to construct Papadimitriou's ETSP instance from a given Exact Cover instance, in which they then multiply all distances by $2Cn/\delta$.
They then prove that Exact Cover has a solution if the optimal DTSP tour has length no more than $2CnL/\delta + Cn$, whereas Exact Cover has no solution if the optimal DTSP tour has length at least $2CnL/\delta + 2Cn$.

My question now is, why is it necessary to multiply all distances by $2Cn/\delta$ ?
It would seem to me that not multiplying the distances by anything would still result in Exact Cover having a solution if the optimal DTSP tour has length no more than $L + Cn$, and Exact Cover having no solution if the optimal DTSP tour has length at least $L + \delta + Cn$. What am I missing here?


texts: Selection Sort runtime in terms of Big O

texts:
I'm trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$.

Looking at the math, the runtime is

$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$.

And this is stated to be equal to

$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$.

Does someone have a great pedagogical explanation that my dim-witted mind can understand?


texts:
so i have this problem where:

I have to accomplish a challenge A with n quests. Each quest gives me:

p points and
needs t time to be done.

The object is to complete the challenge A that needs M points to be completed, in the least possible time.

So let's say A has these following quests:

q1 => p1=20 points, t1=5 minutes
q2 => p2=40 points, t2=20 minutes
q3 => p3=10 points, t3=2 minutes
q4 => p4=30 points, t4=6 minutes

I want to solve this problem for M = 50. Note that you cannot solve challenges, you can only solve quests. If you get enough points with the quests that you have completed, then you can say that you have completed challenge A.
I could solve q2 and q3 in time 22. I will get the 50 points, but it's not the optimal solution since solving q1 and q4 will also give me 50 points in time 11.
I know that this is a knapsack problem but i just can't figure out how i am suppose to store in my table so i can get a result the set of quests that have to be done in order to have the least possible time. I need to find a dynamic programming algorithm which will be able to find the answer.  If someone knows how my data structure should look like and how i should store the data inside, generally what idea should i follow in order to solve this problem, i would really appreciate help since i've been stuck and i don't know how to solve it.
I will put a picture just to make more clear the whole problem:


texts: Understanding This Graphical Depiction of a Radial-Basis Function Network

texts:
Let $f$ be a Radial-Basis Function Network:

$$
f(X) = \sum_{i=1}^N a_i p( \lvert \lvert b_i X - c_i \lvert \lvert)
$$

From Artificial Intelligence for Human Beings, the following depicts $f$:

In the concrete example of this diagram, it seems that $N = 3$ (i.e., there are $3$ RBFs).

Question 1: How is it possible that there are multiple outputs on the right of this diagram coming from multiple summations? In particular, there are 3 summations producing 3 outputs. But shouldn't there just be 1 summation producing 1 output? Are the second and third summations coming from a different set of RBFs than the first summation?

The textbook continues:

  Because multiple summations exist, you can see the development of a classification problem. The highest summation specifies the predicted class. A regression problem indicates that the model will output a single numeric value.

Question 2: Here, does "the highest summation" refer to the very top "Output 1" in the diagram? Or does it refer to the largest summation in the numerical sense?

Question 3: Where in the equation for $f$ above is the $Bias$ (depicted in the diagram as $Bias (1)$) represented?


texts: Computer Algebra: Algorithms for solving equations symbolically

texts:
As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns 1), and all expressions can be reduced to a canonical form.  The CAS can also differentiate expressions.

Using this paradigm, what kinds of algorithms are there for solving equations? An equation in my model would be represented as an (=) tree with two subtrees that are the left and right expressions. I know there is no "magic bullet" for solving all equations, but are there algorithms out there that are designed to symbolically solve an equation? If there aren't, what would be the general approach? What kind of classes can equations be split into (so that I might be able to implement an algorithm for each kind)? I don't want to use naive methods and then paint myself into a metaphorical corner.


texts: Present syntax rules in a more succinct way

texts:
I am resuming syntax rules for a small language:

\begin{eqnarray*}
e_C &::=& \epsilon \mid constant \\
\textit{prefix-op} &::=& - \\
\textit{infix-op} &::=& + \mid - \mid * \\
e_E &::=& e_C \mid \textit{prefix-op} \; e_E \mid e_E \; \textit{infix-op} \; e_E \mid \textit{function}_E (e_{E,0}, e_{E,1},\ldots) \mid \textit{specialE} \\
e_V &::=& e_C \mid \textit{prefix-op} \; e_V \mid e_V \; \textit{infix-op} \; e_V \mid \textit{function}_V (e_{V,0}, e_{V,1}, \ldots) \mid \textit{specialV}
\end{eqnarray*}

The expressions $e_E$ and $e_V$ have something common: $e_C$. Some of their operators look same: $\textit{prefix-op}$ and  $\textit{infix-op}$. Their functions $\textit{function}_E$ and $\textit{function}_V$ are 2 different sets, and $\textit{specialE}$ and $\textit{specialV}$ are totally different.

I am wondering if it is still possible to present this syntax more succinct, more compact in a conventional way... Could anyone help?


texts: Identification and the definition of data type

texts:
A frequently cited definition of data type is that it is a set of values and a set of operations of those values.

I've never read any mention along the lines of a type must be capable of being identified, although the programming languages I've encountered use names to distinguish different types.

Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?
Are there any programming languages that don't use named types?
And, if so, what implications, if any, are there of this? (One possibility I can think of is that it means there is no nominal typing.)


texts: Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?

texts:
Apparently, for every k-tape Turing machine that runs in time $O(t(n))$, there exists a 1-tape Turing machine that runs in $O(t^2(n))$.

I can see how any multi-tape machine $M$ can be simulated by a 1-tape machine $S$. Just have the tape of $S$ contain all of $M$'s tapes separated by some symbol such as #.

However, why is the running time of $S$ $O(t^2(n))$ if the running time of $M$ is $O(t(n))$? I think it would be $O(t^k(n))$ since there exist $k$ tapes, and we have to traverse through all of them.


texts: Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?

texts:
In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$.

Intuitively, with a fixed parameter $k$, in the worst case, the exhaustive search needs to check whether every vertex subset of size $k$ is vertex cover. The number of vertex subset of size $k$ is $\dbinom{n}{k}$, and we have $\dbinom{n}{k}=O(n^{k})$. Meanwhile, the number of steps to check a vertex subset of size $k$ is $O(kn)$, since we only need to verify whether the number of edge connected to or contained in the vertex subset is $m$, where $m$ is the number of edge in the graph. Thus, the time complexity of the exhaustive search is $O(k n^{k+1})$.

Is there any problem with my above analysis? And how to get a exhaustive search algorithm of time complexity $2^{k}n^{O(1)}$?


texts: Is the longest datapath really the limiting factor on clock cycle speed?

texts:
I've been watching a lecture series on computer organization and one of the lecturers statements is something along the lines of 'the clock cycle can only be as fast as the time it takes to complete the longest datapath'.

This doesn't make sense to me.  Couldn't chips be architected so that the control unit can check the state of the operation(s) running on it, and block or allow the next use of the path accordingly?

In which case the limiting datapath would be this checking process (which should be pretty fast since its just checking against a few 'dirty bits' given from the rest of the data paths?