texts:
I have that language $S=\{a^n b^m c^m\mid n,m \geq 0\}$.
How can I prove with the pumping lemma that it isn't regular? Can I use the concatenation closure and say that it's the language $L_1 = \{a^n\mid n\geq0\}$ and $L_2 =\{b^m c^m\mid m \geq0\}$ prove that $L_2$ isnt regular so $L_1 L_2 = S$ is not regular too?


texts:
It can be shown that the logical preposition [ :- (~A->A)->A ] is a theorem (always true).
I want to know if anybody knows a real life description for the preposition above?
I mean an expression in computer, economics, mathematics, politics or anything that fits in that preposition.


texts: Why is c) a combinational circuit, but d) not?

texts: I am doing practice after just learning what combinational circuits are, yet I am unsure of why (c) is combinational, but (d) is not.  Can someone please explain to me why this is? The Solution mentions that for (d) node n6 connects to the output terminals of both I3 and I4, but how is this different from the circuit in (c)?


texts: What is the difference between "backhaul" and "core" network in cellular networks?

texts: I was reading some publications on cellular networks. They constantly mention two similar concepts — backhaul network and core network. I am not sure if these two are the same stuff, or in any way they are different. Does anyone know the differences? thanks!


texts:
Can Register renaming  eliminate all  WAR hazards?

What I think is register renaming is not always successful because If CPU have limited number of registers and our programme is enormously large then required registers for renaming are much larger and register renaming will fail here.


texts: How to measure the complexity of the discrete logarithm problem?

texts: The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the group into account. It seems arbitrary, why don't we chose the size of the group as the argument? Is there a criterion to know what argument to chose? In fact, I know I overlooked something important since the complexity changes hugely if we do it by the size of the group.


texts: Is it possible to simulate a CPU with software?

texts: I know it sounds a bit silly, but I got really curious. Is it possible to simulate a CPU in, let's say, Python? Some have argued that Minecraft, for instance, allows one to build turing-complete machines, but has some real research been made on this idea? Nested computers? How efficient could that be if made on assembly level? What about a computer matrix?


texts: How to connect the math of recurrence relations to daily programming concepts

texts:
What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear homogeneous recurrence relations of degree k with constant coefficients" bit in discrete math and basically understand the math part and have a simple process for solving them mechanically.

What I haven't seen yet is an explanation of what this correlates to in a CS sense. I understand we will encounter recurrence relations in algorithms which we haven't reached yet (next class) but I'm wondering what exactly do the initial conditions and the sequence represent?

For a trivial programming example, if we were to write a recursive function to process a directory and all its subdirectories, I understand conceptually that could be modeled as a recurrence relation because it is recursive, but I don't know how, and I don't know what the initial conditions and final formula for the sequence would represent in such a scenario.

Here's an example of the type of relation I'm talking about. So we solve these by taking the relation down into its characteristic equation, finding the roots, and then building a system of equations from the initial conditions $a_0, ..., a_j$ that we solve to find the constants. Finding the constants gives a closed formula for that particular sequence defined by those initial conditions.

My question is, from a CS/programming/software engineering perspective what would we model using recurrence relations like this other than algorithms, and what would the initial conditions represent in those models?


texts: Closure under intersection of context free binary trees

texts:
Some sets of ordered binary trees can be represented as a CFG with rules of the form

A -> aBC
A -> b

Where A,B,C are nonterminals and a and b are terminals representing internal nodes and leaf nodes respectively. The tree can be recovered from any word in the language by a preorder traversal.

The set of all such grammars forms a class of languages which is a subset of context free languages but isomorphic to a superset of regular languages (by unary encoding the alphabet and adding a dummy terminal for the second nonterminal in every production). It is obviously closed under union as you can simply concatenate the lists of productions to get a new tree grammar.

My question is whether this class is closed under intersection. I have been unable to prove that is either closed or not closed, and I figured I should see if anyone else can see how to do this.


texts:
I know there may be no definitive answer to theses question, since they are rather broad and opinion based.

I have a solid CS background and want to continue (post)graduate study research in CS. In particular, I am interested in questions like "What is source of uncomputability in CS/Math?", "The reason behind why DFA is less powerful than PDA". In other words these questions are closer to the limits of formal systems.

I would be glad if someone could give me some reference, as from which topics to star. By the way, I have found last the book by R. Soare, Computability Theory and Applications: The Art of Classical Computability, very interesting, could I start from this book?


texts:
I am trying to understand what is the PTAS, FPTAS and what is the difference between them.

I found this analysis:

PTAS definition vs. FPTAS

but I cannot understand what do we mean by saying:

"....time complexity is polynomial in the input size and also polynomial in 1/ϵ" ?? Ok n has to do with the linear O(n) worst case that the algorithm runs. But O(1/ε) how does it work?


texts: The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular

texts: This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)


texts: Show Resource Allocation Problem is NP-Complete

texts:
We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task.  The Resource Allocation problem asks: given $S_1, \ldots, S_n$, and an integer $k$, whether it is possible to allocate the resources to the tasks so that at least $k$ tasks are active.  Give a polynomial-time reduction from Independent Set to Resource Allocation

I am not sure how to construct the reduction. The difficulty I am having is the solver looks like a solver for a bipartite graph problem but we do not necessarily get a bipartite graph. Thank you!


texts: Is program analysis part of programming language theory?

texts:
If I am correct, programming language theory studies

syntax and semantics of programming languages, and
design and implementation of programming languages (e.g. compiler, ...)

Does programming in programming languages, i.e. creating programs in
programming languages, belong to programming language theory?
Does program analysis (correctness and performance of programs)
belong to programming language theory? My thought is:

semantics of a programming language is used for verifying correctness of programs in the language, so it seems like the answer
is yes, although I am not sure if analysis of programs' performance
belongs to programming language theory.
program analysis also seems to belong to software engineering, which makes me feel perhaps it doesn't belong to programming
language theory.

Thanks.


texts: The most frequent integer value from set of intervals

texts:
What is the fastest way to get one of the value from set of intervals which occurs most frequently?

For example if I have interval (0, 3) and (2, 4) the most frequent value can be 2 or 3.


texts: Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?

texts:
I am following CLRS for studying Amortized analysis with potential function and there I came through the following :

Let a data structure go through states : $D_0 $ $D_1$ $D_2$ $ ....$ $D_n$ while applying operations  $O_1$ $O_2$ $O_3$ $....$ $O_{n-1}$

$\therefore$ the amortized cost can be written as :

$\hat c(O_i) =  c(O_i) + \phi (D_{i+1}) - \phi (D_{i})$ .

My doubt is that if the state of data structure changes from $D_{i}$  to $ D_{i+1}$ that will be due to that cost of $i^{th} $operation which must be equal to the change in potential of the data structure.

So isn't  $c(O_i) = \phi (D_{i+1}) - \phi (D_{i})$ ? If not, they why are they not equal ?

Is the potential difference between two states, the overwork (credit) we are doing? If this  statement is true, is it the reason for the answer for my doubt to be false?


texts: Analyzing programs with multiple for-loops

texts:
If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...

the ones like

for(i = 1 to n);
   for(j = i to n);
      x++;

I can use $1 \leq i \leq j \leq n$ and use $x_1 + x_2 + x_3 = n-1$ and find out the general solution which is $\frac{n(n+1)}{2}$. But disconnected loops I have no idea. Consider the following for loops.

    for(i = 1 to n);
       for(j = i to n);
          for(k = 1 to i*n);
              x++; (constant time)

    for(i = 1 to n-1);
        for(j = i+1 to n);
            for(k = 1 to j);
                x++; (constant time)

I need to find the general solution.


texts: A variant of the set cover problem: Is that a known problem?

texts:
Can this problem be solved in poly time?

  Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$.

  Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\cdots,a_n\}=\{1,\cdots,n\}$?

Informally, the problem asks for selecting one element from each subset $S_i$ such that the selected elements cover the set $\{1, \cdots, n\}$.


texts:
I have stumbled upon this idea of "algebraic complexity" and I couldn't really find what it is and how it is calculated. For instance: the algebraic complexity of Graham Scan (https://en.wikipedia.org/wiki/Graham_scan) is : second grade polynomials.

Now, another question could sound something similar to this:

Given a triangle ABC, with: A = (xA,yA), B = (xB,yB), C = (xC,yC).¸Let there be P = (xP,yP), Q = (xQ,yQ) other two distinct points in plane. What's the algebraic complexity for:

[?]Deciding if PQ is parallel with AB, AC or BC.

Any ideas?


texts: If A is reducible to its complement, is the converse true as well?

texts: I was reading a proof that said that if $A \le_{m} \bar{A}$, then it can be inferred that $\bar{A} \le_{m} A$ as well. Is this a logical conclusion, and if so, why? I didn't think this followed with languages A and B, but if B is A's complement, can one make such a statement?


texts:
In an abstract register machine, is it possible to add two registers together without losing one of the summands, but without using a third register?

That is to have a register machine that maps $(m,n)\mapsto (m,m+n)$ that only uses two registers to store $m$ and $n$.

Disclaimer I am a mathematician and don't know much computer science. Also I didn't know what tag to put on this so apologies if this ends up in the wrong section.


texts:
What's the running time of:

foo(n)
if(n==1) return;
int i=1;
while(i<n)
{
    i=i+2
}
foo(n-2)

There are $n/2$ recursive calls to foo but how to add to the calculation the while loop


texts: Hardness of maximizing difference of functions

texts: Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it possible to characterize $g$ in relation to $f$ in a way that can be assured that maximizing $f-g$ is also NP-HARD?


texts:
Ok so I understand how $\mathrm{ATM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$}\}$ is undecidable.

Is this because $w$ is a variable?

What if the parameter is fixed?

Consider $\mathrm{BTM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts the string 101}\}$.

BTM is decidable right? The diagnolization problem here doesn't seem to apply because it would seem trivial to build a Turing machine that is 100% capable of accepting only the input "101" and rejecting every other possible input, correct?

And our machine would always reject itself as an input, since it only accepts "101", right?


texts: Time complexity of comparing two $N \times N$ Matrices?

texts: So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of operations is less than $O(N^{2})$ or is the matrix comparison lower bound also $\Omega(N^2)$?


texts:
The A* algorithm terminates when the f (distance + heuristic) is less than the f values for all of the nodes that haven't been visited. Dijkstra's algorithm produces the shortest path to every node from a starting point (not just the end node - the goal).
Is it possible to modify Dijkstra's algorithm so that when the distance to the end node is shorter than the distances to all of the unvisited nodes in the priority queue, we terminate the algorithm?


texts: Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

texts:
Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.

Prove that the given problem is in NP-complete.

I was able to prove that the problem is in NP. Hint is that we need to come up with a polynomial time reduction of the independent set problem to this problem prove that it is in NP-hard.


texts: Determine if two edges of a graph cross?

texts:
Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great.

To be clear, here's an example:

The algorithm would ideally return that the edge shared by 7 and 8 crosses with that between 5 and 11. Similarly for 11 and 10, 8 and 9.


texts: Proof that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ (lower bound of sorting algorithms)

texts:
Regarding the last step of the proof of the lower bound of comparison based sorting, there is the following implication for the runtime T in my book:

$T \ge n \log_2 n - n \log_2 e \implies T \in \Omega(n \log_2 n)$

I tried to verify this by proof, is my conclusion correct?

For any real value $x, a$ element of the extended real numbers:

$f \in \Omega(g) \implies \liminf_{x \rightarrow a} \Big \lvert \frac{f(x)}{g(x)} \Big \rvert > 0$

For $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ it has to be shown that $a$ exists so that
$\liminf_{x \rightarrow a} \bigg \lvert \frac{n \log_2 n - n \log_2 e}{n \log_2 n} \bigg \rvert $ is positive.
Since $\bigg \lvert \frac{n \log_2 n - n \log_2 e}{n \log_2 n} \bigg \rvert = \bigg \lvert 1 - \frac{1}{\ln n} \bigg \rvert$, the above limes inferior will be 1 for $a = \infty$.

It follows that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$.


texts: What is and amplification factor in pseudo-random generators?

texts:
I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this is because, in a world where $P=NP$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).


texts: Is an oracle ever useful if you can't control the input instances?

texts:
Let's say $F$ is an oracle for a problem in  $\mathbb{NP}$, but I cannot call this oracle with any input instance.  Instead, whenever I call $F$ I get returned a random instance and solution.  Thus, I know that $F$ is in fact capable of solving arbitrary $\mathbb{NP}$-hard problems, I just can't specify which one I want it to solve.

Is it possible to use such an oracle to solve an $\mathbb{NP}$-complete problem faster?  My gut says no because the naive use of the oracle still requires $O(2^n)$ time by calling the oracle enough to check every solution.  I just can't think of a way to prove this.


texts: Loop invariant condition IsPrime program

texts:
I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization.
My intuition is that as a loop invariant condition we need i in the range [2,floor(sqrt(n))] and then n mod i !=0 implies n is prime

bool IsPrime(int n)
{
    if (n == 1) return false;
    if (n == 2) return true;

    //if n (>2) is prime, it's prime factor is just n
    //if n (>2) is not prime, n=a*b, where both a,b<n and we have either a<sqrt(n) or b<sqrt(n)
    var bound = (int)Math.Floor(Math.Sqrt(n));

    //invariant: 2<=i<=bound and n mod i=0
    int i = 2;
    while (i<=bound)
    {
        //if n is divisible by some integer smaller than the upper bound it is not prime
        if (n % i == 0)
        {
            Console.WriteLine(" " + n/i);
            Console.WriteLine("x" + i);
            return false;
        }
        i+=1;
    }
    return true;
}

Could you please tell me if that is enough? I already made many attempts and that's the only statement that holds true for the whole loop until i=floor(sqrt(n)).


texts: Finding the closest point in a set in o(n) time

texts: Suppose I have a set S which is a set of points in a 3D plane. Given point P, is it possible to construct a data structure A such that the closest point to P in A can be found in o(n) time? My assumption would be to use a Kd-tree or an octree, which I think would take O(log_3(n)) to find. Any help would be greatly appreciated!


texts: minimum travel from point to point with incremental steps

texts:
It's my first time to make a question here.
I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but I only can use horizontaly and verticaly steps and this steps increases one by one units, a unit is a distance from (0,0) to (0,1), (1,0), (-1,0) or (0,-1).
For example, I need to go to (1,1) point and steps are:

Go to (1,0), a step of 1 unit.
Go to (1,-2) a step of 2 units.
Finally, go to (1,1) a step of 3 units.

And for this example the answer is I need 3 steps with 6 units of distance.
Obviously, there are several ways to go to a point from center but
the problem needs the minimal.
Are there a formula or an algorithm to find the minimum count of steps and the distance of this way?
Well, if you find one of them (steps or distance), the other one is easy to find because the distance is a sum of N (count of steps) first natural numbers.
Thanks for read this and for your answers and suggestions.


texts: Solve the online unweighted 0-1 knapsack problem efficiently

texts:
I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $w_1\leq w_2\leq\cdots\leq w_n$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $j$ appears, place it into the bin with probability $p_j$ and ignore it otherwise.


texts: Equality of cardinality of maximum matching and minimum vertex cover in general

texts:
I'm preparing for exam and I came across this problem:

  We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time algorithm deciding if a graph is König's graph.

I'm stuck. I know that in bipartite graphs this always holds. I also know that we can find maximum matching in every graph in polynomial time. But I don't know how to connect this with minimum vertex cover problem which in general is NP-complete.


texts: Maximum Independent Set of a Bipartite Graph

texts:
I'm trying to find the Maximum Independent Set of a Biparite Graph.

I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":

  Problem:

  Given a bipartite graph $G = (U,V,E)$, find an independent set $U' \cup V'$ which is as large as possible, where $U' \subseteq U$ and $V' \subseteq V$. A set is independent if there are no edges of $E$ between
  elements of the set.

  Solution:

  Construct a flow graph on the vertices $U \cup V \cup \{s,t\}$. For
  each edge $(u,v) \in E$ there is an infinite capacity edge from $u$ to
  $v$. For each $u \in U$, there is a unit capacity edge from $s$ to $u$,
  and for each $v \in V$, there is a unit capacity edge from $v$ to
  $t$.

  Find a finite capacity cut $(S,T)$, with $s \in S$ and $t \in T$. Let
  $U' = U \cap S$ and $V' = V \cap T$. The set $U' \cup V'$ is
  independent since there are no infinite capacity edges crossing the
  cut.  The size of the cut is $|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$. This, in order to make the independent set as large as
  possible, we make the cut as small as possible.

So lets take this as the graph:

A - B - C
    |
D - E - F

We can split this into a bipartite graph as follows
$(U,V)=(\{A,C,E\},\{B,D,F\})$

We can see by brute force search that the sole Maximum Independent Set is $A,C,D,F$. Lets try and work through the solution above:

So the constructed flow network adjacency matrix would be:

$$\begin{matrix}
  & s & t & A & B & C & D & E & F \\
s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\
C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\
F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
\end{matrix}$$

Here is where I am stuck, the smallest finite capacity cut I see is a trivial one: $(S,T) =(\{s\},\{t,A,B,C,D,E,F\})$ with a capacity of 3.

Using this cut leads to an incorrect solution of:

$$ U' = U \cap S = \{\}$$
$$ V' = V \cap T = \{B,D,F\}$$
$$ U' \cup V' = \{B,D,F\}$$

Whereas we expected $U' \cup V' = \{A,C,D,F\}$?  Can anyone spot where I have gone wrong in my reasoning/working?


texts: What is a monotone dataset and monotone classification?

texts:
Classification algorithms, such as k-Nearest Neighbors, are well known in machine learning area, but I faced this new expression Monotone classification and I wonder what does it stand for.

I guess that it has something to do with some peculiar characteristic of the dataset, e.g. if all the objects have growing attributes and, plotted in a 2D plane, they look as if they were gathered around the line of the function f(x) = x or something like this, but as english is not my native language, I couldn't understand the raw meaning of Monotone and Monotone classifiers, the things I read were so confusing that I don't think it is worth it to mention.

I read this:

  The evaluation of teaching courses based on surveys gathered from
  students’ opinions can be categorized as a monotonic classification
  problem if it intends to predict a final qualification that summarizes
  the general quality of the course. The students are asked to evaluate
  each course according to several aspects related to interest,
  achieving appropriate class participation, teaching resources,
  capabilities of the teacher, etc.

I would like to be able to say why these surveys behave as a monotone dataset, but no explanation fits what I have in mind about the monotone definition.


texts: How to define whitespace for certain rules but else ignore it

texts:
I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? Like when you declare an int people usually write "int b", and the whitespace separate these two items, but if I write something like "5 + 5" it should ignore the whitespace. Is that simply done by implementing in the rule for declarations like this:

Dcl --> int" " Id

Expr --> "int+int".

This should force a user to write a whitespace between the int and Id, but don't care whether there is a whitespace in the Expr rule. Is this correctly understood?


texts: Question about numbering of internal nodes in circuit diagrams when one circuit element has more than 1 internal node

texts:
I have the following circuit diagram that I've added labels for the internal nodes to using outside sources.  I understand what an internal node is, however what I'm confused about is-- for example-- E1 has 2 wires connected to another circuit element, so they're both internal nodes, but how do I distinguish which is n1? Or is this completely arbitrary?
And why is n2 after E4 here, is it because it has to follow the flow of the circuit?
Sorry for the noob question, my book doesn't explain this (at least so I've read, I could be missing it).


texts: What is the difference between A-normalization and K-normalization in compilers?

texts:
Administrative normal form is a program intermediate representation in which each immediate instruction has a name. It is used in GHC and OCaml.

K-normalized form is an intermediate representation in which each instruction consists of one assignment and operation. It's used in MLKit, Min-Caml, and GoCaml.

Both A-normalization and K-normalization involve generating a let expression with a continuation.

A-normalization and K-normalization seem to be exactly the same transformation. What is the difference between them such that they deserve different names?


texts: Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs

texts:
Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of the numbers on two balls is not a perfect square (i.e., $c^2$ for some integer $c$), they will repel each other with such force that they can never touch each other.

The player must place balls on the pegs one by one, in order of increasing ball number (i.e., first ball $1$, then ball $2$, ball $3$ $\dots$). The game ends where there is no non-repelling move. The goal is to place as many balls on the pegs as possible. The figure above gives a best possible result for $N = 4$ pegs. One may assume $N \le 50$ in all test cases.

Source: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1217.

I originally encountered this problem in the book "Programming Challenges" from Skiena and Revilla where it is part of Chapter 9: "Graph Traversal"  given a short hint:

  Can the constraints be usefully modeled using a DAG?

Question 1. How to use this hint?

Last but not least, I observed the solution seems to be always

$\displaystyle \left\lfloor \frac{(N + 1)^2}{2} \right\rfloor - 1$

which is the reason I ask this question.

Question 2. How to prove this formula or at least some upper bound on the number of balls depending on $N$?

I appreciate any kind of help in getting more out of this problem. Thanks!


texts: Assign numbers to letters with respect to lowest graph peaks

texts:
I have string which is composed of letters. I want to assign each letter a unique number (letters that repeats should have assigned same number as first unique letter occurrence) and plot those numbers on graph. X-axis will represent the particular letters of string (read from left to right) and y-axis will represent the particular value assigned to letter. The problem is that I want to have graph with minimum peaks. String can be long sequence with repeating letters. In other words I need to assign to letters such numbers that will cause that the plot change over time will be minimal.

So basically this is OK:

STRING
123456

But this not, because graph does not grows/decreases continuously and there are peaks e.g. between S-T, T-R, R-I and I-N (actually it fits criteria only for N-G)

STRING
162534

More complicated example: imagine string "STRINGS" and those two possibilities:

##############
# 1s example #
##############

Letter-Number mapping:
######################
STRINGS
6431256

Distances:
##########
S-T:2
T-R:1
R-I:2
I-N:1
N-G:3
G-S:1

Peak changes:
#############
2-1:T
1-2:T
2-1:T
1-3:T
3-1:T

###############
# 2nd example #
###############

Letter-Number mapping:
######################
STRINGS
1356421

Distances:
##########
S-T:2
T-R:2
R-I:1
I-N:2
N-G:2
G-S:1

Peak changes:
#############
2-2:F
2-1:T
1-2:T
2-2:F
2-1:T

Then the winner is 2nd example because it's maximum distance is less than the maximum distance in 1st example. I can imagine situations where both max distances can be same then the criteria should be the peak changes. In this case 2nd also beats 1st (F - does not change, T - change) because 1st is always changing and 2nd does not change in 2/5 cases

1st: TTTTT
vs
2nd: TFTFT

Is there any theory related to this? Is this even CS theory or some genetic algorithm or what problem set is this? Some library that already does this would be fine e.g. for python, perl etc.

PS: Sorry but I did not know which tags or what title describe this problem the best.


texts: Maximize distance between k nodes in a graph

texts:
I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance.  In other words they have to be spread around the graph as possible.

Let $d(u,v)$ be the length of a shortest path between $u$ and $v$ in $G$.  Now, for a set of vertices $X \subseteq V(G)$, define
$$d(X) = \sum_{\{u,v\} \subseteq X}d(u,v).$$

Let the problem SCATTERED SET be the problem which on input $G,k$ asks to find a set of $k$ vertices $X$ maximizing $d(X)$.

  Is there an efficient algorithm solving SCATTERED SET?


texts: Doubt on Performance Comparison of Splay Trees

texts:
I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their paper. Maybe because I am not that smart to actually understand these proofs, but I am still curious of one certain pathological case.

Suppose that we have a splay tree with $n$ nodes. These nodes are ordered from $1$-$n$ according to their height/level in the tree. You then access them starting from the highest level to the lowest level nodes ($n$ to $1$). In this way, it would guarantee the worst case access sequence of the tree. My intuition says that this case would be significantly slower than an AVL tree. It's probably proven somewhere that even in this case, the asymptotic access time is the same. However, I am also accounting for constant factors for a direct comparison of raw performance. How practical are they in real world application?


texts: How to find whether a grammar's language is finite or infinite?

texts:
I have this context-free grammar and I want to find out whether its language is finite or infinite.

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

So I would do

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb

So I know how to generate words like this but how to find out whether the language is finite or infinite?


texts:
I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'.
The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve optimization problems. The distance to other grasshoppers in the swarm is used to determine, if a grashopper is repelled (exploration) or attracted (exploitation) from grasshoppers in its proximity.
However I am not sure if I understood the first part of the proposed formula correctly:
$$X_i^d = c\left(\sum\limits_{j=1,j\neq i}^Nc\frac{ub_d-lb_d}{2}s\left(\lvert x_j^d-x_i^d\rvert\right)\frac{x_j-x_i}{d_{ij}}\right) + \widehat{T}_d$$
$X_i^d$ calculates the next position of a search agent (grasshopper) with respect to the postion of the other search agents and the best found solution so far. So the next position of a grasshopper depends on its own position, the positions of all other grasshoppers in the swarm and the best solution found so far.
$\widehat{T}_d$ denotes the best solution found so far.
$c$ is a decreasing coefficient that regulates if the search agents explore or exploit in the search space. With increasing iteration count  $c$ decreases and the search agents tend to exploitation.
$s\left(\lvert x_j^d-x_i^d\rvert\right)$
The part in brackets calculates the distance between grashoppers.
$s$ is a formula which takes this value and determines if the search agents should explore or exploit.
$\frac{x_j-x_i}{d_{ij}}$ is a unit vector, where $d_{ij}$ denotes the distance between two grasshoppers.
It states that $ub_d$ is the upper bound and $lb_d$ is the lower bound in the $d$-th dimension.
It further states that the part $c\frac{ub_d-lb_d}{2}$ linearly decreases the space that grasshoppers (search agents) should explore and exploit.
I dont undertsand what is meant with 'upper and lower bound in the $d$-th dimension'.
Upper and lower bound for what exactly?
Can somebody help?
Information extracted from this paper:
Grashopper Optimization Algorithm


texts: Is P = {  | M rejects w} the complement to Atm = {  | M accepts w}?

texts:
As Atm is recognizable, its complement cannot be recognizable, due to being so Atm would be decidable.
I am trying to clarify if the problem P is the complement to Atm.
If so, how could i approach the problem without looking at Atm to prove undecidability?
My first thought was:

H is a machine which solves P:
H halts and accepts when M rejects w.
H halts and rejects when M accepts w.

And from then on contradict the construct like in the proof of Atm.


texts: Is a "protocol" a set of algorithms and data structures?

texts:
I'm not major in science at all and would like to verify whether my understanding is correct or not.

I just did some googling about the definition of protocol, such as in this, this one, this one and more.

And, I would like to know:

is a protocol a pack of algorithms and programming source codes? (in both the computer and network)
regarding the previous question, if so, does that mean that the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follow the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)


texts:
I'm working on a dependency managemen solution for a JavaScript.  I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'.

Given a dependency tree like shown below, I have a 'main' module ( app ), that has 5 children ( login, dashboard, form, builder, users ).  These children might share some common deps amongst them.

I'd like to create a function that would find the commons and group them upwards or in some cases where the overlap would out weight the benefit, creating a new module between them.

In a perfect world, would create a graph like this.  Obviously given a big enough tree, it could over-optimize creating too many child trees so probably stopping at level-3 would be ideal.

In this example:

d1 was shared 90% of the time, lets move it into the main module.
d6 was used in 3 of the 5 modules, lets create a separate module for that combo.  - d5 was used in 2 of the 5 modules, lets create a separate module for that combination.
d3 was used in 2 of the 5 modules, lets create a separate module for that combo.


texts: I have a very silly question, when data is transferred from the RAM to the CPU is this data transferred "copies" of the original data stored inside the RAM?


texts: Type Theory and Principia Mathematica Part IV "Relation Arithmetic"

texts:
As

type theory is a principle focus of modern computer science,
its origins are in Bertrand Russel's theory of types,
Principia Mathematica is both the origin of and is expressed in the theory of types, and
relational databases are among the highest value, most researched applications of computer science

it seems Russell's "Relation Arithmetic"* (developed in Principia Mathematica Part IV "Relation Arithmetic") would be an active field of study in modern computer science.

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments:

  "I think relation-arithmetic important, not only as an interesting
  generalization, but because it supplies a symbolic technique required
  for dealing with structure. It has seemed to me that those who are not
  familiar with mathematical logic find great difficulty in
  understanding what is meant by 'structure', and, owing to this
  difficulty, are apt to go astray in attempting to understand the
  empirical world[emphasis JAB]. For this reason, if for no other, I am sorry that the
  theory of relation-arithmetic has been largely unnoticed."

Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use?  If so, why?

*A good, informal, introduction to relation-arithmetic is in Introduction to Mathematical Philosophy, by Bertrand Russell.  One must first understand Russell's abstract definition of "number", drawn from Frege (Chapter II "DEFINITION OF NUMBER").  Then one can proceed to Chapter VI "SIMILARITY OF RELATIONS" where he defines relation-arithmetic.

Briefly, there are no "sets" in the sense we think of "set theory" -- there are only "relations" which may be "similar" to one another.  All relations that are "similar" to one another comprise a "relation number".  Similarity between two relations, P and Q, obtains if there is a one-to-one correspondence between the relata of P and the relata of Q such that if a relationship holds in P, the relationship also holds in Q between its corresponding relata.  One can even think of ordinary numbers as relation numbers if one restricts the relations to one place relations (monadic/unary/property/etc.).  I emphasize this because although Russell uses the word "class similarity" rather than "relation similarity" in Chapter II, it is apparent that he considers "class" to be a degenerate case of "relation" when one carefully reads Chapter IV.  Because of this, and the fact that type theory is considered an alternate foundation for mathematics used in computer science, it may be incorrect to dismiss relation-arithmetic as a degenerate case of category theory or some other more complex mathematical structure in which it may be encoded or modeled.  Such modeling or encoding should be the other way around.

"Relation numbers", thus defined, are then defined to have the ordinary arithmetic operators, addition, multiplication and even exponentiation.


texts:
$\Sigma = \{0, 1\}$

$L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$  $ \#_1(x) = 3 \}$

What is the regular expression of this language?

At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $ or$ $ $ $r = (0+1)^*1(0+1)^*1(0+1)^*1$

And what is it's corresponding NFA/DFA?

I've been puzzled by this language and if it's regular for a while now.


texts: Where can I find good study material on Role Mining?

texts:
I need to cover these topics in Role Mining. If anyone knows good site which well summarizes the topics and concepts are well explained please help out.

Basic role mining problem
• Delta-approx RMP
• Min-noise RMP
• Nature of the RMP problems
• Mapping RMP to database tiling problem
• Minimum tiling problem
• Mapping min-noise RMP to database tiling problem
• Mapping RMP to minimum biclique cover problem


texts: Is it possible to shorten this Finite Automata Transition Graph?

texts:
I designed this transition graph, seen below. The alphabet contains {a, b, c}, and the goal of this machine is to accept any strings (no limitations on length of string) that ends with a letter that is already in that string.

Example: abba, aaa, bb, ababababacc, cabc are accepted.
Example: abc, bccba, a, b, c, cccab, are a rejected.

Is there a shorter/simpler way to design this finite automata than this transition graph?


texts:
I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed.

0
`----> 1 ------------> 4 ---> 7
`                      ^      ^
`---> 3                |      |
`     `------> 2 -----/       |
`     `------> 5 ----------- /
`     `------> 6 ---------- /
`
`--> 8
     `------> 9
     `------> 10
     `------> 11

I need to perform all tasks consequently but with optimizations like running tasks in parallel where it is possible.

Topological sorting allows me to build just a sequence of tasks execution:

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

But I need something like:

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

// [...] - means parallel processing

Could you recommend any algorithm to achieve this?


texts:
Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to write a paper on reductions (3SAT)

When doing the Reduction from the Clique Problem to 3SAT, I understand that we make clauses and every clause contains 3 literals (hence, 3SAT) but my problem comes when choosing what literals and why they choose them. How do I know which literals to choose? So I know that in every clause I'll have x1, x2 and x3, but how do I choose their assignment order? In one clause I have (x1 or x2 or x3) and in another I have (x1 or not x2 or not x3). How were these chosen?

Also, it seems they don't begin with a graph in mind already. What if I'm given a graph to begin with, how would I convert it into x1, x2, x3? If for clause I have 3 vertices, how would I assign them their respected boolean expression? Thank you very much


texts: How to solve this optimization problem with logarithmic objective function?

texts:
I have this optimization problem

I have no idea how to solve it. Is Lagrange suitable for this problem?

Thank you


texts: How to build a graph with certain fault tolerance

texts: I'm trying to build a graph with $n$ vertices and $k \cdot n $ edges, I need to make sure that this graph is $2k$ connected, meaning that it cannot be disconnected by removing at most $2k-1$ vertices. I'm looking for an algorithm that given n,k outputs such a graph.


texts: Determining which recursive term is bigger if they share the same definition

texts:
We are given a recursive definition:
$a_1 = x,\\a_2=y,
\\a_n= c_1a_{n-1}+c_2a_{n-2}  \text{ for }n\ge3 $
where $x,y,c_1,c_2,n$ are natural numbers
we are to prove that $a_n \le c_3^n$ for all n
The base case is true
Assuming $a_k \le c_3^k$ is true
show $a_{k+1} \le c_3^{k+1}$ is true

We have:

$c_3a_k \le c_3^{k+1}$

and

$a_{k+1} = c_1a_k + c_2a_{k-1}$

where 1 can be written:

$c_1a_k + ma_k$

where $m+c_1 = c_3$
which can be rewritten:

$c_1a_k + mc_1a_k + mc_2a_{k-1}$

Now, 4 and 2 have the first term equal.
How can I determine whether $ mc_1a_k + mc_2a_{k-1}$ in 4  is bigger or not than $ c_2a_{k-1}$ in 2?


texts: Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times

texts:
I need to find a sorting algorithm to sort an array where the the $k$-th element appears $2^{k-1}$ times in $O(2^k)$.
It also given there are $k$ distinct elements in the array, hence there are $1 + 2 + 2^2 + \dots + 2^{k-1}=2^k-1$ elements in the array. So I actually need to sort the array in $O(n)$ where $n$ is the array size.
Not sure how to use the known quantity of each element to sort faster.
Any help is appreciated.


texts:
Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$.

We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$?
Supposing $A\subseteq P^{B\cap C}$ also holds does it also give $A\subseteq {B\cap C}$?
If $P^B=B$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?
If $B\subseteq P^{B\cap C}$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?

Do we know anything else about intersection of oracles?


texts: Variable bytes (bit arrays) and flipping single bits?

texts:
My interest is strictly theoretical at this point, but ultimately applied.

Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ordinal value/position?

Essentially I'm looking for the most compact method reading/writing ordinal values in an array that expresses different subsets/combinations of the power set m: P(m) = 2ᵐ.

--------

Purpose: This is related to the game-theoretic conception of Sudoku and Latin Squares. Although our current software is Java based and uses conventional structure and arrays, the ultimate problem size is so large, when we move on to solution checking and integration of neural networks, we're going to have to be optimized. This means flipping the least number of bits, and using the least amount of volume. (We have a custom server allowing cross platform PvP on any device that can has connectivity, and, at some point, bandwidth usage is going to be an issue.)

A. My assumption is writing a single value to a conventional array require more operation or energy than flipping a single bit, even if I have to pull the whole string to flip the bit.

B. If I have to assign a memory address for individual values (1,2,3,4,5,6,7,8) my understanding is each of those addresses reserves an entire byte.  By contrast, with a bit array, I only need a single 8-bit byte. [For a neural network, there may be trillions of these arrays, conservatively, without coming close to exhausting the problem space.]

C. If we use conventional arrays vs. bit arrays, the amount of data transferred is significantly greater.

Are there any problems with these assumptions, theoretically speaking?

(Apologies if I've tagged anything incorrectly--feel free to modify :)


texts: A slightly different version of the halting problem

texts:
I got stuck with a question and would like to have a little guidance for the solution.

I need to prove that the next problem is undecidable:

Input - A program
Problem - Does the number of possible inputs for which the program halts is larger than those for which the program won't halt?

I tried to build a reduction that (in case the input is even) halts for every even number, goes to an infinite loop for every odd and runs the program with the input. Or in case the input is odd does the opposite - but it only works if I am able to prove that the number of real odd numbers is equal to the real even numbers.


texts: A regular graph is one in which each vertex has the same number of neighbors, but in a star topology the central vertex is connected to more than one vertex. So, why is it referred to as a regular graph?


texts: Reducing vertex cover to minimal vertex cover

texts:
What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?

Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? since minimal vertex cover is essentially $min{f(x)|x\in VertexCover(G)}$

Graph is basic if it matters, no weights, and it is undirected

thank you for helping


texts: How I can find all equivalence classes by Myhill-Nerode?

texts:
first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.

The topic is Myhill-Nerode and the equivalence classes of a regular or non regular language.

I know that every element of a equivalence class by Myhill-Nerode
fulfills this property:

$ \equiv_{A} \triangleq\{(x, y) | \forall z \in \Sigma^{*} \cdot(x z \in A \leftrightarrow y z \in A)\} $

If I understand this right, than a equivalence class consist of element (words) $x$ which we can expand with a word $y$ but for all words $x$ and $y$ of the same class must apply, adding a word $z$ to them both must be in or out of the language.

Hope that is right until now.

Now I will show you my problem:

I have the language (its from a book):

$  \mathrm{B} \triangleq\left\{73 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\} $ with  $ \Sigma_{\mathrm{M}} \triangleq\{\mathrm{a}, \mathrm{b}, 3,7\} $

And a complete solution:

$1: [\lambda]\equiv_{B}=\{\lambda\}  $

$2: [7]\equiv_{B}=\{7\}  $

$3: \left[73 a^{k}\right] \equiv_{B}=\left\{73 a^{k}\right\}  $ für $  k \in \mathbb{N} $

$4: \left[73 a^{l+2} 7\right] \equiv_{B} =\left\{73 \mathrm{a}^{\imath+2+n} 7 \mathrm{b}^{\mathrm{n}} | \mathrm{n} \in \mathbb{N}\right\} \quad  $ für $  l \in \mathbb{N} $

$5: [3]_{\equiv \mathrm{B}}=\Sigma^{*} \backslash\left([\lambda]_{\equiv \mathrm{B}} \cup[7]_{\equiv \mathrm{B}}\right.  \cup\left(\bigcup_{k \in \mathbb{N}}\left[73 a^{k}\right] \equiv_{B}\right) \cup \left(\bigcup_{\mathfrak{l} \in \mathbb{N}}\left[73 \mathrm{a}^{\ l+ 2} 7\right] \equiv_{\mathrm{B}}\right) ) $

So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

In $2$ they build they build the class of $7$ and z has to be something like this $ z = \left\{3 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\}$ to be in the language.

In $3$ they build a class or better infinitely many classes. But here is my problem. I cannot find a $z$ which is working for all classes.

For example we have the words $x_i$ and $z_i$

$x_1 = 73 \to z_1= {a}^{n+2}7b^n$ with $n\in N$

$x_2 = 73a \to z_2= {a}^{n+1}7b^n$ with $n\in N$

$x_3 = 73a^2 \to z_3= {a}^{n}7b^n$ with $n\in N$

$x_4 = 73a^3 \to z_4= {a}^{n}7b^n+1$ with $n\in N$

and so on.

But why is this ok? I Mean they are 2 words in this class for example $x_1$ and $x_2$ who $x_2$ would not be in $B$ with $z_1$.

I hope you can tell me on a simple and understanding way how those classes by Myhill work and how i can find them without making big mistakes.


texts: Union, Intersection, Difference, etc. of different types of languages

texts:
I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example,

  If $L_1$ is recursive & $L_2$ is recursively enumerable, then is $L_1\cap L_2$ recursively enumerable?

Similarly,

  If $L_1$ is regular, $L_2$ is a deterministic CFL and $L_3$ is recursively enumerable, then is $L_1 \cap L_2$ a deterministic CFL? Is $L_3 \cap L_1$ recursive? Is $L_1 \cup L_2$ context free? etc.

Now I can compare such operations between languages of the same type using closure properties, but how do I tackle such questions?


texts: How many time and space units does this algorithm take?

texts:
This is what I counted but I know I'm wrong since my conclusion is not in the choices:

t = time unit
s = space unit
y=1 : 1t & 1s
for 0 <= i <= N : Nt & 1s
y=y*i : 2 reads, 1 write, 1 multiplication therefore 4 time units,
the for loop is thus 4N time units
total time = 4N+1
total space = 2 (because there are only two variables that need to be
stored)


texts: Automated lip-reading: inferring what someone is saying, based upon video of them speaking

texts:
Some humans can lip-read fairly well: by watching someone who is speaking, they can tell what the speaker is saying (even without hearing the speech).

Has there been any work on building computer software to lip-read?  In other words, given a video of someone speaking, is it possible to build software to infer what the person is saying (with access only to the video stream, without audio)?  Has there been any research on this problem, or even deployed systems?

Background and motivation: In the US, certain laws may forbid recording audio without consent.  However, there is generally no prohibition on recording video without consent of the people being recorded.  (That's why you see surveillance cameras all over the place, and why they record only video but never audio.)  I am curious whether technology has advanced enough that, solely from video, it might be possible for automated methods to tell what people are saying -- or whether that might become feasible in the near-future.  And, apart from the privacy implications, such a technology might be pretty useful.


texts:
It seems to me that recursive equations can always be presented as inference rules.  For the forward direction, an example is addition over Peono numerals (built from $O$ and $S(\_)$)

$$
\begin{align}
add(O, m)    & = m \\
add(S(n), m) & = S(add(n, m))
\end{align}
$$

which can be also presented as

$$
\frac{ }{add(O, m) = m} \qquad \frac{add(n, m) = a}{add(S(n), m) = S(a)}
$$

Is the backward conversion (from inference rules to recursive equations) always possible?  If not, it seems inference rules more general, right?  Except the superficial difference between the presentations, is there any other deeper difference between the two?


texts: Anagrams solver based on transitions probability

texts:
I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible anagrams (which have to be into the dictionary) based on transitions probability (my assignment requires that I use this method).

I thought to use the Viterbi Algorithm  but I don't know if it is the right choise. What do you think about a simulated annealing algorithm? Can you give me any help or advice?


texts: Difference between end carry and overflow

texts:
I am confused with end carry and overflow. When will an end carry be the overflow? How to identify whether the end carry is overflow or not? Are they both same?

Sometimes end carries obtained are simply discarded and sometimes the end carries are considered as overflows. What is the exact method to find an overflow?

In the case of unsigned numbers, if the addition causes end carry, then the end carry should not be discarded because it is the part of result number. In this case, is the end carry an overflow? In the case of signed numbers, if the addition causes end carry, then the end carry represents sign bit. In this case is the end carry an overflow?


texts: Reasons for decreasing the number of threads in a parallel implementation

texts:
What are the reasons for decreasing the number of threads in a parallel implementation ?

Assume that we have two implementations, the first one with 4 threads, and a second one with 8 threads, and both have exactly the same run time. What are the various reasons to prefer the first one?

I stress on the fact that the two implementations have the same run times.

The obvious reasons are the following:

If we have 8 processors, we can execute at the same time this implementation on two different sets of inputs thus performing twice the work,
Less resources consumption by the OS which handles less number of threads.

I'm looking for other reasons...


texts:
The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works theoretically).

Algorithm:

abc_delete(T, z) // z is the node that must be eliminated
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

For example, I want to delete the node number $7$:

But, shouldn't the end result be this?


texts: Data structure for finding max, inserting and deleting in O(1) and O(n) space

texts:
This is an interview question. I need to implement a data structure that supports the following operations:

Insertion of an integer in $O(1)$
Deletion of an integer (for example, if we call delete(7), then 7 is deleted from the data structure, if the integer 7 exists in it) in $O(1)$.
Return maximum integer in the data structure (without deleting it) in $O(1)$.

You can also use up to $O(n)$ space.

I thought of something similar to this question, but here we have $O(\mathrm{log}\ n)$.

Do you know how can we implement these operations in $O(1)$?

Edit: forgot important thing - you can assume the numbers that will be inserted are integers in the range $[0,n]$.


texts: Regular expressions and semi-linear sets

texts:
In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as:

$u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in \mathbb{N}\}$ where $u_i$ are vectors of natural numbers.

and a semi-linear set as a union of finitely many linear sets. It goes on to say ''For every semilinear set $S \subset N^k$, it is not hard to construct a regular set $R \subset \Sigma^*$ such that $\psi(R) = S$'' (where $\psi$ is the Parikh map, taking strings over an alphabet $\Sigma$ to vectors where the first entry is the number of the first letter, the second entry is the number of the second letter, etc. So $\psi(\{a, ab, ba, aaa\})) = \{(1), (1, 1), (3)\}$.)

I was trying to think why regular languages would be semi-linear instead of just linear, and it seems like the + (or) operation in regular expressions is to blame. Is this correct: are languages described by regular expressions which use only concatenation and $^*$ linear?


texts: How can you bound the error of an approximation without knowing the optimal solution?

texts: I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is supposed to be?


texts: Selecting n elements from array in sublinear time and subquadratic compute and memory complexity using indices

texts:
Are GPUs or CPUs capable of selecting n elements from an array in sublinear time using indices? If so, what would be some good alternatives to achieve this?
Lets say I have an array A = {1, 5, 6, 3, 6, 2} and indices I = {2, 5, 2, 4, 1, 0}. The resulting array should be: B = {6, 2, 6, 6, 5, 1}. The time complexity for this should be sublinear with respect to the length of I.
edit: sorry I forgot to mention that the memory and compute complexity should be subquadratic. For instance you could retrieve the elements in constant time if you would out of the indices construct a matrix "C" of one-hot encoded column vectors and perform a vector-matrix multiplication A*C.


texts:
A definition for terminals and non-terminals of a CFG says that

  terminals: The symbols that do not appear at the LHS of productions.

Therefore,

Are all non-terminals of the CFG given by the LHS of productions?


texts:
If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?

Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?


texts: Turing machine that can tell if it ends in standard position?

texts:
Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape is $0$.

Suppose the tape is initially consists of a bunch of $1$s, a $0$, a bunch of $1$s, a $0$, and so on for a finite number of $1$ and then the rest is $0$. $M$ is initially scanning the left-most $1$.

Is there a turing machine that can appended to this guy so that, whenever it is about to halt, it checks if it is in standard position? If it is standard position, then it returns to standard position and halts. If it is not in standard position, then it does not halt. This standard position checking could depend on the turing machine (and probably had to depend on the number of states at least) but should not depend on the initial state of the tape.

I thought that arguing that the TM only has to check $n+1$ $0$s beyond the last $1$ in either direction because the turing machine cannot add a $1$ that far away from the last $1$, but there are counter examples. For example, there is a 3-state machine that, when given the tape 100 _ 1, it changes $1$ to $0$ for "spots" 2-100 and then halts at the second argument.


texts: Counting the solutions to a restricted 0-1 knapsack problem

texts:
Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ :

Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is  represented by a fraction $\frac{p}{q}$ in its lowest terms.

Output:  the number of 0-1 solutions (i.e. those having $s_i\in \{0,1\}$) to $s_1 + s_2 + \dots + s_n \leq s$.

  What is the counting complexity of $\mathsf{\#IDKNAP}$?

Let $k := \lfloor s \rfloor$.  The problem asks for the number of $n$-bit vectors with at most $k$ bits set to $1$. The solution is $\sum \limits_{i=0}^k \binom{n}{i}$, for which there is no closed form in general,
and thus cannot be computed in polynomial time in the input size.

So (I think) $\mathsf{\#IDKNAP}$ would be either $\mathsf{NP~Hard}$ or $\mathsf{\#P~Hard}$. It seems to be insufficiently general to encode arbitrary  $\#\mathsf{KNAPSACK}$ problems, which are $\mathsf{\#P~Hard}$.
On the other hand, $\mathsf{\#IDKNAP}$ has exponentially less input size than general knapsacks, for which the weight vector $(w_1,\ldots,w_n)$ has at least $n$ bits.


texts: Density of regular language containing all squares

texts:
I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.

Suppose we have a regular language $L \subseteq \{0,1\}^*$ and the language $ \mathbf{S} = \{uu: u\in \{0,1\}^*\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$. How would I show that there are at least $a2^n$ length $n$ binary words in $L$, for infinitely many $n$? Where $a$ is some constant that can depend on $L$.

Clearly $\mathbf{S}$ is non-regular, so there must be more length $n$ words accepted, but I am not sure how to get $\Theta(2^n)$ length $n$ words. Somehow one has to use the regularity of $L$, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.


texts: How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

texts:
I'm trying to prove that:
 $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma.

This is what I tried so far:
$w=a^ncb^n$, then $|w|\ge n$ and $w\in L$.

By, condition 1 and 2 (of the Lemma) we will get that: $w=xyz$ - such that: $x=a^r,\ y=a^s, \ z=a^{n-r-s}cb^n$. ($r+s\le n,\ s>0$)
Then, by condition 3: for any $i\ge 0$ : $xy^iz\in L$.
We will take $i=0$ then - we will get: $xz=a^ra^{n-r-s}cb^n\in L$.
That's means that: $a^{n-s}cb^n\in L$ - contradict!!

This what I did, but I think that I miss something...
Can you please guide me and tell me where to look at?


texts: Tight examples: Feedback vertex set 2-approximation algorithm

texts:
The specific algorithm I am referring to is Algorithm 6.8 from Vazirani's book "Approximation Algorithms". The book is legally available online here, and the algorithm is on page 58 (76 in the pdf).

The algorithm is pretty simple (especially if you're familiar with the layering technique), but in any case I'm only interested in tight examples, which usually implies "degenerated" (trivial) runs of the algorithm.

I understand the tight example the book has provided (Example 6.10, found one page after the algorithm), but I'm looking for one that uses a simple graph (i.e. without parallel edges).

For an example without parallel edges, the author suggests "a vertex with very high weight" to "be placed on every edge". I have two (independent, related and simple) questions regarding this:

Does Example 6.10 work "as is" (with the only change being that you don't duplicate every edge)? I think that if you simply remove a perfect matching from $K_{n,n}$, then the algorithm might output a FVS with $2n-5$ vertices, where the 5 not-chosen vertices can be any 3 vertices from one side and any 2 vertices from the other side. This is indeed a $2-o(1)$ approximation, as desired.
What is the meaning of the sentence "a vertex with very high weight can be placed on every edge"? I can interpret this in two ways:

One is that we'll have vertices with weight $\infty$ on one side,
and vertices with cyclomatic weight on the other. This is not a good example because the algorithm can output a set of $n$ vertices (which is optimal).
A second interpration is that "in the middle" of each edge we add a new vertex (i.e. if we had an edge $(u,v)$, now we'll have $(u,a)$ and $(a,v)$ for some new vertex $a$ with weight $\infty$).
This example indeed leads to a solution which is a $2-o(1)$ approximation, but I'm not sure why is it worth the trouble of using vertices "with very high weight" when a much simpler example exists (in case the answer to my first question is yes).

How would you interpret this sentence?


texts: Does every problem in NP have an exponential time algorithm?

texts: I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.


texts: Ways of object recognition in computer vision

texts:
In the field of computer vision, we talk a lot about this process of feature detection-description-matching as a way of recognizing objects. But on the other hand, there's also talks about object classifiers and such, but aren't they based on this feature detection description matching?
Is detecting features and describing them and matching those descriptions the only way of recognizing objects?


texts: Intersection of line segments induced by point sets from fixed geometry

texts:
I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson's book Algorithms.

I solved (a) by seeing a relationship to the previous problem on computing the number of array inversions. However, I am struggling with problem (b) as I cannot see how to reduce the circle point arrangement to an arrangement of points and lines that would be an input to the problem posed in (a). Assuming I have something for (b), I also cannot see how one might resolve (c).
For part (b), clearly every point $p = (x, y)$ satisfies $x^2 + y^2 = 1$ but I do not see how I might be able to use this fact to do the reduction. The runtime I am shooting for of $O(n \log^2 n)$ also seems to tell me the reduction is going to cost something non-trivial to do.
Can anyone have some further hints/insights that might help with part (b) and potentially even part (c)?


texts: Proving using a SAT solver that KB entails D

texts:
Suppose you're given this KB:
$$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$
How would you show using a SAT solver that $KB \vDash D$?


texts:
I am new in the field of IoT OS and I saw TinyOS, Conitki etc. can be installed on top of Ubuntu. Its not clear to me how these OSes are able to run on top of Ubuntu without any Hypervisor? Can someone explain whats going on here?
Is ubuntu working as virtual hardware for these OSes without Hypervisor?
Is TinyOs , Conitki installed as just another programs on
ubuntu??


texts: What is the logic behind seperating Shift moves/reduce moves and Goto moves in parsing table?

texts: In the parsing tables of SLR(0), LALR(1) and LR(1) I have seen that shift moves and reduce moves have separate columns from Go-to Moves. What is the logic behind this?


texts: Quick groupby - is this a well known algorithm?

texts:
I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted.

E.g. if input is

array = ["a", "a", "c", "b", "c"]

then output

groupby(array) = ["a", "a", "c", "c", "b"]

or

groupby(array) = ["c", "c", "a", "a", "b"]

etc. The point being the final order of the array isn't important; the only requirement is that identical elements have to be placed contiguously.

One algorithm that is inspired by quicksort is to pick an element, called it pivot, and divided the array into 3 segments with the first segment being all elements that equal pivot; and the other two begin those are "less than" and "greater than" pivot. Elements within each segment have to be placed contiguously.

The segmentation can be achieved in n time using a simple adaption of the pivoting in quicksort and then apply the algorithm recursively on the "less than" and "greater than" segment.

Is this algorithm well known and has a name? Or is it a novel algorithm?


texts:
Hopefully this question is not a duplicate.

How do I show the problem below is decidable by describing a Turing machine?

Input: Turing machine M

Question: Are there infinitely many Turing machines that all recognize L(M)?

I know a language is decidable if there exists a Turing machine that halts on all inputs when running on that language, where it accepts if a string is in the language and rejects otherwise.

Now I know that a Turing machine can simulate the behavior of another turing machine, so in theory a turing machine, say T, CAN simulate the behavior of M, therefore accepting the language of M.

Wouldn't it then be possible if I argue that there can exist an infinite amount of turing machines that all simulate the behaviour of M, and as a result accept L(M)?

Or is what I'm proposing not doing its job of showing the problem is decidable?


texts: Partitioning through block moves to the end

texts:
Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements to the end.

E.g. if our string is $ABCDEFGH$ we can do our operation at index $1$ to get $DEFGHABC$. If we did it at index $4$ we'd get $ABCGHDEF$.

I'm interested in optimal solutions - that is with the least amount of moves. I have a working algorithm using IDA* with heuristic "# of groups of ones with length $\leq 3$ before the final zero", with the logic that each such a group requires at least one move to fix. An example optimal solution (where ^ indicates where a block was chosen to move to the end):

1101101011101011010010010011
                       ^
1101101011101011010010011100
                     ^
1101101011101011010011100001
              ^
1101101011101010011100001110
           ^
1101101011110011100001110010
                        ^
1101101011110011100001110001
     ^
1101111110011100001110001010
  ^
1111110011100001110001010011
                     ^
1111110011100001110000011101
                       ^
1111110011100001110000001111
               ^
1111110011100000000001111111
        ^
1111110000000000001111111111
   ^
1110000000000001111111111111
^
0000000000001111111111111111

However, this algorithm is exponential and not feasible for larger strings. After studying quite some optimal solutions, especially tough ones like above, I can't immediately think of an optimal algorithm. Moves can be quite non-trivial.

Is there a feasible optimal algorithm? Or is this problem hard?


texts: Can you specify a programming language without implementation?

texts:
Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to execute a given program in that language on a given input to the output of the function corresponding to the program on that input.

What is are the minimal requirements of such a language?


texts: I am using detectEigenFeatures in the Matlab command to obtain the corner points. This function only can provide the corner points within a rectangular boundary region. But I want to extract the corner points within a polygon. I have thought about using small rectangles in order to obtain a polygon. But it seems time-consuming.


texts: Structural Equivalence - How exactly is the structural equivalence checked by the compilers?

texts:
I wanted to clear my doubts on the structural equivalence type check in the compilers.
Consider the following two structs (or records):
struct student {
    string sName;
    int sAge;
};
struct teacher {
    string tName;
    int tAge;
};

Are the two structs student and teacher structurally equivalent?
I have studied a recursive algorithm to check for the structural equivalence and I believe these two structs should be structurally equivalent.
However, I have also read that the types of structs are defined using the cartesian product of the data members with the data types (eg. the data type for the struct student will be something like struct((sName x string) x (sAge x int))) and thus, giving the data member names importance and differentiating between the two structs.
Also, I wonder if the order in which the data members are declared in the structs, will have anything to do with the structural equivalence i.e. are the following two structs structurally equivalent?
struct student {
    string Name;
    int Age;
};
struct teacher {
    int Age;
    string Name;
};

Please note that, here, the data member names are the same.
Any sort of help is appreciated. Thanks!


texts: How does a single-track Turing machine simulate a multi-track Turing machine?

texts: It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification of a transition function that does the job. If there are $k$ tracks, then we can think of symbols as being vectors and arrange them one after another in the tape; but again, what's the transition function like in the equivalent single-track machine?


texts: What is the difference between Big O and Theta notation in terms of inputs?

texts:
In Coreman , it's written :

  The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time of insertion sort,however, does not imply $\Theta(n^2)$ bound on the running time of insertion sort on every input.

So, is there any difference between the two notations in terms of input? If so, then why does it use $\Theta(n^2)$ in worst case running time of insertion sort?


texts:
I need some help with explaining why a grammar is not LL(1).

Let us take the following grammar:

$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
B \rightarrow & b \\
\end{align}
$$

This is my attempt:

For the grammar to be LL(1) it is a necessary condition that for any strings $c_1γ$ and $c_2β$, derivable from $S \rightarrow aB$ and $A \rightarrow aS$ respectively, we have $c_1 \ne c_2$.

But, $S \rightarrow aB$ and $A \rightarrow aS$, hence $c_1 = c_2$ and the grammar is not LL(1).

Is my reasoning right?

Thanks in advance.


texts:
The Exercise is

Computer A has a main memory of size HA 2 MiB, and computer B has a main memory of HB = 256 MiB. Both computers process single transactions that have a size of s=84 KiB. Each of the computers loads a maximum number of transactions into the main memory so that at least 512 KiB are still reserved for the processing algorithm. After that, all transactions in the main memory are processed as a batch. The time to load a transaction is 2 ms in both systems. Computer A processes a transaction in 4 ms, computer B needs 7 ms to process a transaction.
Which of the two systems is faster with the processing of all transactions finished? Is there a number of transactions that are processed equally fast by both systems? Justify your answers and give the complete calculation path to your answer.

I need to know if my answer is correct, and if not, why.
My answer would be:
Computer A has 2048 KiB - 512 KiB = 1536 KiB
1536 KiB / 84 KiB = 18 transactions
18 transactions * 4 ms = 72 ms
Computer B has 262144 KiB - 512 KiB = 261632 KiB
261632 KiB / 84 KiB = 3114 transactions
3114 transactions * 7 ms = 21798 ms
Computer B takes longer to process than computer A.
Now one question I have is that I'm pretty sure that this is not the right answer to this exercise, because the 2 ms, for loading the transaction, are not included in my answer.
What did I do wrong?


texts: I'm learning about Turing Machines, decidability, and recognizability, and read that if a language is recognizable, its complement is sometimes recognizable. I don't really understand how this could be, can someone give me an example where a language has a recognizable complement and an unrecognizable complement? Thank you!


texts: Why do some inference engines need human assistance while others don't?

texts:
I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Why is it that automated theorem provers, i.e. ACL2, and SMT solvers do not need human assistance while proof assistants, i.e. Isabelle and Coq, do?

Find the series' next question here.


texts: Whether assigning of single precision IEEE754 float to double is reversible?

texts:
Using the IEEE754 standard, let's assign single precision variable s to double precision variable d and then assign d to single precision variable s'.

Is this operation is reversible (lossless) for any value that can be represented in IEEE754, including NaN, infinity, etc.?  In other words, is it guaranteed that s = s' for all possible s?

On my processor NaN is not reversible (01 00 80 7f != 01 00 c0 7f).  Brute force shows that NaN is not reversible, but this might be implementation dependent, so please answer within the scope of IEEE754 standard.


texts: Graph "coloring" problem minimal number, each edge has a colored end

texts:
(there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not covered that in the lecture yet.)

again I am facing homework and thus, would appreciate it, if you did not(!) give me the solution, but helped me to get there on my own.

I've got an exercise to solve and I think, I'm pretty close, but I seem to can't get there.

I've got a graph and have to color the vertices such that the following conditions are met:

-there are two colors (a,b)

-each edge has precisely ONE a-colored vertex

-the number of a-colored vertices is minimal

I've tried to reduce the problem to 2-coloring. BUT:
I don't know how to deal with the condition that the number of a-colored vertices has to be minimal.
I am pretty sure that I can reduce it to a coloring problem, because I also need to show NP-completeness.

Can anyone push me into the right direction?


texts:
Given an infinite set $S \subseteq \mathbb{N}$, define the language:
$L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$
where $T_M$ is the number of steps that $M$ takes until it halts with the empty word $\epsilon$ as input (or $\infty$ if it doesn't halt).

What are the sets $S$ such that $L_S$ is decidable?

There are some more trivial cases, if $S = \{k,k+1,k+2, \dots \}$ for some $k \in \mathbb{N}$ then $L_S$ is clearly decidable, as we can simulate $M$ on $\epsilon$ for $k-1$ steps and accept if and only if $M$ didn't halt. though, if we take $S= \{k,k+2,k+4,\dots \}$ for some $k \in \mathbb{N}$, or even simply taking $S=\mathbb{N}_{even}$ or $S=\mathbb{N}_{odd}$ this becomes more of a problem, because there is no prevention from it being impossible to have a finite calculation for whether the number of steps until halting will be even in the cases where it halts. Although this seems undecidable I'm not sure how to prove this.
I generally suspect that $L_S$ is decidable if and only if $\mathbb{N} \setminus S$ is finite and $S$ is decidable


texts: Least common multiple of a list of numbers

texts:
I'm trying to learn computer science by doing some challenges. One is the following.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Let's generalize the problem from $1$ to $n$.
I thought of a loop between $n$ and $n/2$ as everything above $n/2$ is a multiple of something between $1$ and $n/2$. At each iteration, the result is the least common multiple of the loop variable and the precedent result (at the beginning the result is 1).
If I am correct, the complexity of this should be $\mathcal{O}(n/2)$. Am I right?
Is there any more efficient algorithms to solve this problem? If so witch one and what is their complexity?


texts: Average-case complexity of linear search where half of the elements in the array are duplicates

texts:
I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:

A(n) = $\frac{n + 1}{2}$

However, I am having trouble coming up with the Average Case complexity in the case where half of the elements in the size n array are duplicates. Take, for example, this array of integers:

1 2 6 6 5 4 6 6 6 3

Here is my thought-process so far:

I know that if we are looking for a specific element x in the array, the probability of doing it in a certain number of comparisons is $\frac{1}{n}$, since the distribution is uniform. So the average number of comparisons is still $\frac{n + 1}{2}$. (referencing this question's approved answer)

If the element we are looking for x is the duplicate number, however, then what is that probability of doing it in a certain number of comparisons? From there, how would I then compute the average-case complexity?


texts: The language of Turing machines that accept exactly $k$ inputs

texts:
For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts.  Is $X_k$ recursive, recursively enumerable or neither?

I think $X_k$ is NOT recursively enumerable because even if you generate every possible string, and test each one, if you find $k$ strings that M accepts, you still have to check every other string (in case $M$ accepts more than $k$ strings), which means your machine will loop indefinitely, and never find a yes-instance. However I'm not sure how you would show this, initially I thought I could reduce the NHP (Not Halting Problem) to L but that didn't go too well. Any ideas?


texts: Get all possible combinations of distributing x*n balls into n boxes

texts:
I'm trying to figure out how to get all combinations of putting x*n balls into n boxes.

There should be the same number of balls in each box.

If it was about putting n balls into n boxes, the result would be n! and the pseudocode:

for b1 in set:
   for b2 in set-b2:
      for b3 in set-b2-b3:
          results.append(b1,b2,b3,b4)

How can I get this way combinations of x*n instead of n balls so in one box there is x balls exactly?


texts: Is there anything that MUST be done on a multi-core CPU?

texts:
When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing requires massively parallel processing, but they argue that things like DOOM were done on single-core CPUs without GPUs.

Is there anything that must be done on a multi-core processor?

Assume there is infinite time for both development and running.


texts: First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I am a bit confused about this. There are classes where using logical synthesis, Karunaugh maps, state encodings, flip flops etc. one is able to construct hardware consisting of logic gates and flip-flops which realizes the desired DFA. Basically all processes that runs on the computer (no matter if is written in C# or Assembler), are at the lowest level realized through logical gates, zeros and ones. So it seems that programs firstly needs to be converted (by compiler I suppose) to some form as I've described. This might imply that every problem that is solvable using C# is solvable using FSM. But this is in contradiction to Chomsky hierarchy and all this theory related stuff, which says that you cannot do the same magic with regular expressions (which are based on FSM) that you can do on Turing machine (which is equivalent of any programming language, if I am wrong correct me please). Moreover, if flowcharts (or even C#, Java ... source codes) were equivalent to FSM why we do not have all software formally verified so far? There is mathematical apparatus for FSM and related stuff, so why do not formally verify everything and ensure the correctness? What I am missing here?


texts: Why does it take more than the original alphabet to generate sets of strings?

texts:
I am reading Computability by Nigel Cutland and I'm stumped on a brief statement about generating particular sets of strings that is not explained or given any examples.

First, here are some definitions provided by Cutland. Let $\Sigma$ be a finite set of symbols, called an alphabet. Write $\Sigma^*$ to denote the set of all string from $\Sigma$. $\mathscr{G}$ is a Post-system over $\Sigma$ if it consists of a finite alphabet $\Sigma$, a finite subset of $\Sigma^*$ (the axioms), and a finite set of productions (ways of generating more strings from existing ones).

He then says "Sometimes, in order to generate a particular set of strings in $\Sigma^*$ it is necessary to use auxiliary symbols in the generation process."

I can imagine how certain string manipulations could only possibly be achieved with some placeholder symbols but for my life I cannot actually come up with an example.

More explicitly, I am struggling to find a situation for which a Post-system $\mathscr{G}$ over $\Sigma_1 \supseteq \Sigma$ is required to generate some particular $X \subseteq \Sigma^*$. Shouldn't some $\mathscr{G}$ over $\Sigma$ be sufficient?


texts: The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 or FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF?


texts:
I am trying to solve the following problem:

Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry it is also true that $M[2][1]=1$). If $M[2][3]=1$, then $\{1,2,3\}$ is a community. If all other entries are $0$, then $\{0\}$ is a community by itself, $\{4\}$ is a community by itself, etc. One can think of $M$ as representation of a graph with $V$ nodes, and $E$ edges. $M$ is $VxV$ matrix and the entries with value $1$ correspond to edges of an undirected graph. For the above example, the total number of communities is $V-2$.

I need to explain the following:

If we solve the above problem with union and find operations (weighted quick union), it will take $O(E+Vlog(V))$ time, explain.

I wrote the code for this. I am also including weighted union and find algorithm code as well below for completeness (but it is a standard known algorithm I guess). With the way I implement it, it does not look like this algorithm takes O(E+Vlog(V)) time. I need to understand how can this be done in O(E+Vlog(V)) time.

It is said that find operation takes O(log(V)) time because the tree is almost balanced with weighted quick union algorithm.

This is my code:

The code for weighted quick union and find (given):

public class WeightedQuickUnion {

int[] parent;   // parent[i] = parent of i
int[] size;     // size[i] = number of sites in subtree rooted at i
int count;      // number of components

/**
 * Initializes an empty union–find data structure
 * Each site is initially in its own
 * component.
 * n is the number of sites
 */
public WeightedQuickUnion(int n) {
    count = n;
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}

/**
 * Return the number of components.
 *
 */
public int count() {
    return count;
}

/**
 * return the component identifier for the component containing p.
 * p the integer representing the item
 */
public int find(int p) {
    validate(p);
    while (p != parent[p])
        p = parent[p];
    return p;
}

// validate that p is a valid index
private void validate(int p) {
    int n = parent.length;
    if (p < 0 || p >= n) {
        throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
    }
}

/**
 * return true if the the item p and item q are in the same component.
 */
public boolean connected(int p, int q) {
    return find(p) == find(q);
}

/**
 * Merge the component containing p with the
 * the component containing q.
 */
public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);

    if (rootP == rootQ) return;

    // make smaller root point to larger one
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
    count--;
}


texts: O(·) is not a function, so how can a function be equal to it?

texts:
I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.

$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.


texts:
I got a question about who and how sets the transation function values in markov decision processes?
I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that? Do we have to determine the transition probability for each step or agents have to? Simply, it should be non-deterministic process, so how could someone tell the probability of that transition?
It should be %25 for each direction!!


texts:
I want to space points evenly (i.e. maximizing minimal distance between two points) on some smooth surface $S\subseteq\mathbf{R}^n$ (usually $n=3$), where I have a projection operator $p:\mathbf{R}^n\to S$ which approximates the closest point on the surface.  My idea is to place them randomly first and then let some repelling force act between them and reproject back to the surface after each iteration of the action.  This can be rather costly, if there are $10^3$ points, I have to compute the distance between $10^6$ points in one iterations, and I need a few iteration until everything stabilizes.

How can I imporove this process?  My ideas:

Measure the distance between every pair of points but compute the force only when the distance is smaller than some $a$, then do a few iterations (assuming the points don't move too far in one iteration) and recompute the distance after $k$ steps.
Choose some partition of the surface where each part has a set of 'neighbours' (including itself), compute for each point the location in the partition, i.e. the part it lies in, then let only the points in neighbouring parts act on each other, recompute the location after $k$ steps.


texts: Has this graph-theoretic problem got a known name? Is it NP-hard?

texts:
I am considering the following problem.

We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, in this graph:

If I contract the nodes $b$ and $c$ into a single node, I obtain a tree (quite a trivial one in this case):

In this example, only one subgraph had to be contracted, but in general more than one subgraph can be required. Note that this is not the only possibility, as contracting $c$ and $d$ would have been also fine. Also, trivially the entire graph could be contracted to obtain a trivial tree of a single node, so we have to look for a minimal solution.

So, the problem I am considering is: Given a DAG, find a set of minimal subgraphs which contractions would turn the DAG into a tree.

Is this problem $NP$-hard? Has it got a specific known name?


texts:
I am reading Yves Lafont's introductory paper Interaction Nets. Early in the beginning he mentions that max cannot be coded as follows

since in this coding it is not possible to choose which argument to look at first (so necessitating the need for a principle port). But I don't understand why it's wrong. I am trying to come up with an example where certain choice of rewritings will lead to a wrong answer.


texts: If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$

texts:
I found the following question with an answer here, but I can't understand the steps of the solution.

Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive.
Solution.  Since $A \leq_m \overline{A}$, it follows that $\overline{A} \leq_m A$, and since $A$ is in RE, it follows that $\overline{A}$ is also in RE. Since both $A$ and $\overline{A}$ are in RE, it follows that $A$ is in R (this follows from a theorem you learned in class).

Here $\le_m$ demotes mapping reducibility.
Actually I can't understand most of the answer. In particular:

Why does $A \leq_m \overline{A}$ imply $\overline{A} \leq_m A$?
I understand the following step (why $\overline{A}$ is in RE).
Which theorem is used to deduce that $A$ is in R? (I'm not a student in this class)


texts: Why does binary search take $O(\log n)$ time?

texts:
My question seems like an elementary question, but it's really not.

Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with the car with license plate AAA111. I want to find the car with license plate ZZZ999. I could do binary search to find the car with license plate ZZZ999, but I'm still going to have to walk the distance of one million cars, not a distance on the order of $\log 10^6$.

So this is why I'm asking how or why did computer scientists come up with the idea that binary search takes $O(\log n)$ time?


texts: What doest it mean: "computer is an intelligence amplifier"?

texts:
There is one example in Kolmogorov complexity books and related articles:

Consider we have a monkey at a typewriter and a monkey at a computer keyboard.

If the monkey types at random on a typewriter, the probability that it types out all the works of Shakespeare (assuming that the text is 1 million bits long) is about

p_typewriter (works of Shakespeare) ≈ 2^−1000000

If the monkey sits at a computer terminal, however, the probability that it types out Shakespeare is now related to the Kolmogorov complexity of the works of Shakespeare, which can be approximated by

K(works of Shakespeare) ≈ 250000 bits

using a program that compacts these works using 250000 bits.
Then:

p_computer(works of Shakespeare)≈2^−K(works of Shakespeare) ≈2^−250000

The example indicates that a random input to a computer is much more likely to produce “interesting” outputs than a random input to a typewriter.

We all know that a computer is an intelligence amplifier...

What actually the computer does?


texts: How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, "how big is each page"? etc

texts: No more information required. I would just like to know how to use the information provided.