texts: Complexity of algorithm inserting an element in a circular linked list at the front end

texts:
In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here)

But in a book currently, I have, it is mentioned that it is done in O(n) (the usual method). I also saw few lecture ppts, they all mention the usual method of traversing the list & adding an element.

My question is :

In practical scenarios which method is used ?
I am about to attend an exam, which consists of MCQs, if above question is asked shall I mark O(n), since that is the standard answer ?


texts: Expressing iterative version of fold in terms of recursive version

texts:
1st Definition. Recursive definition of fold

fold$_{recur}$ (c,h) nil = c

fold$_{recur}$ (c,h) (cons(a, x)) = h(a, fold$_{recur}$ (c,h) x)

2nd definition of fold. Iterative definition

fold$_{itr}$ (c, h) nil = c

fold$_{itr}$ (c, h) (cons (a, x) ) = fold$_{itr}$ (h (c, a), h) x

How do I express fold$_{itr}$ in terms of fold$_{recur}$.


texts: Why is the dynamic programming algorithm of the knapsack problem not polynomial?

texts:
The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?


texts: Proving NP-completeness of a surveilled graph problem

texts:
So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a function.

We can call this graph instance $\textit{consistent}$ if we can find a subset $B \subseteq V$ \ $A$ such that for any $u \in A$, $ g(u) = |N(u)\cap B|$ (in which $N(u)$ obviously denotes the neighbourhood of vertex $u$).

How would one go about proving that the problem of determining consistency of a graph $(V,E,A,g)$ is NP-complete? Would a reduction from SUBSET-SUM using slack variables of some type work?

Thanks!


texts: What does "order of growth decreases exponentially" mean?

texts:
I understand than function decreases exponentially, then order of growth of this function is exponential with negative exponent. But what does it mean that order of growth decreases exponentially?

I don't understand what should i look for in this exercise:

  Exercise 2.33 Find a recurrence describing a sequence for which the order of growth decreases exponentially for odd-numbered terms, but increases exponentially for even-numbered terms.

Could you provide several first items of such a sequence to let me understand the exercise?


texts: I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete.


texts: Efficiently shuffling items in $N$ buckets using $O(N)$ space

texts:
I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows:

We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a unique item $a_i$ and a count $k_i$. Altogether, the collection holds $T=\sum_1^N{k_i}$ items. This is a more compact representation of a vector of $T$ items where each $a_i$ is repeated $k_i$ times.
We want to output a shuffled list of the $T$ items, all permutations equally probable, using only $O(N)$ space and minimal time complexity. (Assume a perfect RNG.)
$N$ is fairly large and $T$ is much larger; 5,000 and 5,000,000 in the problem that led me to this investigation.

(EDIT: further research instigated by @YuvalFilmus’s comment shows that this is equivalent to weighted sampling without replacement, a search term that leads to quite a lot of research.)

Now clearly the time complexity is at least $O(T)$ since we have to output that many items. But how closely can we approach that lower bound? Some algorithms:

Algorithm 1: Expand the buckets into a vector of $T$ items and use Fisher-Yates. This uses $O(T)$ time, but also $O(T)$ space, which we want to avoid.
Algorithm 2: For each step, choose a random number $R$ from $[0,T-1]$. Traverse the buckets, subtracting $k_i$ from $R$ each time, until $R<0$; then output $i$ and decrement $k_i$ and $T$. This seems correct and does not use extra space. However, it takes $O(NT)$ time, which is quite slow when $N$ is large.
Algorithm 3: Convert the vector of buckets into a balanced binary tree with buckets at the leaf nodes; the depth should be close to $\log_2{N}$. Each node stores the total count of all the buckets under it. To shuffle, choose a random number $R$ from $[0,T-1]$, then descend into the tree accordingly, decrementing each node count as we go; when descending to the right, reduce $R$ by the left count. When we reach a leaf node, output its value. It uses $O(N)$ space and $O(T\log{N})$ time.
Algorithm 3a: Same as Algorithm 3, but with a Huffman tree; this should be faster if the $k_i$ values vary widely, since the most often visited nodes will be closer to the root. The performance is more difficult to assess, but looks like it would vary from $O(T)$ to $O(T\log{N})$ depending on the distribution of $k_i$.

Algorithm 3 is the best I’ve come up with. Here are some illustrations to clarify it:

Does anyone know of a more efficient algorithm? I tried searching with various terms but could not find any discussion of this particular task.


texts: Searching for points near given point in a multidimensional space

texts:
I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space.
When I have a 1D case I sort it first.
For 2D I can make boxes big enough to be not wasted on boxes containing no elements, these boxes have subboxes and these have elements.

There is a problem: because when the width is 100, then if I'm looking for a 401 I can find a 490 and I can't find a close element 399.
You would have to look in the boxes around, in 9 instead of in one. It's still possible, but for 3D it will be 27, generally 3^n, what if we have 512D?


texts: Is CS more like software and CE more like hardware?

texts: At my university, a degree is "Computer Science and Engineering" but at US universities I understand that the degrees are different so what is the fundamental difference? Is computer engineering lower level like hardware and operating systems while computer science is more like language technologies?


texts: Divide and Conquer majority element algorithm

texts:
The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

def findMajority(arr):
    if len(arr) == 1:
        return [arr[0], 1]
    else:
        leftHalf = findMajority(arr[:len(arr)/2])
        rightHalf = findMajority(arr[len(arr)/2:])

        if leftHalf[0] is None and rightHalf[0] is not None: #Left half is indeterminate
            return [rightHalf[0], rightHalf[1]]

        if leftHalf[0] is not None and rightHalf[0] is None: #Right half is indeterminate
            return [leftHalf[0], leftHalf[1]]

        if leftHalf[0] is None and rightHalf[0] is None: #Both halves are indeterminate
            return [None, 0]

        if leftHalf[0] == rightHalf[0]: #Majority in both halves is the same
            return [leftHalf[0], leftHalf[1] + rightHalf[1]]

        elif leftHalf[1] < rightHalf[1]: #Right majority has more occurrences
            return [rightHalf[0], rightHalf[1]]

        elif leftHalf[1] > rightHalf[1]: #Left majority has more occurrences
            return [leftHalf[0], leftHalf[1]]

        else: #There is no winner between the two halves and they have equal occurrences
            return [None, 0]

EDIT: It returns the wrong answer for [2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0]
. So it doesn't work.


texts: Integer factorization: comparing with floor

texts:
While working on integer factorization algorithm I came to the next problem:

$$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$

$a$ the number I want to factor
$x$ factor of $a$
$e$ positive integer that I choose

For $e = 1$ I found a linear representation for short sequences of $\lfloor{\frac{a}{x}\rfloor}$, this allows me to compare it to $\frac{a}{x}$ and find the value of $x$. The problem is that there are to many sequences, for this to be efficient. So I decrease their amount by using $e > 1$. Unfortunately it created $c$, and now I have to test all its possible values, it looks some thing like this:

for $e=2$, $c$ can be $\frac{1}{2}$
for $e=3$, $c$ can be $\frac{1}{3}$ or $\frac{2}{3}$
for $e=4$, $c$ can be $\frac{1}{4}$ or $\frac{2}{4}$ or $\frac{3}{4}$

Is there any way that I can predict the values of $c$, or give it a better estimation?


texts:
Let's say I have three functions and each gives true/false answers. The first one gives 2 booleans, the second 6 and third 4. Are they written like this: 01 110010 1000? Do they get spaces between the functions? If so, do the spaces count as data? What I wanna know is, if you send an encryption key using RSA, how does RSA recognize the length of your key with the spaces? Another way to put it is if a symmetric key has 256 functions of one bit each (0 1 1 0 0 1 0, etc.) would it end up being 512 bits long because of the spaces?

I'm new in computer science and I'm learning for fun by myself. I apologize if my question is the smh type.


texts: Hungarian algorithm to search over all matching?

texts:
I am working on the following problem-

"Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching."

Please note that I like to search over all possible matching (that includes maximum matching and other matchings as well). As per my knowledge, Hungarian algorithm searches over all possible maximum matching (and not among all matching). Please let me know if I can use the Hungarian algorithm to solve this problem.


texts:
Assume that we have some efficient way of creating a suffix tree of a string. Then I'm interested in efficient ways of finding:

  Length of longest repeated substring. Given some string $S$, then a repeated substring is a substring $R$ of $S$ that occurs more than once in $S$. Then I wish to find the length of the longest repeated substring.

Example. Consider the string yabbadabbado, then the substring abbad occurs twice and is the longest repeated substring, so the answer would be $5$.

I'm also interested in the similar problem by shared substring of two strings.

  Length of longest common substring. Given strings $S_1$ and $S_2$ then a substring is a common substring if it is a substring of both $S_1$ and $S_2$. I wish to find the length of the longest common substring.

Example. Given strings oompaloompa and boom have longest common substring of oom and hence the answer would be $3$.

How can these be found efficiently?


texts: How to avoid getting stuck on local optimum, for genetic algorithms

texts:
I'm programming a genetic algorithm using grammatical evolution. My problem is that I reach local optimal values (premature convergence) and when that happens, I don't know what to do. I'm thinking about increasing the mutation ratio (5% is it's default value), but I don't know how to decide when it is necessary.

The data I have on every generation is a bidimensional array whose first column is its fitness

adn[i][0] ← fitness
row → is the values of the Grammar
column ↓ Each indiviual result

If you need clarification, please ask and I'll be pleased of modifying. Note that this is not my mother language and sorry for the mistakes and for the inconvenience.

Answering a request, my operations are the following, and exactly in this order:

I generate a random Population (A matrix with random numbers)
I generate a matrix that contains the desired result. For doing this, i have implemented a couple functions that have aditionally a +-5% of variation, for example: fun(x)= (2*cos(x) + sen(x) - 2X) * (0,95+(a number oscillating between 0 and 0,1), the x contains every f(x) with sequentially from 0 to N (Being N the size of row), the y contains exactly the same (more results)
Starts algorithm (generations beginning to change

The actions that make every generation are:

Mutation: A random number of every cromosome can mutate on any gene → adn[i][random] = random number (with a 5% of probability of this happening)
Crossover: I cross every adn with other adn (80% is the chance of mutation for every pair), for the pairing I pick a random number and face adn[i] and adn[(i+j) mod NumADNs]
Translate. I get a matrix that contains the values f(0 to N) making in one step transcription and translate aplying the grammar on the image

-fitness: I compare the values obtained with the expected ones and update the fitness.

-Elitism: After that, i choose the best 4 adn's and get it to the top, they will be selected

-Selection: Any non elitist adn will face a totally random adn, and if its fitness is lower (Lower is better) will prevail, being a possibilities of the worse one surviving


texts: Which of the following languages is accepted by this Pushdown Automaton?

texts: This is a question from a past paper. I am struggling to get my head around the concept of a PDA. I understand that it is a Finite Automaton with a stack but am stuck as far as answering questions like this one. Thanks.


texts: Inclusion of points in rectangles using a sweepline algorithm

texts:
Given is a set of points $P_{1},....,P_{n}$ with $P_{i} = (x_{i},y_{i})$. No two points have the same x and y coordinates. Given is also a set of m axis-parallel rechtangles $R_{1},...,R_{m}$ in a plane, described by their bottom left corner $(l_{j},b_{j})$ and upper right corner $(r_{j},u_{j})$. No two rechtangles intersect or overlay each other and no point is on the border of a rechtangle.

We need to describe a sweepline algorithm which can output all the points which are not in a rechtangle.

I proceeded like so:

The sweepline is a vertical line going from left to right and stopping and evaluating at each event point. Out event points are the points $P$ and also the $(l,b),(r,u)$ of each rechtangle. We sort all the event points according to their x-coordinate.

We use an AVL-Tree to save the y-coordinates of the lower left corner of a rechtangle and remove it once we reach it's upper right corner. When we reach a point $p$, we will simply evaluate if p is within the borders of a currently active rechtangle by checking if $y_{p} \in [b,u]$ of active rechtangle. If so we mark it as false and proceed.

The solutions are that we are given more complicated and I don't understand them fully. I also don't know if my solution would work and why. It seems to be plausible to me.

They also save at each node of the AVL, the size of its subtrees so they can see how many points smaller than a node there are. Then while evaluating a point $p$, they search for p in the AVL tree and determine $A$ the number of keys smaller than $p$. Then it says that if $A$ is an even number, then the point is not in a rechtangle. Done.

I don't understand how this works. please help.

Thank you very much


texts: DFA for exactly two of a and one or more of b

texts:
I'm totally new to DFA's and automaton in general -- this is the first week or two of class that I've actually seen this -- and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet {a, b} that have at least one b and exactly 2 a's"

I've tried to construct a DFA to represent this structure, but I have no idea how to form a structure to count for something and match for one.

Can someone help?

Okay, so. Here's what I got and I think it's the right answer.


texts: How to explain rehosting and retargeting with T-diagrams?

texts:
I'm currently learning for an exam about compilers and found the following question:

  (3 p.) Bootstrapping: Explain the concepts of rehosting and retargeting. Use T-diagrams.

As far as I understand, rehosting means to compile a compiler for another platform (host), so it should look like this:

-------------
| a       b |     --------------
-----   -----     | a        b |
    | c |-------------    ------
    -----| c       x || x |
         -----   ----------
             | ? |
             -----

Is this correct? And what does retargeting mean?


texts:
I have a data-set which contains more than two arrays. I would like to sort the data-set with out merging the arrays to a single array.

Arrays may or may not be in same machine. I am looking for an efficient way to sort the data.


texts: Time spent on requirement and its effect on project success and development time

texts: Is there any evidence suggesting that time spent on writing up, or thinking about the requirements will have any effect on the development time? Study done by Standish (1995) suggests that incomplete requirements partially (13.1%) contributed to the failure of the projects. Are there any studies done which show that time spent on requirement analysis will have any effect on development time of a project, or how successful the project will be.


texts: Cellular automata for 2d cloud simulation

texts:
I want to build a cellular automata that simulates a behaviour that looks like clouds, that is: infinite and random cycles, pieces can gather or break apart, just like the image below:

My question is: Is there any algorithm whose result looks like this cycle (or anything that can help me)?

I've been searching for a long time throught articles, scientific papers, epidemic algorithms, Conway's Game of Life similars, but still no result.


texts:
I believe that in the general case stable matching for 3 members rather than 2 is NP-Complete, but I wonder if in my case there's something that I am missing that could have reasonable time complexity.

The specific purpose of the program I am trying to write is to take an arbitrary number of objects and split them into groups of 3. Hypothetically, each object has a color (let's say right now there's 10 possible colors).

The part of this group creation that allows something of a "preference list" of other members is both having group members of different colors and having been grouped with them in the past as little times as possible.

Everything I have come up with either has horrendous time complexity or has the chance of failing (missing possible groupings). If anyone has done anything like this before I would appreciate any suggestions.


texts: How does the ID3 Algorithm differ from a generic Decision Tree learning algorithm

texts:
Based on the notes of my Machine Learning lecturer, I am struggling to understand how the two algorithms differ? Both seem to select the most informative feature A (based on least entropy), then create subsets of the example set for each value of A. Then create a new branch on the tree by recursively calling ID3 on each subset.
Could someone please explain how they differ?


texts: OS: Are User-level threads and software threads (and also kernel-level threads and hardware threads) the same?

texts:
I am referencing the Book Fundamentals of Computer Algorithms" by Ellis Horowitz et al.
At the part which they talk about multi-threading models, user-level and kernel-level thread are introduced.
And at the scheduling chapter, under multi-core processors, they talk about software threads and hardware threads.
Even though both sections are titled 'multithreading', one deals with how user-threads are mapped to kernel threads and the other deals with hyperthreading. (correct me if I am wrong)
I just want to know whether they are talking about the same terms. If not, will you clarify what is the difference between User-level threads  vs software threads?
Thank you.


texts: LSTM : What should I do if I am always getting an output too close to one value?

texts:
I am training a model for ham and spam classification using LSTM. I am indicating the spams as 0, and the hams as 1. However, the dataset has much more hams than spams, so I tend to get an output very close to 1. That means the output is almost always above 0.5. So I have two questions about this :
Q1. Should I rate my answers based on the ratio between ham and spam in the dataset?
(etc. If there are 4000 ham and 1000 spam, then should I count an output higher than 0.8 as ham and lower than 0.8 as spam?)
Q2. If this is not a legitimate way, do you have any solutions for my problem?


texts: Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and every segment is an edge in the tree.


texts: Why is TIME(n log (log n)) \ TIME(n) = ∅?

texts:
In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be the empty set. Can anyone show me why this is?

both $TIME(n\log(\log n))$ and $TIME(n)$ are regular. I think that only means we can subtract the two sets and the result will still be regular. I just dont understand how its possible to subtract the collection of $O(n\log(\log n))$ time TM decidable languages from the collection of $O(n)$ time TM decidable languages and get the empty set. These two collections are not equal so I feel like there will be something left over


texts: What is the time complexity of text justification algo?

texts:
The following algo is a simplified version of a text justification algo taken from dynamic programming lecture notes of MIT OCW.

I am confused why this particular algo has a time complexity of $\mathcal{O}(n^2)$ and not of $\mathcal{O}(n!)$ -:

function foo(int index) {
//some constant time operation like 2+2
       for( i = index + 1 to end ) {
           foo(i);
           }
}

Lets say end is 10.

So if foo(0) were called, the sequence of function calls would be something like this (correct me if I am wrong)-:

foo(0) = 9 calls to foo using (1 to 9)
Each foo(1) = 8 calls to foo using (2 to 9)
Each foo(2) = 7 calls to foo using (3 to 9)
and so on...

So it is $n * (n-1) * (n-2) ... * 1$ = $n!$

So shouldn't the time complexity be $\mathcal{O}(n!)$ ? Instead I find that in most cases this algorithm is represented as $\mathcal{O}(n^2)$.

Why is that ?

The original version was of the follwing form-:

DP[i] = min{DP[j] + badness(i,j), for (j in range(i+1,n+1))}

Where badness = (page width - total width of string) ^ 3


texts:
For testing automated theorem provers we have Seventy-Five Problems for Testing
Automatic Theorem Provers by Pelletier.

Are there any such standard/well regarded tests for a λ-calculus that verify the evaluation?

EDIT

The best λ-Calculus evaluator I have found so far is:

Lambda calculus reduction workbench with info here.

I like this one because
1. It is a working example that seems to corretly pass every example I can find.
2. Has a trace option for the output.
3. Can do multiple reduction strategies
    * normal order
    * call-by-name
    * head spine reduction
    * call-by-value
    * applicative order
    * hybrid normal order
    * hybrid applicative order
4. Has a list of pre defined abbreavtions such as
    * S, K, I
    * 0 - 5
    * pair
    * pred
    * succ
    * add
    * mul
5. Has source code in SML


texts: Lower Bound for Time Complexity of Pairing Problem

texts:
Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, the second smallest in X matched with second smallest in Y and so on. i.e the algorithm will yield the pairs: $(x_{1},y_{1}),...,(x_{i},y_{i}),...,(x_{n},y_{n})$, $x_{i}$ being the i'th smallest element in X.
I need to find the lower bound for the time complexity of the problem.

I think the lower bound is O(n) because when the two arrays are sorted we only need to match the elements with the same index in each array - so we'll need to go over n indices = O(n). But this just proves the existence of the possible time complexity of O(n) and doesn't prove it's the minimum.

Is O(n) the lower bound? And if so what is the proof?


texts: Can we improve internet speed by serializing timestamps?

texts: If we (scientists) came up with a way of representing numerical timestamps as letters hence reducing the number of bytes needed to represent timestamps, would that mean an improvement in internet speed as less data needs to be serialized?


texts: Is there a program to solve a metric TSP for 80 edges at optimum?

texts:
i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.

But when i'm finished, i'd like to check my solution but i don't know how. So i thought about using a computer-program to find the optimal solution to see, if my solution is within the 3/2-range.

i am not quite sure, if this is really possible or how long it might take. if it would take less than a month, i think, it would be worth a try.


texts: Given a solution for the post correspondence problem, is it co-semidecidable if the solution is a palindrom?

texts:
This was an old exam question. I think, though, that it is some sort of trick question. Isn't this simply decidable and therefore also trivially co-semidecidable?

Because I wouldn't know how to prove that it is co-semidecidable for itself. Being co-semidecidable means that there is a chance that the algorithm (that checks whether it is a palindrome or not) never stops, even if the solution is a palindrome indeed. But I don't see why this should be the case. An algorithm should always be able to check the condition and give a clear answer, right?


texts: Why does appending permutations of servers at the end of hash table avoid bottlenecks?

texts:
I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

The paper has a TLT (tract locator table) for identifying where to write in each server. The table is basically a hash table where the index i maps to some (tract) server to do writes to or reads to.

Say that there are n (tract) servers. It says that if instead of just having index i mapping to server i, if instead we appended n more indexes mapping to some permutation of the servers (and having a table of size 2n in this example), we can avoid having a bottleneck at any specific server when doing reads or writes. Basically it claims that as we append more permutations the better. Why is this?

Why would this be?

Just for reference the index mapping function is:

$$i = (hash(g) + t) \pmod n$$

where:

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin


texts: Is there a broader class of total functions than $PR$?

texts:
In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann function and others aren't part of $PR$. Is there a well-defined class of total functions which is broader than $PR$?

Bonus question:
I heard lately about Walther and substructural recursion, but I can't find any information whether they are just another definition of $PR$ or different classes of total functions. Could you please clarify? Also a little example on how the definition differ from $PR$ would be great.


texts: Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)?

texts:
Acyclic DFAs recognize finite languages. For more info, see this Wikipedia page : https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

To explain that the product of two DFAs $A$ and $B$ could lead to a result of size $O(|A|.|B|)$ in the worst case, most examples make use of DFAs containing cycles (those cycles are responsible in creating |A| copies of B in the result) like in this example :

As they are much more simpler than standard DFAs, I am wondering if the product operation (and more specifically union/intersection operations) of two acyclic DFAs $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

According to the article "State Complexity of Union and Intersection of
Finite Languages" here :
http://toc.yonsei.ac.kr/~emmous/papers/dlt07.pdf
the authors say that the size of the DFA resulting from the product of two acyclic DFAs $A$ and $B$ remains in $O(|A|.|B|)$ only if the alphabet used is of variable size that depends on the size of the input DFAs. Thus, they conclude that this upper bound is $unreachable$ if the alphabet is of fixed size.

Does it mean that given a fixed size alphabet (e.g. $\sum=\{a,b\}$) and two DFAs $A$ and $B$ defined on $\sum$ , there is still the possibility that the intersection of $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

I would appreciate any counter-example, proof or reference to a paper dealing with this problem.

Many thanks, Luz.


texts: Is the complement of every non Turing recognizable language a Turing recognizable language?

texts:
One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable.

What about the complement of non Turing recognizable language? Is the complement of every non r.e a recognizable language.

I don't know how to approach this problem.

But one idea I had was this:

If the complement of every non r.e were a r.e language then there would be a bijection from r.e to non r.e. This bijection maps a r.e to a non r.e . The set of r.e languages is countable(even though infinite). If a bijection exists then non r.e would also be countable. But the union of r.e and non r.e is uncountable. This means one of them must be uncountable. So the original supposition must be wrong.

I am new to coutability and such things. So it may be possible that the idea is compeletely wrong.

Anyhow can someone provide an approach to this problem.


texts: Mimimum spanning tree with a constraint on number of certain types of edges

texts:
I have the the following problem.

Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning tree such that we minimize total weight but also we can only use a maximum of $c$ edges in $B$.

I feel like this is just Prim/Kruskal with an additional condition in the main if condition, but is that correct? I think we can still use a greedy algorithm but do not know how to show correctness.


texts:
In a previous question there was a definition of weight-balanced and a question regarding red-black trees.

This question is to ask the similar question, but for treaps.

The question is:

  Is there some $ \mu > 0 $ such that the expectation of $ \frac{|N_L| + 1}{|N| + 1} $ not less than $ \mu $ and not greater than $ 1 - \mu $ in treaps that the number of nodes is big enough?

Sorry for my poor English.


texts: Comparison of running times: Determine largest n to run in given time

texts:
I am browsing the "Introduction to Algorithms" book by Thomas H. Cormen. One of the very first tasks in the introduction chapter gives a couple of running time functions like

f(n)=lg n
f(n)=n!
f(n)=2^n

and the following durations: 1second, 1minute, 1hour, 1 day, 1month, 1year, 1century

The f(n) functions describe the time taken in microseconds and for each duration I should determine the largest n which still runs in the given time.

Quite easy for potency and faculty, but I am stuck at the logarithm (lg n). Even for one second n gets so sooo huge and later even wolframalpha does not calculate it for 1 day. It is just too huge.

Or ist it wrong to try to calcualte these equations?

1.000.000 = lg n [for 1 second]
60.000.000 = lg n [for 1 minute]

...


texts:
I'm looking for a type inference algorithm for a language I'm developing, but I couldn't find one that suits my needs because they usually are either:

à la Haskell, with polymorphism but no ad-hoc overloading
à la C++ (auto) in which you have ad-hoc overloading but functions are monomorphic

In particular my type system is (simplifying) (I'm using Haskellish syntax but this is language agnostic):

data Type = Int | Double | Matrix Type | Function Type Type

And I've got an operator * which has got quite some overloads:

Int -> Int -> Int
(Function Int Int) -> Int -> Int
Int -> (Function Int Int) -> (Function Int Int)
(Function Int Int) -> (Function Int Int) -> (Function Int Int)
Int -> Matrix Int -> Matrix Int
Matrix Int -> Matrix Int -> Matrix Int
(Function (Matrix Int) (Matrix Int)) -> Matrix Int -> Matrix Int

Etc...

And I want to infer possible types for

(2*(x => 2*x))*6
(2*(x => 2*x))*{{1,2},{3,4}}

The first is Int, the second Matrix Int.

Example (that doesn't work):

{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
  FunctionalDependencies, FlexibleContexts,
  FlexibleInstances, UndecidableInstances #-}

import qualified Prelude
import Prelude hiding ((+), (*))
import qualified Prelude

newtype WInt = WInt { unwrap :: Int }

liftW f a b = WInt $ f (unwrap a) (unwrap b)

class Times a b c | a b -> c where
(*) :: a -> b -> c

instance Times WInt WInt WInt where
(*) = liftW (Prelude.*)

instance (Times a b c) => Times a (r -> b) (r -> c) where
x * g = \v -> x * g v

instance Times (a -> b) a b where
f * y = f y

two = WInt 2
six = WInt 6

test :: WInt
test = (two*(\x -> two*x))*six

main = undefined


texts:
Relation of Entropy and SNR : Based on this question and answer, I had another question that struck me and I am curious to know, if somebody can shed some light, on the following situation: $y= desired_{signal} + noise$ is transmitted where $noise$ is an Additive White Gaussian Noise. $y(t)$ is received by the receiver and the $error = y - \hat{y}$ where $\hat{y}$ is simulated at the receiver by using guessed parameters with the knowledge of the kind of model used at the transmitter.

For increasing SNR (attenuating noise) would Entropy of error decrease? In the link provided, the entropy of the transmitted signal decreases with increasing SNR since the uncertainty decreases when noise is getting attenuated. But what about the entropy of error? Should error entropy increase with increasing SNR? I am confused about this.

EDIT: The way I calculated entropy of error:
Let the system model be AR(2): $y(t)= a1y(t-1) + b1y(t-2) + noise$. At the receiver end, I have $z(t) = y(t) - (a2y(t-1) + b2y(t-2))$ where $(a2,b2)$ are close guesses to ($a1,b1$). I calculated 2 entropies: $Entropy[y(t)]$  and $Entropy[z(t)]$.

z(t) will be close to zero when $a2,b2$ will be equal to $a1,b1$ in which case entropy of z(t) is found to be minimum among all different z(t) for a particular SNR value of noise.
 So, for a particular noise value, I have 10 pairs of (a2,b2) and for each I get 10 values of $Entropy[z]$. I chose the minimum among all $Entropy[z]$ for a particular SNR level. But, for different noise levels, as I increase the SNR at the transmitter end, the minimum entropy, $\min Entropy[z(t)]$, increases with increasing SNR.
While, I found that $Entropy[y]$ decreases with increasing SNR.
What should be the correct trend and why?


texts: Algorithm for determining whether 2 entities of some feature are the same?

texts: I'm trying to think of a way to do approximate joins between 2 rows in a data table. Like for example lets say I have a row where the person name is "John Doe" but then another data table uses a different person format like "Doe, John." Now suppose I can put them both to a standard format say "John Doe." Sweet so I have a way to reference them and let's say there's other data correlated with "John Doe" is there any algorithms out there to infer whether these 2 John Does are the same given the other data columns? You can see the other data columns as features as well, because I know FB has an algorithm to stop duplicates for the same person and StackOverflow will merge accounts if it thinks they're being used by the same person. Any suggestions?


texts:
If i take a safety property $SP$ and a liveness property $LP$, is it true that the result of their intersection is a safety property (and not a liveness property) ? Why ?

Thanks


texts:
Will it be wrong to use g for reducing (λx.λy.x) first in step (2) instead of using to reduce λg?

Is there a rule against it?


texts: Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

texts:
I'm trying to prove that the following languague is a regular language:
$L=\{ w \mid \lvert w \rvert$ is prime $\}$*
What I have thought is to divide each word $w \in L$ into subwords of length 2 if the word is even and and if the word is odd end with a suffix of length 3, in this way I would get the following regular expression:
(aa + ab + ba + bb)* (aaa + aba + abb + aab + baa + bab + bba + bbb + $\epsilon$)
Is my reasoning correct?
Otherwise I would appreciate so much any help.


texts: Literature on recusively applying predicated transformations to a symbol tree to match some target symbol tree

texts:
I am working on a problem that can be simplified to consist of the following:

an initial symbol tree
a list of interpretations (an interpretation is a transformation guarded by a predicate)
a predicate describing what the target symbol tree should look like

Where the goal is to find a path from the initial symbol tree to some symbol tree that matches the predicate of the target symbol tree via the given list of interpretations.

To complicate matters, a transformation can be from a symbol tree to symbol tree, but it might also transform a symbol tree to a new interpretation, which will then be added to the list of available interpretations. Also, predicates and transformations can have access to extra information such as the context and in turn can also request to try and interpret a symbol a certain way (i.e. the interpretation process is recursive).

If implemented naively, this can get computationally expensive really fast, so several optimizations are added to make it more feasible to compute, e.g. requiring transformations to be transparant about on what kind of symbols they will work, so transformations can be ruled out as soon as possible.

The problem described above, seems to me common enough, so I assume there is some existing body of literature that has researched this problem. I tried searching for it, but I have only found literature about very specialized versions of this problem that e.g. only allow certain builtin predicates and where the transformation was not a function, but was a direct mapping to some other symbol tree.

It might be that I just have not yet found the right terminology or that my current approach is considered to be to general, such that people already ruled it out as infeasible, and thus has not received any real attention in literature.

Does anyone know of any literature about the problem I described above? It would be helpful to see what other people have done in this problem domain, to e.g see other approaches, problems and solutions I might have overlooked so far.


texts: Why are not all recursive languages undecidable?

texts:
I learned that recursive language are  decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.

If a language is an REL (recursive enumerable language), I know that there exists a TM (Turing machine) that accepts it (regardless of the TM halting or not). Say, however, that for a language $L$ you have found a TM which accepts it, thus indicating $L$ is REL. We know that, given a TM, it is undecidable whether the TM halts or not. Thus, it is not possible to deduce whether $L$ is recursive or not: we have a TM that accepts $L$, but whether the TM halts or not is undecidable and, thus, we cannot comment on whether $L$ is recursive or not; this makes telling whether $L$ is recursive or not undecidable. Hence, recursive languages should be undecidable―which they are not!

What is wrong with the above reasoning?


texts: Prove that regular languages are closed under Kleene star

texts:
Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too?
I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original initial state, and also connected all the final states to the original initial state with an $\epsilon$-transition.

How can I formally prove that this is correct?


texts:
This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++".

Until recently I thought Lua was an example of a language which could be described by a deterministic context-free grammar. This belief was reinforced by looking at The Complete Syntax of Lua as described in the language reference. Unfortunately it turns out that this grammar has a well-known ("function call x new statement") ambiguity, and that Lua must be parsed using a "greedy" algorithm, not a deterministic one.

Which programming languages have a syntax that can be described by deterministic context-free grammars?


texts: Environment requirement in training image dataset for classifier

texts:
I have a question about preparing the dataset of positive samples for a cascaded classifier that will be used for object detection.

As positive samples, I have been given 3 sets of images:

a set of colored images in full size (about 1200x600) with a white background and with the object displayed at a different angles in each image
another set with the same images in grayscale and with a white background, scaled down to the detection window size (60x60)
another set with the same images in grayscale and with a black background, scaled down to the detection window size (60x60)

My question is that in Set 1, should the background really be white? Should it not instead be an environment that the object is likely to be found in in the testing dataset? Or should I have a fourth set where the images are in their natural environments? How does environment figure into the training samples?


texts: Correctness proof of greedy algorithm for 0-1 knapsack problem

texts:
We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.


texts: What should we return when pattern matching on a Path constructor?

texts:
Context: Cubical Type Theory

Consider a simple HIT, say, an HitInt:

data HitInt : Set where
  pos : (n : ℕ) → HitInt
  neg : (n : ℕ) → HitInt
  posneg : pos 0 ≡ neg 0

Or, if you don't speak Agda we can use cubicaltt:

data int = pos (n : nat)
         | neg (n : nat)
         | zeroP <i> [ (i = 0) -> pos zero
                     , (i = 1) -> neg zero ]

We want to define, for instance, a succ operation for it. As a functional programmer, we want to pattern matching on this HIT. In Agda, it's:

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (neg zero) = pos 1
sucHitInt (neg (suc n)) = neg n
sucHitInt (posneg x) = pos 1

Or in cubicaltt:

sucInt : int -> int = split
  pos n -> pos (suc n)
  neg n -> sucNat n
    where sucNat : nat -> int = split
            zero -> pos one
            suc n -> neg n
  zeroP @ i -> pos one

What I'm interested in is the last case-split of these two pattern matchings. The function is supposed to return the successor of the input integer, but we need to implement something that "finds the successor of the input Path".

My question is, how are we supposed to implement this case-split? In the cubicaltt version (taken from the cubicaltt's GitHub repository, examples/integer.ctt), it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer. Is this really what we want to do? Why it's not returning a Path like <i> pos 1 (even this is not a member of the higher inductive family)?

What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.


texts: Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?


texts: Understanding Correctness of Bidirectional Dijkstra

texts:
I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10:

https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

For a contradiction, they consider an $s-t$ path $p$ that is shorter than the minimum sum $\mu$ of tentative distances from the forward and backward search.
The next step I don't understand: there is an edge $(v,w)$ on this path, such that:

$dist(s,v) < top_f$
$dist(w,t) < top_b$

Where do these relationships come from?

From what I see, after stopping, it holds that $\mu \leq top_f + top_b$.

So if we consider any edge $(v,w)$ of $p$, we have that

$dist(s,v) + length(v,w) + dist(w,t) < top_f + top_b$

We can leave out that edge to get the inequality

$dist(s,v) + dist(w,t) < top_f + top_b$

But from this, I can't derive these two relationships.

I appreciate any help! Thanks!


texts: Algorithm to schedule employees into days

texts:
I'm trying to build a scheduling app for a friend, but am stuck on how to sort the employees.
I have three holidays each with their own employee_need:
thanks_giving: 2
christmas: 3
new_years_eve: 2
I have employees who have a predetermined number of days they will work. The sum of the employee’s predetermined work days will always add up to the sum of the three holiday’s employee_need. They also have ranked the holidays by preference, which should guide the scheduling process.
The data looks something like this:
Polly:
days_to_work: 1
preferences: [christmas, new_years_eve, thanks_giving]
Stan:
days_to_work: 2
preferences: [thanks_giving, christmas, new_years_eve]
etcetera.
Right now my process of sorting is to

Fill each holiday with a list of all employees.

Loop through the employees, starting with those who have the most days off.

Loop through the employee's preferences and pull them from the one they most desire to have off that also has room for them to be taken off

Continue looping until the days are properly scheduled.  If there is room to remove them from that day, I do so, until they are working the number of days they are supposed to.

The algorithm works a decent amount of time, but I really need it to work all the time.
Is anyone familiar with this kind of problem, and can point me toward a better methodology?


texts: Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$

texts:
The full question is: Construct a Turing machine that recognizes the set $\{0^{2n}1^n \mid n\geq 0\}$.  The Turing machine starts with the input on the tape and the head over the leftmost symbol of the input.  The symbols to the left of the input are blanks out to infinity, as are the symbols to the right of the input.  If the string is accepted, the machine should halt with 1 on the tape (the rest of the tape should be blank).  If the string is rejected, the machine should halt with 0 on the tape.

Yes, this is a homework question, but I think I just need some help understanding the problem. We have not gone very in depth into Turing Machines, and he suggested we should just write the answer graphically like a  Deterministic Finite State Machine with read, write, and direction in the transitions.

I am getting stuck because I can only think about it in terms of 3 different paths (being 001, 100, 010), but I know this is most likely not correct, and I do not know how to recognize if the string is not in the set. I understand that the machine know the string has ended when it reads a blank, and then it will move right one and write either a 1 or 0 depending on if the string is accepted or not, but I can only think about it as 3 different paths.

Help would be appreciated! Thanks!


texts: Term for binary search tree using hashes?

texts:
I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, foo2... so tree balance is an issue.

I considered balancing and auto-balancing algorithms, but then I realized that the hash for a key given a good hash function should have a 50% average chance for left/right. And I already had a hash function so that meant no additional code. So I would get a balanced tree for free(edit: at no point did I want to imply a perfectly balanced tree, this is emergent behavior).

I wanted to check if my theory was correct. When I search for BSTs, hashes, and hash trees, however, no relevant information turns up.

What is the term for a binary search tree that balances itself by using a hash?

edit:
I am going to accept the answer because if something doesn't have a name it just doesn't, but I tested this because some comments and asides imply that it is worse than it actually is.

I tested a sorted list of 468685 words containing both English words and "elite" password cracking words.

balanced-tree:    worst(19)     average(18.84)
edlin-tree:       worst(47)     average(22.72)
edlin-tree(SHA2): worst(46)     average(23.25)
regular BST:      worst(468685) average(234342.50)

So it's not going to replace your language library algorithms but, as stated in the accepted answer, it is obviously logarithmic.

As for the hash function(Which for reference is add+xorshift as in:

do{h+=*s;h^=h<<left1;h^=h>>right;h^=h<<left2;}while(*s);

), I have also tested how bad it is by comparing collisions to the expected value.

8 bits:
   expected :  468428.99
   axs      :  468429
   SHA2-256 :  468429

16 bits:
   expected :  403200.35
   axs      :  403189
   SHA2-256 :  403198

24 bits:
   expected :    6485.99
   axs      :    6451
   SHA2-256 :    6433

31 bits:
   expected :      51.14
   axs      :      59
   SHA2-256 :      47

32 bits:
   expected :      25.57
   axs      :      30
   SHA2-256 :      20

33 bits:
   expected :      12.79
   axs      :      14
   SHA2-256 :      11

35 bits:
   expected :       3.19
   axs      :       7
   SHA2-256 :       2

36 bits:
   expected :       1.59
   axs      :       1
   SHA2-256 :       2

37 bits:
   expected :       0.80
   axs      :       0
   SHA2-256 :       0

So, while it appears to lag for some bitnesses, it generally follows the expected values, both for tree depth and collisions.
What would a hash which is not good for your input mean? That your input generates a sequence when passed to it? That would be ridiculously unlikely statistically speaking. Worst case is O(n) but you are not going to see it.

The algorithm is not good compared to AVL or red-black, even though insertion will probably be faster generally, however it beats a linked list or betting on input for a BST any day.


texts: We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than O(N), maybe similar with the single peak finding in O(log N)?


texts: Stronger versions of P != NP which better express actual convictions

texts:
Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy doesn't collapse!" expresses the core of "P is not equal to NP!" ? Let me try to elaborate:

The P vs NP problem implicitly invokes a number of related but distinct challenges and convictions. Focusing on the convictions, we have that NP != coNP is believed with nearly the same conviction as P != NP, and is part of the conviction that the polynomial hierarchy doesn't collapse. (Because the polynomial hierarchy is less familiar than NP, this conviction is weaker, but still strong enough to be used as a reasonable assumption in a proof.)

Similarly, "L != NP is incredibly hard to prove" is believed with nearly the same conviction as "P != NP is incredibly hard to prove". Now there may be weaker statements which we don't know how to prove either, like "$U_{E^*}$-uniform TC0 != PH", but they don't necessarily feel natural enough to be part of real convictions. So my question is whether "L-uniform NC1 != NP is incredibly hard to prove" would qualify as a natural (and sufficiently strong) conviction. (I'm pretty certain that "NC1" is appropriate here, but I'm less certain about "L-uniform" and "NP". Maybe something like "non-uniform NC1 != PH/poly is incredibly hard to prove" would be much more natural and somehow imply all the other related natural convictions.)


texts: Draw 3D bounding box of object in 2D image OpenCV

texts:
Recently I have been interested in Computer Vision and I am now experimenting with OpenCV in Python. I have done some research but haven't really found what I am looking for. Therefore I try to give it a go my own way.

My objective is to have an image where a 3D object is situated in. Of this object I would like to draw a 3D bounding box around it. My idea of accomplishing this is by:

Draw a 2D bounding box around the object (green square)
Determine corners within the 2D bounding box (red dots)
Determine contours withing the 2D bounding box (blue lines)
Connect the corners by the contours

The following image illustrates the 4 steps above.

I would like to know if this is a possible approach, or if there are better ways to do this? Any suggestions and input is welcome since I'm still pretty new into the field of Computer Vision.


texts: Prerequisites for AI and machine learning

texts:
I am interested in the field of AI and machine learning and I am fairly good at mathematics and statistics and programming in general. However I lack a formal CS education and my undergraduate degree was in an unrelated field.

What are the typical prerequisites for a master's-level course in AI and machine learning?


texts:
Is a graph with two of the same edges a graph?
Specifically, can this graph be considered a directed graph?


texts: Bipartiteness testing in restricted cases

texts:
Bipartite testing is in Logspace and a proof is in Is deciding whether or not a graph is bipartite in $L$?.

Is there a restricted version of Bipartite testing in $NC^1$?

For example bounded degree, planar etc. and if so are there references for the algorithms?


texts:
I need to find the time complexity of the following simple algorithm.

Calculate the time complexity of the following algorithm:
void f(int n) {
  int i, x;

  for (i = 1; i <= n; i++)
    if (i % 2 == 1)
      x++
}

It obvious that the time complexity of this algorithm is $\Theta(N)$, but how I prove it formally?
I know that the loop will do $N$ iterations, so the total number of operations will be $N \times \text{(number of operations inside the loop)}$.
Here the tricky part, I know that for each iteration will be one operation for the comparison and one operation only if $i$ is odd.
So it's something like this:
$\sum_{i=1}^{n}(1+\frac{1}{2})$? I'm not sure, it's seems too strange and I'm not sure how to continue.
What is the best way to write it formally?
Also, I would like to ask if there are books with many examples of analysis of simple algorithms like this and proofs of their complexity. The most recommended book seems to be CLRS, but I didn't found many examples of this kind there and from what I understand it can be very complex topic (depending on the series you need to calculate in the end).
Thank you.


texts: Number of non-XOR gates needed to implement an n-bit boolean function

texts:
There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits.

A classic result in circuit complexity is that, if you count the total number of gates needed to implement $f$, most $f$s take $\Theta(2^n/n)$ 2-to-1 boolean gates. I'm interested in a slightly different metric, where you can use as many XOR gates as you want but you don't count them (ditto for NOT gates, which are just a XOR with one input constant). So your circuit could have $n$ AND gates plus $2^n$ XOR gates, and I'd call that a circuit of non-XOR-size $n$.

I've figured out that it's possible to implement any $n$-input function $f$ using at most $2^{n/2+1}$ gates that aren't XOR or NOT. The strategy works by using $2^{n/2}$ AND gates (with XOR gates interspersed) to prepare a set of $2^{n/2}$ indicator bits that can be XOR'd together to make any function of $n/2$ bits. I then pretend the top $n/2$ bits of the input index register are "choosing" the sub-function to apply with the bottom $n/2$ bits, and use my indicator bits to prepare the $2^{n/2}$ possible sub-function outputs. I then use $2^{n/2}$ AND gates to mux out the desired sub-function output (selected by the top $n/2$ bits of the input index register).

I'm interested in knowing is it possible to do better than $2^{n/2+1}$ AND gates, or is that asymptotically optimal.


texts: when can i detect the position of error in hamming code

texts:
I have 4-bit data with the hamming code 0010011.
the parity parameters are: p1=0 , p2=0 , p3=0
and the check codes are: c1 = 0 , c2 = 1 , c3 = 0
so I thought that I have an error in position 2 of my data but the solution says that I can not detect the position of the error.
my question is: when I can find the position of an error in hamming code?


texts: Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

texts:
I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys are tombstones and there are less than 400 active (so non-deleted) keys, the B-tree is completely replaced by a new one with just one top containing all the active keys.

The question is whether this structure still allows to perform all future operations (except the clean-up operation) in $O(log(n))$ time (with $n$ the amount of active keys in the tree).

I suspect that this isn't true because with this tree, it's possible to have very very much tombstones, and still more than 400 active keys (let's say 401 and 10 000 000 tombstones). But I'm not sure if my reasoning is correct. Can someone please verify this for me?


texts: Given all maximal independent sets of a graph, find the maximum indepdent set

texts:
I am new to this independent set problem in graph theory. As per my understanding so far an independent set is a set of vertices in which no two vertices are adjacent. And the maximal independent set is a set of vertices in which if some vertex is added it will construct an edge.

I understand this now my question is if given all maximal independent set for a graph then the maximum independent set of that graph will be maximal independent set with maximum cardinality right?

Note: As per my understanding there can be more than one maximum independent set but their cardinality will be same.


texts: If a grammar is SLR(1) then are the LALR and SLR tables the same?

texts: I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all that has to be in LALR.


texts: What are all the decidable languages that can be constructed using a turing machine with only the Reject and Accept states?

texts:
What languages can be decided by a two-state TM that has two states: one accepting and one rejecting?

As a newbie in TMs, there are some definitions I am not familiar with, of which the answer is obviously dependent,  like:

Can we draw an outgoing arrow from the Accept or Reject states?
Can either of these two states be the starting state?


texts:
I've been trying to solve an interesting problem created by one of my friends. The following is the problem statement:

There are $n$ types of chocolates. $\langle a_1,a_2,a_3....a_n \rangle$ are positive integers which represent the number of chocolates of each type. These chocolates must be packed into boxes of capacity $k$ i.e. each box can contain at most $k$ chocolates. Also no box can contain two chocolates of the same type i.e. the chocolates in every box must be of distinct types. What is the minimum number of boxes needed to pack all the chocolates?

A greedy approach would be to iteratively fill boxes by picking chocolates from the top $k$ types (in terms of number of remaining chocolates). However this is not of polynomial time complexity.

I also tried to solve the decision version of the problem. (can the chocolates be packed using $m$ boxes ?). I was able to model it as a max flow problem but the number of vertices was not polynomial in the input size.

Is this problem NP-Complete? If not what would be a good polynomial time algorithm to solve it?


texts:
I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve:
A Company makes a new contract with a customer and wants to order materials. There are serval suppliers with fix delivery costs.  Each supplier can offer some of the materials with different pack sizes and prices. What is the best approach to get the materials for the lowest price? I wanted my App to automatically suggest the best order.

* You can order at multiple suppliers;  You can order more materials than needed *

Further explanation:
I know what materials needed for the contract, for Example (Input):

750 of Material 1
250 of Material 2
500 of Material 4
50 of Material 5

I know the delivery Costs and material costs of each supplier. Delivery costs are only paid once for each supplier. I want to get the best solution to order the materials (cheapest).

Output should be a list like:
Ammount - Product of supplier - Supplier

Example:

Material 1

1 x 500Q,P40 from Supplier 1
2 x 125Q,P12 from Supplier 3

Material 2

1 x 250Q,P60 from Supplier 3

....


texts: Understanding proof for Busy Beaver being uncomputable

texts:
I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold.

(BB(n) is defined as the number of steps made by n-state Busy Beavers.)

  Theorem: BB(n) is uncomputable. That is, there is no Turing machine
  that can take as input n and computes BB(n).

  Proof: Suppose to the contrary that such a machine existed, and call
  it T. We will use T to construct a machine which solves the halting
  problem as follows:

  On input < T, w >, a description of a Turing
  machine and its associated input, we can determine in finite time the
  number of states that T has (it is encoded in the description of T).

  Now simply compute BB(n), where n is the number of states in T, and
  simulate T on input w, counting its steps as it proceeds.
  Eventually the simulation of T either halts, or makes more steps than BB(n).

  In the former case, we may stop the computation and declare that T halts.
  In the latter, we know that BB(n) is the maximal number of steps that
  can occur for any Turing machine with n states that eventually halts.
  Therefore, if T had not halted on the input w, it must never halt.

  We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.

  This is a contradiction, so the sequence BB(n) cannot be computable.

If we assume that T can calculate BB(n) for any n, don't we also have to assume that it does halt, and therefore that it will not exceed the steps of BB(n)? (That would also mean that using T to solve the halting problem does not work)


texts: Optimizing Fleury's algorithm to work in O(|V|+|E|)

texts:
The time complexity of Fleury's algorithm is $O(|E|^2)$ because for each edge I have to check whether it is a bridge or not and that takes $O(|V|+|E|)$ time. But, instead of that if I store my bridges in a hash table by a traversal at the beginning and then print the Eulerian tour (checking for each bridge in $O(1)$ using the hash table), the overall time complexity would be $O(|V|+|E|)$. So, will this optimization be useful? If yes, why is it not included in Fleury's algorithm?

In addition, which algorithm is used in practice to print an Eulerian path (not Eulerian cycle, I know that can be done in $O(|V|+|E|)$ using Hierholzer's algorithm)?

I am more interested in theoretical analysis (whether this optimization would be useful) rather than actual implementation.


texts: How can I solve it (modification of famous robot travelling problem)?

texts:
Imagine you have to solve this question (+ you have obstacles, i.e. walls), but you're allowed to move in any of 4 directions (not just 2: down and right). How can you solve it? I'm struggling to apply the same dynamic programming principle.

EDIT: one more similar question.


texts: techniques for finding relevant words in a huge list of strings

texts:
I have a huge list of strings. The goal is to make a database of "relevant" words.

Of course in the context of what I work with, "relevance" is something akin to the organization I work with. For e.g. if it is a automobile manufacturing industry they'd buy products like

Automotive assembly equipment
Radial tyres
Etc

If it were an aircraft manufacturing industry:

Fabricated Aluminium Body
Hydraulic Fluid
Skydrol
Jet Fuel
Etc...

Issue is that I might come across so many spelling mistakes, abbreviations, and variations.

So what is a technique I can prepare a database of words like these when I have nothing to start with, except a huge list of strings.


texts: Demonstrating that probability for every possible result is uniform at the end of an algorithm

texts:
I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$.
At some point ($t=k+1$) the array will be full and we must choose a value inside the array to replace with the new one. The objective is to find an algorithm that outputs a uniform subset of $k$ elements. For example, with $k=2$ and $t=3$ it will output with uniform probability one of the following: $\{1,2\}$, $\{1,3\}$ or $\{2,3\}$. One possible algorithm is the following:

create array of $k$ elements
FOR $t=1,.\ldots,T$:
if array is not full insert an empty space
receive an input
discard the input with probability $1 - k/t$
else insert the input at a uniform location
END FOR
return array

It's easy to implement such a program and convince yourself that this is indeed a solution to the problem but how do I demonstrate it?
Essentially I need to demonstrate that each subset has probability $1/\binom tk$ to be the result at the end (that's because $\binom tk$ is the number of possible subsets of $k$ elements at time $t$).


texts: Mathematical representation of value set of a composite attribute

texts:
Following is a paragraph on page 70 of Fundamentals of Database Systems by Ramez Elmasri:

Mathematically, an attribute $A$ of entity set $E$ whose value set is
$V$ can be defined as a function from $E$ to the power set$^6$ $P(V)$
of $V$:
$\quad A : E \to P(V)$
We refer to the value of attribute $A$ for entity $e$ as $A(e)$. The
previous definition covers both single-valued and multivalued
attributes, as well as NULLs. A NULL value is represented by the empty
set. For single-valued attributes, $A(e)$ is restricted to being a
singleton set for each entity $e$ in $E$, whereas there is no
restriction on multivalued attributes.$^7$ For a composite attribute
$A$, the value set $V$ is the power set of the Cartesian product of
$P(V_1), P(V_2),\dots, P(V_n),$ where $V_1 , V_2 , \dots, V_n$ are the
value sets of the simple component attributes that form $A$:
$\quad V = P(P(V_1) \times P(V_2) \times \dots \times P(V_n))$

Here, I don't understand why the value set of a composite attribute has to be the power set of the Cartesian product. To my understanding, a value set of an attribute represents the pool of values from which we can assign a collection to that attribute. So I think that $V$ here should just be $P(V_1) \times P(V_2) \times \dots \times P(V_n)$ and not $P(P(V_1) \times P(V_2) \times \dots \times P(V_n))$. Am I right to say that?


texts:
Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am inserting the adjacent values (top, left, right, bottom) in a min heap.
I am specifically trying to understand how big the heap would grow. I know that BFS traversing would cost me O(mn) and each heap insertion would cost me O(logk) where k is the size of the heap. Here I am trying to figure out how big can be k.
e.g

[
[1,2,3,4,5],
[2,3,4,1,3],
[4,3,2,1,4]
]

My thoughts are that at max there can be m x n elements in the heap. So the overall complexity can be O(mnlogmn). But when I run through some examples, I think not everything will be in the heap all the time. A single cell can at max insert 2 elements (other 2 would have been inserted by some other cell already). So based on the examples I am thinking that it should be O(mnlog(m+n))


texts:
An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an admissible heuristic?

In my opinion yes, because during the search, for any node, we won't have any overestimation as a misplaced tile will have to move at least the number of spots between itself and the correct position.
Is this correct?

And also, would it be correct to say that the Manhattan distance multiplied by the mean of all tiles (eg 8-puzzle -> 4.5) is a heuristic that dominates the Manhattan distance in this case?

Thank you,

(Having troubles with my 1st AI class)


texts:
I was reading deadlock topic from Operating Systems book by Stallings. It states four pre requisites for deadlock:

Mutual exclusion
No preemption
Hold and wait
Circular wait

It then have following sentences scattered in the topic at difference places:

  the four conditions, taken together,
  constitute necessary and sufficient conditions for deadlock
  first three are necessary conditions for deadlock
  all four conditions listed above are sufficient for deadlock

Then I came across following question:

  Which of the following are sufficient conditions for deadlock?
  I.  Mutual exclusion
  II. Hold and wait
  III. No preemption
  IV. Circular Wait
  A.  I and II
  B.  I and III
  C.  IV only
  D.  I, II and III

I got confused whats the correct answer. I feel all are necessary, but fourth one is the only sufficient one, or I should say fourth one is self sufficient. None of first three can be considered as sufficient. So I felt option C is correct.

But I still felt fuzzy. So I googled about "necessity vs sufficiency" and I found below:

From here:

  A necessary condition must be there, but it alone does not provide sufficient cause for the occurrence of the event. Only the sufficient grounds can do this. In other words, all of the necessary elements must be there.

(a) Does this suggest that all conditions together will be called as "sufficient", not just circular wait?
(b) Does this mean that, alaways: $$\text{set of necessary items} \subseteq \text{set of sufficient items}$$
But then wikipedia says:

  A condition can be either necessary or sufficient without being the other.
  A condition can be both necessary and sufficient.

If these points are true then 1(b) above is false.

Can someone please clarify relation between necessity and sufficiency? Also can anybody tell what is/are sufficient condition(s) for deadlock?

Update

Wikipedia also says, if $S \rightarrow N$, then $S$ is sufficient and $N$ is necessary. (Source: https://en.wikipedia.org/wiki/Necessity_and_sufficiency)
Here, we have,

$CW \rightarrow HW, MX, NP$

where,
$CW$: circular wait,
$HW$: hold and wait,
$MX$: mutual exclusion,
$NP$: no preemption

So, I believe $CW$ is sufficient and $\{HW, MX, NP\}$ are necessary.


texts: Algorithm to find a minimal regular language containing given context-free language

texts:
I am not sure that the problem is in general solvable, but here's an example of what I mean:

Any context-free language has a trivial regular language that contains it: $\Sigma^*$.
The language $L_1=\{a^nb^n\;|\;n\geq 0\}$ is contained in $L_2=\{a^nb^m\;|\;n,m\geq 0\}$, which is obviously a subset of $\Sigma^*$.

Questions

Is there a way to prove $L_2$ is the "smallest"* language which contains $L_1$?
Is there an algorithm for finding such language pairs given the context-free one?

"smallest" means that there is no other language which also satisfies the requirement and is its proper subset.

PS
Sorry, I now realized that I cannot actually find the minimal language with the requirement given above, for example: $L_3=\{ab, aabb\} \cup \{a^nb^m\;|\; n,m \geq 2\}$ would be smaller than $L_2$, and one could continue constructing languages like that ad infinitum.  So, maybe an alternative definition for "smaller" could be "having least states"?
I'm sorry for indecisiveness.  Please feel free to put this on hold until I figure out the good requirement.  Or suggest one yourself, if you feel like there may be an interesting one.


texts:
So, computing largely operates through states of 0 or 1, this I am aware of. But I do have a question, is there a meaningful difference in computing using more states. For example, 0, 1, and 2. Logically, looking at the surface, this would allow encoding more information in a smaller number of bits. But is this actually how it would work in theory?
New question looking at answers given, how exactly would a Base-e system work? or does this only work in Pure Mathematics and not the physical world?


texts:
My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \{a^m b^n \mid m \le n \le 2m \}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.


texts: Can you have a binary search tree with O(logn + M) property for the following case

texts:
Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I have devised the following algorithm, where I search until I find the first occurence of the prefix $x$ in one of the nodes. After that I run an inorder traversal on it, such that I print only the ones, that have prefix $x$ and are in order.

For example of sorted strings: $[ACT,BAT,CAT,CAB]$ and the prefix $x = CA$, I would print $CAT$ and $CAB$.


texts: An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

texts:
Suppose there is an unlimited number of pipes, each has length $x$ meters.
There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.

For example we need to have $n_1$ pipes of length $x_1$,$n_2$ pipes of length $x_2$,..., $n_k$ pipes of length $x_k$ $\forall i, x_i \leq x$.

We need to cut the pipes of length $x$ such that the requirements to be fulfilled and also minimize the number of the used pipes.

For example for $x = 12$ and $$item1: x_1=3,n_1=50$$ $$item2: x_2=5,n_2=30$$ $$item3: x_3=7,n_3=80$$$$item4: x_4=2,n_4=90$$$$item5: x_5=9,n_5=15$$

we can cut the pipes in multiple ways. The worst solution is to allocate one pipe for each requirement, in this way the number of used pipes will be $$\sum_{i=1}^{i=k}{n_i} = 265$$

But by combining item2 and item3 into one pipe, we can reduce $256$ by $30$. In this way item2 is prepared then we can combine item1, item3 and item4 to prepare the items and use the minimum number of the pipes.

As another solution we can also combine item5 and item1, or even allocate one pipe of length $12$ for $4$ pipes of item1

I would like to know is this a famous problem? and is there any efficient algorithm for it?

 My Solutions

Solution 1

Because I really don't know what the class of this problem is, I tried to solve this problem using the approximation algorithm given for the Set Cover problem.

The items form the set of elements, and any combination of items where the summation of their $x_i$ is less than or equal to $x$ is a valid set and its cost equals to $$cost(set_i) = x-\sum_{item_j \in set_i}{x_j} $$

But in set cover problem an element may appear in multiple sets while in this problem such thing is not reasonable. Besides that the $n_i$s are different that is why the Set Cover solution is not working here.

Solution 2

My second solution is a simple greedy algorithm. First I create set of valid sets as explained in the Solution 1, select the one with minimum cost. In this way at least one item with the minimum $n_i$ is produced.

In the second step, first I need to update $n_i$s (because some items are produced in the previous step) and remove the completely covered item from the list. If $set_j$ was the set with minimum cost, Then there will be a few pipes with the length $$wasted= x - \sum_{item_k \in set_j}{x_k}$$.

For the remaining items in the list, if there is anyway to form elements in a set such that sum of their $x_i$ is less than or equal to $wasted$ then we produce those pipes, else we should repeat from the first step with the new list.


texts:
Lets say we use the predictive parser LL(1). Why is it necessary that
$FIRST(\alpha) \cap FIRST(\beta) = \emptyset$,
for all $\alpha, \beta$ right side of alternative productions i.e., productions associated to the same non-terminal. Why is this condition necessary?


texts: Does the complement of sigma Kleene star exist?

texts: If $\Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be?  The empty set?


texts: Finding all possible bottom-most overlapping rectangles on a table

texts:
Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for simplicity). The color of the rectangle that is colored the latest on a cell will remain that color. For example, I could have the following progression:

0 0 0
0 0 0
0 0 0

1 1 0
1 1 0
0 0 0

1 1 0
1 2 2
0 2 2

1 1 3
1 2 3
0 2 3

Of course, the example would continue for all $n^2$ colors, and you are only given the final state as the input. For example, the input we would be given is only the last grid of the 4 above. From it, you have to determine, what is the number of possible colored rectangles that could have been painted first?

My initial idea is that any rectangle that "overlaps" another rectangle cannot be the bottommost. For example, in the sample, we know that color 2 cannot be the bottommost because it "covers" color 1. On the other hand, color 1 and color 3 do not cover any other colors, so they can be the bottommost. I suspect that this can lead to an algorithm, but how?


texts:
If a (n,d) random graph is a n-vertex graph defined as :

Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, for every n and $d \geq 2$, a (n,d) random graph is a (n,2d,1/10) edge expander with probability 1 - o(1).

For a given S such that $|S| \leq n/2$, I have found the expected value of the number of edges |E(S,S')| between S and V\S. But since this random variable is the addition of random variables which are not independent, I cannot apply the Chernoff bound to say that, the probability of |E(S,S')| being far from its expected value is low.

Is there any other way to prove this ?


texts: Is the intersection of two context free languages recursively enumerable?

texts:
I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.

I could not, however, find a citation for this quotation (and searching has failed to turn up a restatement of this result somewhere else).

Can anyone provide a proof or a citation to the original proof for this result?  Can anyone state that it is false?


texts:
Let L = { uv composed of {0,1}  |  |u| = |v| and u = v }

Do we agree that this language is not a Context Free Language ?

If not, why ? Can you give me a pushdown automata that recognizes it or the grammar that describes it ?

Thanks in advance for your help !


texts: what is variable capture in nominal logic?

texts:
While reading a paper Nominal Unification from a Higher-Order Perspective, in the abstract I noticed something feel bit confusing,

  Nominal Logic is an extension of first-order logic with equality,
    name-binding, name-swapping, and freshness of names. Contrarily to
    higher-order logic, bound variables are treated as atoms, and only free
    variables are proper unknowns in nominal unification. This allows “variable
    capture”, breaking a fundamental principle of lambda-calculus.

I know a bit about nominal logic, but as I know it respects $\alpha$-conversion, such as $\lambda x.x \approx_\alpha \lambda y.y$.
but I could not understand above statement.

I understand the notion of variable capture which leads to a wrong result during the substitution.

So does variable capture not lead to an incorrect result in nominal logic?

what does it mean saying breaking "variable capture" here?

Can anyone explain with examples?


texts:
For language $M \subset \{0, 1\}^*$ lets denote $And(M) = \#(M\#)^*$ and
$Or(M)=\#\{0,1,\#\}^*\#M\#\{0,1,\#\}^*\#$.  We can say that language
has $AND$ ($OR$) property  with respect to polynomial
reductions if there exists polynomial reduction from $AND(M)$$(OR(M))$ to
$M$.
Show that each language in $P$ has both properties with respect to polynomial reductions.

Please hint me because I cannot come up with an idea how to show it.


texts: Can an alphabet for a Turing machine contain subsets of other alphabets?

texts:
For example;

Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?


texts: Tool for illustrating the relation and hierarchy of different terms and phrases

texts:
Is there some tool which illustrates the relation and hierarchy of different terms and phrases?
Example: What is the hierarchy of "Natural Language Processing" and "Text Analytics"? Which of these terms includes the other one?
What is your opinion on my example?


texts: Worst simultaneous blowup when converting to CNF and DNF

texts:
I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the two normal forms. Or, stated otherwise, given the predicate $p$, how to find:

$$
\rho = \max \min \left\{\alpha, \beta\right\}
$$

where

$$
\alpha = \mathcal{O}(\text{CNF}(p))
$$

$$
\beta = \mathcal{O}(\text{DNF}(p))
$$


texts:
The VPRI institut founded by Alan Kay has some papers on constraint-based  layouts for GUIs based on constraint solving.

For instance:

Wallingford: Toward a Constraint Reactive Programming Language by Alan Borning (2016)
A Report on KScript and KSWorld by Yoshiki Ohshima, Bert Freudenberg, Aran Lunzer and Ted Kaehler (2012)

Further papers by Alan Borning and others include:

Scwm: An Extensible Constraint-Enabled Window Manager by Greg J. Badros, Jeffrey Nichols and Alan Borning
Constraint Solving for Beautiful User Interfaces:How Solving Strategies Support Layout Aesthetics by Zeidler, Lutteroth and Weber (2012)

Are there other groups working on constraint-based layouts for GUIs?


texts: An algorithem for finding the number of primes of the form 4k+3 under some n

texts:
I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 million) in less than 10 minutes, any ideas?
Iv'e tried using variation's on the Sieve of Eratosthenes and lagranages method but the first was too slow and i didnt manage to have the second count only primes of the form 4k+3.


texts: How to eliminate ambiguity of the follwing CFG?

texts:
Consider the following CFG:

$S\to AED | F \\
A \to Aa  | a\\
B \to Bb  | b\\
C \to Cc | c\\
D \to Dd  | d\\
E \to bEc | bc\\
F \to aFd | BC$

The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,c) and $aaa...b^*c^*ddd...$ (equal number of a,d)

There is ambiguity since $abbccd$ can be derived respectively by $S\to AED$ and $S \to F$.
I try to rewrite the production rule like:
$$S\to AED\\E\to BC$$ But my CFG produces $a^*b^*c^*d^*$ which is different from original. Could anyone give me some tips?


texts: Do exponents have higher time complexity than factorials?

texts:
My professor said exponentials will always have higher time complexity compared to polynomials. My question is, do exponentials also have higher time complexity than factorials?

I plotted a chart in Matlab to check it myself.

When range of x is small, from 1 to 10, I get the following chart,

%Matlab script
x  = [1 : 10];
y1 = factorial(x);
y2 = exp(x);

plot(x', [y1',y2']);
title("N! vs e^N");
legend("O(n!)", "O(e^n)");

Here factorial is clearly beating exponential.

But when I bump the range of x from 1 to 1000, I get the following chart,

x  = [1 : 1000];

Here exponential is clearly beating factorial.

So, can I say conclusively that exponentials will always have higher time complexity than both factorials and polynomials?

-


texts: question about the construction of BSTs using a repeated sequence of rotations

texts: How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).


texts: Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear?

texts:
I have read in Wikipedia (and other sources) about the limited backtracking algorithm of Even, Itai & Shamir for solving 2-SAT problem in a linear time, but the approach doesn't seem to be linear, there is no demonstration nor algorithm implementation to check it.

Here is the algorithm description from Wikipedia: Even, Itai & Shamir - Limited backtracking.

Has anyone heard about this algorithm? Does anyone have its implementation/demonstration?

PS: I am not searching for an algorithm to solve 2-SAT problem in a linear time since I have read about the Aspvall, Plass & Tarjan approach. I am just interested in the former algorithm.


texts:
I often read statements such as "the run-time of algorithm X is polynomial in m and n". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one parameter but not the other one, so if this is not the case, it is important to emphasize that it is polynomial in both parameters.

However, I have never read a statement such as "the problem is NP-hard in m and n". A problem is always claimed to be NP-hard, period. My first question is: why? Apparently the same rationale is true here too: a problem may be NP-hard in one parameter, but at the same time, it may have an algorithm with run-time polynomial in the other parameter.

My second question: what is an accurate description of a problem with two parameters: $m$ and $n$, that (1) for a fixed $m$, can be solved in time polynomial in $n$, (2) for a fixed $n$, it is NP-hard (with respect to $m$)?


texts: Merging sorted arrays and finding Big O bounds

texts:
Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, all the way until $xn$ for the cost of merging. How would one go about finding the tightest possible Big-O bound for the cost of all the merges? I don't know how to go about this, I have tried writing an equation for the sequence, and that might be where I am going wrong.
The sequence would look something like $2n+3n+4n \dots +kn = n(2+3+4+5+ \dots +k)$ and I'm not sure where to go next.


texts: How to move spheres in 3d without collision

texts: Is there an algorithm that gets as an input 2 arrays (arr_origin, arr_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to dest without collisions, in the fastest way given each sphere can move at a speed from 0 to V?


texts: Question on an Algorithm for Longest Increasing Subsequence

texts:
I have been reading this paper: https://arxiv.org/abs/2011.10874
This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of the paper: we first organizes elements by layers $L_i$ described as follows: "We define $b_i$ as the size of the longest increasing subsequence ending at element $a_i$ and divide the sequence into disjoint layers. More precisely, let each layer $L_i = \{a_j | b_j = i\}$ be the set of elements whose corresponding $b_j$ is equal to i. "
We then combine executive layers of equal size into basket (expect for the first and last basket). The baskets are considered light or heavy based on criteria listed in Page 14
I got quite confused with part of the algorithm when they say:
"Throughout our algorithm, we maintain a local data structure for each light basket i that stores the following information: If $i = 1$, then for each element ay of basket 1, we store the size of the longest increasing subsequence that ends at $a_y$. If $i > 1$, then for each boundary element $a_x$ of basket $i−1$ and each element $a_y$ of basket $i$, we store the size of the longest increasing subsequence that starts at $a_x$ and ends at $a_y$. Except for the initial element $a_x$, any element that may contribute to such a subsequence is certainly inside basket i" (Page 14).
The part that I am confused with is weather or not we dynamically change the number of layers in a basket. For example, if I remove the element "14" from the list, $L_8$ will only constitute "15", so should "15" be moved to Basket 3 or "15" is kept in Basket 4? This is pretty important since after the deletion, would "13" be the boundary term of Basket 3 or is it "15"?

Thanks
Update: I have understand the problem and post the resolution. I would like to keep the question for other users


texts: Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points

texts:
I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set.

I've tries to find it again many times, but have failed so far.

The algorithm was as follows:

Each object is assigned a sorted queue of nears neighbors (maximum size is k). Let's assume that $k < log(N)$
Each time you calculate $distance(A, B)$ try to add A into B's neighbor list and vise versa.
Choose $log(N)$ support objects (say, first $log(N)$ objects out of $N$). (Or maybe that was $sqrt(N)$)
For each support, build the distance-based index containing all N objects
After the index construction, every object has a candidate list of k nearest neighbors. All real nearest neighbors are not further than the furthest neighbor in the candidate list - candidate neighbor radius.
For each point we use triangle inequality and current neighbor radius to constrain the distances between a candidate point and the support points: $|dist(candidate_i, support_j) - dist(point, support_j)| <= radius$. We efficiently extract the candidates that fall in radius-based ranges for all support points.
We calculate the distances for those candidates and update the nearest-neighbor lists for both the current point and the candidate points.
As we process more points, the neighbor lists become "tighter" - the radius, the distance to the furthest neighbor decreases with each update of the list.
Tighter constraints mean that the candidate lists become smaller and smaller after each processed point and leading to total run time of $N*log(N)$.

So, why do I need the paper again? First of all, several people have asked me for it and I was surprised I cannot find it again.
More importantly, it did not work well for me. This might be caused by a bad choice of the support objects. I remember nothing about the selection process.


texts: Removing identical variables in CFG Unit Productions

texts:
Productions of the form A-> A are removed immediately, but what if the production is of the form A -> AA?

example:
A -> AA | a


texts: proof of convergence in arbitrary precision PRNGs

texts:
consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow).

srand(x)
z = 0
while (z >= 0)
{
  r = rand(100)
  if (r <= 50) z -= 1
  else z += 1
}

the PRNG is inited with seed x (also arbitrary precision). the PRNG rand(100) generates a value between 0..99. hence for 51 values the accumulator var z is decremented, for 49 values it is incremented.

it is expected due to the law of large numbers that this program will halt for all initial seeds x. however,

  how does one prove it will halt for all initial seeds x?

it seems such a proof must depend on the details of the construction of the PRNG. am assuming there exist PRNGs such that a different random sequence is generated for every initial seed x (ie the infinite set of naturals). that in itself may be up for question. are such PRNGs known? where are they used? etc.. so an answer may come up with an arbitrary PRNG for the purposes of the question. a single example fulfilling the criteria would be an acceptable answer.

looking for related literature, similar problems/proof considered, etc.


texts: Implement a search procedure in terms of a set test procedure

texts:
Suppose you have a procedure $\mathrm{Prod}(S, t)$ that inputs a finite set of integers $S$ and an integer target $t$, and outputs either “yes” or “no” according to whether there exist distinct elements $x_1, \dots, x_n \in S$ with $\prod_{i=1}^n x_i = t$. You would like to implement an enhanced version of $\mathrm{Prod}(S, t)$, called $\mathrm{ProdSearch}(S, t)$ that outputs the elements $x_1, \dots, x_n$ if such elements exist.

Describe an efficient such procedure $\mathrm{ProdSearch}$ that works by making multiple calls to $\mathrm{Prod}$ as a sub-routine. Carefully explain why your procedure is correct.


texts: Updating an MST $T$ when the weight of an edge not in $T$ is decreased

texts:
Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
  Now we decrease the weight by $k$ of an edge $e$ which does not belong to $T$.

  How to efficiently update $T$ to make it an MST (denoted $T'$) of $G'=(V,E,w')$, where $w'$ is the same as $w$ except that $w'(e) = w(e) - k$?

The algorithm for updating $T$ to $T'$ is easy: Adding $e$ to $T$ creates a cycle $C$ in $T$. Let $e'$ be a maximum-weighted edge in the cycle $C$. If $w(e') > w’(e)$, then $T' = T \cup \{e\} - \{e'\}$ is the MST as desired. Otherwise, $T' = T$.

I have difficulty in proving its correctness by contradiction. Suppose $T''$ is a spanning tree of $G'$ and $w'(T'') < w'(T')$.

$e \notin T''$: we have $w(T'') = w'(T'') < w'(T') \le w(T)$. Contradicts with the fact that $T$ is an MST of $G$.
$e \in T''$: I am stuck here.

Two Notes:

The accepted answer here to the same question is too general for me to follow.
I prefer to proofs which do not rely on any concrete MST algorithms, such as Kruskal's and Prim's algorithms. However, you don't need to prove it by contradiction or separate the two cases $e \notin T''$ and $e \in T''$ as I did.