texts:
I have a point cloud that has several connections. What I want to identify are the largest (by area) irregular (convex) polygons. I put convex in brackets as it is not fully necessary (like in the red polygon case), but polygons with very small corner angles should not be considered. I know that this is quite ambiguous.

Do you have any suggestions? What I tried so far is a kind of brute force approach of growing polygons by adding more and more points and checking for polygon-line intersections. This is of course computationally very demanding for larger point and connection clouds.


texts:
I read that no LL(1) grammar can be ambiguous.

Can we just make a LL(1) predictive parser table for a grammar to determine whether it's ambiguous? If the grammar is not LL(1), can we say that grammar is ambiguous?


texts: Seek time and latency on disc for a file that is stored sequentially?

texts:
Say there is a file that is sequentially organized over 2.5 tracks on a disc. I'm assuming there would be a non-zero value for seek time and latency when accessing the first track, but what about the remaining 1.5 tracks?

I know it wouldn't actually be zero but I'm talking about a negligible value. When the head moves from the first track to the next, do you assume the next wanted data follows immediately after the end of the last track or would you assume that head just misses the correct sector and the disc has to spin once first?

Sorry for the verbosity, first year CompSci student and this is all very new to me.


texts: Dinamic programming relationships in the all-pairs shortest paths problem

texts:
CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths.
The kernels of these algorithms (side-by-side) look almost identical, except that they seem to exploit two different dynamic programming relationships about this problem.
What's the intuition behind the difference between these two dynamic programming relationships?

To be clear, the code for EXTEND-SHORTEST-PATHS is actually used by the routine below, with a total runtime of  $O(n^4)$ which is slower than Floyd-Warshall above, which runs in $O(n^3)$.


texts: Scheduling Problem Optimisation using LP solvers

texts:
I am currently working on a scheduling system which schedules individuals based on timeslots that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM).

The individuals currently indicate their preference for whether they prefer the AM/PM session for each day of the week in each month eg. (Monday|Jan|AM), this would mean that the person would prefer to do AM session for Mondays of January. Furthermore they are allowed  to indicate that they do not want to be scheduled for certain months of the year, eg. he's able to choose that he does not want to do February time slots and thus my system is required to schedule him accordingly. [Complexity]

As such I currently am required to schedule this large set of data (individuals - 30 people / timeslots - 202). [Large Set]

I have been referred to by some advisors to look into Integer linear programming / linear programming in order to help me schedule these individuals optimally, thus I am currently looking into libraries such as Gurobi to help optimise the solution of this issue. I hope to be enlightened about the following question:

Would solution optimisers such as Gurobi be implementable in my scenario?


texts:
I am a little confused to reduce these lambda calculus expressions.  I am instructed to give applicative and normal order reductions for these expressions.

$(a):$  $$(\lambda x. (\,(\lambda y.(* 2 y)\,) (+ x y)\,)\,)\,y $$

$(b):$  $$(\lambda  x. \lambda y. (x y)\,) \,(λz. (z y)\,)\,$$

Here are the steps I took in my first attempt at $(a)$:

$$(\lambda x. (* 2 (+ x y)))y $$
$$(\lambda x. (* 2 (+ x z)))y \thinspace $$

(substituting $y$ with $z$)
$$(* 2 (+ y z))$$

I'm unsure if I even reduced that correctly and how I would reduce in applicative order.
Any help is appreciated, thanks!


texts: ε-NFA to DFA - initial state with only epsilon transitions

texts:
I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases), but this case I never saw before.

Thank you guys!


texts: Is there a 2D-layout algorithm for DAGs that allows the positions on one axis to be fixed?

texts:
I've got a DAG of around 3.300 vertices which can be laid out quite successfully by dot as a more or less simple tree (things get complicated because vertices can have more than one predecessor from a whole different rank, so crossovers are frequent). Each vertex in the graph came into being at a specific time in the original process and I want one axis in the layout to represent time: An edge relation like a -> v, b -> v means that a and b came into being at some specific time before v.

Is there a layout algorithm for DAGs which would allow me to specify the positions (or at least the distances) on one axis and come up with an optimal layout regarding edge crossovers on the other?


texts: Explanation of a simple algorithm's Big O complexity

texts:
I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation:

Loop2(n)
    for i := 0 to n
        j := 0
        s := 0
        while s <= i
            j := j + 1
            s := s + j

I can see that the outer loop (alone) is run $O(n)$ times, and that the inner loop is $O(\sqrt n)$. However, the part that confuses me is that the correct answer, according to the paper, is $O(n \cdot \sqrt n)$.

I though that, since the inner loop is dependent on $i$, that it would be run $\sqrt i$ times, for $i$ going from $0..n$. Meaning that in total, the loop would run roughly $n$ times, making the whole algorithm $O(n\cdot n)=O(n^2)$. I kinda drew the logic from an analysis of insertion sort, where $$\sum_{i=0}^{n} n-i = O(n^2)$$

I think I remember the above correctly. Can anyone fix my broken logic here?


texts: An algorithm for grouping items according to "constrains" and "preferences"

texts:
Before i explain exactly what i mean, let me just say that i never studied CS or low level programming, so i don't know much about the subject(I'm a self-taught JS programmer). To the point:
Imagine you have a group of workers, you need to construct a work-schedule for. Each worker has "constrains", meaning days/shifts(each day has three shifts, let's say) they can't work on, and "preferences", meaning their more desired shifts.
For example, John declares: "Can't work on Thursday at all; Can't work on Tuesday morning; Would like to have at least 4 shifts this week".
So imagine, that you have many shifts and many workers, and you need to construct a schedule that takes into consideration their requests as much as possible.
I'm sure this problem was already addressed. Can you maybe point me to the right direction, and direct me to some algorithm/methodology, from where i can start?


texts:
I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step.

$T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ which then I got $T(n)=T(n-2)+2(n-1)+2n$. $T(n-2)$ gives $T(n-3)+2(n-3)$ which plugging it back in gives $T(n)=T(n-3)+2(n-3)+2(n-1)+2n$. I substituted the following $2(n-3)+2(n-1)+2n$ into a summation that gave me $\sum_{i=0}^k 2(n-i)$$=-(k+1)(k-2n)$. I am not too sure how I should continue.


texts: Show that a set is turing reducible to another set

texts:
Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$
Show that both $A$ and $B$ are Turing-reducible to $A+B$
I am kind of confused about this notion of turing reducibility thing.
Does it mean that There is a turing machine which converts an input from $A$ to an element of $B$
on the tape. There is a term called oracle that also pops up. So if we have an oracle for $B$
does it mean that there is a decider for $B$? What's an intuitive workable definition of oracle?


texts: a cut containing exactly one edge in each path

texts:
Given a digraph with a source $s$ and target $t$, must there be an edge cut which contains exactly one edge in every path from $s$ to $t$?  I'm not interested in a minimum cut; any cut would do.

If not, how close to "exactly one" can we get?


texts: How to show that i have significant improvements over the baselines?

texts:
I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines.

I tried my classification algorithm on some image datasets such as Extended Yale, and in the literature (other papers) i noticed the same amount of improvements in the results was assumed good enough (e.g. only 0.20 % improvements).

So, how should i convince the reviewers that my results are good enough according to the previous works?


texts: What is the difference between following two finite automata?

texts:
I'm solving problem of drawing the finite automata of (1+0)*(10). Which is any string ends with 10. I've drawn the following diagram for this one:

But somewhere in solution it is given the following diagram:

I can't understand what is the difference between these two? Is my solution is correct? If it is not than what changes in my solution will take me to this given solution?


texts: Existence of a loop in a Turing machine?

texts: Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Can we conclude that there must be a loop in the finite-state control as its inputs get larger?


texts:
I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts the production $S\to\epsilon$ is allowed (as long $S$ isn't on the right hand side of any production)
I'm quite confused.

The book is Formal Models of Computation: The Ultimate Limits of Computing
by Arthur Charles Fleck and the passage in question says:

  Given two context free grammars $G_1$ and $G_2$ first determine if $\epsilon\in L(G_1)$ and $\epsilon\in L(G_2)$. If so, $L(G_1)\cap L(G_2) \neq \emptyset$,  otherwise $L(G_1) - \{{\epsilon}\}$ and $L(G_2) - \{{\epsilon}\}$ are context-sensitive.

Maybe what the book says is that they are also context sensitive (since the set of context-free languages is properly contained in the set of the context-sensitive)?


texts:
I have a question from one of the exercises in CLRS.

Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$?
What about a fraction $1/2^n$?

I have arrived at the step where for a linear time sorter, there will we $2^n$ nodes in the decision tree, which is smaller than the $n!$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $n!$ inputs of length $n$". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $n$ will have $n!$ possible permutations.


texts: Distributed problems in Financial Services?

texts:
When we talk about distributed computing - it often refers to problems in biology or web search where there is a large quantity of data to process, or email where there is a large number of concurrent users.

Often in financial services, the problem space is OLTP for online banking, or overnight batch processing for summing up EOD totals and reporting.

Is there an example problem in financial services that requires the tools available in distributed computing?


texts: Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?

texts: Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?


texts: Are there context free grammars for all restricted Dyck paths?

texts:
A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather than use $1$ and $-1$, it is common to use "U" and "D" for $1$ and $-1$, respectively, so we might write UUDD instead. (These might be more familiar as Dyck words.)
It is well-known that Dyck paths have a standard "grammar." The "Dyck grammar" for a path $P$ is
$$P = \epsilon \quad | \quad U P D P.$$
This grammar is very useful because it lets us quickly compute the generating function which enumerates the number of Dyck paths of given lengths.
I am interested not in all Dyck paths, but restricted sets of Dyck paths. For example, consider the Dyck paths which avoid "peaks" (the bigram UD) at positive even heights; UUUDDD is such a path, while UUDD is not. If we could devise an unambiguous grammar for such paths, then we could write down an equation for the generating function which counts them. (There is such a grammar. It requires two production rules - one for the paths which avoid peaks at even heights, and one for paths which avoid peaks at odd heights.)
This idea leads to a natural question:

Given a (possibly infinite) set of positive integers $A$, does there exist a finite, unambiguous context-free grammar which generates precisely the Dyck paths whose peaks avoid $A$?

The answer (I think) is "yes" when $A$ is finite or an arithmetic progression. I suspect that the answer is "no" in every other case, but I have no idea how to begin proving this.
For example, here is a special case that I cannot decide:

Is the set of Dyck paths which avoid peaks at positive squares a context-free language?


texts: What does a kernel of size n,n^2 ,... mean?

texts:
So according to Wikipedia,

In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the parameterization. The ''parameter'' of an instance $x$ is the number $\kappa(x)$. A '''kernelization''' for a parameterized problem $L$ is an algorithm that takes an instance $x$ with parameter $k$ and maps it in polynomial time to an instance $y$ such that

$x$ is in $L$ if and only if $y$ is in $L$ and
the size of $y$ is bounded by a computable function $f$ in $k$.
Note that in this notation, the bound on the size of $y$ implies that the parameter of $y$ is also bounded by a function in $k$.

The function $f$ is often referred to as the size of
the kernel. If $f=k^{O(1)}$, it is said that $L$ admits a polynomial kernel. Similarly, for $f={O(k)}$, the problem admits linear kernel.
'''

Stupid question, but since the parameter can be anything can't you just define the parameter to be really large and then you always have linear kernel?


texts: How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet?

texts:
I am looking for an automated way to answer the question: what are the URLs on the world wide web that contain at least two strings from a set of strings.

So if I have a set of strings {"A", "B" and "C"} -- I want to know, what pages on the world wide web contain "A" and B", "A" and "C", "B" and "C" or "A", "B" and "C."

Obviously, for this simple example: Google it!

But I want a scaleable, automated, and free solution. Google does not permit automated queries. Yahoo makes you pay.

One idea I have is (1) start with a URL, (2) check the text at that URL for the search strings (3) parse out the links from the text (4) record that you have checked the page and if it contains the strings then (5) search the links from the initial URL. Repeat until you have searched the tree.

How feasible is this in terms of time and space on a single commodity machine -- given the size the internet? The internet is really, really big -- but only a comparatively few pages will contain these strings (they are proper names).

I don't want to index the whole web as if my laptop were google!

Most of the crawler's time will be spent confirming that the pages don't contain the strings.

I'm trying to get a rough ballpark to understand if this is even remotely feasible.


texts: How to find upper and lower bound without using formula

texts:
I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful.

Prove the following sum is $\Theta (n^2)$ (we have to find $O(n^2)$ and $\Omega (n^2)$)

$P(n)= 1+2+3+4\cdots + n$
$P(n) = n+(n+1)+(n+2)+\cdots +2n$

Note you cannot use any formula you have to do it my algebraic manipulation.
This might be simple but I am not getting any clue right now and I dont have solution of it.


texts: Number of balanced binary trees (The Art of Computer Programming)

texts:
In the section 6.2.3 (Volume 3) Donald Knuth says:

... we can ask about the number $B_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the generating function $B_h(z) = \sum_{n\ge0} B_{nh}z^n$ for small $h$, from the relations
$$B_0(z) = 1,$$ $$B_1(z) = z,$$ $$B_{h+1}(z) = zB_h(z)(B_h(z) + 2B_{h-1}(z)).$$

I would understand this formulas if they were like this:
$$B_0 = 1$$ $$B_1 = 1$$ $$B_{h+1} = B_hB_h + B_hB_{h-1}+B_{h-1}B_h = B_h(B_h + 2B_{h-1})$$
Which means that there is only one empty tree ($h=0$), only one tree with a single node ($h = 1$) and number of other trees (of $h+1$, where $h\ge1$) can be calculated as the number of all combinations of shorter trees - having trees shorter by one on as both sub-trees ($B_hB_h$), having shorter by one on the left and shorter by two on the right ($B_hB_{h-1}$) and the wise versa ($B_{h-1}B_h$).
These formulas are actually the same as the ones from the book if $z=1$. This makes me think that it is correct.
Is my reasoning correct? And if it is, can anyone explain what this $z$ actually stands for?


texts: What features should a critical section have to maximize performance?

texts: Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?


texts: design a strange data structure, is it possible?

texts:
I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible?
When just find min is important (not removing) there is lots of $O(1)$ solution for all operation.
Update: All given times is amortized cost.


texts: Probabilistic switching between breath-first and depth-first

texts:
I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and describes the role of of a queue in BF search vs a stack in DF search. It got me thinking hypothetically about an intermediate approach in which the usage of a data structure is, in a probabilistic fashion, treated as either a queue or a stack in a graph search. I'm imagining it would be like a bandit problem where switching between BF and DF would be a stochastic function of how much BF vs DF has been done.

What I've described is not fully specified as there may be different algorithms that implement this strategy. Even so, do such algorithms exist? Please give an example.


texts: Worst time complexity for finding a median number for a list and array data structure

texts:
This was a question that came up in a past exam paper in my computer science course, it states:

"There are two simple, un-optimised sorted data structures, each storing
n numbers. The first is a list; the second is an array. What is the
worst-case complexity of extracting the median number from each data
structure? Are the averages cases different? Why?"

I would like to know the answer to this question as I am confused on what is being asked? Should we not be analyzing algorithms like binary search and not the data structures themselves?


texts:
In the proof of the predecessor subgraph property (page 14 of the following notes)
http://www.cs.sfu.ca/CourseCentral/307/binay/shortestpath.pdf
$d[v_i] \geq d[v_{i-1}]+w(v_{i-1},v_{i})$ is assumed true. Why is this? Shouldn't it be the other inequality:  $d[v_i] \leq d[v_{i-1}]+w(v_{i-1},v_{i})$ by triangle inequality?


texts: Number of descendants of each node in a DAG

texts:
1) Is there a better algorithm than the naive O(|E|.|V|) to compute the number of descendants of each vertex in a DAG?

2) Is there an online algorithm to do so, assuming that nodes are added one by one and connect to a non empty subset of the existing nodes?

Context: I'm interested in the case where m = O(n), millions of vertices, tens of millions of edges typically.
Alternatively, counting the number of descendants which are also sinks would be useful.

A probabilistic approach would be min-hashing, as a way to represent the set of descendants of every node. The union of the min-hash structure is trivial, and the cardinality of the union can be estimated from the number of coincidences in the min-hashes.

However, I'm not sure how well behaved that would be when propagating up the DAG, intuitively it looks like errors would compound pretty fast.

Very related: https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag
And actually a duplicate of: https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability


texts: Spliting in AVL tree in $O(\log n)$ times

texts:
Suppose we are given a balanced binary search tree $T$, AVL tree, now
we want split $T$ at a arbitrary node. Can it be done in $O(\log n)$?

First i read following links:

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

Trying to understand a way to split an AVL tree in O(log n)

Now  i think, because of height of our tree $T$ is $O(\log n)$ then after splitting at a arbitrary node, it is sufficient to re-balance our tree $T$ start from one of leaf node, in this manner we do rotation and because of each level want constant number of rotation to be balanced, after $O(\log n)$ will be in root of $T$ and our tree $T$ is balanced. Are my argument is true?


texts: Computational Geometry: what is the key of the BST in the algorithm " Partitioning a polygon in y-monotone pieces"

texts:
The algorithm to partition a polygon into y-monotone pieces is as follows:

Input. A simple polygon P stored in a doubly-connected edge list D
Output. A partitioning of P into monotone subpolygons, stored in D

Process:
       1.  Construct a priority queue Q on the vertices of P ,use y-
           coordinates to determine priority.If two points have the same y-
           coordinate, the one with smaller x-coordinate has higher
           priority.
       2.  Initialize an empty binary search tree T
       3.  While Q is not empty Do
       4.      remove the vertex vi with the highest priority from Q
       5.      call the appropriate procedure to handle the vertex,
               depending on the type of the vertex
       6.  End Do

An Example process of handling a vertex if it is a merge vertex will be as follows:

HandleMergeVertex(Vi):
    1. If helper(ei−1) is a merge vertex
    2.     insert the diagonal connecting vi to helper(ei−1) in D
    3. delete ei−1  from T
    4. search in T to find the edge ej  directly left of vi
    5. If helper(ej) is a merge vertex
    6.     Insert the diagonal connecting vi to helper(ej) in D
    7. helper(ej) = vi

Now in DeBerg's book of computational geometry , he quoted as:

  In the approach above, we need to find the edge to the left of each vertex.
  Therefore we store the edges of P intersecting the sweep line in the leaves
  of a dynamic binary search tree T. The left-to-right order of the leaves of
  T corresponds to the left-to-right order of the edges. Because we are only
  interested in edges to the left of split and merge vertices we only need to store
  edges in T that have the interior of P to their right. With each edge in T we store
  its helper. The tree T and the helpers stored with the edges form the status of the
  sweep line algorithm. The status changes as the sweep line moves: edges start
  or stop intersecting the sweep line, and the helper of an edge may be replaced

Now my question would be , what is the key of this BST T ? Is it the vertex in consideration , is it the edge ? And how to determine what is the edge at the left of an vertex?


texts: Asymptotic complexity class preservation under logarithm?

texts:
If $f(x)$ and $g(x)$ are two functions such that

$$f(x) \not\in \Omega(g(x))$$

does

$$\log f(x) \not\in \Omega(\log g(x))$$

hold?


texts:
I have a large (~1k) number of boolean formulas like:

f1(x) = p1 AND p2
f2(x) = (p1 AND p2) OR p3
f3(x) = p4 OR !p5

The argument x is a set, and the predicates (the p's) assert that a certain condition is met on the set (typically, that x contains a certain value).

For every input, I have to evaluate all the formulas.

As an example, given a chair, f1 would say: the chair is red and the chair has a head rest, f2 would say f1 OR the chair was built before 1980 and so forth.

Some predicates invalidate the formulas statistically sooner than others in my data set; one of them would be, for example, the chair was built before 1900 (not many very old chairs are found).

If I scan all the formulas, find the pieces of them that are equal, like in this example, the first part of f1 and f2, is there a way to build a common parse tree that lets me use this information to make evaluating all the formulas faster?


texts: Gain the Mastery of prooving NP Complete Problems

texts:
I want some piece of advice on how can I improve my capability of proving NP-completeness of problems. I am well known with all the concepts theoretically but when it comes to solving down, I get stuck. I don't know where to start with, which gadgets to use, how to make reducible structures. These all things indeed make me feel like a loser and helpless. I want some advice on how should I approach a problem and how to practice given problems in order to gain mastery.
 Any advice, practice material or reference papers or related would be helpful.
Thank you so much.


texts: Finding the approximate weight of intra graph paths

texts:
Say that you have access to a source $a$ and destination $b$ in a weighted graph $G$ with $n$ vertices. There exists a path $p$ from $a$ to $b$ with 2 or more vertices in it. We know the total cost of going from $a$ to $b$ and from $b$ to $a$. However, we do not know how much time it costs for one to from $x$ to $y$ where $x$ and $y$ are adjacent vertices on the path $p$. Is there a way to take a snapshot of $G$ such that we can find an approximate weight of all edges?
My approach was to keep a log of timestamps on each of the vertices for when the last time it was passed through. For example, using the vertices above, if I use the path $p$ to go from $a$ to $b$ then every vertex in $p$ would have a log of how much it cost me to arrive at that vertex. But the problem with this approach is that I do not have access to the intermediary vertices in the path $p$.
Another way to look at this problem is to imagine the graph as a network, each vertex is a node in the network and every weight is the time it takes to go from one node to its adjacent node. So can we find the intra network latency of a network?


texts: How can we implement efficiently a maximum set coverage arc of fixed cardinality?

texts:
I am working on solving the following problem and implement the solution in C++.

Let us assume that we have an oriented weighted graph $G = (V, A, w)$ and $P$ a set of persons.

We receive a number of queries such that every query gives a person $p$ and two vertices $s$ and $d$ and asks to compute the minimum weighted path between $s$ and $d$ for the person $p$. One person can have multiple paths.

After the end of all queries I have a number $k \le |A|$ and I should give k arcs such that the number of persons using at least one of the k arcs is maximal (this is a maximum coverage problem).

To solve the first part I implemented the Djikistra algorithm using priority_queue and I compute the minimal weight between $s$ and $d$. (Is this a good way to do ?)

To solve the second part I store for every arc the set of persons that use this arc and I use a greedy algorithm to compute the set of arcs (at each stage, I choose an arc used by the largest number of uncovered persons). (Is this a good way to do it ?)

I wonder also if there is another procedure that guarantees an optimal solution for $k \le 3$.
I am also wondering how can I implement it efficiently?


texts: Neural net that alters its own parameters

texts: Is it possible for an AI neural net to be able to modify its own parameters/hyperparameters and/or add new parameters/hyperparameters? If so, how has it been implemented? For example, to simulate a human mind, could the net utilize 3 basic emotional parameters before realizing it needs many more and subsequently creating them?


texts: What is the reason of using Gaussian model for Background Modeling?

texts:
I am a new learner to Background Subtraction (Background Modeling) and I am reading a few previous works on how it is performed. Starting with Wikipedia (by searching "Background Subtraction"), I could understand the first few simple methods, until the part "Running Gaussian average". I simply have no idea why a Gaussian probabilistic density function was proposed to fit on the most recent n frames. Reading from the original paper by Wren et al., the reason for using the Gaussian PDF is "computational convenience", which baffled me since the Gaussian PDF does not look simple to me.

In addition, many later methods were based on the Gaussian Mixture Model by Stauffer and Grimson, which was even more complicated. But there seems no explanation about why a Gaussian PDF was used, and why the use was justified.

Can anyone throw some light to me on these questions? Thanks!


texts: Can the foundation of computer science be implemented to include new rules of inference so that computer can do causal reasoning?

texts:
The idea I'm thinking of is about a top-down approach for AI. I would like to know if there can be a model for computers so that they can perform causal reasoning. It seems that causal relation can be simplified to be a  mathematical structure, as an acyclic directed graph. If using type theory, one builds some "time types" $\{\sigma_i,i\in\mathbb{N}\}$ ($\mathbb{N}$ as an index set denoting time points). The variable inhabit different time types means they are at different time points. The signature can be constructed according to the existing causal relation. The formation rule is such constructed that the rules for formulas with variables from the same time types are the same as usual logic, and the rules for different time types are based on the causal relation.

Can someone comment about this idea and give some general review about the development of top-down approach, also about causal reasoning?


texts: Calculating the number of multiplications necessary to evaluate a polynomial

texts:
I was watching a lecture and got confused over a slide. This is what it says:

Consider a polynomial - first representation
$$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$

The space complexity is 100 memory locations.
The time complexity is:

Access lookup operations: 100
Multiplication operations: 4 + 7 + 26 + 100 = 137
Addition operations: 5
Total operations: 242

I don't get how the number of multiplication operations are counted. For example, if we consider $x^{3}$ then it should have just two multiplications, right? Such as $x \times x \times x$, isn't it?
Addition operation is 5 or 4...I think its 4?


texts: Python versus Matlab on the quantity 1/0

texts:
Python and Matlab seem to disagree on the division by 0.
Python:
>>> 1 / 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero

Matlab:
>>> 1 / 0
Inf

with the usual properties of $\infty$ for Inf.
Which one is correct when it comes to the IEEE double-precision format?


texts: "Last Come => More Relevant" data structures

texts:
As I think of data structures I studied and dealt with, they are all optimized to retrieve/put  a random element, to perform optimally based on unspoken assumption that each element has equal odds of being asked for (e.g. Red-Black trees).

By the nature of my program, I need to maintain an online dictionary of items that typically serves items that were added last.

That is, the later an item has been added, the higher the likelihood of it being retrieved back in the nearest future.

Speaking more formally, let's define a set $S$ of pair $(k_i, d_i)$, where $k_i \in K $ and $K$ has a comparison operator $\leq$ defined, $d_i \in D$. Let $p(k)$ be the probability of our need to retrieve pair $(k, d)$.

What is an efficient way to store $S$ with regard to function $p$ ?


texts: Could the empty language be NP-Complete?

texts: I think the empty language is NP but I'm not sure if it is NP-Complete


texts:
Is there a notion of coP problem?

Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?


texts: $\lambda$-calculus, is there encoding of for or while?

texts:
In $\lambda$-calculus, we can encode arithmetic, numbers, booleans, and even compute factorials of numbers, as shown here.

Is there encoding of "for" or "while"?


texts:
A basic instruction cycle consists of these 5 stages.

  Instruction Cycle

  IF - Instruction Fetch
  RD - Instruction Decode and Register Read
  EX - Execute
  MA - Memory Access
  WB - Write Back

I understood the function of all the stages accept the fourth (Memory access). What's the significance of this stage?

Over Internet what I've found is this

  MA(Memory Access) does following operation

  If load or store instruction, then access memory
  If branch instruction, replace PC with destination address

The second point is clear, but I'm confused by the first.

Suppose we have load and store instruction like this
$$(I) R_1 \leftarrow m[A_1]$$ $$(II) m[A_2] \rightarrow R_2$$

what will the MA stage do for the above instructions?


texts:
I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the demonstration of the last part of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3, $[b\rightarrow 1]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $[b\rightarrow 1]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. The natural question, I think so, How it is posible that the tree-like refutation of $\Gamma'$ be a proof for $\Gamma \vdash b'$ if $\Gamma \neq \Gamma'$?.

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.


texts: Deciding whether $f(x) = f(y)$ is beyond RE and coRE

texts:
I would like to prove that the following subset is outside both RE and coRE:

$$A = \{ (p, (d_1, d_2,\dots, d_k)) \mid \text{for each } 1 \le i,j \le k, \; [p]d_i = [p]d_j \}, $$

where $p$ is a program, $d_i$ are inputs, and $[p]d$ is the result of running $p$ on the input $d$.

I was thinking about creating a mapping reduction from HALTnil (the halting problem for the empty input) to $A$ and from the complement of HALTnil to $A$ as well.

Since HALTnil does not belong to coRE, neither does $A$.
Since the complement of HALTnil does not belong to RE, neither does $A$.

Can someone suggest an approach that covers it?


texts: Explanation of Summations for Algorithm Analysis

texts:
I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I am taking currently with the "Introduction to Algorithms" text book by Cormen, Leiserson, Rivest, and Stein (CLRS). This is not one of my homework problems, but rather extra effort for me to try and understand algorithm analysis as it relates to using summations.

For instance, consider the example of $T(n) = T(n-2) + n^2$. An answer I saw floating around had $\sum\limits_{i=0}^{n/2} (n-2i)^2$.  I can understand how to get the $(n-2i)^2$ part, but am not sure how to get the upper and lower boundary conditions, as well as what to do after this point. I guess the total answer for this is $\Theta(n^3)$, but am not making the connection between the summation and the final answer.

I have had calculus in the past, and do remember some of the series chapter that dealt with harmonic, Taylor, geometric, telescoping, and power series. But as it relates to CS, I'm not quite sure where it is going.

So, my questions are:

Why are the lower and upper bounds 0 and n/2, respectively?
What do I do with the summation notation to get a final answer?

I'm sure this is easily answered and that I'm just overlooking something.  I know that a series that looks like the harmonic series, which is $\sum_{i=1}^n (1/i)$, will give $\ln(n) + O(1)$. But most of it I don't understand how to get the values associated with Big-O, Omega, or Theta.

I appreciate the help, guidance, and any examples/tutorials you can point me to.


texts:
I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).

Here is a short description

Idea of the algorithm: We start with color labels that have $\log n$ bits. In each synchronous round we compute a new label with exponentially smaller size than the previous label, still guaranteed to have a valid vertex coloring.

Let $i$ be the smallest index where $c_v$ and $c_p$ differ;
the new label is $i$ (as a bitstring) followed by the bit $c_v(i)$ itself

Grand-parent 0010110000 -> 10010 -> …
Parent       1010010000 -> 01010 -> 111
Child        0110010000 -> 10001 -> 001

The problem I cannot understand this example. Let's take Grand-parent($c_p$ = 0010110000) and parent($c_v$ = 1010010000), on the round when $c_v$ receives $c_p$, so we need to change $c_v$. They differ in 5th bit, counting from 0 (5 in binary is 101), so according to definition, $c_p$ is "$101$"+$c_p[5]=1010$, but in example it's 01010, what I get wrong?


texts: Context free languages belongs to NTIME(n)?

texts:
As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)?

Can anyone point me to a proof or outline it here? Thanks!


texts: Example algorithms for first class in programming for EE students

texts:
I am professor of Electrical Engineering who will teach, for my first time, a class to first-year EE students about programming. This will be their first contact in an academic setting with programming, algorithms, data structures, etc.

When introducing the subject of algorithms, I'd like to present a few problems, give a naïve algorithm that might be the first thing that comes to mind to solve it, and then show an efficient algorithm that is clearly more efficient than the naïve one. Ideally, something that none of the students might come up with on their own. Obviously, being their first class in programming, I can't use overly complicated algorithms or I'll run the risk of confusing rather than illuminating them.

Right now I've collected a few examples:

Naïve modular exponentiation vs. left-to-right modular exponentiation
Linear search vs. binary search
Trial division vs. sieve of Erathosthenes (for creating a list of primes from, say, 1 to 100)
Naïve polynomial evaluation vs. Horner's rule
GCD by factoring vs. Euclid's GCD
Schoolbook multiplication vs. Karatsuba multiplication

Of these, (1) and (2) I believe students could come up on their own, and maybe (3) and (4) as well. (5) and (6), I'd risk saying most wouldn't come up with on their own.

What other algorithms could I use to demonstrate the importance of efficient algorithms? Also, would anyone advise against using one of the examples I've listed above, and for what reason?


texts: Find out duplicate number between 1 to N numbers

texts:
I first saw this question on this website where I was trying on Java puzzles.

Here is the Question:-

You are given in an ArrayList, 1 to N Numbers. For Example, 1,2,3,4,5. However, one of
the numbers is repeated twice. That is, in the form 1,2,3,4,2,5. Find the duplicate number
without using loops.

I thought that this could be done with 2 For loops, and tried running the program which Worked fine. However, the question specified otherwise. Therefore, I checked the answer, which read as follows :-

int highestNumber = numbers.size() - 1;
int total = getSum(numbers);
int duplicate = total - (highestNumber*(highestNumber+1)/2);
return duplicate;

Here numbers is the List(Java) which contains the elements. The getSum(List n)method returns the sum of all the elements in the List.

Then comes this line which I fail to understand. How does total - (highestNumber*(highestNumber+1)/2); result in the correct Answer?

Edit1: As answered below the formula -  n(n+1)/2 is derived from Arithmetic Progression. More details are here


texts: What are the vertical and horizontal focal lengths?

texts:
In this paper,

http://www.vision.caltech.edu/malaa/publications/aly08realtime.pdf

the author mentioned "the vertical and horizontal focal lengths" but didn't have any clear definition.

My understanding about "focal length" is the distance between the lens and the image plane.

Does anyone have the idea about these focal lengths?

Thank you.


texts: Bentley-Ottmann for a mixture of segment types

texts:
Is it possible to use the Bentley-Ottmann algorithm with a mixture of allowed segment types, say, line segments and arcs?

The same question could be asked for Balaban's algorithm but it's gonna be for an other time.

http://www.dtic.mil/dtic/tr/fulltext/u2/a058768.pdf


texts: How to determine likely connections in a social network?

texts:
I am curious in determining an approach to tackling a "suggested friends" algorithm.

Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. These users normally (excluding the edge cases in which a user specifically recommends a friend) have a highly similar network to oneself. That is, the number of friends in common are high. I assume Twitter follows a similar path for their "Who To Follow" mechanism.

Stephen Doyle (Igy), a Facebook employee suggested that the related newsfeed that uses EdgeRank formula which seems to indicate that more is to valued than friends such as appearance is similar posts. Another user suggested the Google Rank system.

Facebook states their News Feed Optimization as $\sum u_{e}w_{e}d_{e}$ where

$u_{e}$ = affinity score between viewing user and edge creator
$w_{e}$ = weight for this edge (create, comment, like, tag, etc)
$d_{e}$ = time decay factor based on how long ago the edge was created

Summing these items is supposed to give an object's rank which I assume as Igy hinted, means something in a similar format is used for suggested friends.

So I'm guessing that this is the way in which connections for all types are done in general via a rank system?


texts: Does |xy| ≤ p in the pumping lemma count for all i?

texts:
While learning about the pumping lemma, I came across the following question:

Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are 0, 1, a01, aa001, etc...

In regular english: a word with leading as, followed by any amount of either 0 or 1 characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of as.

My initial attempt was the following:

Pick w as $ a^p0^p1 $. This obviously holds since $ p \cdot 1 = p $.
Split w into xyz as $ x = \epsilon $, $ y = a^p $, $ z = 0^p1 $.
Show that $ xy^2z = a^{2p}0^p1 $ does not hold, since $ p \cdot 1 \ne 2p $.

However, the answer key instead opts to introduce two new variables $ m \geq 0 $, $ n \gt 0 $, then splits on $ x = a^m $, $ y = a^n $, $ z = a^{p-n-m}0^p1 $ (splitting the sequence of a into three parts). Then, they too use $ i = 2 $ to show that $ xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1 $, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $ |xy| \leq p $ condition of the pumping lemma: x is empty and $ |y| = p $. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually does violate the $ |xy| \leq p $ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?


texts: Expected maximum bin load, for balls in bins with equal number of balls and bins

texts: Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is  $\Theta(\ln n/\ln\ln n)$. How can we derive this fact? Are Chernoff bounds helpful?


texts: Evolutionary theory applied to programming languages

texts: I'm looking for books applying evolutionary theory to the history of programming languages. Researching the topic I have found an interesting paper - Modelling the Evolution of Programming Languages Any hints in this direction appreciated.


texts: Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?

texts:
First Slide: Find Max(A)

// INPUT: A[1..n] - an array of integers
// OUTPUT: an element m of A such that m >= A[j], for all 1 <= j <= A.length
max = A[j==1]
for j = 2 to A.length
if max < A[j]
max = A[j]
return max

Second Slide: Proof By Contradiction
Proof: Suppose the algorithm is incorrect. Then for some input A, either:

max is not an element of A or
A has an element A[j] such that max < A[j]

Max is initialized to and assigned to elements of A - so (1) is impossible.
After the j-th iteration of the for loop (lines 4 - 6), max >= A[j]. From lines 5,6 max only increases. Therefore upon termination, max >= A[j] which contradicts (2).
End Of Slides
This algorithm (first slide) finds the max element in the array. This is a proof by contradiction. Isn't this algorithm already proved when it gets to max >= A[j] in the last line of the second slide. Is which contradicts (2) even necessary? Because in the second slide you showed max is in the array, and then you met the condition of a maxium m: an element m of A such
that m >= A[j] for all 1 <= j <= A.length.
This seems to be two proofs in one. And since it seems to me that the direct proof happens first, then the proof by contradiction is redundant and therefore not necessary. Am i missing something here? Is this only a proof by contradiction? Or is it a direct proof instead?
The image below is just the slides 1 and 2 that I transcribed above. From York University.


texts:
So I have this algorithm that outputs the largest value of an array:

Input: $A[1,\dots,n]$, $n\geq 1$
Output: Largest value of an array

Maximum (A)
  m = A[1]
  i = 1
  while i < n
    if A[i+1] > A[i]
      m = A[i+1]
    i = i+1
  return m

I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.


texts: Greedy algorithm correctness proof (UVA 10716)

texts:
Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols (UVA 10716). I've found an AC solution with the following greedy algorithm (from UVA board): "For each letter find it's first and last occurence in current string. Select letter for which sum of distances from its first occurence to beginning and from last one to the end is smallest. Swap its first occurence to beginning and last to the end. And "eliminate" them --> now you have the word which is shorter. You have to repeat until you have <=1 letters left."

But I can't find the proof (and I can't construct it by myself). The question: how to prove the correctness of the algorithm?


texts: Determine image of hypercube under linear map

texts:
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb R^N$ with each entry of $w$ in the range $[0,1]$. In other words I'd like to find the image of the unit hypercube in $\Bbb R^N$ under the map represented by $A$. Does there exist an algorithm that runs in time polynomial in $N$?

Everything I've thought of so far is exponential, basically looping over the $2^N$ vertices of the hypercube. The problem is similar to that of determining the convex hull of a given set of points, except that the entries in $w$ needn't sum to $1$. Obviously taking the convex hull of all $2^N$ points would work, but it's exponential again.

My motivation is that I want to determine the range of colours that can be seen under a given light source, based on the spectral power distribution of the light source and the responsivity curves of the three cone cells in the eye.


texts: Calculating DFT of a specific polynomial

texts:
This seems like a simple problem but I'm getting the impression I'm missing something.

The problem

Given the values $v_1, v_2, \ldots, v_n$ such that $DFT_n(P(x)) = (v_1, v_2, \ldots, v_n) $ for $ P(x) = \sum\limits_{i=0}^k a_ix^i$ , $k < n$ - find $ DFT_{2n}(P(x^2)) $

My attempt:

First expand $P(x^2) $ :
$$P(x^2) = a_0 + a_1x^2 + \ldots + a_k^{2k}$$
Let's denote by $W^j_n$ the j'th root of unity of order n.
We have : $$ W^j_{2n} = e^\frac{2\pi ij}{2n} = e^\frac{\pi i j}{n}$$
Using this information, let's evaluate a term p of $P(x^2)$ on some $W^j_{2n}$ :
$$a_p(x^2)  = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p$$ (since $e^{2\pi i} = 1$)
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get $\sum\limits_{i=0} ^k ak$ and therefore the final answer is:
$$(\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)$$

This seems wrong, I don't even use the information about $(v_1, \ldots, v_n)$(should the answer be in terms of those?)

Any help would be appreciated.


texts: Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable?

texts:
I want to show that it satisfies Rice's theorem:

(i) $L$ is non-trivial, since $\langle M\rangle \notin L$ where $L(M)=\emptyset$, as $M$ halts/rejects any input string in the first step.

(ii) if $L(M_1)=L(M_2)$ where $M_1$ and $M_2$ are turing machines, then $M_1$ makes more than 10 steps on some input iff $M_2$ makes more than 10 steps on some input.

I'm not sure if the second condition is true, and if so, why?

I know that you can always create redundant states/transitions by moving the read-write head go back and forth without changing anything, thus increasing the number of steps on a given input but giving the same outcome. But I'm not sure if you can always "shorten" a turing machine.


texts: "Job" scheduling with skill restrictions

texts:
I was given this real life problem and was asked if there would be a way to optimize this, I realize that this is akin to a job scheduling problem, but I can't seem to grasp how to make it work with the restrictions:

Given:

A list of jobs J = { j1, j2, ..., jn } 1 $\le$ n where each job will have a list of operations O = { o1, o2, ..., on } 1 $\le$ n and each operation will have a skill requirement s, a time to complete t, and a list of required tools RT = { rt1, rt2, ..., rtn } 1 $\le$ n, RT $\subset$ Tools = { t1, t2, ..., tn }. A job is only considered completable if all operations are completable on the same day. An operation is completable if a worker with the correct skill, tools, and time available can be assigned to the operation.

A list of workers W = { w1, w2, ..., wn } 1 $\le$ n where each worker has a skill s, a list of owned tools OT = { ot1, ot2, ..., otn } 1 $\le$ n OT $\subset$ Tools = { t1, t2, ..., tn }, and a fixed 8 hours of time available.

Output:

A list of workers to assigned operations in a day ( a schedule ) with the minimum total time wasted ( defined as the total time not spent on an operation for all workers ).

I've tried this from a greedy standpoint so far, but every metric I've considered doesn't seem to guarantee minimum time wasted.

Note: This was a problem I tried my best to translate into a more rigidly defined problem, please let me know if I can further clarify this.


texts: What is the difference between complexity theory and computability theory? Is there any overlap between the two or are they completely different? Or is one a subset of the other?


texts:
I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem:

Bag Automaton:
A non deterministic finite state automaton $M=(Q,I,s,F,d)$. $Q$ is the set of states, $I$ is the set of items, $s\in Q$ is the start state, $F\subseteq Q$ is the set of accepting states, $d\subseteq Q\times 2^I\times Q\times 2^I$ is the set of transitions, where $2^I$ is the set of all subsets of $I$.
A computation of a Bag Automaton starts in $s$, with given item set $I' \subseteq I$. At each step the bag automaton in state $q$ and associated item set  $I^* \subseteq I$ does a state transition $(q,A,q',B)$, $A\subseteq I^*$, which sets the state to $q'$ and the bag automaton's item set to $(I'-A) \cup B $. $M$ accepts if there is a sequence of transitions from $s$ to an $f \in F$.

Bag Automaton Computation
Input: A Bag Automaton $M=(Q,I,s,F,d)$, a set $I' \subseteq I$ and a positive integer $k$.

Parameters: $k$

Question: Can $M$ accept on $I'$ by executing at most $k$ transitions?

I am almost certain a reduction from clique where the initial bag contains all vertices will work, but I cannot figure out how to formalize it.


texts: How come finding an $n/2$ size clique in a directed/ non directed graph is not in $\sf NL$?

texts:
obviously the "Finding an $n/2$ size clique in a directed/ non directed graph" is not $\sf NL$ but I'd really like to understand where does it fall in terms of the definition of the $\sf NL$ definition.

I have to have an input and witness tapes, both of them can be polynomial and a logarithmic size of work stripe. So why can't I just guess an $n/2$ clique, each time put 2 vertices on the work tape, check that they share an edge, and count them. The witness tape provides me each time two vertices from left to write, in total $O({\frac{n}{2}}^2)$. In order to count that I need $O(\log ({\frac{n}{2}}^2))$ which is logarithmic. so what's lacking or wrong with this attempt?


texts: Arbitrary precision integer square root algorithm?

texts:
Are there any known subquadratic algorithms for calculating the floor of the square root of an n bit integer?

The naive algorithm would be something like

def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

This takes O(n) iterations, each one involving additions that are O(n) time, so it's O(n^2) time overall. Is there anything faster? I know that for the case of multiplication there are special algorithms that do better than quadratic time, but I can't find anything for square roots.


texts: How may I look for 'regions' of text in a larger corpus of different texts

texts:
I have an extremely large (100GB+) corpus of many different texts. All of them are in English and 'well' formatted. They are not loaded into any kind of database, think of them as a huge collection of text files of many different sizes.

What would be the most efficient way to check and retrieve arbitrary text sequences that may be present in the larger corpus? (Precomputation is allowed).

Is there some kind of hash function that I could use and then compare with my database?

I'm looking for the fastest possible implementation.


texts:
Solving $T(n)=4T(n/4) +(n/\log n)^2$.

When I looked at the question I thought that this can be solved by the 3rd case of the master theorem since $f(n)$ is polynomially larger than $n^{\log_ba
}=n.$ But someone said that this is not polynomially larger since it has $(\log n)^2$ in the denominator.

Then I tried the substitution method.
I have found an upper bound of $n^2$ and a lower bound of $n\log n$ but I am unable to proceed any further.

I want a theta bound.


texts: Fast hashing: combination of different techniques to identify changes in a file?

texts:
I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256.
However, the files are expected to be huge video files with several GB, so calculating the SHA256 hash could take some time, especially over the network.

Therefore I want to combine different other techniques:

file size: if the file size has changed, the content has changed (sure)
head / tail hash
random hash

The latter 2 are part of my question:

My guess would be that in the header there are things like:

frame rates (e.g. Videos)
resolution (e.g. Videos, Images)
(file) length (e.g. in frames, pixels etc.)
last change date (e.g. Word documents, not specifically Videos)

Why I consider checking the tail is:

MP3 has the tag information there
EXIF adds custom data at the end if I'm right

Random hashes would select e.g. 126 regions at random positions in the file with a specific length, e.g. 64 kB and create a hash for them. Of course I remember the offsets for later comparison.
All in all I would use (1+126+1)*64 kB of data for my hash, so I need to read only 8 MB instead of several GB to get the hash.

Maybe it's more a Math question now, but: how likely is it to detect a change using the combination of file size, head, tail and random data to generate this quick hash sum?

I assume that the files are always legal files. There's no benefit in manipulating single bytes. The user would use a normal video editing tool to change the files.

UPDATE:
I unaccepted this answer which came from Crypto.StackExchange. I agree that my proposal is not cryptographic and not intended to be secure. I also agree that CRCing a file is fast, but in my case I really need a hash - I'll explain why:

My application is expected to save bookmarks in videos. My database is expected to save the video hash and the bookmarks.
Users sometimes move or rename files. My program will notice that a file does no longer exist, but will not delete the bookmarks from the database. Instead, when the same video is (accidentally) played again, I want to recognize that it's (probably) the same file.
Users are expected to save files on network drives (NAS) and stream videos. Those are dumb storages. I cannot install a server component. And they might be quite slow, so I really don't want the full hash. Calculating a full hash on a 3 GB file takes at least 5 minutes @ 10 MB/s, no matter how fast the hashing algorithm is.
If the user has edited the file, I somehow hope that the hash won't match any more, because otherwise I would display wrong bookmarks.

I'd be ok with a ~80% chance of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?


texts: Applying a 1x1 convolution on an existing layer

texts:
I am looking at the following github. In this, layer3 has a shape of (1, 20, 72, 256) and I interpret this is as a single layer having 20 input nodes and mapping to 72 output nodes and there are $256$ filters, so the depth is $256$. Then, after applying a 1x1 convolution to this, the new shape becomes (1, 20, 72, 2). I don't quite understand how this comes about.

Is it because there are only 2 classes in the model, so it only needs a depth of two at all points? I keep stumbling over the code and can't get anywhere.


texts: Is the knapsack problem NP-hard when $v_i=i$?

texts:
The knapsack problem is NP-hard and can be formulated as:
$$\begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

What if $v_i=i$? Is it still NP-hard?

$$\begin{align}&\text{maximize } \sum_{i=1}^n ix_i,\tag{P2}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

I am trying to reduce (P1) to (P2). Given an instance of (P1), I create the same number of items, same weights. Now, I have to relate the solutions to (P1) and (P2).


texts: Hamming error correction with non-uniform error correction capability

texts:
If I understood correctly, Hamming codes assume the uniform correction among all the bits. This means all the bits have the same weight in terms of correction.

Are there any error correcting codes out there that assume non-uniform error correction probability among the bits? For example, I want a error correcting code that corrects the first bit all the time, but it is fine to correct the second bit 90% of the time.


texts: Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree

texts:
I have homework from recursion tree and despite my search for hours I could not find the answer to this problem.

I appreciate if you can help.

  Draw a recursion tree and give a tight asymptotic bound on the solution of the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$. You need not prove your answer.


texts: How to prove every well-balanced orientation of an Eulerian graph is Eulerian?

texts:
I'm trying to prove that every well-balanced orientation of an Eulerian graph is Eulerian.

I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide, that is

$\qquad \displaystyle P_D'(u,v)=P_D'(v,u)$

for every well-balanced orientation of an Eulerian graph. How can I do this?


texts: How to compare two objects for percentage of equivalence

texts:
I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find users with similar interests in songs, and I suggest them new songs based on that.

Each user profile basically looks like this

userID: [the userid of the user]
songs: [the list of songs that the user has rated]
ratings: [the corresponding ratings each user gave to the song]

Each song is represented by a 9 digit whole number and each rating is a whole number from 1 to 6. Basically put, I have to compare one user to the rest of the users to determine which of them match this user the best. By match, I mean gave the same songs similar ratings. To do this, I created a simple algorithm.

Step 1) Create a list, in which each entry maps our target user to each of the other
        users.
Step 2) Now consider each entry, determine which songs both of the users have rated, and
        store those songs (along with the corresponding ratings each user gave them) in
        this entry itself
Step 3) Now iterate through each entry and perform the following operations

        a) let percentage = 0
        b) let num = [the number of songs that both users rated]
        c) iterate through each song (that both the users rated) and perform the
           following operations

                i)    determine the score our target user gave this song and store it in
                      variable a
                ii)   determing the score the other user gave this song and store it in
                      variable b
                iii)  map a and b to new values based on this
                        1 --> -3
                        2 --> -2
                        3 --> -1
                        4 -->  1
                        5 -->  2
                        6 -->  3
                iv)   now calculate sum as
                    sum = |a| + |b|
                    where || is the absolute values
                v)    now calculate degree as
                    degree = sum/2
                vi)   now if a * b is less than 0 then
                            calculate (percentage - degree) and store that value
                            again in percentage
                          if not then
                            calculate (percentage - degree) and store that value
                            again in percentage

        d) now  calculate (50 + (percentage / (6*num))*100) and store that value
           in this entry as match

Step 4) Now that I have my list of entries (along with the match between each pair
        of target user and other user) I sort the list in descending order of match
        and from that, I can determine which users have the closest match in taste by
        selecting from the first entries

Now for each user pair, I am completely neglecting the songs that one user rated and the other didn't, and that is okay for me.

There are several problems with this method though, the biggest one being that this algorithm is very time consuming for a large set of users (say around 1,000,000). And also that I have to load in all the users, every time I need to find a set of matching users for just 1 user. And I need to do this repeatedly for that user, to update his/her list.

Is there a way to make this more efficient? Can I assign a value to each user that takes into account all the songs that they rated, and use that number to compare the users? Is that even possible? I guess what I'm asking is, how can I compare and contrast this data, mathematically, to find similar users, efficiently. Also, can someone suggest a proper tag for this type of question?

EDIT

D.W. has suggested a solution, but how do I implement it? Can you provide more detail?


texts: Leader election in synchronous ring with unreliable communication channels

texts:
As a part of my Distributed Systems course I am required to provide an algorithm that is able to elect a leader in a synchronous bidirectional ring, where every message that is sent may be lost (lets say with a probability p).
Furthermore, every node/process only knows its own ID, not the ring size nor its neighbors.

I have found that is problem is unsolvable in asynchronous rings:

  Theorem A. There is no distributed algorithm for electing a leader in a ring, when the only local input in processor P~ is its identity (IDi).

Electing a leader in a ring with link failures, Goldreich, O. & Shrira, L. Acta Informatica (1987) 24: 79. https://doi.org/10.1007/BF00290707

Is it possible in synchronous rings? If not, may he want a Randomized algorithm as solution?

I was thinking to implement a modification of HS algorithm where every message needs an ACK reply, and it's being resent until an ACK arrives. But I think that this would result in some processes to proceed to the next phase whereas other processes are still waiting for an ACK reply.


texts: How to generate a list of all graphs with maximum degree D and diameter smaller than P?

texts: I'm looking for a clever algorithm to generate a list of all possible graphs with maximum degree D and diameter at most P such that any two graphs of this list are not isomorphic. Any ideas ?


texts: In database query theory, why do we not want to use a constant that isn't in the dictionary?

texts:
A badly explained textbook example asks the following:
Suppose we have a definition of the dictionary our database will use (that is, it's relations and constants), defined as:
$<R_\le (?, ?), R_+(?,?,?), R_*(?, ?, ?), c_0, c_1>$
where $R_{operation}$ defines the nature of the relationship of the values inside (represented as question marks), and $c_{value}$ represents a constant. For example, $R_+(a, b, c)$ means that $a + b = c$.
If we build a database structure using our dictionary over the real numbers with constants defined as $1, 0$ we have
$<\mathbb{R}, r_\le, r_+, r_*, 1, 0> $
The questions asks:
Write a query that will return all the points on the graph between the lines

$y = x$
$x = 2$
$y = 0$

ANSWER
The answer given is:
$R_\le(y,x) \wedge R_\le(c_0,y) \wedge ∃a(R_+(c_1,c_1,a) \wedge R_\le(x,a))$
What's not explained however, is why the last constraint is so long? Instead of writing $∃a(R_+(c_1,c_1,a) \wedge R_\le(x,a))$, why don't we just say $R_\le (x, 2)$?
What benefits are we getting by doing it this roudabout way?
I understand it has something to do with only using our constants, but 2 is in our domain, why can't we use it?
Please explain, thank you so much.


texts: Algorithm for finding single input/output sub graphs

texts:
I'm running into an interesting directed acyclic graph (DAG) problem and was wondering if this is a known problem and if it has an efficient algorithm for it. I will use 'graph' and 'DAG' interchangeably

Problem statement:

Find all subgraphs of a DAG that can be defined by two nodes 'Input' and 'Output'. All vertices must be reachable from 'Input' and all these vertices must be able to reach 'Output' in order to be a valid subgraph. Only 'Input' may have incoming edges from outside the subgraph and only 'Output' may have edges to vertices not in the subgraph. The 'Input' and 'Output' vertices may be the same vertex. Let's call this kind of subgraph a 'contractible subgraph'

I'm only interested in the contractible subgraphs which are not included in another contractible subgraph.
As an example we can see in the following graph the following contractible subgraphs which satisfy the property.

The contractible subgraphs:
{9, 10}, {11}, {12}, {13}, {0, 1, 2, 3, 4, 5, 6, 7, 8}.

The 'Input' and 'Output' vertices respectively:{9, 10}, {11, 11}, {12, 12}, {13, 13}, {8, 0}

Solution approach:

One can conceptually think of the subgraph being able to be collapsed into a single new vertex where its outgoing edges are the ones of the 'Output' vertex and its incoming edges are the ones of the 'Input' vertex.

I was thinking of some divide and conquer algorithm where you can merge two vertices if the 'Input' vertex has one outgoing edge and the 'Output' node has a single incoming edge coming from the 'Input' vertex. This rule alone is however not enough.

A naïve solution:
Two vertices form a contractible subgraph iff:

(descendants(Output) - descendants(Input)) U {Input} == (ancestors(Input) - ancestors(Output)) U {Output}

Any ideas, some more observations? Is this a known problem?

Edit:

Specified that the 'Input' and 'Output' vertices may be the same vertex
Specified that the graph is a DAG
Removed incorrect Big-O notation for naïve solution


texts: Is the language "untyped arithmetic expressions" in Types and Programming Languages not Turing complete?

texts:
In Types and Programming Languages by Pierce, is it correct that

the language introduced in Chapter 3 Untyped Arithmetic Expressions is not Turing complete? Because it doesn't provide recursion.

the language introduced in Chapter 5 Untyped Lambda Calculus is  Turing complete? Because it provides recursion.

Thanks.


texts: Generating all words of length n in a CFG

texts:
Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$?

Preferably efficient in time, and with low memory usage.

I'm only interested in the words themselves - not their derivations. If the language is ambiguous and has multiple derivations for a word it would be nice if there is an efficient way to make sure each word is only output once.

The order of the words is irrelevant. If time can be saved by preprocessing the grammar $G$ (e.g. to CNF) then that's perfectly fine.


texts: showing that the pair of Finite Automata are equivalent

texts:
Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have.

These are pairs of FA's. Set theory formula in here is (L1' + L2)' + (L2' + L2)'

Conclusion:

  Both machines (FA1'+FA2)' and (FA2+FA1)' has no final states.
  (FA1'+FA2)' to have a final state, the machine (FA1'+FA2)' must have
  no final state. The exact same thing half of the formula. Clearly, if
  we added these machines together we would get a machine with nine
  state and no final state. Because there is no final state, it accepts
  no words and two languages L1 and L2 ar equivalent.

  So the two regular expressions defame the same language and
  equivalent.

Am I in the right direction ?


texts:
Suppose I have a number of airports which have a set number of routes. Large airports have 7, medium airports have 4, and small airports have 1.

First of all, what would I call a graph of this type where it is undirected, has no parallel edges, no loops, and every edge is connected to another (that is no route goes unused)?

Second of all, how can I determine if I get a number number of airports if it'll work / is connected? Example: 1 large, 3 medium, and 7 small will produce a connected graph but that same combination with 8 small will not.

I'm writing a computer program and looking for a simple way to determine (using some theorem or whatnot) if it works or not. I've attached an image below of what I'm searching for.


texts: Why is $A_{TM}$ reducible to $HALT_{TM}$?

texts:
In Sipser, there is a proof I don't understand.

First he established the undecidability of $A_\mathrm{TM}$, the problem of determining
whether a Turing machine accepts a given input.

$$A_\mathrm{TM}=\left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ accepts }w\right\}\,.$$

Then defined $\mathrm{HALT_{TM}} = \left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ halts on input }w\right\}$, he assume that $\mathrm{HALT_{TM}}$ is decidable and use that assumption to show that $A_\mathrm{TM}$ is decidable, contradicting.

He assume that we have a TM $R$ that decides $\mathrm{HALT_{TM}}$. Then he uses $R$ to
construct $S$:

$S$ = "On input $\left \langle M,w \right \rangle$, an encoding of a TM $M$ and a string $w$:

Run TM $R$ on input $\left \langle M,w \right \rangle$.
If $R$ rejects, reject
If $R$ accepts, simulate $M$ on $w$ until it halts.
If $M$ has accepted, accept; if $M$ has rejected, reject."

He says "Clearly, if $R$ decides $\mathrm{HALT_{TM}}$, then $S$ decides $A_\mathrm{TM}$. Because $A_\mathrm{TM}$is undecidable,
$\mathrm{HALT_{TM}}$ also must be undecidable."

I don't understand why is so obvious the problem is $R$. I mean, I don't understand why if $R$ exists, then inevitably we can simulate $M$.  We know that the step number 4 is not possible because $H(\left \langle M,w \right \rangle)$ = "accept if $M$ accepts $w$ OR reject if $M$ rejects $w$" is not possible, so why is $R$ guilty?


texts:
In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here however, it is stated that:

  A short quantum is good because it allows many processes to circulate through the processor quickly, each getting a brief chance to run. This way, highly interactive jobs that usually do not use up their quantum will not have to wait as long before they get the CPU again, hence improving interactive performance.

That's basically the exact opposite to what's stated in the book. So my question is should the quanta for input/output intensive processes and computing intensive processes be high or low and why?


texts: How can I calculate the effective bandwidth of a memory system?

texts:
I am currently doing my homework for my Computer Architecture class. One of the questions asks:

  A computer has a 64-bit data bus and 64-bit-wide memory blocks. The memory devices have an access time of 35 ns. A clock running at 200 MHz controls the computer and all operations take an integral (i.e. whole number) of clock cycles. What is the effective bandwidth of the memory system?

The problem is, there's pretty much nothing in my textbook that explains how to figure this out. Searching online doesn't return much help either. I'm not asking anybody to answer the actual homework question for me, but if you could explain to me how to figure it out, or point me in the right direction I'd really appreciate it!


texts: How to cover given entries in a matrix with minimum number of rows and columns?

texts:
We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.

example

0 0 1 0

0 1 0 1

0 0 1 0

0 0 1 0

cover 3rd column and 2nd raw. so two plates.


texts: Huffman tree generation if the frequency is same for all words

texts:
Can a valid Huffman tree be generated if the frequency of words is same for all of them?

Example :

Value     | Frequency
--------------------
Google    | 2
Yahoo     | 2
Microsoft | 2
Amazon    | 2


texts:
Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.

Proof:

Let $d:=VC_{dim}(C)$, then there exists $S\subseteq X$, $|S|=d$, s.t. $S$ is shattered by $C$.

Let $d':=VC_{dim}(\bar{C})$, then there exists $S'\subseteq X$, $|S'|=d'$, s.t. $S'$ is shattered by $C$.

Show that $d\leq d'$ and $d' \leq d$. I know that a set $S$ is shattered by $C$ iff $\Pi_C(S):=\{c\cap S\mid c\in C\}=2^S$, but I have no clue how to show the two sides. Can someone help me with that?


texts: How to understand a equation related to speaker recognition?

texts:
This question refers to the following paper:

Support Vector Machines for Speaker and Language Recognition, W. M. Campbell, J. P. Campbell, D. A. Reynolds, E. Singer, P. A. Torres-Carrasquillo, Computer speech and Language 20 (2006) 210-229.

I am trying to implement the algorithm in table 1 and table 2 in page 18. In step 6 of of table 1 they are calculating $b_z^i$ as a mean (or sum) of $b(z_i)$ and number of entries is $N_z$ which they claim to be the number of features.

The question is what is $N_z$ here. As I understand each feature set, which is of dimension $N_z$, has been used to create $b(z_i)$, so what this summation means? One can only sum over time dimension, which has nothing to do $N_z$. $N_z$ is kind of spatial dimension as one time frame of data is converted to features.


texts:
$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$.

We do not know if either $NP$ or $P/poly$ is in $ACC^0$.

Suppose every problem in $NP$ can be solved in polynomial time with polynomial sized advice string (that is $NP\subseteq P/poly$ holds) however the circuit that computes it needs only $ACC^0$ type structure?

Would that mean $NP$ is in non-uniform $ACC^0$ or uniform $ACC^0$?


texts: Is there a non-trivial type which is equal to its own derivative?

texts:
An article called The Derivative of a Regular Type is its Type of One-Hole Contexts shows that the "zipper" of a type—its one hole contexts—follow the differentiation rules in type algebra.

We have:

\begin{align}
\partial_x x &\mapsto 1 \\
\partial_x 0 &\mapsto 0 \\
\partial_x 1 &\mapsto 0 \\
\partial_x (S + T) &\mapsto \partial_x S + \partial_x T \\
\partial_x (S\times T) &\mapsto \partial_xS \times T + S \times \partial_x T
\end{align}

We can use this model to derive that the derivative of unit is void, that the derivative of list is a product of two lists (prefix times suffix), and so on.

A natural question to ask is, "what type is its own derivative?" Of course we already have $\partial_x 0 \mapsto 0$, which tells us that void (the uninhabited type) is its own derivative, but that is not very interesting. It is the analog of the fact that the derivative of zero is zero in the ordinary infinitesimal calculus.

Are there other solutions to the equation $\partial_x T \mapsto T$? In particular, is there an analog of $\partial_x e^x = e^x$ in type algebra? Why or why not?


texts: Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3

texts:
I want to detect the non existence of a cycle in a graph using Datalog (which is  a declarative logic programming language).

The proposed solution was:

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)) P-1)
(rule (=> (and (path a b) (path b c)) (path a c)) P-2)

(rule (edge 1 2) E-1)
(rule (edge 2 3) E-2)
(rule (edge 3 1) E-3)

(declare-rel cycle (s))
(rule (=> (path a a) (cycle a)))
(query cycle :print-answer true)

But my question is how can i get SAT when there is no cycle in the graph and UNSAT when there exists a cycle.

One suggestion (but that does not meet my need) is:

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert (not (path a a)))

(check-sat)
(get-model)

which returns as result:

> z3 test.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

I don't understand why z3 assign 0 to the variables while I only have 1, 2 and 3 as vertices?

Another suggestion was :

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert
         (=> (path a a)
            false
            )

 )

(check-sat)
(get-model)

Which returns the result:

> z3 test2.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

Any idea to resolve this problem?

Note: I need to use Datalog for reasons of complexity.


texts: String searching, where we allow characters to almost-match

texts:
Let $\Sigma= \{1,...,n\}$.  Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively.  I am looking for an algorithm to test whether $Q$ appears as a substring of $T$, except that I have a more relaxed notion of when two characters match.

Two characters in these strings are similar if $|Q[j] - T[l]|\leq 1$. Call the indices $i,j$  a good pair if $|Q[j] - T[j+i-1]|\leq 1$, that is if the characters in the $j+i-1$'s cell in $T$ and the $j$'s cell in $Q$ are similar. An index $i$ is good for all if for all $1\leq j \leq k$, the pair $i,j$ is a good pair.

I'd like to find all the good-for-all indices. That is,
I aim to find all the indices $1\leq i\leq n$ s.t. for all $1\leq j \leq k$, we have $|Q[j] - T[j+(i-1)]|\leq 1$.

I'm at a loss even where should I begin from. Obviously I can solve naively, but this is not interesting at all. I'm not even sure what should be the optimal time for this problem. Also, I don't see any lower bound on the running time (except $O(n)$ obviously).

How efficiently can we find all the good-for-all indices?  What algorithm can I use for this?


texts: Finding the best state for chain graph with cycles

texts:
I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative). Each node is connected to m previous ones. The internode weight is shown as edge and node weight as node itself. Is there an algorithm for finding labels, that result in the largest total sum of weights of the graph?

Here is a more formal description by @j_random_hacker:
For each vertex $v$ there is a set of possible states $S_v$ and a function $f_v:S_v \to \mathbb{N}$, and for each pair of vertices $u,v$ that are connected by an edge there is a function $g_{uv}:S_u \times S_v \to \mathbb{N}$, and we want to choose a state from $S_v$ for each vertex $v$ such that the sum of all these functions is maximised.  In other words, we want to choose a function $h:V \to V$ such that $h(v) \in S_v$ for each $v$, and that maximizes $\sum_v f_v(h(v)) + \sum_{u,v} g_{uv}(h(u), h(v))$, where the latter sum is over all edges $(u,v)$ in the graph.


texts: When do we need to change the state of a push down automata?

texts:
I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition operation. An explanation would be appreciated. Thanks!

Also, my understanding of states is that they're basically the indicators in the machine, which let it know which operation is going on. Is this the correct analogy? If not, can you give a better one?

Edit: Regarding finite automata, I can understand when to change the state. But I'm confused in push down automata. Do you change the state only during push and pop, and during introduction of a new character? Or are there more reasons to change the state?


texts: Why ambiguous grammars are allowed for operator precedence parser?

texts:
I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of operations like a-b-c now if we operate it with two different parse trees, say one like (a-b)-c and other like a-(b-c)
there meaning changes..
So how can we allow ambiguous grammar in operator precedence parser? shouldn't it be the opposite?


texts: Some slight confusion with the UNTIL operator in CTL (e.g. a U b)

texts:
I've sketched a very small transition system in paint that I'll use as an example.

I want to see if $A(aUb)$ holds for this transition system. From my understanding, this CTL formula is asking if ALL paths satisfy $aUb$. The only path we can take in this example is S0S1S0S1S0S1S0S1...

This path produces the output (1) $aaaaaaaaaaaaaaaaa...$ or (2) $aaaaaaaaaaaaaaab...$

(2) definitely holds - however it's (1) that I'm unsure about. Am I correct in saying that $aUb$ doesn't hold for (1)? Since we can continue looping over a infinitely without eventually reaching b (and because (1) doesn't satisfy the formula, $A(aUb)$  doesn't hold for this transition system).

Have I understood this correctly? I guess the main confusion for me is that there is 1 path but more than 1 possible output.

Any help is much appreciated.

edit: This is the transition system I'm referring to in the comments below


texts: How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages

texts:
I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L} = \{ \overline{L} \mid L \in \mathcal{L} \}$$

and where $\overline{L}$ is the complement. From what I read in an earlier part of my textbook, the complement of $L$ is equal to $\Sigma^* - L$.

However, say that $\mathcal{L}$ is NP. An instance of a language $L$ that is in $\mathcal{L}$ is the set of graphs with Hamiltonian paths. However, in this case, its complement $\bar{L} \in$co-$\mathcal{L}$ is the set of graphs without Hamiltonian paths, i.e. $\bar{L} \in $co-NP.

But is the set of graphs without Hamiltonian paths equal to $\Sigma^* - L$ (following the definition of complement) ? In this case, we would be including some strings $\in \Sigma^* - L$ that do not represent graphs.

Another example is $A_{TM}$, which represents the language

$$\{\langle M,w\rangle \mid M \text{ accepts input }  w \}$$

In this case, does $\overline{A_{TM}}$ represent $\Sigma^* - A_{TM}$?. If this is the case, we would be including in $\overline{A_{TM}}$ several strings that do not represent TM's, or that refer to other input that is not equal to $w$. Or rather, does $\overline{A_{TM}}$ represent the language

$$\{\langle M,w \rangle \mid M \text{ diverges on input }  w \}$$


texts: What is a "name/variable of base type" in applied $\pi$-calculus?

texts:
I'm studying the articleVerifying privacy-type properties of
electronic voting protocols which uses Applied $\pi$-calculus to formalize voting protocols and verifies some privacy-related properties.

In certain parts of the paper they define some transformations over processes which are defined inductively. For example:

  Definition (Process $P^{ch}$) Let $P$ be a plain process and $ch$ a channel name. We define $P^{ch}$ as follows:

  $0^{ch} \equiv 0$
  $(P|Q)^{ch} \equiv P^{ch} \equiv Q^{ch}$
  $(\nu n.P)^{ch} \equiv \nu n.out(ch, n).P^{ch}$ when $n$ is name of base type
  $(\nu n.P)^{ch} \equiv \nu n.P^{ch}$ otherwise
  $\ldots$

The idea is that they want to model a voter, which is a process, that wants to provide information about how he voted to the attacker (think: guy $X$ buys the vote of $Y$ and wants a "receipt" to be sure that $Y$ voted how he wanted).  What I don't understand exactly is when is that $n$ a "name of base type"?

I've read the article Mobile Values, New Names, and Secure Communication where Applied $\pi$-calculus was first defined but here they just say that they assume that terms have some kind of type-system behind the scenes and the only thing they say is that the type system must include the type $\texttt{Channel}\langle \tau\rangle$ for every type $\tau$.

So, does the condition "when $n$ is name of base type" simply means "$n$ is not the name of a channel"? This would make sense, because in formalizing these protocols it is assumed that there exists some private channels between voter and authorities that the attacker can not eavesdrop due to physical limitations (they represent the voting booth).


texts: How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

texts:
Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular language using the pumping lemma?

I cannot seem to find any sort of pattern for ternary representations of $S$, and so I'm finding it really difficult to prove this using the pumping lemma.

I tried to make a few strings in $L$ and got $\{1, 11, 22, 121, 1012, 2101, \dots\}$ but cannot find any sort of pattern that leads to using the pumping lemma. So, how would you prove that this is not a regular language using the pumping lmma? Thanks in advance.


texts: How to minimize this DFA with already merged states?

texts:
The original nondeterministic FSA I have is:

After converting this to a DFA I get:

If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I think this is incorrect.

I want to minimize this DFA. How should I do this using the Myhill-Nerode theorem, since some of the states are merged already?


texts:
There is $n$ lists (of integers) of the same length.
I want to find the zeros global intersections of those lists.

Example:

$A = [4,6,3,0,7,0,0,0,1,0,0]$

$B = [6,6,7,1,7,0,0,0,4,0,0]$

$C = [2,4,7,0,7,0,0,0,3,0,0]$

The output are the position of those intersections:

The positions are $5, 6, 7, 9$ and $10$

Other than "traversing" the list and checking element by element, is there another way ?


texts: The importance of normal forms like Chomsky normal form for CFGs

texts:
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't understand the need of that.

Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.


texts:
The Subset Exercise taken from LeetCode:

Example: For Input nums = [1,2,3] Return Output:
    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

has as backtrack solution:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

The solution has been taken here.
I would like to know what the time and space complexities of this solution are. Apparently, the time complexity is O(N * 2^n). The N come from the tempList.add() operation, I have a problem understanding where the 2^N come from.


texts: Computing Every Path from a Source to Multiple Destinations [Simpler Algorithm]

texts:
How are these two problems different?

  I. Find all paths between a source vertex and destination vertex.
  II. Find all paths between a source vertex and all vertices in the
  graph.

Both of these problems are NP-hard. We would naturally assume (II.) takes longer.

However, I believe we can use a flavor of (II.) to solve (I.) in relatively equal amounts of time.
In other words, can we reduce (I.) to (II.) doing the following:

We are asked to find all paths from a source to a destination vertex. We can trivially use (II.) to solve this problem by augmenting the graph in linear time. We remove all vertices that are NOT decedents of the source and NOT ancestors of the destination in O(|E| + |V|). Then we run our algorithm for (II.) on the augmented graph. Since our graph has been refined down the only the relevant vertices, the returned value for (II.) and (I.) are the same and have been computed in nearly the same amount of time. Am I correct in my thinking?

Why is this relevant? Let's say you have asked to compute every possible path between one source and multiple destinations[0...n]. How do we reduce pointlessly re-computing things? For example, destination[1] could be an ancestor of destination[0]. A naive algorithm would re-compute every path possible path to destination[1] and destination[0]. A smarter solution would use the results from destination[1] to compute destination[0] faster. That solution essentially uses dynamic programming based on the following property:

  Property: If you find every possible path from some source to some destination, we would also would have every possible path from the source to any of the vertices that are ancestors of the target.

My solution is using the reduction from before. My solution does not need to use the above property. I believe my solution would run as efficiently as a dynamic programming solution, but be simpler to implement. Still NP-hard of course. Does this sound reasonable?


texts: How to select topology for neural network?

texts:
I was given a target function to design a neural network and train: $y = (x_1 \wedge x_2) \vee (x_3 \wedge x_4)$

The number of inputs and outputs seems obvious (4 and 1). And the training data can use a truth table.

However, in order to train it as a multilayer artificial neural network, I need to choose the number of hidden units. May I know where can I find some general guideline for this?

Thank you!


texts:
I read

  FP = FNP iff P = NP

which makes sense.

But if P = NP, does it mean FNP = NP?

Intuitively, I think no because P = NP would mean that decision problems in NP would become decision problems in P. But I don't see how that would reduce search problems to decision problems.


texts: How to place the deadlines in “Earliest deadline first scheduling” in this question?

texts: So I followed this tutorial to get the concept of "Earliest deadline first scheduling". I have to implement this task >>> TASK. Now the thing which I am not getting in this Task is that what does "Start of next period" means in the deadline column. Still, I have implemented it >>> Here. I placed the deadlines with a RED downward arrow while the blue upward arrows meant the periods of the respected processes. But again I am not sure whether my approach was correct in understanding the "Start of next period" because it could also mean the start of every period. Once I am sure that I have placed the deadlines correctly, then I will solve the question.


texts: Multiplying intervals in Two's complement

texts:
I want to perform some interval-operations, and for addition, subtraction, and logic-/shift-operators, that works very well.

The only problem I have is the multiplication.

An interval $[a, b]$ denotes all two's complement numbers $x$ with the property $a \leq x \leq b$.

An interval-operation means that if i have a binary operation $\circ$ and two intervals $[a, b]$ and $[c, d]$, then $[a, b] \circ [c, d] = [e, f]$ means that for for an arbitrary $x \in [a, b]$ and $y \in [c, d]$: $$x \circ y \in [e, f].$$

But additionally, I want to have the most precise or a very precise interval.

"The most precise" means that there are the values $w,x \in [a, b]$ and $y,z \in [c, d]$ for which holds that $w \circ y = e$ and $x \circ z = f$

An example of an interval-operation:

$A = [7,14]$
$B = [-6, 77]$
$A + B = [1, 91]$

It's correct, because there is no value outside of $[1, 91]$ that can be reached, when adding numbers out of $A$ and $B$.

Also it's precise, because $7+(-6) = 1$ and $14+77 = 91$

It seems impossible to find an efficient algorithm that handles all the overflows correctly and finds the precise (or at least a good) interval.

Is there a good algorithm?