texts:
I want to write a scheduling algorithm for the following scenario:

There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is that the user specifies the amount of daily hours available to work on tasks, so the algorithm can create a weekly schedule so the user can work in the tasks that require most attention, scheduled within the interval of hours (e.g. from 9:00 AM to 1:00 PM) the user decides. I have thought to require the user to specificate an approximate amount of time it needs to be used to complete each of the tasks.

The criteria would be priorizing the tasks with the nearest due date, highest difficulty and lowest progress first, then go for the tasks with nearest due date, highest difficulty and medium progress afterwards and so on.

What came to my mind was to create a function to calculate the value of a specific task, the higher the value, the more importance it has. With that in mind, sort all tasks by due date and by this calculated value using some greedy technique, but the issue here is what amount of time to dedicate on each task per day.

What kind of algorithm would this be? Is there any solution or book reference?


texts: Asymptotic time complexity of a two-loop program

texts:
I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for:

for (int x = 0; x < y; x++) {
    total  +=  total;
    total  +=  x;
}

and:

while (y > 0) {
    total  -=  y;
    y  =  y/2;
}

Combining those two pieces of code, what is the run time of that function and how do I calculate it?


texts: Can a DFA just have one state that is both the initial state and the final state?

texts:
so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}.

can i not just have one state (initial and final state) that loops a,b to itself?

thanks


texts: How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

texts:
Consider the recurrence
$$T(n)= 4T(\sqrt n) + \log^2n. $$
 I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.


texts: How to solve this dynamic programming puzzle on matrix?

texts:
We are given 4 integers N,M ,Q and Z.

Initially,the matrix has all zeroes in it.

We have to perform Q operations on the matrix.

In each operation, any cell of the matrix can be selected(same cell can be selected multiple times) .

Once a cell (x,y) is selected, you have to add  '1'  to all the elements of row 'x' and column 'y' .

After all the operations are done , there should be exactly "Z" numbers in the matrix which are odd.

How many sequences of Q-operations are possible for given $N,M,Q,Z$

Example:-

N=2,M=2,Q=2,Z=0

Answer:- 8

If we start by choosing the cell (1,1), the matrix becomes

2 1

1 0

Now we have two options ― we can choose either even-valued cell. If we choose (1,1) again, the matrix becomes

4 2

2 0

If we choose (2,2) instead, it becomes

2 2

2 2

For each of the other three possible initial cells, there are also two cells we can choose in the second operation, which is 4⋅2=8 ways in total.

$N$ and $M$ are dimensions of the matrix.

What have I tried:-

Number of ways to select 'Q' distinct points on a matrix:-

$^{N*M}C_{Q}$

Number of ways to select 'Q' points on a matrix with repetition allowed:-

$^{N*M+Q}C_{Q}$


texts: What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?

texts:
I am a master computer science student, and I am interested in both geometry and complexity theory.
So I would like to know what is the relations between discrete geometry, computer graphics, and complexity theory ?

I know the answer partially but I would like to have a clear answer since I do like to work on these fields in the future.

Thank you in advance.


texts: Are chatbots a good example of overfitting?

texts:
In my highschool class we are learning about Artificial Intelligence, and especially the problems that come with machine learning. I was wondering if chatbots like cleverbot were good examples of overfitting. Obviously, when you get a reply that doesn't make sense, is that a result of the bot modeling a training dataset too closely, or is it something else completely?
Thanks for the help


texts: Balanced weight distribution in buckets, with different weight per bucket

texts:
Is this problem a know variant of the optimisation version of the bin packing problem? There is an approximating algorithm for it?

Let $A = \{a_1,a_2,...a_n\}$ be a set of items, $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Each $a_i$ has a weight, based on the bin it is placed on (the item $a_i$ when placed on bin $b_j$ has weight $W_{i,j}$). Let $T(b_j)$ represent the total weight of the bucket $b_j$, $T(b_j) = \sum_{c=1}^t W_{c,j}$, which is the sum of the weights of each $a_c$ placed in $b_j$.
What is the optimal way to distribute all the items $a_i$ into the buckets $b_j$, such that each bucket $b_j$ has the almost same $T(b_j)$?

This problem came up when I'm trying to distribute a load in a distributed system, with distributed memory, such that each computer has almost the same amount of work. However, in my problem, when an item $a_i$ is placed in a specific computer, some other items from another set, say $x_{d..t}$, aggregate the work load on that server. The matrix $W_{c,j}$ is the map of the aggregated weights, for all choices of $b_j$ for the item $a_i$.


texts: Query Langauge analogy to Turing Completeness

texts: Is there a completeness property for query languages (like SQL, Cypher, Datalog, etc) that is analogous to Turing completeness in programming languages? I wondered if it is something like being able to describe any subset of the facts in the database.


texts:
While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a constant.
But when $b$ is dependent on $n$, can we say that number of levels are still $\log_{b}n$?
For example, in
$T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$

Can we say that number of levels in the recursion tree are equal to $\log_{\sqrt{n}}n = 2$?
I guess this is wrong but I am unable to reason it properly, please explain me the reason "why this is wrong?"(If it really is).


texts: Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional?

texts:
Theorem II.5.8 in P. Odifreddi's Classical Recursion Theory states that

  If $\{\psi_e\}_{e\in\omega}$ is an acceptable system of indices, then there is a recursive permutation $h$ such that
  $$ h(\psi_e(x)) = \varphi_{h(e)}(h(x)) . $$

where $\varphi$ is the standard enumeration of p.c. functions.

My question is whether the converse case holds: For the standard enumeration $\varphi$, some permutation $h$ and some computable enumeration of p.c. functions $\psi$, if we have $h(\psi_e(x)) = \varphi_{h(e)}(h(x))$, then $\psi$ is an acceptable enumeration.

Some possible approaches:

Prove this simpler form and then prove it is equivalent to question:

For some computable permutation $h$ and standard enumeration $\varphi$, $\theta_e(x) = h(\varphi_e(x))$ is also an acceptable enumeration.

H. Rogers' Theory of Recursive Functions p54, defines a universal partial function to be a partial computable function $\psi$ for which exists a computable function $f$ of two variables, such that $\forall x; \varphi_x = \lambda y.\psi f(x,y)$. So $f$ codes both index and argument and $\psi$ takes it as its single input. Then it proves that

  If $\psi$ is universal and $g$ and $h$ are recursive permutations, then $\eta = g^{-1}\psi h$ is universal.

Is this statement, for $g=h$, equivalent to the mentioned converse above?

It seemed very obvious to me at first, though I couldn't manage to prove it. What am I possibly missing?

Update
Removed the second question as an intermediate approach to solve the main question.


texts: Edit distance proof when last chars of 2 strings are the same

texts:
from Wagner–Fischer_algorithm:
I understand substitution cost needs to be adjusted, either 0 or 1:
 for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

But in later proof part, it claims when s[i] == t[j], d[i, j] = d[i-1, j-1]:

If s[i] = t[j], and we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i] and just leave the last character alone, giving k operations.

I don't understand, shouldn't it be d[i, j] = min(d[i-1, j-1], d[i-1, j] + 1, d[i, j-1]+1)?
It's also mentioned in edit distance wiki

How do you prove if the last chars are matched, d[i, j] is d[i-1, j-1]?

following the lemma here,
I can think one way to prove this is to assert minimal is not from d[i-1, j-1] when s[i] = t[j]. Then draw contradiction.
if minimal is not from d[i-1, j-1], the minimum must come from

deleting last char from s, s[i].
or inserting last char from t, t[j].

If we go with 1, we need to match s[0..i-1] with t[0..j].
A: if s[i-1] != t[j],

insert t[j] to end of s, we are rewinding to the original state.
modify s[i-1] to t[j], it's equvilent to deleting s[i-1] (+1) when matching s[i-1] with t[j-1], whose minimum is d[i-1, j-1].
delete s[i-1] -> only viable way

B: if s[i-1] = t[j],

no insert t[j], otherwise the previous deletion is redundant.
no modification: equivalent to 2nd point in discussion A.
deletion -> viable

Combine A and B, only deletion is acceptable and it's impossible to match if only deletion is performed on s.
Do you guys think this proof is correct?


texts:
This is a research problem and I am just wondering if there is any already existing answer in any computer vision related paper that may have skipped my notice since this is not my active area of research.

Imagine you have a shape. Now there is a large class of algorithm in existence collectively known as visual descriptor with properties such as rotation invariance & scale invariance (say Histogram of Oriented Gradients) used in computer vision algorithm such as image recognition.

The pipeline of this is as follows :
Shape ---> Visual Descriptors ---> Neural Nets/Other ML Techniques

However, it is my understanding that such a descriptor is not reversible. That is given the Histogram of Oriented Gradients, I cannot reconstruct the original shape. Which is in general fine because such Networks/NN-Search algorithms usually return a probabilistic value of distances which can be used to match the shape descriptor to some already existing shape.

My question is this : Does there exist any algorithm in Computer Vision which takes a 2D shape and produces a vector representation (it doesn't have to be rotation or scale invariant) from where I can reconstruct the original shape ?

That is :
Shape --> Visual Contour Descriptor_1 ---> Algorithm ---> Visual Contour Descriptor_2 ---> Some New Shape

Additional Clarifications: I have already tried general approaches such as using densely sampled points in the shape, using Spline Reps etc? If someone knows any existing literature/techniques in computer vision that produce shape vector representations, that would be of much help. I don't want to spend time trying out my own representation and claiming it to be my contribution only to find out that the problem has already been solved by someone in the Computer Vision community.

Any help is welcome.


texts: What is the minimal pumping length of this string $(01)^*$

texts:
In this answer, it is told that the minimal $p$ value is $1$. One of the conditions of the pumping lemma is that

$|xy| \leq p$

Now if we try to split a string $01^p$, we might do it like this:

$x=\epsilon$, $y=01$, $z=01^{p-1}$

But this decomposition contradicts the above condition. If we arrive at a contradiction, then how $p$ can be equal $1$?

Besides, is there a maximum pumping length? Various sources define $p$ as constant, and if it is a constant, there should be a single value instead of minimum and maximum range.


texts: Problem with Cormen's treatment of the Rabin-Karp algorithm

texts:
I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. Specifically, when the authors start proposing about some modulo operations for solving some problem, I am unable to follow. To be precise, the paragraphs from

  We have intentionally overlooked one problem: p and ts may be too
  large too work with conveniently...

on till equation 32.2 (pp 991 in 3rd edition) are the paragraphs I am having problems with.

What does "convenient" mean here? Why do they use modulo? I am totally lost.
Is it possible to explain this in simple english?

I will appreciate if someone can help me in understanding this paragraph. And if there is any other reference (with similar mathematical treatment) where this can be read, please tell me.


texts: Failing to solve a recurrence by induction

texts:
My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which implies
$$0\geq 1$$
which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.
However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don't understand how should I be able to justify that, is this a scenario in which "induction fails" ? because I've never heard of such one.


texts: Optimal algorithm for finding the kernel of a polyhderon

texts:
The kernel of a polygon $P$ is the set of all points in $P$ from which $P$ is entirely visible. Equivalently, it is the convex region given by the intersection of the half-planes defined by the edges of $P$ (facing into $P$). The definition generalizes for a polyhedron.

It is known that the kernel of a polygon can be found in linear time by exploiting the order of the half-planes (see "An Optimal Algorithm for Finding the Kernel of a Polygon" by Lee and Preparata).

Is there a linear algorithm for a polyhedron as well (or some other result about optimality)?


texts: How do calculators convert from decimal to fraction?

texts:
Sorry if this question is either obvious or ignorant. I am a high school student with only the computer science knowledge I have taught myself.

Calculators have a function that can convert numbers from decimal to fractional equivalents. For example, 0.5 becomes 1/2, and 0.666666667 becomes 2/3.

I doubt that the calculator has these values kept in storage to look up, so there must be an algorithm for this to be determined.

The simplest possible algorithm I can imagine would resemble this:

for (double i = 0; i < someLimit; i++){
    for (double j = 0; j < someLimit; j += 1){
        if (i / j == decimal){ //return these values }
    }
}

This seems far too inefficient to be the algorithm used by calculators. Even on low power scientific calculators, this operation completes quickly.

How do calculators calculate the fractional equivalent of a decimal?


texts: Proving that finding wheel subgraphs is NP-complete

texts:
Can you help me with this problem ?

  Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.


texts: How do I find the number of inversions using a red black tree?

texts:
I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node into a red black tree then by inserting the node if it inserts properly then it means the values are in the proper order and there's no inversions. If a value is inserted and the order property is not satisfied then we need to either rotate the tree or change the color of the branches to satisfy the order property. So I have an insert method that looks like this:

private Node put(Node h, Key key, Value val){
        if(h==null)
            return new Node(key, val, 1, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else h.val = val;

        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);

        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);

        if (isRed(h.left) && isRed(h.right))
            flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

Now if I declared a variable that kept count of all the inversions then at what points would I need to put it at and is there any code that is unnecessary when counting the inversions? What I'm thinking of doing is replacing all the rotations and color changes with inversion incrementing. Would doing that still give me the right number of inversions in O(nlogn) time?


texts: Construct regular expression for language

texts:
How to construct regular expression for language L which contain all words in which there is a letter 'a' and the letter 'b'?
Of course, I understand that it's easy problem but I just start to learn this science? Please, any advices and hints.


texts: necessary and sufficient pumping lemma - bounded pumping variant

texts:
There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.

According to that lemma:

A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$, $  x=uvw \cap |v|\ge 1$ such that:

$$\forall i \ge 0,\ \forall z\in \Sigma^*: uvwz\in L \iff uv^iwz\in L.$$

My question to you is: is there any way changing the for all $i \ge 0$ condition to for all $ 0\le i\le N$ for some $N$ - and the lemma will still be correct?

That $N$ may be constant, depend on the lemma's k, and so on.

I can't find an approach to prove it, any ideas?


texts:
I know that one can compute the expression $X^{-1}\mathbf{v}$ quickly with conjugate gradient method. Is there a similar approach for computing $\mathrm{tr}(X^{-1}Y)$?

Similarly interesting to me are $\mathrm{tr}(X^{-1})$ and $\mathrm{tr}(X^{-1}YX^{-1}Y)$.


texts: Showing that a directed graph that has a cycle belongs to NL

texts:
DCG = { G | Directed graphs that contains a cycle }

How can I proof that DCG belongs to NL?


texts: Question on the properties of red black trees

texts:
Problem statement

Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the right subtree of $u$, before the properties of the red black tree are broken?

Attempt at a solution

I was given the answer $O(n^2)$ (past exam sheet question with the answer marked). However, I don't think it's correct, unless I have misunderstood the problem.

According to  CLRS the properties of a red black tree are the following:

Every node is either red or black
The root is black
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Since we are in some internal node $u$, from the properties we infer that all simple paths starting from $u$ and ending in some leaf, should contain the same number of black nodes.

We are given that in the left subtree of $u$ we have $n$ nodes, and our goal is to maximize the number of nodes that we have in the right subtree. It seems natural to assume that the left subtree is a chain containing $n$ black nodes, because in this way, we can make the right subtree of $u$ be a complete binary tree, where every simple path starting from the root of the subtree and ending in some leaf contains exactly $n$ black nodes. And not only that, we can also in the end add red levels of nodes in between black levels, thus increasing the size of the right subtree by 2.

Reducing the black height of the left subtree, will only imply fewer nodes in the right subtree.

So lets find the number of nodes in the right subtree. Essentially we have a complete binary tree of height $n$, so the number of nodes will be:

$S = \sum_{i=0}^{n-1}2^n$

$-2S = \sum_{i=1}^{n}2^n$

$S(1-2) = 1 - 2^n$

$S = 2^n - 1$

so the answer is $O(2^n)$. Am I wrong or was there a typo in the exam sheet?


texts:
I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.

  Suppose there is a game with 2 players, A and B and a list of
  positive integers. Player A starts by taking out a number from the list, player
  B does the same and so on after the there are no longer numbers in the
  list. Both players sum up the picked numbers. Each player scores the difference between his sum and the opponent's one. The question is what is the
  maximum score player A can obtain if both players play in an optimal
  manner.

Now, for this I figured out that the optimal strategy for each player is to take the biggest number at each step.

The following 2 modification:

  At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?

and

  At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

For the second modification I can think of a brute-force approach, i.e. computing the tree of all possibilities, but this does not work for big input data. I believe that there is some kind of DP algorithm.

For the first modification I can't think of an idea.

Can someone help with some ideas for the 2 modifications, what algorithm to design in order to get the response?

[LATTER EDIT]

For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/


texts: Testing regular expressions algorithmically

texts:
Is it possible to  test algorithmically whether the language of a given automaton is empty?

If I have a language L, could I say that L intersection with the empty set is L?


texts:
I don't mean compiler flags for pipelining. I would like to program in a way that helps the compiler do optimizations using pipelining. I mean I want to order instructions in C in such a way that GCC (or other compiler) can easily pipeline my instructions. For example, if I have:
a+=b
c=a/b
d+=b
f+=b

Here, the last two 'add' operations would be pipelined, but not the first. I would turn it into:
a+=b
d+=b
f+=b
c=a/b

Notice that the three 'add' operations can be pipelined, but the floating point division cannot.
I want to know, is there more cases in which I can help the compiler do pipelining optimizations? What operations are the ones that can be generally pipelined in modern processors, and that compilers can recognize in code?


texts: Is it possible to find the nth term  of a Fibonacci sequence using a definitive for loop?

texts:
I'm using the book Introduction to Computer Science by John Zelle and at the end of Chapter 3 (Computing with numbers), I'm asked to find the nth term of a Fibonacci sequence presumably using a definitive for loop, as no other decision structure has been introduced yet.

Is this possible? I've tried everything I could think of.

**I know how to solve it using if statements and such. But the book hasn't yet covered decision structures, yet it asks me to find the nth term(given by the user). So I can only presume to know how to do this using "for" loops as this is all that has been covered so far


texts: Python: A doubt on time and space complexity on string slicing

texts:
This qns is from my school's exam paper.

Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase.

The function remove takes as inputs 2 strings, a letter and a word, and outputs the word with all occurrences of letter removed.

Provide an iterative implementation of the function remove and briefly explain the time and space complexity of the function you have written.

Attached below was my code, which is the same as the solution provided.

However I got stumped when I tried to explain the time and space complexity as O(n) and O(1) respectively as the answer given was O(n^2) and O(n).

The explanation provided by the examiner is:

Time complexity: O(n^2) where n is the length of the input string. This is because in every loop iteration, the string concatenation of new_word gets longer until it is at worst, length n.

Space complexity: O(n), even though there are no delayed operations or new objects being created every iteration, the new string created at worst can be the same length as the original string if there are no letters removed.

My practice is when I explain something, I should be able to map it out mathematically.

Time: Sum of time taken for each iteration OR Sum of time for each recursion

1)I do not understand why string concatenation contributes to time complexity. For recursive codes its clear cut as there is string slicing involved(s[0] and s[1:], formation of s[1:] will take O(n-1),O(1) from s[0] is negligible) in every recursive call, sum of time is n+(n-1)+…+1=O(n^2). For the explanation of iterative, should I just accept it or is there a theory behind why concatenation adds to time complexity.

Space: Sum of space taken for each recursion OR sum of space taken for each iteration

2) I initially thought space for recursion and iteration is calculated the same way. Is it correct to accept that for iteration, space should be calculated as the space needed for the most demanding iteration instead of the accumulative sum of space for all iterations. Most demanding would then be when new_word and word are equivalent.

3) I actually accepted the fact that iteration usually takes up O(1) space and would bomb it everytime I can. What is really the reason behind deeming the space complexity of iterative to be O(1)?

Correct me at any point as I find that I am memorising and not understanding many things at this point.

def remove(letter,word):
    new_word=""
    for i in word:
        if letter!=i:
            new_word+=i
    return new_word


texts: How does adaptative Huffman coding (Vitter algorithm) work?

texts:
I have implemented Vitter algorithm thanks to the Wikipedia article. However I don't really understand how some parts of the algorithm make the algorithm more efficient:

 IF (new p is sibling to NYT) THEN
             leaf_to_increment = p
             p = parent of p

Here I don't understand why is the condition necessary. What would it change if we just removed this portion of the algorithm?

Also, in the slide and increment procedure, I don't understand why if the node is an internal node then p becomes the former parent of p while if it is a leaf node then p becomes the new parent of p.

 previous_p = parent of p
 IF (p is an internal node) THEN
         Slide p in the tree higher than the leaf nodes of weight wt + 1
         increase weight of p by 1
         p = previous_p
 ELSE
         Slide p in the tree higher than the internal nodes of weight wt
         increase weight of p by 1
         p = new parent of p.

Are these things here to preserve the Vitter invariant (block of leaves then block of internal nodes in ascending order of weight, from bottom to top, left to right..) or to improve the efficiency of the algorithm?

Also, how is it more efficient to "slide" the nodes instead of just swapping two nodes as in FGK algorithm? I can't find any interesting article about Vitter algorithm.


texts: Relationship of algorithm complexity and automata class

texts: I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!


texts: For an NFA, can we always find a RAM, which recognises the same language?


texts: Swap elements using integer addition and multiplication gates

texts:
I need to swap two integers using only integer addition and multiplication gates.
I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap operation swaps only if the integers being compared are in wrong order. I've to implement this operation using just integer addition and multiplication as the atomic operations. I've figured out the comparing bit, but I need to efficiently swap integers.
Is there an efficient solution (minimum multiplication gates) to this problem?

P.S: I have integers in the form of binary vectors, but I can't apply mod 2 operations on them. I can only use integer addition and multiplication.


texts:
I can not find any simple and detailed source of how to add non-recursive let-expressions to pure type systems.

The best I found is the Henk paper by Simon Peyton Jones, but his explanation of this point is very brief.

Can someone link some references about this topic (source code is accepted)?

EDIT

The let I want to add has the following syntax:

let x : T = M in N

where x is the variable name, T is its type, M is the expression with which all free occurrences of x in expression N will be replaced. It can only introduce nested definitions, so recursion is impossible.

In untyped lambda calculus it is syntactic sugar. By analogy it should be equivalent to (λ(x : T) -> N) M, but as you know this conversion does not type-check in PTS, so new type rules must be included.


texts: Back invalidation to maintain inclusion in inclusive cache

texts:
For an L2 cache that is strictly inclusive of the L1 cache, if a block to be evicted is also present in L1, then back invalidation is required to maintain the inclusion property.

I am interested in some details of how back invalidation is handled.

When an L2 block is evicted, is back invalidation command always sent to the L1 or only sent if the block is in the L1 cache?
If the back invalidation is only sent when the block is in L1, how does the L2 cache maintain the information that a given L2 block is also in L1?
When invalidating L1 block by back invalidation, what happens if the L1 block is dirty? Is it written back to main memory bypassing L2 (assume write-back caches and L2 is the last level cache)?


texts: Simple proof for NP-completeness of Edge Dominating Set

texts:
In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D.
The Minimum Edge Dominating Set problem is to find an edge dominating set
of minimum cardinality. The decision version of this problem is known to be NP-complete, but I would like to inquire whether a relatively simple proof of this fact is known.

The only proof I found in the literature  is in the paper that first tackled this problem, by Gavril and Yannakakis. However, the above proof makes use of the fact that Vertex Cover is NP-complete for planar cubic graphs, and the fact that bipartite graphs of degree d can be d-edge-colored. I would prefer a simpler proof, that would only make use of facts typically known to undergraduates who took an algorithms course.


texts: DCFL with prefix property have LR(0) grammar?

texts:
There are two important theorems about LR(k) grammars and DCFL. Mentioned here.

A language has an LR(1) grammar iff it is DCFL.
A language has an LR(0) grammar iff it is DCFL and has prefix property.

I have counter example for 2nd theorem, plz see if it is valid counterexample.
(Ofcourse its not valid and I am wrong, But what wrong I am doing here ?)
DCFL without prefix property:    $\{b(ab)^n \mid n\geq0\}$
2nd theorem says it should not have $LR(0)$ grammar, but here it is-
$ S \rightarrow Sab \\S \rightarrow b$
PS: This is my first question here, sorry if I violated any protocol.


texts: In computer science how is using passive voice regarded?

texts: A soft question, when I was in high school and in University I took scientific writing classes and people told me I should use passive voice as much as possible to sound objective, but when I entered grad school people told me I should not use passive voice unless I work in Chemistry. So Which one should I follow?


texts: Graph Traversal Solutions for "Find all unique paths" Problem

texts:
I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with the constraint that it can only move down or to the right.

It looks like the standard way to solve this is with the top-down dynamic programming approach but I was wondering if a graph traversal algorithm could also work.

The problem with graph traversal algorithms is that you do not revisit nodes that you have already seen but many unique paths can visit the same node.  So if you got rid of the constraint that you cannot revisit a node, would a graph traversal method work here? This is also a special case where you cannot get stuck in an infinite loop because the robot can only go down or right so it can never go back to a node it has already been to.


texts: Why do P-class problems not require a witness like NP?

texts:
If I am given a problem in P, to claim that I have solved it, I would need to give proof, right? For example, to show a number is not prime, if I use some deterministic algorithm, I can return the prime factors of that number.

I am finding it weird that P does not require a witness/certificate in the definition like NP.


texts:
I'm working on a mini lisp and now I'm wonder about scopes. For my case I'll have this constructs that introduce scopes.

lambdas introduce it's arguments
let binds
and modules

The way I worked on this was, a single scope is an associate array, and all scopes are stacked from inner to out. Also I have a global scope that is read only (only builtins), and finally a lookup function that lookups for a symbol in all scopes in the right order.
During the evaluation, when something introduces a scope, for example a function call, I push the variables to the scope stack and then evaluate the body. I want to get rid of this mutation because it makes hard to parallelize the evaluator (the scope stack is a global in my interpreter).
I couldn't find any formal definition of scope or anything like that, closer I get was E register from SECD machine.
Does anybody know any work done in this direction? Having references would be nice to have some insights


texts: Existence of polynomial time reduction from P to R?

texts:
Why the next idea doesn't work:

If L_2 in R and L_1 in P and the languages are not trivial,
then there is a polynomial-time reduction from L_1 to L_2

I know that if such reduction exists, than L_1 is also in R --> But L_1 is in P and P is in R, so everything looks OK :)

Will be glad for your help here.


texts: are the activations of hidden nodes in an ANN binary or real valued?

texts:
this may seem to be a pretty basic question, but it is something i have been puzzling over for some time.

when calculating the activations of nodes in a hidden layer in an ANN using sigmoid neurons for use with the backpropagation algorithm - should the output of the neuron be thresholded or not?

say the activation vector for layer $i$ is calculated by:

$\mathbf{a}_i = \sigma(\mathbf{w}_i\mathbf{a}_{i-1} + \mathbf{b}_i)$

where $\sigma$ is the sigmoid activation function

should it actually be:

$\mathbf{a}_i = (\sigma(\mathbf{w}_i\mathbf{a}_{i-1} + \mathbf{b}_i) > 0.5$)

to ensure that $\mathbf{a}_i$ is binary vector? or should the real value from $\sigma$ be passed on to the next layer?

my main reason for asking this is that biological neurons don't transmit real valued data, but i haven't really been able to find any definitive answer anywhere to this question or anyone who explicitly says to threshold the value; it seems like a pretty fundamental question to the functioning of ANNs, so either i am missing something in my reading, or it is considered so common-sense that it doesn't need to be mentioned much.

any help would be greatly appreciated


texts: Go-Back-N ARQ Protocol Throughput Question

texts:
I am an undergraduate studying Data Coms and Networking and this question about go-back-N ARQ popped up that I am struggling to get my head around and cant find anything similar online. Any help at all would be greatly appreciated.

The only thing I have at all is that throughput could be defined by (Packet bits + overhead)/N. Is this at all on the right path?

QUESTION
Consider the Go-Back-N ARQ protocol with N=5 and 4 bits used for sequence numbering. The user data frame is 3000 bits long where 100 bits are overhead for header and error check, etc. The frame transmission rate is 2Mbps. Assume that the medium does not reorder the frames. The outstanding frames will be retransmitted when the sending window becomes empty. The probability that a data frame would be received without any errors is 0.3.

i)  What is the effective data transmission rate of this protocol?

ii) Suppose that at time t, the receiver is waiting for an information frame with binary sequence number 1001.  What is the possible sequence number Slast in binary inside the sender’s window at time t? Justify your answer.


texts: Proving asymptotic notations for functions

texts:
I recently started learning about asymptotic notations. While I was doing practice questions (not HW) I found various question that stumped me totally. So I just want some pointers on how to go by solving these type of questions. So here is a basic question.
Given the following,

  If $f(n) = \Omega(h(n))$ and $g(n) = O(h(n))$ then $f(n) = \Omega(g(n))$.

How can I solve this and see if that is true or false.
Here is what I have tried so far,
I tried to use definitions of big-$O$ and big-$\Omega$ on $f(n)$, $g(n)$ and $h(n)$ and then combining those resulting equations to prove/disprove the outcome but I got confused.

So I need explanation of this solutions so I can make it more clear for myself.
Any help would be appreciated.


texts: Control flow graphs - Tree decomposition

texts:
Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example :

While A
if B
do ..
else do ..
end while

For above example, while doing decomposition, I can say its

  D2 (D1)

i.e while  and then inside while, its if-then-else.

Considering same situation. How can you represent

  CONTINUE and BREAK statements

Ever for  FOR statement there is no defined terminology like for while and if then else. FOR statement falls under while.

My prof says in theory, there is nothing about Break and continue statement and I couldnt find anything online too.

For example :

# include <stdio.h>
int main(){
   float num,average,sum;
   int i,n;
   printf("Maximum no. of inputs\n");
   scanf("%d",&n);
   for(i=1;i<=n;++i){
       printf("Enter n%d: ",i);
       scanf("%f",&num);
       if(num<0.0)
       break;                     //for loop breaks if num<0.0
       sum=sum+num;
}
  average=sum/(i-1);
  printf("Average=%.2f",average);
  return 0;
}

Control flow graph for this is as below: the nodes has line number written : (Sorry the image is side ways)

I decomposed this as :

P1;P1;D2(P1;P1;D1);P1

* P1 represents set of statements outside loops

I'm not sure if this is correct. My professors says to use something as D22 for break, like create a new term from above image.

  My main question here is the decomposition. I Know that i drew the
  CFG correctly, but is the decomposition correct according to the first
  image?. The break state kind of creates a while as you can see in CFG,
  but i'm not sure if it has to be considered as while and I guess we
  cannot, as per my professor.

I am working on this and wanted to know, if anyone has come across something for Break and continue statements while decomposition of graphs, please let me know.

Thanks.

PS : Please, Let me know, if am unclear and if anymore info is needed. I can probably write down an example and upload the picture.


texts: Different properties of Heavy-Hitters and Count-Min Sketch algorithms?

texts:
I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an implementation of Count-min Sketch plus a linked list to store the "heavy hitters" instead?

As far as I can tell, both require $O(k)$ space where $k$ is the number of heavy hitters to track; both $O(k)$ time to retreive the ordered values; to insert values the former requires $O(1)$ time, the latter $O(\ln{{1}\over{δ}})$. The accuracy and real-world performance differences I'm not sure about and have struggled to find write-ups that aren't too notation heavy that I can understand.


texts: Quickly obtaining sums of sets of numbers

texts:
We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$.  We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For example:

$$s_k = a_3 + a_5 + a_{17} + a_{22} + a_{35}$$

There is more structure to the sums, however.  The sums are split into $m / \alpha$ groups, where each sum is in only one group.  For example, and to make things easier, sums $s_1$, $s_2$,...,$s_{\alpha}$ are in group 1, sums $s_{ \alpha + 1}$,...,$s_{2\alpha}$ are in group 2, and so on.  Then we know that each bit will occur exactly once in each group.

So for example, the bit $a_1$ will appear in each group, the bit $a_2$ will appear once in each group, and so on...

QUESTION

How fast can we calculate all of the sums?

MY IDEAS

If we assume that there are $\alpha$ sums in each group, then there are at most $2^\alpha$ combinations of bits.  For example, if there are two sums, we know that there are four combinations of bits:

(0)  Bits that are not in either sum

(1)  Bits that are in sum 1 ($s_1$), but not in sum 2 ($s_2$)

(2)  Bits that are not in sum 1 ($s_1$), but are in sum 2 ($s_2$)

(3)  Bits that are in both sums.

Thus we need at most $n$ additions to calculate the sums of each of the $m / \alpha$ groups.  So our total time is at most $n(m/\alpha)$ additions, since there are $m/\alpha$ groups.

However, I believe that we can do better!  I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.


texts: Where is left recursion in this little CF grammar?

texts:
S → D
D → E | EC
E → anyId
C → B | .D | B.D
B → <S> | <SA>
A → ,S | ,SA

The tool I am using keeps complaining about left recursion in this grammar. I can't see where.

The language recognized is something like:

anyId
anyId.anyId
anyId<anyId>
anyId<anyId>.anyId<anyId,anyId>


texts:
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $

I know these inequalities can be solved using Bellman-Ford algorithm. But there is also another condition. I want to find the solution that maximizes $\ x_n - x_1$

As far as I know the default Bellman-Ford algorithm minimizes it. How do I do that?


texts:
This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it.

Suppose there is a collection of shared resources, and a collection of possible processes. Each process consumes fixed quantities of each resource and provides a fixed benefit. Each process can be applied zero or more times (but no fractional amounts), and resources can be left unused.

How can a distribution which maximises the total benefit be found? Brute-forcing each possible allocation will always find an answer, but is there a more optimal way?

An attempt to formalise the question:

$$
\text{Given resources } R \in \mathbb{R}_{\ge0}^n \\
\text{and process requirements } P \in \mathbb{R}_{\ge0}^{m,n} \\
\text{and process outputs } O \in \mathbb{R}_{\ge0}^m \\
\text{find } N \in \mathbb{Z}_{\ge0}^m \\
\text{such that no resource is over-spent: } \sum_{i=0}^m{N_i P_{i,j}} \le R_j \ \forall \ j \\
\text{and } N \cdot O \text{ is maximised}
$$


texts: How can I compare two faces using facial landmarks?

texts:
I'm using first_order_model for an expression transfer between an video and a static image.

Part of the algorithm makes a facial comparison to get the frame in the video where the face is best aligned with the foto.

This is made with:

def normalize_kp(kp):                           # original kp is (step 1)
    kp = kp - kp.mean(axis=0, keepdims=True)    # (step 2)
    area = ConvexHull(kp[:, :2]).volume
    area = np.sqrt(area)
    kp[:, :2] = kp[:, :2] / area                # (step 3)
    return kp

normalized_kp_source      = normalize_kp(get_landmarks(source))
normalized_kp_destination = normalize_kp(get_landmarks(destination))

diff = (np.abs(normalized_kp_source - normalized_kp_destination) ** 2).sum()

What I could not understand is how normalize_kp works. I understand the result of putting the faces roughly in the same "size" and coordinate system.

Below, a comparison between the landmarks in each step of the normalisation:

The question:

How can I compare face alignment. How this normalization works?


texts: What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

texts:
Background

I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:

$$
\text{New List}= \{A, B, C, ...\}
$$

Here is a generic illustration of what the list of pairs looks like:

list of pairs = [['A', 'A1'],
                 ['A', 'A2'],
                 ['A', 'A3'],
                 ['B', 'B1'],
                 ['C', 'C1'],
                  ...

Here is some actual data:

`['394.NGR_c13430',
  '(3R)-hydroxymyristoyl-[acyl-carrier-protein] dehydratase'],`
`['394.NGR_c31790',
  '(Di)nucleoside polyphosphate hydrolase'],`
`['394.NGR_c00410',
  '(Dimethylallyl)adenosine tRNA methylthiotransferase MiaB'],`
`['394.NGR_c28950',
  '1,4-alpha-D-glucan:1,4-alpha-D-glucan 6-glucosyl-transferase'],`
`['394.NGR_c28950',
  '1,4-alpha-glucan branching enzyme GlgB'],`
`['394.NGR_c34010', '1-(5-phosphoribosyl)-5-[(5-ph']]`
`    9606.ENSP00000170630   1IAR`
`    9606.ENSP00000170630   1ITE`
`    9606.ENSP00000170630   287261`
`    9606.ENSP00000170630   287263`
`    9606.ENSP00000170630   287265`
`    9606.ENSP00000170630   287267`
`    9606.ENSP00000170630   287269`
`    9606.ENSP00000170630   287271`
`    9606.ENSP00000170630   3566`

(Sorry for the sloppy formatting, but I hope you get the idea.)

My Attempt

I'm doing:

    names := empty list
    for row in list:
    |   name := first element in row
    |   for name in names:
    |   |    if name not in names:
    |   |    |   append name to names

for line in proteins:
|    name := first element in "line"
|    for prot in prots:
|    |    if prot in name:
|    |    |    append alias to D_{prot}

Where D_{prot} is $D_{prot}$, a sublist in D containing the $A_{i's}$ of prot.

However, this approach is extremely slow. Even running this on only 10 million of the pairs takes more than half an hour. I'm only a statistician and not familiar with the intricacies of computer science or Python. Is there a better way of doing this?

Also...

I know for a fact that there are only 10 million unique values ($A$ values).

With $n$ = 50 million and $p$ = 10 million, I thought my algorithm was $O(np)$. Is it? Is this efficient?

Thank you


texts: Can we somehow get functoriality from purely type-theoretic reasoning?

texts:
In this question, I asked about how to prove naturality from parametric polymorphism, using parametricity. The current answer to that question simply assumes that the functors in question satisfy the functoriality conditions.
Is there a "free theorem" result for functoriality? i.e. is it sometimes possible to see from the type of a "functor" that it is indeed a functor?


texts: ML to approximate a dampened harmonic oscillator from a related curve

texts:
I want to approximate the output of a Monte Carlo simulation that takes a probability density function sampled at x-axis points $0,1,2,3,\ldots,n$ and outputs what tends to look like a dampened harmonic oscillator.

Four examples appear below.  The blue dots are the sampled pdf (or pmf), and the heights of the black lines give the curves I want to approximate.

My inclination is that I would be able to use Machine Learning to either (a) provide second-order differential equations that approximate the output of the Monte Carlo simulation, or (b) bypass the dampened harmonic idea and approximate the output of the MC simulation directly.

Needless to say, I can generate tons of learning data using the MC simulation.  I should also mention that once the ML has done its training, it needs to perform much faster than the MC simulation!

I'm hoping this will be a good introduction to ML algorithms for me, but I'm not sure where I would start.  Hints about learning resources and software frameworks to do my research in are welcome.

Can this be solved with ML?
If so, would I bother with the oscillator stuff?


texts: Best way to find and store difference between two strings

texts:
I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - please write about it).
What algorithms and data models are suitable to find the difference between two strings and to compactly store this difference, as well as to implement this difference in a string?
If my question isn't clear enough, please say so.


texts:
How to proof UNIQUE-SAT is in $\Delta^p_2$ or in $P^{sat}$

1) when given a bool formula can I ask oracle whether the given formula has at least one satisfying truth assignment and whether it has at least two?

2) Is UNIQUE-SAT in NP?


texts: What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?

texts:
In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the likelihood that a random pattern is a GoE as n increases?
Also, by the Garden of Eden-theorem, only cellular automata which are non-injective, that is, for which a given pattern may have more than one predecessor, contain Gardens of Eden.

Is it then in general impossible to see whether a given cellular automaton pattern at some time-step is derived from a GoE (since there could also have been a non-GoE ancestor leading to the same state)? That is, does the evolution of the CA 'wash out' the information that it is derived from a GoE? (I hope it's sufficiently clear what I mean.)

Furthermore, is there a relation between GoE-patterns and uncomputability/undecidability? It seems to me that if you consider the CA to be implementing some computation, then the GoEs are 'outputs that could never be produced', at least heuristically, but a brief Google search led nowhere. Perhaps asked another way, is there a relation between the existence of GoEs and the universality of a CA? I know Life is both universal and has GoEs, but I don't know about the general case. Any pointers would be much appreciated.

Having done some additional reading, I think I can strike out the third question: since reversible cellular automata that are computationally universal exist (according to wiki), there doesn't seem to be any connection between computational universality and GoEs. Now, what about universal constructors? Are there reversible universal constructors? Von Neumann's original rule happens not to be reversible, and in fact, has GoEs, but again, this need not say much.
The wikipedia page above mentions a way to emulate d dimensional irreversible CAs within d + 1 dimensional reversible ones, which readily establishes the computational universality of the latter, but I'm not sure if this holds as well for universal construction: the emulated constructor would only construct patterns on a d-dimensional sub-grid of the automaton (?).


texts: How to compare computational complexity of algorithms

texts: I have three different algorithms for achieving a target. Algorithm 1 takes $O(Mn)$ - $M$ is constsnt and n is variable,Algorithm 2 takes $O(min(p^3,n^3))$ - both $p$ and $n$ is variable and Algorithm 3 takes $O(nk+nd)$ - $k$ constant, $n$ and $d$ is variable. Is it possible to compare these algorithms? Which algorithm is fast and how much fast than other two algorithms?


texts:
Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset V, \ldots, L_n \subset V$ such that $L_0 \cup \ldots \cup L_n = V$ and the outgoing edges of the nodes in $L_i$ only connect to nodes in $L_{i + 1}$.
Is there an online algorithm that can maintain a set of shortest paths as more levels are added to this DAG? In other words, it can answer the query "what is the minimum weight path from the root to some node $n$ in the bottom level of the graph?", even as more levels are added.
I couldn't find any research addressing this question.


texts: shortest cost tiling of path to x distance

texts:
I have a distance to get to, and square tiles that have a cost and length. EX: a 1 unit block that costs 1 unit to purchase.

So if I was trying to get 10 units away. I would require 10 of the 1 unit blocks at that point for a total cost of 10.

So another example would be a distance of 10 units away except I have two tiles to pick from of [1,1], [5,4], [x,y], x = length, y = cost.

The cheapest cost would be 8, (2 of 5 blocks = 10 distance).

So, at first I thought this would be a shortest path problem, but seeing how I can re-use tiles that didn't work out the best.

I then tried to implement a rod-cutting algorithm, using the length of the rod as distance and the price for the length of cuts. This algorithm though kept trying to maximize the distance, which wasn't what I wanted.

My final method, was to divide the cost by length for each tile to find the most cost efficient tile (shown below). This worked for about 9% of my unit-tests, it was failing most because it couldn't see that it might be more cost effective to use a more expensive tile, etc.

I started with a greedy algorithm using cost / length for most efficient cost tiles, when I couldn't get that to work. I moved towards a dynamic programming algorithm using the cutting rod example.

This required a lot of hacky work, since I didn't really want the maximized value via cutting. I wanted the minimal cost value of that distance, though it also only had about a 2% success rate.

I then went into recursion, with help from another tip. Using a tiny little Tile class to help me pass variables around, this had lots of success with my self test values, but once again only had a 10% success rate.

So after trying DFS, Rod-Cutting, Recursion, and Dynamic Programming. I am lost. Did I overlook one of these algorithms?


texts: How to compare the efficiency of two encoding schemes or hypothesis languages?

texts:
My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have the right terminology and just need a starting point so I can help myself.)

I'm trying to interpret the vector inputs to a black-box controller (which I can model as finite-state machine). I can see them and they look like a series of symbols but it is too variable (stochastic) to easily define an "alphabet" based on repetition and it isn't clear how the symbols are grouped. In other words it isn't clear whether they use something like block coding where each symbol is the same number of vectors in a sequence, or convolutional coding where symbols can have different numbers of vectors.

The controller operates a linear actuator (it just goes up and down) and the inputs are large vectors from a CNN. It's essentially a pong playing robot. I make predictions by modeling the controller as binary decision tree that maps each putative symbol to an exact position of the actuator. This is very similar to a language induction problem for a finite-state machine. Recall that a finite automaton can be a representation of a regular language. Also recall that finite automaton can characterized in terms of its memory requirements and computational complexity, hence a regular language can too.

I know that the controller is optimal. There is no controller which has both less memory and less computational complexity. If I have two guesses at coding schemes and each are able to predict actuator position equally well then I want to pick the coding scheme which implies the least complexity and memory. So how does one go about evaluating the resource requirements of a coding scheme (raw inputs-> symbols) and grammar (rules about symbols) in combination?
I need to keep in mind that I might be wrong that it digitizes its inputs into symbols at all. So what are the signs that it is not digital? (such as, if I divide the symbols into smaller symbols and it still works just as well, ad infinitum, that probably means the symbols are meaningless).

If you don't think I've given enough information keep in mind that I don't expect a detailed answer (but I'm happy to offer more). An acceptable answer is something of the form "I think you need to look into ____.", "This sounds like ____ in which case we often use ____.", "This sounds like a paper I read, see ____.", or "The ____ metric compares the level of the difficulty of a task to the number of symbols in the language required to perform that task and tells you how efficient a language is at that task."


texts: Turing machine that applies homomorphism on input string

texts:
I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Change the original input with a 1  into 11 and 0 into 10. You must also append a 01 to the start of the input once it is finished.  for instance, if the input  was 10110, then the output would be 011110111110.


texts: Flow graph that requires pushing back flow in Ford Fulkerson

texts:
Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?

Let's assume we use the standard procedure of repeating this step:

Find an augmenting path $p$ in residual graph $G_R$ of $G$.
Let $c$ be the minimum capacity edge in $p$.
Increase the flow on every edge in $p$ by $c$.
Update $G_R$.

The key here is step 1, where select augmenting paths. For many graphs, if we had an oracle to tell us which augmenting paths to use, we would never need to push flow back. I'm am curious if there is a case for which, regardless of augmenting paths and their orders, we will always be required to "push flow back". To clarify what I mean:

  To push flow back in $G$, means to increase the flow on an edge $(u,v)$ in $G_R$ such that edge $(v,u)$ exists in $G$.

If this is not possible, I would also be interested in a proof that such ordering of augmenting paths always exists? If it is possible, does it generalize to any number of nodes $n$? This question is alluded at in the ending sentences of this answer, but provides no proof.

My initial thoughts were that this would be a trivial proof. However, there are many times when the optimal flow along an augmenting path may not be equivalent to its minimum capacity edge. Since (by step 3) we require paths to be filled to their minimum capacity, we cannot easily meet this. My next thought would be that there should exist at least one augmenting path such that its max flow is equivalent to its minimum capacity edge. This is obvious by the Max flow min cut Theorem, but I am not sure how this would apply to the proof. With this, we may be able to get an inductive proof that it is always possible, but I am really unsure of this strategy as well. Any help would be appreciated.


texts: Matrix of a graph and computational complexity

texts:
Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ otherwise.
Now, suppose we define a special kind of matrix product for matrices whose entries are only 0 or 1. In this special matrix product we replace addition by OR and multiplication by AND. With this being our definition of the matrix product answer the following questions:

If $B_2 = (A+I)^2$ then argue that $B_2 = C_2 +I$ where $C_2$ is the adjacency matrix of the graph $G′ = (V,E′)$ with the same vertex set as $G$. We say that $(i,j) ∈ E′$ if $(i,j) ∈ E$ or there exists a $k ∈ V$ such that $(i,k),(k,j) ∈ E$.
Is it possible to compute $C_2$ (by some other way perhaps) in time which is $o(n^2)$? Or is there some example on which the time taken to compute $C_2$ has to be $Ω(n^2)$? Cause I think that in this case the time taken would be $θ(n^2)$

I tried manipulating $B_2$ and then applying the new matrix product properties, but I wasn't able to give a concrete argument about $C_2$. As far as the complexity goes, I have no idea on how to go about with it. Any help is appreciated. Thanks!


texts:
I'm a self-taught programmer and have been coding for 8 years. Due to this experience, I'm already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.).

However, I never learned "computer science," only programming. What are some good resources for someone in my position to self-study computer science - that is, resources which move at a quick pace and assume basic programming knowledge?


texts: Computing the effective resistance between two vertices in a large graph

texts:
Let $G$ be an undirected graph, seen as a network of 1 Ohm resistors.

As explained by this article (or stated on Wikipedia), the effective resistance between any two vertices can be obtained by taking the pseudo-inverse of the Laplacian matrix $L$ of $G$.

Are there any efficient ways to compute this? Say I am only interested about the effective resistance between a given pair of vertices, in a large graph. I would be interested in the computational complexity of computing that resistance, or any approximation strategy, any preprocessing (lighter than computing the whole matrix) that would make these queries more efficient.

In other words, I am looking for literature about the problem with a computational perspective.


texts:
I have written an algorithm for clustering data-points with their nearest neighbours with a Euclidean distance metric. I estimate its complexity to be $\mathcal{O}(n \times k)$ for $n$ data-points with $k$ genuine clusters. The dimension $d$ of the data results in $\mathcal{O}(e^d)$ complexity, though I believe this can be mitigated.

The algorithm is Monte-Carlo, resulting in an approximate solution. In pseudo-code, for data transformed to a unit hypercube:

radius = 0.15 # This should be fine-tuned for problem.
mode_number = 0 # Label for mode currently being investigated.

while length(data) > 0:

    mode_number += 1
    branching = True
    point = data[0] # i.e. first data point.

    while branching:
        within_radius = [] # Make this list empty.
        for item in data:
            if Euclidean_Distance(item,point) < radius:
                within_radius += point # List of points within a sphere.

        if length(within_radius) == 0:
            branching = False
            continue

        point = Pick_Random_From(within_radius) # Next point.
        data = data.Remove_From_Data(within_radius) # Remove neighbouring points from data.
        mode[mode_number] += within_radius # Add points to mode.

Although the for item in data loop contributes a complexity $\times$ length(data) each pass, length(data) shrinks rapidly, resulting in only $\times n$ complexity. In fact, the length(data) shrinks linearly with iteration (with a saw-tooth behaviour), e.g.

where branch is incremented every time while branching is passed, and number of deleted is the number of points removed at that pass of while branching. That result is from 3 Gaussians with 1000 points sampled from each Gaussian. My code identified six modes:

Modes: 6
Mode 5 , points: 1000
Mode 3 , points: 932
Mode 0 , points: 829
Mode 1 , points: 168
Mode 4 , points: 68
Mode 2 , points: 2

though only three substantial, which wasn't too far off.

The algorithm starts at a point, finds its nearby neighbours, and deletes them from the data list, and repeats from a point within those nearest neighbours. If a point has no nearby neighbours, it begins a new mode. If the data-points are spread in many modes, the algorithm requires more iterations to clear all the modes, resulting in $\times k$ complexity.

The dimension of the data limits performance. In higher dimensions of space, points are more "spread-out", e.g. a sphere radius $r$ takes up an $(r/R)^d$ fraction of the space, which shrinks exponentially with increasing $d$. This, I think, could be mitigated somewhat by increasing radius = 0.15 in my algorithm. This is justifiable - with larger $d$, more of the space in a unit hypercube is "around the edges".

So overall I estimate complexity: $\mathcal{O}(n\times k\times e^d)$. Is my analysis reasonable? Is the working of the algorithm clear?


texts:
I read about TRIE data-structure and is slightly confused about detecting end-of-word. Why do we create another node to detect end-of-word? why cant same node be used it. For example, we have to construct a TRIE for word CAT. Now, as per specification, there will be 4 nodes; in which last node will contain a field

  "isEndOfWord"

which will return true in this case. I am unable to understand why we couldn't use the third node "T" and return true from there.


texts: How to verify number with Bob without Eve knowing?

texts:
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Note: This question is on a list of "google interview questions". As a result, there are tons of versions of this question on the web, and many of them don't have clear, or even correct answers.

Note 2: The snarky answer to this question is that Bob should write "call me". Yes, that's very clever, 'outside the box' and everything, but doesn't use any techniques that field of CS where we call our hero "Bob" and his eavesdropping adversary "Eve".

Update:
Bonus points for an algorithm that you and Bob could both reasonably complete by hand.

Update 2:
Note that Bob doesn't have to send you any arbitrary message, but only confirm that he has your correct phone number without Eve being able to decode it, which may or may not lead to simpler solutions.


texts: Costs of updating arrays to contain only zeroes

texts:
To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also?

And in that case, setting an $n$-array to zero inside a loop with $n$ iterations should be $O(n^2)$, right? I am asking because I have written some code that does this, but the runtime only increases linearly when I increase $n$, not quadratically as I would have expected, so I don't quite understand. Is it perhaps to do with the compiler?


texts:
Given a N * N maze, and string of N,E,W,S denoting positions to move to. I need to determine how many moves are possible in sequence out of a string (containing these 4 letters only) from each cell as starting point.

The maze cells are denoted by 0,1 ,where 0 denotes an obstacle and 1 denotes free path to move on.

For eg- If string is NNN , and maze is

0101
1001
0000
1111

now for all cell in first row we cant go N(i..e up) so the answer is 0 for (0,0),(0,1),(0,2),(0,3).
For(1,0) it is blocked so the answer is 0 again.
For(1,1),(1,2),(2,0),(2,3) I can go only 1 N of NNN so the answer is 1 for them.
For (2,1)I can traverse 2 characters of string so the answer is 2.
For(2,2)I can traverse 3 characters so the answer is 3.
For last row, it is blocked so the answer is 0 since we can't move.

I used recursion to check for valid moves and calculated for each step.

int fun(maze[][], i) // here x and y denotes position which are intialized when code runs for each cell in maze
{

    if(x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == '1') // valid conditions
    {
        while(i<l)
        {
            if(s[i]=='N')
                x--;
            // and so on defining the moves depending on current string character

            if(fun(maze,i++)==1) // moving 1 step forward in string
            {
               possible++ //increment counter
            }

            return 1;
        }
    }
    else
    return 0;

}

Is there a way to do this more optimally ? How can I reduce its time complexity ?


texts: Are there any steps or rules to draw a DFA?

texts:
In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two switches, is this question.

I understand what an Alphabet as well as the Language of a DFA is, but are there any rules or steps to followed to reach a correct automaton for a given Language? Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

Note:- Please keep your language as simple as you can, since this is my first lecture and I am not yet aware of concepts like regular expressions or any other thing in the subject for that matter.


texts: I argue that right quotient of  $a^*b^*/b^*$ is $a^*$,is that true?any help or argument  to accept or reject my argument will be appreciated:)


texts: Boolean Algebra Simplifying complex equation

texts:
I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not.

F(A,B,C,D) = A'B'C' +ACD + A’BCD + A’BC’ + ABC + AB’CD'

After regrouping I got:
A'(B'C' + BCD + BC') + A(CD + BC + B'CD')

I thought right after this you'd get 1 because A + A' is 1 and then after that you would get each term in parentheses leftover as the final expression. Is that right?


texts: What is the simplest example of a prob whose complement does not have the same complexity?

texts:
Firstly it is my understanding that the complement of a problem is simply the "reverse" question. So the complement of "Is the sky blue?" would be "Is the sky not blue?". Is my understanding correct?

If so, how can a complement ever be more or less complex than the original problem? Please include the simplest example that you can think of.


texts: Where in the toolchain does formal specification come in?

texts:
Where is the formal spec located?
Like this?

Are tests made from formal or informal spec?
I saw a project where they where generated from a the formal
spec and that never made sense to me.

Is the verification step manual or can it be automated?

If it is manual, we now have 3 things to maintain and keep in sync.
The problem of a possible mismatch between informal spec and code has just been moved
between the informal and the formal spec. What did we gain?

If the verification step can be automated completely then
why write any code at all? Just let it be generated from the spec automatically.
If we fold those two steps into one the situation is the same as
before; we have a high level description of our problem which a compiler
turns into a low level representation that can be executed by a machine.
What did we gain?


texts:
I have theorised a indexing algorithm (like a B-tree).

However, there's a mental block stopping me actually implementing it.

The algorithm comes in to forms:

form 1:

A look up time of O(1) to O(log2(n))

Each value in the index will have metadata associated to it that is of the size log2(n)*memory address size

form 2:

A look up time of O(1) to O(log2(n)/2)

Each value in the index will have metadata associated to it that is of the size log2(n)*2*memory address size

Unlike B-tree/other index algorithms, there's no time penalty for a add/deletion.

You can for example do a add, then do a search straight after (with no waiting in between).

You get a faster search at the expense of more metadata (memory) along with being able to insert/delete in real time.

You can also do sequential access/search sequential data values fast.

I can't find any other algorithm that has that attributes and time complexity.

If I can get it to work, I plan to sell it.

My question is; would this actually worth anything to anyone/or useful in any particular application?

Or is the amount of memory it uses too much of a deal breaker?


texts:
I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:

x :: Int
x = id 1

y :: Char
y = id 'a'

id :: a -> a
id x = x

If the type-checker traverses the program from top to bottom, then from x we can infer that the type of id must generalize Int -> Int, and from y we can infer that id must generalize Char -> Char, but I'm unclear how we can use these constraints without inferring a too-specific type for id.

If we check id first, then we can just instantiate its type in x and y, and use unification. However, if we have recursive or mutually recursive bindings, ensuring that all mentioned top-level bindings are typechecked before the binding itself would lead the type-checker into an infinite loop.

How are these issues resolved?


texts: Longest increasing subsequence (Dynamic Programming)

texts:
I have written the following recursive structure for finding length of longest increasing subsequence.

int lis(int arr[],int n,int k,int prev)  //k=0 (pointing to start)
{                                   //prev=0 (value of prev element included in subsequence)
    if(k==n)    return 0;
    int res;
    if(arr[k]>=prev)   res=max(1+lis(arr,n,k+1,arr[k]),lis(arr,n,k+1,prev));
    else               res=lis(arr,n,k+1,prev);
    return res;
}

1.So, firstly I check whether that element is greater than prev element or not. If it is greater then there are two recursive calls-

a) In first call that element is included and I send that element as prev in the next call and

b) in second call that element is not included in the subsequence.

2.If it is less than prev element than I simply don't include that element and proceed further.

I am trying to write the top-down approach (DP) for this. It cannot be written using 1-d array because it depends on value of k and previous values in the subsequence. How can I write the top to down approach for this?

I read an article on lis on GeeksForGeeks and found a different recursive structure for this problem.

But, I want to know that Can every recursive solution be written into top-down approach (DP) or do I have to find recursive solution (there can be more than one recursive solutions for a problem I think..) such that it follows optimal substructure property?


texts: convex hull for unsorted vertices solved by graham scan algorithm

texts:
can graham scan algorithm work with convex hull vertices when vertices are not sorted?

I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull.


texts: Why is the video game Braid Turing-complete?

texts:
It's written in wikipedia https://en.wikipedia.org/wiki/Turing_completeness#Games that the video game Braid is Turing-complete.

I've played Braid before but I can hardly reconcile it with Turing completeness. In what sense is it Turing-complete?


texts: smn-theorem: Application by instantiating s with other function

texts:
The smn-Theorem on the basis of Turing Machines and computable functions rather than programs, as in the Wikipedia article for instance, can be defined as follows:

$$
\begin{align*}
&&& s \langle m, n \rangle &&= \lceil M' \rceil \\
&&\implies &\varphi_{s\langle m, n \rangle} &&= \varphi_{\lceil M' \rceil}\\
&&&&&= f_{M'}\\
&&\implies &\varphi_{s\langle m, n \rangle} (i) &&= f_{M'}(i)\\
&&&&& = f_{M_m} \circ f_{M_{\langle n, . \rangle} (i)}\\
&&&&&=\varphi_m \langle n, i\rangle
\end{align*}$$

where $M_{\langle n, . \rangle}$ denotes, that machine $M_{\langle \rangle}$ has $n$ already pre-written on its tape and $\lceil M \rceil$ denotes the Gödel-number of machine $M$.

Now, I am confronted with the claim, that

$$ \varphi_{h(n)}(i) = f\langle n, i \rangle $$

because

$$ f := \varphi_m \in \text{set of computable functions}$$
then
$$f\langle n, i \rangle = \varphi_m \langle n, i \rangle = \varphi_{s \langle m, n \rangle}(i)$$

therefore it has to be that

$$ h(n) = s\langle m, n \rangle $$

so I guess then it has to be like this:
$$h(n) = \lceil M' \rceil = \lceil f_{M_m} \circ f_{M_{\langle n, . \rangle }} \rceil = s\langle m, n \rangle$$

And so $h$ contains $f_{M_m}$ ... basically just because there can be such a function? Am I interpreting this right?


texts: A variant of travel salesman problem in grid graph

texts: In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. The problem is to determine the starting position and the directions of robot so it can cover the whole grid (also in some situations there can be no solution). An example of this game is shown below, where the starting position is chosen to be near the lower right corner, in this example, robot fail to cover the whole places. The movement constraint of robot is similar to ricochet robot but this robot can only visit a place once. I want to know if this problem has been studied before and if there is efficient algorithm to solve it. Currently I just use depth first search to attack this problem, which is quite slow on a large grid. I think this problem can be transformed into a boolean satisfiability problem. I found that this problem is called full house and is published by Erich Friedman.


texts: What does Sigma notation mean, in the context of computability of functions?

texts:
I was reading a paper on the computability of AIXI [1] and came across the notion of $\Sigma^0_n$-computability for real-valued functions in section 2.3.

I'd like to read about this in more detail.
Unfortunately I couldn't find this definition anywhere else in the literature. I already checked the references given at the end of the paper.

Could somebody point me to some book/article I can take a look at?

On the Computability of AIXI by J. Leike and M. Hutter (2015)


texts: Rooted Binary Tree - Chain Nodes Algorithm

texts:
The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that child is not a leaf.
I am stuck any help would be appreciated, so far I have done this:

Algorithm Chainnode(x) {
    if (not Leaf(x)) and (left[x] XOR right[x] == Null) {
        return True
    }
    else {
        return False
    }
}

Algorithm ChainnodeCount(x) {
    i = 0
    if (x == Null or Leaf[x]) then {
        return i
    }
    else if ChainNode(left[x]) == True {
        i = ChainNodeCount(left[x]) + 1
    }
    else if ChainNode(right[x]) == True {
        i = ChainNodeCount(right[x]) + 1
    }
    else {
        i = ChainNodeCount(left[x]) + ChainNodeCount(right[x])
    }
}


texts:
I am not a computer scientist or even a student of CS. I just want to find more information and would like if someone could put if in right direction about how actually computer works. I understand that when we write program in C++, it's been compiled to assembly language and then into machine code. How can all this functions be understood by a machine?
And how can all this functions be executed if assembler can only work with such simple commands like MOV(move some data to CPU register), SUB, ADD and others. How does actually "print" command work? Is there a course, a book or a series of artices for teaching me all that stuff? Thanks in advance


texts: Search vs planning in artificial intelligence

texts:
I'm studying artificial intelligence following the Russell & Norvig book.
We did a search and planning part that for me is the same (at least on the representation).
I'd like to know what is the difference between these two techniques, but I couldn't find it.

Looking online I found this resource:
Planning and Search, where it says: "The main difference between search and planning is the representation of
states."

Is the difference between these two techniques limited to the representation?


texts: Example Turing Machine for a time-constructible function

texts:
I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a simple function $f(n)=n$ using the definitions in the book.

The authors start by introducing $k$-tape turing machines: $1$ read-only input tape and $k-1$ read/write work tapes with the last one being the output tape. The tapes are one-directional and they are initialized in the leftmost cell via a special start symbol $\triangleright$. The input tape also contains the input $x$ after the $\triangleright$ symbol, in binary notation. All remaining cells contain the blank symbol $\square$. The tape-heads start on the $\triangleright$ symbol.

  A TM $M$ computes a function $f$ in $T(n)$-time if for every $x$, after $M$ is initialized in start configuration on input $x$, using at most $T(|x|)$ steps, $M$ halts with $f(x)$ written on its output tape.

They then define time-constructible functions

  A function $T \colon \Bbb N \to \Bbb N$ is time-constructible if $T(n) \geq n$ and there is a TM $M$ that computes the function $x \mapsto \llcorner T(|x|)\lrcorner$ ($\llcorner T(|x|)\lrcorner$ denotes the binary representation of $T(|x|)$) in time $T(n)$.

I have a problem constructing TMs $M$ for the functions $F(n)=n$ and $G(n)=n^2$. Let's say $x = 3$, so $|x|=2$. The machine for $F$ will have to halt after $F(|x|)=|x|=2$ steps and output $\llcorner x \lrcorner$. How is this possible if the machine heads start on the $\triangleright$ symbols?

In $2$ steps, the machine can't even read the input, since the first step is wasted by moving right from the $\triangleright$ symbol.

Shouldn't the definition make use of asymptotic notation?


texts: Iterate over each cell of a grid through whose interior a given line segment passes

texts:
Let $a,b>0$ and suppose we have divided the domain $\Lambda:=[0,a]\times[0,b]$ into a grid of width $n_x$ and height $h_y$.

We enumerate the grid from bottom to top and left to right. Given $(x_0,y_0),(x,y)\in\Lambda$, I want to iterate over each grid cell through whose interior the line segment connecting $(x_0,y_0)$ and $(x,y)$ passes.

Suppose we number the first cell by $(0, 0)$ and the last cell by $(n_x-1,n_y-1)$. How can we find an efficient algorithm, which iterates over the desired cells?


texts:
I've got two questions about bitonic sorting:

Does a bitonic sorter compare a pair of elements more than once?
How many comparisons does a bitonic sorter perform in the case where the size of the array not a power of two.


texts: What does "If P1 is reduced to P2, then P2 is at least as hard as P1" mean?

texts:
I am having trouble understanding the following statement regarding Turing reduction:

"If P1 is reduced to P2, then P2 is at least as hard as P1."

Does this mean that
(i) P2 can be harder or as hard as P1, or
(ii) P2 can be easier or as hard as P1?
To represent this visually...

I would appreciate any insight on the matter. Thank you.


texts: What are the elements of the modular ring mod 7?

texts:
Are the elements of a modular ring simply the set of all the numbers from 1 to p−1?

in this case p−1 = 6 ?

I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was told that 0 is included in the the ring. Is this treated differently in CS ?


texts:
Is machine epsilon the largest relative error in representing a number as a floating point number?
There are so many definitions of machine epsilon. I'm starting to get confused.
Isn't the machine epsilon the smallest?


texts:
I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin  NP. But I can't seem to wrap my head around this.

Why is this so?


texts:
I'm doing a practice question (not graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly.

Suppose $f(n) = O(g(N))$ and $g(n) = O(h(n))$ (all functions are positive).

Prove that $f(n) = O(h(n))$.

I am having lots of trouble with this, and it would be greatly helpful if someone showed me how to do this.


texts:
Where can I find a list of algorithms organized by complexity.
I'm curious of what O(n), O(NlogN) algorithms are there.
These are the most useful for large datasets.
I'm aware of this but it isn't organized by complexity:
https://xlinux.nist.gov/dads/
Thanks


texts:
I have a doubly link-list like this

typedef struct Record
{
   int i;
   Record* next;
   Record* prev;
}Record;

I have over 5 trillions of records that I need to handle, now that I need to retrieve all of them and sort them out.
If its size was small, I could borrow stl's vector or list to do the job but now that it is too huge, I have no idea how to save the object data before sorting is performed

my function prototype

void sortRec(Record**recToSort,bool bASC){}


texts:
I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:

(i) For all x ∈ A, |x| ≤ 5.

(ii) Every DFA that decides A has more than 8 states.

To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}* that holds both of these properties?


texts:
I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation.

Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am supposed to prove, or disprove, the following statement: $f(n) \in \mathcal{o}(g(n))$.

I am fairly sure that it's true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $\mathcal{O}$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $\mathcal{o}(g(n)) = \{f(n)|\forall C > 0 \exists n_{0} \forall n\geq n_{0}:f(n) < C * g(n)\}$. This means other than with big $\mathcal{O}$, where it suffices to show that there's at least one pair $C$ and a $n_{0}$ so that $f(n) \leq C * g(n)$  $\forall n \geq n_{0}$, I now have to prove that for every $C > 0$, there is such a $n_{0}$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $\mathcal{O}$, because you can prove with induction that $2^{n} < n!, \forall n\geq 4$. Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance!
(It would already help to know how to start. Probably like, let $C$ be greater 0, and then I have to show that for any Value of this $C$, there is... because...
My biggest struggle is to find meaningful estimations to get a chain of inequalities.)


texts: EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

texts:
So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we can also reduce $A_{TM}$ to $EQ_{TM}$ itself, that means: $EQ_{TM}$ and ${NEQ_{TM}}$ are not disjoint since we can reduce $A_{TM}$ to the two of them? And also, $EQ_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A_{TM}$ to it?
I have an intuition that these two questions have 'YES' as an answer and they are not problematic: it is OK to answer them with YES. But I have an unclear image about the fact of being a complement but having some shared elements with its complement, maybe the elements that are shared are just the strings but not the problems themselves?
Any clarifications would be welcome


texts:
Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)
Partition: Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

For $B=0$, you can always partition $L'$ into $\{2S-0\}$, $\{S+0\} U L$.
It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.


texts: Why a separate ALU is needed, since any integer can be represented as floating point numbers?

texts: Most of the operations in computers are using floating-point arithmetic, and why a Floating Point Unit alone is not sufficient? Can we do away with ALU? Is FP operations are resource-intensive alone be the reason for this, over the advantages provided by FP operations?


texts:
I have, lets say, 8 bits mantissa and 4 bit exponent. Then,

-1=1111 1111
there are no 0s so how can I normalise -1 in 2's complement form?


texts: Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$

texts: I have been trying to find a context sensitive grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ for some time but I cannot get it done. Any ideas ?


texts: Do image artefacts reveal the original image orientation?

texts:
An image is taken and then rotated by an arbitrary angle and cropped.  Let us assume that the original image is rather meaningless and is not aligned in any way.  Given the rotated image, is it possible to learn anything about the original orientation?  For example, using:
1. lossy compression artefacts (e.g. some averaging now happening in not axis-aligned rectangles),
2. any artefacts created by the camera sensors (probably camera-dependent).


texts: In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition?

texts:
I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$.

What is the purpose of the middle two states and the $\varepsilon$ transition between them? Could this NFA be designed without them and still work as intended?

Here's another example of an NFA that recognizes the language described by $aba$. Again, I'm confused by the addition of the empty string transitions and the extra states.


texts: Hamming numbers for $O(N)$ speed and $O(1)$ memory

texts:
Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory.

Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers.

Is there a possibility to generate Nth Hamming number with $O(N)$ time and $O(1)$ (constant) memory? Under generate I mean exactly the generator, i.e. you can only output the result and not read the previously generated numbers (in that case memory will be not constant). But you can save some constant number of them.

I see only best algorithm with constant memory is not better than $O(N log N)$, for example, based on priority queue.

But is there mathematical proof that it is impossible to construct an algorithm in $O(N)$ time and $O(1)$ memory?


texts: How to select a binary tree node uniformly at random

texts:
The exercise I'm trying to solve is

  You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method getRandomNode() which returns a random node from the tree. All nodes should be equally likely to be chosen. Design and implement an algorithm for getRandomNode(), and explain how you would implement the rest of the methods.

The answer from the book is:

 1  class TreeNode {
 2    private int data;
 3    public TreeNode left;
 4    public TreeNode right;
 5    private int size = 0;
 ...
12    public TreeNode getRandomNode() {
13      int leftSize = left == null ? 0 : left.size();
14      Random random = new Random();
15      int index = random.nextInt(size);
16      if (index < leftSize) {
17        return left.getRandomNode();
18      } else if (index == leftSize) {
19        return this;
20      } else {
21        return right.getRandomNode();
22      }
23    }
...
55  }

But here is the problem. With this algorithm, I don't see how nodes are equally likely to be chosen. In line 16, it says if leftsize > index, where index is a number from 0 to size, then the algorithm will continue with the left node, otherwise the right node. It only works when the tree has a depth of 2. When the tree is taller, the probability of each node being chosen will not be equal.

Am I wrong? Does this algorithm work?


texts:
I check for the symmetric directed graph and it's impossible to be bipartite , because we can't divide the vertices into two sets since all will have in - and out arrow
but in general it could be right ?
 if I draw a graph with one direction


texts: What is the most efficient way to turn a list of directory path strings into a tree?

texts:
I'm trying to find out the most efficient way of turning a list of path strings into a hierarchical list of hash maps tree using these rules:

Node labels are delimited/split by '/'
Hash maps have the structure:

{
    label: "Node 0",
    children: []
}

Node labels are also keys, so for example all nodes with the same label at the root level will be merged

So the following code:
[
    "Node 0/Node 0-0",
    "Node 0/Node 0-1",
    "Node 1/Node 1-0/Node 1-0-0"
]

Would turn into:
[
    {
        label: "Node 0",
        children: [
            {
                label: "Node 0-0",
                children: []
            },
            {
                label: "Node 0-1",
                children: []
            },
        ]
    },
    {
        label: "Node 1",
        children: [
            {
                label: "Node 1-0",
                children: [
                    {
                        label: "Node 1-0-0",
                        children: []
                    },
                ]
            },
        ]
    },
]


texts:
Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$.  This is not expressible in a MILP directly.  Is there a way to express this using linear inequalities, by adding some new variables (possibly variables restricted to integers)?

To put it another way: I want to express the constraint $(z=0 \land y=0) \lor (z=x \land y=1)$, in a situation where I already know $y$ is constrained to be either 0 or 1.


texts: LTL Model of (infinitely often p) ∧ ( infinitely often q) ∧ (¬ Eventually (p ∧ q))?

texts: Can anyone give a model (pi) of the ltl formula above?


texts: Is Pattern Matching as expressive as Case Expression in Haskell?

texts:
Nomenclature

The term expressive in the question shall bear the same meaning as in the following sentence:

  A Turing Machine is as expressive as Lambda Calculus.

Introduction

While learning Haskell, I had noticed that there are 2 ways to achieve the same effect, namely Pattern Matching and Case Expression. For example,

-- Pattern Matching
not True  = False
not False = True

-- Case Expression
not x = case x of True  -> False
                  False -> True

I am also fully aware that Pattern Matching is actually a form of syntax sugar that will be compiled into Case Expression.

Therefore, we can be very sure that every Pattern Matching expression can be converted to Case Expression.

Question

So, this is my question: Is the following statement true?

  Every Case Expression can be re-written using Pattern Matching.

Regardless of the truthiness of the statement above, I would be glad if you could provide a formal proof to support your answer.

P/S

The motivation that drove me to seek answer for this question is because I'm currently designing my own language, which I wish to have as less feature as possible, but not too minimal like Lambda Calculus which only have 3 features.