Breadth First Search Path Finding - Store Paths in Queue or Track Predecessors? In studying various solutions for finding a path in a 2d maze using BFS, I've come across two different approaches. One is to store the whole path to a given position in the search queue. The other is to keep track of predecessors and build the path at the end by back-tracking.

I'm curious to hear which of these approaches is considered better in which situations. It looks to me like the time and memory requirements for the "store the path in the queue" method would grow much faster than the "predecessors" approach as the maze grows in size. Is that correct?

Below are two implementations in Python showing the different approaches.

"""
BFS maze solver.
The queue contains paths.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        print("queue:", queue)
        path = queue.popleft()
        print("path", path)
        i, j = path[-1]
        if grid[i][j] == goal:
            return path
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append(path + [(i2, j2)])
                seen.add((i2, j2))

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
path = bfs(grid, (0, 0))

"""
BFS maze solver.
The queue contains only positions. Predecessors are kept in dictionary.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([start]) #!!
    seen = set([start])
    while queue:
        print("queue:", queue)
        i, j = queue.popleft()
        print("i, j:", i, j)
        if grid[i][j] == goal:
            return (i, j)
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append((i2, j2))
                seen.add((i2, j2))
                previous[(i2, j2)] = (i, j)

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
start_pos = (0, 0)
previous = {}
previous[start_pos] = (-1, -1)
goal = bfs(grid, start_pos)

if goal:
    path = []
    i, j = goal
    while i != -1:
        path.append((i, j))
        i, j = previous[(i, j)]
    path.reverse()
    print("----Node history---")
    for item in previous.items():
        print(item)
    print("----Path----")
    print(path)
```

There's no set answer, as it depends on the number of nodes in the graph, the average number of nodes in the queue at any point in time, and the average length of paths.

"Considered better" is a matter of opinion, and on this site, we focus on technical questions rather than opinion.

If it were me, I would use predecessor pointers as my default, unless I had careful measurements showing that on my workload the other was better.


Optimal data structure for sorted list Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".

Even though B-trees are a generalization of BSTs, I have not seen much of anything say they are used to create ordered data structures. Wondering if programming languages could/should B-plus trees to create a sorted array, or does it use BSTs. So part of the question is, can B-trees, and B-plus trees be used to create associative arrays and sorted arrays and other list data structures (or should they). The other part of the question is which data structure is optimal for all three sorted list operations (search, insert, delete).

I have heard of skip lists as well, but don't understand them yet. I haven't implemented any sort of BST so I don't have a great deal of knowledge about them but I roughly understand how they work. I have read B-plus trees are best for disk storage solutions (not sure exactly why) because high fanout / low depth. But I am more wondering for purely in-memory sorted arrays, what is the optimal data structure for maintaining it:

Binary Search Tree
Red-Black Tree
B-Tree
B-Plus Tree
Skip list
Other

Yes, B-trees and B+ trees can be used to create a sorted array or other ordered data structure.

There is no one data structure that we can call "optimal".  There are a variety of data structures that have various tradeoffs.  Their performance has some similarities, and which one you choose depends on the specific situation (whether you want an in-memory data structure or an on-disk data structure, how important ease of programming is, how important worst-case vs average-case performance is, and many other considerations).  So, I would be reluctant to pick any one of them as "optimal".


PSPACE and NP complexity I'm reading a definition of PSPACE and say: are the decision problems solvable in polynomial space on a Deterministic Turing Machine. My question is: Why NP is in PSPACE?. I have a doubt beccause for example a SAT problem is solvable in Non-Deterministic Turing Machine and SAT $\in NP$ and not in $P$.

NP is a complexity class with constraints on time, whilst PSPACE is a complexity class with constraints on space.
The difference between time and space is (in this case) simple: Space can be reused, whilst Time cannot. A Space-bounded machine can run for as long as it wants (as long as it terminates).

Therefore we can construct a PSPACE-Machine that solves SAT: The machine simply tries every solution.


How to make a Post Machine for $a^nb^n$? I have tried to make a Post machine for that all words of the form $a^nb^n$ by the following steps.

add a marker '#'
read first 'a'
read next 'a's and add them
read first 'b'
read next 'b's and add them
read '#' (that we added in the first step)

repeat steps while input tape is not empty

but this algorithm also accepts words of the form $(ab)^n$ e.g abab, ababab
I want to make a Post machine that only accepts words of the form $a^nb^n$
How to do that?

This language $a^nb^n$ can be recognized by a one counter automaton,
i.e. a pushdown automaton with only one kind of stack symbol (other than the stack bottom).

That can be easily mimicked by a Post machine (with capital P, like
Turing), according to the Wikipedia definition.

So first try to design the PDA with a single stack symbol (that is
easy), and then translate it to a Post machine.

But I am not sure you are using the same type of Post machine as described in Wikipedia, and you did not describe your model.


Spatial data structures are part of Computational Geometry? Are spatial data structures like BVH - Bounding Volume Hierarchy ,kD-Trees etc are part of Computational Geometry( http://graphics.stanford.edu/courses/cs268-14-fall/) or of

Data structures and Algorithms( http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/index.htm ) or of

Geometric modelling( https://graphics.stanford.edu/courses/cs348a-12-winter/ ) ?

If Spatial data structures are not part of neither of these 3, Can you tell which branch of computer science deals with the spatial data structures?

You need spatial data structures as part of computational geometry, to have at least some reasonable base reference against which to compare the time and memory consumption of special purpose (sweepline/randomized) algorithm. For this purpose, BVH is too vaguely defined to be useful (except for summarizing a common principle for some better specified data structures), but kD-trees are good enough for this purpose.

I don't see where you would need spatial data structures for non-geometry related data structures and algorithms, so I would say it is only a part of it, if you study geometry (or GIS) related problems. But if anybody shows me a non-geometry related application, then I'm quite willing to change my mind.

For geometric modeling, things like constructive solid geometry, homogeneous coordinates, Bézier curves, B-splines and NURBS should come first, because understanding them is also important when just using existing geometry modeling software. But BVH fits in well, because it is an intuitive geometric concept. It can sometimes be useful for understanding the performance behavior of existing geometry modeling software (sometimes the user can even influence the BVH to improve performance). I see fewer reasons why kD-trees should be part of geometric modeling.


Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.

My Thoughts:

I am new to proving results like these with Turing machines, so I'm often not sure what is "legal" or "not legal" with a Turing machine. For example,
my textbook often gives "high level" descriptions of Turing machines doing a computation instead of formally step by step. This is the way we are expected to describe Turing machines in class, but it often leaves me unsure if I'm being rigorous enough in my description.

My Attempt:

Construct a Turing machine $M'$ the following way:

$M'$ = "On input $\langle M,w,n \rangle$:

(1) Represent $n$ on the tape by $n$ consecutive $1$'s

(2) Simulate $M$ on $w$

(3) Each "execution" of the transition function is followed by a mark on one of the $1$'s

(4) If $M$ enters an accepting state, accept; Otherwise, reject if $M$ enters a rejecting state or after all of the $1$'s are marked."

My main concern is step (1) of the algorithm. I'm really unsure if that can be done. I'm also not sure how $n$ is represented as a string for the input $\langle M,w,n \rangle$. Am I able to choose how it's encoded?

Thank you for your time and feedback.

This is not a problem. You have an infinite tape, so you can store whatever you want on it.
Depending on how explicit your proof should be, consider a few edge cases for defining your transition function:

a.) How does your TM recognize, if all n 1s are gone? The complexity of this depends on the alphabet of the TM, if $|\Sigma| > 2$ it should be easy, else you have to work out a few details.

b.) After you've marked one of the 1s - how do you get back to the next step of your computation?


What is the time complexity of FC_MRV algorithm? I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.

The worst case complexity of FC-MRV is $O(n^2 d^2)$ where $n$ is the number of variables and $d$ is the number of domain size.


Lambda calculus lists construction explanation I have the following notes that introduce how lambda calculus handles lists. They go as follows:

A list is something we can match on and deconstruct if it is not
empty:
list match{
 case Nil => M
 case Cons(x,y) => N(x,y)
}

A list value is given by how it interacts with two terms M and N

(1) For starters I don't understand at all what is the role of M and N here. Then it continues:

We define it (a list) as a function that will take such M and N as
arguments
$Nil = \lambda mn.m$
$Cons(P,Q) = \lambda mn. n (P,Q)$

(2) Assuming I know how pairs and if constructs work in lambda calculus how can I come up with this expressions myself? I suppose that once this is clear I will be able to understand this sentence:

Cons is like a pair but takes m as argument, too, to fit along with
nil

Can you clarify points (1) and (2)?
Edit:
This are some further comments made in my notes that may make easier to understand what the intention of the writer is:
$Nil \  M \ N \implies M$
$Cons(P,Q) \ M \ (\lambda p. p._1) \implies \cdots \implies (P,Q)._1$

There are several ways to define lists in lambda calculus. You can find them here.
Your definition doesn't seem to fit exactly in any of those (please, check that).
Anyway, I'll try to answer to your questions.

Lists (and many data types) can be defined in lambda calculus in terms of the way to deconstruct them.

If you are familiared with the fold operation, you know it follows this specification:

$fold\ Nil\ e\ f$ = $e$
$fold\ (Cons\ x\ l)\ e\ f$ = $f\ x\ (fold\ l\ e\ f)$

Many functions over lists can be defined with $fold$. For example, if you want to sum the elements of a list $l$ of integers, you can do:

$sum\ Nil = 0 $
$sum\ (Cons\ x\ l) = +\ x\ (sum\ l) = x + sum\ l$

Or just say:

$sum\ l = fold\ \, l\ 0\ +$

In this case, you can imagine that the $sum$ functions replaces the empty list with $0$ and the cons operator with '+'.

So, if we want to define lists in lambda calculus, a way of doing it is to define each constructor ($Nil, Cons$) to do the work of $fold$.
The fist step is to state that $fold$ is just the identity function ($\lambda x . x$).  Then we get the $fold$ specification to be our specification for $Nil$ and $Cons$:

($\lambda x . x$)$\ Nil\ e\ f$ = $e$
($\lambda x . x$)$\ (Cons\ x\ l)\ e\ f$ = $f\ x\ ((\lambda x . x)\ l\ e\ f)$

This is the same as:

$Nil\ e\ f$ = $e$
$(Cons\ x\ l)\ e\ f$ = $f\ x\ (l\ e\ f)$

Rewriting it a bit, we get:

$Nil$ = $\lambda e\ f.e$
$(Cons\ x\ l)$ = $\lambda\ e\ f. f\ x\ (l\ e\ f)$

So, this answers fits in the last form of definition of lists from the wiki (using right fold). But it is important to notice that is not the only way. The way you posted seems to do the same as here, but instead of using the $fold$ operator, using some sort of $destructor$, where:

$destructor\ Nil\ m\ n = m$
$destructor\ (Cons\ x\ l)\ m\ n = n\ x\ l$


What is the relation between NC and P/poly? I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)

If you define NC as the class of problems computable using polynomial size, polylogarithmic depth circuits, then NC$\subseteq$P/poly, since P/poly is the class of problems computable using polynomial size circuits (without restrictions on the depth). Sometimes we also require the circuits to be uniform, and then we get the stronger conclusion uniform-NC$\subseteq$P. In both cases it is conjectured that the containments are strict.

In fact, since P-complete problems are complete with respect to very weak reductions, uniform-NC$\subsetneq$P if and only if a P-complete problem is not in NC. Wikipedia has a list of many P-complete problems.


Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes? I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q?

I'd thought that as our integer number representation on the typical computer is 2-complement, it's actually exactly equivalent as bounding all our operations over the rolling hashes by 2^31, so that in other words, I simply shouldn't care. Plus, the smaller we bound or hashes to, the more collisions we'd have, so a bigger Q should equal with improved performance!

I've tried coding a simple (Java) implementation:

public static int rabinKarp(String text, String pattern) {
    if (text.length() < pattern.length()) {
        return -1;
    } else {
        int patternHash = 0;
        int textHash = 0;
        int pow = 1;

        // preprocessing the pattern and the first characters of the text string
        for (int i = pattern.length()-1; i >= 0; --i) {
            patternHash += pattern.charAt(i) * pow;
            textHash += text.charAt(i) * pow;
            pow *= 10;
        }
        pow /= 10;

        // actual search
        if (patternHash == textHash && areEqual(text, 0, pattern)) {
            return 0;
        } else {
            for (int i = 1; i < text.length()-pattern.length()+1; ++i) {
                textHash -= text.charAt(i-1)*pow;
                textHash *= 10;
                textHash += text.charAt(i+pattern.length()-1);
                if (textHash == patternHash && areEqual(text, i, pattern)) {
                    return i;
                }
            }
            return -1;
        }
    }
}

From some preliminary tests, my hypothesis seems to be empirically accurate, yet I have not seen that written anywhere, so I am left wondering..

Am I missing something?

Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo computation. However, it lacks some of the theoretical performance guarantees. You need to be very careful with the choice of the base (in this case: $10$) with respect to the modulus.

In particular, your choice of $10$ is very poor. Note that $10^{32}=2^{32}\cdot 5^{32}$, so $10^{32} \textrm{ mod } 2^{32} = 0$. This means that only the last $32$ characters of the string are taken in to account in the hash, so one can construct an input on which your algorithm performs very poorly.

Let the haystack be a string of $m$ $1$'s, i.e. $1111111\ldots$ and the needle a string consisting of $n$ $1$'s, one $0$, and then $32$ $1$'s. Because the string ends with $32$ $1$'s every position will result in a spurious hit, and the algorithm will need to loop over $n$ $1$'s before encountering a zero, meaning you will get a $\Omega(nm)$ running time.

I tested your algorithm on an input where $n=3000,m=n^2=9\cdot 10^6$. It took $18$ seconds to run on an input that ended in $32$ 1's, but only $200ms$ for a string ending in $31$ $1$'s.

The problem is that $10$ is not relatively prime to the modulus. For instance, taking $9$ as the base makes your program perform much better, taking only $200ms$ for the case with $32$ $1$'s. Of course, taking a prime modulus will partially solve this problem since the base will automatically be relatively prime to it. However, this is not the only reason for preferring a prime modulus.

Now, even if the modulus $n$ and base $b$ are relatively prime, undesirable things can still happen. For instance, there is a $k$ for which $b^k=1\textrm{ mod } n$. It is undesirable for $k$ to be small, since the hash function can not distinguish every $i^\textrm{th}$ character from every $i+k^\textrm{th}$ character. In mathematical terms you want the order of $b$ mod $n$ to be as large as possible.

The order of $b$ mod $n$ is always at most the Euler-Phi function $\phi(n)$. For a prime $p$, $\phi(p)=p-1$ while for non-primes $n$ it will be smaller. So taking $n$ to be a prime will allow more of the values of $b^k$ to be "useful". Ideally, one should take $b$ to be a primitive root modulo $n$, making that $b^k=1 \textrm{ mod } n$ does not hold for any value of $0<k<\phi(n)$.

Note that you can always construct instances for which the performance is poor, and to protect against "attacks" from an adversary you need to take the base and modulus to be random values.


Generate random numbers from an interval with holes Given a set $S$ of $k$ numbers in $[0, N)$.
The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.

Edit - Also given an API to generate random numbers between $[0, N)$. We have to use it  to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.

I would also like a generic strategy for such questions. Another one I came across was to generate random numbers between [0,7] given a random number generator that generates numbers in range [0, 5].

0 1 2 3 4 5 6 7 8 9

0 1 2 3 - 5 - 7 8 -

"-" are in $S = \{4,6,9\}$

You can create mass distribution with  $$\text{Prob}(x) = \begin{cases}\frac{1}{N - |S|} & \text{if } x \notin S\\
0 & \text{if} \ x \in S
\end{cases}
 $$

and then use this algorithm. Copied from here.

from collections import defaultdict
import random

def roll(massDist):
    randRoll = random.random() * sum(massDist) # in [0,1)
    s = 0
    result = 0
    for mass in massDist:
        s += mass
        if randRoll < s:
            return result
        result+=1

sampleMassDist = [1,1,1,1,0,1,0,1,1,0]

d = defaultdict(int)
for i in range(1000):
  d[roll(sampleMassDist)] += 1

print d


Why is writing down mathematical proofs more fault-proof than writing computer code? I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs.

It seems that this is something more widespread than just my experience. Most people make software bugs all the time in their programming, and they have the compiler to tell them what the mistake is all the time. I've never heard of someone who wrote a big computer program with no mistakes in it in one go, and had full confidence that it would be bugless. (In fact, hardly any programs are bugless, even many highly debugged ones).

Yet people can write entire papers or books of mathematical proofs without any compiler ever giving them feedback that they made a mistake, and sometimes without even getting feedback from others.

Let me be clear. this is not to say that people don't make mistakes in mathematical proofs, but for even mildly experienced mathematicians, the mistakes are usually not that problematic, and can be solved without the help of some "external oracle" like a compiler pointing to your mistake.

In fact, if this wasn't the case, then mathematics would scarcely be possible it seems to me.

So this led me to ask the question: What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?

One could say that it is simply the fact that people have the "external oracle" of a compiler pointing them to their mistakes that makes programmers lazy, preventing them from doing what's necessary to write code rigorously. This view would mean that if they didn't have a compiler, they  would be able to be as faultless as mathematicians.

You  might find this persuasive, but based on my experience programming and writing down mathematical proofs, it seems intuitively to me that this is really not explanation. There seems to be something more fundamentally different about the two endeavours.

My initial thought is, that what might be the difference, is that for a mathematician, a correct proof only requires every single logical step to be correct. If every step is correct, the entire proof is correct. On the other hand, for a program to be bugless, not only every line of code has to be correct, but its relation to every other line of code in the program has to work as well.

In other words, if step $X$ in a proof is correct, then making a mistake in step $Y$ will not mess up step $X$ ever. But if a line of code $X$ is correctly written down, then making a mistake in line $Y$ will influence the working of line $X$, so that whenever we write line $X$ we have to take into account its relation to all other lines. We can use encapsulation and all those things to kind of limit this, but it cannot be removed completely.

This means that the procedure for checking for errors in a mathematical proof is essentially linear in the number of proof-steps, but the procedure for checking for errors in computer code is essentially exponential in the number of lines of code.

What do you think?

Note: This question has a large number of answers that explore a large variety of facts and viewpoints. Before you answer, please read all of them and answer only if you have something new to add. Redundant answers, or answers that don't back up opinions with facts, may be deleted.

Let me offer one reason and one misconception as an answer to your question.

The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this:

function MaximumWindow(A, n, w):
    using a sliding window, calculate (in O(n)) the sums of all length-w windows
    return the maximum sum (be smart and use only O(1) memory)

It would be much harder to go wrong when programming this way, since the specification of the program is much more succinct than its implementation. Indeed, every programmer who tries to convert pseudocode to code, especially to efficient code, encounters this large chasm between the idea of an algorithm and its implementation details. Mathematical proofs concentrate more on the ideas and less on the detail.

The real counterpart of code for mathematical proofs is computer-aided proofs. These are much harder to develop than the usual textual proofs, and one often discovers various hidden corners which are "obvious" to the reader (who usually doesn't even notice them), but not so obvious to the computer. Also, since the computer can only fill in relatively small gaps at present, the proofs must be elaborated to such a level that a human reading them will miss the forest for the trees.

An important misconception is that mathematical proofs are often correct. In fact, this is probably rather optimistic. It is very hard to write complicated proofs without mistakes, and papers often contain errors. Perhaps the most celebrated recent cases are Wiles' first attempt at (a special case of) the modularity theorem (which implies Fermat's last theorem), and various gaps in the classification of finite simple groups, including some 1000+ pages on quasithin groups which were written 20 years after the classification was supposedly finished.

A mistake in a paper of Voevodsky made him doubt written proofs so much that he started developing homotopy type theory, a logical framework useful for developing homotopy theory formally, and henceforth used a computer to verify all his subsequent work (at least according to his own admission). While this is an extreme (and at present, impractical) position, it is still the case that when using a result, one ought to go over the proof and check whether it is correct. In my area there are a few papers which are known to be wrong but have never been retracted, whose status is relayed from mouth to ear among experts.


How Fibonacci LFSR work What is "Fibonacci" about the Fibonacci LFSR?
If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken in consideration (ie. XORing the taps in the current state, shifting and inputing the left bit..).
What am I missing?

"In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state." wiki quote.
Its output depends on state and polynomial, not two states.

The name come (afair) from Fibonacci work on recurence relation, his sequence, and further interest in characteristic polynomials of generating sequences, but the one who gave closed form solution to Fibonacci numbers and researched characteristic equation (the one used in generator with possibly minimal monic to make longest period), was Lucas. I cannot find any reference why it is called Fibonacci LFSR, but it is inventors will to name it.

The same stands for LFG - lagged Fibonacci generator was (in multiplicative form) introduced by Marsaglia to overcome deffects of additive one.

The real interest in random generation was started by Galton (if it matters Romans did toss coins and stored bits), random numbers by Pearson, first PRNG is attributed to von Neuman, first working one to Lehmer, as for Fibonacci his insights are nice, but he started his sequences to count rabbits with no connection to PRNG whatsoever.

Of you are interested in history of PRNG, History of uniform random number generation
 is nice.


Membership in 1, 5, 2, 13, 10, ... (recursively defined sequence) Find if a given integer is in the series $1, 5, 2, 13, 10, \dots$ in the most efficient way, where the sequence is given by
$$
f(n) =
\begin{cases}
1 & n=1, \\
2f(\tfrac{n}{2})+3 & n \text{ even}, \\
2f(\tfrac{n-1}{2}) & n>1 \text{ odd}.
\end{cases}
$$
The series is infinite of course, and $x$ can be a number with at most 9 digits. The idea is not to hardcode this and maybe find some kind of correlation that will allow you to solve this fast. I want to say that I have an idea of how to solve it but I don't.

Your sequence contains all positive integers not divisible by 3. Let us prove this by induction.
Suppose first that $x$ is divisible by 3, and $f(n) = x$. Considering the definition, we see that $x = 2f(n/2) + 3$, and so $f(n/2) = \tfrac{x-3}{2}$, which is also divisible by 3. By induction, this is impossible.
Suppose next that $x>0$ is not divisible by 3. If $x=1$ then $x$ appears in the sequence since $f(1) = 1$, so we can assume that $x \geq 2$. We now consider two cases: $x$ even and $x$ odd.
If $x$ is even then $\tfrac{x}{2}<x$ is positive not divisible by 3, and so by induction, $\tfrac{x}{2} = f(m)$ for some $m$. Then $f(2m) = x$.
Similarly, if $x$ is odd then $\tfrac{x-3}{2} < x$ is not divisible by 3. Furthermore, since $x \geq 5$, it is furthermore positive. By induction, $\tfrac{x-3}{2} = f(m)$ for some $m$. Then $f(2m+1) = x$.


Maximum number of matched vertexes in a one-to-many bipartite graph I have a variant of bidding problem at hand.
There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who are satisfied. A bidder is satisfied if he gets all the items that he bid for in the first place. For eg-

Bidders = A,B,C
Items = 1,2,3,4

Bidder    Bids
A         1,2
B         2,3
C         3,4

In this case its only possible to satisfy 2 bidders at max.

I've tried to model the problem to a maxflow problem and have taken several approaches but to no avail
My approaches so far-

Tried to model this problem as a bipartite matching problem. The only problem being that instead of a one-one mapping I have a one-many mapping with an AND condition.
A maxflow problem with edges going from source to each vertex with a capacity of number of bids. Problem here being ensuring that all edges from a bidder are selcted.
A maxflow problem with both upper bounded and lower bounded edge capacities.

Since your problem is exactly the set packing problem, it is NP-hard. However, you only have $n = 20$ bidders, so you can solve it using a simple exponential algorithm:

For every item $i$, build the subset $B_i$ of bidders that bid for it. You can represent this subset for example as a bitmask. You know that for all $i$, every subset $S \subset B_i$ with $|S| > 1$ can not be a subset of the solution.
For all $B_i$, enumerate all of its "forbidden" subsets of size > 1 and store them. Avoid revisiting already stored subsets by using recursion and memoization, by canceling the bits one after another.
Go through all subsets of bidders. For every set, check whether it has a a forbidden subset. You can use the same recursive algorithm as in step 2.

Note that if you only enumerate subsets of size 2 in step 2, you have reduced your problem to an independent set problem in a graph with $n$ nodes, so you can apply any other more efficient algorithm to it.

Runtime: $O(n \cdot (2^n + m))$, with $m$ being the number of items and $n$ being the number of bidders. With a good independent set algorithm you can get something like $O(m \cdot n^2 + 1.3^n)$


Counter Machine (Halting Problem) How can we show that Halting Problem for one-counter additive machines is decidable ?

A simple way is the following:

Suppose that the increments are $+1, -1$; the number of states of the machine is $m$ and the current value of the counter is $n$.

You can notice that if the counter reaches $n+m+1$ without hitting the $0$, then by the pigeonhole principle the machine from value $n$ to $n+m+1$ has entered the same  state $s_i$ two times ($s_i \to ... \to s_i$), and the difference in the counter value is positive; so it will continue to repeat the same loop and increase the counter.

After hitting the $0$ - for the same reason - if the counter reaches $m+1$ then the machine will never halt.

So it's enough to simulate the machine up to $m(n+m+1)$ steps; if it doesn't halt in that time it will never halt: it will loop forever on the same values  $(s_i,c_j) \to ... \to (s_i,c_j)$ or increase forever the counter: $(s_i,c_j) \to ...\to (s_i,c_k) \to ...;\; c_k > c_j+m$ .

If the increments are $\pm v, v \in [1,h]$ then the machine can be reduced to an equivalent one with $\pm 1$ increments.


On the robustness of BQP class Typically the notion of quantum Turing machine is introduced with its transition function.

$$
\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}
$$

Where $\mathbb{C}'\subseteq\mathbb{C}$ is a computable subset of $\mathbb{C}.$ This sort of definition basically gives any 1-qubit unitary gates "for free," you only need one step to perform any such unitary transform.

We knew that there's Solovay Kitaev theorem saying that any single qubit transformation could be approximated by a finite set of gates, but sometimes it still require more than $\Omega(1)$ gates to do this (grow with the precision). So it's natural to ask whether there exist an "efficient" approximation, so that when we're using just regular gates, the complexity would be roughly the same. (e.g. with only some polynomial amount of resources added up).

  Let's say we're given another QTM with transition $\delta'$ only allowing $O(1)$ gates as a generating set of a dense subset of $SU_2(\mathbb{C})$, then we redefine the $BQP_{\delta'}$ with it, is it the case that $BQP_{\delta'}=BQP_{\delta}$?

After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.


what is weak extensionality in $\lambda$-calculus? I was reading the book lambda calculi , encountered  an equality theory called "the rule of weak extensionality", which is shown as follows.

$\frac{M \, = \, N}{\lambda x.M \, = \, \lambda x.N}$

Yes, it is obviously true.

But why it is called the rule of weak extensionality? what is weak? what is extensionality here means?

I think the reason should be interesting.

There are different kinds of equality. Equality is said to be extensional when things are equal when their parts are equal, so to speak:

Equality the elements of $A \times B$ is extensional if, for all $u, v : A \times B$, $u = v$ if and only if $\pi_1(u) = \pi_1(v)$ and $\pi_2(u) = \pi_2(v)$. Here $\pi_1$ and $\pi_2$ are canonical projections. That is, $u$ and $v$ are equal if they have the same components (parts).
Equality of elements of $A \to B$ is extensional if, for all $f, g : A \to B$, $f = g$ if and only if $f(a) = g(a)$ for all $a : A$. That is, $f$ and $g$ are equal if they have the same values (parts).
Equality of sets is equal if, for all sets $S$ and $T$, $S = T$ if and only if $x \in S \Leftrightarrow x \in T$ for all $x$. That is, $S$ and $T$ are equal if they have the same elements (parts).

Equality which is not extensional is called intensional. For instance, if by $A \to B$ we mean programs (pieces of code) which take inputs $A$ and produce outputs $B$ then equality of functions could simply mean equality of the code.

The rules of the $\lambda$-calculus do not specify whether equality is extensional or intensional. They allow for both possibilities. With this in mind we see that it is not entirely clear whether the $\xi$-rule (that's what it's called)
$$\frac{M = N}{\lambda x . M = \lambda x . N} \tag{$\xi$}$$
should be part of $\lambda$-calculus. Normally it is, but we could envision a situation in which $\lambda x . M$ gets compiled differently from $\lambda x . N$ for some reason. So much about it being "obviously true".

Personally, I would not call the $\xi$-rule "weak extensionality" because that conveys the wrong idea. It is a congruence rule expressing the fact that $\lambda$-abstraction preserves equality. Another congruence rule is
$$\frac{M_1 = M_2 \qquad N_1 = N_2}{M_1 N_1 = M_2 N_2}.$$

If we insist, we can think of the $\xi$-rule as weak form of extensionality in the sense that two $\lambda$-abstractions are equal if their bodies (parts) are equal.


strong reduction of $\lambda$-terms, useful? As we know many programming languages and systems don't implement the strong reduction  of $\lambda$-terms, instead they do weak reduction (no reduction under abstraction).

I recently experimented several tests on $\lambda$-terms. I applied strong reduction and call by value reduction on them.

strong reduction took longer time even the size of the term is moderate.
call by value reduction is very fast.

I believe if we ignore inefficiency, strong reduction is more useful than weak one.
These are what I felt from my experiments. That makes me think about some questions. here I would like to share them with you.

programming languages or other systems do not implement the strong reduction because it is inefficient (takes more time)?
programming languages or other systems don not implement the strong reduction because it is difficult to do?
which one is the reason, or something also?

There are several possible answers to your question:

1) Strong reduction is not implemented because it is not that useful: why take the trouble to reduce a term with un-instantiated variables when you'll have to go back in later to do the reduction when the variables get values anyway? And if the variables never get instantiated, then you've wasted your time entirely! More generally, it's easier to compute with concrete values than symbolic ones.

2) Strong reduction is implemented, because it is useful. It's just that this is usually done at compile time: inlining and constant propagation is just that, a way to do strong reduction.


How to find out what are accept, loop and reject in this Turing Machine? I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about...

so accept state would be --> Accept(T2) - all words with a a
                      loop state would be --> Loop (T2) - /\

reject state would be --> Reject(T2) - Strings with b

am I on a right track ? how could I do find accept, loop and reject on this TM? thanks!

Yuval's answer applies to your machine T$_2$. With his assumptions, we have the following behavior for your T$_1$ on possible inputs:

It will reject the empty string, since there is no move defined on the "blank" symbol.
It will not accept any string consisting only of $a$ characters, since it won't reach the HALT state.
It will accept $a\dots ab$, since it will reach the HALT state.
If the input is a single $b$, it will enter the HALT state and will then fall off the left end of the tape. Whether that should lead to acceptance or rejection depends on your definition of "accept" and "reject".
Whether it will accept a string like $aba$ or $abb$ will depend on your definition of "accept", since in these cases it will enter the HALT state and will never process the characters beyond the first $b$.
There is no loop state, at least under Yuval's and my interpretation.

You need to look closely at your local definition of a TM, since there are several forms they might take and of course we have no way of knowing what definitions you're using.


Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.

Assume there are are at least 3 connected components. Then there must be a connected component of size $\le\frac{n}{3}$. Let $v$ be a vertex in that connected component. By assumption we have $deg(v)\ge\frac{n-2}{3}$. Since the size of that connected component is at most $\frac{n}{3}$ than it must be that $deg(v)\le\frac{n}{3}-1=\frac{n-3}{3}$. So we get both $deg(v)\ge\frac{n-2}{3}$ and $deg(v)\le\frac{n-3}{3}$, a contradiction. Thus, there must be at most 2 connected components.


Given two sorted arrays check if one is subset of another Question: Given two sorted arrays A1 and A2, check if A2 is a subset of A1. Also, assume there might be duplicates.
Example:
 A1 = [0,0,0,0,1], A2 = [0,1] // should return true
 A1 = [-1,0,1,2,3,4,5], A2 = [1,2,3] // should return true

Answer: My answer is below and works, but I believe my running time is slow. Not sure if there is another algorithm I can leverage.

FYI: this is not for school or project, just curious with solving problems.

function isSubArrayOfAnother(a1, a2) {
        if (!a1 || !a2 || a1.length === 0 || a2.length === 0) {
            return false;
        }

    let loc = a1.indexOf(a2[0]);
    let allIndexes = [];

    while(loc > -1) {
        allIndexes.push(loc);
        loc = a1.indexOf(a2[0], loc + 1);
    }

    for(var i=0; i<allIndexes.length; i++) {
        let isMatch = true;
        let tempIndex = allIndexes[i];
        for (var j = 0; j< a2.length; j++) {
            if (a2[j] !== a1[tempIndex++]) {
                isMatch = false;
                break;
            }
        }
        if (isMatch)
            return isMatch
    }
    return false;

}

There is a O(n) solution to this.

Finding all possible start index of the subset can be eliminated

while(loc > -1) {
    allIndexes.push(loc);
    loc = a1.indexOf(a2[0], loc + 1);
}

And, there seems to be an edge case where it will attempt to access element out of the array's bounds. I mean, the input like the one below

A1 = [-1, 0, 1, 3, 1, 2], A2 = [1, 2, 3]

The below pseudocode-like is a starting point, there is still optimisations left in this algorithm.

Given array A, find the presence of sub array B,

matchPointer = 1
for i = 1 to A.length
  if A[i] == B[matchPointer]
    if matchPointer == B.length
      "Subset Found"
    matchPointer = matchPointer + 1
  else
    matchPointer = 1;


Construction of graph with given Wiener Index Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be created?

This question is addressed on the Wikipedia page Wiener index. Gutman, Yeh and Chen showed that there are no (unweighted) graphs with Wiener index 2 or 5, but all other values are attainable. In a subsequent paper, Gutman and Yeh determine which Wiener indices are attainable on bipartite graphs, and on the way explain how to prove the earlier result, an explanation which we reiterate here.
Consider the clique on $n$ vertices. Its Wiener index is $\binom{n}{2}$. Pick a vertex $v$ from the clique. Suppose we remove $m$ edges $(x_1,y_1),\ldots,(x_m,y_m)$ not adjacent to $v$. Since $x_i,y_i$ are connected via $v$, each edge we remove increases the Wiener index by one, and so the resulting Wiener index is $\binom{n}{2} + m$. The maximal number of edges we can remove is $\binom{n-1}{2}$, which corresponds to a Wiender index of $\binom{n}{2} + \binom{n-1}{2} = (n-1)^2$. We deduce that for every $n$, there are graphs having Wiener index $\frac{n(n-1)}{2}$ to $(n-1)^2$. Let's list these ranges for small $n$, starting with $n = 2$:
$$ [1,1], \; [3,4], \; [6,9], \; [10,16], \; [15,25], \ldots $$
Denoting the intervals as $[a_n,b_n]$, starting with $n=5$ we have $a_{n+1} < b_n$, which is not hard to check directly. Therefore, in this way we can construct graphs of any Wiener index other than $2$ or $5$.
It remains to rule out 2 and 5. First, note that a graph of $n$ vertices has Wiener index at least $\binom{n}{2}$. Since $\binom{4}{2} = 6$, it is enough to consider all graphs on at most 3 vertices:

A path of length 1 has Wiener index 1.
A triangle has Wiener index 3.
A path of length 2 has Wiener index 4.

These are the only connected graphs on at most 3 vertices.


A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold? I'm looking for a data structure that supports efficient:

Insertion of arbitrary integers.
Value lookup (given a particular value needle, return true if it's currently in the structure).
Removal of all values below a given threshold integer.

I suspect this can be with a self-balancing BST, with insertion and lookup both costing log(n) time. I think the removal operation can be done by pruning an entire subtree out, but I'm not sure this can be done in log(n) time while keeping the tree balanced. If we remove a very large subtree (say the left child of the root node), it seems like it would take basically rebuilding the entire tree, which is O(m log m) with m being the number of remaining nodes, and at any rate no less than O(m).
A cheaper approach would be to use a naturally-ordered self-balancing BST. For removal, we can just start at the smallest node, and keep removing (and rebalancing) until we run out of nodes or hit the threshold. This will cost O(m log n) where m is the number of nodes to be removed.
Bonus question: what if instead of removing below a threshold, we need to support removal of all nodes in a range between upper_bound and lower_bound?

If you accept randomized algorithms you could use TREAP. This data structure is BST where each node is augmented with priority, a random number. The only one invariant over normal normal BST is that parent's priority must be greater than children's. This results in a very simple implementation of Insert and Delete functions (recursive variant is 10-15 lines of clean C code).
The complexity of basic operations is $O(\log N)$ on average.
It is possible to cut-off all nodes below threshold in $O(\log n)$ time assuming that nodes below the threshold are not disposed.
Node cut(Node node, int threshold) {
   if (node->key < threshold) {
      // optionally dispose node, and subtree at node->left
      return cut(node->right, threshold);
   }
   node->left = cut(node->left, threshold);
   return node;
}

root = cut(root, threshold);

Note, that there is no rebalancing because the node is replaced by one of its children (or subchildren). As result the priority invariant in satisfied.
Disposal of nodes with a key below the threshold will increase complexity to $O(k + \log n)$, where $k$ is a number of disposed nodes.
Cost of disposal will be amortized to $O(1)$ over multiple operations because each node is created and disposed only once.
Removal of nodes above a given threshold will require symmetrical functions.


Compare log^k(n) with n^(1/2) I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that:

$$\lim_{n \rightarrow \infty} \frac{\log^{k}(n)}{\sqrt{n}} = 0$$

And apparently $\log^{k}(n) \in O(\sqrt{n})$, but by trying to solve this limit on paper in order to reach an appropriate proof I would need to keep applying L'Hospital rule indefinitely. Is that what I suppose to be doing? How could I proceed to build this proof?

Yes. Using L'Hospital:

$\lim_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^{k-1} (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdots  2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \frac{k!}{\sqrt n} = 0$

I hope I got it right, quite some time since I've used it. I^ve left out the $\frac{1}{2}$ from the $\sqrt n$


L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma L ={ $a^{m^n}$ | $m$>$n$ }
I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR  L = $a^{\left(m^n\right)}$.

If it is considered as L = $(a^m)^{n}$ then want to check it is Regular or not by Pumping Lemma.
I tried by following way.

$m$ > $n$ so we can take $m's$ value as $n+1$.
So $L$  = $(a^{n+1})^{n}$

Let n be the Pumping Lemma Constant.
Then by pumping Lemma $u$$v^{i}$$w$ in $L$ for every $i$ $>=$ $0$.

$1<= |v| <= n$

$uv <= n$.

So here $u$ = $(a^{n+1})^{n-1}$

$v$ = $(a^{n+1})^{i}$  and

w = $\epsilon$

By taking $i = 2$ ,
I am getting string as $(a^{n+1})^{n+1}$Which is not possible. Because it means $m=n$.
So above string is not Regular.

But different solutions giving different answers. So confused whether it is Regular or not. And is there any problem in my solution ?

Let $A = \{ m^n : m > n \}$, so that $L = \{a^k : k \in A\}$. It is not clear whether $m,n \geq 0$ or $m,n > 0$. In both cases, every $m > 2$ is in $A$ and $0 \notin A$. If $m,n > 0$ then $1 \notin A$, while if $m,n \geq 0$ then $1 \in A$. In the former case, $L = aa^+$, and in the latter, $L = a^+$. In both cases $L$ is actually regular.

We can also consider the other interpretation, $A = \{mn : m > n\}$; this interpretation is wrong, but it can shed light on your proof. Again we find that every $m > 2$ is in $A$, and that $1 \notin A$. If $m,n$ are allowed to be zero then $0 \in A$, and otherwise $0 \notin A$. In the former case $L = aa^+ + \epsilon$, and in the latter, $L = aa^+$. In both cases $L$ is regular. So something must have been wrong with your proof.


Can we call deterministic equivalent of all NFA to be finite Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we always call the deterministic equivalent to be a finite automata just by saying that as n is finite 2^n will also be finite even though the actual memory will be very large or is there some limitation?

Finite automata is defined as a simple machine having small memory.

In fact, they are not defined in this way. You can look up the actual definition on Wikipedia. Even as an informal definition, the adjective small is inappropriate here — in fact, DFAs and NFAs have constant memory.

You are using the letter $n$ to represent the number of states in a finite automaton. The letter $n$ is usually reserved for the input length. The number of states in a finite automaton doesn't depend on the length of the input. On the contrary, the number of states is fixed ahead of time, and the finite automaton then uses exactly the same number of states for any input, of any length. Perhaps it will be less confusing if you use a different symbol, say $m$.

  ... the actual memory will be large ...

In theoretical computer science, there are no arbitrary constants thrown around. Today, $2^{50}$ bytes of memory can be considered large, but next year it might be $2^{60}$ bytes of memory. The same theory should account for both. In theoretical computer science, the formal meaning of large (or, more accurately, super-constant), is "tending to infinity with $n$", where $n$ is the input length. Finite automata use a fixed amount of memory which is independent of the input length, and so they never use a large amount of memory, as far as theorists are concerned.

In practice, some automata are too big to actually implement. But this is a practical restriction rather than a restriction on the actual definition.


Floating point precision from rearranging equation When I run $x^2 - y^2$ with x=8.8888888888 and y=9.9999999999 in python, I get the following result:

>>> 8.8888888888**2 - 9.9999999999**2
-20.9876543205679

However, if I rearrange it to $(x-y)(x+y)$ with the same x and y values, I get:

>>> (8.8888888888 - 9.9999999999) * (8.8888888888 + 9.9999999999)
-20.987654320567895

It seems that the two equations, though logically equivalent, give varying amounts of floating point precision by a difference of 2 digits.  What could be causing this?

First of all, the different numbers of digits are misleading. The two numbers store the same amount of precision; Python is just leaving off final zeroes.

However, there is a loss of precision here, and it comes down to the intermediate results.

Floating-point values aren't infinitely precise, and the larger their absolute value, the fewer places they can store after the decimal point. (Hence the name "floating point": one way to think of floating point numbers is that they're a fixed number of digits long, but you can move the decimal point back and forth to represent both really big and really small values.)

When you compute 8.8888888888**2, you're effectively using more of the available bits to store things before the decimal point. So there are fewer left over to store things after the decimal point. It gets less precise.

When you instead compute 8.8888888888 - 9.9999999999, you're not using those extra bits before the decimal point, so they can all be devoted to the part after the decimal point.

(Note: this is an intuitive explanation, not a technical one. The essence is correct, but the details are somewhat handwaved. If you want more technical details, look into how an IEEE float is stored.)


How can you represent a Huffman-tree in Hex? I was trying to store a Huffman tree in a binary file recently. I thought it wouldn't be a big problem since you actually have the binary codes already in front of you.
Well, the difference is that the file (in the hex editor) is logically coded in hex. So I tried to convert the "characters" from binary to hex. Without any success.
Let's take this tree as an example:

My first attempt was to simply convert Binary to Hex. So for example 01 became 0x01. But there is a problem now: There are duplicates. So 01 as well as just 1 both became 0x01.
So I couldn't use that. I also tried to just represent the  zeros and ones in hex, for example: 10 1... (The equivalent of 1 01) but that wouldn't be really efficient anymore.

So how could I now make a Huffman tree in Hex? Would I maybe even have to use a different encoding?
I hope I could describe my problem well enough.

This practical problem comes up in JPEG, where you can define your own Huffman tables. The codewords are limited to 16 bits, and the table is stored as follows:

For $\ell=1,\ldots,16$, the number of codewords of length $\ell$ bits.
For each $\ell$, a list of the values encoded by the codewords of length $\ell$.

The codewords themselves need not be stored, since a Huffman code can be extracted from this description. See Imran Nazar's notes.


Grammar for $L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}|i,j>0\}$ I'm supposed to write grammar for this language: $$L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}\mid i,j>0\}$$
This is what I have so far:
$$\begin{align}
S &\to aXbY \; \\
X &\to aXb \;|\; a \\
Y &\to ccYdE \;|\; ccdE \\
Ed &\to dE \; \\
dE &\to dee \; \\
eE &\to eee \; \\
\end{align}$$
Edit:
Thank you for answers, I looked at the https://en.wikipedia.org/wiki/Noncontracting_grammar#Example and edited my grammar:
Is this correct? Is it necessary to do
$$\begin{align}
Ed &\to dE \; \\
dE &\to dee \; \\
eE &\to eee \; \\
\end{align}$$
or can I just do
$$\begin{align}
Ed &\to dee \; \\
E &\to ee \; \\
\end{align}$$

Your answer is correct.
The alternative with $E\to ee$ is incorrect, as it might generate 'ee' in between 'd's. You must first shift all the E's to the end and only then make them into $ee$.
I would generate $cc$ and $ee$ together, and play with the $D$'s, i.e., $Y\to cc YD ee$, etc. This will be slightly more simple, though equivalent.


Are asymptotic lower bounds relevant to cryptography? An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be secure.

However, an asymptotic lower bound does not rule out the possibility that a huge but finite class of problem instances are easy (eg. all instances with size less than $10^{1000}$).

Is there any reason to think that cryptography being based on asymptotic lower bounds would confer any particular level of security? Do security experts consider such possibilities, or are they simply ignored?

An example is the use of trap-door functions based on the decomposition of large numbers into their prime factors. This was at one point thought to be inherently difficult (I think that exponential was the conjecture) but now many believe that there may be a polynomial algorithm (as there is for primality testing). No one seems to care very much about the lack of an exponential lower bound.

I believe that other trap door functions have been proposed that are thought to be NP-hard (see related question), and some may  even have a proven lower bound. My question is more fundamental: does it matter what the asymptotic lower bound is? If not, is the practical security of any cryptographic code at all related to any asymptotic complexity result?

I'll try to give a partial answer, since I'm not fully aware of how this issue is considered by the entire crypto-community (maybe repost on crypto.SE?).

I would say there are two "kinds" of cryptographers: Theoretical and  Practical. I will not try to tell them apart (every practical-cryptographer is also a bit theoretician..) but I'll say that for theoretical cryptography - this issue doesn't really matter. For any security parameter, there will be an instance size that will provide that security level, and that is usually all that we care about.

Practical cryptographers care a lot about the issue you mention. For a given security parameter (say $2^{1024}$) cryptographers try to come up with the most efficient protocols, shaving the constant as much as possible. Look for instance for NIST's AES or SHA-3 competition. The algorithms were required to be both secure and efficient.
The issue here is that the notion of security is somewhat different from the "theoretical" one, and sometimes is not really asymptotic.

A concrete example I can think of is the discrete log or the DDH assumption (the security of many cryptographic schemes are based on these assumptions). We assume that for some group $G$ computing the log takes $O(|G|)$ time. (We can't be sure: it might be that $\text{P}=\text{NP}$ and this problem can be solved in $O(\log |G|)$). Cryptographers DO care about the actual time it takes to compute the log. More accurately, they care alot about special cases for which computing the log is easy. In many papers you will see the sentence "Let $G$ be a group in which DDH
is hard". See this survey for families of groups for which DDH is believed to be intractable (unless P=NP).


Is the intersection of two regular languages regular? Trivially decidable problem is one in which the problem is a known property of the language/grammar. So  intersection of two regular languages is regular should be trivially decidable? But it is given as not trivially decidable.

Summarizing the discussion, the intersection of two regular languages is always regular, and so "trivially decidable".


How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)? This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=[0100001\dots 01]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x_i + x_j + \dots + x_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\{0,1\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C_0 = [0\dots 0], C_1 = [0\dots 0 1]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b_i + b_j + \dots = 1$?", where $b_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A_i$ and $B_i$ where $|A_i| = |B_i|$ and ask questions of the form "is $x$ of type $A_i$ or $B_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that any size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}_{2^k}$ for $k>1$.


Big O: Nested For Loop With Dependence I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to understand it:

sum = 0;
for (i = 0; i < n; i++
    for (j = 0; j < i; j++)
        sum++;

The part that's throwing me off is the j < i part. It seems like it would execute almost like a factorial, but with addition. Any hints would be really appreciated.

So let me clarify a few things, you are interested in the big-O notation - this means upper bound. In other words, it is okay to count more steps than you actually do. In particular, you can modify the algorithm to

 ...
    for (j = 0; j < n; j++)
 ...

So you have two nested loops, each loop runs $n$ times, which gives you an upper bound of $O(n^2)$

Of course, you would like to have a good estimate for the upper bound. So for completion, we want to determine a lower bound. This means its okay to count less steps. So consider the modification

for (i = n/2; i < n; i++)
    for (j = 0; j < n/2; j++)
        sum++;

Here, we perform only a some of the loop-iterations. Again we have two nested loops, but this time we have $n/2$ iterations per loop, which shows that we have at least $n^2/4$ additions. In this case we denote this asymptotic lower bound by $\Omega(n^2)$. Since the lower and upper bound coincide, we can even say that $n^2$ is a tight asymptotic bound, and we write $\Theta(n^2)$.

If you want to know more, read here.


Making a profit as a high-dimensional store owner? Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.

Let's say that I am some business owner with a set of $n$ possible store locations $L = \lbrace x_i \in \mathbb{R}^m \rbrace_{i=1}^n$, for $m > 1$, where I'd like to build some new stores. I have estimates that each location $x_i$ will cost $c_i$ to build and should make a corresponding profit $p_i$ after opening. Further, I have a budget of $B$ that I cannot exceed and all stores I build must be at least a distance $D$ away from each other based on the metric $d(\cdot,\cdot)$. My goal is to build stores such that I maximize my profit and stay within the desired constraints. Note that $(L,d)$ is a metric space.

Define $S = (s_1, s_2, \cdots, s_n) \in \lbrace 0, 1 \rbrace^n$ such that $s_i = 1$ means I am building a store at location $i$ and $s_i = 0$ means I am not. It is clear that this optimization problem can be posed as:

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\&\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\& && d( x_j, x_i ) \geq D \hspace{1cm} \forall j > i \geq 1 \text{ where } s_i = s_j = 1 \end{align*}

Now when looking at this problem, it is quite simple to solve it using dynamic programming if we assume the store locations are far enough apart that the distance constraint is automatically satisfied or the locations are all contained within some 1-dimensional affine subspace. Outside of this, things seem a bit complicated.

My thought is to initially construct a graph $G = (V,E)$ such that $V(G) = \lbrace 1, \cdots, n \rbrace$ and $E(G) = \lbrace ij \;|\; d(x_i, x_j) \geq D \rbrace$. From here, a simple but inefficient idea is to enumerate all cliques of $G$, solve them using dynamic programming, and choose the solution, across all of them, that's the best. This should be fine because each clique, by construction, is comprised of store locations that satisfy the distance constraints and in turn should individually allow for efficient solutions. This might be formalized by defining $\lbrace C_1, C_2, \cdots, C_p \rbrace = \text{cliques}(G)$ as the set of cliques of $G$ and then solving

\begin{align*}& &&\max_{S^{(j)} \in \lbrace 0, 1 \rbrace^n} \sum_{i = 1}^n p_i s_i^{(j)} \tag*{}\\&\text{subject to} &&\sum_{i = 1}^n c_i s_i^{(j)} \leq B\\& &&s_i^{(j)} = 0 \hspace{1cm} i \in V(G) \setminus V(C_j) \end{align*}

for each $j^{th}$ clique $C_j$. From here we then choose $S^* = \arg \max_{j \in \lbrace 1, \cdots, p \rbrace} \sum_{i=1}^n p_i s_i^{(j)}$ as the optimal solution for the overall problem.

Obviously the crappy thing about the above approach is that we have to enumerate all the cliques, which may be both a large set and computationally demanding to find. Is there any structure to the problem I am missing that might make this solvable without enumerating all the cliques in this formulation? Perhaps there's a different perspective that could shed some light?

I'm not sure why you would need to enumerate the cliques. You can encode the distance constraints explicitly in just a quadratic number of constraints.

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\
&\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\
& && s_i + s_j \leq 1 \hspace{1cm} \forall j > i \geq 1 \text{ where } d(x_i, x_j) \leq D \end{align*}


Giving a regular grammar for the language I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve this.

I want to give a regular grammar for the language of the finite automaton whose screenshot is below, please help me, and if you can, a step by step answer would be of great assistance. Thank you!

That's fairly easy. Just take a non-terminal X and add the rule $X\to aY$ where $a$ is the label on the arrow from $X$ to $Y$ if $X$ is not final; if it's final add a rule like: $X\to \epsilon$ as well. Do that for every non-terminal and you get a right-regular grammar.

Here is a right-regular grammar for the given automaton:

$A \to 1 A$

$A \to 0 B$

$B \to 1 A$

$B \to 0 C$

$C \to 0 C$

$C \to 1 C$

$C \to \epsilon$


Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$ Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a constant, it's really difficult to apply tree method and master theorem here. Any hint? My thought is that let $c = \sqrt{n}$ such that $c^2 = n$ so we have $T(c^2) \leq cT(c) + c^2$ but I does not look good.


Knapsack with same value I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight constraints.

Maximize $\sum_{j=1}^nx_j$

subject to $\sum_{j=1}^nw_{ij}x_j\leq W_i$ for $1\leq i\leq m$

and $x_i=0,1$.

This is a special case of multidimensional knapsack. I've looked at the list of knapsack problems, but the only one with uniform value is not multidimensional but instead wants the sum of weights to be exactly $W$. Is there some reference for the version I described?

Your problem appears to be a special case of integer programming where the variables are boolean. I could not find it on wikipedia, but a lot of course materials online introduce this problem as Capital Budgeting problem under different models of integer programming. Hope it helps.


Finding connected components without building the graph first What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in X is itself a set of features f and a Boolean connectivity function (defined by generalization/subsumption) c(x,x')?
c(x,x') = True if generalizes(x,x') or generalizes(x',x) else False
generalizes(x,x') = True if x-x'==set([]) else False
The point is not to build the entire graph (partially ordered set) in the first place but to use c(x,x') as an oracle to query while computing component labels on the fly.
This can also be seen as finding weakly connected components of the DAG given by the partial order of the subset relation, but I think perhaps for this algorithm it could be better to have c return True more often, so I view the DAG as undirected and then define the task.

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive.
From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:
component = 1
mark = array of size n; initialized with 0
for i = 1 to n:
  if mark[i] == 0:
    mark[i] = component
    for j = i+1 to n:
      if i != j and mark[j] == 0 and c(X[i],X[j]):
        mark[j] = component
    component += 1

$mark$ now assigns every node a component.
The runtime of the algo is $O(cn)$ where $c$ is the number of components.
This would usually considerably faster than a dfs.
Notice in the worst case every node is its own component leading to $O(n^2)$.
But if this even occurs depends on the properties of your $c(x,y)$ function.
EDIT: The algorithm doesn't work since c(x,y) isn't transitive. My bad.


Why use minhash instead of directly computing Jaccard coefficient? Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute.

But isn't it possible to also compute the Jaccard coefficient $\frac {|A \cap B|} {|A \cup B|} $ in $O(|A|+|B|)$ time by simply doing :

1  Given collections A' and B', create hash set datastructures A and B from them.
2. foreach(a in A){ if(a in B)sizeOfIntersection++; }
3. sizeOfUnion = A.size() + B.size() - sizeOfIntersection;
4. Jaccard = sizeOfIntersection / sizeOfUnion;

Assuming [an ammortized] O(1) hash set membership lookup, the complexity of the above is O(|A|+|B|), which is less than with k hash-function minhash.

So how is Minhash more efficient, and what benefit does it provide?

If you only have two sets $A,B$, then you are right: there is no point computing the minhash.

But now suppose you have sets $A_1,A_2,\dots,A_n$, and you want to know whether there exists any pair $A_i,A_j$ with high Jaccard similarity.  It's more efficient to compute the minhash of each $A_i$ once, and then use that to help you look for a pair that hash high Jaccard similarity.  As a trivial observation, once you've already computed the min-hashes of them all, then estimating the Jaccard similarity of $A_i,A_j$ can be done in $O(k)$ time using the existing minhashes, which can be significantly faster than the naive  $O(|A|+|B|)$-time method.

(In fact, once you have the minhashes of all of the sets, there are even cleverer ways to look for pairs $A_i,A_j$ with large similarity.)

This is even mentioned on the Wikipedia page for Minhash: see the section labelled Time analysis.  However, you do have to read it pretty carefully to get the point.


Product construction for given two finite automata I need to construct a finite automata which accept a language $L =  L_1 \cap L_2$, where $L_1$ and $L_2$ are given below.

$L_1 = \{  w \mid w $ is divisible by 2 }

$L_1 = \{ w  \mid w $ is divisible by 3 }

I know how to design a finite automata for a single number but how do I combine the automatons which check divisibility by 2 and 3? I am able to combine the initial states of the two automatons by using ϵ transitions from a new state but how can I combine the final states of the two automatons? Input is in the set of decimal numbers Σ = {0,1,2,3,4,5,6,7,8,9}

Here is a product construction for finite automata. I am considering you have two finite automata $M_1$ and $M_2$.
Let $M_1$ = $(Q_1,\Sigma ,\delta_1,q_{01},F_1)$ and $M_2$ = $(Q_2,\Sigma ,\delta_2,q_{02},F_2)$ be two finite automata with the same input alphabet.
Let us define $M$ such that

$$L(M) = L(M_1) \cap L(M_2) $$

Finite automata for $L(M)$ is defined as $M$ = $(Q,\Sigma ,\delta,q_0,F)$ , where
$Q$ is a finite set of states, $\Sigma$ is a input alphabet, $q_0$ is a start state, $\delta$ is a transition function and $F$ is final state of a finite automata $M$.

$Q$ = $Q_1$ X $Q_2$ (Cartesian product),
$\delta((q_1,q_2),a) = (\delta_1(q_1,a),\delta_2(q_2,a))$,
$q_0 = (q_{01},q_{02})$,
$(q_{1},q_{2}) \in F $ iff $q_1 \in F_1 $ and $q_2 \in F_2$.

Each state in $Q$ is a pair consisting of a state from $Q_1$ and a state from $Q_2$.
Reference : the Product Construction for Automata by Laura Kovács.


How do I show T(n) = 2T(n-1) + k is O(2^n)? This is a practice problem I've come up with in order to study for an exam I have in a couple of hours.

Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant.

First of all, 2^n is indeed the upperbound, right? Since I've made this problem up myself, I'm not 100% sure, but from what I have seen, this should be O(2^n).

If so, here's my progress:

We want to show P(n) is true for all n > n0, where P(n) is the statement "T(n) <= c * 2^n" (for some fixed c, to be determined)

For now, let's fix c at T(1).

Base case: n = 1

We want to show T(1) <= c * 2. Since c = T(1), our equation becomes T(1) <= T(1) * 2, which is trivially true.

Inductive step: Assume P(n - 1) is true for n > 1. We want to show that P(n) holds.

T(n) = 2 T(n - 1) + k, by definition
    >= 2 (c * 2^(n-1) ) + k = c * 2^n + k

Here's where I get stuck. How can we possibly show that c * 2^n + k <= c * 2^n for any value of c? Did I make a mistake somewhere?

In this case, your best bet is to just solve the recurrence by direct substitution.

$$\begin{align*}
T(n) &= 2T(n-1) + k \\
     &= 2\big(2T(n-2) + k\big) + k \\
     &= 2\big(2\big(2T(n-3) + k\big) + k\big) + k\\
     &= \cdots\\
     &= 2^rT(n-r) + k\sum_{i=0}^{r-1} 2^i\\
     &= 2^rT(n-r) + k(2^r-1)\,.
\end{align*}$$

Putting $r=n$ gives
$$\begin{align*}
T(n) &= 2^nT(0) + k(2^n-1) \\
     &= 2^n(T(0) + k) - k \\
     &= O(2^n)
\end{align*}$$
since, although you forgot to define $T(0)$, it is a constant and so is $k$.


Techniques (tools) to convert temporal logic (CTL,CTL* or LTL) to μ-calculus formulae Suppose one wants to use a μ-calculus model checker, but specify things in temporal logics, which is easier (more intuitive). Is there a technique (even better, a tool) that automatically translates formulae in any of these logics (CTL,CTL* or LTL) to the μ-calculus?

Thanks very much in advance!

You may find an answer or at least relevant references in the article
A linear translation from LTL to the first-order modal $\mu$-calculus.


How to solve Tower of Hanoi iteratively? It may seem obvious to many but i am having a hard time figuring out the iterative solution to the Tower of Hanoi problem. There are some solutions on the Internet but without explanations. So can anybody give a sound explanation so that it becomes more intuitive and easy to reason.

You can transform the recursive solution to an iterative solution. To do this, create a stack that will contain items consisting of quadruples ("from", "to", "via", "num_disks"). For every function "call" in your recursive algorithm, push the parameters to a stack in the iterative algorithm. For every function "return" in your recursive algorithm, pop the parameters from the stack in the iterative algorithm.

Wikipedia has the complete iterative solution.


Understanding the fundamentals of building an in-Memory Distributed Graph I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple nodes in a network.

I know basic graph data structure. I googled to know about distributed graph, but what I found mostly is just an info about existing distributed graph databases like titan, FlockDB etc. But I really couldn't find any fundamental guide to building a distributed graph or in general explaining a basic algorithm of building a distributed graph.

Can you please suggest few references where I can get such material explaining the fundamentals.

You should look at the Cloud Computing area - there is a lot of research about graphs representation and processing there.

For example, this paper.


Program interpretation for static analysis Are there any implementations, or even academic work, regarding an application capable of looking at code and inferring what the code actually intends to do? For example, we give it a program that calculates the SQRT(x); it should go and annotate that particular piece of code with SQRT(X), regardless of implementation technique. Say you use recursion instead of a for loop; it should still be able to infer what the code intends to do. Pattern matching is not really an option here.

Another example: Say you have a program that computes the sum of inverse squares, starting at 0. It should print out the mathematical equivalent of that expression as result. Something like SIGMA 1/x^i

It's been hinted at in the comments, but in general, the task of giving non trivial explanations of an arbitrary piece of code by some automated analysis is impossible.

The first issue is giving a well-defined meaning to the term "program intent". The field of operational semantics can give us a precise definition of what a piece of code actually does when run on a concrete computer, under the hypothesis that the compiler or interpreter is free of programing errors, but the intent of the person who wrote the code can obviously not be divined from the code itself, e.g. a piece of code may be intended to say, crash if given a negative number as input, or that outcome may be the result of programmer oversight.

However it might be desirable to, say, infer various mathematical properties of an arbitrary piece of code, in your example you might want to infer

forall x, if x > 0 then SQRT(x)*SQRT(x) == x

This also is impossible to do in general. This somewhat surprising fact can be demonstrated using Rice's theorem, which essentially says that any property like the above statement can not be proven or refuted automatically for arbitrary programs.

That being said, there has been a substantial body of work which aims at identifying and proving properties such as the above for concrete program implementations. Because of Rice's theorem, such attempts must be incomplete, but in practice much can be done for "real world" programs. This field is usually designated under the term formal methods, and even a short summary would be significantly more effort than I'm ready to put forward right now. A good overview can be found here.


Find the error in the following “proof” that $O(n) = O(n^2)$ Let $f(n) = n^2 , g(n) = n$, and $h(n) = g(n)−f(n)$. It is clear that $h(n) ≤ g(n) ≤ f(n)$ for all $n ≥ 0$. Therefore, $f (n) = \max(f (n), h(n))$. Thus,
$O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n), h(n))) = O(f(n)) = O(n^2)$.

Can you explain why this statement is wrong?

You're basically claiming that $O(n^2+n-n^2)$ is the same thing as $O(n^2)$, and that's not true.


Identity types and universes Let us consider Martin-Löf type theory with a cumulative hierarchy of universes
$$
\mathcal{U}_0\colon\mathcal{U}_1\colon\ldots
$$
If $A, B\colon \mathcal{U}_i$, we can form an identity type $A=_{\mathcal{U}_i} B:\mathcal{U}_i$. Using the axiom of cumulative hierarchy, we can derive $A, B:\mathcal{U}_{i+1}$, so we have also an identity type $A=_{\mathcal{U}_{i+1}}B$. Assuming the Univalence axiom (for all the universes), they are both equivalent to a type of equivalences $(A\simeq B)$, which has nothing to do with universe issues. What can we say about the relationship between types $A=_{\mathcal{U}_i} B$ and $A=_{\mathcal{U}_{i+1}} B$ without the Univalence axiom?

In general cummulative universes are a bit nasty. To see what is really going on, at the very least it makes sense to have explicit lifting maps $\mathsf{lift}_{i,j} : \mathcal{U}_i \to \mathcal{U}_j$ for $i \leq j$. With these in place, your question is: how do the types
$$\mathsf{lift}_{i,i+1}(A =_{\mathcal{U}_i} B)$$
and
$$(\mathsf{lift}_{i,i+1} A) =_{\mathcal{U}_{i+1}}(\mathsf{lift}_{i,i+1} B)$$
relate?
The answer is: unless we make further assumptions, we cannot show them to be equivalent. In fact, when type theory is given with explicit $\mathsf{lift}_{i,j}$ maps, we include judgemental equalities which say "lifting maps commute with type constructions", such as, for $i < j$,
$$\mathsf{lift}_{i,j}(A =_{\mathcal{U}_i} B)
\equiv
(\mathsf{lift}_{i,j} A =_{\mathcal{U}_{j}} \mathsf{lift}_{i,j} B).$$
These sorts of details are usually skipped in informal presentations of type theory. In particular the HoTT book is a bit sloppy on this point. (But the formalizations of HoTT in Coq, Agda and Lean are not.)


How to filter a very, very large file I have a very large unsorted file, 1000GB, of ID pairs

ID:ABC123 ID:ABC124
ID:ABC123 ID:ABC124
ID:ABC123 ID:ABA122
ID:ABC124 ID:ABC123
ID:ABC124 ID:ABC126

I would like to filter the file for

1) duplicates

example
ABC123 ABC124
ABC123 ABC124

2) reverse pairs (discard the second occurrence)

example
ABC123 ABC124
ABC124 ABC123

After filtering, the example file above would look like

ID:ABC123 ID:ABC124
ID:ABC123 ID:ABA122
ID:ABC124 ID:ABC126

Currently, my solution is this

var hash;

foreach line in file
      get ID1
      get ID2

      if exists in hash ID1ID2 or exists in hash ID2ID1
        //next line, as we have already have this in our collection
      else
         add to hash ID1 ID2
         print the line

which gives me the desired results for smaller lists, but takes up too much memory for larger lists, as I am storing the hash in memory.

I am looking for a solution that will take less memory to implement.
Some thoughts I have are

1) save the hash to a file, instead of memory

2) multiple passes over the file

3) sorting and uniquing the file with unix sort -u -k1,2 , but that takes many hours and it also doesn't reduce the file that much.
So even if I run that sort,  Most of the filesize is retained.
 when the hash is searched for ID2ID1 , I still have to load a huge file into memory

You have a dataset with at least billions of entries, whose size is that of a medium-sized hard disk. This is large. If something takes only “many hours” and not many months, that's as good as you can expect.

Sorting the file is a viable strategy to get rid of the duplicates. You'll also need to canonicalize the pairs. If you stick with a flat file, the most likely strategy is to do a pass of canonicalization where you define an order relation on the IDs and swap the pairs if the larger ID comes first. For the canonicalization step, you can use awk or a custom C program. For the sorting step, use sort, which is (at least on Linux) capable of doing external sorts and is likely to be faster what you'd come up with. Do this in a C locale to make processing faster (based on bytes rather than multibyte characters).

If you want to do lookups, a terabyte-sized flat file is not the right format. This is large even for a database. On the topic of databases with billions of records, read Can MySQL reasonably perform queries on billions of rows? and Which database could handle storage of billions/trillions of records?. A database may or may not be adequate for your task — this depends if the pairs are all you have or if there's other data to consider, and on whether there's structure to the IDs. I think a database would be the right tool if you want to support queries like “list the pairs that contain this ID value”. You should ask database professionals, rather than computer science professionals, whether and which database would be suitable; be sure to explain the structure of your data and what kind of queries you'll want to make. If you decide to use a database, there's no need to remove duplicates or canonicalize entries before importing them, that will happen on the fly.

If you determine that you aren't going to benefit from a database, then you should organize your data in a structured way. The best structure depends on the density of the data, i.e. how many of the potential pairs are present, how many of the potential IDs are present, the distribution of IDs, etc. Here's an example of the kind of structure that might work:

A toplevel directory determined by the first two characters of the first pair.
A second-level directory determined by the next two characters of the first pair.
In these directories, a file per first ID, named with the first ID and containing the list of second IDs.

This is just an example — you need to find a repartition that works. With typical Linux filesystems, aim for about 100–1000 entries per directory (i.e. 100–1000 toplevel directories, 100–1000 subdirectories in each directory, 100–1000 file in the deepest directories).

There's no need to remove duplicates before moving the data into a structured file set like this. You may want to do a pass of canonicalization first (or do it on the fly).

If you're going to make a lot of queries and you expect many of them do come up negative, build a Bloom filter. Define a fast hash function on pairs whose output is $N$ bits, and write an array of $2^N$ bits to a file where the nth bit indicates whether there exists a pair whose hash is $n$.


Reduction PSPACE language to DSPACE(O(1)) We have a language $L \in PSPACE$.  Is it possible to reduce it with $f \in LOGSPACE$ to $L'$ and $L' \in DSPACE(O(1))$?
Why/why not?

The only languages in $PSPACE$ that can be reduced by the above constraint are languages in $LOG-SPACE$.

Assuming it's a Karp reduction:

A language in $DSPACE(O(1))$ is in $DTIME(O(n))$ (the number of configurations is linear). [Thanks to Yuval's comment]

Clearly, everything you can solve in $DSPACE(O(1))$ you can solve in $DSPACE(O(logn))$; So, you might as well leave a bit flag indicating whether to accept the string or not when you reduce the language by solving it in the transducer directly.

Thus, the reduction function will decide the language and since you are constrained to $LOGSPACE$ reduction you can decide only languages in $LOGSPACE$.


How to check whether a graph is connected in polynomial time? I have to solve the following problem:

  Consider the problem Connected:

  Input: An unweighted, undirected graph $G$.

  Output: True if and only if $G$ is connected.

  Show that Connected can be decided in polynomial time.

I have been at this for hours, and I can't seem to find a way to prove this.
Any hints?

Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not.
Note: You have to apply BFS/DFS only one time on the graph


Certificate Definition of NL As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for a deterministic verifier machine.

My doubt is that for a $3-SAT$ problem, if instead of storing an assignment to the $n$ variables, I store the $3k$ assignments to the $3k$ literals in a $k$ clause 3-SAT formula in the certificate tape. This way I don't have to re-read a previous symbol and I can go from left to right in the certificate tape at each step of the machine.

And in work tape I can calculate OR of 3 literals. If it is $0$, then I reject, if it is $1$, I erase the contents of the work tape and store the values of 3 literals of the next clause, and repeat. If all clauses were satisfying, I accept.

The certificate is also polynomial in the length of input. Kindly point out the flaw in this argument, otherwise $3-SAT$ would $\in NL$, which is not believed to be true.

The problem is that you won't be able to verify if the certificate is legitimate as you are making certificate with assignment of variables clause by clause. To check it is legitimate you would have to traverse back on certificate tape which you won't be able to. For example let $\phi = \{ (x_1 \vee x_2 \vee x_3) \wedge (\overline{x_1} \vee x_4 \vee x_5) $. And say your certificate is {(True,False,False),(True,False,False)}. In this case you would declare that assignment makes $\phi$ True but that's not the case as $x_1$ and $\overline{x_1}$ can't both be True and to check all assignments are valid you will have to traverse back and forth on certificate tape which you can't do. Thus your approach is not correct.


Minimizing the overall cost over groups I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this:

User (U) | Group (G) | Price (P)
================================
U1       | G1        | P11
U2       | G1        | P12
--------------------------------
U1       | G2        | P21
U2       | G2        | P22
--------------------------------
U3       | G3        | P33
U4       | G3        | P34
--------------------------------
U5       | G4        | P45

A user (U) can apply to be an admin of more than one Groups (G). There is a salary (P) that must be given to U if U is selected as the admin of G (U can demand any arbitrary number as salary for a group G).

The goal is to satisfy these conditions

Every group should have exactly 1 admin.
A User should not be the admin of more than 1 group.
Find admins for as many groups as possible.
The sum of salaries should be minimum.

Examples/Notes

If there are only two applications and are by the same user U (say for groups G1 and G2, expected salaries P1 and P2), only either of G1 and G2 will get an admin. If P1 > P2, U should be adjudged the admin of G1 (and not G2).

I'm not very sure which category of Assignment problem does this fall into. My approach was greedy and doesn't look optimal.

Group-wise sort (ascending) the expected salary.
Arbitrarily allocate a user to a group where there is only 1 admin-ship request. Remove this user from other group-admin requests.
Among the first request across groups, find the maximum and allocate the user to the group. Remove this user from other group admin-ship requests.
Repeat

Question: What is an optimal solution to this problem?

You are probably looking for a solution to the following optimization problem.

Weighted maximum biparite matching. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \rightarrow \mathbb{N}$, find a set of edges $A\subseteq U\times V$ such that all edges in $A$ are disjoint (that is, no two edges are adjacent, that is, no group has two admins and no admin has two groups) and the sum $\sum_{a\in A}w(a)$ is minimized, and it is not possible to add another pair $(u,v)\in U\times V$ to $A$ without violating the non-adjacency constraint.

The sets $U$ and $V$ are the users and the groups, respectively. The set of edges $E$ is the set of applications (user-group pairs) and the set of weights is the salary of a given assignment. The Blossom algorithm (link) is a optimization algorithm that finds a maximum matching, and it can be adapted to solve the weighted case.

A final note: you seem to be optimizing two objectives at once: both the minimum salary, and the maximum number of covered groups. Obviously these objectives conflict: covering less groups gives a lower salary. Fortunately, the Bloom algorithm will find a maximum matching, so it will cover as many groups as is possible, and within the set of matchings that cover the maximum number of groups, it finds the one with the lowest sum salary.


Dynamic programming tree algorithm We have a network of sensors organized in tree form, where the sensors
  occupy the nodes. Most of the time the sensors are turned off, until
  the root sensor wakes up the rest of the sensors. This process of
  awakening the nodes requires a certain amount of time since, in a
  unit of time, a sensor can awaken only one of its children. Obviously, the total wake-up time for all sensors depends on the order in which each sensor wakes up your children.

  It is asked to design an efficient algorithm that gives a sorting of
  the children of each node in the tree providing the minimum time to
  wake up all the sensors.

The solution must use dynamic programming.

I have got no clue where to start from; I know dynamic programming exercises are based on suboptimal structure and overlapping problems, and in this case, at least, overlapping problems is quite obvious since the tree structure is used.

Have you got any clue about the underlying recurrence? -- I am not asking you the solution since those are my homework :)

Thanks.

Suppose that the root of the tree has subtrees $T_1,\ldots,T_m$, and that you found the optimal wake-up times $t_1,\ldots,t_m$ for each of the subtrees (that's the "dynamic programming" part, though I'd just call it recursion). In which order should you wake up the subtrees? If $t_i > t_j$, should you wake $T_i$ or $T_j$ first? Use this to come up with a recursive formula for the optimal wake-up time of the tree.


How many recursive calls does it take to compute binomial probability weights? I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen within $100$ elements with $0.25$ their probability to appear.

This is the method:

binomial1(int N, int k, double p) {
    if (N == 0 && k == 0) return 1.0;
    if (N < 0 || k < 0) return 0.0;

    return (1.0 - p) * binomial1(N-1, k, p)
         + p * binomial1(N-1, k-1, p);
}

The question is, how many calls to binomial1 would be required to evaluate binomial1(100, 50, 0.25)?

I tried first the fool strategy to implements a system.out.println within the code with an indice increasing each time the algorithm was called. But I realised that it was something fool when I noticed I reached:

passed 2485266 times

Thus I was wondering that as far that the algorithm is called twice every time it is called, I was wondering if it was simply called $2^{100}$ times? Yet, p*binomial1(N-1, k-1, p) seemed to be called only $50$ times with a parameter $k=50$...

I'm only asking for a hint.

If we let $T(n,k)$ represent the number of times that binomial1 is called when computing binomial1(n, k, p) we'll have $T(n,k) = T(n-1, k) + T(n-1, k-1)+1$ and $T(-1, k) = T(k, -1) = T(0,0)=1$. The closed form expression for $T(n,k)$ is a bit messy, but fortunately we don't need it.

Note that the binomial coefficients $\binom{n}{k}$ are defined by the nearly similar recurrence $\binom{n-1}{k} + \binom{n-1}{k-1}$ so we'll have $T(n,k)\ge \binom{n}{k}$ and in particular $T(100, 50)\ge \binom{100}{50}$ and by Stirling's approximation we'll have $T(100,50)\approx 2^{100}/\sqrt{50\pi}$, which is pretty much what you guessed.

[In fact, it turns out that $T(n,k)$ is quite a bit larger than $\binom{n}{k}$.]


Is the graph symbol used in dask a general notation? Dask is a flexible library for parallel computing in Python.

This piece of code define some simple functions.

def inc(x):
    return x + 1

def double(x):
    return x + 2

def add(x, y):
    return x + y

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

output = []
for x in data:
    a = inc(x)
    b = double(x)
    c = add(a, b)
    output.append(c)

total = sum(output)

this piece of code wraps the functions above, and defer their execution.

x = dask.delayed(inc)(1)
y = dask.delayed(inc)(2)
z = dask.delayed(add)(x, y)
z.visualize()

and this task graph

question

is the symbol here a general graph notation? is this a kind of graph language, like UML for visualizing the design of a system, used to visualize the computation task?

It's... a visualization. Don't read too much into it. Graphs in computer science are formalized, but unless specifically mentioned a visualization of a graph doesn't have a formal underpinning. They're generally self-explanatory, there are objects (nodes) and arrows (edges).

UML is more of the exception than the rule, being a graphical language with a formal interpretation. Most visualizations in computer science aren't that strict in meaning.

Here it seems that the round nodes are functions, the square nodes are (temporary) variables, and the arrows indicate data flow.