texts:
There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there exists the same algorithm that would solve the problem on that model (e.g. emulation).

I was wondering, if there's a model of computation, that is equivalent to turing machines (the coding translation being just general bijection), but encoding standard input to its input would be an uncomputable problem. In essence making it an model of computation that is cut off from convetional models by it's coding being uncomputable. That would be first part of my question. I

For the second part, if such model exists, let's call it $S$, can you find other models of computations $S_0, S_1, \dots$, such that conversion between $S$ and $S_i$ would be computable by both $S$ and $S_i$? If $T, T_0, T_1,\dots$ were models of turing machine, and other conventional computation models, would $\mathcal{T}=\{T,T_0,T_1,\dots\}$ and $\mathcal{S}=\{S,S_0,S_1,\dots\}$ be two seperate "islands" of computation? Both equivalent, but no member of either family would be able to encode it's inputs to the other family? Or maybe only $\mathcal{S}$ would be able to, making some sort of partial order on such families of models of computation, like $\mathcal{T}<\mathcal{S}$?

note: I'm not sure if it's formal to talk about a model of computation as a mathematcical object, I meant most of the last paragraph mostly informally, but maybe it would suffice to just take set of all instances of such model of computation. Like $T=\{\text{all Turing machines}\}$, $T_0=\{\text{all Lambda expressions}\}$ and such .


texts:
Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{min}, y_\mathrm{max})$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $O(n^3)$) approximation algorithm that gives a sequence $\{y_0, \ldots, y_{n - 1}\}$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $y_\mathrm{max} = 10$ and $h_k = 3$, then $y_k = 9$ would be invalid, since the top edge would be at $12$ which is more than $10$.


texts: Need recursive version of Conflict based backjumping

texts:
I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?

In AIMA they give the recursive version of backtracking.

function BACKTRACKING-SEARCH(csp)
  return BACKTRACKING({}, csp)

function BACKTRACK(assignment, csp)
  if assignment is complete then return assignment
  var ← SELECT-UNASSIGNED-VARIABLE(csp)
  for each value in ORDER-DOMAIN-VALUES(var, assingment, csp) do
  if value is consistent with assignment then
    add { var = value } to assignment
    inferences ← INFERENCE(csp, var, value)
    if inferences ≠ failure then
      add inferences to assignment
      result ← BACKTRACK(assignment, csp)
      if result ≠ failure then
        return result
  remove { var = value } and inferences from assignment
  return failure

They have said backjumping can be built by a little modification to this algorithm with conflict set but I don't think so.

Backtracking is just a recursive algorithm and it has to use stack stack. But,  in backjumping the stack sequence is trouble in jump. The worse is that java does not support goto statement.

So am i missing here something.
Please advice me how to get backjumping by modification of backtracking as shown in figure.


texts: Traveling salesman problem with limited distance

texts:
I have a problem which is basically TSP where is a limit on how far youcan go and every city has a profit.

I need to make algorithm where he could come back with highest profit after a trip. It's not important how many cities he will visit as only profit is important.

I need to the solution in code so it has to be practical and not necasirly the complete best solution, which means some approximations/shortcuts to save calculation time is also good.


texts: How do I sort these elements in O(n) time?

texts:
So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix sort. The run time of radix sort is O(d(n+N)) or O(dn) if n is really large. So how can I modify radix sort so that it runs in O(n)?

EDIT:
I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array.


texts: Find longest path by number of edges, excluding cycles

texts:
I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there's better terminology, then please let me know about this.

It's important that I'm able to determine what the path is, so I would need an algorithm that can produce a list of edges.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance


texts: Polynomial time algorithm - Matching pairs of vertices

texts:
Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. The following figure shows an example in which S consists of the six vertices enclosed in circles and three paths (denoted by three different types of dotted lines) that match those vertices.

Hint: Gain intuition by making instances like the one in the figure and observing what happens when you walk the entire border of the tree almost touching it, but not really doing that; then think about how to express the idea of such walk with a recursive algorithm.

I tried to analyze the problem but I don't really understand how to express it as a recursive algorithm, could you help me, please?


texts: Understanding the Sipser-Gacs-Lautemann theorem

texts:
The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input.

The class $\Sigma^p_2$ contains all the languages for which there is a polinomial time Turing machine $M$ and a plynomial function $q : \mathbb{N} \rightarrow \mathbb{N}$ such that:
$$ x \in L \iff \exists u \in \{0,1\}^{q(|x|)} \forall v \in \{ 0,1 \}^{q(|x|)} M(u,x,v)=1$$
Define $\Pi^p_i=\{\bar{L} : L \in \Sigma^p_2 \}$

The theorem states that the class $BPP$ is contained by the intersection of $\Sigma^p_2$ and $\Pi^p_2$.

To prove the theorem it is proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \leq 2^{m-n}$ and every k vectors $u_1, \ldots, u_k$
$$\bigcup_{i=1}^k(S+u_i) \neq \{0,1\}^m$$
Where $S+u = \{ x+u : x \in S \}$ and + denotes addition modulo 2 i.e. bitwise XOR.

It is also proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \geq (1-2^{-n})2^m$ and every k vectors $u_1, \ldots, u_k$
$$\bigcup_{i=1}^k(S+u_i) = \{0,1\}^m$$

I don't get why this claims imply that if a language is in $BPP$, then
$$ \exists u_1, \ldots,u_k \in \{ 0,1 \}^m \forall r \in \{ 0,1 \}^m \bigvee_{i=1}^k M(x,r \oplus u_i) = 1 $$

How does the claims about sets of binary strings imply the computation above?

What I don't understand is how the translations preserve the original random strings and how can a small set of translates cover all possible random strings.


texts: Does making the keys of a hashtable the same length make the hashtable any better?

texts: The question popped up in my head. The hash function used is Murmur3.


texts:
http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

I'm confused as to the solution for the snowball question. To start with, I have two specific questions:

(1) Each pair $a_i,b_j$ will account for one term (and why ONE term)? What is meant by term here? The coefficient, $c_k$ of the polynomial C? Or maybe the $x$ value at the $kth$ spot?

(2) Why is $c_k$ the number of such pairs?


texts: In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity?

texts: It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the multiplicative constant?


texts:
I have a directed graph which has edges between every vertices $i$ and $j$ such
that $i < j$ and the edge is from i->j and every vertex needs to be visited.  I need to divide the graph into two parts such that the
travel distance on both the parts i.e. sum of edge weights while traveling from the lowest index to the highest index in each of the group is minimum.  For example there is a graph
of 4 vertices where each edge weight is the following

$w(1, 3) = 2$
$w(1, 4) = 1$
$w(3, 4) = 3$
$w(1, 2) = 100$
$w(2, 3) = 100$
$w(2, 4) = 100$

The solution would be $\{2\}, \{1, 3, 4\}$. In the first group {2} doesn't have any vertex so no edges between any of the vertices in that group. In the second group we travel from 1->3 and 3->4 so the edges we travelled would be 2 + 3. Hence the ans would be 0 (from the first group) + (2+3) (from the second group). We start from the lowest index vertex and move to the highest index vertex as the edges are from lower index to higher index vertex.
The algorithm I came up was a brute force i.e. considering each
combination and return the minimum of it i.e. to take one vertex in one
group or include in other which leads to complexity $O(2^n)$.
I want to get the above problem to run in $O(n^2)$ solution.  I did draw
a decision tree for the above problem and can see nodes being overlapped
i.e. $\{1,2\}, \{3,4\}$ and $\{3,4\}, \{1,2\}$ so I figured this is a
dynamic programming problem but I am not able to define the states.
Edit - It can be done using a 1d dp array


texts: Are these examples of unification problems?

texts:
I have been studying unification, especially nominal unification (paper) gets my attention.
I read the theory and examples. But I am wondering that what kind of problems occur in unifications.
For examples, The following examples are from nominal unification paper. (I write distinct bound variables, so easier to see the solutions )

(1) $\lambda a. \lambda b. (X  \, b) = \lambda c. \lambda d. (d \,X) $

(2) $\lambda a. \lambda b. (X \, b) = \lambda c. \lambda d. (d \, Y) $

(3) $\lambda a. \lambda b. (b  \, X) = \lambda c. \lambda d. (d \, Y) $

I observed that each variable ($X$ or $Y$) occurs only once on one side of equations.
Should it be always that way?
Can I write the following

(4) $\lambda a. \lambda b. (X  \, X) = \lambda c. \lambda d. (d \,X) $

(5) $\lambda a. \lambda b. (Y  \, X) = \lambda c. \lambda d. (d \,X) $

(6) $\lambda a. \lambda b. (X  \, X) = \lambda c. \lambda d. (X \,X) $

and are these possible unification problems?

I read many sources, but and all presented unification problems with variables only have once occurrences on one side of equations.
I tried to find more examples, but could not find anything different.

I know the unification problems arise from logic programming. And so far, I did not see any logic programs which puts $X$ twice in a term.

Anyway, hoping someone to clarify these points.

Thanks in advance!


texts: How to prove that a language $A$ is decidable?

texts:
How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering.

Word length alphabetically means a sorting first after the word length and then after the character ordering $(\epsilon,a,b,aa,ab,ba,bb, ...)$.

Hope somebody can help me like give a hint or an approach.


texts:
I have been recently studying Lie theory. I discovered that there is a family of Lie theoretic error correcting codes. I did not find any information except this paper:

“Representations of Lie Algebras and Coding Theory“ by Xiaoping Xu

So, my question is: why isn't there a further development of this research? Are these codes considered inefficient or impractical?


texts: Calculating Contiguous String Kernel efficiently

texts:
I am given two strings, $\overline{a},\overline{b}$ in a finite alphabet, $\Sigma$, and a positive integer $k$.   I want to compute the $k$-th order contiguous string kernel, which is defined to be the sum $$\sum_{s\in\Sigma^k}n_s(\overline{a})n_s(\overline{b})$$ where $n_s(x)$ is equal to the number of occurrences of $s$ as a substring of $x$.  I am trying to come up with an $O(k\ell_a\ell_b)$ algorithm for this, where $\ell_a,\ell_b$ are the lengths of $\overline{a},\overline{b}$, respectively.

I think the algorithm uses the fact that the substring must be present in both strings in order to actually affect the sum but I am unsure where to go from there in order to get such an algorithm. Any help or references to related sources would be greatly appreciated!


texts: All pairwise shortest paths in a graph: does knowing the path weights help?

texts:
This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we want to get the lowest-weight path from every starting vertex $i$ to every ending vertex $j$),

The "Path reconstruction" subsection of the Wikipedia article on the Floyd-Warshall algorithm, claims:

  Floyd–Warshall algorithm typically only provides the lengths of the
  paths between all pairs of vertices. With simple modifications, it is
  possible to create a method to reconstruct the actual path between any
  two endpoint vertices. While one may be inclined to store the actual
  path from each vertex to each other vertex, this is not necessary, and
  in fact, is very costly in terms of memory. Instead, the Shortest-path
  tree can be calculated for each node in Θ(|E|) time using Θ(|V|)
  memory to store each tree which allows us to efficiently reconstruct a
  path from any two connected vertices.

In general (not simply on the FloydWarshall algorithm), if we were given the optimal path distances (i.e., the distances of the most efficient routes) between every starting vertex $i$ and every ending vertex $j$, but not given the paths themselves, is this of any help to finding the best paths? I can think of trivial uses (like branch and bound to discard any paths that exceed the provided optimal path length), but am curious if there are other uses for the minimal distances.

Do you know if starting with the minimum final path distances would help find the corresponding paths?


texts: Would adding recursive named functions to Simply typed lambda calculus make it Turing complete?

texts:
Say I have Simply typed lambda calculus, and add an assignment rule:

<identifier> : <type> = <abstraction>

Where <identifier> is the name of the function, <type> is the function type and <abstraction> is the abstraction to be assigned to the identifier.

Then I add a typing rule that says that when you see an assignment such as the above, you use a temporary type context, in which the declared type (the one in <identifier> : <type>) is associated with the identifier, to type check <abstraction> and then make sure the declared type equals the abstraction's type.

And finally I add another rule that would let me have a list of assignments on top of a lambda term which is the one I'd evaluate, such that all these assignments would be added to the global scope before the term is evaluated.

Seems to me that this alone would make it Turing complete since I'd be able to do stuff like:

stackoverflow: NUM -> NUM = λn:NUM.(stackoverflow n)
(stackoverflow 0)

And at the same time, everything I can define in this language would be "well typed" in the sense that it wouldn't be able to define infinite types (I wouldn't be able to define the Y combinator).

So my questions are, is this really Turing complete? And, am I missing something when I say everything would be "well typed" (like for instance, I could define the Y combinator in a way I haven't yet realized or is there any gotcha in this type system)?


texts: Good characterization of unsatisfiable Horn3SAT formula?

texts:
Horn3SAT is $P$-complete problem under logspace reductions. Since Horn3SAT is in $P$ its complement must have short witnesses. I am looking for natural short proof that a Horn3SAT formula is not satisfiable. Examples for similar problems in $P$ are 2-coloring problem and planarity problem. A graph is not 2-colorable if and only if it contains an odd cycle. A graph is not planar if and only if it contains a subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

  Is there a good characterization of Horn3SAT formulas that are not satisfiable? What does constitute a natural short witness for unsatisfiable Horn3SAT formulas?

I am not interested in algorithmic proof such as running an algorithm for deciding Horn3SAT problem. I am only interested in good characterizations similar in spirit to the above two examples.

EDIT: As illustrated by the two examples above, I am only interested in characterizations of the complement set of Horn3SAT in terms of some forbidden structure.


texts: The difference between dynamic logic and temporal logic

texts:
To find the difference, I'd just encountered with assertions below about temporal logic in Wikipedia:

  another variant of modal logic sharing many common features with
  dynamic logic, differs from all of the above-mentioned logics by being
  what Pnueli has characterized as an "endogenous" logic, the others
  being "exogenous" logics. By this Pnueli meant that temporal logic
  assertions are interpreted within a universal behavioral framework in
  which a single global situation changes with the passage of time,
  whereas the assertions of the other logics are made externally to the
  multiple actions about which they speak. The advantage of the
  endogenous approach is that it makes no fundamental assumptions about
  what causes what as the environment changes with time. Instead a
  temporal logic formula can talk about two unrelated parts of a system,
  which because they are unrelated tacitly evolve in parallel. In effect
  ordinary logical conjunction of temporal assertions is the concurrent
  composition operator of temporal logic. The simplicity of this
  approach to concurrency has resulted in temporal logic being the modal
  logic of choice for reasoning about concurrent systems with its
  aspects of synchronization, interference, independence, deadlock,
  livelock, fairness, etc.

I could not realize the difference, considerably. Can't dynamic logic cover every time-driven aspect within arguments, as well as temporal logic?

Or why is dynamic not supposed to handle concurrent systems?

Would you please clear the case?


texts: What is difference between Buffering and Spooling with respect to Operating System

texts:
I have googled a lot to find the answer and found some links like this, this and this and even in a book Understanding Computers Today and Tomorrow (13th edition) couple of paragraphs are written as given below:

  Some input and output devices are exceedingly slow, compared to today’s CPUs. If the CPU had to wait for these slower devices to finish their work, the computer system would experience a horrendous bottleneck. For example, suppose a user sends a 100-page document to the printer. Assuming the printer can output 20 pages per minute, it would take 5 minutes for the document to finish printing. If the CPU had to wait for the print job to be completed before performing other tasks, the computer would be tied up for 5 minutes.
  To avoid this problem, most operating systems use two techniques—buffering and spooling. A buffer is an area in RAM or on the hard drive designated to hold input and output on their way in or out of the system. For instance, a keyboard buffer stores characters as they are entered via the keyboard, and a print buffer stores documents that are waiting to be printed. The process of placing items in a buffer so they can be retrieved by the appropriate device when needed is called spooling. The most common use of buffering and spooling is print spooling. Print spooling allows multiple documents to be sent to the printer at one time and to print, one after the other, in the background while the computer and user are performing other tasks. The documents waiting to be printed are said to be in a print queue, which designates the order the documents will be printed.

but I cannot clearly understand the difference between Buffering and Spooling.

Can anyone explain the difference between them in simple and easily understandable terms.

Also in couple of the links mentioned above, it is written as :

  The main difference between buffering and spooling is that the latter allows the I/O of one job to overlap the computation of another. Buffering only allows the I/O of a job to overlap with its own computation.

so what is meant by overlapping the computation of own or other job?

[I don't know whether this is a proper place to ask this question or not, if not, then kindly tell where should I post this to get the answer]


texts: Method for combining derivative free optimization results of different data inputs

texts:
I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as possible.

What I found, is that when optimizing the parameters for a specific time period, these parameters don't necessarily work well when used on another time period.

The way I see it, is that there are two possible solutions to this problem:

use a longer time period when optimizing the parameters
find a method of combining the optimal parameters for different time periods, such that these "averaged" parameters work well on all time periods

Option 1. would be incredibly expensive in terms of computational time. And although it makes intuitive sense that this should fix the problem, I am not sure that this would indeed be the case.

Option 2. reminds me of training neural networks, where one would feed in a large number of "data points" and somehow take a (weighted) average of the results to find a set of parameters that work well for all data points. Unfortunately, I know very little to nothing about the algorithms used for this kind of optimization/learning.

Any help or suggestions are greatly appreciated. Please let me know if there is anything you'd like me to expand upon.

Thanks!

EDIT:
As suggested in the comments, here is some additional information:

my loss function is not an actual mathematical function, so I don't know exactly what it looks like, this also means that I can't compute the gradient.
The optimization method I currently use is differential evolution using the best1bin strategy.
The reason the predictions fail is because of overfitting.
There are ~10 parameters
One iteration takes about 5-8 seconds


texts: Undecidability and Unrecognizability of Language with two Turing Machines

texts:
I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the statement, and assuming that Language1 is decidable, so that there is a decider D which decides Language1. Then we construct a Turing Machine which produces a contradictory result. However, I'm not sure how to do this! Can anyone help me formalize this? The question is:
Consider the following language called Language1:
Language1 = {(⟨M1⟩, ⟨M2⟩) | L(M1) = {⟨M2⟩} and L(M2) = {⟨M1⟩}} .
i.  Prove that Language1 is undecidable.
ii. Prove that Language1 is unrecognizable.


texts:
How would you evaluate a new metric or benchmark?

My concrete example: I want to benchmark code review. As others did [1, 2] , one can apply metrics from social network analysis (such as centrality, degree, ...) to a social network emerged from code review (who reviewed when whom?).

But how do I evaluate if the metrics I have chosen are any good or meaningful?

My first thoughts were expert interviews. Do you see other opportunities?


texts: How does the number of clause affect the difficulty of a 3-SAT Problem?

texts: It was asked here and closed although it is a very specific question witch was exactly answered in several papers. The complexity of 3-SAT problems has a phase transition which reaches the critical point if the ratio of clauses to variables is 4.25.


texts: enumeration of all Maximal independent set on trees

texts:
what is the algorithm for enumerating  all maximal independent set on trees (without the constaint of  lexicographic order) .
It 's very natural to find an algorithm faster than $ O(3^{n/3})$ on trees .

In fact ,in  trees we have at most $O(2^{n/2})$ maximal independent set but I try to find an algorithm to enumerate those .


texts: Decidability of Turing machines and misconceptions on the halting problem

texts:
In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability only arises when we are talking about a class of a problem.
As a rebuttal to the original argument someone replied that if we have a Turing machine and we give it an input w it'll be undecidable to say will it halt or not and was proven by Turing himself.
Is this a correct argument because skimming through wikipedia it looks that's not what Turing actually proved

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist

What he proved was that no general solution exists for all possible program-input pairs and not that we can't have a specific algorithm to solve this on a single machine (e.g if we take a halting Turing machine a simple solution would be to say yes for all inputs).
In support of my original statement look at the PCP, no general solution exists but if we are given two string we can sure brute-force them by looking at all possible subsequences and tell whether a correspondence exists or not.
So what I am asking here does my original statement hold weight and what exactly did Turing proved.
Edit: I've realized this question doesn't make much sense and is just not useful to anyone. But because it has answers it can't be deleted.


texts: Write a regular expression - Contains an equal number of 01 and 10 subtrings

texts:
I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. Substrings can overlap, so $010$ is in the language but, e.g., $01101$ is not.

I've worked on a DFA where I can move on to create the RE. Here is my DFA:

I'm trying to use Arden's theorem to get the regular expression but I'm  stuck. This is how I'm thinking:

\begin{align*}
a_1 &= 0a_2 + e\\
a_2 &= 0a_3 + 1a_5\\
a_3 &= 0a_3 + 1a_4\\
a_4 &= 0a_3 + 1a_4\\
a_5 &= 0a_6 + 1a_5\\
a_6 &= 0a_6 + 1a_5\,.
\end{align*}
I dont describe $a_7$, the "sink state" because it only results in the empty set.

My problem here is that I will never be able to get describe the language because of how $a_3$, $a_4$ ,$a_5$, $a_6$ are? Where did I go wrong?

After some work, I came to this solution, is it correct?

$$0 + 00(11^*0 + 0)^* + 01(1 + 00^*1)^*00^*$$


texts:
The shortest common cyclic superstring problem is closely related to the shortest common superstring problem. The difference is that each of the strings in the input set may have an arbitrary rotation of the algorithm's choosing applied to them. By rotation I mean that for example abcde -> deabc would be a rotation by 2. Additionally any valid output may have an arbitrary rotation applied to it and it will still be considered valid (I don't think this helps much, though).

The classic greedy approximation algorithm for shortest common superstring runs in $O(m n^3)$ for a set of size $n$ where all the strings have at most length $m$. There are other approximation algorithms that run faster (even as fast as $O(mn \log \sigma)$ for an alphabet of size $\sigma$) but they are more complicated.

One obvious way to solve the shortest common cyclic superstring problem is to modify the greedy algorithm so that it rotates every pair of strings by every rotation. I believe this can result in an $O(m^2 n^3)$ algorithm. Is there a faster approximation algorithm for this problem that is about as complicated as the greedy algorithm for SCS? Hopefully with a similar approximation ratio, though I realize that there is probably little research on this subject.


texts: Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus?

texts:
Suppose I am a bus transportation company. I have n buses. I want to change the bus routes so that the "average" commuter spends as little time on the bus as possible, while being able to arrive at as close to their final bus station at their desired time as reasonably possible.
Inputs: Origin bus stations, destination bus stations, and desired time of arrival for each passenger.
Constraints: The average commuter shall arrive no earlier than 15 minutes prior to their desired time of arrival.
As far as I am aware, no readily available (commercial or otherwise) solution exists.


texts: How to tackle Big O proofs that involve multiple parameters

texts:
I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am sure it is :")) and how to prove

  a^n = Θ(logn)

or any other, similar-looking expression?

  c1 * logn ≤ a^n ≤ c2 * logn

where, e.g. c1 = 1 and c2 = 2,

  logn ≤ a^n ≤2 * logn.

Can I go one step further and set n, to be equal e.g. 2? This way I will get

  log(2) ≤ a^2 ≤ log(4)

Which is surely true(for a between ~ 0.55 and 0.77)...

...but isn't that too specific and interfere with the inequality too much? Sorry if the answer is trivial but Google is not helping and I have nobody to ask for explanation.


texts: Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$

texts:
I'm having a lot of trouble constructing a PDA for the language: \begin{equation*}
\{a^m b^n : m < 2n < 3m \}
\end{equation*}

I know if I push a symbol for each $a$ I see, then pop 2 symbols for each $b$ I see, then I should run out to satisfy the $m < 2n$ part of the inequality. But I really don't understand how to include the requirement $2n < 3m$. I'm assuming it has something to do with clever branching based on non-determinism, but I can't wrap my head around it. Any help would really appreciated.


texts: Estimation of the number of solutions by Counting

texts:
This is a question from a quantum computation textbook.

Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X_1,X_2,X_3,...X_k$ be the results of the Oracle calls. So $X_j=1$ if the $jth$ Oracle call found a solution and $X_j=0$ otherwise. This algorithm estimates the number of solutions $S$:

  $$S=N * \sum_{j}\frac{X_j}{k}$$

Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:

  $$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$

The question is:
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.

I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:

  $$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$

Can someone help me with this?


texts: Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

texts:
The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time.

$$LIN \subseteq P$$

Since HORN-SAT is solvable in $O(n)$ (as indicated in Linear-time algorithms for testing the satisfiability of propositional horn formulae (1984))

  New algorithms for deciding whether a (propositional) Horn formula is satisfiable are presented. If the Horn formula $A$ contains $K$ distinct propositional letters and if it is assumed that they are exactly $P_1,…, P_K$, the two algorithms presented in this paper run in time $O(N)$, where $N$ is the total number of occurrences of literals in $A$.

I am wondering why we can't conclude that

$$LIN = P$$

given that HORN-SAT has also been proven to be $P$-complete under log-space reduction? I must be missing something. Or is that a well-known fact?

(I have yet thoroughly gone through the 1984 paper so I don't quite understand the algorithms for solving HORN-SAT in linear time, and thus I may have misunderstood the implication.)


texts: How to prove that sequences of stack operations are not context-free

texts:
By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...\}$.

This language is not against Pump lemma of CFL, right ? But I read from some materials that this language is NOT context-free. So why is that ?


texts: Why do the sequent calculus NOT left and NOT right rules work?

texts:
The rules I am considering are $\frac{\neg A, \ \Gamma \implies \Delta}{\Gamma \implies \Delta, \ A} (\neg L)$ and $\frac{\Gamma \implies \Delta, \ \neg A}{A, \ \Gamma \implies \Delta} (\neg R)$

I am trying to get my head around some of the sequent calculus rules, and while I think I understand most of them, I am struggling to apply any intuition to the negation rules shown above.

The intuition of looking at the left as a conjunction of literals and the right as a disjunction of literals seems to break down, and I am unclear how to explain these rules to myself.

What is a sensible way to view such rules and put some understanding on them?


texts: How many Turing machines are there with $c$ characters and $n$ states?

texts:
By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept.

We can assume every $n$-state Turing machine has $(c+1)n$ transitions going to either another non-accepting state, reject, or accept, that is that it has a transition for every state and character on the tape. It can either move to the left, right or not shift each transition. I tried some myself to figure out how many Turing machines there were and got the two following incompatible results.

We have $(c+1)n$ transitions and each transition has $3(n+2)(c+1)$ different options. Encoding it as a 5 tuple I get $3n(n+2)(c+1)^2$, but taking from options for transitions for each transition gives me $((c+1)n)^{3(n+2)(c+1)}$

Is either of these correct and if so why?


texts: How to express time complexity when the exponential "e" comes into play?

texts:
I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size.

While timing the execution of such algorithm I have figured out that the time elapsed follows an exponential law:

Time(size)=0.15*exp(0.05*size)

My question: is it correct to define this complexity according to

T(n)=O(e^n)?


texts: Decidability of the language of all TMs whose languages reduce to a fixed decidable language

texts:
Given that $L_1$ is decidable language. That means it has a TM  ($M_1$) decider.
Now we consider a language, $L_p$;

  $$L_p = \left \{ \langle M \rangle \mid L(M) \text{ is reducible to } L(M_1) \right \}$$

$L_p$ consists of all the encodings of the Turing machines whose language is reducible to $L_1$.

What can we say about $L_p$, Or, $L_p$ is decidable or undecidable ?

I understand if we assume to have a decider for $L_p$ and using this as component if we can construct a TM which decides a problem $P$. If $P$ is already known as undecidable then we can conclude that out assumed decider for $L_p$ does not exist.

How to come up with this reduction idea for $L_p$ ?


texts:
I jsut read up on the principle of centrality, where
"Think of a "network" as an NxN matrix, which has information about how N people (or N pages or N countries..) are connected to each other.

Adjacency Matrix is an NxN matrix, let's say it looks something like this. People who aren't connected to each other have A[i][j] = 0, people with weak relationships have A[i][j] = 0.1, people with medium ties have A[i][j]=0.4,
people with strong ties have A[i][j] = 0.6
        1---2----3----4
1---0.0 0.1 0.4 0.6
2---0.1 0.0 0.4 0.0
3---0.4 0.4 0.0 0.1
4---0.6 0.0 0.1  0.0

1 and 2 are weakly connected, 1 and 3 have medium ties, 1 and 4 have strong ties. This is just a quick example to give you a quick idea. These matrices may not always be symmetric either.

People with "higher eigenvector centrality" are people who are better connected to each other."

Is it feasible to use this to locate blobs in images using their color relations to each other? I need a feature detector/ blob extractor that doesnt use corners so I saw this. Any advice appreciated.


texts: What is the purpose of using NIL for representing null nodes?

texts:
In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for example a child of a node (in a tree) that does not exist.

Once, during a lecture, instead of saying NIL, my classmate said null, and the professor corrected him, and I don't understand why professors emphasise this word.

Is there a reason why people use the word NIL instead of null, or none, or any other word? Does NIL have some particular meaning that the others do not have? Is there some historical reason?

Note that I have seen also a few places around the web where, e.g., the word null was used instead of NIL, but usually this last one is used.


texts: Acyclic Tournament Digraphs and Hamiltonian Paths

texts:
I am studying MIT OCW lecture notes but they do not have solutions for the following problem.

Directed Acyclic Tournaments

In a round-robin tournament, every two distinct players play against each other
just once. For a round-robin tournament with no tied games, a record of who beat
whom can be described with a tournament digraph, where the vertices correspond
to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.

A ranking is a path that includes all the players. So in a ranking, each player won
the game against the next lowest ranked player, but may very well have lost their
games against much lower ranked players —whoever does the ranking may have a
lot of room to play favorites.

Give an example of a tournament digraph with more than one ranking.
Prove that if a tournament digraph is a DAG, then it has at most one ranking.
Prove that every finite tournament digraph has a ranking.
Prove that the greater-than relation, $>$, on the rational numbers,
$Q$, is a DAG and a tournament graph that has no ranking.

I got stuck at  questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.


texts: Decidable product with an undecidable projection

texts:
I got some problems with building a set, which should looks like this: $S = A\times B \subset N \times N $, where $S$ is decidable but $A$ is undecidable.

Could somebody give me a clue how to actually do this?


texts: How does sum of first $k$ integers equal $k(k+1)/2$

texts:
According to this video, he explains
$$p = k(k+1) / 2$$
Where $p$ is the sum of the first $k$ natural numbers. I understand $k$ means times of repetition and $k+1$ is how it increments, but why does he divide by $2$? I can't justify it.

Here is what the video describes:

for (i = 1; i <= n; i++)
  p += i

$$\begin{array}{|c|c|}
\hline i & p \\
\hline 1 & 1 \\
\hline 2 & 3 \\
\hline 3 & 6 \\
\hline 4 & 10 \\
\hline \vdots & \vdots \\
\hline i & i(i+1)/2 \\
\hline
\end{array}$$


texts: How to compute relative error for the rounding of floating point numbers when the rounded number is 0?

texts:
I have asked this question on Stack Overflow, I am asking it here in the hope to get more traction.

The relative rounding error for a floating point number x is defined as

$e_r = |\frac{(round(x)  - x)}{x}| = |\frac{round(x)}{x} - 1|$ (1)

Assuming that the rounding to nearest mode is used for $round(x)$, the absolute rounding error $|round(x) - x|$ is going to be less than 0.5 ulp(E(x)), where the ulp are units in the last place

$ulp(E) = 2^E \cdot \epsilon$

and $E(x)$ is the exponent used for $x$, and $\epsilon$ is the machine epsilon $\epsilon=2^{-(p-1)}$, $p$ is precision (24 for the single precision and 53 for the double precision IEEE formats).

Using this, the relative error can be expressed for any real number $x$

$e_r = |\frac{(round(x)  - x)}{x}| = \frac{|(round(x)  - x)|}{|x|} < |0.5 \cdot 2^E \cdot 2^{-(p-1)}| / |2^E| < 0.5 \epsilon$

For denormalized numbers $0 < x < 2^Em \epsilon$, where Em is the minimal exponent (-126 for single precision, -1022 for double):

$0 < x \le 0.5 \cdot \epsilon \cdot 2^{Em}$

the rounding always goes to $0$!

If the round(x) is 0, then by (1)

$e_r =|\frac{(0 - 1)}{1}| = |1|$ !

How is the relative error computed for such numbers? Should the relative error be even used for the numbers that are rounded to 0?


texts: Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

texts:
I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with a preemptive scheduler (a thread has no way to prevent the scheduler from preempting it). I'm exploring how minimalistic the system can get while remaining powerful and efficient enough for my needs. Compared with Mutex implementation on top of a minimalistic preemptive scheduler, there's a twist: the kernel does not guarantee thread liveness.

From the hardware, I get a basic atomic primitive such as compare-and-swap or load-link/store-conditional. You can assume that the word size for these instructions is large enough to store a pointer or a thread identifier.

From the kernel, I get two primitives:

sleep(): suspend the current thread until a thread has called wake(t) where t is the current thread. If the current thread's wake-up flag is already set then sleep() returns immediately. Returning from sleep clears the wake-up flag.
wake(t): wake thread t if it's asleep. If t isn't asleep then its wake-up flag is set and t's next call to sleep will return immediately.

Can I implement a mutex on top of these primitives?

lock(m): if m is taken, sleep until it is free. Mark m as taken.
unlock(m): mark m as free. If some other thread is waiting for it to become free, that thread is woken up.

Note the absence of a yield() primitive. If a thread does not go to sleep then there is no guarantee that some other thread will get any CPU time. Why? Because the scheduler assigns priorities to threads, and a low-priority thread will never run if all cores are busy running higher-priority threads. But the mutex functions must work between threads with different priorities.

If these primitives aren't enough to implement a locking mechanism, what feature can I add to the kernel to make it possible (keeping in mind that I'm trying to keep it small)? Note that I want to maintain the guarantee that high-priority threads won't be interrupted by low-priority thread if they don't take some explicit action permitting it.


texts: A simple way to find the feasible region of a system with simple constraints

texts:
I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in.  Here's the problem:

I start out with this directed acyclic graph:

The values describe the range that the edge lengths are allowed to be.  So the edge B->E can't be shorter than 9, but can be any size larger, while the edge B->C has to be between 0 and 1 (inclusive).

Also, it's constrained as if they were flattened onto a number line: for example, the distance from A->B->C is equal to the distance from A->C.  And BE=BC+CD+DE, DF=DE+EF, AF=AB+BE+EF=AC+CD+CF, and so on.  It's important to note that the ordering matters: D must come before E and F. Here's a visualization of that.  Think of the gray lines as extendable/retractable bars:

My goal is to create an algorithm that narrows down the values to the most constrained possible range that is legal.  For example, D->F has range (2,∞), but it can't be shorter than 3, since the smallest D->E->F can be is 3.  So I would want to raise the minimum value of D->F's range to (3,∞). Note that real numbers are allowed. The end result would look like this:

The challenge is that I need performant method that runs ideally in roughly linear time.  In practice, the graphs will be enormous and I will need to run this algorithm hundreds of thousands of times.

Originally, I was just dealing with minimum values, and had a version that was simple and worked well.  It just added the previous min values up, did the same in reverse, and found the difference:

- put the root A in queue Q
- while Q is not empty:
    - node N = Q.dequeue
    - if N has no previous edges:
        - N.prev_range = (0,0)
    - else:
        - N.prev_range = (0,∞)
        - for each edge PN in N.previous_edges:
            - N.prev_range.min = max(N.prev_range.min, P.prev_range.min + PN.min)
            - N.prev_range.max = min(N.prev_range.max, P.prev_range.max + PN.max)

- now do the exact same thing in reverse:
    - start at F and move down, storing values in N.next_range instead

- total_length = 15 (AF, in this example.  We can treat AF as a special edge in my case,
as I think my data will always have such an edge, although ideally the best solution
would not need to designate a particular edge for this)

- then, for each edge XY:
    - XY.min = max(XY.min, total_length - X.prev_range.max - Y.next_range.max)
    - XY.max = min(XY.max, total_length - X.prev_range.min - Y.next_range.min)

This algorithm just traversed the graph twice, and only looked at neighbors, so it ran fine on increasingly large graphs.  However, once I started adding constraints with maximum values, like the B->C and D->E in this example having a max value of 1, I started getting a problem where edge B->E is essentially locking C->D into having a min size of 7 (through BC and DE), and that locking relationship isn't captured by the process I implemented, so it's not constraining it to 6.

Is it even theoretically possible to find the real sizes without having to search local edges for these kinds of relationships?  I've been thinking about some physical analogs (ropes and knots, or sliding tubes) but they haven't helped. Does anyone have any ideas, or what kinds of things I should researching?  Or if such a solution isn't possible, if there's a simple and relatively performant non-linear solution?

Thanks!


texts: What is the asymptotic time complexity of the following 2 recurrences?

texts:
$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

and

$$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

for any given $i$ and $k$.

I think it helps to know that for $0<j\leq 1$

\begin{equation}
\lim_{n\to\infty} \frac{n/n^j}{n/\log n} = 0.
\end{equation}

But what is a simple way to derive the asymptotic time complexity for the two given recurrences?


texts: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

texts:
The fake proof:

We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it.
But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable.
We also know that we can construct $\mathbb{R}$ through what are called Dedekind cuts.
We choose to let the partition itself denote a new number and go forth to define mathematical operations on it as to be compatible with the rest of the numbers (mainly $\mathbb{Q}$ and our new number $x$)

Sidenote: I think so far this is standard, and contains nothing false. The actual argument starts below this line.

Let us denote the set containing $x$ as $S_1 := \mathbb{Q}\cup\{x\}$. For convenience, the superscript of $S_1$ is how many new such numbers we have added through the cuts.

Since $\mathbb{Q}$ is countable, we can enumerate over every single rational $q\in\mathbb{Q}$ to produce an $r\in\mathbb{R}$. Do this process $n$ times and you end up with $S_n = \mathbb{Q}\cup{x_1}\cup{x_2}\cup\dots\cup{x_n}$.

But $S_n$ is also enumerable since it has a finite more elements than $\mathbb{Q}$.

Hence - After enumerating over the entirety of $\mathbb{Q}$ - Start enumerating over the entirety of $S_{|\mathbb{N}|}\setminus\mathbb{Q}$

Now we will end up with even newer numbers to put in our set, which we will now call $S_{n = |\mathbb{N}|,k}$ where $n$ represents the enumeration over $\mathbb{Q}$ and $k$ represents the enumeration over $S_{|\mathbb{N}|}\setminus\mathbb{Q}$. Do this ad infinitum and you will eventually describe $\mathbb{R}$.

I know I went wrong somewhere, I just don't know where.


texts: Identify objects (bus) on the map based on coordinates (lat, lon)

texts:
Let's say I have an android app that frequently sends current GPS location of the user. If person is driving with bus, I can easily get GPS location of the bus and display it on the map and update it accordingly every 30 seconds.
Let's say that instead of one bus there are 3 buses driving along same route. My problem is to display real time location of every bus on the route. In this case there are X users on every bus all having my android application installed on their phones. Here is the picture that could represent the problem:

As you can see, every mobile application will send GPS location of the user to my server. Server receives and saves data.
Based on the server data I should create a web app that should display map whith position of every bus in real time.
One possible way to do this is to to try to cluster GPS data and based on clusters to conclude where is position of every bus. This approach has few problems:

This algorithm could be slow if there is lot of data (then I can't
update position of every bus every 30 seconds)
Second problem is that I don't know number of clusters (buses). There might be 2, 3, 4 or N buses

Is there any other better approach to this problem?


texts: Path between two vertices in directed graph without cyclic vertices

texts:
I have been searching online for some time but I have not found an answer.

Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic vertices can be found:

A path $v_1,\ldots , v_n$ (so $v_i\rightarrow v_{i+1}\in E$ for all $i$) has cyclic vertices when $v_{j}\rightarrow v_i \in E$ for some $i < j$.

For example: a the path $m \rightarrow v \rightarrow n\rightarrow u$ has cyclic vertices when $u\rightarrow v$.


texts: Given A to C, and B to C with known complexities, what can be said about A to B?

texts:
Say I have two sets of values $A$ and $B$ and for each set I have a computable function from that set to a third set $C$. Now suppose that I want to construct a function from $A$ to $B$, such that if I compose that function with the $B$ to $C$ function mentioned above I get a function that produces the same results as the $A$ to $C$ function mentioned above.

If I know the time-complexity of the two functions that return elements of $C$, does that allow me to say anything about a function from $A$ to $B$ with the specified property? For example can any bounds be placed on the computational complexity of such a function? Can we even say whether such a function is computable or not?


texts: Why are we interested in square-free words?

texts:
There is wikipedia page about square-free words, and there are a lot of theorems about these words, and examples of infinite square-free words.

I am wondering: why are we interested in these words?

Are there real-life applications of these words? Why are square-free words more useful to consider than other words?


texts: Formal defintion of SET-PARTITION as a language

texts:
I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it

$$
\left\{ \langle S,A,B\rangle  \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\in B} n \right\}
\quad \text{ or } \\
\left\{ \langle S\rangle   \;\middle|\; \text{ there exists a partition } (A,B) \text{ of } S \text{ with } \sum_{n\in A} n = \sum_{n\in B} n\right\} \quad ?
$$


texts: Is the language of rectangular matrices in MATLAB-style syntax context free?

texts:
Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be an
arbitrary number of rows, but each row must contain the same number of integers.

For example: $[3, 5, 6; 8, 9, 10; 7, 3, 6] \in L$ and
$[3, 5, 6; 7, 8, 10, 12; 7] \notin L$, because each row contains a different number of integers and so the matrix is not rectangular.

Is this language context-free? I have a very strong hunch that it isn't, given that not even the language $A^{n}B^{n}C^{n}$ is context free, but I don't have much experience with proofs using the pumping lemma for context-free languages and I'm hoping there is a simpler way to prove that $L$ is not context free.


texts: Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?

texts:
In Types and Programming Languages by Pierce et al:

  The recursive equation specifying the type of lists of numbers is similar to the equation specifying the recursive factorial function on page 52:

factorial = λn. if n=0 then 1 else n * factorial(n-1)

  Here, as there, it is convenient to make this equation into a proper deﬁnition by moving the “loop” over to the right-hand side of the =.
  We do this by introducing an explicit recursion operator µ for types:

NatList = µX. <nil:Unit, cons:{Nat,X}>;

  Intuitively, this deﬁnition is read, “Let NatList be the inﬁnite type satisfying
  the equation X = <nil:Unit, cons:{Nat,X}>.”

I have some questions for understanding it:

What does the “loop”  mean?
Does the recursion operator µ for types play similar role as operator λ for abstractions?
Doesn't NatList defined by NatList = µX. <nil:Unit, cons:{Nat,X}> look more like the generator of the recursive type X, i.e. a type mapping so that X = NatList X?
How can NatList as the generator of the recursive type X be the inﬁnite type X satisfying the equation X = <nil:Unit, cons:{Nat,X}>?

Thanks.


texts:
I'm so far a self taught programmer who's mostly been working on simple web and app development. But now my teacher wants me to enter a school competition in programming.
Of course the competition is based on problem solving and such, areas I'm guessing counts as computer science.
Even though I don't have much experience with this kind of problem solving I have been getting along quite well through the exercise problems.

Unfortunately I'm now completely stuck on one of the harder exercises and I could really use some help.

The problem is as follows:
You're in a cave which can be represented as a grid which size is defined by w and h, the cave also has walls inside it. Your goal is to get to the exit without the bear, who's also in the cave, reaching you.
You are able to move only one step at a time and you have to move every tick. The bear is able to two steps at a time to reach you.

But the bear is a bit stupid. First it moves horizontally until it's in the same column as you and then it continues by moving vertically until it reaches you. The bear is not aware of the walls and simply walks right into them.

The output should be a sequence of movements defined as U: up, L: left, D: down and R: right.

I'm currently programming in python but I'm not to interested in a real implementation. I would much rather have directions on how to think and reason to solve these kinds of problems.

I have a few test-cases if needed.


texts: Concave Polygon Intersection - Algorithm

texts:
I'm trying to develop an Algorithm for Polygon Intersection. Where each polygon is an array of Points, where each Point has X and Y properties.
Algorithm limitations:
- Algorithm input: 2 Polygons.
- Algorithm output: Intersection Polygon.
- Polygons may be convex or concave (angle between 2 neighbor edges my be more than 180).
- Polygons will not have any holes and will not be self intersection polygons.

I managed to develop this algorithm this far (given 2 polygons A and B):

For each vertex in PolygonA:
1.1 If vertex is inside PolygonB then Add this vertex to groupA.
For each vertex in PolygonB:
2.1 If vertex is inside PolygonA then Add this vertex to groupB.
For each edge {edgeA} in PolygonA:
3.1 For each edge {edgeB} in PolygonB:
3.1.1 If edgeA and edgeB are intersect (in the edgeA and edgeB segment area) then add there intersection point to groupI.
marge(groupA, groupB, groupI); // I don't know how to implement this

In debug I see that the Intersection area is built from vertexes combined groupA, groupB and groupI. But I don't know how should I merged them together - how to order/sort them???

I have try to sort the clockwise around the center point of the new intersection polygon - but this will only work for convex polygons not for concave.

In this example:
- The Blue Points are vertexes of PolygonA inside PolygonB (groupA)
- The Red Points are vertexes of PolygonB inside PolygonA (groupB)
- The Yellow Points are intersect vertexes of PolygonA with PolygonB (groupI)


texts: Can a computer determine whether a mathematical statement is true or not?

texts:
I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting:

During the first half of the twentieth century, mathematicians such as Kurt
Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨
cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false. This task
is the bread and butter of mathematicians. It seems like a natural for solution
by computer because it lies strictly within the realm of mathematics. But no
computer algorithm can perform this task.
Among the consequences of this profound result was the development of ideas
concerning theoretical models of computers that eventually would help lead to
the construction of actual computers

As a CS student, completely new to the theory of computation, this is hard to believe for me. It said that a computer can't solve a basic task such as determining whether a mathematical statement is true or false. Can't it really!? I have programmed lots of codes that determine if a mathematical statement is true or not. For example,  a simple code such as return 6 == 2*3 will return true if this statement is true, so why does the text says that a computer can't perform this task?
I'm sure I'm missing something here. Perhaps I'm mistaken by the definition of "Mathematical statement".
But I'm quite sure "Is 6 equal to 2 * 3?" is a mathematical statement and can be validated by a computer.
So what did the text mean by that? I'm confused!
PS: Sorry if the Complexity theory tag is misplaced here. As I said I'm new to the field and on the same page the author of the book stated that the theories of computability and complexity are closely related.


texts: Prove that max weighted independent set is NP hard using k-Independent Set

texts: Max weighted independent set returns a set of nodes that form the maximum weighted independent set. K-independent set returns yes/no if the graph has a independent set of size k. How would you go about proving this?


texts: Incorrect Answer Trying to Find Hamming Distance

texts:
A 010101
B 110011
C 111000
D 000111

The minimum Hamming distance of those code words is 3 as the minimum difference is 3 but the correct answer is 2.

How can I find the correct Hamming distance?


texts: Feedback vertex set and disjoint cycles (directed graphs)

texts:
I've looked at the feedback vertex set and thought about connecting the problem to finding vertex disjoint cycles.

My first thought was that if there are at most k vertex disjoint cycles in a graph, then k is a bound for the feedback vertex set problem and there is a subset of k vertices satisfying the requirement (i.e. there exists a subset of size k s.t. the graph without the subset is cycle-free)

However, I easily found this example that refutes it:

Here there is only 1 disjoint cycle, but we have to remove 2 vertices from the graph to obtain a cycle free graph.

My question is, can we find a bound for the feedback vertex set problem by looking at disjoint cycles? (for example, for graphs with at most k disjoint cycles the feedback vertex set is bounded by 2k, or maybe even by k+1 as I've shown here)

P.S. I'm asking specifically about digraphs.


texts:
I was given the following CFG :

$S \rightarrow A\ |\ B$

$A\rightarrow aAa\ |\ abAb\ |\ bAc\ |\ aca\ |\ abcb\ |\ bcc$

$B \rightarrow bBa\ |\ aBb\ |\ babBc\ |\ bca\ |\ acb\ |\ babcc$

And I have to show if it is ambiguous by giving two leftmost derivations for the same word.

I am pretty sure that there are two leftmost derivations but I can not find them.

I do not need the solution, just a tip where to start with would be enough.


texts: Proving Regularity of Languages that are 1/k of an already known regular language

texts:
There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language that is two-thirds of already known regular language is regular. I'm tempted to think that it should also hold true for any general $k>0$ that $m/k$th ($1 \leqslant m \leqslant k-1$) portion of a regular language would also be regular. I need a mathematical proof ( or a constructive proof having mathematical verifications done on it ) for the above statement.
   EDIT: For the "first half Language" which is much better formalised by David in the comments, I tried a similar argument as the answer in the link given by Hendrik. The product automaton notion was intuitively clear. But I was stuck with the transition listings for the 2nd state in the pair of states so formed by constructing the product automaton. I was flummoxed as to how I could be able to get the exact state for the corresponding word 'w' which would be the "first half" of a word accepted by the original regular language.


texts:
I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$}
I know the idea of building each one separately but how do I combine them into 1 PDA?
LHS: for every 'a' I push 'A' inside stack and for every 'b' I eject 'A'.
RHS:for every 'a' I push 'A' inside stack and for every 'b' I eject 2 times 'A'.
How can I combine them? Can I somehow use non determinism?


texts: Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?

texts: I have a 6-axial sensing device used to record the acceleration data. There is an algorithm used to count the number of step and walking distance of the user, but I want to further increase the accuracy of the result. I want to write an algorithm which can calculate the step size and the walking velocity of the person. Is it possible ?


texts: Calculating a jackpot winner based on probabilities

texts:
Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner?
My solution and the pitfall
To determine winning users, you could check if a drawn roll [0-100] falls between a stack of users' winning probabilities.
Winning probability for each user is calculated by applying Fc(Bet, Pot Size) = Bet * 100 / Pot size.
The only algorithm I have in mind to determine who the winner is, is to perform math server-side and iterate each user's winning probability, and check if roll falls within:
user_bets = [250,250,500]
pot_size = sum(user_bets)
roll = 32.21;
cur_range = [0,0]
for bet in user_bets:
    win_chance = bet * 100 / pot_size
    cur_range = [  cur_range[1] , win_chance + cur_range[1] ]
    if roll >= cur_range[0] and roll <= cur_range[1]:
        # cur_range[0] = 25, cur_range[1] = 50
        # We found the winner
        break

Goal
The goal is to possibly adopt a one-liner algorithm to determine the winner within SQL language, whereas no iteration is involved
Graphic example
User X = BET    =  $13.000
User Y = BET    =   $6.500
User Z = BET    =   $3.250

POT_SIZE        =  $22.750
----------------------------------------------------------------------------------------------------
User X Win range               = 0 ->  57,14     (57% win chance)
User Y Win range               = 57.15 ->  85,71 (29% win chance)
User Z  Win range              = 85,72 ->  100   (14% win chance)
----------------------------------------------------------------------------------------------------
ROLL Example          = 32.27...
WINNER                = User X
----------------------------------------------------------------------------------------------------
ROLL Example          = 91.38...
WINNER                = User Z


texts: are all problems solvable given infinite time?

texts:
Given a turing machine which has unlimited memory and time, can it solve all problems or are there a class of problems that cannot be solved even with unbounded power.

Is there a way to prove this?


texts:
I don't "see" why the following syntax is equivalent to the second

syntax1:

E -> E + T
E -> T

syntax2:

E -> T E'
E' -> + T E'
E' ->

(it is to avoid left recursion and I am not understanding why the solution works)

How do I mathematically prove that both syntax definitions are equivalent


texts: Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

texts:
As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous?

I mean, it would have to look something like:

S -> function_declaration | function_call | expr
function_declaration -> ... | S
function_call -> ... | S
expr -> ... | S

Maybe not all of them would have to point back to S, that depends on the specifics.
Is there any way to solve this?


texts:
I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood as recognizing/finding one selected changing shape/signal among all the present shapes/signals. Ideally, it should be possible to track the shape.

I believe that this process (of recognising) might be computationally expensive (depends on the resolution). I would very much appreciate a survey level paper that summarises achievements so far.
It would be even better if the paper would point out to existing limits due to engineerical/hardware/technological restrictions. I am sorry that the question is a bit fuzzy.


texts: How MO'S algorithm with update query works?

texts:
MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing difficulty to understand MO'S algorithm with updates (https://www.youtube.com/watch?v=gUpfwVRXhNY)

Since articles related to MO'S algorithm with updates is rare can someone who knows this algorithm can explain it.


texts: How to get time complexity of n queen puzzle algorithm(Using Backtracking)?

texts:
I have the following algorithm

void NQueen(int k,int n)
{
  int i;
  for(i=1;i<=n;i++)
  {
    if(place(k,i)==1)
    {     x[k]=i;
            if(k==n)
            {
                printf("Solution\n");
                printboard(n);
            }
            else
                NQueen(k+1,n);
    }
  }
}

int place(int k,int i)
{
  int j;
  for(j=1;j<k;j++)
  {
    if((x[j]==i)||abs(x[j]-i)==abs(j-k))
        return 0;
  }
  return 1;
}

void printboard(int n)
{
  int i;
  for(i=1;i<=n;i++)
    printf("%d  ",x[i]);
}

void main()
{
    int n;
    printf("Enter Value of N:");
    scanf("%d",&n);
    NQueen(1,n);
}

I am having trouble understanding the time complexity of the following algorithm.It has time complexity: $O(n^n)$, As NQueen function is recursively called n times.But is there is any tighter bound possible for this program? what about best case, and worst case time complexity?

Can someone help me understand the time complexity of the algorithm?


texts: Cryptography substitution frequency analysis

texts:
I am trying to find the plain text for the following cipher text using a frequency analysis

vr pvst yqlp mq nvf

But for the letters above this is really difficult, as if I use the alphabetic substitution technique, where I assume that v corresponds to e as this occurs most in the english alphabet. What about p, this also occurs three times, does this mean it corresponds to e. Same for r,s,t,y,l,m,n,j,f which occur only once. Is there an algorithm which looks at such duplicated frequencies, or do I guess:

v and p corresponds to e
q corresponds to t
r to f correspond to a

?

even using the bigram method for something like this is difficult as a bigram of pv is found,
if p = t
and v = h
that means p doesn't correspond to t anymore?

Thanks in advance!


texts: Can A still be a key if two tuples are the same

texts:
I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key.

What if 2 tuples are exactly the same, can we still say A is a key? To me A cannot determine an unique tuple.


texts: What are the k characters which make the most complete words?

texts:
Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ characters to learn, where "best" is defined as the set of $k$ with which the most complete words can be spelled.  Ie, if I know these $k$ characters I can spell $N_k$ words.  What is the maximum $N_k$ for every $k$ and which characters should I choose?

Checking a given set of $k$ words is equivalent to a Scrabble problem, but searching the space becomes very hard very fast.  This problem is of limited interest in English where $M=26$ but is more important in Chinese or Japanese where $M \sim 10^3$.

I thought of considering the bipartite graph of characters and the words that they make but I'm not sure what the best search strategy is.  I'm somewhat pessimistic that this problem is strictly solvable and therefore I am willing to try heuristic or stochastic methods.


texts: what is instrument validation in computer science?

texts:
I'm writing an assignment involving some statistics comparing different implementation methods for web applications. I'll be using some downloaded software and web pages I create, on both virtualized environments (docker, VM, cloud) and bear metal. I intend to measure response times from the client side.
Do I need to have instrument validation and what would it look like?


texts: von neumann architecture and functional programming languages

texts: Why functional programming languages do not use Von-Neumann architecture?Please explain elaborately.It'll be more helpful if you explain it diagrammatically. Thanks in advance. :)


texts: Comparing variable image to static image

texts:
What are Levenshtein distance algorithms, but for images?

I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created)

For example,

Target:

The following should be classified as "close enough"

Actual:

But the following should be classified as "incorrect" (even though it has 2 strokes and fills the '|' part)

I will be using this as a guide for users new to the English alphabet to practice on writing.

I will, of course, have other checks in place such as counting the number of strokes made (2 for 'K', 1 for '|', 1 for '<') and also checking to see if the area covered is reasonable (filling whole area should not be identified as "correct").

The user "drawing" will only be in black and white (not greyscale).

I suppose I could train a neural network (like handwriting recognition) but only to identify if it is "close enough". I think this is overkill as this only requires checking to see if it matches a single image and not selecting the best-matching image from a set.


texts: What are real life use case of algorithms like median of median or selection algorithms (assuming unsorted array)?

texts:
I am struggling to find out any real life (software) use case of using median of median or K’th Smallest/Largest Element in Unsorted Array problem.I found below text in link (https://news.ycombinator.com/item?id=2476272).

  However, partial sort (for which finding the median is a sub problem)
  is an easy optimization relevant for search engines, where you
  sometimes only need to extract the hits from position 1000-2000.

Apart from that, I am clueless why such problem exists in computer science and Interviews.

Your help is appreciated and will motivate me to understand computer science in a more realistic way.


texts: Why is computation of this function numerically unstable?

texts:
Why is computing the function at certain ranges of h
$$f(x) = \dfrac{\sqrt{-x+a} - \sqrt{2x+a}}{ 4a}$$
unstable? How would I rewrite this function so that it is stable?


texts: Intuitive explanation of why a large spread makes scheduling problems harder

texts:
The problem of minimizing weighted flow-time (min-WPFT) is defined as follows:

We are given a set $J$ of $n$ jobs, each job $j$ having a release time $r_j$, a processing time $p_j$, and a weight $w_j$.
We want to find a preemptive scheduling of the jobs on a single machine. (Preemptive meaning we are allowed to halt and resume jobs.)
For a given schedule $\mathbf{S}$, each job $j$ has a completion time $C_j$, which is simply the time at which it is completed in $\mathbf{S}$, and a flow-time defined as $C_j - r_j$, which is how long it was waiting to be completed after being released.
Our goal is to minimize $\sum_{j \in J} w_j (C_j - r_j)$

Here is the paper I am currently reading about this problem. Although I don't think anyone answering this problem has to even look at it to provide an answer.

It turns out that for this scheduling problem, what makes this problem difficult is when there is a large spread. We define the spread of the processing times $\hat{P}$ as $\hat{P} := \frac{\max p_j}{\min p_j}$ and the spread of the weights $\hat{W}$ as $\hat{W} := \frac{\max w_j}{\min w_j}$.

The paper I linked shows that there is a polynomial time $O(1)$ approximation for min-WFPT even when the spreads aren't polynomial in the input size. However, before this paper, there was only a pseudo-polynomial time $O(1)$ approximation for min-WFPT. This pseudo-polynomial time algorithm was polynomial in $n$, the number of jobs, and $\hat{P}$, the spread of processing times. (So in other words, if $\hat{P}$ happened to be exponential in the size of the input, this pseudo-polynomial time algorithm would not run in polynomial time in the size of the input.)

The questions I have is: Intuitively speaking, why does a large spread make scheduling problems hard?

I provide this example specifically because it is what I'm looking at right now, but I believe I have seen different scheduling problems in the past that were also hardest when the instance had a large spread, whether that be in the weights or the processing times.

My thinking right now is that when all the jobs are very similar, it is easier to get a good approximation because there are less sort of tricky, nonobvious ways of ordering the jobs. This being because an arbitrary job would typically be replaceable by another arbitrary job in a given schedule.

I was hoping some more experienced people could affirm this or affirm whether it even makes sense to generalize difficulty due to a large spread in the first place to most scheduling problems. Thanks for the help!


texts: Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

texts: Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...


texts: Analysis of and references for Koch-snowflake-like (and other exotic) network topologies

texts:
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied analytically to determine properties related to their expected performance; such characteristics include diameter (maximal distance between a pair of nodes, in terms of the number of links which must be crossed if such nodes communicate), the average distance between nodes (over all pairs of nodes in the network), and the bisection bandwidth (the worst-case bandwidth between two halves of the network). Naturally, other topologies and metrics exist.

Consider a network topology based on the Koch snowflake. The simplest incarnation of such a topology consists of three nodes and three links in a fully-connected setup. The diameter is 1, average distance is 1 (or 2/3, if you include communications inside a node), etc.

The next incarnation of the topology consists of 12 nodes and 15 links. There are three clusters of three nodes fully, each cluster being fully connected by three links. Additionally, there are the three original nodes, connecting the three clusters using six additional links.

In fact, the number of nodes and links in incarnation $k$ are described by the following recurrence relations:
$$N(1) = 3$$
$$L(1) = 3$$
$$N(k+1) = N(k) + 3L(k)$$
$$L(k+1) = 5L(k)$$
Hopefully, the shape of this topology is clear; incarnation $k$ looks like the $k^{th}$ incarnation of the Koch snowflake. (A key difference is that for what I have in mind, I am actually keeping the link between the 1/3 and 2/3 nodes on successive iterations, so that each "triangle" is fully connected and the above recurrence relations hold).

Now for the question:

  Has this network topology been studied, and if so, what is it called? If it has been studied extensively, are there any references? If not, what are the diameter, average distance and bisection bandwidth of this topology? How do these compare to other kinds of topologies, in terms of cost (links) & benefit?

I have heard of a "star of stars" topology, which I think is similar, but not identical, to this. If anything, this seems to be more of a "ring of rings", or something along those lines. Naturally, tweaks could be made to the definition of this topology, and more advanced questions could be asked (for instance, we could assign different bandwidths to links introduced at earlier stages, or discuss scheduling or data placement for such a topology). More generally, I am also interested in any good references for exotic or little-studied network topologies (regardless of practicality).

Again, apologies if this demonstrates ignorance of relevant research results, and any insights are appreciated.


texts: What is the difference between Partition and Division?

texts:
While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different?
Can anyone explain me their difference in Set Theory?
I know this is a simple question but anyone hardly talk about it but they always make here a mistake.


texts: Show that A** subset of A*, where A is a regular language

texts: I do not understand the proof for this. I know that every word in $(A^*)^*$ is made up of words from $A^*$, and that this is made up from words in $A$. But how does this help with showing that $(A^*)^*$ is a subset of $A^*$.


texts: Time complexity of recurrence function with if statement

texts:
Given the following code.

public static int fc(int n, int p) {
    if (p == 0) {
        return 1;
    } if (p % 2 == 0) {
        int a = fc(n, p / 2);
        return a * a;
    } return n * fc(n, p - 1);
}

How to calculate the time complexity of this code in big-$\mathcal{O}$ notation? I already define the recurrence function, which is

\begin{equation}
T(p) =
\begin{cases}
  1, & \text{if}\ p=0 \\
  T(p/2) + 1, & \text{if } p \text{ is even} \\
  T(p-1) + 1, & \text{if } p \text{ is odd}
\end{cases}
\end{equation}

Assuming that $p = 2^k$, then $T(p) = T(2^k) = T(2^{k-1}) + 1$. By backwards substitution, the equation become $T(2^k) = T(2^{k-n}) + n$. When $k = n$, $T(2^k) = T(1) + k = 1 + \log p$. Thus, $T(p) = \mathcal{O}(\log p)$.

However, I think that it only holds for the best case. I want to know about the other cases as well. How do I prove the average and worst case for this code?


texts: Implementation-level description of a Turing Machine

texts:
I am new to Turing Machines!

I need to work on an implementation-level description of a Turing machine that
decides the language L = an where n is a Fibonacci number.

I know Fibonacci numbers include  1 1 2 3 5 8 13 21 34 55 89 144 233 377...

So would this be as

M= "On input a^n:
    Scan a^n, if a '1' is found, cross it out, and move the head
    of the tape back to the left-hand end, and then go to II
    (****could I make II my accept state? Or should I make two the recursive calculation I explain in C below?)

    If a '0' is found, cross it out, and go to the reject state
    (can I make this three?)
    II. Accept
    III. Reject

I want to incorporate the recursion aspect of this in the implementation. Because if I were in C, and n is not a 0 or 1, it is a fibonacci number if you do a sort of fib(n) where inside it 'return fib(n-1) + fib(n-2)'.

Thoughts? Thank you.


texts: Is this an $NP$-complete problem: Product-2-Partition

texts:
I want to prove the NP-hardness of some problem P in scheduling theory. I was trying with Partition, 3-Partition and Subset product, But neither was successful.

Now, I can reduce a problem, say PRODUCT-2-PARTITION to P, but I am not sure whether such problem is $NP$-complete or not?

The problem PRODUCT-2-PARTITION is as follows:

Given $n$ integers. Can we partition them into $n/2$ subsets, where each subset contains exactly $2$ integers, and the product of the elements of any subset is equal to a given value $B$?


texts: Is there a decision problem in NP whose corresponding function problem is not in #P?

texts:
I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in contrast to the NDTM it does not stop when it reaches some accepting state in one path, but keeps running every path till the end since it wants to find out how many end in an accepting state. This leads me to the conjecture that it could take more time than an NDTM on the same instance. But on the other hand I think I can't be sure that there is always a short path. Hence in worst case the running time could also be equal.
Is this problem solved?
Does my imagination make sense so far?
Thanks a lot in advance!


texts:
I know that a graph G' is a subgraph for G if V(G')⊆V(G) and E(G')⊆E(G).

Today my professor wrote that G' is a subgraph for G if G' is a graph and V(G')⊆V(G), and then he told us that this definition is equivalent to the one we've seen before (= the first line in this post).

However, I don't think that these definitions are equivalent. In fact, if this is G:

       2
     /   \
    1     3

and this is G':

    1 - 3

we have that G' is a subgraph for G according to the second definition (wrong), while it is not according to the first one (right).

Am I missing something or was the professor wrong?


texts:
I need a clarification related to the following situation.

Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are given a function $f:\Sigma^* \mapsto \Sigma^*$ and a language $J_2 \in \Sigma^*$ such that $$ x \in J_2 \iff f(x) \in J_1.$$

I would assume this readily implies $J_2$ is recursive as well since one can create a Turing machine $T_2$ that on given input $x$ evaluates $y = f(x)$ and simulates $T_2$ on the given input $y.$ Clearly $L(T_2) = J_2.$

What now confuses me is the following.

  Are there any restrictions on $f$ for this ''reduction'' to work?

What is the usual approach here? Is $f$ assumed to be given as a black box that always evaluates $f(x)?$ If so could someone explain the motivation behind this, because it appears to me that it could as well be that $f(x)$ cannot be computed effectively and hence $T_2$ cannot be constructed in a "feasible" way.

As for the motivation for the question, I would like to show that given $f:\Sigma^* \mapsto \Sigma^*$ and a recursive language $L,$ the language $f^{-1}(L)$ is recursive as well.


texts: Determine if a line going through n rectangles exists

texts:
I guess this is kinda like asking if 3 (or more) rectangles are collinear.

The question is, given n rectangles on the 2D plane (given as the rectangle's top-left corner coordinates and it's width/height), does there exist a line that goes through all of them?

Notes:

The rectangles' sides are perpendicular or parallel to the axes. So
basically,  none of the rectangle sides are slanted.
Rectangles themselves can intersect
Does not actually need to produce the line equation

I've been thinking through this for a good portion of today, and can't figure out (or find online) an answer. I keep finding edge cases and can't figure out a guaranteed method. The line of best fit for the mid-point or the corners of all n rectangles seem like a good heuristic for a line, should one exist, but I don't think it always works.

The corners of the rectangles seem like good starting points to determine the extreme slopes of a potential line, but it's still unclear to me how i'd use them to determine if a line exists for all n rectangles. I also know how I'd do this intuitively IRL, but not sure how to turn it into an algorithm.

Visual Example for 4 rectangles:


texts: Notation for a Kleene fixed point with a starting element

texts:
Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times composed with itself) leads to a fixed point of $f$.

It is also clear, if $f$ is inflationary, that for any $q \in Q$, the chain $q \leq f(q) \leq \ldots \leq f^m(q)$ leads to a fixed point. (This follows immediately by just considering the subset $\{\,p\,|\, p \in Q \wedge q \leq p\}$, which is also a CPO.)

This second form is often more useful in practice. But how to denote it? While the fixed point of $f$ is easily written $\text{fix} f$, is there a standard convention for the second form? Writing $\text{fix} f(q)$ seems intuitive but is - strictly speaking - wrong, since $f(q)$ is not a function (it might also be confusing in the case of higher-order functions).

edit: Added note, that $f$ must be inflationary.


texts: Understanding x64 and x86 OS with 64bit cpu

texts: Kinda stupid question, but makes me a bit confused. If my OS (Win 7) is 64-bit type system and my CPU is 64-bit, why Program Files directory is marked (x86), x86 stands for 32-bit OS?


texts: Does the 'difference' operation add expressiveness to a query language that already includes 'join'?

texts:
The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases that do not support the set difference operator directly, but which support LEFT JOIN (a kind of outer join), and in practice this can be used instead of a set difference operation to achieve the same effect.

Does this mean that the expressive power of a query language is the same even without the set difference operator, so long as the LEFT JOIN operator is maintained? How would one prove this fact?


texts: $NP \ vs \ co-NP$: tautology to SAT and vice versa?

texts:
Let define formula $\Phi%$ given in CNF and it's complement $\overline \Phi$.

$\Phi$ is satisfiable iff $\overline \Phi$ is not tautology and vice versa.

$\Phi$ can be converted to $\overline \Phi$ in polynomial time using following method:

Change all literals with non-literals and vice versa: $\forall i:x_i \Rightarrow \overline {x_i}; \ \overline {x_i} \Rightarrow x_i$.
Change all disjunctions with conjunctions and vice versa.

This property is a corollary of CNF/DNF definitions.

This will give us a DNF $\ \overline \Phi\ $ of the same length as $\ \Phi$.

Assuming DIMACS format SAT solver can solve tautology this way:

Multiply all variables by $-1$.
Solve SAT.
Return $\overline {answer}$, where $answer$ is global (final) answer for SAT.

Example 1:

$\Phi = (x \lor y \lor \overline z) \land (\overline x \lor t) \land (\overline y \lor \overline t) = 1100.1010.0101.0000$ - is satisfiable.

$\overline \Phi = (\overline x \land \overline y \land z) \lor (x \land \overline t) \lor (y \land t) = 0011.0101.1010.1111$ - is not tautology.

Example 2:

$\Phi = (x \lor y) \land (\overline x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline y)= 0000$ - is not satisfiable.

$\overline \Phi = (\overline x \land \overline y) \lor (x \land \overline y) \lor (x \land y) \lor (\overline x \land y) = 1111$ - is tautology.

Does this proves that $NP = co-NP$? Or, maybe, somewhere I'm wrong with complexity classes?


texts: Doubt regarding Chomsky Hierarchy, CFG and CSG

texts:
I was following a discussion on a website, where a fellow scholar claims that
this grammar

  S→ aAa | bAb | ϵ

  A→aA | bA |ϵ

is not CSG, so it should also NOT be a CFG. But this grammar properly satisfies the rules of CFG according me, on the other hand it fails to satisfy the conditions of CSG, which states that--

  In addition, a rule of the form

S → λ

  where λ represents the empty string and S does not appear on the
  right-hand side of any rule is permitted

So the given grammar is definitely not in CSG. But According to chomsky hierarchy

A CFG should be contained in CSG, so why this rule is NOT being satisfied for this case?


texts: Finding shortest cycle in graph with positive weights

texts:
Given a graph G, with all positive weights, find the shortest cycle length in O(V^3)

My idea is, negate al the edges, apply floyd-warshall algorithm and then for all $i$, find the largest $M[i][i]$ where $M$ is the final distance matrix, and then negate $M[i][i]$ and return.

Could this work? I know floyd can be used to detect a negative cycle, but if all edges are negative, can I apply it in this way to get the smallest cycle length?

Thanks


texts: Proof of undecideability that one state is reached before another

texts:
I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ pass on the state $q$ before reaching $q'$, but if $q'$ is never reached then $w$ is not in $K$, is both recursively enumerable and undecidable.

I am thinking that this could be solved by a reduction of the Halting problem, but I do not know how to proceed.

Reducing the Halting problem to this problem would mean that a machine $M$ with data $w$ will halt on $w$ iff a machine $M'$ with data $w$ that first passes state $q$ then $q'$.
I see that if we were to associate $q$ in $M'$ with $q_0$ in $M$ and $q'$ in $M'$ with $q_f$ in $M$ we could associate part of the problem with the halting problem, but how can the condition "$q_f$ must not be reached first" be included?


texts: Is subset sum problem with multiplicities NP-complete?

texts:
To be specific, the problem is formalized as follows.

Given a set of integers $\{a_1,\ldots,a_n\}$, determine whether there exist non-negative integers $x_1,\ldots,x_n$ such that $a_1x_1+\cdots+a_nx_n=0$ and at least one of $x_1,\ldots,x_n$ is positive.

Note this is not a duplicate of this problem. In that problem, the target sum is given as input, while in our problem, the target sum is fixed to be $0$.

I tried to follow the idea of the answer to that question to come up with a new reduction, but since a basic idea of that answer is to use big elements as well as big target to prevent an element from being chosen multiple times, while in our problem the target sum is $0$, I failed.

Related question: Is the following Subset Sum variant NP-complete?


texts: Bellman-Ford algorithm - Why can edges be updated out of order?

texts:
The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path from $s$ to each vertex is computed; this goes on for  $|V|-1$ iterations. My questions are:

Why does there need to be $|V|-1$ iterations?
Would it matter if I checked the edges in a different order?
Say, if I first check edges 1,2,3, but then on the second iteration I check 2,3,1.

MIT  Prof. Eric said the order didn't matter, but this confuses me: wouldn't the algorithm incorrectly update a node based on edge $x_2$ if its value was dependent on the edge $x_1$ but $x_1$ is updated after $x_2$?


texts: Data structure with constant time operations

texts:
I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value in constant time.

This data structure should probably be sorted to find the maximum values and I have looked into red-black trees, however they have logarithmic-time operations.


texts: How would I convert a 16K x 32 SRAM into a 64K x 8 SRAM?  The 16K x 32 RAM module is a single unit that cannot be altered internally and is capable of address decoding, has tristate outputs, and read/write/and chip enable.  Also only the memory read of the circuit has to be implemented.


texts: Maximum weight perfect matching in general graphs

texts:
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\text{maximize}~~\sum_{e\in E} w_e x_e
\\
\text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V
\\
0\le x_{e}\le 1\text{ for }e\in E.
$$
In the corresponding Integer Program $x_e$ is a binary variable s.t.
$$
x_e =
\begin{cases}
1 \text{ if } e \text{ is in the perfect matching}\\
0 \text{ otherwise}
\end{cases}
$$
I am unable to come up with an example where given $G$ has a perfect matching, the LP does not have an all integral optimal solution $x_e^{\text{*}}$. I tried taking small examples with odd length cycles, though there was a fractional optimal for the LP, there was an all integral optimal as well (in the examples I took).
I am aware that for bipartite graphs if the LP is feasible, then there always exists an all integral optimal for the LP. Does it hold for general graphs as well? If not I would appreciate hints so I can come up with such an example.


texts: Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this problem, but I couldn't find it.


texts: Achieving the capacity of an AVC under random coding

texts: Is there any work that shows how to achieve the random coding capacity in an Arbitrarily Varying Channel (AVC)? The best I can find is in the book 'Information Theory: Coding Theorems for Discrete Memoryless Systems' by Csiszar and Korner but it seems quite dated.


texts: Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?

texts:
I have got some difficulties to solve this algorithm problem.

I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.

To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:

partition all distances with a randomly chosen pivot, and
find out the numbers of distances on each side to determine which part for recursion.

There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.

Please help me. Thank you very much.