texts:
I am trying to compute the average cell size on the following set of points, as seen on the picture: . The picture was generated using gnuplot:

gnuplot> plot "debug.dat" using 1:2

The points are almost aligned on a rectangular grid, but not quite. There is a limited bias (jitter?) of 10-15% along either X or Y (never more). How would one compute efficiently a proper partition of tiles so that there is virtually only one point per tile, size would be expressed as (tilex, tiley). I use the word virtually since the 10-15% bias may have moved a point in another adjacent tile.

Just for reference, I have manually sorted (hopefully correct) and extracted the first 10 points:

 -133920,33480
 -132480,33476
 -131044,33472
 -129602,33467
 -128162,33463
 -139679,34576
 -138239,34572
 -136799,34568
 -135359,34564
 -133925,34562

Just for clarification, a valid tile as per the above description would be (1435,1060), but I am really looking for a quick automated way. A tile in my case is rectangular.

A brute force approach would be to use a Delaunay triangulation but that feels way too complex because of the restrictions of my issue (limited bias, rectangular tiles...)


texts: How to solve this mapping reduction problem by proving the computability of this function?

texts:
I am working on a mapping reduction problem. Define the union of two languages $L_1,L_2\subseteq\{0,1\}^*$ to be $L_1 \cup L_2 = \{x0\mid x \in L_1\} \cup \{y1\mid y \in L_2\}$. I want to prove that $L_1 \le_m L_1 \cup L_2$.

I was reading about the mapping reduction. According to mapping reductions, for any $w \in \Sigma^*$, $w \in L_1$ iff $f(w) \in L_1 \cup L_2$.

I am thinking of making my computable function $f=\{x \mid x\text{ ends with }0\}$. If I can prove that this function is computable, then I can complete my reduction. I just have two following questions:

Am I thinking correctly about this problem?
How to correctly prove that this $f$ is computable? I am thinking to create a TM $M$ that enumerates $w \in L_1 \cup L_2$. If the string ends with a 0, then I halt the machine and accept the result. I am not sure how to formally prove the computability of $f$.


texts: Possible to develop a game using assembly language?

texts: I am wondering what it takes to develop a game in assembly language. For example, what are the limitations or advantages from using assembly language in game development? Also, are there any programs/softwares to aid the development of games in assembly language?


texts: What is the complexity for the BFS algotithm for shortest path on unweighted grid?

texts:
What is the complexity of the BFS algorithm for the shortest path on the unweighted grid?
The grid is a classical maze with a starting point and exit, need to find an exit.  Can move only vertically and horizontally.
Found the answer here: https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode#:%7E:text=The%20way%20I%20see%20it,cols


texts: Determining whether a change in an memoized algorithm will improve the performance

texts:
I have an algorithm that constructs an optimal binary tree using dynamic programming.  After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is there an analytical way to determine whether such change will improve the runtime of an algorithm with memoization?

Python code and description follow:

def solver(problem, memo={}):
    try:
        return memo[problem]
    except KeyError:
        if is_base_case(problem):
            memo[problem] = base_solver(problem)
            return memo[problem]

    best_score, best_solution = INFINITY, None

    for left_subproblem, right_subproblem in all_splits(problem):

        left_solution = solver(left_subproblem, memo)

        if (base_score(problem) + score(left_solution) >= best_score):  #optimization
            continue                                                #optimization

        right_solution = solver(right_subproblem, memo)

        current_score = base_score(problem) + score(left_solution) + score(right_solution)
        if (current_score < best_score):
            best_score = current_score
            best_solution = combine_solutions(problem, left_solution, right_solution)

    memo[problem] = best_solution
    return memo[problem]

The function iterates over all ways to split an instance problem into two subproblems, recursively solves them and stores the solutions.
Optimal tree is a tree that has the lowest score, determined by the score() function. The score of a tree is always positive and is a sum of a base score of the root node plus the score of the subtrees.
The optimization in question are the lines marked as #optimization. It's supposed to avoid solving the right subproblem, if, based on the left result, it's impossible to create a solution with a better score than the current best.
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work. However, this is just my hindsight and I would like to have a rigorous way to analyse the problem, in case an algorithm like this was presented to me in pseudo-code.


texts: Examples for directed graphs with super polynomial cover time

texts:
The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes.

For undirected graphs the cover time is upperbounded by $O(n^3)$.
What about directed graphs? I'm looking for examples of super-polynomial cover time.

Is there an example for such graph with $O(2^{\sqrt n})$ cover time?


texts:
I am attempting to learn neural networks using the Keras libary on the MNIST hand written digit dataset, using dense layers only. I am trying to figure out what the best shape for the network should be but I can't seem to find any literature or discussion on the subject.

By shape, I mean should the hidden layers have more nodes as I go deeper, less nodes, or the same? I've taken to calling them square, pyramid, and reverse-pyramid because I couldn't find a better name. See the end of this post for clarification on shape

I've tried all 3 and the reverse pyramid is giving me the best at 80% accuracy but I can't imagine why. I feel like I would just be losing data and introducing noise by expanding the number of neurons as I go deeper.

Is there any literature or discussions about this subject? Perhaps, I'm not using the right keywords to look, I just don't know the correct terminology. I've tried neural network shape, structure, hidden layer layout, etc. with very little luck.

Thanks in advance.

Square - Hidden layers stay same size until the end

Pyramid - less neurons at each additonial hidden layer (pretend they are all hidden layers)

Reverse Pyramid - more neurons at each additiona hidden layer


texts: Minimal class of grammar required to run program

texts:
In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, and weaker machines lower. Machines are able to "recognize" languages within their class, and they are able to "decide" the halt-ability of weaker languages. "http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html". Doing such tasks has different complexity classes based on the class of what is being acted on.

Here is my question: What is the process of determining the minimal class of machine required to recognize, and then decide, on a language. Also what is the cost of this function in relation to the class of machine?

I know that one way is to construct a grammar for a weak machine, see if it accepts, and then if you cant find one work your way up the hierarchy.

I certainly hope there is a solution to this problem besides just brute forcing potentially forever? Thanks!


texts:
The MAX k-SAT problem is:

  “Given a set of clauses C1,…,Ck, each of length k, over a set of
  variables x1,…,xn, find a truth assignment that satisfies as many of
  the clauses as possible.”

I'm trying for find a randomized 0.999-approximation algorithm for the MAX 10-SAT problem. Help :(


texts: Updating a mst after increasing the weight of an edge in the mst

texts:
Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$
Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$.

I'm using a common algorithm to update $T$ so we don't have to find a mst of $G_2$ from scratch. The algorithm is to first take out $e$ from $T$, which will result in two subtrees $T_a$, which contains $a$, and $T_b$ which contains $b$. Then, I iterate over all the edges in $G_2$ and find the edge with the minimum weight that has one ed in $T_a$ and the other end in $T_b$. Call this edge $e_2$. Then I add this edge into $T$ to get $T_2$.

I'm having a lot of difficulty proving that $T_2$ is a mst for $G_2$. I've proved that $T_2$ is a spanning tree of $G_2$, but again, I'm having a lot of difficulty with proving that $T_2$ is a minimum spanning tree.

Any help would be greatly appreciated!


texts:
I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr[M(x)=L(x)]> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \{0,1\}^*$ and random coin tosses $ r \in \{0,1\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr[M(x) = L(x)]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?


texts: Euclidean Steiner Tree Question in Approximation Algorithms

texts:
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
Prove that each of the additional points must have degree 3, with all three angles being $120^\circ$.


texts: How is Perfect shuffle a better interconnect scheme for parallel processing? For example if we consider a problem of sum reduction, I want to understand how this scheme is useful when implementing sum reduction in parallel , for example on a GPU?


texts: How to prove this language is not context-free language by pumping lemma?

texts: Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?


texts:
Given the alphabet $Λ = \{a, b\}$ and this non-regular language:

$$L=\{aba^nb^ma^n|n,m>0\}$$

what's the best way to generate the grammar?  Every string has to start with $ab$, then we have $aba$ and this part has to have the same number of $a$. In words that is clear, but I'm stuck; should I first consider the fixed part $ab$, or is better to produce the $a^nb^ma^n$ part and then add the $ab$? I need a method basically.


texts:
Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual programming allows developers to write programs by manipulating graphical elements. I guess using visual programming should improve the quality of code and reduce programming bugs. I'm aware of a few visual languages such as App Inventor, Scratch, and LabView.

Why are there no mainstream, general-purpose visual languages for developers? What are the advantages and disadvantages of visual programming?


texts: Understanding constraint formula concept in Java

texts:
JLS defined a concept called "constraint formula". There is a formal definition:

  Constraint formulas are assertions of compatibility or subtyping that
  may involve inference variables. The formulas may take one of the
  following forms:

  ‹Expression → T›: An expression is compatible in a loose invocation context with type T (§5.3).
  ‹S → T›: A type S is compatible in a loose invocation context with type T (§5.3).
  ‹S <: T›: A reference type S is a subtype of a reference type T (§4.10).
  ‹S <= T›: A type argument S is contained by a type argument T (§4.5.1).
  ‹S = T›: A reference type S is the same as a reference type T (§4.3.4), or a type argument S is the same as type argument T.
  ‹LambdaExpression →throws T›: The checked exceptions thrown by the body of the LambdaExpression are declared by the throws clause of the
  function type derived from T.
  ‹MethodReference →throws T›: The checked exceptions thrown by the referenced method are declared by the throws clause of the function
  type derived from T.

I have some misunderstanding about it. As far as I've understood we have a set of all Java types, denote it by M. Could we say, that any constraint formula defines a subset of M, for instance

‹S <: T› = {S | (S belongs to M) and (S is a subtype of T) }


texts: Enumerating points on the integer lattice, within a sphere, sorted by angle, in O(1) space

texts:
Inspired by this StackOverflow question: https://stackoverflow.com/questions/63346135
(it was not clearly presented, and got closed)
Let's say I wanted to enumerate all the 3D points on the integer lattice, within a sphere, in order of the angle between the vector to the point and the up vector (say z).
Could I do this in O(1) space efficiently?
All I can find is:
Remembering last point (init at (0,0,0)). (O(1) memory)
while true
    init best dot product to 0
    going through all 3D points (three nested for's with radius range)
        if this point has better dot product but least or equal [caveat] than last point
            keep this point as best
    if best dot product is still 0, exit
    pick best point as current point (this is where the listing occurs)
    update last point to best point

Not only is this absolutely slow, it also needs the use of integer math for dot product and length so that numerical precision doesn't mess with symmetrical points and it would also need a tweak to guarantee symmetrical points are listed in a known order.
Is there any good algorithms that would apply here?


texts: How do confluently persistent data structures handle merge conflicts?

texts:
From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and also disallowing the remerging of these branches.

       o o o
      /
o o o o o o o o o
  \
   o o o

Confluently persistent data structures on the other hand seem to allow the merging of these branches even though over time they may accumulate conflicting modifications to the contents of their given nodes.

o o o o o o o o o o o o
  \
   o o o o o x x x
      \     /
       o o o

I think I've searched the given research for an algorithm about how to potentially handle merge conflicts arising from this situation but have come up with nothing. Real world examples like git appear to punt this question to the user for manual resolution. Is this really the only option? Thanks for reading!


texts: Notions of information content and randomness of binary square matrix

texts:
We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.

For a binary square matrix, it is not sufficient to just convert the matrix into binary string and measure its information content or its randomness since naive unraveling of the binary matrix into binary string would lose the adjacency information in each row and in each column.

My question: What are the analogous notions for measuring the information content and randomness of binary square matrix?


texts: Number of nodes of given height in binary heap

texts:
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap.

How can I show this? Or, how can I prove this?


texts: Hardness of approximating Minimum Cardinality Exact Cover

texts:
The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.

Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for a subcollection $S'$ of $S$ of minimum cardinality such that the union of $S'$ is $U$, and $S_1 \cap S_2 = \emptyset$ for every distinct $S_1, S_2 \in S'$.

We may assume that for each $u \in U$' there is a set $S_u = \{u\}$ in $S$.  This ensures that there exists an exact cover of cardinality at most $|U|$.

I'd like to know if MCEC is as hard to approximate as set cover, i.e. cannot be approximated to within a $\log |U|$ factor.
I can show that MCEC has no constant factor approximation, reducing from $k$-Set-Cover for any constant $k$ by adding every subset of a set present in the set cover input.  But having the same inapproximability as set cover would be stronger.


texts: Why does space(n) <= time(n) imply that TIME(f(n)) is a subset of SPACE(f(n))?

texts:
The title might be hard to understand, here's a picture of what I don't understand:

And further, why can we conclude this?

I thought about posting to theoretical CS stackexchange but it asks for research level and I don't think this will be accepted


texts: Greedy sequential/parallel task scheduling

texts:
We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task i we know how much time it needs to spend in each part, namely mi for the guarded part, and ai for the part that can be executed in parallel.
The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.
My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending ai order.
For example given the tasks with:
m1 = 3, a1 = 9
m2 = 2, a2 = 7
m3 = 6, a3 = 10
The optimal solution is the permutation 3, 1, 2.
However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?


texts: Busy Beaver machines on semi-infinite tape

texts:
The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input.

The usual Busy Beaver machines run on a blank tape that is infinite in both directions.

  Is there any research (and/or experiments) on Busy Beavers machines that run on a semi-infinite tape? (the Turing machine's head is initially positioned on the first cell of the tape)

With a semi-infinite tape we must also consider what happens if the head tries to cross the boundary at the beginning of the tape; the two approaches:

the computation halts
the head "bounces" to cell 2

probably lead to different results.


texts: If $L$ is NOT Turing-recognizable, does that mean that super sets with $L$ are also not?

texts:
Suppose there is a language $L$ that is not Turing-recognizable. Now suppose, for every word in $L$, you would concatenate a "0" as prefix, resulting in $L' = \{0w | w \in L\}$. Does this mean that $L'$ is also not Turing-recognizable?

I would argue that $L'$ is also not Turing-recognizable:

No Turing machine recognizes $L$. So there exists no TM that recognizes all the words in $L$. That means that all the words that can not be recognized by a TM that are in L, also can not be recognized even with a "0" added before them. Because after the TM's head reads the "0", we assume that the head will read what comes after, which is a word that is not Turing-recognizable. One could argue that the head doesn't need to read the word and just go to "accept" after reading the 0, but then I can also build a TM that would just go to "accept" straight away before reading this word at all, meaning that the word was not Turing-recognizable which contradicts the initial statement.

In other words, after reading the "0", the TM will have to come across the not Turing-recognizable word, which it can't recognize. Therefore $L'$ is also not Turing-recognizable.

To generalize, I think if a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable.

However, I feel my explanation is shaky and I'm not convinced I am correct. Can anyone verify my claim, and either prove me wrong or give tips for a better proof?


texts: How do I normalize a push down automaton?

texts: Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does this mean that there must be two separate transitions to push the * and then pop the *? Or is it normalized as is? Is it okay to have multiple transitions from a single state to another, some of which pop, and some of which push?


texts: What are the known ambiguities in C language grammar?

texts: I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we can modify the BNF grammar to avoid those ambiguities, including the known one mentioned above?


texts: How can I solve a recursive equation with a summation notation?

texts:
Consider the following formula:

$T(n) = n + \sum_{k=1}^{n-1} [T(n-k) + T(k)], T(1) = 1$

What is the order of T?


texts:
Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit some collision/overlap where the worst-case performance of the algorithm is better than O(n^2)?
You can assume that intervals starting at an end of another interval do not overlap, ex [15,22) and [22,30) do not overlap.
For example, given this collection {[12,16),[8,13),[16,34)} the result would be {0,1} because interval at index 0 intersects some interval, and interval at index 1 intersects some interval.
I have an algorithm that in worst case performs O(n^2) but can't figure out one that is faster.  Mine doesn't use binary search trees, simply orders the intervals according to a, and then has a loop over all the elements with an inner loop on the remaining elements checking for intersection -- once an inner loop interval doesn't intersect the inner loop stops and the outer loop proceeds to the next element.
I am not looking for exact code, just a clear explanation of such an algorithm.


texts: Historical relation between computer science and the theory of dynamical systems

texts:
I have asked this question at math.stackexchange, but I have been redirected here.

My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such as Optimal control) and (theoretical) Computer science. The reason for which I ask this question is, that several older major journals, now considered to be primarily focused on theoretical computer science, were originally devoted both to computer science and to dynamical systems.

The example of such journals can be for instance Journal of Computer and System Sciences. Mainly in its beginnings (however, I am too young to remember these times), it published papers both on computer science and on system sciences, and both of the fields seemed to be of equal importance. Moreover, also the name of the journal Information and Control suggests the relation to optimal control. However, this journal was always focused mainly on theoretical computer science and information theory.

So therefore I wonder, if these fields (nowadays, up to my knowledge, considered to be substantially different) have something in common or if there is some purpose to consider these fields to be related.


texts:
I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I require is to merge the closest nodes, (bounded by a threshold) into a single node and recompute the graph each time, recursively. This is because if two nodes are merged, then all the links connected to the new node has to be updated with the newly computed distance for the new edge. Since its a complete graph this would be an expensive operation.

I would have a large number of nodes with $N*(N-1)/2$ links for $N$ nodes , and $N=60$ or more ,
What I want to do is to reduce this complete graph into clusters of  sub graphs with low intra node distance, yet with a relatively high distance between the subgraphs. So,How can I go about solving this problem?

This is like applying the graph partitioning techniques to complete graphs.

One of the solutions is this paper which proposes the normalized cut criterion for partitioning the graph  minimizing normalized cuts on graphs which is clearly NP-complete,Is there a practically efficient way and what are the recent developments to achieve this?

So what I want is an efficient solution to the above problem which is not NP complete ? Since this problem is NP Complete , answers using randomization or approximation methods would be welcome


texts: Models of computation: the arithmetic model, Turing machine (and ...)

texts:
How is an arithmetic model defined?

What relations are between it and Turing machine? Are they equivalent in some sense?

Is it true that

in the arithmetic model of computation, the basic arithmetic operations (addition, subtraction, multiplication, division, and
comparison) take a constant unit time step to perform, regardless of
the sizes of the operands.
in the Turing machine, the time each operation takes will depends on the storage size of the operands?

What is the point of having these two different computational models?
Are there other models of computation distinct from the Turing
machine and the arithmetic model?
There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic
model. The
Euclidean algorithm for computing the greatest common divisor of two
integers is one example.

If an algorithm runs in polynomial time in the Turing machine, will
it run in polynomial time in the arithmetic model?
Is an algorithm running in polynomial storage space defined the same under the Turing machine and the arithmetic model?

Thanks and regards!


texts: sentiment analysis by sentence similarity

texts: How can sentence similarity be used for sentiment analysis? I know we have sentence Bert which can use cosine sim to measure the distance between to vectors (the sentence embeddings), but has anyone used to for sentiment analysis specifically?


texts: Is there a name/algorithm for this problem related to set cover and CSP?

texts:
Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy multiple graduation requirements (e.g., writing, quantitative literacy, and art), each class may only count for up to two graduation requirements for a single student. We wish to be able to determine the mapping of courses (within a given transcript) to graduation requirements that satisfies the most graduation requirements in order to see if a student can graduate, and, if not, what graduation requirements are unmet. I've tried writing this up semi-formally:

Given:

A set of graduation requirements $\cal G$.
A set of classes $\cal C$ offered at the college.
A map ${\cal M: C} \rightarrow 2^\cal G$ indicating which classes fulfill which requirements. A given class can fulfill anywhere from 0 to $|\cal G|$ requirements.
A set of classes $\cal T$ (for transcript) $\subseteq \cal C$.

Determine:

A set $\cal S$ of $(c, g)$ pairs, where $c \in \cal T, g \in \cal M(c)$ that maximizes coverage of $\cal G$ but contains no more than 2 pairs with the same $c$.

Is there a name and known algorithm to solve this problem?


texts: I need clarification about DFA's and DFA acceptable languages

texts:
In class yesterday we went over DFA's and DFA acceptable languages.  An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$.  The reason given was that the machine would need an infinite amount of states.

But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?

Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states.  But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

I think I must be misunderstanding something crucial here.


texts: What is the difference between expected cost and average cost of an algorithm?

texts: While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.


texts: Machine Learning: What program will derive the underlying algorithm in this series?

texts:
This is a machine learning question. Given this series of categorical data, what program will derive the underlying algorithm and predict what comes next in the series?

Here is the series:

B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, ...

Anyone with knowledge of computer science may quickly realize that this series is simply counting in binary with "A" substituted for "0" and "B" substituted for "1". This is true, but...

the program that predicts what comes next must do so only by manipulating the symbols given in the series. It must not use hard-coded knowledge of binary counting.

I realize many patter recognition algorithms are available but I haven't seen how any can solve this deceptively hard problem.

-Edit-

Based on the votes that this problem is insolvable, I've done some refactoring and posed the question another way, with more constraints, here:
What program will derive the underlying algorithm in these question-answer pairs (updated)?


texts: Algorithm for fewest number of moves with artificial minimum

texts:
I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.

To summarize, I built an undirected graph with edges representing possible moves of 1's, 10's, 100's, etc to get from one value to another.

public static UndirectedGraph<int, IEdge<int>> GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph<int, IEdge<int>>();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i <= 10000; i++)
    {
        for (int j = i+1; j <= 10000; j++)
        {
            // only add edges if difference is base of 10
            if (j - i == 1 || j - i == 10 || j - i == 100 || j - i == 1000)
            {
                graph.AddVerticesAndEdge(new UndirectedEdge<int>(i, j));
            }
        }
    }
    return graph;
}

So, the minimum distance from 46 to 121 is 8 steps/moves:

add 100 (146) - 1 move
subtract 10 (136) - 1 move
subtract 10 (126) - 1 move
subtract 1 five times (121) - 5 moves

Let's say the minimum number of steps through the graph has to be greater than 8 e.g. 10, 15, etc.

For example, a game application could stipulate that you must move at least 11 times in the problem above, so a possible answer could be:

all steps above (8 moves)
add 1 - (9)
subtract 1 - (10)
add 1 - (11) (we're at the minimum number of moves here, but we're at 122)
subtract 1 - (12) (correct answer)

So, these "dummy" moves are allowed, but aren't there scenarios where simple dummy moves may outnumber a shorter path to the answer?

I think I found an Eppstein implementation in C# that should give k-shortest paths, but can anyone explain the meaning of the vertices with two letters? e.g. What does the vertex "A,E" mean, and how can it have a single edge between "B,I"?

g.CreateEdges("A,E", "B,I", 20, "alpha");

What if I had to specify an odd or even number of moves?

Can this be done with the existing graph, or is there another graph structure that would support it? Weights, directions? Could I build the graph differently to describe the criteria e.g. not adding edges until certain number of edges exist back to the source, but then I would need Dijkstra on every iteration at build time


texts: Is there an algorithm for random sampling from a priority queue with probability proportional to priority?

texts:
Suppose I want to randomly sample from a large set of items, each of which has a "score".  I want my probability of sampling to be proportional to the score.  One simple way to achieve this is divide each score by the total, then randomly sample based on each probability.  This is at least O(N), and running it the next time will be O(N) as well since we have to renormalize.  Inserting is also O(N) because we have to renormalize.  I'm wondering if there is way we can utilize a priority queue or binary tree to make sampling and insertion less costly.
I am thinking for example, store every item in a priority queue, then to sample:
Look at the current item's score, the left item's sum of scores, and the right item's sum of scores.  Normalize by dividing each by the sum of all three, and sample the result.  If the result is the left, rerun the algorithm on the left node.  If the result is the right, rerun the algorithm on the right node.  Otherwise if it's the current node, remove the node and return it as the sample.  It is guaranteed to terminate when it gets to a leaf.  We would have to do some extra work to keep track of the sum, but I think this would make all operations O(log(N)).  Not sure this would sample with the actual required probability or if the time complexity is correct.  Is there any existing work on this?
Edit: I think I found the answer: https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res


texts: Optimal wagering to minimize expected time to reach a target payoff

texts: Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ and lose that amount with probability $1-p$ ($p$ is known). We wish to reach target amount $T$ in the minimum expected number of plays. At each stage we can wager a different amount. To make the expectation simpler to compute we can assume that if the current amount goes below $S$ we incur a large number of additional plays, say $M$, and then our amount returns to $S$. I have a feeling that the optimal strategy for this situation depends on $p$ (and possibly $T$ and $M$) but I can't figure out how to show the optimal strategy.


texts: Can you do operations on the halt state of a turing machine?

texts: As the title says, can operations be performed by a turing machine after it has transitioned to the halt state like shown in the following image.


texts: Are there any practical drop-in replacements for BSTs in the case where data are integers?

texts:
There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement the key ordered dictionary primitives in sublogarithmic time.

However, to the best of my knowledge, all three of the above data structures are interesting only in a theoretical context, since their hidden constant factors are so large that they're effectively impractical. (I may be wrong about that, though!)

Are there any integer data structures that support sublogarithmic query times in theory which are also efficient in practice?


texts: Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly code

texts:
this is a piece of Assembly code

section .text
    global _start       ;must be declared for using gcc
_start:                     ;tell linker entry point
    mov edx, len    ;message length
    mov ecx, msg    ;message to write
    mov ebx, 1      ;file descriptor (stdout)
    mov eax, 4      ;system call number (sys_write)
    int 0x80        ;call kernel
    mov eax, 1      ;system call number (sys_exit)
    int 0x80        ;call kernel

section .data

msg db  'Hello, world!',0xa ;our dear string
len equ $ - msg         ;length of our dear string

Given a specific computer system, is it possible to predict precisely the actual run time of a piece of Assembly code.


texts:
Find any kind of grammar for the language L = {w ∈ Σ* | in w there
  are twice as many a's than b's} and reason its correctness.

Where w means word and Σ means alphabet, in this case obviously made up of a,b.

So I imagine I can build a NFA for the language and then "transform" that NFA into a regular grammar.

A NFA for that language should look like that:

The regular grammar is G = ({A,B,C}, {a,b}, P, A)

P : A → aB, ε (where ε is the empty word)
    B → bC
    C → aA

How would you show the correctness of that grammar though? I think it's not sufficient to say that the NFA terminates if and only if you start reading an a, then a b and end with an a, all that in a loop. Thus twice as many a's than b's.

Is it correct like that and is there a better way of doing it?


texts: Class of languages recognizable by n-bit formulas of size at most $T(n)$

texts:
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-in=0 for the IN nodes
fan-out=0 to exactly one node (the OUT node)
Unbounded fan-out to the rest of the nodes (but the OUT node)

A Boolean formula is a Boolean circuits with fan-out $\leq$ 1 to all of the nodes.

Let us denote by $C(T(n))$ the class of all languages recognizable by n-bit formulas of size (in the meaning of Boolean circutit size) at most T(n).

Let us denote by $\text{Size}(T(n))$ the class of all languages recognizable by n-bit Boolean circuits of size at most $T(n)$.

What is the relationship between $C(T(n))$ and $\text{Size}(T(n))$?
Is $C(T(n))$ a well-known class? What is its name in the literature?


texts: I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data.  I know that PRNG produce recurring 'patterns, but google has revealed none that expressively produce gaussian distributions.  Do you have an recommendations ideally I'd like several suggestions to produce multiple different test datasets usable for automated testing.


texts: Why and how is a quantum computer faster than a regular computer?

texts:
I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.

How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?


texts:
We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all up. I understand the substitution part, but not how to simplify the end result.

One of the problems I am stuck on is $T(n)=2T(n/2)+n^3$ where $T(2)=c$, When I sub in $n=2^m$ and $S(m)=T(2^m)$ I get:

$S(m)=2S(m-1)+(2^m)^3$

$S(m-1)=2S(m-2)+(2^{m-1})^3$

...

$S(3)=2S(2)+(2^{3})^3$

$S(2)=2S(1)+(2^{2})^3$

$S(1)=c$

Now because there is a coefficient on the right side we have to multiply each equation by a power of 2 so we can sum them.

$S(m)=2S(m-1)+(2^m)^3$

$2*S(m-1)=2^2S(m-2)+2*(2^{m-1})^3$

...

$2^{m-3}*S(3)=2^{m-2}S(2)+2^{m-3}(2^{3})^3$

$2^{m-2}*S(2)=2^{m-1}S(1)+2^{m-2}(2^{2})^3$

$2^{m-1}S(1)=c*2^{m-1}$

So sum these and we get:

$S(m)=(2^m)^3+2*(2^{m-1})^3+2^2*(2^{m-2})^3+...+2^{m-3}(2^{3})^3+2^{m-2}(2^{2})^3+c*2^{m-1}$

And this is where I get stuck, how can I simplify this? I tried dividing by $(2^m)^3$ but that came out to a awful mess. The other two I'm having trouble with are $T(n)=16T(n/4)+n^2$ and $T(n)=7T(n/2)+n^2$ Any help would be appreciated.


texts: Is there a way to compute time without system clock

texts:
I was thinking about any method where we can use RAM I/O speed, to calculate time, let's say for example:
RAM transfer rate is 1000 MB/s, so when it's half full (about 500 M Bytes written), by dividing 500 by 1000 we get the time which is epoch + 0.5 seconds
so all in all we have three routines:

one for writing data (zeros for example) into RAM
another one for checking when a specific size is full
and the third for calculating time

  Note: Sorry if it sounds stupid, because this is not my study field,


texts: Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?

texts:
I just found out by luck that

 Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min()

For example,
Consider a sorted array, {1 43 65 97 98 99 101}

Abs(1-43-55-97-98-99-101)= 101-1

Does anyone know why?

Thanks in Advance.


texts: Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?


texts: find the missing number in a block of 3 numbers

texts:
Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.

eg: 11122333 : Missing number 2
11122233344455666 Missing number 5

I think we can't do better than just going from beginning to the end and checking the count if a specific number count is less than 3.

s = "11122233344455666"
count = 1
flag = 0
for i in range(0, len(s), 3):
    if i+2 < len(s) and s[i] != s[i + 2]:
        print s[i]
        break
    elif i+2 >= len(s):
        print s[i]
        break


texts: Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children

texts:
How to prove
In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.


texts: Are empty-set languages recursively enumerable?

texts:
Are languages whose sets are empty recursively enumerable or recursive? For example, consider the language $L$ $\subseteq$ {0,1}*:

  $L$ = { $w$ | $w$ consists of only 0's} $\cap$ { $w$ | $w$ consists of only 1's }

I believe this language creates an empty set. There are many different ways to design a Turing Machine that decides that whether word $w$ is in $L$. In that sense, $L$ seems recursive. Further, there are many different machines that can return the empty set. Any of these them would effectively "enumerate" the members of L, even though there are none.

My gut tells me to reject these conclusions. Could anyone steer me in the right direction? Any guidance would be much appreciated.


texts: Determining properties of linear code from generator matrix

texts:
I have a problem in error-correcting codes.

Say we have a generator matrix of a linear binary code

$$g=\begin{pmatrix}
10011 \\
01101
\end{pmatrix}
$$

  Q1: How many different codeword do we have? How many code bits can the code correct?

Say the generator matrix of a $(6,2)$ binary code is
$$g=\begin{pmatrix}
101001\\
011111
\end{pmatrix}$$

  Q2: How many errors can it guarantee to detect?

My try:

For Q1:

The way I find the number of codeword is count the number of rows in $g$ and raise it as a power to 2. So the answer is $2^2=4$.

For detecting and correcting I’m not sure, should I find the hamming distance and subtract 1?

I hope someone can explain to me how I can find the number bits I can detect and correct.


texts: Can algorithms of arbitrarily worse complexity be systematically created?

texts:
We’ve all seen this:

Can we get worse?

Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation?

Part 2: If they can, can algorithms of arbitrary complexities be systematically generated?

Part 3: If such algorithms can be generated, what about programs implementing those algorithms?


texts: Assumption: A PSPACE-hard problem can be solved in polynomial time

texts:
Under the assumption that a PSPACE-hard problem A can be solved in polynomial time, is the following argumentation valid?

Since every problem in PSPACE can be reduced to A in polynomial time, every problem in NP which is a subset of PSPACE is included. That means that each Problem in NP is solvable in polynomial time and therefore P = NP.

Since coNP is a subset of PSPACE as well, we can argue that every problem in coNP can be reduced to A and therefore be solved in polynomial time as well, which means that P = coNP.

Therefore we can say that P = NP = coNP.

I don't see a problem with this argumentation at the moment, but it seems a bit too simplistic to me, so is this a valid way of arguing for the equality above?


texts:
I am still confused over my professor's explanation on why this problem is not a DFA.

The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA

My professor explained it as that it was because the DFA could not store the $k$ iterations in memory. But I still don't get it. In my mind, you just draw states $k$ number of times for $p$ and then $q$.

What's wrong with my logic?


texts: Is the language of TMs that decide some language Turing-recognizable?

texts:
Is the language

$\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$

a Turing-recognizable language? I think it's not,  as, even if I am able to tell somehow that a Turing machine halts for some input there are still infinite strings to check for. Similarly I think that this problem is not even co-recognizable. Am I right? If yes is there a more precise proof ?


texts: Is this theorem about left-factored grammars correct?

texts:
I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor:

  A CFG grammar cannot be left-factored if all elements in the FIRST-set of one factorizable rule belong to the FIRST-set of the alternative rule.

Mathematically speaking:

$$
A \rightarrow \alpha\beta_1 | \alpha\beta_2 , \forall x \in \text{FIRST}(\alpha\beta_1)
\wedge x \in \text{FIRST}(\alpha\beta_2) \implies \text{Cannot left-factorize}
$$

Is it correct? I think it is not!

Consider grammar rules $A \rightarrow aB | a C$ This thing can be left-factorized in: $A \rightarrow aD; D \rightarrow B|C$. But considering the theorem such a grammar is not supposed to be left-factorizable because $\text{FIRST}(aB) =\text{FIRST}(aC) = {a}$.

Which one is the correct version of this theorem? Thankyou


texts: Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

texts:
Consider a nondeterministic Mealy machine, $M$, defined as follows:
$M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where

$Q$ is a finite set of states
$\Sigma$ is an input alphabet
$\Delta$ is an output alphabet
$\delta : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q)$ is the transition function
$\tau : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(\Delta)$ is the output function
$q_0 \in Q$ is the start state

Let $M(x)$ for $x \in \Sigma^*$ denote the set of all strings that $M$ could output on input $x$.  Note that $M$ could fail to process the entirety of its input, and thus a string is output only if $M$ processes all of its input.  Also, we define, for $L \subset \Sigma^*$, $M(L) = \bigcup\limits_{w \in L} M(w)$.  Given this, if $L$ is regular, does it follow that $M(L)$ is regular?

I've attempted to solve this by first showing that for every non-deterministic Mealy machine, there exists an equivalent deterministic Mealy machine.  By "equivalent" I mean that the input-output behavior of the two is identical.  The problem, however, is that the output function for a deterministic Mealy machine can only output a single character at a time.  How, then, could I get the simulating deterministic Mealy machine to output a set of strings?


texts: Shortest cycle containing a particular edge?

texts:
Let $(u,v)$ be an edge in the graph, I have to develop an algorithm to find the length of the shortest cycle containing this particular edge.
Also, the graph has only positive edge weights

Here's what I have so far, and I wanted to know if I am in the right path (or, if this is correct):

•Remove $(u,v)$ from the graph

•Compute the length of the shortest path from $u$ to $v$ in the modified graph

•Return $shortestPathLength(u,v)+weight(u,v)$


texts:
The (second) distributive law in boolean algebra is defined as

  $A + (B C) = (A + B) (A + C)$

But wouldn't it be correct to define it that way:

  $(A + (B C)\, ) = (A + B) (A + C)$

Because if you transform

  $(\sim D + \sim C) (\sim D + B + A) (C + \sim B + \sim A)$

to

  $\sim D + (\sim C (B + A) \, ) (C + \sim B + \sim A)$

it would be incorrect since * has higher precedence than +, so

  $(\sim D + (\sim C (B + A)\, )\, ) (C + \sim B + \sim A)$

would be correct, or am I totally mistaken?


texts: How does one generate all the terms of a multivariate polynomial algorithmically?

texts:
I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a specific point (in reality I will feed it vectors with a value for each polynomial and I want to evaluate the polynomial). So here is an example input output in pseudocode:

f(variables=[x1,x2],Degree=D) = 1+x1+x2+x1x2+x1^2+x2^2

when there is a general number of variables and Degree it gets tricky.

I noticed that this problem is equivalent to considering tuples/sequences with that satisfy the following:

$$ S_D = \{ (d_0, ..., d_N) : \sum^N_{i=0} d_i = D \}$$

then my answer would be the set:

$$ S^{*}_D = \cup^D_{d'=0} S_{d'} = \{ (d_0, ..., d_N) : \sum^N_{i=0} d_i \leq D \} $$

I started with an example to try to actually compute that set, say degree 3 and 3 variables. I considered N = 3 and got the tuples:

(3,0,0), (0,3,0), (0,0,3)
(2,1,0), (2,0,1)
(0,2,1), (1,2,0)
(0,1,2), (1,0,2)

I also tried higher numbers but I didn't really see an obvious way to generalize it wrt to N or D. Any hints on how to do it? (Also the full solution is welcome so I can implement it for my real task)


texts: Does keeping underflowed nodes unbalance the R-tree?

texts: When deleting nodes from an R-tree, if a branch underflows, then it's meant to be dissolved and its children are meant to be reinserted into the tree. But most R-tree implementations that I've seen just keep the node until it's completely empty. Does this lead to unbalanced R-trees?


texts: Why is average waiting time is the same for FIFO and LIFO

texts:
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:

  Support retrieval in first in, first out (FIFO) order. This is surely
  the fairest way to control waiting times for services. You want the
  container holding jobs to be processed in FIFO order to minimize the
  maximum time spent waiting. Note that the average waiting time will be
  the same regardless of whether FIFO or LIFO is used. Many computing
  applications involve data items with infinite patience, which renders
  the question of maximum waiting time moot.

Can someone please explain what is meant by minimizing maximum time spent waiting and why the waiting time is same for FIFO and LIFO?

Thanks


texts: Existence of a function between two functions $f$ and $g$ where $f \in o(g)$

texts:
Is this statement true?

For each two functions $f$ and $g$, where $f \in o(g)$, there exists a function $h$ where $f \in o(h)$ and $h \in o(g)$

Please note that I am using small $o$ notation.


texts: Description and semantics of program graphs

texts:
I'm working on a question which gives me a program graph and tells me to give a mathematical description of it. I'm aware that a program graph PG is a tuple

$(Loc, Act, Effect, \rightarrow, Loc_0, g_0)$

This is the question I'm trying to answer:

So far for $PG_1$ (one of the 2 transition systems) I have:

$Loc = \{k_1, k_2, k_3\},$ with  $Loc_0 = \{k_1\}$

$Act = \{\alpha_1, \beta_1, \gamma_1\}$

$Effects = \{Effect(\alpha_1, \eta) = \eta[x := x + 1]$,
$Effect(\beta_1, \eta) = \eta[y := y - 1]$,
$Effect(\gamma_1, \eta = \eta[y := y + 2]\}$

$\rightarrow = \{(k_1, \alpha_1, k_2), (k_2, \beta_1, k_3), (k_3, \gamma_1, k_1)\}$

$g_0 = $ ?

I'm aware that $g_0$ is the starting condition, but I'm not sure what it is in this case? Also for $\rightarrow$ I assumed this was done the same was it is in Transition Systems, if somebody could clarify whether or not this is the correct way to do it I would be really grateful.

Thanks in advance for any help.


texts: Size of order-preserving minimal perfect hash family

texts:
Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if  for every subset $M\subset U$ of size $m$  has at least one function $h\in H$ which is an over preserving minimal prefect hash.   It is shown in [1,2] that for every   $(U,m)$-OPMPHF $H$ obeys:

$$H=m! \cdot \left.\binom{u}{m}\middle/\left(\frac{u}{m}\right)^m\right.   $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $\log_2 |H|$ bits.

In particular, if $m=3,u=8$, we have that $|H|\geq 17.7$.

However, I think I can create as set of  $|H|=6$ functions for such family. For every $2\leq i\leq 7$ we define $f_i(x)$ to be equal $1$ if $x<i$, equal $2$ if $x=i$ and equal $3$ if $x\geq i$. Every function $f_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f_i$.

Do I miss something in my analysis?

[1] Havas and Majewski, Optimal algorithms for minimal perfect hashing

[2] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984


texts: Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

texts: I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the new strings. But I don't think there's such a thing in CFGs. Second approach was to produce the strings of the language top-down. Starting from the last string $a^{2^{20}}$ and removing an $a$ each time till epsilon but I don't think that's achievable either. Any ideas?


texts: Does the language of Regular Expressions need a push down automata to parse it?

texts:
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular expresssions?

I assume it must be a push down automaton because the presense of brackets means the need to count and a DFA/NFA cannot perform arbitrary counting. Is this assumption correct? For example, the expression a(bc*)d would require a PDA so that the sub-expression in brackets is handled correctly.


texts: classify location of the expiry date on drug label and lot number

texts:
Is it possible that using the Machine Learning classification model we can classify/predict the LOCATION/ORIENTATION of the lot number and expiration date on different vials label?

If yes, possible approaches.

Update: So far what I have observed is with EAST model
https://arxiv.org/abs/1704.03155

one can locate text in the scene and then use OCR s/w like Textract to read those locations. Now, the real challenge is when you have lots of text available in the image vertical and horizontal and when you don't know where the particular text would appear in the image like expiry date - Is it possible to train a system to give just one or two locations which will be expiry date and lot number?

The challenge here I feel is the location but what features we would take to train as it's just text. I feel it's a classification problem with supervised learning but I may be wrong. Comment?

Thanks


texts: Will the machine ever reach on any other state other than start state?

texts:
Given a TM M, will it ever reach any other state other than start state if it starts with blank tape ?
Is the above problem decidable ?

I think that if a TM really reaches any other state other than start state then we can check the transitions and find out. But if it doesn't at any point of time then we can't say that it will never reach other state in future too so it results in infinite waiting.

So the problem is undecidable or R.E according to me but the answer is decidable.

Please tell me where am I going wrong .


texts: Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular

texts: Are there any closure properties which I can use to come up with a contradiction?


texts: How to uniformly sample a sorted simplex

texts:
I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should satisfy:

x + y + z = 1
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
x >= y >= z

My guess is all i have to do is uniformly sample a simplex (Uniform sampling from a simplex), and then sort the elements. But i'm not sure whether the result sampling algorithm is uniform.

Also, rejection sampling is not ideal for me, because i'll use this for high dimension.


texts: Extracting regex submatch boundaries without backtracking

texts:
I'm attempting to develop from scratch a simple regex engine.  I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index  and ending at index ."
It makes sense to me how to accomplish this using recursive backtracking.
However, I'd like my implementation of the search to use Thompson's multi-state approach.  Is this feasible?


texts: Why are ADT packages opened immediately after they are built, while existential objects opened as late as possible?

texts:
Section 24.2  in Types and Programming Languages by Pierce defines ADTs in existential types:

  A conventional abstract data type (or ADT) consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of
  some operations for creating, querying, and manipulating values of
  type T, and (4) an abstraction boundary enclosing the representation
  and operations. Inside this boundary, elements of the type are viewed
  concretely (with type T). Outside, they are viewed abstractly, with
  type A. Values of type A may be passed around, stored in data
  structures, etc., but not directly examined or changed—the only
  operations allowed on A are those provided by the ADT. ... We ﬁrst
  create an existential package containing the internals of the ADT:

counterADT =
{*Nat,
{new = 1,
get = λi:Nat. i,
inc = λi:Nat. succ(i)}}
as {∃Counter,
{new: Counter,
get: Counter→Nat,
inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  We can open it for example

let {Counter,counter} = counterADT in
counter.get (counter.inc counter.new);
> 2 : Nat

and then defines existential objects  in existential types:

  A counter object comprises two basic components: a number (its internal state), and a pair of methods, get and inc, that can be used
  to manipulate the state. We also need to ensure that the only way that
  the state can be queried or updated is by using one of these two
  methods. This can be accomplished by wrapping the state and methods in
  an existential package, abstracting the type of the state. For
  example, a counter object holding the value 5 might be written

c = {*Nat,
{state = 5,
methods = {get = λx:Nat. x,
inc = λx:Nat. succ(x)}}}
as Counter;

  where:

Counter = {∃X, {state:X, methods: {get:X→Nat, inc:X→X}}};

  We opens it for example:

let {X,body} = c in body.methods.get(body.state);
> 5 : Nat

and  compare ADTs and existential objects:

  when programming with ADTs, packages are opened immediately after they are built; on the other hand, when packages are used to model
  objects they are kept closed as long as possible—until the moment
  when they must be opened so that one of the methods can be applied to
  the internal state.

What does "when programming with ADTs, packages are opened immediately after they are built; on the other hand, when packages are used to model objects they are kept closed as long as possible" mean?

They are both opened in the binding parts of the let terms, which can be anywhere (not immediately) after they are built. So their timings seem to be the same to me.
What are the differences in the definitions of ADT and of existential objects in terms of existential types, which lead to the timing difference of their opening?

Thanks.


texts: Ideal value of d in a d-ary heap for Dijkstra's algorithm

texts:
I stumbled upon the following statement:

  By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time of $ O(m \log_{m/n} n) $ for the algorithm, an improvement over the $ O(m \log n) $ running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices

Applications of d-ary heaps

I don't understand why we choose to have a heap where nodes have exactly $ m/n $ children to speed up Dijkstra's algorithm. Remove min takes overall $ O(n \log_d n) $ time and  decrease takes $ O(m \log_d n) $, so total runtime is $ O(m \log_d n) $.

What I don't understand is say we have $ m=3, n=1 $, $ m/n $ gives 3, but $ O(m \log_3 n) $ is slower than $ O(m \log_4 n) $, so why not choose 4 as value of $ d $ instead? What motivates taking $ m/n $?

Thanks!


texts: Document definition in information retrieval

texts:
Is there common formal definition of Document in information retrieval field? In many researches authors don't define the term Document(maybe because it is evident for them). Wikipedia says "text file, document (computer science) a computer file that contains text" but it doesn't seem as common formal definition.

Do you know the common formal definition of Document, or, if not, do you know any researches where that term was defined?


texts: Why is this youtuber applying comparing two functions with O(n^2), by applying a contant to one of the functions?

texts:
Here is the video in question:https://www.youtube.com/watch?v=BpiMRyWoDu0&t=131s
F(n) and g(n) are both equal to each other since they both have a time complexity of n^2
What's the point of applying the constant c to g(n) to make it 2n^2? What is this trying to show us?
Additionally, why does the inequality include 'equal to'? When will 2n^2 ever be equal to n^2 + n + 3?
Further more, why has he written n >= 4? Where did the 4 come from? I understand why he wrote n >= 3 because n(n-1)is the same as n for time complexity purposes, therefore this becomes n >= 3


texts: Weak equivalent tree grammar for Context-sensitive word grammar?

texts:
Consider arbitrary context-sensitive grammar on strings $G_s$.

Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which yield language will coincide with $L(G_s)$:

$L(G_s)=\{yield(t)|t\in L(G_t)\}$ ?

Yield operator is as it defined in TATA book: it computes a
word from a tree by concatenating the leaves of the tree from the left to the right.

It is known, for instance, that for indexed grammars, context-free tree grammars have weak-equivalence to them in sense of strings language. Same property exists between regular tree grammars and context-free word grammars.


texts: Can expected "depth" of an element and expected "height" differ significantly?

texts:
When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that

$\qquad\displaystyle \mathbb{E}[d(k)] \in O(\log n)$

where $d(k)$ is the depth of the element with rank $k$ in the set of $n$ keys.
Intuitively, this seems to imply that also

$\qquad\displaystyle \mathbb{E}[h(T)] \in O(\log n)$

where $h(T)$ is the height of treap $T$, since

$\qquad\displaystyle h(T) = \max_{k \in [1..n]} d(k)$.

Formally, however, there does not seem to be an (immediate) relationship. We even have

$\qquad\displaystyle \mathbb{E}[h(T)] \geq \max_{k \in [1..n]} \mathbb{E}[d(k)]$

by Jensen's inequality. Now, one can show expected logarithmic height via tail bounds, using more insight into the distribution of $d(k)$.

It is easy to construct examples of distributions that skrew with above intuition, namely extremely asymmetric, heavy-tailed distributions. The question is, can/do such occur in the analysis of algorithms and data structures?

Are there example for data structures $D$ (or algorithms) for which

$\qquad\displaystyle \mathbb{E}[h(D)] \in \omega(\max_{e \in D} \mathbb{E}[d(e)])$?

Nota bene:

Of course, we have to interpret "depth" and "height" liberally if we consider structures that are not trees. Based on the posts Wandering Logic links to, "Expected average search time" (for $1/n \cdot \sum_{e \in D} \mathbb{E}[d(e)]$) and "expected maximum search time" (for $\mathbb{E}[h(D)]$) seem to be used.
A related question on math.SE has yielded an interesting answer that may allow deriving useful bounds on $\mathbb{E}[h(D)]$ given suitable bounds on $\mathbb{E}[d(e)]$ and $\mathbb{V}[d(e)]$.


texts:
Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?

I see some problems that I will explain with few examples. I will use a prefix instead of a postfix notation, so evaluation takes place from left to right.

Duplicate an argument seems trivial:

drop A B  ->  B

However, we can not forget that A is unevaluated, so the previous example only work for literals or quotations, but not for unevaluated code:

drop 123 B      ->  B
drop "abc" B    ->  B
drop [+ 1 2] B  ->  B
drop + 1 2 B    ->  1 2 B  -- NON SENSE!

This can be solved in two ways. First, we can impose some structure (unflat) to the code based on the functions arity in the parsing stage:

drop + 1 2 B    ->  drop [+ 1 2] B  // at parse time
drop [+ 1 2] B  ->  B               // at run time

The problem with this approach is that we lose all the benefits of concatenative programming (for example, flatness and multiple return values). In fact, we are converting function composition to function application in prefix notation... In this case:

dup + dup 2 3

Naively translates to:

dup [+ [dup 2] 3]  ->  dup [+ 2 2 3]  // `+` arity mismatch. What to do with the extra value? Which one is it, 2 or 3?

But it result in an strict language is:

4 4 3

The second solution is to instruct the evaluator to reduce the stack just enough to get as many arguments as the current word needs:

drop + 1 2 B  ->  drop 3 B  ->  B

Looks good, but the target of lazy evaluation is to evaluate arguments only when needed. In this case we are evaluating + 1 2 needlessly. It is not a big problem until we found:

drop + bottom 2 B  ->  bottom

What contradicts the expected call-by-need semantics:

drop + bottom 2 B  ->  B


texts:
In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:

  Insertion into a full array can be handled by resizing, i.e.,
  allocating a new array with additional memory and copying over the
  entries from the original array. This increases the worst-case time of
  insertion, but if the new array has, for example, a constant factor
  larger than the original array, the average time for insertion is
  constant since resizing is infrequent.

I grasp the concept of amortization that seems to be implied here, yet they seem to imply that in other cases, a newly allocated array could possess a constant factor smaller than the original array. Is that so? What does "constant factor" mean in this particular context? I'm having trouble understanding what's being said here.


texts:
I'm trying to implement a simple image segmentation application that accepts an initial contour and evolves it to compute a refined contour in successive iterations. I'm taking some inspiration from the explanation provided here:
https://profs.etsmtl.ca/hlombaert/levelset/

I'm having trouble understanding what exactly the author means when he writes the formula for the derivative of the surface with respect to time:

In particular, I am unsure how to compute the left and right side finite difference for every point in the image. While there are countless possibilities for computing the gradient using central differences (Sobel filter, Scharr filter etc.), a quick online search revealed nothing of the sort for computing left and right finite difference.

From what I can understand, one would have to compute the left and right side finite differences separately for the horizontal and vertical directions. So to compute the right side finite difference, one would convolve the image separately with a row filter $[-1, 1]$ centered at -1 and a column filter $[-1, 1]^T$, also centered at -1.

But then the question arises: how to combine the outputs from both these convolution operations. Of course the simple, logical approach would be to compute the L2-norm of the two outputs for each point:

$G=\sqrt{G_x^2 + G_y^2}$

where $G_x$ is the output at $(x,y)$ obtained by convolving the image with the row filter, and $G_y$ is the output obtained by convolving the image with the column filter. But I suspect this is incorrect, since this approach would lead to $G$ always being positive, thus making the $min[0, \Delta^{+x}\phi(i,j)]^2$ term in the first equation above pointless.

Can anyone point out where I'm going wrong and what I should actually be doing?


texts: How to prove regular languages are closed under left quotient?

texts:
$L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language
$$w^{-1} L := \{v \mid wv \in L\}$$

How can I prove that $w^{-1}L$ is regular?


texts:
I have to prove or disprove the following identities:

$(RS+R)^*RS=(RR^*S)^*$
$(R+S)^*S=(R^*S)^*$
$S(RS+S)^*R=RR^*S(RR^*S)^*$

So what I tried:

Not same because LHS cannot generate $\epsilon$ while the RHS can.
Not same because LHS can generate $\epsilon$ while the RHS can.
Not same because LHS is the set of strings starting with $s\in S$ and ending with $r\in R$, so can generate $sr$ but the RHS cannot generate $sr$ .

Correct me please if I am wrong.
EDIT:
As Nathaniel suggested, for 2. ''Not same because LHS cannot generate $\epsilon$ while the RHS can.''


texts: Binary search in log time on a Turing Machine

texts:
I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :

Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted array $A$) in $\log$ time ? That is, is it possible to simulate random access on a TM ?

My thoughts so far are that it is not possible, because the memory of a TM has to be accessed sequentially, e.g. in binary search, reading the element at $n/2$ in the array (first comparison for binary search) takes at least $n/2$ steps.

If it is indeed impossible, does the same hold for structures like binary trees ?


texts: Walk around a coordinate in circular order to a distance of N

texts:
For my development purpose, I need to work on all the 2D coordinates (in whole number) around [0,0] from 0 to N distance. For example, with N=1, I need

N0: [0, 0]
N1: [-1, -1] [0, -1] [1, -1] [1, 0] [1, 1] [0, 1] [-1, 1] [-1, 0]

The order is important. I want to walk these values in a circular way, starting from 0, incrementing the distance each round.

I first created two for-loops, from -N to N on each axes, but the resulting order is the one as you read a book: from top left to bottom right.

Here's the order I aim (the first coordinate to walk on each circle is not important):

Here's a first algorithm I tried, in pseudo code

int totalSize = (2*N+1, 2)*(2*N+1, 2)
Vector2[] coordinates = new Vector2[totalSize]
int index = 0
coordinates[index++] = new Vector2(0, 0)
for (int d = 1; d <= N; d++) {
    for (int x = -d; x <= d; x++) {
        coordinates[index++] = new Vector2(x, -d)
        coordinates[index++] = new Vector2(x, d)
    }
    for (int y = -d+1; y <= d-1; y++) {
        coordinates[index++] = new Vector2(-d, y)
        coordinates[index++] = new Vector2(d, y)
    }
}
for (int i=0; i<coordinates.Length; i++) {
    print(coordinates[i])
}

But:

It seems too cumbersome. I don't like the creation of a scructure that retains the coordinates. And 4 for-loops seems not optimized.
The order of the circles is ok, but the order inside each circle is not the one I described.
I have the feeling trigonometry can help me, but I can't see how to implement it on discrete values

Any idea?


texts: determine the language of the independent set problem

texts:
Given an undirected graph $G = (V,E)$ an independent set is a subset of nodes $U ⊆ V$, such that no two nodes in U are adjacent.

In the independent set problem, $G = (V,E)$  is an undirected graph, $k \in \mathbb N_{>0}$ and we need to decide, if there is an independet set with $|I| = k$.

I want to determine the language $L_P$ which is related to this decision problem.


texts: Linear programming: reduce a contstraint that includes minimun

texts:
I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or introduce additional variables) to turn this into a linear programme?

In other words, I have the problem that looks like the following:
$$
\mathbf c' \mathbf x \to \min,
$$
s.t.
$$
A \mathbf x = \mathbf b,\quad x_1 = \min(x_2, x_3).
$$

Update: I thought about substituting the constraint with $\min$ to the following pair: $x_1 \le x_2$ and $x_1 \le x_3$. However, this doesn't work if $x_1$ has a positive coefficient in $\mathbf c$, which is exactly the case for me. In fact, all the entries are positive in $\mathbf c$.


texts:
Are there countable infinte decision problems or uncountable infinite?

Thank you


texts: How is this lamda function beeing executed in an example for the Y combinator

texts:
I have spent a few hours now trying to understand how the Y Combinator is working and how it allows us to construct recursive functions with higher order functions.

I have been going through this derivation http://mvanier.livejournal.com/2897.html which is using the factorial function for explanation which I find quite helpful but at some point I am always getting lost.

I still understand this part

  (define (part-factorial self)
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))
     (self self)))

  (define factorial (part-factorial part-factorial))
  (factorial 5) ==> 120

We have a function part-factorial which takes as a formal parameter self and applies it as argument (self self) to the first lambda function. So inside the first lambda f will evaluate to (self self) which in case of the factorial function will evaluate to (part-factorial, part-factorial). So in the second lambda then if we take 5 as our n the call to the function f will evaluate to part-factorial part-factorial 4 which will start the recursion.

After a few syntax changes we now define the functions as

  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

  (define factorial
    ((lambda (x) (x x))
     (lambda (self)
       (almost-factorial (self self)))))

  (factorial 5) ==> 120

And at this point I am confused. I understand the almost-factorial function as it is pretty much unchanged compared to part-factorial however the new factorial function is unclear to me, from a syntax perspective. I don't understand anymore which lamda will be executed with which parameters and in which order.

Could anybody explain to me the execution of this function?


texts: Proving correctness of connected algorithm

texts:
Okay, so a graph $G = (V, E)$ is (fully) connected if and only if for every pair of vertices $u, v ∈V,$ $u$ and $v$ are connected in $G$.

And that if the vertex set is $V = \{0, 1, . . . , n−1\}$, then we can represent
a graph in a program as a two-dimensional n-by-n array $A$, where the entry $A[i][j]$ is set to $1$ if vertices $i$ and $j$ are adjacent (the edge), and $0$ if they aren’t.
The following algorithm takes as input such an array, and returns True if the algorithm is connected, and False otherwise.

def connected(A):
    n = len(A) # This is the number of vertices in the graph.

    # First, set diagonal to 1, since every vertex is connected to itself.
    for i in range(n):
        A[i][i] = 1

    for q in range(1, ceil(log(n)) + 1): # Main Loop: q =1,2,...,ceil(log(n))
    A1 = new n by n array containing all zeros # UPDATE: Assume this takes n*n steps.
    # Find new connectedness information
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if A[i][k] == 1 and A[k][j] == 1:
                    A1[i][j] = 1 # UPDATE: A1 stores new connectivity
                                 # information.

    for i in range(n): # UPDATE: Change A to store the new connections.
        for j in range(n):
            if A[i][j] == 0: # If A[i][j] is already 1, don't need to update.
                A[i][j] = A1[i][j]

    # Check if the graph is connected at this point.
    all_conn = True
    for i in range(n):
        if A[0][i] == 0:
            all_conn = False
            break

    if all_conn:
        return True
    # The loop has ended and *not* returned early.
    return False

So as you can see, this algorithm starts with an adjacency matrix $A$ and continually updates the entries of $A$ to represent new connectedness relationships between pairs of vertices. Essentially, at each iteration of the innermost loop, the algorithm checks whether vertex $k$ is connected to both $i$ and $j$; and if so, it records the fact that $i$ and $j$ are also connected.

I need to prove the the following predicate, where $G$ is a graph, $u$ and $v$ are vertices in the graph, and $d\in \mathbb{N}$.

$$PathLength(G,u,v,d):\text{"there is a path in G between u and v of length at most d"}$$

Using this predicate, we can state the key property of graphs that makes the connected algorithm work: $\forall G=(V,E), \forall u,v \in V, \forall d \in \mathbb{N}, PathLength(G,u,v,2d)\Leftrightarrow (\exists w \in V, PathLength(G, u,w,d) \wedge PathLength(G,w,v,d)$

Let $n\in \mathbb{Z^+}$ with $n>1$, and consider running connected on an n-by-n adjacency matrix representing a graph $G = (V,E)$, where $V = \{0,1,...,n-1\}$.

Prove by induction on $q$ that at the end of iteration $q$ of the Main Loop, the following is true:$$\forall i,j \in V, A[i][j] = 1 \Rightarrow PathLength(G, i, j, 2q)$$


texts: Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

texts:
We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?


texts: How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?

texts:
The recurrence I have is

$T(n) = 2T(\sqrt{n-1} + 2) + 1$

I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm supposed to find the height of the tree but I have no idea how.

I need to solve this recurrence only using trees. And I can't find anything about solving recurrences with trees and square roots as parameters.


texts: Would a modern processor/ALU process data bit or byte wise?

texts:
We look at 32 bit and 64 bit systems with octal-core processors.
What does all that mean? As in, does it have 8 processors that operate bit wise?
Or do they all operate on 32/64 bit blocks.
I was studying Crypto with stream and block ciphers. And this has been confusing me now.
Also, is it fair to say that a computer has no value for "bytes" as there aren't anything more than our way of grouping bits to make them more convenient to read?


texts: Find the smallest set of strings which "covers" a given set of strings (coverage = containing as substring)

texts:
Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds:

$\forall t \in T(k,l): k \leq |t| \leq l$
$\forall s \in S \ \exists t \in T(k,l): t \subset s$ (meaning: $s$ is containing $t$ as a contiguous substring).

I would appreciate any help regarding this problem. I see that I could generate the set of all strings with length between $k$ and $l$ then consider the power set but I think there must be a better way to solve this.

I'm not even sure how hard this problem is (I think there may be a reduction for the set cover problem which means it is $NP$-complete but I really don't know) or if there are any good approximation (or maybe exact) algorithms available.

I would like to solve this problem primarily in practice. Typically, $3 \leq k \leq l \leq 10$ holds, $|S| \approx 2000$ and the lengths of the elements in $S$ can vary from 10 to 50 mainly.


texts: if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$

texts:
I'm looking for a proof to the claim stated in the title:
if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$.
I read the proof from my professor's recitation, but couldn't understand it, and I was hoping to find more easy-to-understand version of that proof.
It goes something like that:
Let $L\in NP\cap Co-NP$ be an $NPH$ problem, and let $L'\in Co-NP$, our goal is to first show that $L'\in NP$.
We know that there exist a Cook reduction from $L'$ to $\bar{L'}$ (any problem can be reduced to its complement with Cook reduction), and since $\bar{L'}\in NP$, we also know that there exist a Karp reduction from $\bar{L'}$ to $L$.
So by transitivity, we have a reduction from $L'$ to $L$.
The only problem is, $NP$ is not closed under Cook reduction (if a problem $A$ can be reduced to a problem $B\in NP$ with Cook reduction, that doesn't mean that $A\in NP$...)
So define the relation $R_{L'}$, associated with $L'$ (meaning $R_{L'}$ is the search problem of $L'$) as follows:
$R_{L'}=\left\{(x,[(z_1,\sigma_1,w_1),(z_2,\sigma_2,w_2),...(z_t,\sigma_t,w_t)]) \right\}$
Now if we can prove that $R_{L'}$ can be decided with a deterministic polynomial verifier, and that for all $(x,y)\in R_{L'}$, $|y|\leq p(|x|)$ for some polynomial $p$, we're done, and that will prove that $L'\in NP$...
Now comes the part where I really lost him, he starts to rattle on and on about "questions" and "answers", and I completely lost track.
Can anyone provide a link that explains the rest of that proof more clearly?


texts: Proving by induction that a function gets called n-1 times

texts:
This is the pseudo-code from the problem:

procedure Foo(A,f,L)

   Precondition: A[f..L] is an array of integers, f,L, are
                 two naturals >=1 with f<=L.

   if (f=L) then
     return A[f]
   else
     m <-- [(f+L)/2]
     return min(Foo(A,f,m), Foo(A, m+1,L))
   endif

The Question:

Using induction, argue that Foo invokes min at most $n-1$ times.

I am a little lost on how to continue my proof for part (iii). I have the claim written out as well as the base case. Which I believe it to be $n\geq2$. But how do I do it for $k + 1$ terms? Since this is a proof by induction.

Thanks


texts: Proving undecidability of a language with mapping reductions

texts:
I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to prove is undecidable to solve a known undecidable language.
However, with mapping reductions, am I right in assuming these calls aren't needed? In addition, in the link provided, the solution pseudocode says
For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

How can you say "if it accepts"? How can you determine this, what if it loops forever and this is never found out? Why can you make such statements with a mapping reduction but not with Turing reductions? Could I make a statement like "if M halts on w, do ...". I mentioned this to my teaching assistant and he said you can't make any statements like these unless you're accessing an oracle and doing a during reduction, but I see loads of examples which seem to show otherwise. Hopefully this makes sense


texts:
Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the spanning tree $T(V, E')$ of $G$ such as maximal distance between vertices in $T$ is minimal.

I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $\Theta(n^3)$ solution exists here, but no full solution is anywhere.

I believe this community would benefit if solution is described here.


texts: Finding Shortest Paths of weighted graph using stacks

texts:
I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall algorithm it is kinda of possible, but unfortunately I'm only allowed to use stacks (instead of matrices). I also looked for Dijkstra's algorithm but I could not get the relationship with my problem.

Clearly my aim is to get all shortest paths from one point to another one. As I mentioned I will just output the solution from my stack in a vector string. I guess I have to visit each node and what I am most afraid is of getting stacked in a loop or even loosing the track during the search.
Also note that this is not a directed graph. If  Dijkstra's algorithm is applicable here I would be very grateful if anyone of you would guide me and I would really appreciate any help, suggestion, idea or even a vision for not getting stacked in a loop or loosing the track while searching.

Thanks in advance.


texts: Finding maximum of $n$ many $m$-bit integers

texts:
Suppose you want to determine the largest number in an $n$-element set $X = (x_1, x_2, \dots , x_{n})$, where each element $x_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that solves this problem in $O(n + m)$ steps, where at each step, your algorithm compares one of the elements $x_i$ with a constant. In particular, your algorithm must never actually compare two elements of $X$!
My thoughts: I thought about making intervals $[1,2), [2,4), [4,8), \dots , [2^{m-1}, 2^m)$ and somehow associate comparisons with these ranges. But, all of them were in vain. Would be welcome to hear your ideas on solving this!


texts: Trying to tag parts of a word and keep track of any changes that happen to those parts

texts:
I'm a researcher working with a language that has gone through phonological changes through time.  I would like to tag parts of a word (i.e. prefix, stem, suffix) and then apply those phonological changes and then see what is left or different about the stuff that I tagged.

I'm currently using Python with some regex stuff to apply the changes so if I can do this using its NPL toolkit that would be perfect.  I've start to mess around with it but I haven't found anything that will work just yet.  I'm also not sure if this toolkit would be the best for this.

For example, I apply the following transformation to tag re, peat and ed in repeated:
$$
\begin{align}
  \mathtt{repeated}
  & \xrightarrow{\mathtt{rep} \mapsto \mathtt{rp}} \mathtt{rpeated} \\
  & \xrightarrow{\mathtt{ea} \mapsto \mathtt{e}} \mathtt{rpeted} \\
  & \xrightarrow{\mathtt{d}\$ \mapsto \epsilon} \mathtt{rpete} \\
\end{align}
$$

I would like to be able to find out what is left of the stuff I tagged.  So I'd like to see that r is all that is left of the prefix, pe is all that is left of the stem, etc.  Any help or direction is greatly appreciated!


texts: L(M)=L where M is a TM that can move right or stay, so L is decidable

texts:
Suppose that L(M)=L where M is a one tape TM that can move right or stay.

I need to Show that L is decidable.

I thought of reducing a PDA to this TM, since moving to the right is equivalent to popping and pushing some new symbol to the stack. and staying is the same as not touching the automata at all. but im not sure this is correct.


texts: Is it decidable if a given TM accepts infinitely many words in a fixed number of moves?

texts:
$L=\{\langle M \rangle \mid \text{There are infinitely many words accepted by M in less than 10 moves}\}$

I am having hard time understanding this language and I have several questions:

How is it possible to derive infinite amount of words in finite moves?
How can we determine if a word is or isn't in the language at all?
Why is this language decidable? I understand that it is because it halts on every input, but what are we looking for after 10 moves to decide if it will reject or accept?

Any further clarifications on this language will be highly appreciated.


texts: From my CS course, the Peterson's Algorithm and the Bakery Algorithm both are solutions which satisfy the 3 requirements of any solution to the critical section problem. a) What are their adv/disadv over each other , and b) if they already solve the critical section problem, why do we need semaphores?


texts: Exactly what is the difference between Finite Automata and Transition Graphs?

texts:
I haven't found a good enough answer by googling. Here's what i know:

TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to show transitions for all letters

Notes:

I am talking about plain TG's, not GTG's and DFA's only not NFA
Only thing i know about NFA's is that each a state can have multiple transitions for the same letter, so please keep that in mind if hte answer invloves NFA's
Links would be appreciated.


texts: Using closure properties to show that $a^n b^m a^{n+m}$ is not regular

texts:
I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular.

Can I say that the complement of $L$ intersected with $a^*b^*$ equals $\{a^n b^n \mid n \geq 0\}$ and since I know that $\{a^n b^n \mid n \geq 0\}$ is not regular, then $L$ is not regular?

Or would I have to use the pumping lemma?


texts: Calculating depth mask from different lighting

texts:
I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ?

Concept is to use - calculate height from shadow length

Lets imagine a have more images likes this.

And light source is moving, which is sun, and from time it's position, distance, orientation can be calculated.

Yellow lines are sun rays.

Those circles are brightest pixel previously(direction of raw) of a very dark pixel. considering them highest i'n my knowledge . And those green lines as shadow. How can I calculated the depth mask of this terrain.

I'm ignoring the fact that, object/terrain can be colorful - no reflection/absorption.


texts: Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

texts:
I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$
This last one is quite easy to get ($S\to aSb | Sb | b$), but still I am unsure on how to proceed.
I expect to manipulate the language by differentiating cases, and for example I found that if $n>m$, I will have to solve $a^{m+k}b^mc^rd^s, k\ge1$, and if $n<m$, I will have to solve $a^nb^{n+k}c^rd^s, k\ge1$, but, still I don't see the recursivity.


texts:
I have numbers $a$, $b$ and $m$, and I need to get the result of $\ \dfrac{a}{b} \mod m$.

The catch is that while $m \leq 10^9$, $a$ and $b$ can get extremely large ($2^{100,000}$), so I'm keeping them as a multiset of their prime factors.

I read about modular multiplicative inverse but I haven't found a way to use it in this problem and would appreciate any help.

Also, note that $m$ is not necessarily prime;


texts: Generating a fast permutation function over an integer range

texts:
Is there a way to generate a bijection over integers $F : [0..n) \rightarrow [0..n)$ that satisfies the properties:

$n$ is arbitrarily chosen and can be any positive integer
$F$ generates a pseudorandom, potentially biased permutation of its domain
$F$ is seedable and can be easily influenced to generate a different random permutation
The computational complexity of computing $F(i)$ for all $i$ is better than $O(n)$ (ideally, $O(1)$)
The computational complexity of generating $F$ itself is better than $O(n)$ (ideally, $O(1)$)

I have looked at Fisher-Yates, LCGs, LFSRs, minimal perfect hashing, and unique-permutation hashing, and haven't found anything that could tell me if this is possible.
I am mainly interested in this because I want a "scrollable" output of randomly-permuted integers, of which there may be an impractically large number to compute the entire permutation at once, but which will eventually all be consumed.
To optimize memory usage, it would be preferable to return a fixed number $k$ at a time. If such an $F$ exists, the algorithm could then fetch the next $k$ integers, and so on until the permutation is exhausted.


texts: How does a computer play a video while doing something else?

texts:
How is video playback done on a computer?  It's obviously not relying purely on the CPU, since video playback continues when a user performs another activity, such as typing into a YouTube comment field.  This task seems further complicated in the case of streaming video, where data presumably needs to be transferred from the network interface to the video/graphics controller.

EDIT: I should have made clear that I understand that the CPU switches among multiple processes and threads all of the time.  My question was meant to be more specifically about video playback.  Is the video processing done on the graphics chipset/card? Do those typically offer buffering? Or can it all be handled by a single-core CPU with time to spare for other tasks, or am I wrong to think that low-end CPUs can play back video without (not-network) delays?


texts: Is every graph with minimum degree $n/2$ connected?

texts:
Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
Decide whether the above claim is true or false, and give a proof of either the claim or a counter example.

I drew out a few examples and the claim seems to hold, and I cannot find a counter example to prove it is false, which leads me to believe the claim is true.  However, I am having a really hard time generating a proper proof.


texts: Are results after performing operations on AVL trees ambiguous?

texts: After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions exists that satisfy all AVL properties?


texts:
I'm trying to figure out how to create a CFG for univocalic words...

Univocalic words are words that have only one the same vowel letter throughout the word

Example:
September, Anna

Would appreciate any of your help..


texts: Could be solved a NP-complete problem in constant time?

texts: Under the assumption that P would be equal to NP, it could exist a NP-complete problem that is solved in constant time?


texts: Homomorphisms and isomorphisms in an equational calculus

texts:
Suppose we have an algebraic specification in the form: $\{S,F,w\}$ where $S$ are the sorts, $F$ are the functions and $w$ are the set of equations.
For example, the specification for natural numbers:

$S = \{\mathrm{int}\}$
$F = \{
         0: \mathrm{int}, \;
         \mathrm{succ} : \mathrm{int}\rightarrow\mathrm{int}, \;
         \mathrm{pred}: \mathrm{int}\rightarrow\mathrm{int}
       \}$
$w = \{
         \mathrm{succ}(\mathrm{pred}(x)) = x, \;
         \mathrm{pred}(\mathrm{succ}(x)) = x
       \}$

My question is, why and where do we need homomorphisms and isomorphisms in this case? How do homomorphisms and isomorphisms look like between algebras ?