texts: Weak hashing function for memorable IPv6 addresses

texts:
IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4.

There have been attempts to mitigate this, making IPv6 addresses somehow more memorable.

Is there an intentionally-weak hashing function which could be reversed to find that the phrase, say, "This is relatively benign and easy to spot if the phrase is bent so as to be not worth paying" would hash to a target IPv6 address?  The hash would, of course, have many colliding inputs to choose from, and a potentially more memorable sentence, such as this example phrase, could be automatically offered.

I guess there are two parts: First a weak hash with good distribution in both directions.  Second is an algorithm for selecting memorable phrases from among the many collisions (short, consisting of words from a specified language, perhaps even following a simplified grammar).

Although the hash function would need to be weak, I don't doubt that the effort is still significant - however, once the phrase is known, the computation of the hash to the target address is very quick.

EDIT

I found this related idea, Piphilology, for memorizing some digits of π:

  How I wish a drink, alcoholic of course, after the heavy lectures involving quantum mechanics!


texts: efficient DELETE in proto-Van Emde Boas Tree?

texts:
TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know whether it works or not.
In particular:
In Section 20.2.1 of CRLS, the book introduces a "proto" Van Emde Boas (vEB) structure that has some, but all, of the features of true vEB trees. At the end of the section, it says

The DELETE operation is more complicated than insertion. Whereas we can always set a summary bit to 1 when inserting, we cannot always reset the same summary bit to 0 when deleting. We need to determine whether any bit in the appropriate cluster is 1. As we have defined proto-vEB structures, we would have to examine all $\sqrt u$ bits within a cluster to determine whether any of them are 1.

However, that last claim seems dubious, since the summary structure itself already tells you that information, so that you don't have to "examine all $\sqrt u$ bits within a cluster to determine whether any of them are 1."
In particular, exercise 20.2-2 asks for an implementation of PROTO-vEB-DELETE that "scans related bits within the cluster". The following seems to work in O(lg u) time without scanning any bits, except in the base case of V.n == 2! Of course the true vEB tree has O(lg lg u) deletion, so the below is still inferior to that.
PROTO-vEB-DELETE(V, x)
  if V.n == 2
    V.A[x] = 0
    return  V.A[1-x] == 0
  else
    return PROTO-vEB-DELETE(V.A[high(x)], low(x))
        && PROTO-vEB-DELETE(V.summary, high(x))

PROTO-vEB-DELETE(V, x) deletes element x from the vEB structure V, and returns TRUE if and only if the deletion of x caused V to become completely empty. This algorithm seems to have complexity $T(u) = 2 T(\sqrt u) + O(1)$, which becomes $T(u) = O(\lg u)$. Does this algorithm actually work?


texts:
I have been reading $CO$ by Carl Hamacher. I have read generally $PC$ is incremented during the fetching phase of the instruction only, so if interrupt occurs because of branching or call during execution of instruction, then first the current instruction is completed followed by the storage of address of next instruction (or simply, storage of current $PC$ value).

But I have got some doubts concerning $HALT$ instruction. Suppose there is a 4 byte $HALT$ instruction at memory location $1000$. Then

What will be the $PC$ value and return address saved on stack if interrupt occurs during execution of $HALT$? $1004$ or $1000$?
I have read $HALT$ instruction is actually uncondition branch instruction on itself. Is it true? Any reference for this statement?


texts: Computational complexity vs other complexities

texts:
Complexities, such as time complexity, space complexity, communication complexity and sample complexity, are often used to analyze the performance of algorithms. As far as I know, time complexity and space complexity are collectively referred to as computational complexity.

Are there other common complexities in theoretical computer science? Is there any theory that can cover all these complexities?


texts: Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

texts:
Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ elements of $A$ in $O(n^2)$ or $O(n^3)$ time complexity? If yes what would be the pseudocode?

This seems to be a knapsack problem to me and according to Wikipedia it's an NP-complete problem. So even if the array was unsorted in the first place and we wanted to sort it it would take $O(n\log n)$ time which doesn't really help if the problem is NP-complete anyway. Yet I wonder if some optimization may be made to achieve better time.

Please treat $x$ and $k$ as constants, for running time analysis.


texts: Dependency on adjacent blocks decreases as block count increases

texts:
The following is an excerpt from Information Theory: A Tutorial Introduction, page 65.

Now, supposing the identity of each letter in English does not depend
on any letter that is more than 10 letters away. In practice, the
dependency between letters diminishes rapidly as inter-letter distance
increase, as shown in Fig. 3.6. Once the block length has grown to $N =
 10$, the identity of every letter in a given block $B_k$ depends on other
letters in that block and exactly two other blocks: the previous block
$B_{k-1}$ and the next block $B_{k+1}$. All other blocks contain letters
which are more than 10 letters away from, and therefore independent
of, every letter in block $B_k$.
If the original text is sufficiently long, and if there are a large number of blocks, then the dependency between adjacent blocks just
described accounts for a tiny proportion of the overall dependency
between blocks. Thus, the more blocks there are, and the longer each
block is, the smaller the dependency between blocks. By analogy, it
is as if each block is one of a large number of independent
super-symbols, and if the blocks are independent then finding their
entropy is relatively simple. The only question is, how long do those
blocks have to be to ensure that they are independent?
The block
length beyond which inter-letter dependence falls to zero is called
correlation length $N_C$. Once the block length exceeds the correlation
length, it is as if all  blocks are effectively independent, so
increasing the block length $N$ beyond $N_C$ has a negligible effect on
the estimated entropy $G_N$. At this point, $G_N$ equals the entropy of
English; that is $G_N = H$. This matters because Shannon's theorems are
expressed in terms of infinite block lengths, but in practice these
theorems apply to any block length which exceeds the correlation
length  of the sequence under consideration.

Given some block, I can't see how block count decreases dependency on two blocks adjacent to it. Could someone, please, explain?


texts: Where can I find CS problem set resources?

texts: I am trying to learn to program and I don't just want to learn syntax, but rather learn and practice breaking up and solving problems. Now, I want to know where can I go to get hold of material that ranges in programming problems from beginner to intermediate and hopefully even further so that I can train my problem-solving skills. Any tips or advice on how to train problem-solving skills would be highly appreciated too.


texts: Is a Petri net without places well-defined?

texts:
I'm a bit confused about the definition of a Petri-Net. From Wikipedia (EN) I have this defintion:

A Petri-Net is a 5-Tupel (P, T, F, W, s)
P and T are disjoint finite sets of places and transitions, respectively.

So the defintion says: $P \cap T = \emptyset $ &  $P \cup T \neq \emptyset $
Let's say T is $ \emptyset $ and P = { p } so both prerequisites are given. I think that is okay. We have a system which stays allways in one state and can not change to another so we do not need any other state or transition.
Now think about the other case: T = { t } and P is $ \emptyset $. Now we have a system which does not have a state. The transition can't do anything because we do not have any states and it does not have any meaningful meaning in this case.
So does any Petri-Net which has minimum one transition need two places? Or have I missed out something?


texts: An algorithm that finds ord(a) in $O(\log n)$

texts:
Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^*_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$).
I showed that if $n$ is the above then $φ(n)$ is power of 2.
For example:
let $m=k=2$ so $n=5\cdot4=20$ and $φ(20) = |{1, 3, 7, 9, 11, 13, 17, 19}| = 8 = 2^3$
Let $a=7$:
$7^1 \bmod 20 = 7$,
$7^2 \bmod 20 = 9$,
$7^3 \bmod 20 = 3$,
$7^4 \bmod 20 = 1$
so $\operatorname{ord}(7) = 4$
But I don't get how can I use that to find such algorithm.


texts: In Coq, what does it mean to have an inductive type where the right-hand side of ":" is Prop?

texts:
I'm new to Coq, and my (rather limited) understanding is that inductive types are like algebraic datatypes in Haskell, so there is a constructor data T = A a with some arguments, and the result A a is a T: specifically a T, so I understand stuff like this:

Inductive List := Nil : List | Cons : nat -> List -> List.

where you apply a constructor and get a List, which defines what Lists (as opposed to something else) are.

So how exactly does it work that I can define an inductive type like this:

Inductive Person := Name : nat -> Person.
Inductive Knight : Person -> Prop := Knight_ : ∀(A:Person), Knight A.
Inductive Knave : Person -> Prop := Knave_ : ∀A, Knave A.

where the inductive type has Prop (or Person -> Prop?) on the right-hand side of it? This is supposed to represent "A is a knight" and "A is a knave" in knights-and-knaves puzzles. I think this is a way to encode the idea, but this is a little confusing, and I couldn't find an explanation of this. Some places in fact introduce inductive types as being similar to Haskell's data, but that's clearly not all of it.


texts: Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

texts:
I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum:

Given a set of integers, $S$, and a target number, $n$, what is the number of subsets of $S$ that sum to less than $n$?

For example, if $S$ is $\{1, 2, 3, 7, 7, 15\}$, and $n$ is $20$, the answer is $38$.

Is this an NP-Complete problem? If not, what is a fast algorithm to compute the answer?


texts: Does Thompson's algorithm produce optimal NFAs?

texts:
I'm using Thompson's algorithm to convert from a regular expression to a NFA.  Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of states?

For instance, consider this example.  I have the regular expression $(a|b)$.  According to this website, Thompson's algorithm converts it to the following NFA:

   o--->o
  /ε  a  \ε
>o        O
  \ε  b  /ε
   o--->o

However, the following NFA is smaller and seems like it would also be equivalent:

   o
 a/ \ε
>o   O
 b\ /ε
   o

Why doesn't Thompson's algorithm output the latter NFA?  What did I miss here? Is that Thompson's construction algorithm not optimized at all?


texts: Linear and almost-linear perfect hashing

texts:
I am trying to understand the sentence from a paper by Patrascu:

  Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity

The context is a reduction between two variants of the 3-SUM problem:

In the usual variant, 3SUM, given an array $A$ we have to find 3 indices $i,j,k$ such that: $A[i]+A[j]=A[k]$.
In the other variant, Conv3SUM, we have to find 2 indices $i,j$ such that: $A[i]+A[j]=A[i+j]$.

Theoretically, we could reduce 3SUM to Conv3SUM if we had a linear hash function - a function $h$ such that: $h(x+y)=h(x)+h(y)$, and that maps all elements of $A$ to the range of indices $\{0,...,n-1\}$

The reduction is by sending every element of $A$ to an index determined by $h$, i.e. create an array $B$ such that for every $x\in A$: $B[h(x)]=x$

Then, if there is a solution to 3SUM on A, $x+y=z$, then on B we will have: $B[h(x)]+B[h(y)]=B[h(z)]$, and by the linearity of $h$ also $h(x)+h(y)=h(z)$, so this is a solution to Conv3SUM on B.

Conversely, every solution to Conv3SUM on B is trivially a solution to 3SUM on A, since every element of B is also an element of A.

Unfortunately, we do not have linear perfect hashing, so we have to use a family of almost-linear hash functions.

MY QUESTION IS: why do we have perfect almost-linear hash functions and not perfect linear hash functions? How does almost-linearity make it easier to find perfect hash functions?


texts: If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid

texts:
I have to prove the following problem in propositional logic:

Let $F$ be a set of clauses and let $F' = F \cup \{res(C_1,C_2,A_i)\}$ be the extension of $F$ by a resolvent of some clauses $C_1,C_2 \in F$ where $A_i$ is a literal occuring positively in $C_1$ and negatively in $C_2$.

Prove that: If $F$ is valid, then $F'$ is valid.

So in other words I have to prove that when I construct the union of the original formula $F$ and the formula resulting by applying resolution on $F$ over a literal $A_i$ in $F$, validity is still preserved.

I think that this should be provable by applying a direct proof.

Recall: Note that resolution is defined as follows: given two clauses:
$C_1 = (A_1 \lor \dots \lor A_i \lor \dots \lor A_n)$ and $C_2 = (B_1 \lor \dots \lor B_j \lor \dots \lor B_m)$ such that for some $i, j$ with $1 \leq i \leq n$, and $1 \leq j \leq m,\; A_i = \neg B_j$,
the resolvent of $C_1$ and $C_2$ on $A_i$ is the clause

$res(C_1,C_2,A_i) = (A_1 \lor \dots \lor A_{i-1} \lor A_{i+1} \lor \dots \lor A_n \lor B_1 \lor \dots B_{j-1} \lor B_{j+1} \lor \dots \lor B_m)$

EDIT: Here is my try:

Let $I$ be an interpratation taken from the set of models $Mod(F)$. Hence, $I(F) = 1$. Because this interpretation satisfies $F$ it must also be the case that it satisfies $C_1$ and $C_2$. If we take a look at the structure of $C_1$ and $C_2$ we have to distinguish between $2$ different cases:

(1) $A_i$ is positive in $C_1$ but negative in $C_2$ and

(2) $A_i$ is negative in $C_1$ but positive in $C_2$.

In case (1) if $A_i$ is set to true in $C_1$ it would be false in $C_2$.
In case (2) if $A_i$ is set to true in $C_2$ it would be false in $C_1$.

$A_i$ cannot be the literal which preserves satisfiability of $F$. Hence $I$ must include some assignment of other literals in $F$ such that $F$ is satisfied. Thus, the resolvant $res(C_1,C_2,A_i)$ is also satisfied.


texts:
Is there a way to use median-of-medians to find a median in,

simultaneously,  O(log n)  memory and O(n) comparisons?

The user orlp on this site seems to claim that there is.

Getting  O(log n)  auxiliary memory seems to be straightforward,

but I have no clue how that can be improved to O(log n) memory.


texts: Advantages/Disadvantages of adaptive contexual arithmetic coding

texts:
What are the advantages and drawbacks of considering ever longer block lengths or context lengths, if one was to work with estimated probabilities(measuring on the fly: aka "adaptive") rather than probability distribution that was measured offline(static).

I have thought of the following advantages

Lesser compression as even though the context is taken into account the probability distribution of the source is not accurate, particularly for smaller n.
Reduces the need to send the uncompressed dictionary of probabilities.
For an nth order contextual model we will need to store $|X|^{n+1}$  ($|X| =$ alphabet size)worth of memory space to store and send the contextual data for the static model. However, this is not needed in adaptive coding. As the context length increases, this advantage plays a more important role.

For drawbacks

More susceptible to corruption.
Larger context length implies more conditional probability to update which may mean that the estimated distribution will take more time to approach the true distribution.


texts: What is an algorithm for what I am trying to do?

texts:
I have an equation $y=2x^4-20x^2-50x$ within a range of -4 to 6

I already have an algorithim that tell me the y value when I plug in the $x$. It simply uses a loop.

What I am trying to do is determine what will be be the y max value and what $x$ corresponds to it.
Is there some sort of loop or counter I can use. I am program this on SPARC machine but any sort of pseucode loop will be appreciated.

I tried to do the following

I have a counter


texts: Do modern operating systems use memory control blocks?

texts:
I was taught in my operating systems class that sections of memory in the heap are marked as free/occupied through the use of memory control blocks (MCB). The generalized definition of an MCB that was given to us is that they hold two memory addresses (one for the next MCB and one for the previous MCB), the size of the block of memory attached to the MCB, and a flag stating whether that block is occupied or not.

When a chunk of memory is requested, the OS finds an unoccupied MCB, marks it as occupied, and creates a new MCB at the end of the now occupied block.

This seems like a sensible way to do things, and yet I cannot find any mention of the term "memory control block" outside of explanations of how DOS tracks memory allocations, even in the textbook Operating Systems Concepts (Silberschatz et al).

I'm confident that some sort of administration is going on, via a simple C++ program that creates several pointers to ints and then prints out the addresses stored by the pointers, which are consistently not consecutive (although I guess this doesn't prove anything for sure).

What's going on behind the scenes? Are MCBs simply called something else nowadays?


texts: Time-complexity for basic multiplication and division algorithms

texts:
The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen.

p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ additions of bits are required for all n additions".

Why isn't this algorithm $O(n)$? I can see only two non-nested for loops.

p.254 says that "this means that we need $O(n^2)$ bit operations to find the quotient and remainder when a is divided by d".

Why isn't this algorithm $O(n)$? I can see only one while loop.


texts: Which sort algorithm to choose given two specific arrays?

texts:
Interview question:

Given array A which contains only odd numbers and array B which contains only even numbers, explain
which sort algorithm would you choose.

I said merge sort. I thought that given two lists both of which are sorted (which I assumed) I can just merge them i.e use the merge part of merge sort.
I was then asked if the numbers were not even or odd would I have chosen merge sort still? Then I was asked if both arrays were not sorted i.e. A contain even numbers (not sorted) and B contain odd numbers (not sorted) which algorithm will I use. I said in practice quicksort typically performs better. I wanted to ask if the length of the arrays is not too big because then bucket sort might do but given his insistence on odd and even integer arrays I did not go for bucket sort (I was afraid I was mentioning all the algorithms).
Does anyone know which algorithm might the interviewer be looking for?


texts:
Premises or Givens:

$∃x(A(x) → B(x))$
$∀x (B(x) → K(x))$

To Prove:

$∃x(A(x) → K(x))$

My Solution:

$A(z) → B(z)$  From premise and  Existential instantiation $x$ for $z$

$B(z) → K(z)$  From premise and  Universal instantiation $x$ for $z$

$A(z) → K(z)$  Transitivity of 1,2

$∃x(A(x) → K(x))$  From Existential generalization (Substitute $z$ for $x$)

OR
I was thinking about assuming $A(z)$ and then using Modus Ponens to get $B(z)$ and then further $K(z)$, then using the deduction theorem on $A(z)$ and $K(z)$, and then using Existential Generalization on that statement by substituting $x$ for $z$.

Can someone suggest which way would be more effective?
Is there any other effective way to solve it?


texts: Find a schedule with lowest total penalty

texts:
Given a set of n jobs with [arriving time, service duration time,
  penalty per unit of time] find a schedule with lowest total penalty.

Notes:

Arriving time is the time when objects aarivies to processing system.
All objects can arrive at the same time
Processor is able to process only one object at the same time
Servicing time is the time required to process the object
Penalty is calculated as (penalty * time spent in the system), i.e. departure time - arrival time

The easiest way to understand the problem is to imagin a loggistic company with a number of trucks that are waitings loading/unloading of the cargo. Trucks arraives at a given time and can wait on a parking. There is only one terminal that process loading and unloading. It's required to find an optimal schedule of processing.

Example of the input data:

t,tau,a
5,4,12
4,6,2
9,2,1
11,4,5
13,4,5
16,3,2

The question here - which approach is required to solve this and similiar problems? I assume these algorithms are providing solutions close to a brute force.


texts: Will a Greedy algorithm give a correct result for minimum partition?

texts:
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?

Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now I have to divide it into two subsets so that the difference between the sums of the two subsets is the minimum possible.

Greedy Method:

I have the given set of numbers and an empty set. On each iteration, I select the number from the first set and check which causes the minimum difference and put that into the second set and repeat the process again.

For example: let us say I have to partition $\{1,2,3,4\}$ into two subsets so that their respective sums are minimum.

So using the above method I would do the following steps:

Select the number that causes the min diff so far ie.

$\{2,3,4\}$ and $\{1\}$ diff = $9$

$\{1,3,4\}$ and $\{2\}$ diff = $6$

$\{1,2,4\}$ and $\{3\}$ diff = $4$

$\{1,2,3\}$ and $\{4\}$ diff = $2$

so the minimum is $\{1,2,3\}$ and $\{4\}$

I use the above configuration and repeat the same process, and I land up with the partition $\{2,3\}$ and $\{4,1\}$ which has a difference of $0$ and is the correct answer.

So, assuming the numbers given are all positive integers, will the greedy method work for all inputs or will it fail for some. Is dynamic programming the only way to get the optimal solution?


texts: How to handle the time complexity for an optimization that depends on numerical values

texts:
I'm working on an algorithm and there is an optimization I applied that is unpredictable because it depends on calculations done on top of the input trough several iterations, so as the input values change, the optimization gain oscillates (between a 20% to 90% step count reduction) as is adaptive to the input.

Is there any formal approach to handle these situations in respect to time analysis?


texts:
I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I now want is to bring i1 and i2 into alignment, that is I want to know where pixel (x,y) in i1 is in i2. This "alignment-matrix" should be valid in general, that is not only for i1 and i2, but also for further images of the cameras c1 and c2 as long as they haven't been moved. I believe this problem is called "correspondence problem".

I have now read quite a bit about camera calibration, image rectification, essential and fundamental matrix. But there are still open questions and I would not know how to achieve my task.

So, the question basically is:

The essential matrix E and the fundamental matrix F both only give constraints for the correspondence problem (point p in i1 must lie on line l in i2). How do I actually solve the problem?

Thanks a lot for your time and answers!


texts: Compression technique exploiting common similarities

texts:
I asked this on StackOverflow, but it was determined more appropriate to post here.

So it goes like this..

For people concerned about users having slow connections and timeout issues, it is known that it can't be just always solved with minification, latency reduction etc..

I'll try to keep this question as short as possible, however retaining clarity where possible.

I've thought about a technique to further reduce uncompressable files (like mp3 and mp4), bear with me please.

What if we could skip chunks/bits/frames of a file being similar and rebuild them locally? Ok, let's explain it with a short example.

Assume you have many files in your computer, and that 3 of them are videos with a knife and a guy with blue eyes non-evenly spread over many frames. You go to this site and there's a post.. this post features a video of a serial killer's life. It is totally unrelated to the videos you have on your pc, except for the killer's knife, and the victim he kills having blue eyes.

What we could do here, is, remotely and locally make the videos (in this case) have "metadata blocks" about the most frequent frames and do a bidirectional check. If the two happen to have the same/similar blocks, the remote server just sends the new blocks, and, we rebuild the missing ones locally.

Like this:

Remote file =
    MetadataBlock:
        knife:
            from (minute 3.12) to (minute 3.59)
                and from (minute 4.40) to (minute 5.20)
        blue eyes:
            from (minute 0.06) to (minute 0.60)
                and from (minute 1.20) to (minute 1.30)
                and from (minute 6.50) to (minute 6.58)

Local file =
    MetadataBlock:
        knife:
            from (minute 8.00) to (minute 8.20)
                and from (minute 40.00) to (minute 40.02)
                and from (minute 42.00) to (minute 42.50)
        blue eyes:
            from (minute 3.05) to (minute 3.15)
                and from (minute 6.08) to (minute 7.40)

Local file.knife.total = 1.12 minutes

Local file.blue_eyes.total = 1.42 minutes

FileTotal = Local file.knife.total + Local file.blue_eyes.total

FileTotal (2.54) * 3 / 1.5 = 5.08 minutes

Remote server remove the blue eyes and knife bits/frames, appending instructions to build them locally from MetadataBlock.

As soon as the file is received, the os reads the instructions and execute them like:

"Replace MetadataBlock(from(knife.minutes)) with local file 1 MetadataBlock(from(knife.minutes))"

, the same goes for other metadata blocks such as blue eyes, black hair, shirt color etc..

Is a technique like, or similar to this feasible, or just pure utopia?


texts: How many unique counting functions there are for strings of N bits?

texts:
Let a counting function inc for inputs of N bits be defined as:

inc(b0 | b1 ... | bN) = F0(b0) | F1(b0,b1) ... | FN(b0,b1,...bN)

Where FN is a function from N bits to a bit, and such that the period of inc is 2^N. Notice that, here, we have a special restriction: the nth bit of the output of inc must only depend on bits that come before the n+1th bit of the input. This is obviously the case for the traditional counting function. How many unique inc functions there are for a given N?

Example

For n = 3, there are at least two unique functions:

# Example 0

F(b0 | b1 | b2)
   = not(b0)
   | xor(b0, b1)
   | if b2 then and(b0,b1) else or(b0,b1)

Produces the usual counting: 000, 100, 010, 110, 001, 101, 011, 111, 000...

# Example 1

F(b0 | b1 | b2)
    = not b0
    | xnor(b0,b1)
    | if b2 then and(b0,b1) else or(b0,b1)

Produces the sequence: 000, 110, 011, 101, 001, 111, 010, 100, 000...


texts: Best way to translate while loops to functions for software verification

texts:
I have a verification engine where while loops are translated into functional code, like this:

def f() = ... while(c) b ...

def f() = ... fwhile() ...
def fwhile() = if(c){ fwhile() }

We want for the users to be able to annotate while loops with a decreases construct which says that certain measure decreases at each iteration. This is used to prove termination as follows:

while (x > 0) {
 decreases(x)
 x = x - 1
}

The problem is that the checker of the decreases uses the hints given by the preconditions of the functions it is working with. We cannot specify that the precondition is the while loop condition since it may be false at the first call. From my side, I proposed the following translation:

def f() = ... if(c) fwhile() else ...
def fwhile() = b if(c) fwhile() else ...

I would like to have some feedback on the correctness of my approach as well as if there are any better options, since still this will require moving in function f a part of the while which should be naturally contained in the fwhile function.


texts: Minimising sum of consecutive points distances Manhattan metric

texts:
I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.

I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).

Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.

The problem resembles the TSP problem, but the "path" is not closed and metric used is L1 (Manhattan, TaxiCab).

The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.

The problem I am having is with giving the objective function.


texts: Is a physical process with unbounded input Turing equivalent?

texts:
Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A.

Now if this process has an unbounded number of states (for example we could think of an engine in a car and take the geographic coordinates of the car as its states) we could say that A is also Turing complete.

And therefore Turing equivalent.

Edit: Let's try to see more precisely how A could be considered as Turing complete even if the physical is continuous. Let's for example consider a car moved by an engine. And let's consider a planet where towns' names are built with the classic alphabet A, B, C etc. following rules that make the number of towns on that planet potentially infinite or unbounded. Now let's imagine that my vehicle is programmed by an algorithm to drive from town to town indefinitely. Let's call these towns the states of my system. Now I am certain (but please correct me if I am wrong) that my physical system is indeed Turing complete - and not just a push down automaton. Now if you accept that any state an observer (typically a physicist) will use to describe a physical system can be coded in a finite alphabet i.e. an integer (even if the physical world is continuous) then surely we could use the vehicle experience to say that in human eyes the physical world is Turing complete.

Is that correct?


texts: Effective AI for one player-one ghost pacman

texts: I am thinking of a modified version of pacman. In this version, it will be a two-player game. Each player will have one pacman and one ghost. So there are 2 pacmans and 2 ghosts in the board at a time. No additional ghost is there. A player will control both his pacman and ghost separately- there is no predefined or random move of ghosts. Ghost of a player will try to catch the opponent's pacman. Pacman of a player will try to avoid the ghost of the opponent. Collision of ghost and pacman of the same player won't affect anything. So the pacman and the ghost of the same player need to cooperate with each other. "Moving Target Search" seems promising for the ghost, but what about the pacman? Will minimax (with alpha beta pruning) work in this multi-agent cooperative environment? I am saying this cooperative because my ghost will try to catch the opponent's pacman and my pacman will use this opportunity to eat more food. I have separate functions for the pacman move and the ghost move to simplify the gameplay. So returning a single tuple (including the moves of both pacman and ghost) from a function is not possible here.


texts: Space requirement of a universal Turing machine

texts:
Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$.

If $B$ is restricted to using at most $n$ memory cells of its tape and the memory cells of $A$ and $B$ can assume the same number of states, how much space does $A$ require at least to simulate any $B$?

$A$ knows the $n$ of the $B$ of the $g$ its given.

I'm not interested in how this behaves for small $n$ or constant additive terms but would like to know constant multiplicative factors. So if $A$'s space requirement is $3 \cdot n^2 + |g|$ memory cells, that'd be nice to know, not just that its space complexity is $\in \mathcal{O}(n^2 + |g|)$.


texts: What are cases where we cannot perform LR parsing without augmented grammar?

texts:
Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing.
The reason frequently is

It is required in cases where start symbol comes on right hand of any production
It is required when start symbol's RHS have multiple production.

I figured that if in the parse table's action part of very first state of DFA, we provide "success" under entry of '$' we would not require augmented grammar. Is that correct or i am missing something?
Edit: Here is how i think we can declare a parse as success:
Consider S ->  .a
After we reduce 'a' instead of going to goto(S) from our current state a tTop of stack, we can simply lookahead '$' and output success


texts:
I have been trying to come up with an efficient algorithm for the following problem.

Let $G = (V,E)$ be an undirected acyclic weighted graph, where there is exactly one path from a vertex $u$ to any other vertex $v$.

Let $S \in V$ be a set of vertices from $G$.

$|S|$ is the size of the set.

$0 \leq |S| \leq |V|$.

Split the graph into $|S|$ connected components such that each component has exactly one vertex $v \in S$, and the sum of the weights of the edges that get removed is minimum.

I have thought of two algorithms which I will briefly describe.

Algorithm 1

The complexity of this algorithm is $O(2^{|E|} \ (|V|+|E|))$

Algorithm 2

This second approach is more feasible. If implemented naively, though, the time complexity is $O(|S| \ (|V|+|E|))$. This is the result of running a depth first search to find two vertices that belong to the same component and are in S. And it is also used to find the smallest edge in the path from $u$ to $v$. The depth first search is then executed $O(|S|)$ times.

I was wondering if this problem can be solved asymptotically better. I was thinking I could use a dynamic graph which supports queries of the form: are $u$ and $v$ in the same component? and allows deletion of edges. I think this is also known as decremental connectivity. However, this data structure would not help me find the shortest edge from $u$ to $v$.

Any help is appreciated.


texts:
Let us consider the class $\cal F$ of functions that contains

all constant functions
all projections
the successor function
the Ackermann function

as basic functions, and that is closed under composition and primitive recursion.

(If we remove the line with the Ackermann function from this definition, then
this is the standard definition of the class of primitive recursive functions.)

  My question: What function class $\cal F$ do we get by adding the Ackermann function as basic function? Do we get all $\mu$-recursive functions, or do we get some strange sub-class?


texts: How to apply a Hadamard gate to one qubit in a 2-qubit system?

texts:
Edit:

I've pinpointed that the difference between solutions occurs when I apply the $H$, up to there, the solutions match. So, perhaps it is better to phrase my question as: how to apply an $H$ gate to one qubit in a 2-qubit system?

End Edit

I have the following quantum circuit, and I need to calculate the values of the two qubits afterwards.

Now I know the values are:

$\lvert \psi_1 \rangle = \frac{1}{\sqrt{2}}(\lvert 0 \rangle+\lvert 1 \rangle)$
$\lvert \psi_2 \rangle = \lvert 0 \rangle$

It's pretty simple to see, and I checked them with a simulator just to be sure.

The trouble I'm getting into is when I try to express this as a two qubit system.

As I understand it should be as follows:

$$\lvert \psi\prime \rangle=M\lvert \psi \rangle=\frac{1}{\sqrt{2}}(\lvert 00 \rangle+\lvert 10 \rangle)$$

Where $\lvert \psi\prime \rangle$ is the state after the circuit is complete, $\lvert \psi \rangle = \lvert 00 \rangle$ is the initial state, and $M$ is the matrix representing the combined effect of all the gates of the circuit.

Now, I calculate $M$ as follows:

$$M=\frac{1}{\sqrt{2}}(I\otimes X)\begin{bmatrix}I&0\\0&X\end{bmatrix}(I\otimes X)(H\otimes I)$$

I wrote the $CNOT$ matrix in block matrix form here, and extracted the $\frac{1}{\sqrt{2}}$ from $H$ to the beginning.

$$\begin{align}M&=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&I\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\end{align}$$

Now, plugging $M$ back into the first equation...

$$\begin{align}\lvert\psi\prime\rangle &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\lvert\psi\rangle \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{bmatrix}\begin{bmatrix}1\\0\\0\\0\end{bmatrix}\\&=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\0\\1\end{bmatrix}\\&=\frac{1}{\sqrt{2}}(\lvert 00\rangle + \lvert 11\rangle)\end{align}$$

Which is not the correct solution. Where am I at fault?


texts:
After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time?

Additionally, what about division with a constant numerator, ie. "division of a constant"?


texts:
I've started with tree automata. The definition is

  (Leaf-to-root) Tree automaton $\mathcal M$ over (nonempty, finite) alphabet $\Sigma$ is quintuple $\mathcal M=(K,\Sigma,\delta,S,F)$ and bound $f$ (the fan-in bound), where $K$ is finite set of states, $S\subseteq K$ set of initial states, $F\subseteq K$set of accepting states with $\delta:A\to K$ for some (nonemty?) $A\subseteq\bigcup\limits_{i=1}^f\underbrace{K\times\cdots\times K}_i\times\Sigma$.

It seems ok to me, but when it comes to an example I'm lost. For example consider following tree automaton over $\{0,1\}$

I suppose $S$ is set of leaves. And now what is example of word $w$ accepted by the automaton? And how is the word read by it?

Thx a lot for help...


texts: Is there an algorithm to compute the shortest Hamiltonian path in an directed graph from one point to another in polynomial time?

texts:
I am wondering whether the Shortest Hamiltonian Path (SHP) problem is NP-Complete, because I couldn't find a way of solving it in a polynominal time. if it is NP_Complete, it will be so kind of you to give me the proof or the relevent papers,thanks a lot

the problem explanation: Given a directed,weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u.
by the way,the graph must exit a hamiltonian path from v to u.


texts: Can inputs in the decision tree model be computed?

texts:
The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still unresolved by reading the article, are:

Can those functions be fed any values computed by the algorithm (including ones of asymptotically larger magnitudes) or just ones from the input array?
Do the coefficients in the linear decision trees have to be hard-coded? The article seems to indicate that there are as many of them as elements in the input (and even more, exponential in the maximum allowed degree $d$, for algebraic decision trees), which means they cannot be hard-coded. Or is the $n$ in this fragment different and actually only sums of some fixed number of terms, independent of the input length, are allowed?
Regarding point 1, does it make a difference, i.e. can some problems be solved asymptotically faster (or in less memory) when comparisons of differences (or linear combinations, or polynomial functions) of any intermediate computed numbers are allowed? If yes, does the answer change if the numbers fed to the functions can only be $$ of those in the input array?


texts:
In 8-bit address space there are 16 pages and the page table stores:

68792EA51BD3CF04 (hex)

The physical address is 39h, what is the corresponding logical address?

I have literally no idea what to do, tried to look on different sites and work with formulas but nothing seems to work. I don't think it was ever covered on the lectures but it might show up at the exam.

I'd appreciate any form of help, thank you and sorry for taking your time.


texts: Lambda Calculus inductive substitution definition

texts:
I'm reading Lambda-Calculus and Combinators: An Introduction, and there's the following definition of $\lambda$-substitution:

$FV(P)$ stands for the set containing all free-variables from $P$.

Definition 1.12 (Substitution) For any $M, N, x$, define $[N/x]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows (after [CF58, p.94]).
(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

I do understand that:

$(a), (b)$ are the base cases for this induction.
$(d)$ exists per definition, as one is not allowed to substitute bound variables.
$(g)$ prevents a bound variable from changing to a free one. It does this by first substituting a bound variable.

My question is: If one deletes $(d)$ and allows bound variables to be substituted, is $(g)$ strong enough to handle it without messing up everything?
I'm asking this because $(d)$ seems to prevent the following $\alpha$-equivalent substitutions.
$$ [y/x] ~~ \lambda x. x \equiv \lambda y.y $$


texts: Confused between bandwidth and frequency

texts:
I am new to Computer Science and started learning about computer networking very recently. I know that bandwidth means how many bits can be sent through the channel in 1 second. However, recently I came across another definition of bandwidth which says it is the range of frequency where the signal is received.

How to think intuitively of this? Frequency is the number of cycles per second. What is the relation between frequency and bandwidth?

Please note that I am a lay man. Kindly elaborate.


texts: Start / End-Point in TSP - How to consider in an algorithm

texts:
I moved my question from Theoretical Computer Science to this site - proposed by one of the users there - and I'm hoping don't be off-topic again.

At my university, I had chosen to write a term paper about Inventory Routing Problem (IRP).
To get comfortable with this topic (I'm a software engineer), I started with some simpler problems like Traveling Salesman Problem (TSP) and afterwards with the Vehicle Routing Problem (VRP) which can be defined as simplified IRP problems.

To solve these kind of problems, I wrote an Ant Colony System algorithm with some adaption to the specific problem.
But one thing I'm pretty unsure is how to deal with the start and end node of a TSP?
Most literature have a strong constraint, that the depot (start/end node) has to be the same and is determined, which makes sense.
But the algorithms (heuristics) just cover finding the shortest path.
A lot of algorithms determines the starting point randomly.
Are there any disadvantages if I define the starting point as fix?
But the bigger question is can I add the last point (starting point) independently of the found route to calculate the total costs?

Let's say the algorithm find the cheapest way with D -> 2 -> 3 -> 1 (-> D) but recalculating these manually results in D -> 2 -> 1 -> 3 -> D because 1 -> 3 -> Dis faster than 3 -> 1 -> D.
But how I have to include a fixed ending point in my algorithm?
I guess it's independent of which specific algorithm.

If you don't understand my question please leave a comment and I try to rewrite it =)


texts: how can i prove Demorgan's law (X+Y)'=X'. Y'?I already tried studying book but doesn't understand the first step so plz answer in detail.(beginner here)


texts: Impossibility condition in the Byzantine Generals problem

texts:
I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows:

Each general decides a strategy and forwards their strategy to all the other ($3m$) generals.
Each general forwards a vector containing the strategies (of all the other generals they received) to all the generals ($m$)
Now, each general has a list of vectors corresponding to the vote made by each general and using a majority criteria (majority vote) decides each general's strategy and thus, the strategy that it itself chooses.

If there are $3m+1$ generals then, with $m$ (loyal) generals choosing to 'attack' and $m+1$ (loyal) generals choosing to 'defend' and $m$ traitors, then since every loyal general forwards the message correctly, each of the $m$ 'attacking' generals will receive $m-1 + m$ (from the other 'attacking' generals and the $m$ 'defending' generals) confirmations of attack for all the other $m-1$ 'attacking' generals, similarly $m-1 + m$ confirmations of 'defend' for the strategy adopted by each one of the defending generals. The traitors however can alter either by sending whatever they'd like (different bits) to the attackers and the defenders [send d for all the defenders and a for all the attackers, but send conflicting values — d to the defenders and a to the attackers — for all the traitors' values], thus making them follow a different plan (defenders will defend, while attackers will attack).

This can't be right, because all the papers and presentations I've gone through state that $3m+1$ with only $m$ traitors will definitely give you the correct solution (all loyal generals follow the same plan). Can anybody go through my understanding, find the flaw and re-explain it to me?

Also, I have understood the $m = 1$ example, it would be nice if someone could explain to me how it fails when $m = 2$ and there are 6 generals and how it succeeds if $m = 2$ and there are 7 generals... I've tried a lot and am stuck.


texts:
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable.

Between these two types are the recursive non-context-sensitive languages. Wikipedia gives one example here:

An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

So the question: What others problems exists that are decidable but yet non-context-sensitive? Is this class of problems the same as decidable EXPSPACE-hard?


texts: A Question about what it means to Compare two Vectors

texts:
Please consider the following question:
Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in the set ${ 0, 1 }$ such that $Ax \leq b$. Prove that 0-1 integer programming is
NP-complete.

Am I correct that $Ax$ is a vector, $b$ is a vector and $Ax \leq b$ is true iff every element of $Ax$ is less than or equal to its corresponding element of $b$?

Thanks,
Bob


texts:
Let's say I have a function that runs in $O(n \lg n)$.

Let's say instead of running this function with a $n$-sized input, I run it $k$ times with an $(n/k)$-sized input, so I want to check if

$$ O(n  \lg n) = k \left( O \left( \frac{n}{k} \lg \frac{n}{k} \right) \right)$$

I think it is, because of:

$$ O(n \lg n) =  O \left( \frac{kn}{k} \lg \frac{n}{k} \right) = O \left( n \lg \frac{n}{k} \right). $$

Supposing $0 < k \leq n$, as in worst case $k = 1$, we can say that $\dfrac{n} {k}$ is $n$.

Am I right?

In general, will the original $O(n \lg n)$ function be faster or slower? It seems to be slower because what was $\lg n$ now is $\lg \dfrac{n}{k}$ for some $k > 0$.

PS: $\lg = \log_2$


texts: How to correlate a matrix of values to get a coordinated point?

texts:
I got a n*m matrix updated in realtime (i.e. about every 10ms) with values between 0 and 1024, and I want to work out from that matrix a multitouch trackpad behaviour, which is:

generate one or more points on the surface given the values on the matrix,
make this or those point as big as the value can be.

For example here is a few lines of a 9x9 matrix updates, and we can consider the following matrix as an example (with a touch in the middle):

[ [ 12,  7,12 ],
  [ 12,129,19 ],
  [ 12, 11,22 ] ]

The goal is to mimic the behaviour of a common touchpad (like on every smartphone, or laptop). So, I'm getting values from a evenly distributed matrix of capacitive sensors on a physical object, which are processed by a microcontroller into a matrix, and I want to get coordinates and weight of one or several points.

The idea would be to get something like this (of course, I don't expect to have more than 2 or 3 detected points, and that level of precision with a matrix that small).

Here are a few example raw logs:

http://m0g.net/~guyzmo/touch_diag.log
http://m0g.net/~guyzmo/touch_double.log

Edits:

Thinking about my problematic made me consider this idea: I think I should make some kind of interpolation to augment the definition of the matrix, and in some way make the new values additive.

i.e. imagine we have the following matrix :

[ [ 200, 200, 150 ],
  [ 150, 150,  80 ],
  [  80,  80,  40 ] ]

and we want to interpolate it somehow into something that would look like (I'm inventing the values, but it's to expose the idea):

[ [ 200, 400, 200, 175, 150 ],
  [ 175, 200, 175, 150, 125 ],
  [ 150, 170, 150, 125,  80 ],
  [ 100, 125, 100,  80,  60 ],
  [  80,  80,  80,  60,  40 ] ]

I've looked at interpolation algorithms, and it looks like the one we want that is the closer to our needs is the hermite interpolation. But though I have RTFM on interpolation methods, I don't know how I can apply it to a matrix.


texts: Good book on the history of programming languages?

texts:
I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, object oriented programming etc were developed? I was introduced to programming when OOP was well developed and hence I don't really know what it was like for OOP to be developed for the first time. Similarly for structured programming, procedural etc.

Is there a good book that starts with the first programmers who worked directly in computer code, and goes through the different developments, showing how the developments were non-trivial at the time (even though from our current perspective they might seem natural and obvious)?


texts: Fine-Grain parallel algorithm for LU-decomposition

texts:
How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the
min(i; j) - 1,

because I have no idea, what the author wanted to say by it. I know that it means " choose the lesser number of 'i' and 'j' and then substract one", but I don't know what is I and J here (maybe coordinates of the current task? Or is it written from the task's point of view, so the whole pseudocode runs at every task?) etc.
The whole presentation with this code (slide 12) is here.

Pseudocode and diagram of tasks

Bigger picture here.


texts: How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

texts:
We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki
"This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]"  we can also know if we build the heap using other methods. the big O could be better. Where should we begin if we would like to prove that the  performance, Big Omega ,of building a binary heap using recursive method is  Ω(nlog(n)), which is same as Big-O?

insert method from wiki

  To add an element to a heap we must perform an up-heap operation (also
  known as bubble-up, percolate-up, sift-up, trickle-up, swim-up,
  heapify-up, or cascade-up), by following this algorithm:

  Add the element to the bottom level of the heap. Compare the added
  element with its parent; if they are in the correct order, stop. If
  not, swap the element with its parent and return to the previous step

then we have the buildheap as

buildheap((1,1),(,))
   if n==1:
      return [(1,1)]
return insert(( ,),buildheap((1,1),...(−1,−1))


texts: Does NP mean verifiable in polynomial time or solvable in polynomial time?

texts: Is NP defined as verifiable in polynomial time, or solvable in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be found in polynomial time?


texts: What is the difference between bounding and pruning in branch-and-bound algorithms?

texts:
Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is?

I'd also appreciate references (preferably books), where this distinction is made clear.


texts: How to prove SPACE-TMSAT is PSPACE-hard?

texts:
I understand that the language:

$\operatorname{SPACE-TMSAT} = \{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\}$

is in PSPACE since it doesn't use more than $n$ space. But to prove that it is PSPACE-complete, we need to do the reduction from any other PSPACE language to it. If we assume the language to run on a DTM using $O(n^k)$ space, how could we reduce it to SPACE-TMSAT?


texts: For what kind of data are hash table operations O(1)?

texts:
From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.

However, from a programmer's perspective, I don't know in advance what my data will be: it often comes from some external source. And I rarely have all the data at once: often insertions and deletions happen at a rate that's not far below the rate of lookups, so preprocessing the data to fine-tune the hash function is out.

So, taking a step out: given some knowledge about data source, how can I determine whether a hash table has a chance of having $O(1)$ operations, and possibly which techniques to use on my hash function?


texts: Is it possible to have a code which cannot be solved by computer

texts: I was looking at Turing machines and Turing completeness and I was wondering whether it is possible to prove that there is a problem which cannot be solved by a Turing complete computer or whether it is possible to prove the opposite.


texts: In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

texts:
I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the claim by the authors.

Form of a Syntax-Directed Definition
In a syntax-directed definition, each grammar production $A\rightarrow \alpha$ has associated with it a set of semantic rules of the form $b := f(c_1, c_2, . . . , c_k)$ where $f$ is a function, and either

$b$ is a synthesized attribute of $A$ and $c_1, c_2, . . . , c_k$ are attributes belonging to the grammar symbols of the production, or

$b$ is an inherited attribute of one of the grammar symbols on the right side of the production, and $c_1, c_2, ... , c_k$ are attributes belonging to the grammar symbols of the production.

Claim:
In a syntax-directed definition, terminals are assumed to have synthesized attributes only, as the definition does not provide any semantic rules for terminals. Values for attributes of terminals are usually supplied by the lexical analyzer.

That values of the terminals is provided by the lexical analyzer is a usual practice.(Which makes us assume that terminals have synthesized attributes usually). But cannot understand their claim, with the logic that the definition does not allow it. Going by point $2$ in the definition:
$b$ is an inherited attribute of one of the grammar symbols on the right side of the production: so the right hand side of a production might as well contain terminals, making $b$ an inherited attribute of a terminal.
The point $1$ applied to $b$ which is an attribute of a symbol(non terminal) on the LHS and only point $1$ talks about synthesized attributes, so $1$ makes no provisions for attributes for the non terminals. Hence there is no provision of synthesized attributes for the terminals.
Is this something like this?


texts: Efficiently calculating minimum edit distance of a smaller string at each position in a larger one

texts:
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.

That is, for each suffix of $r$ beginning at position $k$, $r_k$, find the Levenshtein distance of $r_k$ and $s$ for each $k \in [0, |r|-1]$.  In other words, I would like an array of scores, $A$, such that each position, $A[k]$, corresponds to the score of $r_k$ and $s$.

The obvious solution is to use the standard dynamic programming solution for each $r_k$ against $s$ considered separately, but this has the abysmal running time of $O(n m^2)$ (or $O(n d^2)$, where $d$ is the maximum edit distance).  It seems like you should be able to re-use the information that you've computed for $r_0$ against $s$ for the comparison with $s$ and $r_1$.

I've thought of constructing a prefix tree and then trying to do dynamic programming algorithm on $s$ against the trie, but this still has worst case $O(n d^2)$ (where $d$ is the maximum edit distance) as the trie is only optimized for efficient lookup.

Ideally I would like something that has worst case running time of $O(n d)$ though I would settle for good average case running time.  Does anyone have any suggestions?  Is $O(n d^2)$ the best you can do, in general?

Here are some links that might be relevant though I can't see how they would apply to the above problem as most of them are optimized for lookup only:

Fast and Easy Levensthein distance using a Trie
SO: Most efficient way to calculate Levenshtein distance
SO: Levenshtein Distance Algoirthm better than $O(n m)$
An extension of Ukkonen's enhanced dynamic programming ASM algorithm
Damn Cool Algorithms: Levenshtein Automata

I've also heard some talk about using some type of distance metric to optimize search (such as a BK-tree?) but I know little about this area and how it applies to this problem.


texts: Expected value of the distance between nodes in a binary tree

texts:
If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T?

My question here is, how do I correctly approach this question?

(Also tell me how to develop numerical skill in algorithm?)


texts: Feedback polynomial of 7-bit Linear Feedback Shift Register


texts: Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method

texts: How can I use the master's method in order to solve the recurrence formula $T(n)=3T(\frac{n}{3})+\sqrt{n}$ ?


texts:
I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution.

The setup is the standard Towers of Hanoi, except that moving the smallest disk costs one unit of time, moving the second-smallest disk takes two units of time and so on.

What is the total minimum time solving towerOfHanoi?


texts: Does TM $M$ on input $\epsilon$ ever moves its head 5 consecutive time to right?

texts:
Is language $L$ decideable ?
$$L = \{ \langle M \rangle | M \text{ on input $\epsilon$ moves it's head five consecutive time to right}\}$$
I think it is not but i am not sure about it. My reason :
if there was decider $D$ for $L$ then we could have a decider $F$ for $A_{TM}$ as follow:

F = on input $\langle M,w\rangle$ which $M$ is a turing machine:
construct $M'$
$M'$ on input $x$:
  simulate $M$ on $w$  and whenever $M$ is doing 5th right move do a dummy left and right move.
 (at first line i could check and rejects all inputs $x$ which are not $\epsilon$ but i dont think that is necessary.)
 if $M$ is going to accept state then do a five consecutive right move and then change the state to accept.
 also if $M$ rejects then $M'$ doese too.
simulate $D$ on $\langle M' \rangle$ and output whatever $D$ decides.

on high level it looks right to me but what if $M'$ itself (durring the simulation) does a 5 conscutive right move.


texts: How to compute amoritized cost for a dynamic array?

texts:
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.

Let A of size m be an array of n elements. When $n = m$, then we create a new array of size $4m$, and then copy the elements of A to the new array. When $n = \frac{m}{4}$, then you create a new array of size $\frac{m}{4}$, and copy the elements to that array.

What I am confused about is how to calculate the costs.
From what I know so far:
Before the first expansion, you pay two dollars to insert. 1$ for the insert, and 1$ you just store with the element, so that you can use that later for a copy operation.

Then when you expand it, you use that stored $ to move the element to the new array.
Now in the new array the elements won't have any $ with them. But now as you insert a new element, you use 3$. 1$ for the insert, then one more for itself (for a future copy), and one more for the previous element that was just copied.

The problem here is, what if you have an array like this:

1$ 2$

Then insert an element

1$ 2 3$ _ _ _ _ _

Now how do you handle a delete operation?


texts:
Situation :

I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-96RUg).
In the lecture the professor is proving largest number of minimum cut in a graph.

My Problem :

To prove largest number of minimum cut in a graph. Prof. first stared proving Lower Bound. To get a lower bound he took a cyclic graph. My confusion is why he took cyclic graph?

My way of Thinking :

To get a lower bound we need to select the best case input (like for selection sort best case input will be an sorted array) and here Prof. was selected cyclic graph as an input but it doesn't seems to be the best case input. Like if we choose a star (https://en.wikipedia.org/wiki/Star_(graph_theory)) we could have easily get a lower bound which is n-1.


texts: Number and probability of random allocations of n processes to n servers

texts:
I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space of allocations is n^n, and each has equal probability.

Intuitively this seems unlikely to me: if you imagine each server having a number and that number being the number of processes assigned, you wouldn't have the case of two servers being assigned n processes; yet the n^n -- as far as I can see -- assumes that such allocations are possible.

Am I missing something?


texts:
Given a language, how do you go about deciding if it's decidable or not? For example:

Given a DFA $A_0$ and a TM $M_0$

$L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$

$L_2 = \{ \langle A \rangle \, | \, A \mbox{ is a DFA and }L(A) = L(M_0) \}$

What's the intuition/process of figuring out if $L_1$, $L_2$ are decidable or not?

This is not homework, $L_1$ is not decidable and $L_2$ is decidable, but I have not idea why, and how to solve this problem and problems similar to it. If you could explain to me the process of doing that you will help a lot.


texts: Is there a total binary computable function that specifies Turing machines with nonempty domain?

texts: I am working through Bridge's computablity book and I came across this problem that does not have an answer. I don't know how to precede, any help is much appreciated.


texts:
Suppose a computer using direct mapped cache has 512KB of main memory and a cache of 4 Bytes, where each cache size is 64KB.
1)Find Number of blocks in cache.


texts: Testing two DFAs generate the same language by trying all strings upto a certain length

texts:
Given the language

$EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$

Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings upto a certain size. Calculate a size that works.

(This is from Sipser chapter 4)

I make a directed graph as usual but if two transitions $\delta(q_1, c_1) = q_2$ and $\delta(q_1, c_2) = q_2$ then the graph I am making will just have one edge for these two characters. My idea is to walk the directed graph in a way so that every transition is traversed, but when I walk over an edge forming a cycle, I would need to traverse the edges I have previously walked through in the cycle once again. Do this for both the DFAs and choose the greater number of edges traversed. Then enumerate through all the strings of this length (from the given alphabet) and the two DFAs are equal only if they accept and reject on the same strings.

I could probably write some pseudocode, but I'm not sure if this is the correct way to approach the problem even.


texts:
This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name.

I have a multiset $S$ of $n$ (not necessarily unique) integers in the range $\{1,2,\dots,k-1\}$.

The problem is to partition this multiset in submultisets such that each submultiset has a sum of at least $s$ and the number of submultisets is maximized.

For example $k=20 \wedge s=40 \wedge S= \{14, 19, 12, 19, 3,15\} \Rightarrow \{\{19, 19, 3\}, \{12, 14, 15\}\}$.

Is this a known problem? What is its complexity, considering $s, k$ are bounded small integers?


texts: How to model reversible interactive programs

texts:
Reversible programs with finite execution steps are well studied. For example, a Turing machine whose transitions are reversible and halts can be executed backwards consuming its tape in the reverse order. A variant of Turing machines with distinct input, output, and work tapes can be similarly executed in reverse to consume its output and regenerate its input, assuming it halted with an empty work tape in the forward execution (to avoid the possibility of stashing input information in the work tape).

Is there any work for the equivallent concepts in the setting of interactive programs (in the spirit of https://en.wikipedia.org/wiki/Interactive_computation)? In the three-tape Turing machine model described, it is clearly possible to have infinite interactive runs consuming an infinite input stream and emitting an infinite output stream while storing intermediate results in the work tape. Some of these programs are clearly reversible in an analogous way to the finite programs, but cannot be covered by that formalism if they are non-halting. How can we characterize reversible interactive programs in this model? We need to exclude programs that simply stash away their input in the work tape, but unlike the finite case, we can't simply require that the program ends with an empty work tape.

Is there any work on such reversible interactive programs?


texts: Why does Kadane's algorithm solve the maximum sub-array problem?

texts:
I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".

it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], A[i+1] , ... , A[j] in given array A[1] , ... , A[n].

The exercise is about developing linear-time algorithm to solve this using a following idea, (f.y.i. A[1 ,... , j] means A[1] , A[2] , ... , A[j] )

  Knowing a maximum sub-array of A[1, ... , j], extend the answer to find a maximum sub-array ending at index j+1 by using the following observation: a maximum sub-array of A[1, ... , j+1] is either a maximum sub-array of A[1,...,j]        or a sub-array A[i,...,j+1], for some 1 <= i <= j+1. Determine a maximum sub-    array of the form A[i,...,j+1] in constant time based on knowing a maximum sub-           array ending at index j." .

People said that this solution is actually Kadane's algorithm, which is relatively a simple algorithm stated on Wikipedia
(I'm really sorry that you have to move to another site. but it explains better than I do.)

However, Kadane's Algorithm deals with only a sub-array that ends at exactly j.
but above idea says I should use maximum sub-array of A[1, ... , j] and we can't guaranteed that this sub-array should end with j. Because I think this two algorithm is quite different.


texts: How does one implement Dijkstra while skipping an edge

texts:
Like let’s say you find the shortest path, but you want to find an alternate path as well. In order to do that, you have to ignore each edge in the shortest path one at a time, and then find the shortest path without using that respective edge. At that point you have a set of alternate paths, of which you want to select the one that is the shortest yet also different enough.

But I don’t know how to find the alternate paths while skipping edges. Could anyone please clear this up


texts: The No-Free-Lunch Theorem and K-NN consistency

texts:
In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large error, with high probability.
The conclusion is that in order to learn, the hypotesis class or the distributions must be restricted.
In their book "A probabilistic theory of pattern recognition", Devroye et al prove the following theroem for the K-nearest neighbors learner:
$$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.}
\text{ if } n>N \quad P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon  ^{2}) $$
Where $R^*$ is the error of the bayes-optimal decision, and $R_n$ is the true error of the K-NN output (the probability is over the training set of size $n$). $C_d$ is some constant depends only on the euclidean dimension.
Therefore, we can get as close as we want to the best hypothesis there is (not the best in some restricted class), without making any assumption on the ditribution. So I'm trying to understand how this result does not contradict the NFL theroem? thanks!


texts: What type of formal notation is being used here to represent functional algorithms?

texts:
Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design.  I have experience with a number of programming languages, but my only experience with functional programming is in Scala.  I understood that I would have to pick-up Standard ML and Haskell from the description of the book, but when I started reading the first section, I wasn't familiar with some of the operators being used.

Here are some examples of function definitions from the first chapter of the book (free to preview on Amazon):

I have seen "^" and "v" used to represent "and" and "or," but some of the other syntax (like False (0,n)) still throws me off.

In this one, I'm not sure what the accumArray(+)... is referring to.  I'm thinking it's like a fold method using addition, but I don't understand the rest of the line.

Here, the author has done a good job of describing that \\ is set difference and the two vertical lines crossed with a horizontal one is union.  However, I've never seen anything like that union symbol before.

I don't want to know what each of these examples means as much as I want to know what library of formal representation is Bird using to represent these algorithms, and also, if a specific programming language (Haskell/SML?) syntax is being used as well in conjunction with these special symbols.


texts: Source Coding Theorem: what happen when go below N⋅H(x) bits?

texts:
I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website.

I have question on the source coding theorem (emphasis mine):

  Shannon's source coding theorem (p81): $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to \infty$; conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.

My question is the emphasised part of the above, what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), which he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for the risk tolerance between $0< \delta< 1$. (So it becomes more flat as indicate on the diagram).

Therefore,  $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take. In the theorem above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?


texts: Why do compute time complexity for algorithms?

texts:
I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor. Some algorithms have a worst-case time of $O(n)$ or $O(n^2)$ or $O(n^3)$.

What I want to know is what is the best time complexity of an algorithm? And why?


texts: How do you compare algorithms based on scaling of their cache misses?

texts:
We all know how to use “Big O” notation to show how CPU instructions run increase as the size of the dataset increases.   E.g.  a quick sort is O(n log n).

However for the last few years, instructions that don’t access any data outside of the level 1 cache have been close to free compared to instructions that hit main memory.

So is there some notation that is as clear as the “Big O” notation to help capture the sort of effect?


texts: When give two encodings rise to the same notion of computability?

texts:
To my understanding, the notion of Turing-computability of a partial map $ℕ_0 \dashrightarrow ℕ_0$ depends on the encoding of $ℕ_0$.

Say $Σ$ is an alphabet and $γ \colon Σ^\ast → ℕ_0$ is a bijection. A partial map $f\colon ℕ_0 \dashrightarrow ℕ_0$ is then called computable with respect to $γ$ if its conjugation $γ^{-1} ∘ f ∘ γ \colon Σ^\ast \dashrightarrow Σ^\ast$ is computable by a turing machine over the alphabet $Σ$.

So say we have two bijective encodings $Σ^\ast → ℕ_0$ called $γ$ and $γ’$. Give these encodings rise to the same notion of computability if both make some basic maps $ℕ_0 → ℕ_0$ computable?

For example, if the successor map $ℕ_0 → ℕ_0$ is computable with respect to both $γ$ and $γ’$, are then all computable maps $ℕ_0 \dashrightarrow ℕ_0$ with respect to $γ$ and $γ’$ the same?

This seems intuitive to me, yet I don’t know if it’s true.


texts:
Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?

Let:

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,\\
\forall_{C_i} \left.C_i=(p \oplus q)\right|_{\left(p\in \mathbf x \vee\neg p\in\mathbf x\right),\left(q\in \mathbf x \vee\neg q\in\mathbf x\right)}
$$

The $\text{2-XOR-SAT}$ problem is to find a satisfying assignment of $\mathbf x$ that would make $\Phi\left(\mathbf x\right)=T$. This is in $P$, as it can be encoded in a set of linear equations mod $2$.

The $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ problems are to maximize or minimize the number of true values in $\mathbf x$, respectively, subject to the constraint that $\Phi\left(\mathbf x\right)=T$.


texts: Assuming the original instance is not easy in NP-hardness reduction

texts:
Partition problem: given a non-empty finite set $P = \{p_i : i ∈ I = \{1,\dots,m\}\}$ of $m$ positive integers such that $\sum_{i=1}^m p_i = 2T$, can $I$ be partition into two disjoint subsets $I_1, I_2$ such that $\sum_{ i \in I _ 1} p_i = \sum_{ i \in I _ 2} p_i = T$?
My question is: when we deriving reduction from Partition to another problem, can we assume that $\max_{ i\in I} p_i \leq T$?


texts:
Given a WAVL tree with pointers to its' minimum and maximum, we will add two operations:

Insert-Max: given an element, which is bigger than all other elements in the tree, add it as the right child of the maximum element, and update the max pointer.

Delete-Min: find the successor of the minimum element, delete the minimum element and update the min pointer.

Rebalancing after inserting and deleting elements will be as in regular WAVL tree.

We are given a sorted array of $n$ elements and an empty WAVL tree.

We will do $n$ Insert-Max operations on all elements of the array, from smallest to biggest, and then we will do $n$ Delete-Min operations.

I would like to find the worst cast bound for one operation in the described sequence of operations, which will cover both Insert-Max and Delete-Min.

We know that the amortized cost of a rebalancing operation is WAVL tree is $O(1)$, but I'm not sure what can be said about the worst case.

Any help is appreciated.


texts:
i get stuck in one sentence in machine learning.

i read tom Mitchel book on ML, and some other materials.

if we have small training set, always over-fit can occurs?  or is likely to occurs?

i read lots of material but i'm not sure that which of my fact will be correct.

any solution or idea?


texts: Can all permutations of a set or string be generated in O(n log n) time?

texts:
I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye:

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes only O(n log n) time for all permutations in total, so only O(1) -- constant time -- per permutation.

This seemed strange to me because the best method I was aware of to generate all permutations of a string is in O(2^n) time. Looking through the other results, I came across a response to a similar question which states: While it technically produces the desired output, you're solving something that could be O(n lg n) in O(n^n)

I am aware of an algorithm to unrank permutations in O(n log n) time, but these responses seem to imply that all permutations in total can be generated in time O(n log n). Am I misunderstanding these responses?


texts:
Given a metric space $X$ with finitely many points, and a nonnegative integer $n$, I want to find a set of $n$ points in $X$ which maximizes the minimum distance between any two points.

What algorithms are there to do this?


texts:
I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm:

do i=1, n
  do j=1, n
    A[i, j] = A[i-4, j-4] + A[i-3, j-3] + B[i, j]
  end do
end do

I was thinking that the best i could do here is a loop skewing (but with what factor?) and loop interchange that would allow me to finally have a DOALL on the inner loop. Any feedack and help regarding those thoughts?


texts: What does $|w|$ mean in the statement " $|w|$ where $w \in L \subset \Sigma^*$"?

texts:
In my assignment I find these symbols:

$|w|$ where $w \in L \subset \Sigma^*$

I believe it means the lexikografic value of a word, but I am not 100% certain.

Let me phrase my question this way: could this notation have any other meaning ?


texts: How many 3-SAT expressions with up to N variables are satisfiable?

texts:
TL;DR

There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-sat expressions with exactly 4 variables. Of those, how many are satisfiable? How did you get that number?

Problem Statement

Assume you have a 3-SAT equation where all the clauses have exactly 3 distinct variables (i.e. $X$ and $\neg X$ will never appear in the same clause), and no clause appears more than once (i.e. some expression won't have both $(X \lor Y \lor \neg Z)$ and $(X \lor \neg Z \lor Y)$). With this construction, there are a finite amount of expressions with only N variables.

For the class of expressions with up to N variables, is there an equation to compute how many are satisfiable?

Example of N=3

For example, with N=3, there are 254 solutions.

We know this because for N=K, there are exactly $8 *\binom{K}{3}$ distinct clauses, as you must select three distinct variables for each clause, and 1 of 8 possible sign values for those variables (+/+/+, +/+/-, +/-/+, +/-/-, ...). If there are $8 *\binom{K}{3}$ possible clauses, then there must be $2^{(8 *\binom{K}{3})} - 1$ possible boolean expressions, because each clause may appear or not (so $2^{(8 *\binom{K}{3})}$) and we have to subtract one for the case with no clauses.

For N=3, there are 255 possible expressions (using the lemma above), and only one is unsatisfiable. So there must be 254 distinct satisfiable expressions.

How about for N=4?


texts: Weighted Interval Scheduling with constraint

texts:
How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do we solve it when we need to find the maximum weight that cannot exceed a given weight?

Formally:

Given n tasks with start and finish times s and f, and weights w, return the tasks that result in maximum weight that does not exceed a given constant G. You can assume s,f,w and G are all positive integers.


texts:
Is there a fast algorithm to compute dominator tree for acyclic graphs?

The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?


texts: Do all greedy algorithm produce just the first solution, no matter how bad it is?

texts:
In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the first set that satisfies the constrain under greedy strategy.

For example, in the activity selection problem, all we need to do is to go down the list and keep finding solution of the type $d_i$ > $f_j$, and the first list that returns (even if it is near empty) is considered the greedy solution.

My question is that this strategy doesn't even take into consideration of any other case which may be better, is this the signature of greedy algorithm?

Thanks


texts: Mean and variance of number of buckets of length $i$ in hashing with chaining

texts:
Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $i$. Then the cardinality $s = |S|$ of the set $S$ is
$$ s = X_1 + 2 X_2 + \cdots + i X_i + \cdots \enspace. $$
Clearly the summation can end at $i=s$. The number of non-empty buckets $s_m$ is
$$ s_m = X_1 + X_2 + \cdots + X_s \enspace.$$
I am interested in upper bounding $s-s_m$ for my application.
$$ s-s_m = X_2 + 2 X_3 + \cdots + (i-1)X_i + \cdots \enspace.$$
In the previous equation:

$s_m$ is known by $s$ isn't. However, $s$ is fixed and is not a random variable.
$X_i$ for $i\geqslant 2$ is also the number of $i$-wise collisions.

For $i=2$, if we are using k-independent hash functions with $k$ at least 4, we know the mean and variance of $X_2$ as a random variable [1, Lemmas 1 and 2]. Therefore we can bound $X_2$ from above w.h.p. using Chebyshev's inequality: $X_2\leqslant s_m^2/m$.

I am asking whether other works discussed the mean/variance of $X_i$ for $i>2$, or whether it possible to bound the quantity above with other means.

I can already generalise lemma 1:

  Lemma   Suppose that $s$ elements, denoted by $e_1,\ldots,e_s$, are hashed   into a table of size $m=\beta s$ by a random function $h$
  is a   $k$-independent class $H_k$, $k\geqslant t$ for $t\geqslant s$.
  Let   $Y_{i_1\cdots i_t}$ be an indicator variant whose balues is $1$
  if   and only if elements $e_{i_1},\ldots,e_{i_t}$ hash to the same
  location. That is $h(e_{i_1})=\cdots=h(e_{i_t})$. Let $X$ be the
  random variable whose value is the number of $t$-wise collisions
  between elements, that is,   $$X=\sum_{1\leqslant i_1 < i_2 <\cdots < i_t \leqslant s}    Y_{i_1\cdots i_t} \enspace.$$
  Then   $$ \mathbb E[X] = \binom{s}{t}
 \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace. $$

  Proof   Since $H$ is $k$-independent for some $k\geqslant t$,   $$\mathbb E[Y_{i_1 \cdots i_t}] = 1/m^{t-1} \enspace.$$ Hence   $$ \mathbb E[X] =
 \sum_{1\leqslant i_1 < i_2 < \cdots < i_t
       \leqslant s} \mathbb E[Y_{i_1\cdots i_t}] = \binom{s}{t}
     \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace.  $$

Probably Lemma 2 can be generalised as well, although the combinatoric counting will be a little bit more challenging. However, is there a solution that we can stick only with 4-independent hash function not with s-independent hash functions, since $s$ is unknown?

UPDATE: A generalisation of Lemma 2 may be obtained. The combinatoric counting is shown here.

Thank you,

1 Broder, A., & Karlin, A. R. (1990). Multilevel Adaptive Hashing. SODA'90. http://dl.acm.org/citation.cfm?id=320181.


texts: Find $b$-th bit of a number $n$, with sign

texts:
Let $n\in\mathbb{Z}$ and $0\leq b\leq63$, $b\in\mathbb{N}$. Find the $b$-th bit for the number n on it's $64$ bit representation with sign.

and $T$ be the number of test cases.

This is my attempt:

#include <iostream>
#define f cin
#define g cout
using namespace std;

int T;
long long n;
int b;

int main()
{
    f >> T;
    for(int i = 1; i <= T; ++i)
    {
        f >> n >> b;
        int ans = 0;
        bool ok = true;
        while(n)
        {
            if(b == ans)
            {
                g << n % 2;
                ok = false;
                break;
            }
            n /= 2;
            ++ans;
        }
        if(ok) g << 0;
    }
    return 0;
}

but it does not work on all test cases... also is there another way to do this? or is there another way to store the bits? is there some special libraries? can you do this more efficiently with other tools?  can you give me some information to read about bitmasks? and where and when you should use them and how are they usefull?


texts: Would it be correct to characterize loop invariants as a type of tautology?  I ask since the invariant must basically always be true, before the loop starts, before each iteration and after the loop terminates.  I realize that there is the possibility that the invariant could become false during the body of the loop.  But since inside the loop "doesn't count" is it fair to characterize the invariant as a tautology?


texts: Is detecting easy instances of NP-hard problems easy?

texts:
My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible to find a deterministic polynomial-time algorithm to solve this particular instance $I$?

For example: Suppose that $\Pi$ is GRAPH COLORING. The adversary gives you a graph $G$ with $n$ vertices.

The adversary knows that $G$ is complete but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $\Delta +1$ colors"?
The adversary knows that $G$ has some property $P$ but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $b$ colors"?
...


texts: Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

texts:
The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as:

FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y))$

I understand its purpose and I can trace the execution of its application perfectly fine; I would like to understand how to derive FIX from first principles.

Here is as far as I get when I try to derive it myself:

FIX is a function: FIX $\triangleq \lambda_\ldots$
FIX takes another function, $f$, to make it recursive: FIX $\triangleq \lambda f._\ldots$
The first argument of the function $f$ is the "name" of the function, used where a recursive application is intended. Therefore, all appearances of the first argument to $f$ should be replaced by a function, and this function should expect the rest of the arguments of $f$ (let's just assume $f$ takes one argument): FIX $\triangleq \lambda f._\ldots f~(\lambda y. _\ldots y)$

This is where I do not know how to "take a step" in my reasoning. The small ellipses indicate where my FIX is missing something (although I am only able to know that by comparing it to the "real" FIX).

I already have read Types and Programming Languages, which does not attempt to derive it directly, and instead refers the reader to The Little Schemer for a derivation. I have read that, too, and its "derivation" was not so helpful. Moreover, it is less of a direct derivation and more of a use of a very specific example and an ad-hoc attempt to write a suitable recursive function in $\lambda$.


texts: How do I determine the basic operation of this algorithm?

texts:
Admissions:

Yes, this is a homework assignment.
No, this is not me trying to outsource my homework to the internet.

I am honestly fazed by my teacher's explanation of the "basic operation", and the internet is not helpful either. I get lists that say what a basic operation can be (e.g. assignment, multiplication, comparison), and what it is used for (determining time complexity) but not how to determine it for a given algorithm.

Here is the algorithm in question.

// Problem: Search a given value K in a given array A by sequential search
//Input:  array A[0..n − 1] and a search key K
//Output: The index of the first element in A that matches K and −1 if there are no matching elements.

SequentialSearch(A[0..n − 1], K)
{
   i ←0
  while i < n and A[i] ≠ K do
  {
    i ←i + 1
  }
  if i < n
     return i
  else
   return −1
}

The question: is the basic operation assignment, or comparison?

Candidates that I see:

Comparison: A[i] ≠ K
Assignment: i ←i + 1

The problem is that both of these would work to determine time complexity. The comparison is executed 1 time in best-case and n times in the worst-case scenario. The assignment is executed 0 times in best-case and n-1 times in worst-case. Towards infinity, constants do not matter, so really they both work equally well.

So the irony is that I know the time complexity of this algorithm, but not the basic operation which I am supposed to determine to figure out the time complexity.

What is the logic to use here to figure out which one is the basic operation, and which one isn't?


texts: How to identify object(s) in image when given a list of all images?

texts:
I see a lot of articles and topics about OpenCV and machine learning in regards to identifying general things (like cats, or alphanumeric characters) but I am wondering if something more specific is easier/detailed somewhere.

Basically, if I have a folder of 20 images, how would I identify those images contained with another image?  Like for a game, where you have to find all the hidden items in an image but are given a list of the items to find.

To make this even easier, let's just pick one image to find within another and also assume this image to search in won't even change the original image at all (no skewing or rotating), just put it (non-overlapping) somewhere zero or many times.  If done correctly, I would imagine the results would be an array of rectangles that contain each instance of the image.  Just looking for any assistance in learning how to write a program that can do this, even if its just articles/books regarding the technique.  Thank you


texts: I'm asking for a sequence of instances for SAT, one instance for each length, such that the sequence takes exponential time with MiniSAT.


texts:
According to this chart, DCFLs are closed under reversal.

However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and pops) for this seems to depend on non-determinism in choosing the null transition to take from the initial state (since the new initial state would contain a null transition to all the old final states).

This would make the "reverse PDA" of a DPDA non-deterministic whenever there is more than a single final state in the original DPDA.

What is the fallacy in my argument? Or is there another way to go about proving this?


texts: why the big-oh of a linear function is n^2?

texts:
I know the definitions and differences of big-theta, big-oh, and big-omega in finding time complexity of algorithms. what I can't understand is that why the big-oh of a linear function cannot be O(n).

$0 \le an + b \le cn \Rightarrow  c = a + \frac b {n_0}$

so we could find a value for constant $c$. as a result, the big-oh of a linear function can also be $n$. am I right??

Note: I have read all the previous answers and questions in this commission and others. but I didn't understand. that's why asked a new question


texts: How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

texts:
If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the total amount of clauses?

I realized after posting that we can't guarantee that the number of clauses can be reduced.  However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we guarantee the total number of clauses can be reduced by? For instance, if we start with $k$-SAT with $n_k$ clauses, what is the smallest guaranteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to $(k+m)$-SAT?

More importantly, how do we carry out this conversion?


texts: Find the exactly correct separating hyperplane of SVM when the data is not perfectly linearly separable

texts:
I am thinking about the following case where the data in region 1 is always positive and the data in region 2 is always negative, but the data in region 3 can be both positive and negative. Are there any existing results on finding exactly the $l_1$ and $l_2$ (or region 3)?

As far as my understanding of SVM when the data is not perfectly linearly separable, we can maximize the soft margin to find the separating hyperplane. We can control the penalty of misclassification to achieve different separating hyperplanes. But is there a method for finding the exactly correct separating plane like $l_1$ and $l_2$? I am not very familiar with SVM, and I would really appreciate it if you can provide some comments or references.


texts:
While going through bubble_down implementation for min-heap in The Algorithm Design Manual By Steven Skiena, since routine pq_young_child gives the index for youngest child which can be replaced with the parent I feel the lines 10 - 13 are useless or maybe I am not able to identify the cases it handles. Here is the implementation given in the book.

bubble_down(priority_queue *q, int p)
{
    int c;                /* child index */
    int i;                /* counter */
    int min_index;        /* index of lightest child */

    c = pq_young_child(p);
    min_index = p;

    for (i=0; i<=1; i++)
        if ((c+i) <= q->n) {
            if (q->q[min_index] > q->q[c+i]) min_index = c+i;
        }

    if (min_index != p) {
        pq_swap(q,p,min_index);
        bubble_down(q, min_index);
    }
}

Do these lines handle any specific corner cases? I can't come up with the test cases which would fail if I remove these 4 lines.