texts:
If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?
I think that as we know nothin about $M$, in general case we can't  determine wherther a random element $m$ belongs to $M$, so we coundn't say anything about $A \cap M$. Am I right?


texts: Shannon Entropy of 0.922, 3 Distinct Values

texts:
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.

Taken from the introduction on this wikipedia page:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?

Thank you in advance.


texts: Necessary and sufficient condition for unique minimum spanning tree

texts:
This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13]
.

  Prove that an edge-weighted graph $G$ has a unique minimum spanning tree if and only if the
  following conditions hold

  For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.
  The maximum-weight edge in any cycle of $G$ is unique.

Consider the "$\Rightarrow$" direction and the following graph $G$.

$G$ has a unique MST. However, for the partition $\{A\}$ and $\{B,C\}$, the minimum-weight crossing edge is not unique.

  Did I misunderstand some points? Or if there are flaws in the theorem, how can we fix it?


texts: Showing that CLIQUE can be verified in polynomial time

texts:
The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is

in NP and
there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in polynomial time.

Part 2. above is fine -- all over in every resource and very well explained. For Part 1., from what I know, we need to have the following: Given a specific solution instance, we need to show that it can be verified, in polynomial time, that that solution is an answer to this problem. So for instance, given a specific graph and a subgraph of it, we should be able to check whether that subgraph is a clique of maximum size in that graph.

The resources I've read so far are phrasing this Part 1. here as "easy, straightforward, etc" or "it can be shown in $O(n^2)$ time that the given subgraph is a clique/not". However, the verification here is not just whether it's a clique, but also is whether it is a maximum clique in the graph. How can this be decided in polynomial time?

What am I missing here?


texts:
How to prove that language $L = \{G \; | \; \omega(G) \geq \frac{9}{10}\cdot n\}$, where $n$ - number of vertices in the graph, NP-hard?
$\omega$ - is a clique number.


texts: How are hash tables O(1) taking into account hashing speed?

texts:
Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity.

However, this assumes the lengths of the elements are constant. Computing the hash of an element requires going through the element, taking $\Theta(l)$ time where $l$ is the length.

But to discriminate between $n$ elements, we need the elements to have length at least $\lg n$ bits; otherwise by pigeonhole principle they won't be distinct. The hash function going through $\lg n$ bits of element is going to take $\Theta(\lg n)$ time.

So can we instead say that the speed of a hash table, taking into account a reasonable hash function which uses all parts of the input, is actually $\Theta(\lg n)$? Why, then, are hash tables in practice efficient for storing variable-length elements, such as strings and large integers?


texts: Why doesn't the C/C++ compilers create different tokens for different types of numbers?

texts:
Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc.

However if we have something like this:

int A[10.5];

then will there be a parser error or semantic error?

The book that I'm reading says the parser rather than the semantic routines will detect it, but after the lexical analysis wouldn't that be converted to this:

A[Constants];

meaning the 10.5 will be converted to a Constants token based on that website? Therefore the parser will not notice this is an error because both of 10 and 10.5 will be Constants!

So which one is right? Will the parser or one of the semantic routines detects this error? Do the C/C++ compilers create the same tokens for int numbers and floats?


texts:
I know 15s complement subtraction may not be much taught/popular one, but I just want to give it a try. Just trying to clear my basic digital logic/number systems concepts.

Here is what I am doing:

Normal decimal subtraction

$(339)_{10}-(401)_{10}=(-62)_{10}$

1's complement subtraction

$(101010011)_2-(110010001)_2=(101010011)_2+(001101110)_{\text{1s comp}}=111000001$
No end over carry generated. That is the result is -ve and is in 1's complement form. Taking back 1's complement, we get $000111110$. Thus the solution is $(-000111110)_2$

This sounds correct as $(62)_{10}=(111110)_2$

However this is not working with 15's complement:

15's complement subtraction

$=(153)_{16}-(191)_{16}=(153)_{16}+(E6E)_{\text{15s comp}}=FC0$

No end over carry, means result is -ve in 15s complement form. Taking back 15s complement we get 03F. So the solution is $(-03F)_{16}$

However this does not sound correct as $(62)_{10}=(3E)_{16}$ not $(3F)_{16}$.
Where I am doing silly mistake? Or I am completely messed up?


texts:
Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$.
Is this CFL? How do I write CFG for it or prove it with pumping lemma?
Thanks.


texts: Proving that Every Full Prefix-Free Language is Maximal

texts:
I'm practicing a problem where I need to prove that every full prefix-free language is maximal.

I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, where a prefix-free language is full if,

$$\sum_{x\in A} 2^{-|x|} = 1$$

Furthermore, I know that a language A ⊆ {0, 1}* is prefix-free if no element of A is a prefix of any other element of A and that the Kraft inequality says that for every prefix-free language A,

$$\sum_{x\in A} 2^{-|x|} \leqslant 1$$

I'm pretty sure that a full prefix free language is maximal, since it belongs to the maximal prefix-free set. I don't know, however, how to formally prove this. Should I be doing induction with Kraft's Inequality and with what I know about the relationship between maximal and prefix-free sets?

Any help would be appreciated!


texts: General methods for polynomial reductions?

texts:
Let's say you want to show $A \leq_{p} B$ (this is usually in the context of showing $B$ is NP-complete, but I'm just asking about the reductions. We are specifically looking at polynomial (Karp) reductions. Also, specifically decision problems--the answer is YES or NO)
Here's how I'm thinking of it. Reach into a bag for a hypothesis function f.
Now check:

Does $f$ actually map instances of $A$ to instances of $B$? (eg, if I am reducing to Traveling Salesman, did I actually make a complete graph).
If $a \in A$, is $f(a) \in B$?
If $a \notin A$, is $f(a) \notin B$? (alternatively, if $f(a) \in B$, is $a \in A$)?
Does $f$ take polynomial time?
Given a certificate to $a \in A$, will I be able to concoct a certificate for $f(a) \in B$?

Sometimes, these restrictions will yield more questions. If $f$ didn't work, then I try to consider why it didn't work and how I can change $f$ so that it works. But I'm often getting stuck by not being able to think of all the possibilities for $f$.
If $f$ works on all these things, you can conclude $A \leq_{p} B$. (5 may not be necessary, I'm not sure. But it's still a good question to ask).
These questions come about from using the definition of what a polynomial reduction is. But I was wondering, are there other questions or strategies that can be applied in general? I think (in the context of an exam) I will be told what to reduce from (things like Subset-sum, Hamiltonian paths, Traveling Salesman, etc).


texts: What is the advantage of product quantization?

texts:
I'm reading Product Quantization for Nearest Neighbor Search. Quoting page 4:

  The strength of a product quantizer is to produce a large set of
  centroids from several small sets of centroids: those associated with
  the subquantizers

Can someone please try to explain why this happens?

My interpretation so far is that (using the paper's annotation) if each sub-vector has dimension $m$ (where $m$ is a multiple of $D$, i.e. the original vector dimension), with $k^*$ centroids for each sub-quantizer, we have that the total number of possible centroids $k$ is:

$$k = (k^*) ^ m$$

So we can obtain an huge number of centroids from a small set of $m  k^*$ centroids.

Is that correct? Please help me understanding this concept :)


texts: The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive structures in English, and that's about all anyone seems to say.


texts: Three-address code versus JSON, XML, etc

texts:
I'm working on a compiler. The textbooks I have say to output a 3-address intermediate code. This can be translated into the target language of choice.

I don't have a problem with the bulk of the source being translated to 3-addr code. But for the data-rich symbol table, this is awkward.

Is the exclusive use of 3-addr code old, obsolete advice? My compiler is multi-pass compiler. I'm working pretty hard to build a symbol table in my first pass, and I'm pretty much having to reconstruct it in 3-address code for the next pass. This seems like make-work to me when I could create from my symbol table XML or JSON.  I could write that to the intermediate file instead.

How should I represent my symbol table in the intermediate code?


texts:
In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a different theoretical framework from implementations like awk or sed. Cox claims a difference in performance between 60s and 20microseconds (the difference is an order of magnitude of millions!). Link to the article.
Is this issue still up-to-date? That is, is the theory behind these groups of implementations basically different?
Is there any real life scenario when a programmer would need to pick some Jurassic implementation like awk (due to its solid theoretical framework) because otherwise the task at hand could not be dealt with?


texts: Count all possible 2-3-monotone sequences

texts:
Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as:

$s_i < s_{i+2}$, for $1 \leq i \leq N-2$
$s_i < s_{i+3}$, for $1 \leq i \leq N-3$
$s_i \in \{1,\dots, N\}$

Given $N$, calculate all the possible sequences of length $N$ given above formula.

I have already come up with a solution in $\mathcal{O}(N^3)$, but that's too slow for $N=1000$. For my solution I used dynamic-programming, but I cannot come up with a recursion which would allow me a better complexity. As far as I've discussed it with others, there is a $\mathcal{O}(N^2)$ dynamic programming algorithm.

Example: For $N=3$ we have $9$ such sequences, i.e:
112,
113,
122,
123,
132,
133,
213,
223,
233


texts: Why is binary search called binary search?

texts:
I heard several possible explanations, so I would like some trustable reference.

Update 05.19:
I'm interested in the question because one of mine students wrote in his thesis that the name comes from the below explanation (1). Until now I thought/heard that it comes from explanation (2). I would feel bad both for letting the wrong thing in his thesis, as well as telling him to remove it if it might be right.

(1) Consider the search for an integer in the interval $[0,2^{n-1}]$.
We can find it using $n$ questions by asking in step $i$ the $i^{th}$ binary digit of the number.

(2) If we have a search space with $2^n$ elements, we can find an unknown element by questions that repeatedly split the remaining part of the space in two.

And yes, I know that (2) can give the same algorithm as (1) but that's not the point here.
(2) can be also applied for more general problems.


texts: Is the following true? log2(2n) ∈ O(log2(n))?

texts:
Is $\log_2(2n) \in O(\log_2(n))$ ?

I don't know how to prove whether this is true or false.
Any help is appreciated


texts: How to find number of permutations of 1-N length, each [1-N] with k values

texts:
This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values.

A real-world example might include 5 different single-digit combination locks.

How many different ways could I lock a single gate, assuming that I can use any number of locks?

Assuming that each lock takes values ([1-3], [1-3], [1-3], [1-3], [1-3]) There would be 3^5 ==  243 possible combinations. But I'm also interested in calculating the total number of combinations possible by using subsets of the 5 locks, so adding the solution for each combination of four locks, each combination of 3 locks and so on. The solution would also ideally be generalisable so that each list of values can differ i.e. ([1-2], [1-10], [A-C] ... )

Does there exist a mathematical solution to this problem?

edit:

In the main, the question is about a general purpose mathematical solution. For example, to find the number of combination of a set of length (3), one uses 3! ie. 6 combinations of [1,2,3].

I was wondering if there exists a general purpose solution to the above scenario. If not, I would think it could be possible to program something to recurse over the possibilities, which I guess is why I decided to post it here first as my search for a mathematical solution came up empty handed.

Some examples of inputs and outputs as requested:

input = [A,B,C] [1,2,3,4,5] [G,H]

output combinations are all possible combinations of those three lists, without needing to sample all three lists. Note combinations, hence [A1G] == [G1A]

i.e. (this is not all the combinations):
A
B
C
A1
A2
A3
...
C4
C5
A1G
A1H
A2G
A2H
...
C5G
C5H
...
1
2
3
4
5
1G
1H
.
.
5G
5H
..
G
H


texts: Recurrence $T(n) = 2T(\sqrt{n}) + \log n$

texts:
So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book (Introduction to Algorithms, Third Edition pg. 86). I'm having a hard time understanding how they rename $m = \log n$.

They then get the new equation $T(2^m) = 2T(2^{m/2}) + m$. I see that turning the $m = \log n$ into $2^m = 2^{\log n}$ and using the property $a^{\log b} = b^{\log a}$ so you get $2^m = n^{\log 2}$ which goes to $2^m = n$ and hence $\sqrt{n} = 2^{m/2}$.

My question is, how do you know to guess to substitute $m$ for $\log n$?


texts:
can someone pls help
How do I prove

2⌊lg n⌋ = Θ(2⌈lg n⌉)
2 ⌈lg n⌉+⌊lg n⌋ = Θ(n2)

I'm not too good at maths.
I know,
lim ( n -> infinty) = f(x)/g(x) if we get a real constant the statement is true.


texts: Is it feasible to generate every possible RGB image?

texts:
This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent resolution then that of all the atoms we estimate are visible in our universe.

This makes sense because an image of a decent resolution (like the image displayed your computer monitor) should be able to contain every picture imaginable, every frame from every movie ever made and never made. It would contain every correct and incorrect mathematical equation. Or even every book/webpage that will exist or can exist. It's intriguing to think it would be possible to generate every possible image because it contains all knowledge but also all anti-knowledge which means there is a lot of stuff to sift through including lots of random noise.

The only other research into this topic that I could find is this art project, where they wrote some code to generate all 15x10 pixel black and white images which is estimated to take approximately 46 quinvigintillion or 4.6x1079 years to complete.

So is it feasible to generate every possible RGB image (of a decent resolution)?


texts: Why register access bandwidth is higher then residing inside CPU cache?

texts: Access to registers claimed to be faster then cache. Why is it? Is it because cache has less wires or spatially further from functional units?


texts:
Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct?

  If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in P$ is false

I think this means that since $Y$ is not polynomial time solvable, and it is reducible to $X$, then X is not polynomial time reducible. This makes sense to me, but the statement ends with a false, how is that?

  If  $Y \leq_p X$ and $X$ is solvable in constant time, then $Y$ is
  solvable in constant time as well

Seems pretty intuitive, if you can reduce to $Y$ using a polynomial reducer, then it should also be solvable in constant time. But I have the nagging feeling that it wouldn't be constant time since polynomial time > constant time.

  Say you have $SORT$ which checks if the list of ints is sorted, then
  for all $X$ we have $SORT \leq_p X$

I don't get this at all, how can the $SORT$ algorithm be reducible to all $X$, isn't that a bit too farfetched?

  Assume $Y \leq_p X$, if $Y$ doesn't have a polynomial time algorithm
  to solve it, then there isn't one for $X$ either

I think this implies that since $Y$ is not solvable in polynomial time then neither is $X$, but isn't that false? Isn't the whole purpose of us using reductions is to show that we can reduce one to another that already has a solution, thus translating the solution?


texts:
I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$
which I want to build a simple jump table for (not considering special optimizing cases for now).
I only want to build a jump table based on matching suffixes of $P$ (the bad character rule is not relevant here).
The problem is to build a table such like this one:

where suffix[i] is the longest suffix of $P[1 \ldots i]$ that is also a suffix of $P$ as a whole
and beta(i) is a heuristic which tells how much you may shift the pattern against an arbitrary text $T$ on mismatch.
I am able to build the suffix-table but I have no idea how to use these values to build the beta array/function from that. The definition the professor gave me for this is also really sloppy and a jumbled mess of indices which does not give me any intuition.
Just by looking at it you could spot that for example at $i = 6$ you have beta(i) = 2. If we look at the pattern we have the suffix $P[6 \ldots 8]$ and the closest occurrence of this suffix is at position $i = 4$. If we shift by $2$ we have these characters aligned for free. But it could also be the suffix $P[7\ldots8]$ ($i+1$) and its reoccurrence at $i = 5$ which would result in the same shift.
We notice: for $i=6$ we want to find the longest suffix starting at $i$ (or $i+1, i+2, \ldots$?) which is also a suffix of some prefix of $P$. (which, essentially, is a substring but I guess defining it as a suffix of a prefix makes more sense since I need to use the suffix-table)
So

Do we always want to find occurrences of suffixes of $P$ starting at $i$ or any suffix from $i$ onwards up to $m-1$?
If there are both, which one to choose? The longest?
How did these $7$s get calculated?


texts: Difference between cross edges and forward edges in a DFT

texts:
In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).

There are some leftover edges connecting some of the other nodes. What is the difference between a cross edge and a forward edge?

From wikipedia:

  Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

Doesn't an edge that is not used in the traversal that points from one node to another establish a parent-child relationship?


texts:
I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'.
 The non-ambiguous if-else statement I took from the dragon book, which turns to be ambiguous when I add the braces. To build the parser and test it I am using the Ply library written in Python.

The grammar terminals/nonterminals specification is backwards here - Uppercase strings are the terminals and Lowercase are the non-terminals. Also the grammar below is not ambiguous untill you try to enclose the if-else with {} which is tokenized as LBRACE and RBRACE.

Below is the grammar specification:

Rule 0     S' -> program
Rule 1     program -> function_definition program
Rule 2     program -> empty
Rule 3     function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN block
Rule 4     function_definition_args -> var_list
Rule 5     function_definition_args -> empty
Rule 6     var_list -> var_declaration COMMA var_list
Rule 7     var_list -> var_declaration
Rule 8     var_declaration -> data_type ID
Rule 9     data_type -> VOID
Rule 10    data_type -> INT
Rule 11    data_type -> FLOAT
Rule 12    data_type -> STRING
Rule 13    data_type -> CHAR
Rule 14    block -> LBRACE statements RBRACE
Rule 15    statements -> statement statements
Rule 16    statements -> empty
Rule 17    statement -> matched_statement
Rule 18    statement -> unmatched_statement
Rule 19    matched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE matched_statement RBRACE
Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE
Rule 23    logical_expression -> logical_term OR logical_term
Rule 24    logical_expression -> logical_term
Rule 25    logical_term -> logical_factor AND logical_factor
Rule 26    logical_term -> logical_factor
Rule 27    logical_factor -> boolean_statement
Rule 28    logical_factor -> NOT logical_factor
Rule 29    logical_factor -> LPAREN logical_expression RPAREN
Rule 30    boolean_statement -> value comparison_op value
Rule 31    boolean_statement -> value
Rule 32    value -> ID
Rule 33    value -> NUMBER
Rule 34    comparison_op -> LESS_THAN
Rule 35    comparison_op -> LESS_EQUAL
Rule 36    comparison_op -> GREATER_THAN
Rule 37    comparison_op -> GREATER_EQUAL
Rule 38    comparison_op -> EQUAL
Rule 39    command -> compound_statement
Rule 40    command -> simple_statement
Rule 41    compound_statement -> WHILE LPAREN logical_expression RPAREN block
Rule 42    simple_statement -> expression
Rule 43    expression -> expression PLUS term
Rule 44    expression -> expression MINUS term
Rule 45    expression -> term
Rule 46    term -> term TIMES factor
Rule 47    term -> term DIVIDE factor
Rule 48    term -> factor
Rule 49    factor -> NUMBER
Rule 50    factor -> ID
Rule 51    factor -> LPAREN expression RPAREN
Rule 52    uminus_expression -> MINUS LPAREN expression RPAREN
Rule 53    empty -> <empty>
Rule 54    function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN error

The following change bellow is the one which causes the shif/reduce conflicts

Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE


texts: Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

texts:
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the coins face the same side or not. You continue flipping until all coins are facing the same side.
I tried breaking it down to smaller base cases:
(1) when there is 1 coin: no need to flip
(2) when there are 2 coins: the only odd cases you can have are {H,T} or {T,H}, so flipping the first coin will do the trick
(3) when there are 3 coins: there are 6 odd cases you can end up, but 3 of them are similar to one another, hence only 3 cases to consider with {H,T,T}, {T,H,T} and {T,T,H} (same with one T and 2 heads).
The strategy for this could be flipping the 1st coin, if the order is still not made then flip the second coin, if the order is still not made then flip the 1st coin again.

I am having a hard time coming up with a general algorithm for n coins. Any ideas?


texts: foresightful acceleration and decelerations

texts:
I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need to make sure that no large acceleration/decelerations takes place, because this would induce vibrations. If the amplitude of these vibrations exceeds approx. $50nm$ they would generate unwanted structures on the machined surface.
Since most people are not familiar with the CNC context, I like to transfer the problem to a car, which is driving down a street in 2D. As input to the program I have a 2D point cloud $(x,y)$, which represent the ideal path. The goal is to move along this ideal path as quickly as possible. However, not only should the change in position $(x, y)$ be smooth, but also the change of the accelerations $(a_x, a_y)$ -- we have to avoid vibrations.
The main problem I am currently facing is the deceleration. Since I like to move along the path as fast as possible, I accelerate the car till I reach it's maximal velocity. However, my code does not work well, if I reach a sharp edge. In order to stay within the given path the car has to "look ahead" and decelerate way before reaching the edge.  Hence, I need to implement a foresightful driver. Are there simple methods available for this task? How would you implement this?
Inputs: The input is a dense point-cloud $(x,y)$ with a step side of $\Delta x = 1\mu m = \Delta y$. This raster is only used to define the surface.
Outputs: In order to achieve the high accuracy I have to use an external reference, which define a fixed time interval $\Delta t$. The path is defined as point-cloud $(x,y)$ in such a way, that the machine (car) gets one point per time interval:

$$x_1 y_1$$
$$x_2 y_2$$
$$x_3 y_3$$

Hence, the velocity and the accelerations are defined by the point-cloud itself. Each point must be accurate to the $1nm$ level.
===
There are robotic communities, which did these kind of calculations. Here is one example: Link.


texts:
In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4:

The concept that I am referring to is:

  Then $\mathit{\Phi}$ is false if and only if there exists a clause $\phi \in N^+_\mathit{\Phi}$ or $\phi \in N_\mathit{\Phi}$ such that $\forall x_1\exists y_1\cdots y_{k-1}\forall x_k(P_\mathit{\Phi} \land \phi)$ is false.


texts: What is "rank" in a binary search tree and how can it be useful?

texts:
I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.

What I have looked into:
From what I have read, a ranked binary search tree is a tree where each node has a variable "rank" attached to it.

In the question here, someone states that in order to determine the rank of a node in a binary search tree you can do the following:

  Start the rank at zero. As the binary search proceeds down from the
  root, sum up the sizes of all the left subtrees that the search skips
  by. Also include the nodes along the path less than the searched item.
  These are just the parents of right children on the search path.

Questions:
The rank seems like it is just a number that reflects how many nodes it takes (plus one for the root) to get to a particular node in a tree. Is that right? It didn't seem right to me only because that seems like that would just make the rank of a node the same as the depth of a node.

Also, what is the difference between "weight" and "rank"? If a node in a particular binary search tree has a weight attached to it, is that just a random value assigned to it by the user/developer?

Lastly, what is the point of having a rank? My first thought is that it can be used to indicate priorities. However, in that case, why wouldn't the developer just use weights?

Other things:
I also took a look at the site here. It explains how to calculate rank, but I'm still not convinced I understand the concept yet.

Thanks for any help.


texts: How to develop an $O(N)$ algorithm solve the 2-sum problem?

texts:
Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.

Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.

  How to find an algorithm which is of order $O(N)$?


texts: Non-linear optimization of a family of functions

texts:
I'd like some advice about the following problem (resolution methods, problem category, etc.).
The context is about the coregistration of several images all-in-once ($n$ images, $f_{i,j}$ the function that maps coordinates $(x_i, y_i)$ to $(x_j, y_j)$.

Let $f_{i,j}^k(x, y)$ a polynomial function of order $k$ from $\mathbb{R}^2$ to $\mathbb{R}^2$, with $i, j \in [1, n]$.

For example, if $k=0$, such functions can be expressed as $f_{i,j}^0(x, y) = (a_{ij}^0, a_{ij}^1)$.
Or if $k = 1$: $f_{i,j}^1(x, y) = (a_{ij}^0 + b_{ij}^0 x + c_{ij}^0 y, a_{ij}^1 + b_{ij}^1 y + c_{ij}^1 y)$.

Let's assume $k$ is fixed, it will be omitted in the following.

This family of functions should respect as much as possible following the property: $f_{i,j} = f_{i, k}(f_{k, j})$.

I want to use this property to decrease the number of unknowns and obtain robust estimates of coefficients.
Moreover, I have a large set of matches that can be expressed as such: $v = f_{i,j}(u)$.

My problem is the following: how can I compute robustly the functions $f_{1,i}$ ?

If $k = 0$, the problem is quite simple: $f_{i,j} = f_{i, k}(f_{k, j}) = f_{i, k} + f_{k, j}$ so i can write an overdetermined linear system and solve it with a Moore-Penrose inverse or an algorithm such as RANSAC.

If k = 1 or 2, I don't really known how to proceed. I think I could try to design a custom convergence scheme with a predetermined equation resolution order and some iterations to converge.

As an example, if I solve for $f_{1,2}$, then to get $f_{1,3}$ I can use my matches of the form $v = f_{1,3}(u)$ but also the matches such as $v = f_{2,3}(u) \Rightarrow f_{1, 2}(v) = f_{1,3}(u)$


texts: Removing epsilon transition from the grammar. What's the difference between accepting languages?

texts:
I want to remove the epsilon transition from following grammar:
\begin{eqnarray}
S & \rightarrow & A | B \\
A & \rightarrow & \epsilon \\
B & \rightarrow &  aBa \\
B & \rightarrow & b \\
\end{eqnarray}
This is the result of removing $\epsilon$ transition:
\begin{eqnarray}
S & \rightarrow & \epsilon | B \\
B & \rightarrow & aBa \\
B & \rightarrow & b
\end{eqnarray}

My question is what's the difference between languages that accept these two grammars?


texts: What is the complexity of a bracketed search using mediants?

texts:
I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / n$. The compiler has converted the division into an integer multiplication and a shift: $(x * \lfloor 2^\beta / n \rfloor) >> \beta$, where $\beta$ is the number of bits of the computer's machine word. The resulting constant multiplication is a lot faster than a division in most contemporary architectures, but no longer resembles the original code.

To illustrate: the C statement

y = x / 10;

will be compiled by the Microsoft Visual C++ compiler to  following assembly language

mov edx,1999999Ah  ; load 1/10 * 2^32
imul eax           ; edx:eax = dividend / 10 * 2 ^32
mov eax,edx        ; eax = dividend / 10

The net result is that the register eax will now have the expected value of y from the source code.

A naive decompiler will decompile the above to

eax = ((long)eax * 0x1999999A) >> 32;

but Reko aims to make the resulting output more legible than that by recovering the constant that was used in the original division.

The algorithm hinted at above is based on the description on this article in Wikipedia. First, the algorithm treats the constant multiplier as the scaled reciprocal $2^\beta / n$. It converts that to a floating point number $2^\beta r_f$ and then scales it down by $2^\beta$ to $r_f$, where $0.0 < r_f <1.0$. The final, expensive step is to bracket the floating point value $r_f$ between two rational numbers $a/b$, $c/d$ (starting with 0/1 and 1/1) and repeatedly compute the mediant $(a + c)/(b + d)$ until some convergence criterion is reached. The result should be the "best" rational approximation $r$ to the reciprocal $r_f$.

Now, if the bracketing was being done with a typical binary search starting between the rationals $0/2^\beta$ and $2^\beta/2^\beta$, and computing the midpoint $(a/b + c/d)/2$, I expect the algorithm to converge in $O(\beta)$ steps. But what is the complexity of the algorithm if the mediant is used instead?


texts: LZ-type compression with a limited recursion depth

texts:
I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get references or any other advice to know what to search for in the academic literature on this topic.

Consider a standard LZ77-type compression algorithm. The compressor replaces substring at the current position with the pointer back to the already decompressed text or a literal copy of a single character. Early compressors tended to use greedy algorithms for choosing specific substrings, but better (in fact, optimal for a fixed LZ77 code) results can be obtained by generating a set of several (all) encoding options at each position and then treating the problem as a problem of finding the shortest path on a weighted graph. Each position of the text becomes a vertex, each edge contains the length of the code needed to encode the corresponding substring. The resulting problem is routinely solved by using the Dijkstra algorithm.

In principle, one does not need to store the decompressed text. Instead, one can make references back to the positions in compressed stream and decompress it as needed on the fly. In this case the algorithm becomes recursive - references to previous positions in the compressed stream can require one to follow further references before in the compressed stream. Dealing with overlapping substrings in this case can be a bit tricky, but otherwise, the logic of the algorithm remains mostly the same.

Now, suppose that we have an additional complication. We are using a recursive (buffer-less) version of LZ77 with back references to the compressed stream, but for various reasons we would like to limit the depth of recursion that we are allowed to use during decompression. For example, the maximum recursion depth of 1 would mean that a referred substring can involve further references to previous substrings, but neither of these substrings would be able to have any further back references. The easiest case would be to prohibit recursion completely. Overlapping substrings would not be allowed in this case. All this can be done and in fact I have a working implementation of a greedy algorithm for this problem. Of course, it is much less efficient compared with the classic LZ77. However, this is not a problem.

My real question is: what approach would be necessary to construct an optimal representation of the original text in the case when no recursion is allowed? It is clearly not possible to implement something similar to a Dijkstra algorithm mentioned earlier, because the graph is no longer static: once a particular edge (i.e. a particular substring) gets included into the shortest path, all edges referring to substrings overlapping with the current substring disappear from the graph. The graph is now dynamic and the path-finding algorithm is not "local" in the sense that it can no longer work in a "ripple"-type fashion, because any rush decision early on may disallow much greater savings later on. How would one attack this kind of problem?


texts:
I'm solving some past job interview problems.
I met an embarrassing question about compilers.

The question is :

  Consider the following grammar, with start symbol $E$:

  \begin{align*} E &\rightarrow E \ast E\\  &\quad \mid E ~/~ E\\
 &\quad \mid E + E\\  &\quad \mid E - E\\  &\quad \mid (E)\\  &\quad
 \mid a \mid b \mid c \mid \ldots \mid x \mid y \mid z \end{align*}

  The following strings are legal derivations from this grammar:

  $a \ast b + c$
  $( a - b ) \ast c$
  $a ~/~ ( b – c)$

  Which of the above are rightmost sentential forms?

When I was an undergraduate student, I learned that rightmost(leftmost) sentential form is result of rightmost(leftmost) derivation.
so, I think if $1,2,3$ are legal derivations form above grammar then absolutely all of $1,2,3$ are rightmost sentential form.
If I'm correct, above question is very worthless.

Is there any counter example that is not rightmost sentential form of the grammar $G$ although it is a legal derivation from $G$?

OR

Is there another definition about rightmost sentential form corresponding to above question? I have googled "rightmost sentential form" but there are few results and most of them is the definition that I already know.


texts: Most cost effective way to traverse a set path

texts: I have a set path of $N$ destinations to be visited in order, knowing the distance $D_i$ between each one of them. I can traverse one node $i$ with the cost of $D_i \times r$ or traverse any $5$ nodes in order with a set cost of $B$. How can I find the most cost effective way to visit all the destinations using dynamic programming?


texts: Converting a 2-SAT formula into an implication graph

texts:
Both wikipedia and my lecturer explained how the 2 satisfiability problem work. However, I am finding it really hard understanding how this formula:

xvy≡ ¬x-->y ≡ ¬y -->x

Then breaks down the following conjectures :

(¬x v y) & (¬y v z) & (¬z v w) & (¬w v ¬x) &
(x v ¬y) & (y v ¬z) & (z v ¬w) & (w v x)

is converted to an implcation graph.

Heres my attempt:

 (¬x v y) = (¬y-->x)

          = (¬x-->y)

but this cannot be right, as they have diffrent truth tables:

(¬y-->x)

1 0 0 0

1 0   1  1

0 1   1   0

0 1   1   1

(¬ x-->y)

1 0 0 0

0 1 1 1

1 0 0 0

0 1 1 1

I understand once you have the conjectures converted to implication, how to construct the implication graph and find out if its not satisfiable (bad loops).

Could someone please explain clearly how to break down the conjectures to implications?


texts:
It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it.

So you can state that there is no such reduction from 3-SAT to 2-SAT unless $P=NP$.

I am looking for strong proof for this state, regardless NP belong to P or not.


texts: What does the phrase "Simple For Loops" mean in computability theory?

texts:
I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?

The Phrase:
An upper bound of the number of iterations of every loop can be determined before entering the loop

The Wikipedia page


texts: Can a quantum computer (theoretically) do things a classical computer (literally) can't?

texts:
I've been searching the net for an answer to this question, but it's guetting quite confusing.
I want to know if there are some undecidable problems for a classical computer that a quantum computer could do.
The examples I've seen are things like Shor's algorithm, but that's "just" because the quantum computer is more powerfull than the classical one, and can do stuff like Integer factorization faster. Or at least that's how I understand it so far.
Basically my question is this : is there anything a quantum computer can do that a regular one can't if said regular computer had infinite power (or processing speed or whatever)?
Examples, explanations, sources would be greatly appreciated, but a simple yes/no would please me also.


texts: Counterexample for LTL - CTL equivalence

texts: I have to find an example of a model where the LTL-formula $F G p \wedge F q$ is valid and the CTL-formula $EF AG p \wedge AF q$ is not valid. I found this example, but I'm not completely sure whether it's correct:


texts:
I was reading about the finiteness property of an algorithm where it is mentioned that

  the algorithm must always terminate after a finite number of steps.

Does this mean that any pseudo-code cannot contain infinite loops or it should be equivalent to Halting Turing Machine.  I don't know whether the statement about finiteness property of an algorithm is correct or not. I have not found any reliable source for it and I have not read it in CLRS.

My question is whether the statement and whether my interpretation about it is correct:

  An algorithm must always terminate after a finite number of steps

References:

Intro Problem Solving in Computer Science, CS@VT (Page 3)
Wikipedia article on Algorithm_characterizations
Data Structures and algorithms, CmpE, Boun


texts: On asymptotic complexity class notation?

texts:
Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are equivalent to $\mathsf P$ ($n$ is number of input bits)?

(This is my view. Denote $C(n^{n^\epsilon})$ to be class of problems solvable in $O(n^{n^\epsilon})$ at every $\epsilon>0$ and let $D(n^{f(n)})$ be class of problems solvable in $O(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. Does $\cap_{f(n)\in\omega(1)}D(n^{f(n)})=\cap_{\epsilon>0}C(n^{n^\epsilon})$ hold?  $\forall n\in\Bbb N\wedge\forall\delta>0 \exists\epsilon>0:n^\epsilon<1+\delta$ and so $C(n^{n^\epsilon})$ is smaller than $D(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. However for every $\epsilon>0$ there is an $f(n)\in\omega(1)$ such that $f(n)<n^\epsilon$ at large enough $n\in\Bbb N$ and so $D(n^{f(n)})$ at any $f(n)$ in $\omega(1)$ is smaller than $C(n^{n^\epsilon})$. We then conclude both $O(n^{n^\epsilon})$ and $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ are morally equal. Since $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ is same as $\mathsf P$ we have the notation.).


texts: Till which layer does the loopback packet goes?

texts: I want to know exactly till which layer in the OSI model the 127.0.0.1 (loopback) packet goes till it is returned to the upper layer. I read some where it goes till data link layer. but as i was told data link layer cannot see the ip address then how data link layer decide that the packet has to be send "up" instead of "down".


texts:
Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?

Maybe pumping lemma will do? I was advised to try with a word $a^Nb^Na^Nb^N$ but if I pump only second block of $a$ then this word still is in $L$, because it has non empty prefix $a^Nb^N$ that is also a suffix.


texts: Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings

texts:
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book.

You’re consulting for a group of people (who would prefer not to be
mentioned here by name) whose jobs consist of monitoring and analyzing
electronic signals coming from ships in coastal Atlantic waters. They want
a fast algorithm for a basic primitive that arises frequently: “untangling” a superposition of two known signals. Specifically, they’re picturing a situation in which each of two ships is emitting a short sequence of $0s$ and $1s$ over and over, and they want to make sure that the signal they’re hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows.

Given a string $x$ consisting of $0s$ and $1s$, we write $x^k$ to denote $k$ copies of $x$ concatenated together. We say that a string $x$ is a repetition of $x$ if it is a prefix of $x^k$ for some number $k$. So $x = 10110110110$ is a repetition of $x = 101$. We say that a string $s$ is an interleaving of $x$ and $y$ if its symbols can be partitioned into two (not necessarily contiguous) subsequences $s'$ and $s''$, so that $s'$ is a repetition of $x$, and $s''$ is a repetition of $y$. (So each digit in $s$ must belong to exactly one of $s'$ or $s''$.) For example, if $x = 101$ and $y = 00$, then $s = 100010101$ is an interleaving of $x$ and $y$, since characters at position $1,2,5,7,8,9$ form $101101$—a repetition of $x$—and the remaining characters form $000$—a repetition of $y$.

In terms of our application, $x$ and $y$ are the repeating sequences from the two ships, and $s$ is the signal we’re listening to: We want to make sure $s$ “unravels” into simple repetitions of $x$ and $y$. Give an efficient algorithm that takes strings $s, x,$ and $y$ and decides if $s$ is an interleaving of $x$ and $y$.


texts: While studying ALU I came across this example, now what's difference between operations of OR Gate and SUM(Adder), in binary language


texts: Why does Skiena reserve space for n+1 adjacency lists?

texts:
I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows :

#define MAXV        100     /* maximum number of vertices */
#define MAXDEGREE   50      /* maximum outdegree of a vertex */

typedef struct {
    int v;              /* neighboring vertex */
    int weight;         /* edge weight */
} edge;

typedef struct {
    edge edges[MAXV+1][MAXDEGREE];  /* adjacency info */
    int degree[MAXV+1];     /* outdegree of each vertex */
    int nvertices;          /* number of vertices in the graph */
    int nedges;         /* number of edges in the graph */
} graph;

I am confused about why the size of adjacency list or the degree is MAXV+1. Is it to handle edges that begin and end in the same vertex E(v,v) ?


texts: Equality of lambda terms which do not have normal form

texts:
In the context of lambda calculus, how should one prove $\beta$-equality of terms that do not have normal form?
In particular, how to prove that these are different combinators:
$$
Y = λf.(λx.f(xx))(λx.f(xx)) \\
Θ = (λxf.f(xxf))(λxf.f(xxf))
$$
These work the same if we reduce them, but Wikipedia states that they are different, and that there are in fact infinitely many combinators that work the same as these.


texts: Finding partition with maximum number of edges between sets

texts:
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?

For example, for the following set of edges of a graph with vertex set $\{1, 2, 3, 4, 5, 6\}$:
$\{(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)\}$, one possible "maximum" partition is $\{\{1, 3, 4, 6\}, \{2, 5\}\}$ with $4$ edges between the sets $\{1, 3, 4, 6\}$ and $\{2, 5\}$.


texts: Any Natural Problems shown Easy by Reduction to Horn SAT?

texts:
To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing at most 2 literals).

On the other hand, I never seem to have success with reducing problems to Horn SAT (that is the problem for CNFs in which every clause contains at most 1 positive literal). This might not be too surprising given that the algorithm solving Horn SAT is (in some sense) more basic than the one for 2SAT, and because satisfiable Horn formulas have minimal models while most other problems don't.

Nevertheless, are there some examples of problems that are (most naturally) shown to be easy by reduction to Horn SAT?


texts: IS $LOGSPACE\subsetneq QMA$ an open problem?

texts:
Having read some chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions:

$L \subseteq NL \subseteq P \subseteq BPP \subseteq BQP \subseteq QMA$

but no inclusion is known to be strict, and it is not known whether at least one of these inclusions is strict. The statements $L=P, P=BQP, BQP=QMA$ are all unsolved, so I am free to conjecture that they are all true, or all false. I know that it is absolutely obvious that $L\subsetneq QMA$, because to go from one to the other one must (1) remove the logarithmic space bound, (2) introduce randomness to the algorithm, (3) add quantum and (4) add nondeterminism.
This question is interesting because each of these augmentations is believed but not proved to add computational power (with the possible exception of (2)), they correspond to their respective flagship inclusions above, and this question captures all of them simultaneously, showcasing an enormously long distance unsolved relationship. It is also interesting because to my knowledge it is the longest-distance unresolved inclusion between two natural complexity classes (classes that arise naturally in studying theory and which capture fundamental notions of resource-bounded computation, but this point is subjective).

The only strict inclusions I can find are $L\subsetneq Space(n) \not= NP$ and $L \subsetneq PSPACE \supseteq P$. The first is not satisfying because $Space(n) \subsetneq NP$ is open.

This also begs the question, alright if these augmentations individually are hard to reason about, but surely you cannot add them all at once without changing your complexity class? And is it easier to prove such weaker strict inclusions?

(and, tongue in cheek, if the answer to my question is yes, what have complexity theorists been up to the past few decades?)


texts:
Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

An asynchronous multiplier is much bigger than an adder. It's about 18*n^2 NOR gates where n is the number of bits. An adder is about 15*n NOR gates. But for a 32-bits multiplication, a multiplier with successive additions will need 32 clock cycles, while an asynchronous mutliplier only 1. I think it's a big performance gain.

The same is for BCD to binary converter.


texts: Understanding the definition of Positivity Constraints in Coq

texts:
In Interactive Theorem Proving and Program Development the authors explain constraints on constructors of inductive types in Coq.

For inductive type $T$, a constructor must have the form $t_1 \rightarrow t_2 \rightarrow ... \rightarrow t_l \rightarrow T a_1 ... a_k$ where $k$ is the number of arguments of the inductive type $T$.

There are some restrictions placed on the $t_i$s, which I cannot understand.

  If $t_i$ is the type of a constant, then $t_i$ can have the form "$g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k}),$" provided the expressions $b_{i,j}$ also satisfy the typing rules, and $T$ does not occur in these expressions or in $g$.

and

  If $t_i$ is the type of a function, this type can have the form $t_1'\rightarrow ... \rightarrow t'_m \rightarrow g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$ but the type $T$ cannot occur in the expressions $t'_1, ... t'_m$ or in the expressions $b_{i,j}$

I am confused on what it means for a type $t_i$ "to have the form of $g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$".

For instance, does nat (the type of natural numbers) have the form of $g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$"?

If so, how does nat obtain such a elaborate form? What is $g$ and what are the terms in the $(l,k)$ matrix $b_{i,j}$?

If not, am I prohibited from using nat in type constructors of inductive types? (That would seem absurd...)

Below I have uploaded a screenshot of the page in question.

Update: I was able to construct a counterexample to the textbook:

Definition g := fun x y z : Type => nat.

Inductive T : Set :=
  t : (g T T T) -> T.

Here $l = 1, k = 0$, and $t_1$ can only have the form $g(T)$ but I was able to use $T$ 3 times inside an actual Coq environment.

Edit 2:
I think what you guys are saying about the reduced form makes sense so I tried to make another "counterexample"

Inductive g (x y z: Type) : Set.

Inductive T : Set :=
  t : (g T T T) -> T.


texts: Proof that uniform circuit families can efficiently simulate a Turing Machine

texts: Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity classes (e.g., $\mathbf{P}$ or $\mathbf{NC}$). I would like to see how uniform circuit families is a strong enough model for universal, efficient computation.


texts: How hard is it to play 1-dimensional minesweeper optimally?

texts:
(This is based on my earlier MSE question that has been stagnant for just over a week, since the

best answer only addresses the case of two mines and does not even completely resolve that.)

What is the computational complexity of playing 1-dimensional Minesweeper in a way that

maximizes the probability of winning, where the board length is given in unary, the number

of mines is known, and their position is chosen uniformly from among all possibilities?

I believe the reasoning used in the proof of $\:$IP $\subseteq$ PSPACE

shows that the complexity is at most PSPACE.


texts: Classification of the complement of a language

texts:
$L = \{   \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$.

What is complement of this language?

my attempt:

the complement is: $M$ accepts no two strings of same length and this can be done by dovetailing different inputs on M but we can never say IT CANNOT ACCEPT TWO STRING OF SAME LENGTH and hence its NOT RECURSIVELY ENUMERABLE?


texts: Closure of regularity under the action of replacing identical pairs of letters

texts:
Given any regular language L,
we define
$$shrink(L) = \{ \sigma_{1}\sigma_{2}\sigma_{3}...\sigma_{n} : \sigma_{1}\sigma_{1}\sigma_{2}\sigma_{2}\sigma_{3}\sigma_{3}...\sigma_{n}\sigma_{n} \in L \} $$
The question is whether these languages are regular or not.
The intuition says they are, and I was thinking about proving it with Homomorphism, i.e defining homomorphism from shrink(L) by duplicating each word and then proving that $h(shrink(L))$ is regular therefore shrink(L) is regular.
But I'm not exactly sure how to do it properly..
edit: another idea I had is by using DFA - if L is regular it has a DFA called M, so I can build M' by changing Delta such that $\delta (q,\sigma w) = \delta(\delta(q,\sigma w),\sigma w)$. Will it work?
Thanks for any help


texts: How can I tell who is a truth teller and who is a liar?

texts:
This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance?

  At Hogwarts a new shipment of $n$ goblins has arrived.  To be of any use, a goblin must be completely truthful (never lies).  Unfortunately, not all of the $n$ goblins in the shipment are truth tellers.  Only some are truth-tellers, and some are deceivers.  It is your task to design an algorithm to separate the truth-teller goblins from the deceiver goblins.  To do this, you have one tool available:  You may combine any two goblins and have them state whether the other goblin is a truth-teller or a deceiver.  A truth-teller will always say correctly what the other goblin is, but a deceiver may lie (but also may sometimes tell the truth to REALLY confuse you).  For any two goblins that you test, the following can be concluded from the goblin responses:

  $$
\begin{array}{ccc}
\text{Goblin A says} &
\text{Goblin B says} &
\text{Conclusion} \\\hline
\text{B is a truth-teller} &
\text{A is a truth-teller} &
\text{both are truth-tellers or both are deceivers} \\
\text{B is a truth-teller} &
\text{A is a deceiver} &
\text{at least one is a deceiver} \\
\text{B is a deceiver} &
\text{A is a truth-teller} &
\text{at least one is a deceiver} \\
\text{B is a deceiver} &
\text{A is a deceiver} &
\text{at least one is a deceiver}
\end{array}
$$

  Show that if more than $n/2$ goblins are deceivers, it is impossible to determine which goblins are the truth-tellers using only the pairwise testing strategy.
  Consider the problem of identifying $1$ truth-teller goblin.  Show that if we assume that more than $n/2$ of the goblins are truth-tellers, then the problem of finding a single truth-teller from $n$ goblins can be reduced to a problem of about half the size using $n/2$ goblin comparisons.
  Use a recurrence equation to show that if more than half of the goblins are truth-tellers, then the truth-tellers can all be identified within $O(n)$ goblin comparisons.


texts: Since physical memory is the RAM where is logical memory stored on the computer?

texts: Since logical memory maps to the RAM (physical memory) it has be stored somewhere right and it will obviously take large bunch of memory of itself. Where is it stored?


texts: Get the nth lexicographic string of "all" possible combinations of an alphabet

texts:
Is there a way to find the nth string of characters from an alphabet, without having to store "all" of the combinations?

Example:

Alphabet $A = \{a,b,c\}, n=12$.

All possible combinations in lexicographic order are $C = \{a, ab, abc, ac, acb, b, ba, bac, bc, bca, c, ca, cab, cb, cba\}$.

You can see that there's no repetition of characters in any string and the empty string is not a member of $A$.

So, the nth string is: $ca$.

Clearly, to find this I'm iterating over the set $C$.

The problem is that I have to generate all these strings, wich takes a really long time, and then search for the nth one. If the alphabet is large $(1 \leq A \leq 26 )$ the set $C$ grows too fast (not sure how much) and is impossible to store.

My questions is if exists a way to find these nth one, without generating all the strings.

Also, I'm not sure if this question goes in this StackExchange site.


texts: A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone have to put before it can be expected that the "computer" is Turing Complete?


texts: Determine the move in which a LOGO turtle crosses a point that it has already visited

texts:
I was given the following problem in an test (at codility.com)

  A turtle starts at (0, 0) on a cartesian graph. We have a non-empty
  zero-indexed "moves" list that contains positive integer numbers. Each number
  represents the distance moved. The first number is the distance north,
  the second is the distance east, the third is the distance south, the
  fourth is the distance west, and so forth. Therefore
  the directions cycle every four moves.

  Find an algorithm that gives the move number that makes the turtle
  cross a point that it has already visited before.

  The move number is the index of the "moves" list.

  This algorithm should have O(n) time complexity and O(1) space complexity.

  Example:

  If given this move list: [1, 3, 2, 5, 4, 4, 6, 3, 2]

  The move number answer is then 6. (It's the 7th move).

  Draw it on a graph, the turtle will go:

  (0,0) -> (0,1) -> (3,1) -> (3,-1) -> (-2,-1) -> (-2,3) -> (2,3) ->
  (2,-3)

  At this 6 move number (7th move) it will meet (2,1) which is a point
  that the turtle has already crossed.

I have been struggling with for quite a time, because I intuitively think there's no way to meet both space and time complexity requirements, unless there's some hidden structural property in the problem I'm not noticing. For example, if the path does not cross itself it forms an spiral-like curve, and therefore each north move must be greater than the previous south move, and viceversa. The same applies to the east and west moves. Therefore, not meeting this property implies the curve will eventually cross itself, but gives no indication on which move does it.

My main problem is that I've not been able to identify the type or algorithmic problem this problem relates (e.g. sorting)


texts: Algorithm to seed a cash register drawer

texts:
Not looking for code, just a general solution or pointers in the right direction. I think that my problem can be adapted into an instance of the knapsack problem. I made an attempt at it, but couldn't figure out something that worked. (I can elaborate on this more if necessary.)

Concrete scenario

The actual scenario is to seed a cash register drawer with bills for the day. (The seed is the initial cash in the drawer used to make change.) The drawers are seeded every day to a specific amount. \$200.00 or \$100.00 in my case depending on the drawer. The business rule that I must follow is to maximize the number of bills available to the cashiers to make change with.

Problem

I need to transform an array of integers (values can be repeated, but will always be greater than or equal to 1) into another array of integers so that the sum of the result array is exactly equal to a given target value and so that the length of the result array is maximized.

Input: array of integers, target value
Output: array of integers (with maximal length and a sum exactly equal to target value.)


texts: 'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges

texts:
Take the language $L = \{a b^n c^n \; : \; n \geq 0\}$.

It's obvious that $L$ is non-regular because $\{b^n c^n \; : \; n \geq 0\}$ is non-regular, but I don't know a satisfying way to show that to the hypothetical Devil's advocate reading my proof without dragging out a full argument using the pumping lemma.

Is there some property of languages that can allow us to easily deduce that $L$ is non-regular if its accepted as known that $\{b^n c^n \; : \; n \geq 0\}$ is non-regular?


texts: Optimal combination, given pairwise costs

texts:
I want to pick k objects from a pool of n. Not any k objects, the optimal k objects: that which minimizes the cost of the set, defined as the sum of pairwise costs for all pairs within the set.

What NP-complete/hard problem is this an instance of?

What is a good (i.e. fast but finds a low cost) way to solve this problem.


texts:
Is Turing machine is robust ?
if it solved with one tape, can it solved with multi-tape?
I know that TM is robust but i can't understand why


texts: Subset sum, pseudo-polynomial time dynamic programming solution?

texts:
I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm

I have looked at the problem and found  some solutions  but so far they seem to be NP,
I believe I can make a sufficiently fast algorithm in NP time.

My problem is I am not good in theory so it doesn't help me much to talk about the Cook-Levin Theorem or Non-Deterministic Turing Machines.

What I would like is an explanation of the pseudo-polynomial time dynamic programming subset sum that on Wikipedia.

I have read it and I believe I understand the general concept of why it is NP instead of P (related to the size of the input rather than the operations with it),
but I do not understand the algorithm.

I would appreciate if someone would put provide an example with some numbers and how it works. It would help me a lot because it would:

Give me ideas to improve my future algorithm
Help me understand intuitively when an algorithm is pseudo-polyonmial instead of NP.


texts: Approximately counting the number of marked elements in a list of n numbers

texts: Assume that we have n sealed boxes. There are k boxes with a ball inside. The goal is to approximate k  by an additive error epsilon, using the minimum number of box probing. I know that this is possible using O(n/k. 1/epsilon^2) box probing but I don't know the algorithm and its analysis.


texts:
In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this?

while a % 2 == 0:
    a = a / 2

I am guessing the worst case is $O(log(k)k^2)$ as a decreases by 2 each time but each division takes $k^2$


texts: Can lambda-calculus be used for knowledge representation?

texts:
Natural language semantics (in computational linguistics) uses lambda terms for expressing the semantics of natural language sentences. There is vast literature about combinatorial categorial grammars and lambda semantics of natural language, e.g. tutorial about framework http://yoavartzi.com/tutorial/

The question is - if lambda calculus can be used to represent the meaning of the natural language text, then can we use lambda calculus for the universal representation of knowledge? Why there are so few results in this direction? Or maybe there are efforts to bridge the meaning as expressed in lambda calculus with some of the common knowledge representation approaches?

Maybe (extended) Curry-Howard isomorphism between lambda calculus and logical/deductive systems can be used to translate the semantics in terms of lambda calculus into knowledge in terms of logical expressions, e.g., maybe translation to description logics and action logics is possible?


texts: What is the difference between centralised, decentralised, distributed, fully-distributed?

texts:
What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system?
Which type or topology is the system attached in the picture below? For instance, A is a master node (coordinator) of A1, A2, A3, which makes this part a centralised system. A, B, C and D are all connected between each other, which makes this system a decentralised one. But then, what are fully-distributed, partially-centralised, partially-decentralised systems?


texts: Time complexity of insertion in linked list

texts:
Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:

  What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

In my opinion, the answer should be $O(n^2)$ because in every insertion, we will have to insert the element in the right place and it is possible that every element has to be inserted at the last place, giving me a time complexity of $1 + 2 + ... (n-1) + n = O(n^2)$

However, the solution that I have says that we can first sort the elements in $O(n \log n)$ and then, we can insert them one by one in $O(n)$, giving us an overall complexity of $O(n \log n)$.

From the given wording of the question, which solution is more apt? In my opinion, since the question mentions "linked list needs to be maintained in sorted order", I am inclined to say that we cannot sort the elements beforehand and then insert them in the sorted order.


texts: Finding a solution to a satisfiable formula

texts:
I know that it is as hard to find a solution to a SAT formula, as it is to decide it has a solution at all. See the answer to:
Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Are there also families of formulas for which it is guaranteed that there is a solution, but it is hard to find one?


texts: Is an axiom for time required for any non-trivial algorithm?

texts:
By non-trivial algorithm, I mean anything besides the trivial "do nothing" algorithm that simply terminates.

This is pretty trivial, but don't algorithms require a notion of monotonic time?

From what I understand, all computation requires a sort of reduction step, from the reduction of the transition function in Turing machines to the types of reduction within lambda calculus. But having reduction requires a notion of change itself means that a change of state must be defined with respect to a change in some constant unit of change that is uniform.

Whether that notion of change is the steady rate of change of the instruction count register of a computer or the steps in the reduction of a formula to normal form, does every single type of computation require a notion of change, and, therefore, "time" as a sort of immutable, constant, and uni-directional measure of change?


texts: What is the time complexity of memory allocation assumed to be?

texts:
It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more room in the buffer, so the dynamic array allocates a new buffer and copies over $n$ items.

My question is, what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?


texts: Finding bounded lexicographically largest string of digits but not larger than other with counted substitutions

texts:
The problem comes from the book текстовые и жадные алгоритмы (String and greedy algorithms) by a fairly unknown Russian computer scientist Николай Сухоруков.

We are given two numbers $A$ and $B$ of the same length but possibly with leading zeroes, which are bounded by $10^{(10^5)}$, but this is fine as this is a strings problem, and $k$ bounded by the number of digits of the larger.

When two numbers $p$, $q$ differ on exactly $l$ positions (including leading zeroes), we call them $l$-distant.

The objective of the problem is to find the largest $N$ which is $k$-distant of $A$ but less than $B$.

For example, given $A=0555, B=0551, k=3$ the solution is $N=0499$. Although there exist other, greater $N$s like $N'=0550$ or $N'=0549$, they cannot be reached by changing exactly three positions.

My first idea was to use a really trivial greedy algorithm, which fixed digits left-to-right. However, it did not pass a simple test of $$A=23, B = 12, k = 1$$
where the answer should be $N=03$, but the program yielded $N_{wrong}=13$.

My second thought was to use the parametric search algorithm, searching over $k$. However, I did not manage to come up with the sub-algorithm to be searched.

Binary search over $N$ also seems infeasible to me, due to sheer size of the number.

Do you have any ideas? I really appreciate any help!


texts: How to analyze the performance of a genetic algorithm experimentally?

texts:
I have a genetic algorithm for an optimization problem.
I plotted the running time of the algorithm on several runs on the same input and the same parameters (population size, generation size, crossover, mutation).

The execution time changes between executions.
Is this normal?

I also noticed that against my expectation the running time sometimes decreases in place of increasing when I run it on a larger input.
Is this expected?

How can I analyze the performance of my genetic algorithm experimentally?


texts: Low-level division operator implementation

texts:
A few weeks ago, I asked this question on the implementation of the shift operator for an architecture that implements boxing. Reviewing my implementation I found out that the division operator wasn't correctly done. My language should implement the construct L3IntDiv that implements floored division in contrast with truncated division used for instance in Java. For example $\frac{-14}{5}$ should give -3 and not -2. For that purpose it relies on an instruction Div that also implements floor division. So the main challenge is to deal with the boxing representation in an efficient way.

The translation I was doing for my construct was as follows:

L3IntDiv(x,y) {
 c1 = -1
 t1 = Add(x,c1)
 t2 = ArithShift(x,c1)
 r = Div(t1,t2)
 n = Sub(r,c1)
}

Remember that the convention is that the shift to the right takes a negative argument and the shift to the left a positive argument. Also the shift left fills the bit-array with zeros and the right shift just removes digits introducing zeros by the left hand side.

But the actual code that works looks as follows (note the replacement by OR at the last line):

L3IntDiv(x,y){
 c1 = -1
 c2 = 1
 t1 = Add(x,c1)
 t2 = ArithShift(y,c1)
 r = Div(t1,t2)
 n = Or(r,c2)
}

The formal deduction that I did looked as follows:

$[[x \,/ y]] = 2*{\Big[\frac{\frac{[[x]]-1}{2}}{ \frac{[[y]]-1}{2}}}\Big] + 1 =2*{\Big[\frac{\frac{[[x]]}{2}}{\frac{[[y]]}{2}}}\Big] + 1 $

I don't think this notation is fair, instead of dividing by two I should write shift to the right.

$[[x \,/ y]] = 2*{\Big[\frac{\frac{[[x]]-1}{2}}{ \frac{[[y]]-1}{2}}}\Big] + 1 =2*{\Big[\frac{shiftRight([[x]],1)}{shiftRight([[y]],1)}}\Big] + 1 $

In summary, I'm asking for a reasoning that would give me the specified division operation (floor division) from the box representation of the integers (with the notation [[⋅]]) and how does this fit the second implementation.

Remember that the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int i I use instead 2i+1) and that I'm denoting the box representation as [[⋅]].

Edit:

To formaly deal with this operations it might be of use wikipedia.


texts: Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

texts:
If this is my adjacency matrix for the hamiltonian cycle:
$$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$
Then a reduction algorithm to reduce this to a TSP problem is to introduce 1 anywhere an edge is missing and let pre-existing edges have a cost of zero (according to this), applying this yields:
$$\begin{pmatrix}1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\end{pmatrix}$$
Now I see that I have also introduced weighted-loops to my undirected graph, would asking whether this has a zero-cost salesman tour be equivalent to asking whether the unreduced version has a hamiltonian cycle, or should I maybe have something else on the diagonal of the reduced matrix?


texts: Can you complete a basis in polynomial time?

texts:
Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ bits to describe. We would like to find vectors $v_{k+1}, \ldots, v_n$ such that $v_1, \ldots, v_n$ is an orthogonal basis for $\mathbb{R}^n$.

I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. My question is to provide a proof that this can indeed be done in polynomial time.

Here is where I am stuck.  Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v_1, \ldots, v_l$. Take the basis vectors $e_1, \ldots, e_n$, go through them through them one by one, and if some $e_i$ is not in the span of the $v_1, \ldots, v_l$, then set $v_{l+1} = P_{{\rm span}(v_1, \ldots, v_l)^\perp} e_i$ (here $P$ is the projection operator). Repeat.

This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e_i$ onto, say, $v_1$ may have denominators which need $2K$ bits or more to describe - because $P_{v_1}(e_i)$ is $v_1$ times its $i$'th entry, divided by $||v_1||$. Just $v_1$ times its $i$'th entry may already need $2K$ bits to describe.

By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?


texts: Example of a superword w such that v^2 isn't its subword

texts:
What is an example of an infinite word(superword) w such that if a nonempty word v belongs to L = {1,2,3}*, v^2 isn't a subword of w?

For example if w = 123123123...123 and v = 123, v^2 = 123123 hence it's a subword of w, I can't seem to find a superword that fits the requirement.


texts:
If $T_n = \{ \langle M \rangle \mid M \mbox{ is a Turing machine and } |L(M)| = n\}$ where $n$ is $0,1,2....$

I need to show that if $n \geq 1$, $T_{n+1}$ reduces to $T_n$. I know I need to create a machine where that machine accepts $|L(M)|-1$ strings, which I could then use to verify with $T_n$. I'm just confused as how to properly do it. Can I use some kind of search algorithm to find a string in it and exclude it?


texts: Any algorithm for finding Euclidean shortest path with specific constraints in 2D?

texts:
I have the following problem:

  In a 2D space with polygonal obstacles, find the shortest path between two given point.

Without additional constraints, we can reduce it to a graph problem by constructing a visibility graph and then solve it by searching.

If the following constraints are added, how can we solve it?

Let's define a path as a set of line segments.

Each segment must be longer than a given value.
Each segment must be horizontal or vertical. (simplified version)
Each segment must be parallel or perpendicular to other segments. (general version)

Clarification

The problem is in continuous 2D space.
To simply the problem, the direction of the first and the last segments is given.

Application

This can be considered as a routing problem. I am going to use the algorithm for MEP services routing (e.g. duct, pipe, cable tray).

We need a connector to connect two services when the direction is changed.

As the connector consumes some space, we have constraint (1).
As we only have limited choices of the connector (90°, 60°, 45°, 30°), we have constraint (2). To simplified the problem, I only use connector for right angle.


texts:
I was studying Theory of Computation and I'm kind of lost in solving this problem.

Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for some $a\in\Sigma$.

Is $R$ an equivalence relation? Prove.

So to prove that $R$ is an equivalence relation, I have to show that

$R$ is reflexive
$R$ is symmetric
$R$ is transitive

But since it's related to DFA, I'm not sure how to approach this problem. Some help is much appreciated.


texts: What is the formal justification for the correctness of the second formulation of rod cutting DP solution

texts:
CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.

Define $r_j$ to be the optimal way to cut a rod of integer length $j$.
Since we do not know where is the optimal place to cut the rod we consider every location $ i  \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally.
If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:

$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$

However there seems to be an alternative (or maybe simpler strategy to solve such a problem):

$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$

CLRS has the following discussion about it:

  In a related, but slightly simpler, way to arrange a recursive
  structure for the rod- cutting problem, we view a decomposition as
  consisting of a first piece of length $i$ cut off the left-hand end,
  and then a right-hand remainder of length $n -i$. Only the remainder,
  and not the first piece, may be further divided. We may view every
  decomposition of a length-n rod in this way: as a first piece followed
  by some decomposition of the remainder. When doing so, we can couch
  the solution with no cuts at all as saying that the first piece has
  size $i = n$ and revenue $p_j$ and that the remainder has size $0$
  with corresponding revenue $r_0 = 0$.
  In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.

Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.

Usually I've tried to justify it to myself by having the following thought experiment: well, if I want to have an optimal revenue I need to make sure that I some how explore all good solutions exhaustively and not miss any. If I want the solution to the whole thing $r_j$ then it could be that the full rod is required, then the cut is at position $i=n$. That is if the optimal solution contains no cuts. But if we have a cut we will have some part of the rod that must remain un cut.
If that is the case, then just consider all possible full parts of the rod from the beginning of the rod to the end that remain uncut. Basically, it seems that the solution is as follow, every solution to $r_j$ must contain a piece of rod from the beginning that is uncut to some cutting location $i$.
Since this is part of the optimal solution, we just consider all beginnings that are "full" rods up to $i$ and then make sure to solve the remaining optimally.
This justification feels close to being the argument of correctness but for some reason it just seems to be missing something (wish I knew what it was).

Does someone know how to write a better clear proof of correctness of this? If its really formal or rigorous that is ok with me, I just sort of want some proof for the second recursion where there is no doubt that its correct.

Thanks for the help!

Recall the rod cutting problem.
You manufacture steel rods of some fixed length and sell them in segments of integer length and because of the laws of supply and demand, the price per length is not constant.
Given a set of prices (i.e. an array $p_i$ indicating the price for an integer cut of length $i$) for each possible length segment, how should you cut a given rod of length $n$ into integer length segments to maximize revenue?
You may assume that no cost or loss incurred with each cut.


texts: What is the purpose of standardization in machine learning?

texts:
I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying

  When independent variables in training data are measured in different
  units, it is important to standardize variables before calculating
  distance. For example, if one variable is based on height in cms, and
  the other is based on weight in kgs then height will influence more on
  the distance calculation.

Since K nearest neighbor is just a comparison of distances apart, why does it matter if one of the variables has values of a larger range since it is what it is.

Also,what exactly does standardization do to the values? One of the formulas does it by Xs = (X-mean)/(max-min) Where does such a formula come from and what is it really doing? Hopefully someone can offer me a simplified explanation or give me a link to a site or book that explains this in simple terms for beginners.


texts: A set that is not recursively enumerable and not (K'≤ A)

texts:
Is there a set A such that it's not recursively enumerable and not(K'≤ A) ?
where K' is complement of K= {n| φ  n  (n) halts}

Thanks!


texts: Algorithm for generation of Canonical represented integers

texts:
Is there a way to get canonical representation of an integer by algorithm?
I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How can I compute the power of each prime number?


texts: Inductive proof on Quicksort with Explicit Stacking

texts:
Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $O(\lg n)$.

This is because the smaller sublist has length $\le 1/2$ the length of the current list. But how can this be proved using induction?


texts: Confusion related to time complexity of dynamic programming algorithm for knapsack problem

texts:
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming

I didn't get how the time complexity of the algorithm came out to be $O(nV^*)$


texts: Time Complexity: Intuition for Recursive Algorithm

texts:
I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book.

The first example problem presented there is Rod Cutting (15.1). Given a rod of length n and a list of prices for rods of any sizes figure out how to cut the rod so that the price of the pieces will be maximized (and one can only cut at even positions).

The first recursive algorithm presented there is the following

CutRod(p, n)
  if n == 0
    return 0
  q = -inf
  for i = 1 to n
    q = max(q, p[i] + CutRod(p, n -1))
  return q

n is the size of the rod and p an array that contains the prices.

I understand the algorithm, the problem I have is that I thought intuitively the time complexity of such an algorithm would be O(b^d) (where b is the branching factor and d the depth of the recursion tree) which would be O(n^n).

In the book the recurrence relation is presented: T(0) = 1 and T(n) = 1 + sum(j=0, n-1, T(j)) Then it is explained that the complexity following from this is O(2^n) which you can easily be seen by expand the recurrence relation.

How can I quickly see that my initial intuition was wrong? And in general when looking at a recursive algo how can I figure out weather the time complexity is O(b^d) or not.


texts: Relationship between height and depth of a binary tree

texts:
The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree.

The following binary tree is full according to the wikipedia definition (every node has 0 or 2 children), n = 11, h = 4 but n is not greater than $2^4 - 1 = 15$.

Am I missing something?

                        .
                       /  \
                      a    .
                          / \
                         b   .
                            / \
                           .   .
                          / \ / \
                         c  d e  f


texts: Perfect matching in a bipartite regular graph in linear time

texts:
Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.

It is easy to show that there is a perfect matching for the graph, by using flow and showing a flow of size $|V|/2$.

Using flow networks, we can also use Dinic's algorithm to find the max-flow which is equal to the perfect matching (thus, deriving a perfect matching) in $O(|E|\cdot\sqrt{|V|})=O(|V|^{3/2})$ (Since $E=O(|V|)$).

Can we find a perfect matching in linear time?

Thanks!


texts:
Which of these properties hold for all FO theories? (but not regarding fragments thereof)
a. Decidable
b. At least expressive as propositional logic
c. NP-complete
a) Decidable: no, some first order theories are not decidable.
b) Propositional logic lacks expressiveness, so possibly yes. However, are hence all FO theories more expressive than propositional logic?
c) NP-complete: An undecidable FO-theory is not NP-complete
Are a) and c) correct? How about b), is there a counter example?


texts: Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

texts:
This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea is to contract the graph, i.e. collapse two or more nodes into one node. So each reduction will reduce the graph by at least half nodes. The question is to come up with implementation such that time complexity of MST-REDUCE is $O(E)$. This uses set operations. MakeSet, Union and Find-Set. I've annotated my analysis in the picture along with algorithm.
I'm thinking to implement the set as linked list here. So my make-set and find-set are $O(1)$. But Union sucks: $O(V)$. Since we are doing union for all the elements, we have total $O(V^2)$ time spent in union. Which gives amortized $O(V)$. Now the problem isn't clear whether it is expecting amortized time complexity or not. So I'm wondering if any better approach is possible. Note the algorithm is running for all nodes and all edges. Hence I think amortized makes sense.

Here is my analysis (line, complexity)

1-3 $V$

4-9 $\frac{V}{2} \cdot union = \frac{V}{2} \cdot \frac{V}{2} = V^2 = V$ (amortized)

10 $V \cdot findset = V$

12-21 $E \cdot findset = E$

Since $E >= V - 1$, we have overall time complexity of $O(E)$.

0   MST-REDUCE(G, orig, c T)
1   for each v in V[G]
2       mark[v] <- FALSE
3       MAKE-SET(v)
4   for each u in V[G]
5       if mark[u] = FALSE
6           choose v in Adj[u] such that c[u,v] is minimized.
7           UNION(u,v)
8           T <- T union { orig(u,v) }
9           mark[u] <- mark[v] <- TRUE
10  V[G'] <- { FIND-SET(v) : v in V[G] }
11  E[G'] <- { }
12  for each (x,y) in E[G]
13      u <- FIND-SET(x)
14      v <- FIND-SET(y)
15      if (u,v) doesn't belong E[G']
16          E[G'] <- E[G'] union {(u,v)}
17          orig'[u,v] <- orig[x,y]
18          c'[u,v] <- c[x,y]
19      else if c[x,y] < c'[u,v]
20          orig'[u,v] <- orig[x,y]
21          c'[u,v] <- c[x,y]
22  construct adjacency list Adj for G'
23  return G', orig', c', T


texts: Is there a fundamental CS problem in ORMs that leads to N+1?

texts:
Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it.

The problem goes like this. If your database has a table of cars and each car has a list of wheels (stored in another table), if you first query for all cars (1) and then for each car you query for its wheels (N) you get orders of magnitude less efficient query because you in fact have N+1 queries, whereas you could just have one.

I'll show you one scenario in which it is difficult for a less experienced developer to spot that they have an N+1 problem while using ORM.

Let's assume we have the following tables definition in Microsoft Sql Server:

CREATE TABLE [dbo].[Article](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [Title] [nvarchar](max) NULL,
CONSTRAINT [PK_dbo.Article] PRIMARY KEY CLUSTERED ([Id] ASC)
)
GO

CREATE TABLE [dbo].[ArticleScore](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [ArticleId] [int] NOT NULL,
  [ActualCity] [nvarchar](10) NULL,
  [Score] [int] NOT NULL,
 CONSTRAINT [PK_dbo.ArticleScore] PRIMARY KEY CLUSTERED ([Id] ASC)
)

GO

ALTER TABLE [dbo].[ArticleScore]  WITH CHECK ADD  CONSTRAINT [FK_dbo.ArticleScore_dbo.Article_ArticleId] FOREIGN KEY([ArticleId])
REFERENCES [dbo].[Article] ([Id])
GO

There is nothing fancy here, the main thing is that we have two tables that have a foreign key relationship.

Now let's assume that we use EntityFramework, and somewhere in the code we have a line like this:

var scores = context.ArticleScores.Where(x => x.Score < 100).ToList();

Now the scores list gets passed around a few methods, and somewhere else it's used like this:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

This last line will cause a separate query to be executed for each Article object. When the number of objects are large, the overhead as we all know serious.

Full example that can be run and examined in SQL Profiler can be found here, which is adapted from here but I hope that the idea is clear.

The problem with this particular case can be solved with eager loading, and Entity Framework offers Include method that would load Article objects along with ArticleScore objects in the first query, thus eliminating the need to query the database at all for the second query.

Now to my question.

I would (apparently incorrectly) imagine, that there should be enough information for ORM to execute the second query in a single sql query, thus reducing N+1 problem to 1+1 problem which, in most cases won't be a problem.

ORM knows about relationship between Article table and ArticleScore table. It knows that conceptually a list of ArticleScore objects represent a slice of ArticleScore table. Thus it should be able to figure out how to get the corresponding slice of the Article table in one query, it does not look like a rocket science.

So could you please tell me, is there some fundamental problem, when writing ORMs, that would prevent elimination of most of the N+1 problems?

I understand that you cannot prevent someone from shooting oneself in the foot by writing specifically incorrect code, but in the examples like the one given above many people can easily miss the problem altogether, which is apparent to me after a few code reviews I conducted. To many people this code looks like it should have worked without exhibiting N+1.


texts: Crossover method for 3D velocity vector genetic algorithm

texts:
I am trying to write a genetic algorithm which will learn how to throw a ball at a target. I have successfully implemented code that will graph the projectile motion of a sphere given an input velocity vector $u(0)$.

However, I'm not really sure about the crossover part. Right now, I am selecting the parents using a distribution whereby their chance of being picked is equal to $\dfrac{i}{\tfrac{n(n+1)}{2}}$ where $i = n - p$ where $p$ is the individual's position in the population when sorted by fitness from best to worst and $n$ is the number of individuals in the population. Then I randomly pick $n$ individuals from the population according to this distribution, and I take individuals $n_i$ and $n_{i+1}$ as parents. Then I make a child $c = \begin{bmatrix} \dfrac{u_{x_i}(t) + u_{x_{i+1}}(t)}{2} \\ \dfrac{u_{y_i}(t) + u_{y_{i+1}}(t)}{2} \\ \dfrac{u_{z_i}(t) + u_{z_{i+1}}(t)}{2}\end{bmatrix}$ and keep repeating this until I have a new population filled with $n$ children.

After $51$ generations, my sphere hit one point specified point on the plane. However, I don't think this is the most effective crossover method and I would really appreciate some suggestions on how to improve it.

Sorry if my notation or explanation is unclear, please ask me to explain it if it is not evident what I mean.


texts:
A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all vertices). I need an algorithm to find the longest path in such a graph.

I know that in general longest path problem is NP-hard. I want to know whether for this special case there exists a polynomial time algorithm.


texts: Can a shortest-path tree be a also maximum spanning tree?

texts:
If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example!

I tried every combination I could come up with using connected graphs with cycles on them (so that there is more than one possible path) and used Dijkstra's algorithm. No luck!


texts: Maximum matching to find the minimum edge cover

texts:
Suppose that I have an edge cover for the graph $G=(V,E)$ with non-isolated nodes to be a subset of $E^1$ of $E$ such that every vertex $v∈ V$ is incident to some edge in $E^1$. The size of an edge cover $E^1$ is denoted by $|E^1|$, is the number of edges in $E^1$ and $|M|$ denotes the number of edges in the matching graph.
So, I'm using the maximum matching to find the minimum edge cover. To do this, I'm showing
My Attempt:
I first assumed the graph $G=(V,E)$ without isolated vertex. Next, both edge cover and matching are set of edges, and the subset of an edge cover can be a matching. Given arbitrary edge cover C, we denote by $M_C⊆C$ the maximum matching containing in C.
I don't understand how to proceed further.
I'm very new to graph theory, so please help me by pointing in the right direction.


texts: How can a language whose compiler is written in C ever be faster than C?

texts:
Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler  originally written in C, outperform C code?

Figure: benchmark times relative to C (smaller is better, C performance = 1.0).


texts: How to write recurrence relation for backtracking problem?

texts:
I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that.
Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but  think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable. Can anyone help in explaining such recurrence relation.