texts: PDA and CFG of language of regular expressions

texts:
I am stuck on a problem involving PDA's and CFG's. The problem is as stated:

  Give a CFG and a PDA for the language of regular expressions over the
  alphabet $\{a, b, c\}$. Give the formal tuple definition of each. You may use the
  shorthand for pushing a string in the state diagram of your PDA, but not in the
  tuple form. It will help if you expand out the shorthand in the state diagram.
  To avoid ambiguity, use the symbols $($, $)$, $λ$ for the language.  The alphabet should
  be $\{a, b, c,(,), +, λ,∗ \}$. For brevity, you can define $δ$ by giving its output on
  the inputs that don’t return $∅$. Something like $δ(x_1) = y_1; δ(x_2) = y_2;$

My first attempt at it got me stuck after defining the Context Free Grammar and the PDA. I am having trouble understanding how this grammar could, for instance,

Derive $(a + b)^*(c + λ)a^*$
Make a PDA for this.

How can I make a PDA for this? How can I make a CFG for this?


texts: Does a shift operation distribute over XOR

texts:
In this question, we abuse the mathematical notation to express bitwise operations in the following way:

$\ll$ is a binary left shift
$\oplus$ is a bitwise XOR
$0b1, 0b110, 0b10 \ldots$ are used to denote raw bits
$repr$ is a function associating to a number a given bit representation
$\mathbb{B}$ is the set of natural numbers to which $repr$ associates a two's complement bit representation
$\mathbb{G}$ is the set of natural numbers to which $repr$ associates a Gray code bit representation

I was trying to prove that the binary representation of a power of $2$ in binary reflected Gray code was always two ones followed by zero or more zeroes, except for $2^0$. The demonstration is roughly as follows:

  We know that the two's representation of powers of $2$ can be expressed as follows:

  $$ \forall n \in \mathbb{N} : repr(2_\mathbb{B}^n) = 0b1 \ll n $$

  And the function $to\_gray$ can be expressed as follows:

  $$ \forall n \in \mathbb{B} : to\_gray(n) = n \oplus (n \gg 1) $$

  Therefore, we have the following equivalence (ignoring the special case when $n = 0$):

  $$\begin{align*}
\forall n \in \mathbb{N} : repr(to\_gray(2_\mathbb{B}^n)) &= (0b1 \ll n) \oplus ((0b1 \ll n) \gg 1)\\
&= (0b1 \ll n) \oplus (0b1 \ll (n - 1))\\
&= (0b10 \ll (n - 1)) \oplus (0b1 \ll (n - 1))\\
&= 0b11 \ll (n - 1)
\end{align*}$$

However, the last line of the demonstration assumes that $\ll$ distributes over $\oplus$. Is this assumption true or does it only work for my specific use case?


texts: MTBF calculation with 2 units connected in series

texts:
Me and a friend have a opinion difference regarding a question that got asked in a previous IT test.

The short version:

2 units, n and m are connected in series but operate as one system. n has a MTBF of 200, m of 300. What is the MTBF of the entire system?

possible solutions:

200
250
300
500

I am convinced (as is the guy who made the question) that the correct answer is 250.

My friend is convinced it is 120 and the question contains a mistake.

How were I to calculate this?


texts: How does pre-training help with semantic segmentation with U-net

texts:
I am working with a u-net, a variation of the more commonly known fully convolutional network for semantic segmentation. For training a u-net, I was given the suggestion that I should use a pre-trained network. But, I'm not quite sure how this makes sense.

My understanding is, in pre-training, we freeze the network up to the final classifying layers from a pre-trained network and then, we initialize random weights for the classifying layers. Then, we take our new dataset and retrain the weights through the whole network. Basically, we don't have random initialized weights for the convolutional blocks.

Now, if I'm using something like the u-net which has a very unique structure, how exactly would I do this pre-training with something like vgg16? The only thing I can think of is to share the feature maps during the upsampling layers but that's about it and that's not really pre-trained weights.


texts: Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?

texts:
I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 \leq i < n}{\left| f(i) - p(i) \right|}$.

Now, I know that for $L_2$, this can be solved using a system of linear equations (for getting a zero vector as the derivative of the error) - that is the "Least Squares" method. But - the $L_\infty$ error is not a derivable function. I also know that for a continuous interval rather than a finite grid, there's an iterative approximation algorithm - the Remez Algorithm (although I'm not entirely clear about the specifics - I just noticed it.) And I also had a vague hunch which I didn't manage to act on that Chebychev polynomials, each of which being the optimal solution to the problem with $f = 0$ and a fixed leading coefficient 1, might be relevant here somehow.

Anyway, what I'd like to know is:

Is this problem is essentially combinatorial or essentially numero-analytic?
Can it be solved in PTIME (assuming operations on real values are O(1))?
If so, what's the numerical stability features of such a solution (since my n is large-ish)?
If not, does it admit an efficient (PTIME) approximation scheme?
If not, how do people deal with it in practice?


texts: Maximizing the product of a set of dot products

texts:
So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following:

$\prod_{x \in X} b \cdot x$

where the components of $b$ sum to $1$

If it matters the components of each $x$ sum to $1$ as well.

What algorithm would you use to do this?

Sorry if this belongs on the mathematics exchange, I was stuck between the two


texts:
What does $L_1 \in CS - CF$ means?

I think the meaning is $L_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars.

Am I understanding this correctly? Just to be sure.


texts: Turing reductions by NX ∩ coNX and binary relation problems

texts:
Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good definition of a Turing reduction to $A$, in the context of the decision problems NX$A$ solvable by an NX Turing reduction to $A$?

It would be nice if a Turing reduction would ignore any resources (like time, space, random bits, ...) used by algorithm $A$ itself, when it is part of a larger program.
It would be nice if a Turing reduction would only depend on the computed binary relation, not on the specific algorithm $A$ used to compute the relation.
It would be nice if the complement of the binary relation would lead to the same Turing reduction as the binary relation itself. So if $B$ is a non-deterministic algorithm computing the complement of the binary relation computed by $A$, then NX$A$=NX$B$.
Edit: Note however Ricky Demer's comment. The complement is problematic anyway, because arbitrarily long output strings would be required. So better restrict this to the case where the output strings have a fixed length (potentially dependent on the length of the input string), and only refer to the complement relative to this fixed length.
It would be nice if an NX Turing reduction to $A$ would at least enable us to do everything we could do if we had subroutines $A',B'\in\text{FNX}$, where FNX would be the binary relation problem class associated to the complexity class NX, $A'$ would compute the same binary relation as $A$, and $B'$ would compute the complement of the binary relation.

This last point raises the following question: If such $A'$ and $B'$ exist, will it lead to NX$A$=NX? Or to go back to decision problems (because those are better studied and understood), do we (normally) have NX$D$=NX for decision problems $D\in$ NX ∩ coNX?

It is common practice to reduce (binary relation and) function problems to decision problems by posing a separate decision question to an oracle for each bit of the function value. To enable this sort of reduction, arbitrary decision problems $D\in$ NX ∩ coNX could be composed with the binary relation to get decision problems. Then a Turing reduction must be able to answer those decision problems (for the resource cost of solving $D$ with the implicitly produced output string of $A$ as input). Is this a good definition of the Turing reduction NX$A$?
Edit: Note that the composition of the complement of $D$ with the complement of the binary relation is different from the complement of the composition. So this part of the question is not affected by the issues related to the complement of a binary relation, because it doesn't try to incorporate the corresponding desirable property.


texts: Differentiating between BubbleSort and InsertionSort

texts:
This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this.

The problem is this:
You have two unknown sorting algorithms, one is Bubble Sort, the other Insertion Sort.
Identify which is which given that you can only differentiate them via differences in asymptotic time for different data sets. (Meaning no run time cross comparison between the two sorts, as our professor may add constant time costs making Insertion Sort slower).

Edit: To clarify, we can specify any array of length n, with a particular sequence if you wish, to see the time it took to sort.
However, you may not compare times between the two sorts. E.g. This sort is faster, therefore this is Insertion Sort.

My findings:

            Insertion Sort | Bubble Sort
Best case:            O(n) | O(n)
Worst case:         O(n^2) | O(n^2)
Average case:       O(n^2) | O(n^2)
Stable:                Yes | Yes
In-place:              Yes | Yes
Nearly Sorted:        O(n) | O(n)
Reversed:           O(n^2) | O(n^2)
Few Unique: closer to O(n) | closer to O(n^2) // not sure

Given how similar the two sorts are, it's really hard to distinct them...


texts: 2OPT Approximation Algorithm for Multiway Cut Problem

texts:
In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum
set of edges in $E$ whose removal leaves all terminals in different components.

How do we show that this problem can be solved exactly in polynomial time when
$k= 2$?
How do we get an approximation algorithm with ratio at most 2 for the case when $k \geq 3$?


texts: If we spoke in TM-computable English, what would it look like?

texts:
We know that any "effectively computable" process is computable by a Turing machine (Turing-Church thesis).

Although it seems that "effectively computable" is still open to discussion, the intuitive interpretation is that any process that is "mechanical enough" can be computed by a Turing machine.

Turing's initial objective was to axiomatise how humans do reasoning. Now what do you need to reason? Non-ambiguous definitions (axioms) and non-ambiguous rules. Then you are good to go. So in effect if TM successfully modelise how humans think, that's all they should need and hence natural languages should be quite a close candidate to become regular languages as long as we impose that words have just one meaning.

My question is then, intuitively, is it enough for a language to be "non-ambiguous" to be computed by a Turing machine? Or is there more intuitive properties that the language need to respect?

(I am currently trying to figure out if the laws voted in a parliament, although written in mundane English, have enough of these characteristics to be computed by an automaton).


texts:
What are some applications where irreducible control flow is required*?
I'm particularly interested in programming language features that will be tricky to efficiently compile if the compile target does not permit irreducible control flow. For example, a programming language offering GOTO will generate irreducible control flow for some programs. What other language constructs are like this? For example, is irreducible control flow required to implement resumable exceptions?
I'm also interested in application-level uses of irreducible control flow.
(*: irreducible control flow graphs (CFGs) can be converted to reducible CFGs at some cost, and also some compiler optimizations can convert reducible CFGs to irreducible CFGs, so what I mean is that the original, unoptimized CFG produced by the source code is irreducible. Less formally, I mean that the "programmer's intent" naturally includes irreducible control flow)


texts: Bias or not when finding patterns using data mining techniques?

texts:
I am currently following a course on Data Mining and i am very curious about the deeper underlying method. As far as i have learned so far data mining is about finding unknown patterns that can be useful and provide new knowledge about your data.

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case. Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with. Say if i would like to test whether the survival percentage was smaller for a male passenger, i could do some statistical analysis, and find out whether or not that would be the case. I could programme a decision tree and see what my data tells me. That would tell me HOW to use machine learning to analyse the data in order to be able to predict what chance of survival a new passenger x with specific 'properties' would have. What would the data mining perspective come into this process?

I am aware of different types of classifiers and how we can use them to check for patterns in order to do predictions, but how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

Citing directly from the wiki page of data mining:
"Neither the data collection, data preparation, nor result interpretation and reporting is part of the data mining step, but do belong to the overall KDD process as additional steps." and "Data mining is the analysis step of the "knowledge discovery in databases" process, or KDD."

This indicates that the actual data mining part is the analysis using mathematics, statistics and machine learning tools. Well from here, how would i start finding patterns in a large data set. Would i start from what my prior tells my could be interesting and dig deeper to see whether there actually is an interesting pattern here - and if not, i can conclude that there isn't, which in itself is insightful - and then i can try finding other patterns.
OR do i make an algorithm that randomly tries to find correlations and patterns across different random combinations of attributes in my data, without me choosing ANY direction to look in?
Because one thing i have been taught is that when you work with REALLY large datasets, all sorts of patterns begin to emerge, and no matter where you look, you will find some sort of patterns. The art is to find USEFUL patterns, and patterns that actually provide some kind of insight into your data! As always correlation does not necessary imply causation, but that is for the analysis part, and i guess data mining is all about just finding the patterns - so how do we actually go about and do this.

I hope my question is possible to understand. I find it hard to formulate any better. If i were to boil it all down into one sentence, it would be: If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?


texts: Evaluation functions of Minimax algorithm

texts:
Let's say we have the following relationship between $f_1$ and $f_2$:

$$f_2(s) = \sqrt{1 + f_1(s)}$$

And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to the same action as using $f_1$ but is not guaranteed to return the same action as $f_1$ when used in expectimax search?

I understand that expectimax takes into account the weight of the arcs to compute the possible path. But I am still not able to understand how the aforementioned conclusion is being made.


texts:
What is the definition of the complexity class $D^P$?

In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too.

Is it the same as: "A language L is in the class $DP$ if and only if there are two languages $L_1\in NP$ and $L_2\in coNP$ such that $L = L_1\cap L_2$" (Def. 17.1 from Papadimitriou - Computational Complexity (1994))?

Note: In the stated definition it says $DP$ not $D^P$. But I was wondering if it is the same.


texts: Context-free grammar for ${a^n b^n a^n}$

texts: I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can not find a context-free one. Any ideas?


texts: Papadimitrou and standard landau notation

texts:
This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction.

From huge majority of sources the definition of $\mathcal{O}(n)$ is:

$f, g : N \to R^+$

$f \in \mathcal{O}(g) \Leftrightarrow \exists{c,n_0} \in N \> \forall n > n_0 : f(n) \leq c\cdot g(n)$

but in Papadimitriou's book there is a different definition I haven't seen anywhere before:

  The order of $f$, denoted $\mathcal{O}(f)$, is the set of all functions $g:N\rightarrow N$ with the property that there are positive natural numbers $c>0$ and $d>0$ such that, for all $n\in N$, $g(n) \leq c \cdot f(n)+d.$

I assume the first definition evaluates the functions as continuous functions whereas the second definition is concerned only about the points on $n \in N$. Therefore undefined values that asymptotically goes to $\pm\infty$ are not an issue anymore.

For example if we take $f(n)=\frac{1}{n}$ and $g(n)=1$.
We know that $f(n)\in g(n)$ because $\lim_{x\to\infty}\frac{\frac{1}{x}}{1}=0$. We find the value for $f(1)$ and raise the $g(n)$ above this point such as:
$f(n) \leq 6\cdot f(n)$ or $f(n) \leq f(n)+6$

Is my assumption correct? If it is how can I prove this equivalence?


texts: Formally proving properties of fold function

texts:
Recall the fold function for lists:

$fold(f,z,[x,xs]) = fold(f,f(z,x),xs)$

$fold(f,z,[]) = z$

I want to formally proof that if $f$ is associative, commutative and idempotent (meaning $f(x,y) = f(x,f(x,y))$ and we have to lists $l_1$ and $l_2$ such that their contents  are equal then $fold(f,z,l_1) = fold(f,z,l_2)$.

What I've tried

I've tried double induction on the sizes of the list but this doesn't clarify much the problem.
I've figured out a procedure that would leave me with a list of non-repeating elements. I take each element of the $f(f(f(\cdots)))$ list and take it to the outside thanks to associative and commutative property. En each step I make sure that if I find two equal elements I remove them using idempotence. The basic rules are as follows:

$f(f(z,x),y) \text{ push x out, push y in} = f(y,f(z,x)) = f((y,z),x) = f(f(z,y),x)$

$f(f(z,x),x) = f(z,x)$

The actual transformation to the list would look like this:

     def transform[A](l: List[A]) := l match {
        case Nil() => Nil()
        case x :: Nil() => x :: Nil()
        case x :: x :: xs => transform(x :: xs)
        case x :: y :: xs  => y :: transform(x :: xs)
     }

My first problem is how to write the predicate to say that this algorithm gives a list with non-repeating elements. I do it like this:

$\forall x,y. x \in l \land y \in l \land x = y \implies index(x) = index(y)$

But I don't how to proof that my algorithm guarantees that this property holds.

The idea is that if I can proof that this transformation does not leave repeating elements then it would be easy to show that the lists end up with equal lengths and for each first element of one list I could transform the second list to get the very first element and I could apply induction to show that the statement holds.

So in short, if you think my approach is efficient and correct do you know how to solve the problems I got? And if you think you have better ideas can you give me any hints?

Edit

Just realized that my function only eliminates one repeating sequence. So adapt the argument...


texts: Divide and conquer algorithm for finding majority element of array

texts:
I'm trying to solve the problem for finding majority element of given array. I made two attempts to solve the problem, but seems that both have something wrong in them.
First one relies on the logic that :
1) If $A$ is array with $n$ elements then $A$ has majority element $\Leftrightarrow A_{1} = A[1,...,\frac{n}{2}], A_{2} = A[\frac{n}{2} + 1, ...,n]$ both $A_{1}$ and $A_{2}$ have a majority element and the majority element of the first is equal of the majority element of the second subarray. The bottom of the recursive definition is when $A.size = 1$ then every singleton has a majority element - the only element itself.

Here is an implementation in C++ :

#include <vector>
#include <iostream>
#include <limits.h>
#define INF INT_MAX

int majority(std::vector<int>& arr, int begin, int end)
{
    if(begin == end)
        return arr[begin];
    int mid = (begin + end) / 2;
    int majorityLeft = majority(arr, begin, mid);
    int majorityRight = majority(arr, mid + 1, end);
    if(majorityLeft == majorityRight)
        return majorityLeft;
    else if(majorityLeft != majorityRight &&
            majorityLeft != INF &&
            majorityRight != INF)
        return INF;
    else if(majorityLeft != INF || majorityRight != INF)
        return std::min(majorityLeft, majorityRight);
    else return INF;
}

The second attempt relies on the Dirichlet principle. If i randomly divide the arry into $\frac{n}{2}$ pairs then at least one pair is going to satisfy the condition $\exists i,j : i \neq j, i < j \le n : A[i] = A[j]$
Then for every pair if the elements are equal i keep just one of them in new array, and if they are not equal i discard both of them. Then recussively do the same on the new array.

Here is C++ implementation :

int majority2(std::vector<int>& arr)
{
    if(arr.size() == 1)
        return arr[0];
    if(arr.size() == 0)
        return INF;
    std::vector<int> subArr;
    for(int i = 1 ; i < arr.size() ; i += 2){
        if(arr[i - 1] == arr[i])
            subArr.push_back(arr[i - 1]);
    }
    if(arr.size() % 2 == 1)
        subArr.push_back(arr[arr.size() - 1]);
    return majority2(subArr);
}

I'll be really grateful if somebody tells me what is my mistake in the implementation or algorithms' logic!


texts: What are the characteristics of a typeless programming language?

texts:
Assume that we have an imaginary programming language that allows you to assign a Literal to a variable, but does not allow you to set the the data type of the variable, for example

Allocate4Bytes   an_int_variable        123456;
Allocate2Bytes   a_short_int_variable   123;
Allocate4Bytes   a_float_variable       2.1;

And this programming language also provides different operators to work with different data types, for example:

The + operator is used to add an int to a short int.
The #+ operator is used to add a float to an int.
the = operator is used to assign an int to an int.
the #= operator is used to assign a short int to a short int.
etc.

So it is the job of the programmer to keep track of the data type of each variable and use the appropriate operator on it.

Is this programming language considered to be a typeless programming language, or can we say that this programming language have data types (even though it does not have operator overloading and type safety, etc.)?


texts: Finding stabbing numbers for lines for a set of segments in the plane

texts: So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the plane *(not necessarily axis aligned). The set of segments is fixed but the number of query lines could be large.  I was thinking about maybe dualizing the problem: Each line segment turns into either an infinite "bow tie" or a horizontal band, and then we can compute the overlay of this arrangement, counting the number of intersecting regions inside each cell. But even though this becomes a pretty nice data structure, query time is still an issue. Any thoughts on how to make preprocessing time and stabbing query time low, assuming there will be a "somewhat large" number of queries (the tradeoff between preprocessing time and total query time is somewhat a parameter in this).


texts: Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?

texts:
I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me thinking, can people or do people combine hash tables with other more complex data structures like trees and graphs? Are there use cases and what would they be called? I don't see much written about these on the usual sites like Wikipedia.
Obviously the hash table gives constant lookup time (or nearly so allowing for collision resolution), and the tree or graph gives you ways and means of doing traversals.
I know you can hang a new tree's parent node from every single hash entry but I mean having one tree main tree or graph overlayed and interconnected with one main hash table


texts: Advantage of byte addressable memory over word addressable memory

texts: What is the reason that almost all computers (besides some DSPs) use byte addressable memory? With byte addressable memory and a 32 bit address you can have 4GB while with word addressable memory you can have 4GB * wordsize. Are single bytes used that much that you can't use routines that filter out single bytes from a word because there is an advantage of having more memory?


texts:
Let relational schema R(A,B,C,D,E,F,G,H,I).

The functional dependencies are: A -> BC, AD -> BE, C ->F , A->F , D-> E

Find the number of non-trivial functional dependencies ? I know that R has only five non-trivial functional dependencies but i do not know how to prove this(How to think)?


texts: Recusively Enumerable or Recursive dependent on whether P=NP

texts:
If a language is defined such that
$L = (0+1)^{\ast}$   if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$   otherwise

Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the empty langauge.
Therefore $\mathsf{P} = \mathsf{NP}$ , $L$ is recursive (being regular), but is $L$ still recursive if $\mathsf{P} \neq \mathsf{NP}$?


texts: Finding the N'th viable combination between arrays A and B

texts:
To dumb it down to basics, lets say I have a struct called item that looks like this:

struct item {
    int power, cost;
};

then I have 2 arrays of these items, each filled with N items with various amounts of power/cost

Then I want a list of combinations of these items (item a + item b) where each item must have the highest(or equal to highest) amount of power among other possibilities with the same cost.

One way to get this list is as follow (in pseudo code)

item arrays are A and B

declare array C
do a nested loop through all the combinations of A and B and add these combinations to C
now C contains all the possible combinations

sort C by in an ascending order by cost

declare array D
loop through all the items in C and if
-the item power is higher or equal than the current highest power
-the cost is equal or lower
then if
-the cost is higher than the current highest
   add element to D
else -the cost is equal or lower
   replace last element of D with this one

It works but the amount of memory required for the algorithm is a.size * b.size + then some which is way too much for the 24kB i have available.

A and B aren't random though, due to the nature of the data, the amount of viable combinations is actually less than either A or B.

I'm looking for an algorithm to get the same result as described above but with much less memory use.

I tried one idea I had -

sort A and B by cost in ascending order

while i havent looked to the end of both arrays do
    find next A that in combination with last B has greater or equal power than current highest and mark it down
    find next B that in combination with last A has greater or equal power than current highest and mark it down

    add 1 - 3 elements to D depending on a chain of conditions described in the last snippet, possibly A product, B product and the product of both A and B index

It sorta works but not perfectly, it misses some good combinations and due to that adds some bad combinations. I'm trying to fix it but meanwhile.. figured I'd ask here.

EDIT: to further clarify what I mean, I'll solve a small example with the working (but memory hungry) method

lets say the input is as follows:

A[0].power = 3; A[0].cost = 1;
A[1].power = 5; A[1].cost = 3;
A[2].power = 7; A[2].cost = 8;

B[0].power = 2; B[0].cost = 2
B[1].power = 4; B[1].cost = 3
B[2].power = 1; B[2].cost = 4

As you can see, both arrays are already ordered by cost so we can skip doing that, we can however eliminate B[2] because it has a lower power and higher cost than other options in B and will only yield combinations that would be removed anyway.

Next we combine all of them

(first number between curly brackets indicates power, second cost)
A[0] + B[0] = {5, 3); A[0] + B[1] = {7, 4}
A[1] + B[0] = {7, 5); A[1] + B[1] = {9, 6}
A[2] + B[0] = {9, 10); A[2] + B[1] = {8, 12}

then we list combinations by cost (note that in this example they just happened to be in the right order already, this is not always the case)

{5, 3}, {7, 4}, {7, 5}, {9, 6}, {9, 10}, {8, 12}

Now we can eliminate {7, 5}, {9, 10} and {8, 12} because they yield no improvement of power over equivalent or lower cost options

final result

{5, 3}, {7, 4}, {9, 6}

I'm looking for a way to calculate either all of the final results or better yet, calculate the results on demand by index (they would still be requested in a sequential manner so possibly an algorithm that calculates all of them is the right sequence could be modified to do that). That is because while all the results will very likely fit in the memory, I realized that the theoretical maximum is still A.size * B.size and I cant have it crash under an exceptional circumstance.


texts:
I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested in LLVM but would be interested in any thoughts people had or places to start research. A quite google seems to bring little to light.

My guess would be that there are some optimisation steps which are exponential, but which have little impact on the actual time. Eg, exponential based on the number are arguments of a function.

From the top of my head, I would say that generating the AST tree would be linear. IR generation would require stepping through the tree while looking up values in ever growing tables, so $O(n^2)$ or $O(n\log n)$. Code generation and linking would be a similar type of operation. Therefore, my guess would be $O(n^2)$, if we removed exponentials of variables which do not realistically grow.

I could be completely wrong though. Does anyone have any thoughts on it?


texts: How to reduce UNSAT problems so that less than $7/8+\epsilon$ of clauses are unsatisfied?

texts:
In this question I ask about what use is a solver that can find an assignment that satisfies, say, 90% of the clauses of a known satisfiable 3SAT problem in polynomial time.  The answer seems to be: given a problem ϕ that may or may not be satisfiable, you perform a reduction on an input formula ϕ to another formula ϕ′ such that ϕ′ is 90% satisfied iff ϕ is SAT and run my hypothetical algorithm on ϕ′, which will tell you if ϕ is SAT or not.

My question is a follow-up: what is the reduction from ϕ to ϕ'?


texts: Discrete Mathematics books for Computer Science Self-study

texts:
I am an experienced software developer, want to refresh discrete math back in uni.

I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study beginner.

There are two books below that are recommended by others. Which one should I pick:

Susanna S. Epp's Discrete Mathematics with Applications 4th 2010
Kenneth Rosen's Discrete Mathematics and Its Applications 7th 2011

Below are their books in uk, one of which I will buy based on the US edition.

Susanna S. Epp's Discrete Mathematics with Applications 4th 2011
Kenneth Rosen's Discrete Mathematics and Its Applications Global Edition


texts:
The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?


texts: What is the difference between finite automata and Büchi automata?

texts:
as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented.

From an assignment I'm working on, this automaton can be depicted as both infinite automaton and Büchi automaton.

Can you give me an example for each of those automatons to understand the differences?


texts: Show that this algorithm does not work for determining convex polygons

texts:
Context

Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$  does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no".

My answer

Consider this nonsimple polygon having 4 vertices; the algorithm above will output "yes" as the set of points does not contain both left and right turns, yet the polygon is not convex. Is this a good counterexample rendering the above algorithm incorrect?

Thanks in advance.


texts: Community detections in networks using more than one factor?

texts:
all community detection algorithms in major python packages are using only edges & edge weights. Is there any algorithm that uses multiple attributes of nodes to detect communities?
For ex, in social network, while edges imply relationships, nodes have attributes like age, gender, & interest. Given that FB does have predictions and suggestions, I suspect there are algorithms that use multiple factors to find communities.


texts: Find all non-decreasing sequences given lenght and size

texts:
I'm trying to find a solution for this exercise:

  Give the pseudocode of an algorithm which takes two positive integers
  n and k and prints all the non-decreasing sequences of length k
  (1,2,...,n).

  For example n=4, k=3:

  111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333
  334 344 444

  the complexity must be O(n S(n,k)) with S(n,k) the number of the
  sequences to print for n and k.

i think from the complexity required that a backtracking algorithm it's needed  but i could'nt solve it.

i tried something like this:

P(n,k,h: prefix length, S: sequence)

      if h == k then
           OUTPUT S
      else
         for i=1 to n do
             if(i>=S[h])
                   S[h+1]=i;
                   P(n,k,h+1,S);


texts:
Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by
Barrington, Immerman, and Straubing. Using the following statement:

  Every $\mathbf{NC^1}$-predicate is computed by a Dlogtime-uniform family of polynomial-size propositional formulas

This sentence is essential to defining a reduction from an $\mathbf{NC^1}$ function to the $\Sigma_1^q$-witnessing problem for $G_0$, however I'm not able to understand how this statement was reached from the original paper, either I'm missing something important here or my expertise in circuit complexity is just not enough, can someone intuitively explain how this sentence came to be?


texts: Language of all sequences of permutations whose product is the identity

texts:
Let $\Sigma$ be the set of all permutations in $S_n$. What is the minimum number of states in a DFA accepting the language of all words over $\Sigma$ which multiply to the identity permutation?

For example, if $n=2$, then $\Sigma$ consists of two mappings, the identity mapping $\iota$ and the transposition $\tau$. The language in this case consists of all words containing an even number of $\tau$'s.


texts: What happens if the holder of a lock tries to acquire a lock?

texts:
In a system, suppose there is a process and a resource with only one instance.

Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a deadlock? Under what circumstances?


texts:
What are preconditions and postconditions in this C++ function?

I have this example in my slides but still didn't get the idea!

*Comment function declaration:
    void showInterest(double balance, double rate);
    //Precondition: balance is nonnegative account balance
    //      rate is interest rate as percentage
    //Postcondition: amount of interest on given balance,
   //       at given rate …
*Often called Inputs & Outputs


texts: Find maximal subgraph containing only nodes of degree 2 and 3

texts:
I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to compute a maximal 2-3 subgraph of the input graph.

To be precise, a 2-3 graph is one that has only vertices of degree either 2 or 3. By maximal we mean that there is no other 2-3 subgraph which contains the maximal subgraph as a proper subgraph. It does not have to be a maximum subgraph.

The authors of the paper claim that the computation can be carried out by a simple Depth First Search (DFS) on the graph. However, this algorithm seems to elude me. How can the maximal subgraph be computed?


texts: Why do we use dynamic memory allocation in general and why did we use it in this particular example?

texts:
Dynamic Programming C/C++ implementation of LIS(Longest Increasing Subsequence) problem

/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */

int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );

/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++ )
    lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++ )
    for (j = 0; j < i; j++ )
        if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */
for (i = 0; i < n; i++ )
    if (max < lis[i])
        max = lis[i];

/* Free memory to avoid memory leak */
free(lis);
return max;
}

It is a code from www.geeksforgeeks.org . I have seen explanations that memory is allocated(when done dynamically) on heap,  which is a free store of (very large) memory, so it makes sense to only use dynamic allocation when memory required exceeds memory of stack used for storing variables and data locally allocated in functions.

Would it make a difference if I declared array as int arr[n] (as n is given by user in input) and then in main function use lis(arr, n) ? If so, why? If not, what else does dynamic allocation benefit from in this case and in general?


texts: Heavy hitters problem linear scan and auxiliary space

texts:
I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem:

We have an array of $n$ elements and we want to know which elements appear at least $\frac{n}{k}$ times, for a given $k$. You can think of $n$ as being pretty large and $k$ small.

Proposition There's no algorithm that solves the Heavy Hitters problem in one pass while using a sublinear amount of space.

An intuition for why this holds is given in the notes:

for $k=\frac{n}{2}$ we're looking at elements that appear at least twice in the array.
suppose the array is of the form $x_1, x_2, \ldots , x_{n-1}, y$ , say $S=\{x_i \mid 1\leq i\leq n\}$, then basically the HH problem reduces to a membership problem, is $y\in S$?
we can solve this problem by saving $S$ as a hash table, and the idea is that we can't solve all the memebership problems (for say $n/2$ elements) using sublinear space.

They suggest using the PHP but I don't see how that applies in this context, any idea?

I can see why the statement is true but I'm looking for a formal proof of it.


texts: What is this algorithm? Create a tree's equivalent hierarchical network

texts:
This question was originally posted here: https://stackoverflow.com/q/20735339/2305618

I am surely not the first to have implemented code to perform the following graph transformation. But try as I might, I can't find a previous reference to it.

The transformation arises when creating a single graph that simultaneously models hierarchical inclusion relationships and other pairwise relationships between nodes.

The algorithm transforms a rooted directed tree DAG into an equivalent hierarchical network DAG. Equivalence in this sense - if the meaning of the tree structure is that parents 'consist of' or 'contain' their children the equivalent network structure would carry the same 'consisting of' or 'containment' information.

The tree hierarchy is represented in the network as sub-networks and sub-sub-networks. The tree's exterior nodes are copied across and each interior node X is represented by the pair: X' and X''

Does anyone know the name/reference of this transformation/ algorithm? :-)

Illustration image of this transformation:

Thanks

David


texts:
The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states

  A maximal cut of a cubic graph can be computed in polynomial time

Browsing through some other related results (for example this SODA paper) one gets the impression that this problem is actually NP complete even for cubic instances. In particular, the last paper states that this is indeed so if the graph is subcubic.

That makes me wonder.. What's going on? Is the survey paper (and the result cited therein) faulty or is there some point that I am missing?


texts: Undecidability in the context of modern programming languages

texts:
Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code:

x = read_input
print x

Does undecidability mean that there may possibly be an input to this program such that the program may never halt?


texts: Find the minimum path to every vertex using Bellman-Ford

texts:
I was studying the chapter 24 of the CLRS and got to the following question:

  24.1-5 $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $O(VE)$-time
  algorithm to find, for each vertex $v \in V$, the value $\delta^{*}(v) = \min_{u \in V}\{\delta(u,v)\}$.

From what I understood, he wants an algorithm to find the shortest path beginning in any $u \in V-\{s\}$ to every vertex $v \in V$. So, this algorithm would return one shortest path for each vertex in $V$ in $O(|V||E|)$. I couldn't come with any other answer besides using an All-Pairs Shortest Paths algorithm and choosing the paths with less value for each vertex. But, as this chapter is about the Bellman-Ford, this is probably some modification from the original algorithm.

If someone could point me in the right direction, I would really appreciate.


texts:
Let's say that lists are defined as

List a = Nil | Cons a (List a)

Then, in Haskell is List x the greatest or least fixpoint? I'm asking because the lfp should exclude infinite lists (but you can build them in Haskell), whereas the gfp should exclude finite ones.


texts:
There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right.

Given a function $f:\mathbb{N}\to\mathbb{N}$ we say that $\mathsf{NL}[f(n)]$ is the class obtained by the above definition but the verifier can read the witness $f(n)$ times for an input of size $n$ (i.e. when the verifier finished reading the witness the goes straight to the beginning of it).

We can see of course that $\mathsf{NL}=\mathsf{NL}[1]$.

The question is whether $\mathsf{NL}=\mathsf{NL}[2]$.

Clarification: Prove or Disprove that $\mathsf{NL}=\mathsf{NL}[2]$.

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}[2]$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}[2]$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}[2]$ verifier for $L$ with $w$ and then when it finishes and wants to read it again with second copy of $w$. But the major problem with my approach is that maybe someone tricked me and put a non equal sub-witnesses and I won't be able to find out about this with $\log(n)$ space thus it does not work.


texts: find maximum number of sections that satisfies the condition in a grid

texts:
Here is the description of a problem

Given an array of strings representing an $N$x$N$ grid of $red$ and $blue$ cells and a target color $r$ or $b$, partition the grid into $N$ sections of $N$ contiguous cells. The goal is to have the maximum number of sections where more than half of cells are of the target color. Return the sections as an array of arrays of strings representing the coordinates of the cells in each section.

For example, in a 3x3 grid, given
$$
\begin{pmatrix}
b & r & r\\
b & b & b\\
b & b & r
\end{pmatrix}
$$
and a target color of $b$ the expected return would be
$$
  \begin{eqnarray}
   section&=&(2,1) (1,1) (1,2)\\
   section&=&(1,3) (2,3) (2,2)\\
   section&=&(3,1) (3,2) (3,3)
  \end{eqnarray}
$$
To solve the problem, what I wanted to try is to represent the matrix as graph and then perform these steps

Find all the (N-1)-hop neighbors and create arrays like $((1,1), (1,2), (1,3))$ for $N=3$
Find all combinations of those arrays that covers the whole matrix
Rank it somehow?
???

(failed to come up with a solution for step 3 and below).
However I believe my approach would be too complex if for example N will become like 6, 7 etc, because it is basically a brute force. So I have been wondering if there is some existing algorithm that tackles the same problem?


texts: Problems showing the constraint of master theorem case three holds

texts:
Prove or disprove the following statements:

$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$

I think I should use the third case of the master theorem to check these equations.

But I have not been able to check this constraint for these inequations:

$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$

How do I do that?


texts: how to add bound to clustering algorithm?

texts:
I've got a numeric matrix with 72 rows and 2 columns where the first column is the index value and the other column has sequence from 0 to 5 repeated 12 times.  The dataset is like above:

1  0
2  1
....
6  5
7  0
....
72 5

I add the dataset graph

I would like to use machine learning with a clustering algorithm to group data in 6 clusters horizontally. How to force algorithm to consider only nearest values on the x axe? How to modify the dataset to force the algorithm to consider this bound?
How to obtain a solution like below?


texts: What is the time and space complexity of Rete algorithm

texts:
I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, some of his paper and he has provided some complexities which are not based on then, nor does its efficiency is provided in the space complexity.

My algorithm despite large inputs worst case is $O(n^2)$. Can someone point me to a good reference where I can find its complexity? I have been searching for a while now, and I did not even get the pseudo code. Things not to consider in order to save your time is algorithms, software, expert systems based on Rete algorithm e.g. Jess etc.
reference link for algorithm thesis pdf  Click to download

citation of the paper "Forgy, C.L., 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial intelligence, 19(1), pp.17-37."


texts:
A regular language is a language that can be represented by a regular expression(or for which there exists a DFA), then why is language represented by  0$^{+}$   not regular?

I am asking this because for the following question the correct answer is option 2

Let L denote the languages generated by the grammar S→0S0∣00.
Which of the following is TRUE?

L=0$^{+}$
L is regular but not 0$^{+}$
L is context free but not regular
L is not context free


texts: Can someone explain this formula for calculating Manhattan distance?

texts:
This is from a Kickstart problem:

  Note: The Manhattan distance between two squares (r1,c1) and (r2,c2)
  is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the
  absolute value.

Then in the analysis:

  Note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

  This formula is based on the fact that for any point, the set of
  points within a manhattan distance of K form a square rotated by 45
  degrees. The benefit of this formula is that if we fix (x2, y2), the
  distance will be maximized when x1 + y1 and x1 - y1 are either
  maximized or minimized.

Could someone explain in more details how this formula can be derived?


texts: Unrestricted grammar to generate $a^{n^2}$

texts: I have been asked to find a grammar that will generate the language $\{a^{n^2}:n \ge0\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn't work. Any idea on how to setup such grammar? Any help will be appreciated.


texts: Golden Section, Fibonacci and Dichotomic Searches

texts:
I wonder if somebody could quickly and briefly outline some of the similarities and differences between the line search methods Golden Section Search, Fibonacci Search and Dichotomic Search.

I know Dichotomous has two functional evaluations per iteration whereas the other two only one, and that the Fibonacci search tends to the Golden Section as the number of functional evaluates tends to infinity. I know also that you have to predetermine the number of functional evaluates for Fibonacci. Are there other, similar techniques?


texts: Situation calculus: how to find pre-conditions in 15-puzzle game?

texts:
I have been working on finding the preconditions for a situation calculus example for some time now. This example is called the game "15-puzzle" where you can find a discription here https://en.wikipedia.org/wiki/15_puzzle.
The following fluents are given for this game:
at(x,y,z,s) // which means: there is a tile z at position x,y.
free(x,y,s) // which means: position x,y is free.

And now I have to find the preconditions for the following actions (movements):
move_up()
move_down()
move_left()
move_right()

I have tried really cumbersome solutions which I am sure are not correct. I would be very grateful if someone has the right approach for me!


texts: Finding Hamiltonian cycles in polynomial space

texts:
Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space.

My thoughts: I thought that I could show that $H \in NP$, by which it would automatically follow that $H \in$ polynomial space. By the witness theorem, the $m$ distinct Hamiltonian cycles (call them the set $C$) would serve as a witness. However, what is not apparent is if $|C| \leq |G|^k$. In fact, that is the entire problem, isn't it? What am I thinking about wrong over here?


texts: How fast can we decide whether a given DFA is minimal?

texts:
Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem:
Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$.
Most of these algorithms run in polynomial time.

However, I wonder whether the decision variant of this problem - "given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal?" - can be solved more efficiently than actually computing the minimal automaton.
Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.

As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms.
Unfortunately, I cannot see how (I hope I am not missing an obvious point here).

Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any "shortcut" that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process.


texts: How to show that pda accepts empty language?

texts: I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski or Thompson, but they are for DFA, so I don't know if it would work.


texts:
A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice.

A simple undirected graph is an undirected graph with no loops and multiple edges. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A path of length $n$ is a sequence of n edges $e_1$,$e_2,\ldots,e_n$ such that $e_1$ is associated with $\{x_0,x_1\}$, $e_2$ with $\{x_1,x_2\},\ldots,e_n$ with $\{x_{n-1},x_n\}$.

  What is the length of the longest simple walk in a complete graph with $n$ vertices?

What I tried: When $n$ is odd, every vertex has degree $n-1$ which is even. It follows that the graph has a euler circuit (every edge is included), therefore the longest walk length is $n(n-1)/2$, corresponding to the total number of edges.

But when $n$ is even, I try to follow similar reasoning and get stuck. I get a degree sequence, but I can't prove it is graphic. How could we handle the case where $n$ is even?


texts: In-place patching of diff between two sets?

texts:
For two ordered sets of keys Paul Heckel's diffing algorithm generates the necessary actions to transform, or patch, one set to the other. I am asking how you'd do the patching without keeping a copy of the "old set" around, nor incurring a large performance penalty. The problem statement is agnostic to the choice of diffing algorithm; the Longest-Increasing-Subsequence algorithm, or similar, could be used just as easily.

To illustrate, the first set could be patched not in-place using the following Rust code:

let old = vec![0, 1, 6, 4, 9, 3, 2, 8];
let new = vec![3, 5, 2, 7, 1, 0, 9, 4, 8];

let mut out = old.clone(); /* <-- Creates temporary copy. */
for action in diff(&old, &new) {
    match action {
        Insert(i) => {
            out.insert(i, new[i]);
        }
        Remove(i) => {
            out.remove(i);
        }
        Move(i, j) => {
            out[j] = old[i]; /* <-- Uses old set. */
        }
        Update(i) => { /* ... */ }
    }
}

out == new // = true

However, the above code clones old to refer to when performing out[j] = old[i];. This is unwanted since I am operating on a data structure that is unwieldy to copy.


texts: Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?

texts:
So I just started learning about computability, undecidability and Turing machines. And I wonder if:
Given a computable and injective function $f$, is $f^{-1}$ also computable and injective?
I don't really know where to start to prove this, any hint or explanation would be appreciated.


texts: What is the distinction between S-attributed definitions and L-attributed definitions? Which one is more expressive? Is there any significant difference in how easily they can be implemented with a recursive descent parser? Why or why not?


texts:
Given a Weighted Partial Max SAT problem (WPM-SAT) - are there generally used algorithms or techniques to generate 'approximate' solutions, which are
not necessarily optimal, but found faster than solving directly? The approximate solutions must satisfy the hard clauses.
Context
I have a series of very large (millions of literals, billions of hard clauses, millions of soft clauses) WPM-SAT problems, that I would like to get an answer to. However, I do not want to wait days for the absolute optimal result. I would like a reasonable (possibly sub-optimal) answer in a shorter amount of time.
So far
In my brief literature review, perhaps I am not searching with the right terms, I haven't found too many good results for specifically approximating weighted partial max SAT.
Some methods seem to solve the hard clauses separately and then use various schemes for selecting literals to make true/false. Based on various randomized 3/4 approximation stuff. I'm not too interested in setting the hard clauses just once, or even just a few times. I know that, at least in my problems, there are many, many different solutions to the hard clauses.
In terms of solving the WPM-SAT problem there is the Fu-Malik paper, where they proposed 2 SAT based solvers for PM-SAT:

Diagnosis Based, which seems to originally create an UNSAT core and then sort of successively relax clauses to arrive at the final optimal result. - This does not seem aplicable because it goes 'backwards', starting unsatisfiable and then slowly becoming satisfied at the maximum.
Encoding Based, where an efficient ranking type scheme is created and then through a binary search / linear scan the optimal is arrived at. - This seems very promising, is this normally how this approximation would be done - just stopping early in the linear scan, or stopping the binary search after only a few iterations?

Opposed to SAT based techniques there are also branch and bound based techniques to solving WPM-SAT problems. Where we generate some upper / lower bounds on a given partial solution, if the upper bound is lower than our best so far we don't need to bother looking at it. When we arrive at a full solution it's upper bound is possibly better than our best, and we could stop after a certain amount of time maybe.
The Question, (again)
I have some big WPM-SAT problems, I want a reasonable solution to them; fast not necessarily optimal.

Should I modify/implement the encoding based Fu-Malik algorithm to exit early?
Should I modify/implement the branch and bound based algorithm to exit early?
Is there something else that I have not found? References / survey papers that I haven't found for this stuff? Anyone working on this?

Bonus question: If I have a reasonable heuristic already can I use that to seed the optimization to go faster? What if that heuristic does not satisfy the hard clauses?


texts: Algorithm to partially sort list into equal-sized buckets

texts:
Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need to be sorted.

For example, for the input

[64, 72, 57, 47, 5, 4, 64, 21, 64, 65, 36, 43, 81, 44, 19, 87, 17, 86,
 73, 21, 19, 64, 94, 91, 34, 49, 8, 52, 18, 37]

that I want to divide into 5 buckets, some valid outputs would be

[[4, 5, 8, 17, 18], [19, 19, 21, 21, 34], [36, 37, 43, 44, 47],
 [49, 52, 57, 64, 64], [64, 64, 65, 72, 73]]

[[8, 17, 18, 5, 4], [21, 19, 21, 34, 19], [43, 37, 44, 36, 47],
 [52, 57, 49, 64, 64], [64, 64, 72, 73, 65]]

[[8, 18, 5, 4, 17], [19, 19, 21, 21, 34], [47, 36, 44, 43, 37],
 [52, 64, 49, 64, 57], [64, 72, 64, 65, 73]]

[[18, 8, 17, 5, 4], [21, 19, 21, 19, 34], [36, 44, 43, 37, 47],
 [57, 64, 64, 49, 52], [64, 72, 64, 65, 73]]

One approach to do this would be to sort the list, and then divide it at equal intervals. Can this be done faster?

I would also be happy with a result where the buckets are of only roughly equal size, but note that I can't assume a uniform distribution for the numbers, so bucket sort doesn't help.


texts: How is Rank Selection better than Random selection and RWS?

texts:
I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does:

Tour1's Fitness: 0.87
Tour2's Fitness: 1.22
Tour3's Fitness: 1.03
Tour4's Fitness: 0.58

We rank them using their fitness:

4) Tour2 -- Highest rank (N)
3) Tour3
2) Tour1
1) Tour4 -- Lowest rank (1)

We generate a random number between 1 and 10 (sum of ranks), for example X = 3.
We then loop and sum the ranks until its greater than X and we select the tour, in this example it will be Tour2 since it's rank is 4 and 4 > 3.

What I don't understand is how is this better than just randomly selecting a tour and why is it better than Roulette Wheel Selection? ALso please correct me if I'm missunderstanding the method.


texts: Why are both caller-save registers and callee save registers needed?

texts: I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller prologue and restored in caller epilogue. Callee-save are those who are used by callee and are saved in callee prologue and restored in callee epilogue. But why are both needed? If caller is saving the needed registers already, why should callee save them again on use? I am really confused.


texts: Cycle of length k with no repeated edges

texts:
I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with no repeating edges, of a size at least k? (i.e. the number of edges in the cycle is at least k)

I thought that this problem can be reduced somehow to the euler cycle problem, but have no idea how to do this.

Thanks


texts: Is this lambda abstraction created as a generator of a recursive function?

texts:
In lambda calculus, a recursive function $f$ is obtained by

$$ f = Y g $$

where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e.  $f == g f$.

In The Scheme Programming Language, I saw an example implementing a recursive function $f$ that sums the integers in a list:

(let ([sum (lambda (f ls)
                  (if (null? ls)
                     0
                     (+ (car ls) (f f (cdr ls)))))])
(sum sum '(1 2 3 4 5)))  => 15

What is the mathematical derivation that drives to create the lambda abstraction

 lambda (f ls)
     (if (null? ls)
         0
        (+ (car ls) (f f (cdr ls))))

?
It looks like a generator of $f$, but not entirely.

Thanks.


texts: Regular language for word that was merged from 2 diffrent words

texts:
I need to prove that if $L1,L2$ is regular languages
$L=\left\{ a_{1}b_{1}a_{2}b_{2}\cdot\cdot\cdot a_{k}b_{k}\mid a_{1}\cdot\cdot\cdot a_{k}\in L_{1},b_{1}\cdot\cdot\cdot b_{k}\in L_{2}\right\} $
will be regular as well.

My approuch is :

There is $A_{1}=\left\langle Q_{1},\Sigma,\delta_{2},q_{0_{1}},F_{1}\right\rangle $
and $A_{2}=\left\langle Q_{2},\Sigma,\delta_{2},q_{0_{2}},F_{2}\right\rangle $

s.t $L\left(A_{1}\right)=L_{1}$ and  $L\left(A_{2}\right)=L_{2}$

I was thinking to create a DFA that will recognize $L$

$A=\left\langle \left(Q_{1}\cup Q_{2}\right) ,\Sigma,\delta,q_{0_{1}},F_{2}\right\rangle $

But Im having troubles with the defenistion of $\delta$, how i can force transition from $A_1$ to $A_2$ and vice versa ?
Any advices ?


texts: Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

texts:
Baker, Gill and Solovay [1] gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language

$$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \text{ using }<n\text{ tape slots} \}.$$

(This inductive definition of $A$ is sound because no machine can query "beyond its means" and ask $A$ whether he himself will accept his input string, because he would have to query $A$ and write $1^n$ on the oracle tape. If he is still writing, then clearly he has not accepted, and so $A$ says "no".)

The proof that $P^A=PSPACE^A$ is likewise simple: Suppose that $L\in PSPACE^A$. Then a $p(n)$-space machine $M$ accepts $L$. Given an input $x$, a $P^A$-machine $T$ for $L$ is: Write $\langle M, x, 1^{p(|x|)}\rangle$ on the oracle tape, query $A$, and accept iff $A$ says "yes". So $PSPACE^A\subseteq P^A \quad\square$

But in fact $T$ is not only a $P^A$-machine, $T$ is even a $LOGSPACE^A$-machine! Hence $PSPACE^A\subseteq LOGSPACE^A$. But the space hierarchy theorem says this cannot be the case. BGS even remark that the reduction $T$ performs can be performed in Logarithmic space, but they do not use that fact to come to my conclusion.

Clearly I have made a mistake somewhere. Where?

(One response might be that while a $PSPACE$ machine can use only polynomially much tape for its work, it can write exponentially long queries to the oracle. Denote by $PSPACE^{A[poly]}$ the class of languages solvable by a $PSPACE$-machine which makes only polynomially long queries to $A$. Then the space hierarchy theorem for $Logspace^A\subsetneq PSPACE^{A[poly]}$ goes through as usual)

[1] Baker, Theodore, John Gill, and Robert Solovay. "Relativizations of the P=?NP question." SIAM Journal on computing 4.4 (1975): 431-442.


texts: Program that generates a regular expression from an FA

texts:
Possible Duplicate:
  How to convert finite automata to regular expressions?

Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation.

To make things less complicated I want to limit the number of states to about 4, assume the FA is in minimal form and that the FA has only one FinalState and only one StartState.

Ive been thinking about it for a while now and I think the first obvious thing to do would be to create a transition table for the FA.

So an FA could look like this:

NumberOfStates 4
StartState   1
FinalState   4
StateNumber  NextStateA   NextStateB
1            2            4
2            3            2
3            4            4

And would generate the regular expression: b + (ab*a(a + b))

Ive been racking my brain for hours but am stumped on how to go about this. Any ideas is greatly appreciated.


texts:
I have a floating point number system and I have a number for which I need to calculate the  exact relative error after rounding. The number is clearly an overflow. Does anyone know what I should do?

I've tried converting the number to from the decimal base to the base of the system, then just chopping of and rounding the excess and keeping the exponent within the bounds of the system.

For example, say I had .a0a1a2a3a4... and the exponent was say b4;
I chopped off at a3 and rounded so now I have .a0a1a2a3 and I just changed the exponent to the bound which is b1

So, my new number is .a0a1a2a3 * b1 my answer need to be in base 10 so I take this number go back to decimal and calculate the exact relative error. I got something like 0.99... Is this what I'm suppose to do or is there something else to be done when it overflows?


texts: Question regarding notation of a language decidability

texts:
$1.\: A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$
$2.\:A_{DFA} = \{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$
I know how to proof that 1 is decidable by constructing a machine that always halts and accepts whenever $B$ accepts, otherwise rejects. what's the difference between 1 and 2. I find that it doesn't make sense to not include $w$ inside the encoding brackets but I have seen this notation in other places. are they both the same?


texts:
I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously confusing me.
This paper describes the use of the Stockham FFT on the GPU. It contains the following diagram:

I understand how to calculate the discrete fourier transform for any individual point, but I'm confused how exactly the Stockham FFT proceeds. My understanding was that the FFT in general divides the input into odd and even data points, and then recursively processes these. But the diagram I added above looks reversed to me. It starts by dividing the input into the smallest segments and then adds up to larger ones, I would have expected this to work exactly the other way around.
How exactly does the divide-and-conquer part of the Stockham FFT work?


texts: Why isn't an edge-map graph implementation used in practice?

texts:
Wikipedia states that three different graph implementations that are used in practice:

Adjacency Lists
Adjacency Matrix
Incidence Matrix

While I was learning about these structures, another implementation occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are (vertex, vertex) pairs and the values are the cost of their edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

Store graph: $O(E)$
Add vertex: $O(1)$
Add edge: $O(1)$
Remove vertex: $O(V)$
Remove edge: $O(1)$
Query cost between vertices: $O(1)$

Since this implementation has strictly better time and space complexity then all three options listed, I'm confused as to why this option isn't.

Why isn't this implementation used in practice?


texts: Using B-method, and formal methods in general, to model and verify a reverse linked list

texts:
I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead.

Is there already any formal methods or any formal for doing this ?

Exactly the same as a normal linked list but when a new block (value etc) is added this references the past value (much like the bitcoin blockchain).

I have modeled a normal linked list (Data queue) modeled in the b method

MACHINE DataQueue ( DATA , anydata , maxqueue )

CONSTRAINTS anydata E DATA /\ maxqueue > 0
SEES Bool TYPE
SETS TOKEN
PROPERTIES card ( TOKEN ) = maxqueue
VARIABLES TokenSeq , TokenMap

INVARIANT
TokenSeq E iseq ( TOKEN ) /\
TokenMap E TOKEN -|-> DATA /\
dom ( TokenMap )=  USED
INITIALISATION
TokenSeq , TokenMap : [] , {}

OPERATIONS
success , token <-- AddItem( item )  =^
PRE E item DATA THEN
CHOICE
ANY new token WHERE new_token  E TOKEN_USED
THEN
TokenSeq := TokenSeq <-- new token ||
TokenMap ( new token ) := item ||
success , token := TRUE , new token
END
OR
success := FALSE || token :E TOKEN
END
END ;
DEFINITIONS
USED =^ ran ( TokenSeq )
END


texts: Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

texts: I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }


texts: How to Solve the following Recurrence Equation?

texts:
I wanted to Solve the following Recurrence Equation using Master Theorem and Back substitution but Im stuck at certain point . can u pls help me how to proceed further

$T(n)=T(\sqrt{n})+n+c$

Using Master Theorem,

put n = $2^{m}$

$ T(n)=T(2^{m})= S(m)$ ie $T(\sqrt{n}) = S(\frac{m}{2})$

Hence the Recurrence Relation will be
$S(m)=S(\frac{m}{2})+ 2^{m}$

Here a =1 , b=2 $f(m)=2^{m}$

case 1 :  $2^{m} \notin O(m^{\log_b a - \epsilon })$

case 2 : $2^{m} \notin \Theta (m^{\log_b a } \log^{k} n)$

case 3 : $2^{m} \in \Omega (m^{\log_b a +\epsilon } )$

put $\epsilon = 1$  We get

$2^{m} \in \Omega (m^{\log_2 1 +1 } ) \Rightarrow \Omega (m^{0+1})\Rightarrow \Omega (m)$ Which is True

Now checking Regularity

$af(\frac{m}{b})\leq \delta f(m) \Rightarrow f(\frac{m}{2})\leq \delta f(m)$

ie .$2^{\frac{m}{2}} \leq \delta \ 2^{m}$ taking log on both sides
$\frac{m}{2}\leq \log_2 \delta +m$

taking $\delta =\frac{1}{2}$

$\frac{m}{2}\leq -1 +m \Rightarrow 1 \leq  \frac{m}{2} $

How to check this last condition is satisfied or not ? How to proceed from here... ?

Using back Substitution
$T(n)=T(\sqrt{n})+n+c$

$T(n)= T(n^{\frac{1}{2}})+n+b \\ = T(n^{\frac{1}{4}})+n^{\frac{1}{2}}+n+2b \\ =T(n^{\frac{1}{8}})+n^{\frac{1}{4}}+n^{\frac{1}{2}}+n+3b \\ ... \\ .. \\ = T(n^{\frac{1}{2^{k}}})+\sum_{i=1}^{k} n^{\frac{1}{2^{i}}} + kb$

How to Evaluate the summation ? How to proceed further... ?

please explain both the method.


texts: Fast hill climbing algorithm that can stabilize when near optimal

texts:
I have a floating point number x from [1, 500] that generates a binary y of 1 at some probability p. And I'm trying to find the x that has highest p. I'm assuming there's only one maximum.

I know we can do this with simulated annealing but I don't think I should hard code temperature because I need to use the same algorithm when x could be from [1, 3000] or the p distribution is little bit different.

Is there an algorithm that can converge fast to the x with highest p while making sure it doesn't jump around too much after it's achieved for e.x. within 0.1% of the optimal x? Specifically, it would be great if it stabilizes when near < 0.1% of optimal x.


texts: Solution to a Np-hard problem and its relevance to a dual LP

texts:
From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual):

  Let $y^*$ be an optimal solution to the following dual LP $$max \sum_{i=1}^n{y_i}$$$$subject \sum_{i:e_i\in{S_j}}{y_i \leq w_j}, y_i \geq0; j=1,...,m;i=1,...,n$$
  and consider the solution in which we choose all subsets for which the corresponding dual inequality is
  tight; that is, the inequality is met with equality for subset $S_j$, and $\sum_{i:e_i \in{S_j}}{y^* = w_j}$. Let $I^{'}$
  denote the indices of the subsets in this solution. We will prove that this algorithm also is an $f$-approximation algorithm for the set cover problem

I would like to know what does the writer mean by corresponding dual inequality? Is there any correspondence between a solution of the Set Cover problem and a dual LP solution?

I can't understand what does the paragraph mean.

Thanks in advance.


texts: Emulating equal operator using multiplication

texts:
I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use multiplication at the end.

Basically I want to find $f$ and $g$, such that:

$$ f(A) \cdot g(B) = \begin{cases}
1, & A = B \\
0, & A \ne B
\end{cases} $$

For example, if I use $g(x) = 1/x$ I get something close to what I want
$$ A \cdot 1/B = \begin{cases}
1, & A = B \\
A/B, & A \ne B
\end{cases} $$
Is it possible to do that? If so, what are the functions $f$ and $g$ that I should use?


texts:
The standard resolution algorithm returns false if no new clauses are added.

I know that if $KB \land \neg a \implies []$, it returns true by proof by contradiction, but how can I understand the false case intuitively?


texts: Algorithms - Solving recurrence-relations/Bounds?

texts:
I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige.

Suppose we have this recurrence:

$$    T(n) = 2T(n/2) + \log n$$

How would we figure out running time for this, and specifically, how would we PROVE the upper and lower bounds (ideally as tight as possible)?

I tried working through my homework with the help of a few YouTube videos, but I don't seem to be following it. In giving an explanation, please try and be careful to explain why something is a certain time, as I haven't really gotten the hang of intuiting that yet.

I have some working knowledge of induction and calculus, but it seems like I'm missing a big chunk of context somewhere and I really need to get up to speed. Thank you for any assistance.


texts: Algorithm complexity similar to Selection Sort

texts:
I'm working on an algorithm that takes an array of $N$ values and it will iterate through each of the values and in each of them iterate through the rest of the array to the right. So the first value will check $N-1$ positions, the next one will check $N-2$, etc

I'm a bit confused about the time complexity of my algorithm. I remembered that Selection Sort does a similar operation and I checked it's considered $O(N^2)$ best and worst case. Why is that? If both algorithms check less and less positions every new position I imagined it would be some complexity between $O(N)$ and $O(N*log(N))$ and not $O(N^2)$.

Another question. If I did my algorithm only for half of the array what would the complexity be? I mean starting at the middle position and only doing the algorithm to the right side for example so the middle position would check only $N/2-1$ positions and the next only $N/2-2$, etc.
I guess it would be $O((N/2)^2)$ which would be $O(N^2/4)$ and so still $O(N^2)$?


texts: Merging of two increasing binary trees why do we exchange left and right subtree

texts:
We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.
One way to merge these kind of trees is as follow (we denote by $E$ the empty binary tree) :

merge ($E$, $B(l, x, r)$) = $B(l,x,r)$

merge ($B(l, x, r)$, $E$) = $B(l,x,r)$

merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_1, B(l_2,x_2,r_2)$), $x_1, l_1$) when $x_1 \leq x_2$

merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_2, B(l_1,x_1,r_1)$), $x_2, l_2$) when $x_1 > x_2$

Thus when merging two binary trees we are exchanging the left and right subtrees. I am wondering why it's important to do so ?
I guess this is because we don't want our final binary tree to be pathological like for example a tree with only nodes on it's right (which will cause a big height). If this is the reason why we exchange the left and right subtrees when merging I am wondering what make us believe that with this merging function we will not encounter pathological trees ? I mean how can we be sure that this new merging function will not produce pathlogical binary trees ?
Also it's the first time I see a merging function that exchange the left and right subtree. So is this a common thing to do for some categories of binary trees like increasing trees ?
Thank you !
Some references : Skew heap and min-heap


texts: How are two layer feed-forward neural networks universal?

texts:
Across my studies I have noticed the following statement in my Subject Guide; namely, that two-layer feed-forward neural networks using the sigmoidal activation function are universal. My question is how are the networks 'universal' and what does 'universal' actually mean in this instance?

Thanks in advance.


texts: Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$

texts:
I'm studying the PCP theorem.

While it is easy to prove that $\mathsf{P}=\text{PCP}(O(\log n),0)$ , proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$  i.e. PCP that uses $O(\log n)$ random bits and read 1 bit of the proof is less obvious, what I tried to do is to take some proof $\pi$ of length $n^{O(1)}$ (because effectively the message sent by the prover is bounded by $2^{r(n)}q(n)=2^{O(\log n)}=n^{O(1)}$) then try all the coin tosses each time the verifier read some bit of the message so if the proof is not correct we flip the bit in the proof!


texts: What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + ... + (n-1)2 + n$?

texts:
My best guess is that the series
$$ \sum_{i=1}^n i(n-(i-1)) $$
becomes
$$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$
So the highest term is $n^2$ and there are $n$ terms. Does that mean its $O(n^3)$? That seems high. Intuitively, it seems like it should be closer to $O(n^2)$ but I can't find a way to bring it down mathematically.


texts: Recursive euclid algorithm for gcd complexity

texts:
I am trying to calculate the complexity of the euclidean algorithm for finding the greatest common divisor (gcd) (recursive version).

Here's the pseudo code:

algorithm euclid(a,b)
if b = 0 then
    return a
else
    return euclid(b, a mod b)
end if

My initial thought is that every time the recursive function is called, its complexity is O(1). I also know that $b\ge F_k$ for k calls of the function, as I have proven this by induction previously (see proof below). This means that the runtime grows with the input b and this is where I am stuck. Any help would be greatly appreciated!

Additional Question: Does calculating the complexity of the recursive algorithm work in any way similar to the calculation of the complexity of the iterative algorithm in this post: Euclid's Algorithm Time Complexity? What would be similarities and differences?

Proof by induction, that $a\ge F_{k+1}$ and $b \ge F_k$ iff $a>b\ge 0$ for $k \ge 1$ recursive calls of the function:

Let $n_0=1$ then a%b = 0 and gcd(a,b) = b. From this follows that $F_1 = 1 \le b$, since if $b<1$, $k$ would have to be $k = 0$. $F_2 = 1 \le a$ is also valid, since otherwise $a>b$ would be invalid.
$a\ge F_{n+1}$and$b\ge F_n$, $k = n$,  is valid.
To show: For $k=n+1$: $a \ge F_{n+2}$ and $b\ge F_{n+1}$

Let euclid$(a_{n+1},b_{n+1})$ be a call of the recursive function
above.

Then for $q \in N, q>0$:
$b_n+1 = a_n \ge F_{n+1}$

and

$$a_{n+1} = b_{n+1}*q+b_n
= a_n*q+b_n \ge F_{n+1}*q+F_n \ge F_{n+1}+F_n
= F_n+2$$
Q.E.D


texts: Egg dropping problem binomial coefficient recursive solution

texts:
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)

In the binomial coefficient solution we construct a function $f(x,n)$, which represents the maximum number of floors we can cover with $x$ trials and $n$ eggs.

So there are two cases, if we drop an egg. Either it breaks, so we have $x-1$ trials left and $n-1$ eggs, or it does not break, so we have $x-1$ trials left and $n$ eggs.

Thus we have the following recursive expression:
$$
f(x,n)=1+f(x-1,n)+f(x-1,n-1)
$$

I cannot understand why we are adding the terms $f(x-1,n)$ and $f(x-1,n-1)$. As only one of the two contingencies happens, (the first egg breaks or not), why do we use simultaneously both terms in the sum.

Can someone please explain that in detail?

Thank you in advance


texts: Do there exist fast multiplication algorithms for two integers with one of them being static?

texts:
Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). But there is always the assumption that both numbers are equally arbitrary.
Are there algorithms that are even faster under the assumption that for every time N changes, M changes K times with K being 2^20 or more?
An algorithm that given an integer, constructs/primes a special fast algorithm to compute a product just for that integer.
The only algorithm of this kind that I was able to find and that gave rise to this question is described in this paper: https://sci-hub.tw/10.1007/s00224-020-09986-5
C code provided by the author (GMP lib): http://www.fit.vutbr.cz/~ibarina/tmp/n.c
Summary: Uses the Collatz conjecture to do multiplication, O(Nk) where k is the number of odd integers in the Collatz sequence of a given odd operand. If k < log N it can beat current state of the art multiplication algorithms.


texts:
Person(name, phone)
  Mike 456-789
  Mike 123-456
  John 230-785
  $\dots \dots$

How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am frustrated with all materials that I've learned.

Is it correct syntax to use count() like $\pi_{name}(\sigma_{count(phone)>2}(Person))$ ?


texts: Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0

texts:
Lets consider sequences whose elements are $-1,0,1$.
Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$.
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$.
Subsequence $A[i...j]$ is $supergood$ if it is good and every its prefix-sum is $>= 0$
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is not $supergood$ but $1,0,-1$ is $supergood$.

Now I want to have dynamic data structure which allows me efficiently do these operations:

Insert(S,x,i) - inserts $x$ into $S$ on $i$'th position
Remove(S,i) - Remove $i$'th element
isSuperGood(S, i, j) - checks if subsequence $i$, $j$ is supergood

The solution could be AVL tree with sum of elements in left and right subtree. It is easy for update and allows us to check if subsequence is good in $O(\log(n))$:

Find node i (let say v) $\ O(\log(n))$
Find node j (let say u) $\ O(\log(n))$
Check if v.val + v.lsum - u.lsum == 0 $\ O(1)$

But if it comes to checking supergood condition, I don't see how.


texts: Updating types during type inference in a Hindley-Milner type system

texts:
I'm looking at implementing type inference for a Hindley-Milner type system, and before I have even started to implement the Damas-Milner algorithm, while working through some examples, I hit some stumbling blocks.

I'm trying to follow some notes on the algorithm. Given the following program:

let id x = x
  in id id

I first use the pseudo code for the letfn case:

Create a new type variable for the function type: funType := α
Create a new type variable for the argument type: argType := β
Infer the return type:

Extend the (empty) type environment for the function body to be functionBodyTypeEnv := ['x' → β, 'id' → α]
Look up the return type and find it to be β: returnType := β

Note down the constraint that the function type and (argument → result) type must be the same: α = β → β

Okay. So far so good. We now have a type for the function (α) and also have found one constraint: α = β → β. Now let's infer the type of the let's body (which will be the type of the full program):

Extend the (empty again) type environment with the generalized type of the function so we get letBodyTypeEnv := ['id' → ∀α.α] ⚠
Infer the type of the let body, which is a call with of 'id' (function) with 'id' (argument):

Find the type of the variable 'id' (function) to be ∀α.α and instantiate/specialize this to be γ: funType := γ (there are no free type variables, so it's a monotype) ⚠
Same as above: Find the type of the variable 'id' (argument) to be ∀α.α and instantiate this to be δ: argType := δ ⚠
Create a new type variable for the return type: returnType:= ε
Note down the constraint that the function type and the (argument → result) type must be equal: γ = δ → ε
Return the result type as the type of the let body: return ε

So at this point we have the type ε for the full program and have recorded the constraints [α = β → β, γ = δ → ε]. However, this is (obviously) wrong and I suspect that the problem is with step 4, 5.1 and 5.2.

In step 4 we have the type of the function 'id' as α and generalize it to be ∀α.α before inferring the type of the let body. However, if instead of just “noting down” that α = β → β we replaced α by β → β in the type environment of the let body, we would have inferred the type β → β in step 5.1 and 5.2 – and that would have been the (correct) type of the program.

Are my observations correct? If so, should I always replace a type variable with the type it's equal to when finding such a constraint?


texts: If $L$ is a regular language, then $s(L)$ is also regular

texts:
...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.

For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.

My thoughts so far are that replacing characters in a regular expression with regular expressions still gives us a regular expression overall. Namely I can show for $x \in L$ that $s(x)$ will be a regular set, and then I can do a union over $s(x)$ for all $x \in L$ to show $s(L)$ is regular (by closure of union).

My problem here is carefully showing the substitution will produce a regular set. Does it suffice to say if $x$ is something captured by a regular expression, then $s(x)$ is regular as well? I'm not sure how to prove this.


texts:
In the textbook I'm reading, it states that

  If the interrupt is of a lower/equal priority to the
  current process then the current process continues
  If it is of a higher priority the CPU finishes its current
  Fetch-Decode-Execute cycle. The contents of
  the CPU’s registers are copied to a st...

In short, the CPU reacts instantly to the interrupt and either ignores/defers it or waits until the current cycle is completed before processing it.

I don't know if this is just a simplification, but this doesn't seem right...

I thought interrupts were pushed into a buffer, while the CPU is running, and after every cycle, the buffer was checked by the CPU. This makes more sense, and seems more plausible, but also contradicts the previous explanation.

Does the CPU physically get interrupted by the interrupt, or does it briefly check the buffer after every cycle?

I don't know much of the terminology, besides "an interrupt service routine."

Edit: Is it a mixture of both? The highlighted explanation references a process, which I realise could encompass many CPU cycles, which are ended in the check of the buffer. If the precedence is higher, the process is popped out, for the ISR.


texts:
Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is there some set of items of total weight $w$?" in time $O(1)$ with some kind of precalculation in time $O(n c \log c)$.

I've got a hint - for every $i = 0, 1, 2, \dots, c - 1$ find minimal $x$ such that there is a set of items with total weight $x$ and $x \equiv i \quad (\bmod c)$. How to calculate all $x$'s and how to use them to answer the queries?

This problem is somehow related to graphs and shortest paths, but I don't understand the connection between actual knapsack-like thing and graphs (maybe there is some graph with paths of desired weight?).

Source: problem 76 on neerc.ifmo.ru wiki.


texts: Algorithms which are both deterministic and non-deterministic

texts:
I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms which return deterministic output for certain inputs, but non-deterministic output for other inputs? Say, something along the lines of

$$
s\leftarrow n\in\mathbb{R}\\
\text{if }s\le 5:\text{ return }2\times s\\
\text{else }x\leftarrow\text{generateRandomNumber()};\text{ return }s\times x
$$

This algorithm returns the input, doubled, if the input is less than or equal to five, and otherwise returns it multiplied by a random number (assuming the RNG returns a truly random number and is itself non-deterministic).

So once again, my main question: are algorithms of this nature useful in any practical application? Additionally, what would this class of algorithm be called? Semi-deterministic? Pseudo-deterministic?


texts: How do I select a subset such that the sum and the product are greater than some value?

texts:
I have asked few days ago this question. Now I am simplifying the problem a little bit.

Given two sets $A=\{a_1,\ldots,a_n\}$, and $B=\{b_1,\ldots,b_n\}$ of non-negative integers, a positive integer $k<n$ and a positive integer $\Delta$. The question is: is there a subset of $S$ of $\{1,\ldots,n\}$ of size $|S|\leq k$ such that
$$\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta$$
Say no, if no such subset exists.
Note.$ \Delta$ is greater than $1$ and not big enough.

My question is:

How do I solve this problem? I do not know if this is an NP-complete problem or not. Do you see some hardness or reduction?

My attempt: First I failed to to prove that it is a hard problem. I tried to reduce from PARTITION but no way. I give up and I tried to design an algorithm. Here is my algorithm.

Choose $S=\emptyset$ and $P=0$
Choose the $i$ of the largest sum $a_i+b_i$ and add it to $S$
Let $j$ go from $1$ to $n$ except $i$ do

3.1. Add $j$ to $S$
3.2. Calculate the product above with $S=\{i,j\}$ and store it in $P$

Pick the $j$ with the highest $P$
Re-do this $k$ times.

In this algorithm optimal?

Note: The real question is about the hardness of the problem. Thanks.


texts:
Could anyone suggest other page replacement algorithms that are applicable to the real world aside from

FIFO,
Second Chance (Clock),
Enhanced Second Chance and
Random?


texts:
I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch".

With "from scratch" I mean that it does not use some other undecidable problem to prove some undecidability (which is the usual case), I cannot wrap my mind about how proving undecidability that way (without a previous proof) could be possible.

This question may be inspiring: An example of an easy to understand undecidable problem

Also, I know this is probably not very objective, but it is important to me, it should be something as simple as possible, hopefully enough so that even I can understand it.


texts:
Let $s$ and $t$ be 2 vertices (not adjacent) in graph $G$.
Let $p_l(s,t;G)$ be the $maximum$ number of vertex-independent paths from $s$ to $t$ in graph $G$, of length $\le$ $l$ ($l \in \{1,...,|G|\}$). Also, let $k_l(s,t;G)$ be the $minimum$ cardinal of a set of vertices (different from $s$ and $t$), that if we remove from the graph there won't be any more paths from $s$ to $t$ of length $\le$ $l$.

I) Please prove that $p_l(s,t;G) \le k_l(s,t;G)$ $(*)$
II) Using the below graph prove that the $(*)$ inequality is strict.

III) Find values for $l \in \{2,...|G|\}$ so that $p_l(s,t;G) = k_l(s,t;G)$ for any graph $G$ and vertices $s$ and $t$.

Any ideas?


texts: Is the given language finite or infinite?

texts: I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that basically a language such as $0^*$ is obviously infinite since there can be any nonnegative number of $0$'s. However, is a language such as $(0 \cup 1)((0 \cup 1)^p)((0 \cup 1)^p)(0 \cup 1))$ also infinite? Technically, there can be any number of $0 \cup 1$ as it matters on the $p$ value, but I am also under the impression that there can only be so many values for $p$ and therefore the language is indeed finite. Can anyone explain as to why the language is either finite or infinite? I have read other examples but get a little confused when the language is in the gray area. Thanks!


texts: # of permutations satisfying special inequalties of each element0

texts:
Recently I was solving a counting problem, which needed this subproblem to be solved:

Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations $p_1, p_2, \cdots, p_n$ which satisfy:

for all $1 \le i \le t$, $p_i \le f(i)$, and
for all $t < j \le n$, $p_j \ge f(j)$.

For my problem, $n$ is quite big (about 40, which enabled me to think of meet-in-the-middle), but $t$ is quite small (about 10-15). So I tried to solve the problem with an algorithm regarding $t$, but failed.

I tried to exploit the fact that, if we consider only one of the conditions, the problem becomes super-easy. So I allocated first $t$ elements of the permutation(tried all possible cases), and then calculated # of possible permutations of the remaining $n-t$ elements. This method could give an answer reasonably faster than iterating all possible $n!$ permutations. However it is still really slow, maybe using an $2^n n^2$ dp approach would be faster than this.

I believe that iterating first $t$ elements is not required to solve the problem, but couldn't find any way. Could you please help me solve this problem?


texts: In our university, we were taught that since all 26 letters cant be placed together in a $5*5$ square matrix we must put $i/j$ together like this represented in the below diagram. Here our key is $monarchy$, now what would have happened if the key contained $j$ in itself? say if the key would have been $jargon$ then how do we accommodate the one extra letter which should have been left?


texts: Algorithmic intuition for logarithmic complexity

texts:
I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.

In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of the list.
$\Theta(n)$ is where I'd walk the entire list once, and $\Theta(n^2)$ is walking the list once for each element in the list.

Is there a similarly intuitive way to grasp $\Theta(\log n)$ other than just knowing it lies somewhere between $\mathcal{O}(1)$ and $\Theta(n)$?