texts: Is there a data structure that can perform range modulo additions and range minimum queries?

texts:
It is well-known that the Segment Tree performs range additions and range minimum queries in O(logN) each.

Let each element in the array have value V[i], M[i]. We define a "range modulo add" as the following: add +X to V[i] for each element in the range L<=i<=R and then calculate modulo M[i] for each element L<=i<=R. Can both this operation and range minimum queries be run in (worst-case or average-case) o(N)? If not on ranges [L,R], is it possible to handle range minimum queries and range modulo adds on the entire array quickly?

EDIT: There are two separate operations here. One is void range_add(L,R,X) which adds X to every element L<=i<=R, and then takes every element L<=i<=R modulo M[i]. The second is int rmq(L,R) which finds the smallest element in the range [L,R].

Here is an example of how it may operate, for clarity:

Let the starting (1-indexed) array be:
V = {1,2,3,4,5}
M = {5,4,6,2,8}

After range_add(1,3,4), the array V looks like this (the array M is always unchanged):
V = {0,2,1,4,5}
Note that indexes all the indexes from 1 to 3 exceeded their M-value after the addition, and were taken modulo their M-value.

After this, rmq(2,4) would return 1.

Please note that values X may be negative. If the value of a V[i] is reduced to below 0, then it becomes positive - eg. if V[i]=-1 and M[i]=4, V[i] will become 3.


texts: How many segments a process can have in operating system employing Segmentation for memory management

texts:
Some facts about "Segmented Paging"

1)  Each process has one segment table.
2)  There is one-page table per segment.

Fact about "Paged segmentation"

3)  Contains page table of segment table.

Now consider following problem

  In a paged segmented scheme of memory management, the segment table itself must have a page table because.
  (A)  The segment table is often too large to fit in one page.
  (B)  Each segment is spread over a number of pages.
  (C)  Segment tables point to page tables and not to the physical locations of the segment.
  (D)  The processor’s description base register points to a page table

Given solution is:

Here option (A) is true , as segment table are sometimes too large to keep in one pages. So, segment table divided into pages. Thus page table for each Segment Table pages are created.

My Doubt

I believe a page can contain several hundreds of segment table entries of form

  <segment base, limit>

I only came across code, data, stack and heap segments. I believe a process can have only these  "four" segments. And also, we know each process has a segment table (Fact 1). Then how a segment table can grow so large that it cannot be fitted in a single page?


texts:
recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
EXPLANATION PART
 consider a box with n-dimension and there are k different boxes with n dimension each
so the task is simple we have two insert one box into another and we have to find maximum number of boxes which can be inserted one after the another rotation is also allowed around different axis
for example there are 4 box with 2 dimension
5 2
1 1
5 8
3 2
so the boxes 1 can be rotated and can be inserted into 3 and 2 can be inserted into 1 so the maximum is 3
i have a question that why topological ordering works here why not normal sorting works what i did was first i sorted all the edges of one boxes in increasing order and then  sorted all the boxes in increasing order based on their first index and after that i calculated the longest increasing subsequence


texts: Defining a predicate on the structure of a string

texts:
I have the following homework question. (For a bit of context - the study unit is Formal Languages and Automata).

  Define the predicate $\mathrm{pre}(s,t)$ over $s, t\in\Sigma^*$ by induction on the structure of $s$ such that it satisfies the following conditions:
  $$\mathrm{pre}(s,t) = \begin{cases}
\mathsf{true} & \text{if there exists $s'\in\Sigma^*$ such that $s \mathbin{+\!\!+} s' = t$} \\
\mathsf{false} & \text{otherwise}.
\end{cases}$$

Now I have considered two definitions so far. However they both assume things about the structure of $t$, and the way the question is worded implies that we can only assume things on the structure of $s$ (in a recursive way).

The definition is:
$$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\
   \mathrm{pre}(\alpha.s,\beta.t) := (\alpha = \beta) \wedge \mathrm{pre}(s,t),
$$
and the second, which avoids having $\beta.t$ in the argument:
$$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\
   \mathrm{pre}(\alpha.s,t) := (\alpha =\mathrm{head}(t)) \wedge \mathrm{pre}(s,\mathrm{tail}(t)),
$$
where I would then define $\mathrm{head}$ and $\mathrm{tail}$ in a recursive way on $\alpha.s\in\Sigma^*$ (so essentially, this does the same thing).

Is there a way this can be done without assuming anything about the structure of $t$?


texts:
How should I understand the definition of computational problem?

  A computational problem is a mathematical object representing a
  collection of questions that computers might be able to solve. For
  example, the problem of factoring

  "Given a positive integer n, find a nontrivial prime factor of n."

What is the mathematical object in the example above? Quoting Wikipedia again:

  Commonly encountered mathematical objects include numbers,
  permutations, partitions, matrices, sets, functions, and relations.

So how can you 'represent' a collection of questions with numbers or permutations, matrices etc.? What is meant here is probably the following collection of sentences:

'find a nontrivial prime factor of 1', 'find a nontrivial prime factor of 2' and so on...

But the thing is - these sentences are not mathematical objects.

A little further in the article it reads:

  A computational problem can be viewed as an infinite collection of
  instances together with a solution for every instance.

which makes perfect sense, but I don't quite see the relationship with the first definition.


texts:
I have an exercise in my algorithm's Course for which I have the correction but do not understand it.

1.Exercise .

Let Th be a full binary three of height h(meaning all the levels all completely full).

(1.a) : Let f(h) be the number of leaves of Th(nodes of the last level).
Establish a relation for f(h) and solve it recursively. Give the exact expression for f(h) in terms of h, and the asymptote expression (in Big-O notation)

Correction

f(h)=2*f(h-1) for h >= 1 and f(0) =1.
f(h)=2*f(h-1)=4*f(h-2)=8*f(h-3)=...=2^hf(h-h)=2^hf(0) =2^h.
Complexity : O(2^h)

I simply do not understand why h-1. Because suppose we have a full binary tree with h=2 . If h=2, then number of leaves = 4 . Applying the correction resolution:
f(2) = 2*f(2-1) = 2*f(1) = 2, which is different from the number of leaves, which is 4.


texts: Basic requirements for Integrality gap examples

texts:
I have the following question about giving a series of examples of range spaces for my Hitting Set problem that establish a lower bound for the integrality gap (IG).

IG is the supremum of ratio of the optimum for natural integer linear programming (ILP) formulation of Hitting Set to the optimum for its (mean ILP) LP-relaxation taken over all range spaces corresponding to my problem.

There are lots of algorithms where solution for LP-relaxation is rounded to some feasible solution of ILP which is not far from optimum. IG gives the lower bound of multiplicative factor to which rounding procedure could worsen the optimum for LP with respect to the goal function.

Specifically, do I need to provide any polynomial algorithm for generating those series of example range spaces (giving the gap lower bound) ? if yes, then what are the parameters with respect to which my algorithm should be polynomial in ?
I'm interested in this because by claiming some gap lower bound I provide  educated lower bound for approximation algorithm performances which are based on aforementioned LP-relaxation.


texts: If L1 ∪ L2 and L1 are regular, is L2 also regular?

texts:
This is a problem in a theory of computation book that's stumping me:

  Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is
  regular? Explain.

At first, I thought I could build the NFA that is the union of two DFAs, one which accepts $L_1$, and one which we don't know about.  Then lambda transition over to the $L_1$ DFA.  Then, the union would be regular, but we wouldn't be able to conclude anything about the $L_2$ DFA.

I think my reasoning is poor though.  Could someone please point me in the right direction?

Thank you.


texts: Will a vertex present in the set of vertices present in each basis cycle be present in all the cycles?

texts:
I read that the XOR of basis cycles can generate all the cycles present in the graph.

I was just wondering if there exists any one vertex which is present in all the basis cycles and is present in all the cycles of the graph.

Can someone point me to something that might help me tackle this problem?


texts: How to cluster similar objects into fixed size groups?

texts:
I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day.

eg - Suppose there are 3 people who are free on (M,T,W,Th,F), (M,W) and (W,Th,F) respectively. They can all be placed in the same group since all of them can meet on Wednesday.


texts: Implementation/explanation of the hub based labelling algorithm

texts:
I've found plethora of papers describing the performance advantages and basic correctness proofs of the hub-based labelling shortest path algorithm.

However I'd like to implement the algorithm, and short of doing it from scratch don't see much of any other way.

Is there a resource or a project where such an algorithm is implemented, and or explained in detail?

My biggest problem is that I don't know much about the most practical datastructures (e.g. I'd be using a Fibonacci Heap, when it might be smarter to use something else, and I have very little information on the details of the algorithm.


texts: Explanation of the extended Euclidean Algorithm

texts:
I am looking for some help with understanding the extended Euclidean Algorithm, specifically, this implementation (in Haskell):

eGCD :: Integer -> Integer -> (Integer,Integer,Integer)
eGCD 0 b = (b, 0, 1)
eGCD a b = let (g, s, t) = eGCD (b `mod` a) a
           in (g, t - (b `div` a) * s, s)

I understand the Wikipedia explanation but that is based on the invariant

$$ as_i + bt_i = r_i $$
With the recurrence relations:

$$ r_{i+1} = r_{i-1} - q_i r_i $$
$$ s_{i+1} = s_{i-1} - q_i s_i $$
$$ t_{i+1} = t_{i-1} - q_i t_i $$

And the proof follows from Induction.

On the other hand, the implementation above uses the rule

$$ s_{i+1} = t_i - q_{i-1} s_i $$
$$ t_{i+1} = s_i $$

These must be somehow equivalent but I am having trouble seeing it.


texts:
In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For example, on the stated page it says that graph isomorphism is a more general problem than group isomorphism.

Hence I am posing the following

  Given a group $G$ can someone give a construction of a graph
  $\Gamma(G)$ of size polynomial in $|G|$ such that $$\Gamma(G) \cong
 \Gamma(H) \iff G \cong H$$ for groups $G$ and $H?$


texts: Find K-subset that includes the most W-subsets

texts:
I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements.
Subsets can overlap partially or totally.

For a given $K < N$ (but $K \gg W$), I want to determine the subset $X_K \subset N$ so that:

$X_K$ has $K$ elements.
$X_K$ includes the largest possible amount of subsets among $\sigma_0, \ldots, \sigma_{N -1}$.

Example:

$S = \{A, B, C, D, E\}$, $W = 3$

$\{\sigma_0, \ldots, \sigma_4\}= \{\{A, B, C\}, \{A, B, C\}, \{B, C, D\}, \{A, B, E\}, \{A, B, D\}\}$

$X_4 = \{A, B, C, D\}$ (as it includes $\sigma_0, \sigma_1, \sigma_2$ and $\sigma_4$)

What is the best algorithm to find $X_K$?


texts: Is it possible to modify the linux assembler in order to modify what fuctions do?

texts:
I was wondering if it were possible to modify the linux assembler in order to change the function of "-" to "+" and vice versa.
I was also wondering if this would affect the whole system making it collapse. I apologize if this question is not appropriate here. Please explain why if it is the case.

E.g:
2+2 = 0
2-2 = 4

My objective is to see what applications this could have for a potential computer virus (I hope this is allowed here).


texts:
If given any language L, how do I find the complement of said language?

I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $\overline{L}$, is recognizable.

But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:

  Is the following language co-recognizable?
  $L$ = {$<M>$ | $M$ is a
  turing machine, and $1010 \notin{L(M)}$}


texts: Counting elements that are greater than the median of medians

texts:
Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition.

Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers.  The algorithm is roughly:

  Input: an array of $n$ elements and $i$, the number of the order statistic to return from the elements.

  Divide the $n$ elements into $\lfloor n/5 \rfloor$ groups of 5 elements each along with an optional group containing $n\mod{5}$ elements (resulting in $\lceil n/5 \rceil$ groups.)
  Find the median of each of the groups by sorting.
  Recurse, using the $\lceil n/5 \rceil$ medians as the array and $\lfloor\lceil n/5 \rceil/2\rfloor$ as the order statistic, resulting in the median-of-medians.
  Partition the $n$ elements around the median-of-medians (using a quicksort-like $O(n)$ partitioning algorithm.
  Letting $k-1$ be the number of elements less than the median-of-medians, if $i = k$, return the median-of-medians.  Otherwise recurse: if $i < k$ then recurse finding the $i$th order statistic of the $k-1$ elements less than the median-of-medians; if $i > k$,  then recurse finding the $i-k$th order statistic of the $n-k$ elements greater than the median-of-medians.

  Output: the $i$th order statistic of the $n$ numbers.

In the proof of the runtime, CLRS argue that the number of elements greater than the median-of-medians is at least:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg)
$$

The reasoning is that half of the medians are greater than the median-of-medians, and each of those medians' groups has at least three elements greater than the median-of-medians (the median itself plus the two elements greater than the median.)  That would result in

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg)
$$

for the lower bound on the number of elements greater than the median-of-medians.

But we must account for two things: the group containing the median-of-medians (the median-of-medians is not greater than itself) and the group that contains the modulo leftovers.  To account for the group containing the median-of-medians, we subtract 1, resulting in:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 1
$$

and I think that for the modulo leftovers group, we should subtract 4, because the least number of elements in the group is 1.  So that would give:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5
$$

which can be transformed into

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) + 1
$$

Why does my analysis lead to a lower-bound 1 greater than that given in CLRS?


texts: Different decompositions of the string in the pumping lemma proof

texts:
Let $s = a^pb^{2p}$, now which one of those decomposition is correct:

$x=a^k$, $y=a^l$, $z=a^{p-k-l}b^{2p}$, where $k+l \leq p$

$x=a^{p-k}$, $y=a^k$, $z=b^{2p}$, where $1\leq k \leq p$

$x=\epsilon$, $y=a$, $z=a^{p-1}b^{2p}$

or are they the same? I've read in multiple answers that we don't get to pick the decomposition, but I'm not sure how to understand this, because to me all of those decompositions are legitimate.


texts: Simple Representation of Matrices with the Given Equivalence Relationship

texts:
I'm currently working on an algorithm that requires me to come up with unique matrices. Two matrices are considered equivalent if one's rows and columns can be swapped to make it match the other. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}$. I think it would be immensely helpful to find a nice way to represent each matrix so that equivalent matrices have the same representation. The best I could come up with is just making a list of the rows and columns and comparing them. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}=>\{R:((0, 0), (1, 1))\}, \{C:((0, 1), (0, 1))\} $ $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 1), (0, 1))\}$ $\begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 0), (1, 1))\}$

but I feel like there's a better way because this looks messy. Any suggestions?

Edit: This is not always binary matrix. Numbers can range from 0-19.


texts: what are read/write operations involved in main memory, cache and processor?

texts:
please bear with me, I always get confused with the terminologies used in my computer architecture class.

What are read and write operations exactly? What are their relationship with processor, main memory, and cache?

I always thought that load/store are interchangeable with read/write...

What about the modify operation?


texts: DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring

texts:
In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA.

  The set of binary strings of length at least 3 where every substring
  of length 3 contains at least two 0s.

So in other words, something like 100100010 should be in the language (L) for this DFA but something like 11001010 would not be in the language.

I know that you can start off by writing/drawing smaller DFAs for the substrings that are the pattern 000, 010, 100, 001, etc, but I cannot seem to get a hold of how it should look all together.

Any help in understanding this would be appreciated.


texts:
I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the machine being used to solve them.

My Understanding

Standard Turing Machine - a Turing Machine which has a finite alphabet, finite number of states and a single right-infinite tape
Turing-Equivalent Machine - a Turing Machine which, can emulate, and be emulated by, a Standard Turing Machine (quite often with some trade-off between space and time achieved by the emulation)
P - the class of problems which can be solved in polynomial time using a Standard Turing Machine (defined above)
NP - the class of problems which can be verified in polynomial time using a Standard Turing Machine
NP-complete - the hardest problems which are still in NP, which all NP problems can be converted to in polynomial time

My Question

Are the complexity classes (P, NP, NP-complete, etc) related to the algorithm, or the algorithm and the machine?

Said in another way, if you could create a Turing Equivalent Machine (that can solve all the problems that a Standard TM can, but in a different amount of time/space) and this new machine could solve an NP-complete problem in time which grows as a polynomial with respect to the input, would that imply P=NP?

Or must the NP-complete problem be solvable on all possible Turing Machines in polynomial time to be considered in P?

Or do I mis-understand something fundamental above?

I have had a look (maybe not with the correct search terms, I don't know all the jargon quite well) but it seems most lectures/notes etc. focus on standard machines but say that custom machines often have some time/space speed up at the expense of space/time, without saying how that bears on complexity classes. I'm not really familiar enough with the jargon in this field yet to find papers which explain this.


texts: How to graph search a LTL-generated Buchi automaton to generate valid execution paths

texts:
I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal.  I want to find a way to enumerate all permutations of the tasks that meet the specification.

For example, suppose there are two tasks, A and B, and the LTL spec <>(A&<>B) is.  This spec says that A should eventually be done and after A eventually B should be done.  In this case, there is only one legal sequence: (A,B).

We can convert the LTL formula to a Buchi automaton, as shown above. Then since this example is so trivial, it is easy to see that the only legal sequence is A-->B.

But what if we had a more complex LTL formula?  How could we enumerate all legal sequences (permutations) of the tasks that satisfy the spec?  Is there an efficient algorithm to do this?


texts: Independent set poly reducible to Strongly independent set?

texts:
A strongly independent set of a graph $G'$ is a subset $S$ of vertices such that the distance in $G'$ between every two distinct vertices in $S$ is larger than $2$.

It is possible to reduce an instance $\langle G, k\rangle$ of the decision version of independent set to an instance $\langle G', k\rangle$ of the decision version of strongly interdependent set by (1) replacing each edge $e=(u,v)$ of $G$ with two edges $(u, w_e)$ and $(w_e, v)$, where $w_e$ is a new vertex; and (2) connecting all the vertices $w_e$ with a clique.

In the newly created Graph $G'$, why does adding a middle node prevent us from choosing that node? Basically, how does the reduction step help us?

Solution Notes: http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut11.pdf


texts: Where can I find a high quality copy of Turing's On Computable Numbers?

texts:
Currently, I'm reading a photocopied version of Turing's famous article On Computable Numbers, With an Application to the Entscheidungsproblem.

This is the best photocopy of his paper that I can find; most other copies are of pretty low quality to the point that I can't distinguish between different characters. The e in the final m-config column on page 233 for example, looks exactly like a c on many copies (not the one I'm using though). I also have trouble distinguishing between the german capitol letters C and E later in his paper on page 238 and such. Is there any place where I can find a well copied version of the paper? Perhaps a book would have a nice copy.


texts: How to express a type that represents an associative array whose keys determine the type of the value?

texts:
I'm fairly new to type systems and theory, so I would appreciate some guidance in a problem that sparked my interest.
I would like to understand what type system features are required so a compiler can enforce that a given key will return a value of the same type as the one the key was associated with in the first place.
A practical version of my problem is to declare a Map in TypeScript that allows a developer experience like in the pseudocode below:
const cache =  new  Map<K,  V>()

cache.set('Foo',  Error('R'))

cache.set('Bar',  1)

cache.get('Foo')  // Return value typed as Error.

cache.get('Bar')  // Return value typed as number.

cache.get('Qux')  // Compilation error.

What would the type of K and V be?


texts: How to decide between operational, denotational, and axiomatic semantics?

texts:
Context

I'm designing a language which implements lambda calculus and (first-order) predicate calculus, where lambdas behave as the abstraction encapsulating logic, compositionally forming a computational model for higher-order logic.

Question

How does one, in general, choose between operational, denotational, and axiomatic semantics? I understand the way in which they describe the semantics for some language specification, and I understand they're often mixed (particularly operational semantics with one of the other two), but I'm not sure how to best identify the right formal semantics to use in general. I've seen lambda calculus expressed in both operational and denotational semantics (purely), for instance. I'm currently favoring denotational semantics for my project. But I would like to know how to identify whether this is the right choice for this project and others in the future.

I've read that denotational semantics is useful in source-to-source translation, which is what I'm thinking of doing: either writing an interpreter or a transpiler (source-to-source compiler), which translates the code into C++ and allow a C++ compiler handle the compilation into machine code. The idea is that I can make use of lambdas in C++ (since C++11), as they are standard/portable and rigorous. I'm leaning towards the compiler currently. Or might this not be a good idea? I may write something better later on with LLVM or GNU Lightning.

An additional question (if anyone can answer this as well, that would be great!)

I understand how environments / environment functions are necessary when interpreting a language that needs to keep track of variables and such, but is it necessary/applicable for a compiler? If so, how would the environment be best expressed/implemented if I were to compile to C++?  By environment, I mean the set of paired values which map identifiers to values.


texts: Survey of Graph Algorithms with applications to data/ML?

texts:
I'm a new Computer Science student in a masters program, switching from Applied Math. I'm really new and lacking some background, but I am interested on what literature is out there on graph algorithms, just so I can get an idea of what is possible, what is impossible, what work has been done before, etc. I'm trying to fill some gaps and get up to speed on so I can start reading papers on the topic.

I'm interested in the ways we can represent datasets as graphs and in what scenarios we can learn those graphs. For example, if we have a time series data set, we can model this as a Hidden Markov Model with potentially continuous hidden states. It's possible to write this down as a graph where each hidden state is a node with an edge towards the realized response. Or, if we have a data set, we can write down a Belief Network that represents some kind of causal model for how each random variable affects each other.

In particular, I'm curious about the following questions:

1) Since it is difficult to learn a graph/BN from data under no assumptions, when can we learn a graph/BN? When can it be done quickly?

2) Do we generally use belief networks when talking about graphs and data together, or are there other graphical models for common data problems?

Bonus question: What is the best way to get up to speed on the techniques used in algorithms literature? I'm comfortable with mathematics and proofs but am lacking some experience in how theoretical computer scientists think and solve problems.


texts:
Is there any feature detector or extractor that uses color information?

Detectors like SURF and SIFT and many others work with grayscale. How do you think, may be transform can be sued to generate a grayscale image without loosing color info but suitable for those algorithms?

In particular, I need to distinguish objects similar in shape, but of different color. And in general, color provide more information about objects, and allows to classify them with better performance, that's why we have color vision.


texts: Extending the type scheme for Burks/Warren/Wright machine to handle operators on functions?

texts:
Some background: Burks, Warren and Wright published a description of simple interpreter for a Logic Machine for unparenthesized Lukasiewicz notation (paper, SO question, c implementation, postscript implementation) which was heavily cited in Kenneth Iverson's 1962 classic A Programming Language.

Within there is an elegant system of typing by associating integer weight to variables, literals, and functions, which allows a simple max_weight/length test for well-formedness (ready for reduction), as well as a simple formula to convert the weight into the degree or arity of the function. Specifically, variables and literals are given weight=1, and unary functions are given weight=0, and binary functions are given weight=-1. For a function (w<1), its degree d is 1-w.

What I'd like to do, and I'm not sure how to go about it, is to add APL's operator type to the mix. But it would seem that I need a very weird kind of number, that can by simple arithmetic yield the function arity and yield the correct positive (minimum, ie. 1) weight for a complete well-formed formula.

For the extended language, I'm adding integers 0-9 as well as variables a-z, binary + and -, and unary < "box" and > "unbox", and the monadic operator / "reduce". Also, we'll use infix syntax with right-to-left evaluation, like APL.

So for the very simple formula "0+4", we encounter

0  literal, w=1
0+  function, w=-1, sum of weights=0,  function degree=1-w=2
0+4  literal, w=1, sum of weights=1 <--complete wff

Now the problem happens when I try to add an operator, it needs to counterbalance the weight of its associated functions, thus it should be positive, but it shouldn't ever create a condition of "false positive", so it also needs to be further from positive. Perhaps another dimension, or a second field of the type descriptor?

For "+/ab", the sequence of discovery is

+  function, w=-1, function degree=1-w=2
+/  operator w=1??  sum of weights=0
+/a  variable, w=1, sum of weights=1 <-- false positive.
+/ab  variable w=1, sum of weights=2, yet I want this to sum to 1.

Is there a better way that I'm not seeing?


texts:
I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model.

I have a pretty basic question, but am really hoping some of you guys can help me understand the concept behind it:

  Why is everything centered around the notion and definition of
  LANGUAGES (i.e. regular languages and context free languages)? And how
  do these relate and describe the complexity of an algorithm and the
  possible computational models for solving them?

I read these sort of related questions:

https://cstheory.stackexchange.com/questions/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
https://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory

but still don't have an answer to my doubts, since they provide a practical justification of why they are important (which I do understand) but don't help me understand why complexity theory is based upon them.


texts: Do I understand pseudo polynomial time correctly?

texts:
The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.

My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?


texts: Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

texts:
I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.

I couldn't make up my mind on this statement. How can a grammar which is both left recursive as well as right recursive not have more than one parse tree for a single string.

Am I right? If not, please provide a counter example whereby my assumption can be proved wrong.

Thanks in advance!


texts: Is it possible to turn an eulerian NFA into a linear size DFA?

texts:
In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states.

But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n into a DFA of size at most O(n) ?

If so, does it hold also for a NFAs whose graph is strongly connected ?

I would appreciate some counter example, proof or any reference to research papers dealing with this problem.

Many thanks, Luz


texts: Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

texts:
The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction.

The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction.

I wonder if NPSPACE is also closed under polynomial-time reduction and/or under log-space reduction.


texts:
I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot of the relevant paragraph is here: screenshot

Edit: sentinel item a[0] = x, the current item that I want to insert at the appropriate place.

Sorry, another screenshot of relevant paragraph is here: screenshot2

    type index = 0..n
    var a: array[0..n] of item

    procedure straightinsertion
        var i,j: index; x: item;
    begin
        for i := 2 to n do
        begin x := a[i]; a[0] := x; j := i-1;
            while x.key < a[j].key do
                begin a[j+1] := a[j]; j := j-1;
                end;
            a[j+1] := x
        end
    end

I think, that the analysis of the number of comparisons might be wrong. He claims, that the number C_i of key comparisons in the i-th sift is at most i-1. But shouldn't it be i? Because at the worst case, since we are using sentinel, we have to make an extra comparison with the sentinel too. I claim, that:

C_min = n-1
C_ave = 1/4 * (n^2 + 3n - 4)
C_max = 1/2 * (n^2 + n) -1

The number of moves M_i should then be (i-1)+2. M_min, M_ave, M_max are, I believe, correct in the text (screenshot).

Could you please confirm if I'm right or is there something I'm missing?Thank you all very much!


texts: what algorithm is used to calculate the exponential function $e^x$?

texts:
I am using Matlab daily. But I just realized that I even do not know what algorithm Matlab is using for calculating the exponential function $e^x$.
The power series expansion is obviously not appropriate for a big $|x|$.


texts: Upper Bound on Runtime of Memoized DP Algorithms

texts:
I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions.

However, I am now trying to determine a "Big-O" for a DP problem I've memoized.  I don't really care about the answer to this specific problem, but am more interested in a method I can use for other programs I write, or a resource that I can read to learn how to analyze this type of program.

In case a concrete example helps, the following is my program to solve this box stacking problem.  (I wrote my solution before looking at theirs, which appears to use bottom-up DP instead of top-down/memoization.  Thus, I don't think I can cross-apply their time complexity to my algorithm.)

Below is the pseudo-code for my solution.  Assume that putting something on the memo and checking the memo can be done in constant time.

Let a box have parameters width (w), height (h), and depth (d)
reward(maxW, maxD, elementH):
  Zero max1, max2, max3
  If memo contains key (maxW, maxD), return associated value.

  for each box B in the list of input boxes:
    //If the box fits in any orientation, put it on the pile and recurse
    if (B.w < maxW AND B.d < maxD) OR (B.w < maxD AND B.d < maxW)):
      max1 = max(max1, reward(B.w, B.d, B.h) + B.h)
    if (B.h < maxW AND B.d < maxD) OR (B.h < maxD AND B.d < maxW)):
      max2 = max(max2, reward(B.h, B.d, B.w) + B.w)
    if (B.h < maxW AND B.w < maxD) OR (B.h < maxD AND B.w < maxW)):
      max3 = max(max3, reward(B.h, B.w, B.d) + B.d)

  put (maxW, maxD) onto memo, associated with max(max1, max2, max3)

  return max(max1, max2, max3)


texts: Encoding (binary) trees using lambda calculus

texts:
I'm new to lambda calculus, and I read all kinds of interesting stuff about encoding data types as functions. Church booleans, numbers and lists.
https://en.wikipedia.org/wiki/Church_encoding

Is there a way to encode (binary) trees?


texts: Dynamic programming table for finding similar substrings is too large

texts:
Substring Diff
  Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of
  mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}$. In set
  notation, $M(i, j, L)$ refers to the size of the set $\{0 \leq x < L \mid p_{i + x} \neq q_{j + x}\}$.

  Given an integer $K$, your task is to find the maximum length $L$ such
  that there exists pair of indices $(i,j)$ for which we have $M(i, j, L) \leq K$. Of course, we should also have $i + L - 1 \leq n$ and $j + L - 1 \leq n$.

  Constraints

  $0 \leq K \leq |P|$
  Both $P$ & $Q$ would have the same length
  The size of each of the string would be at the max 1500
  All characters in $P$ and $Q$ are lower-case English letters.

The recursive function will have the form:

longest(string1, string2, allowed_mismatches) =
    {
        ... (something :P )
    }

The state space then has size $K^3$. With an upper bound on $K$ of 1500, the running time and space usage will be terrible... So direct dynamic programming will not work without some additional property to reduce the state space.

Ideas?

UPDATE

Using the ideas suggested by both Yuval and Vor, I came up with the following solution that works like a charm, running in $O(K^2)$ time and using $K$ space.

def longest_range_min_sum(str1, str2, start1, start2, slice_size, max_sum):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < slice_size:
        if str1[start1 + i + longest] != str2[start2 + i + longest]:
            running_sum += 1
        if running_sum > max_sum:
            if str1[start1 + i] != str2[start2 + i]:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest

import sys

data = sys.stdin.readlines()
num_cases = int(data.pop(0))
for ignore in xrange(num_cases):
    max_mismatches, str1, str2 = data.pop(0).split()
    max_mismatches = int(max_mismatches)
    m = n = len(str1)
    longest = 0
    for i in xrange(m + n + 1):
        if i > n:
            slice_size = m - (i - n)
        else:
            slice_size = min(i, m)
        if slice_size == 0:
            continue
        end1 = max(m, m - i)
        if i > n:
            end1 = m - (i - n)
        start1 = end1 - slice_size
        end2 = min(i, n)
        start2 = end2 - slice_size
        #print zeros_and_ones
        #print str1[start1:end1], ' - ', str2[start2:end2]
        longest_in_sub = longest_range_min_sum(str1, str2, start1, start2, slice_size, max_mismatches)
        #print longest_in_sub
        longest = max(longest, longest_in_sub)
    print longest


texts: Ellipsoid with minimal volume that contains 2 other ellipsoids

texts:
Given two ellipsoids $e_1, e_2$, and we need to find another ellispoid $E$ such that $E=\arg\min_{E\ :\ e_1,e_2\subseteq E} {V(E)}$ (where $V(E)$ is $E$'s volume). In words, $E$ has the minimal volume among all ellipsoids that contain both $e_1$ and $e_2$.

So, I am looking for some algorithm/ formula for computing $E$.

So far, I investigated the case where $e_1$ and $e_2$ have the same center. In that case, I guess that taking the biggest radius (from the union of $e_1$'s radii and $e_2$'s radii), and then projecting the ellipsoids $e_1,e_2$ (or their radii) onto this radius, then repeating this process yields the desired ellipsoid.

However, I have no idea what to do in the general case - where $e_1$ and $e_2$ have different centers.

Any help would be appreciated!
Thanks in advance!


texts: Can minimal CNF contain clause longer than initial CNF?

texts:
Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$.

Can $\Phi_{min}$ contain a clause of size $m > k$?

What I have tried:

Let's define the concept of partial assignment: asingnment that has free variables. Example: $x_1 = 0, x_2 = \{0\ ,1\}, x_3 = 1$. Here $x_2$ is a free variable.

If $\Phi$ contains clause $C(p)$, then $\Phi(\overline p) =0$.

Example: $\Phi = (x_1\lor x_2\lor x_3)\land (x_2\lor x_3\lor x_4)$. Here $\Phi(x_1=0,x_2=0,x_3=0)=0$.

Going further, if $\Phi$ is k-CNF, it means that shortest unsatisfied partial assignment has length $l\leq k$.
Also, formula already contains info about all unsatisfied partial assignments.

P.1 and p.2 says, that we don't need to use partial assignment of length $l>k$ to express the formula.

One more statement, $\Phi(p)=0\Rightarrow \Phi(p, x_i)=0$, where $x_i$ is fixed variable that is not in $p$.

Here is where I got stuck: $\Phi_{min}$ contains smallest amount of shortest inverted partial assignments of formula $\Phi$. Let's say that each of partial assignments $p_1, p_2$ has length $l$, such that $\Phi(p_1) =0, \Phi(p_2)=0$. Can we change them to one longer partial assignment $p$?

Restrictions are following: if you'll change or remove any variable in $p_1$ or $p_2$ (we'll call them $p'_1$ and $p'_2$ respectively), then $\Phi(p'_1) = 1$ and $\Phi(p'_2)=1$.

Intuitively it seems that they can't be combined, but what about logic?


texts:
If the two generals problem is unsolvable how can we human beings agree on things?

I mean, we communicate everyday and have the same limitations as any communication problem handled by computer science. Why doesn't it affect us?


texts: What is the practical purpose of an epsilon NFA?

texts: If for every $\epsilon$-NFA their exists an equivalent NFA what is the purpose of ever using an $\epsilon$-NFA? I am having trouble understanding what the practical purpose of using one would be.


texts: What are the technical reasons for which the empty string is not allowed to be accepted by a Turing machine?

texts:
Below are the excerpts from the automata text by Peter Linz.

Definition 9.3
Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is
$$L(M) = \{ w \in \Sigma^+ : q_0w \vdash ^* x_1q_fx_2 \text{ for some } q_f \in F,x_1,x_2 \in \Gamma^*\}$$

From the above definition it is clear that the $\Sigma^+$ in it does not allow the empty string to be accepted by the Turing machine.
Later in the example:

Example 9.6
For $\Sigma = \{0,1\}$, design a Turing machine that accepts the language denoted by the regular expression $00^*$.
Solution :

Though the diagram is not given, I give it to simplify the situation. Then Linz adds,

Note that the Turing machine also halts in a final state if started in state $q_0$ on a blank. We could interpret this as acceptance of $\lambda$ (empty string), but for technical reasons the empty string is not included in Definition 9.3.

I have read the automata text by Ullman, but there was no such restrictions imposed on Turing machines. Using the concepts I have learnt from Ullman text, I could solve the problem as:

this no longer has the problem of acceptance of $\lambda$.

So what might be the technical reason or it is just a discretion of the author or reduction of the number of states?


texts:
In the proof in wikipedia, it goes like this:

Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula:

$\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$

(where V is polynomial deterministic verifier etc...)
Now they look at the subformula : $s(y)=\exists_{z} V(x,y,z)$ and say that because it's an instance of $SAT$, and according to the hypothesis that $NP \subseteq P/poly$, its equivalent to $C(s(y))$, where $C$ is a valid circuit for solving $SAT$.

These are my questions:

What does $s(y)$ mean? Like what's the meaning of saying that something equals some predicate? It look like merely a technical part of the proof but I can't wrap my head around it.
What's the meaning of exchanging a logical predicate with circuit evaluation mean? Does it mean that we can decide if for every $y$ there exists $z$ such that $V(x,y,z)=1$ with a circuit?


texts: Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

texts:
I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
The site here https://courses.csail.mit.edu/6.046/fall01/handouts/ps2sol.pdf mentions :

The running time of HEAPSORT on an array A of length n that is sorted in decreasing order will
be  $\Theta(n\lg n)$.
This occurs because even though the heap will be built in linear time, every time the
max element is removed and the HEAPIFY is called it will cover the full height of the tree.

It's the last line which I can't understand. I tried the array A <7, 6, 5, 4, 3, 2, 1>. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get <6, 4, 5, 1, 3, 2> 7. However, the second time itself the full height of the tree is not covered and I get <5, 4, 2, 1, 3> 6, 7. How does that statement hold then?
Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs full $\lfloor \lg k \rfloor$  operations, where k (I'm assuming) is the number of nodes in the modified heap in each iteration, thereby obtaining the summation.
$$ \sum_{i=1}^{n-1}\lg{(n-i)}= \lg\Big((n-1)!\Big) = \Theta(n\lg{n}) $$
Can someone help me realize this. I just want to understand how MAX-HEAPIFY covers the full height of the tree each time it is called.
UPDATE: I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. During HEAPSORT, if each node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree, that would mean that each call to MAX-HEAPIFY won't perform full $\lfloor \lg k \rfloor$ operations but $ \Theta(\lg k) $ operations, right? (I know $\lfloor \lg k \rfloor $is also $\Theta(\lg k)$ but all I need is for MAX-HEAPIFY to perform $\Theta(\lg k) $ operations each time)  $$ \sum_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But that statement doesn't hold as pointed out in the comments. Now I don't have anything to work with. How can I guarentee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time?


texts:
I'm not sure how go about this question:
Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<c\cdot g(n)$.

$\mathcal O(2^n) < \mathcal O (n!)$.

I'm well aware how to prove $2^n < n!$ using induction, I just don't understand how  one is supposed to find a constant, etc. The only thing that springs to mind here is choosing $N = 4$, since that is when $2^n < n!$ begins to hold. If someone could clarify how I can apply the definition of Big-O notation to solve this, I would be greatful.


texts: How to prove properties about a specific modular arithmetic equivalence

texts:
Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific equivalence:
$$a^3 \equiv 5 \, (\text{mod } 7)$$
And I have a hunch that no $a$ exists s.t. this equivalence is true. Simulating it, it's clear that there is a pattern: 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0...

But I can't figure out how to formally prove 1. that this pattern is the actual pattern and as an extension, 2. that the equivalence above doesn't hold (it should be trivial if I can prove 1).

Can anyone help? Thanks so much.


texts:
my question is if my regular expression R is  1* that means the language accepted is {^,1,11,111,1111...}

in that case i don't understand the meaning what (R*)* means


texts: Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

texts:
MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem
is to find a subgraph with R vertices that is connected and maximizes the sum of the weights
(or values) of the R vertices.
CMCG Problem: The CMCG problem is the MCG problem with a constraint of having one predetermined (fixed) vertex included in the solution.
In 1 it has been stated (First paragraph, Section 1) that MCG is an NP-complete problem, which is proved in [3] (However I could not find the technical report [3] anywhere on the internet).
In 2 it has been "claimed" that CMCG is NP-complete (second to last paragraph, Section 3). But did not provide any proof.
I want to know (and see a proof, if possible) that if CMCG is NP-complete.
In 1 it has been shown that Steiner tree problem, which is NP-complete is a special case of the CMCG problem. Does it imply that CMCG is NP-complete?
[3]:Lee, H. F., and D. R. Dooly. The maximum-weight connected graph problem. Technical Report 93-4, Industrial Engineering, Southern Illinois University, 1993.


texts: Single-tape Universal Turing Machine time complexity

texts:
When studying the time-hierarchy and space-hierarchy theorems, the main idea is to use a simulation by the universal TM. It is mentioned that the time bound is increased by a logarithmic factor while the space bound remains the same.

I still can't figure out why, as most of the answers I've found to similar questions involve a multitape TM, while the complexity is determined by the bounds of a single-tape TMs and the time bound is known to strictly increase when converting a multitape TM to a single-tape one.

What am I missing here?


texts: How i can use Mathematical induction to prove CFG production?

texts:
If I have production $G_n$

$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_i \rightarrow a_j A_i \mid a_j\quad$   for $1 \le i$ and $i \ne j$

Prove $G_n$ is sub-productions from $2n^2 - n$
Prove $G_n$ is $LR(0)$ production from $2^n + n^2 + n$


texts:
Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too?

I'm confused with this spread of lower bounds and applicability of reductions.


texts:
Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$  and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations for problem $Q$ is polynomial many.

Question :  Can I say that $\textbf{DSPACE}(\log^2 n)$ is in polynomial time complexity class?


texts: Generate Evenly Distributed Pattern Based on Weights

texts:
I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements predictable manner.

For example: an array of 3 elements: $A_1 = 1, A_2 = 2, A_3 = 3$ and weights: $W_1 = 1, W_2 = 2, W_3 = 2$. This means that pattern will consist of 5 repeating elements. One example of this pattern: $1, 2, 3, 2, 3, 1, 2, 3, 2, 3, 1$ (each iteration of 5 elements has exactly one 1, two 2's and two 3's).

What I need is the name of this problem to search for suitable algorithms. Thank you!


texts:
I'm reading the CLRS book and there is a statement

  for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ time (e.g., when the input is already sorted). It is not contradictory, however, to say that the worst-case running time of insertion sort is $\Omega(n^2)$, since there exists an input that causes the algorithm to take $\Omega(n^2)$ time.

I just want to clarify some things to find that I understand this correctly. So does the last statement mean that the worst-case running time can't be linear function as we have $\Omega(n^2)$ for this? And another, can we say that the best case running time of insertion sort is $O(n)?$


texts: Complexity of find histogram bins vs convex hull

texts:
For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order.
Meanwhile What’s the complexity of finding the histogram bin edges of k bins on both axis ?
E.g.:
$$
X= ((x_0, a_0), (x_1, a_1), \cdots, (x_n, a_n)), x_i \in \mathbf{R}, a_i \in \mathbf{R}
$$
Finding the extreme points of the convex hull of $X$ vs Finding the edges for $K$ histogram bins for both $(x_0, x_1, \cdots x_n)$ and $(a_0, a_1, \cdots, a_n)$.
Which one is faster ?


texts: Run-time analysis of distributed network decomposition algorithm

texts:
I'm trying to understand the run-time analysis in the article [1].

The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their algorithm, they find that
$$T(l) \leq \hat O(p\log n)10^{\log_{p/2} l} \equiv f(l,p)$$
where $n$ is the number of nodes in the network, $l$ is the number of nodes in the input to the (recursive) algorithm and $p$ is a parameter.

Then they claim that the minimum of $f(n,p)$ is attained when $p=2^{\Theta(\sqrt{\log n})} = \hat O(n^{\epsilon(n)})$ with $\epsilon(n) = \frac 1{\sqrt{\log n}}$. This is the part that I don't understand. How do you minimize $f(n,p)$?

On the Complexity of Distributed Network Decomposition by A. Panconesi and A. Srinivasan (1996)


texts: How to find expected number of slots of a certain size k in hash table?

texts: If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a programming answer.


texts: Finding the dichotomy that maximizes information gain for a classifier?

texts:
Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let

$$H(C) = H(C, \Omega, P) = \sum_{i \in \pm 1} P(C = i) \log P(C = i)$$

be the entropy of $C$.

For a random variable $Y$ on $\Omega$ and $r \in \mathbb{R}$, define the level set $\{Y = r\} = V_r$, and define

$$H(C | Y) = \Sigma_{r \in \mathbb{R}} P(Y = r) H(C|_{V_r}, V_r, P_{V_r})$$

where $P_{V_r}(B) = P(B \cap V_r) / P(V_r)$ is a measure on $V_r$. $H(C|_{V_r}, V_r, P_{V_r})$ is the entropy of the random variable restricted to the the subset $V_r$, with the conditional probability measure.

As in a decision tree classifier, I want to determine the subset $A \subset \Omega$ that maximizes $H(C) - H(C|1_A)$. That is, I want to maximize the information gain. What is the "best" algorithm for doing so? What is the complexity of this question? Are there good probabilistic algorithms ?

Some computation allows one to reformulate this as finding the subset $A$ that maximizes

$$\sum_e \sum_{i = \pm 1} P(C^i \cap A^e) \log(P(C^i \cap A^e)) + \sum_e P(A^e) \log P(A^e),$$

provided we let $A^e$ mean $A$ or $A^c$, and $C^i = \{C = i\}$.


texts: Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a’s and an odd number of b’s

texts:
Does the question mean draw a Turing machine that takes input with any number of a's and any number of b's (eg. aaabbb, ab, abababab, etc.). The turing machine should only then accept or reject the input and should not be stuck in loop?

Example of a drawing to answer the question:


texts:
I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with.

Here is a example sentence showing how it is used:

  The loop is executed in time $O(n^2(e+n))$, which makes a polynomial delay for the output of the data.

I've tried searching a bit but I can only seem to find other papers and no definition.


texts: Mapping intuitionistic logic to the modal logic S4

texts:
In his famous Semantical Analysis of Intuitionistic Logic,
S. Kripke speaks of the "well-known mappings of intuitionistic logic
into the modal system S4". I'm not sure which mappings Kripke means.
One guess would be K. Gödel's "Eine Interpretation des
Intuitionistischen Aussagenkalküls" (translated into English as "An
Interpretation of the Intuitionistic Propositional Calculus". I don't have
access to either.)

Could somebody please point me towards a text that details these
translations?


texts:
I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions.
For eulerian, I can say that the graph has vertex with odd degree hence not eulerian, but how can I determine if they are hamiltonian or not?


texts: Is there a standard way to define a formal language transformer?

texts:
I'm about to study a system that takes words in a formal language $L$ and converts them into words in a different formal language $L'$. In other words: a formal language transformer. I was wondering if there is literature on formal language transformers, some standard way of studying, and defining them?

All I found are a 1995 paper by Cousot & Cousot on program analysis where formal language transformers are mentioned, but not really studied, and a 2005 presentation by Jaeho Shin that mentions the Cousot & Cousot paper. But maybe I'm looking in the wrong place or maybe I'm using the wrong vocabulary?

After all the effort in defining and studying the very many kinds of formal languages, it seems strange to me that nobody has bothered studying their transformations into each other.


texts: Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

texts:
We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size.

For example if the following matrix is given:

1000  0010
1101  0111
1101  0111
1101  0111

We should output 9 because the biggest rectangle we can get is with size 9. We are allowed to swap any columns infinite number of times and we are only requested to find the maximum size of the subrectangle.

Can we solve this problem faster that trying all possible permutations?


texts:
Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$.
To prove that Bubblesort works, we have to prove that it always terminates and that
$$A'[0]\leq A'[1] \leq \dots \leq A'[N-1].$$
Is there anything else that needs to be proven to show that Bubblesort actually sorts?

(I have found this question in a textbook about algorithms.)


texts:
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not understand why the approximate solution $$\sum_u w_u x^*_u \leq OPT$$
where $w_u$ is the weight to each vertex and $x^*_u$ is the approximate solution to the vertex cover problem and $0 \leq x_u^* \leq 1$
Can someone provide an explanation on how it is possible for the equation above ?


texts: Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

texts:
Is there any difference between saying
$ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $
with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $?
I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$
my understanding is that there is no difference between them and for $w = abaaabbb$ we have $ w \in L_1$ and $w \in L_2$ . but I have a feeling that maybe $w \notin L_1$, because it doesn't have the same $n$ for different $a^n b^n$.
Also, does the same apply for Kleene star $*$ too? for example if we have  $ L_3 = \{(a^n b^n)^m \mid n \ge 1, m \ge 0\} $ and $ L_4 = \{a^n b^n \mid n \ge 1\}^* $, Are $L_3$ and $L_4$ equal?


texts: What is the significance of the semi clustering formula in the Google Pregel paper?

texts:
Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula

$\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c - 1)}$

where

$I_c$ is sum of the weights of all the internal edges,
$B_c$ is the sum of the weights of all the boundary edges,
$V_c$ is the number of edges in the semi cluster and
$f_b$ is the boundary edge score factor (user defined between 0 and 1).

The algorithm is pretty straight forward, but I could not understand how the above formula was derived. Note that the denominator is the number of edges possible between $V_c$ number of vertices.

Could someone please explain it?


texts: Best combination of values pulled from a matrix

texts:
What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized?

For example, given the matrix:

$$A=\begin{bmatrix}0 & 1 &5 \\1 & 4 & 3\\2 & 7 & 0\end{bmatrix}$$

The solution is $\{A_{1,2}, A_{2,1}, A_{3,3}\}$, taking 1 from the first row, 1 from the second row, and 0 from the third row.

In the brute-force case, there are $n!$ possible solutions that have to be analyzed, so the ovreall running time is $O(n!)$, although are there any faster algorithms to solve this?


texts: Encoding algorithms better than or equivalent to Run Length Encoding

texts: I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but I would like to know if there are any other such encoding techniques or algorithms which can perform better than RLE or their performance is almost equivalent to RLE.


texts: Is the per-vertex error over a PageRank iteration monotonically decreasing?

texts:
It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.

However, is the same true on a per-vertex basis? I.e., from iteration t to iteration t+1, is the squared error of a vertex guaranteed to always decrease as it moves closer to its PageRank value? Or is it possible that the vertex squared error would ever increase?

This also seems to me to have some broader relationship with power iterations in general? Some explanation or proof with the answer would be appreciated.


texts: Turing-completeness, Conway's Game of Life and Logical Gates

texts:
I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life.
I'm not required to actually build up a Universal Turing machine in Life, but rather I'm supposed to provide a step-by-step explanation of universality of GoL (as well as the meaning of such result).
I decided to follow this path:

Introduce Turing machines, the notion of universality, and Universal Turing machines.
Introduce the notion of Turing-completeness and its relation with computational universality.
Using such notions and based on previous works and papers, show how Life can be used to simulate a Universal Turing machine.

(Is it a correct reasoning?)
The last point of the assignment asked me to prove the universality of Life by providing an implementation of logical gates in such model, and here come my doubts. I have read dozen of times in StackExchange forums, papers, etc. that the necessary conditions for a system to be Turing-complete are:

A form of conditional repetition or conditional jump (while, for, if and goto)
A way to read and write to some storage mechanism

But I never read anywhere about logical gates (or logical propositions in general). So, my questions are:

Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an alternative requirement?
Which is the correlation between Turing-completeness and logical gates?

Thank you in advance!
EDIT
Here is a link to the pdf file of the report that I submitted, thanks for your suggestions!


texts: Is this concatenation of two FA done right?

texts:
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider these two FA
$FA_1$

$FA_2$

if $r_1,r_2$ and $r_3$ are regex for $FA_1,FA_2$ and $FA_3$ respectively where
$r_1=(a^*b)^*$
$r_2=(a+ba)^*bb(a+b)^*$
then, mathematically, $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$
But $r_3$ turns out different when I actually concatenate $FA_1$ and $FA_2$ and use the new transition table (given below) for $FA_3$ to generate its regex ($r_3$) and the $TG_3$ (given below) and then simplify, $r_3$ becomes $(a+ba)^*bb(a+b)^*$ which is the same as $r_2$ (i.e. $r_1$ not prefixed). and since $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ can't be simplified into $r_2=(a+ba)^*bb(a+b)^*$
I am convinced that the problem is in the concatenation/transition table,
especially with the circular references to $x_1$ and $y_1$, which i don't completely get. That also would mean $TG_3$ iswrong.

The Transition Table:

$TG_3$

Now, it'd be very tedious to explain how i created the transition table, it's easier to figure out by looking at it. but key point i can't quite grasp the "$x_1$ and $y_1$ being connected" part
Sidenotes:
 - This is the only way to concatenating two FA that i know of. I am on a distant learning platform and it's quite low quality material, so links to proper methods are appreciated.
 - If you use another method, please keep in mind that the transition table, regex and the TG and all required
 - The TG looks like an FA to me (barely know the difference) but the site i used to generate it says it's a TG. what's the difference?


texts: Compression of Random Data is Impossible?

texts:
A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to the size of randomly generated data (the entrance cost would be \$100 and the contestant could choose the file-size).

I understand the result which shows it is impossible to compress all files of size >= N to a smaller size (http://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression).

But in the challenge question the idea is to only compress a single randomly generated file. A simple approach is to find $l$ the longest recurring substring in a file and substitute that with $s$ the shortest non-occuring substring which would give a saving of $l-s$ (since the decompresser only needs one l,s pair).

To obtain an approximation for the single shortest non-occurring substring as Usul pointed using the approximation for the coupon problem: $$E(t) = nlog(n) + \gamma n + (1/2n)$$

In this case $t$ is the number of possible substrings and using bytes for simplicity that's respectively:

275 megabytes for 3 byte strings ($n=256^3$)

91 gigabytes for 4 byte strings ($n=256^4$)

The probability of a recurring substring in the random data is equivalent to the birthday problem over the size of the random data,
$p = 1-e^{-((n^2)/2d)}$, for example at 91 gigabytes one can expect to find a recurring 9 byte substring with: $d=256^9$, $n = 91*1024^3$. $p \approx .636$

With $5000:100$ odds it should be possible to optimize a little more. Of course the cost of sed delimiters will be 3 bytes, if the cost of the command counts this method isn't enough to be successful - but this is without doing anything particularly clever.

Am I missing something (It would seem that the majority of random data should not be in fact incompressible)? What is the basis on which someone offers such a challenge and presumes it is entirely unwinnable for the player?

Edit (updated calculations up top as well): Also I think its possible to have a savings of precisely $l-s$ without having to pay for a delimiter. This is because it is known that substring $s$ did not exist prior to insertion - therefore the pair can be arranged with $sl$ contiguously written in memory and either the length of $s$ is known ahead of time (by estimating the shortest substring) or the next byte following $s$ in the file does not collide with the first byte of $l$ with at least probability $255/256$ (this gets better actually by having a choice which non-occuring $s$ to substitute for which recurring $l$).


texts: Figuring out the language accepted by a DFA?

texts:
I have been asked to give a formal description of a finite state machine. I have tried for over five hours to minimize it, to understand what gets accepted, and what gets refused, to no avail. I really am in need of help. If solving the problem does not seem reasonable, I would really appreciate any tips to attack this problem. The machine looks as such:

Things I've tried:
 I tried minimizing it, but the minimized version no longer accepts the same language.
 I tried looking at what gets accepted. I looked at how one can reach state q1 (through loops and what not), and how one can reach state q4 (through the same idea). When I tried this, I couldn't find a reasonable answer.
Example:

For q1: 4 ways to get to q1:

a run of a's,

loops of the manner (q1->q2->q3->q1),

loops of the manner (q1->q2->q4->q3->q1),

and loops of the manner (q1->q2->q4->q3->q2->q4->q1).

I would follow a similar thought process for arriving to q4. However, I can't seem to write a language that encompasses all of the possible combinations of these, along with the union of the two. I appreciate any help.
Thank you very much.

EDIT: My attempt at minimizing the state machine :

I look at the state diagram of the state machine, which looks something like the following:

The 0 equivalence looks like this:
[Q2 Q3] [Q1 Q4]

1 equivalence looks the same

This means we only have two states. I'll denote [Q1 Q4] by A, and [Q2 Q3] by B.
Initial and final state is A, and the other is B, which is not final.

A on a goes to A, A on b goes to B.

B on a goes to B, B on b goes to A.

resulting in the following state machine:

In the initial machine, bbb is accepted, but not in the minimized version.
Hence, I don't know where I went wrong.


texts:
Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$, and exactly $k$ times as a negative literal in $\phi$, where $\phi$ is a 3-CNF formula. The problem is then to decide if such a formula has a satisfying assignment.

  Is the $k$P$k$N-3SAT problem NP-complete?

In the $m$P$n$N-SAT problem each positive literal occurs exactly $m$ times in $\phi$, and each negative literal occurs exactly $m$ times in $\phi$, where $\phi$ is a CNF formula. It was shown in [1] that $2$P$1$N-SAT is NP-complete. This hints that the $k$P$k$N-3SAT problem is hard as well.

The $1$P$1$N-SAT is apparently easy, see a related question and answer here. Is $k$P$k$N-3SAT perhaps hard already for $k \geq 2$?

[1] Yoshinaka, Ryo. "Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete." Term Rewriting and Applications. Springer Berlin Heidelberg, 2005. 235-249.


texts: How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

texts:
I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

The solution must use hash-tables and advanced data structures including any variation of trees is not allowed.

I thought of the following:

1 Sort(A, n)
2   init B[2][sqrt(n)] //B[1][sqrt(n)] will hold the distinct elements
                       //B[2][sqrt(n)] will hold the number of occurrences
                       //of element B[1][k] in the original array A
3   for i<-0 to n
4       hash(A[i]) //the hash function will also update B[2][i] counter
                   //of occurrences of A[i] in A
5   Quick-Sort(B[1][sqrt(n)]) //quick-sort will also move
                                  //B[2][k] when B[1][k] is moved
                                  //so that they're aligned
6   count<-0    //keeps track of the next location in A
7   for i<-0 to sqrt(n)
8       for j<-0 to B[2][i]
9           A[count]<-B[1][i] //copy the sorted array into the original array
10          count++

In terms of space complexity it looks right to me since we're using $\sqrt n$ additional space for the hash table.

In terms of time complexity I'm running into problems. The quick-sort operation (or according to my understanding any optimal sort for that matter) on line 5 takes $\Theta(\sqrt n \log{\sqrt n})=o(n)$ which is not $\Theta(n)$.

How can I modify the sorting part/algorithm in order to arrive to $\Theta(n)$ complexity?


texts: How to represent calculable real numbers?

texts:
Suppose I want to do arithmetic without any loss of precision. Floats and doubles are inappropriate. I want to use dynamic memory allocations to store any real number obtained after a finite amount of finite operations (addition, subtraction, multiplication, division), starting from natural numbers without ever losing the slightest chunk of the result.

This means, I don't care at all about Pi or the square root of 2, because I have no finite method to obtain them in the first place. I don't want to apply any transcendental function either (cos/sin) because by definition they would never end.

Intuitively, it is obvious that 1/3 cannot be stored in base 2 or 10 using a finite amount of memory (0.33333...), therefore a correct representation would have to be at least fractional.

If this is possible, surely there must be some software out there who already does this. What would be the standard way to go? Preferably, I want a fast (hardware-accelerated) solution, for example using words as digits instead of bits.


texts: How to merge a lot of trees into one single graph?

texts:
I have a few different trees, which resemble what the AST that compilers often deal with.

For example:

tree 1

( (a, b), (c, d) )

Imagine that each tree split represents the function "add", then tree 1 simply says: add a and b, then add c and d, in the end, add the sum of these 2 sums as the final result.

tree 2

(  ( (a, b), (c, d) ), (e, f)  )

obviously, I can merge tree 1 into tree 2, because tree 2 is simply constructed by adding a sibling (e, f) to tree 1.

By doing so, I don't need to re-visit a, b, c , d twice, I can simply add e and f, and add the result to the result of tree 1, to get the result of tree 2.

If I have a lot of these kind of trees, with overlapping (redundant sub-subtrees),  is there  an algorithm that can automatically create a graph that covers all the computation in the most efficient way ?

PS: all the trees share the same set of leaf,in this case, a b c d e f. Some trees are taller (deeper), some are shallower.

PS2: tree are not necessarily binary trees. A tree could have multiple

PS3: there could be a tree like ( (a,b), (g,h) ), i can still be partially merged with tree 1


texts: Trouble finding loop invariant for this while loop

texts:
I'm having trouble coming up with an invariant for proving partial correctness of this function.

def f(A):
    # Pre: A is a list of integers
    # Post: Returns true if and only if there is an even number of positive
    # numbers in A

    even = True
    i = 0
    while i < A.length:
        if A[i] > 0:
            even = not even
        i = i + 1
    return even

So far, I have something like:

i <= A.length and (even == True or even == False)

However, I don't really know whether this is correct or, if it is even, if I can prove that it is inductive. I don't really know how to start the proof and was just looking for some help to point me in the right direction.

Thanks.


texts: What is an example of a problem that is in NP - P, but not NPC?

texts:
Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true.

What is an example of a problem that is complex enough to be in $NP - P$, but doesn't allow every $NP$ problem to be reduced to it in polynomial time?


texts: Complexity of edit distance with block operations

texts:
Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$.  The operations are:

Insert a single character into $P$
Delete a single character from $P$
Substitute a single character in $P$ for another one
Move an entire substring of $P$ to another location in $P$

What is the time complexity of this problem?


texts: Working out the connectives (And, Or, Not) in a Truth Table that has the outputs

texts:
I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g

P | Q | Output
1 | 1 | 1
1 | 0 | 0
0 | 0 | 0
0 | 1 | 0

I need to find the logical operators and connectives (and, or, not, implies etc.) that is equivalent to the output.
Please guide me through the steps or teach me how to work out how to do this. Thanks.


texts: Looking for name of siblings-first-depth-second traversal order

texts:
I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name.

The requirements of the algorithm are:

it visits the parent before the children.
it visits all the children in one group.
it is otherwise depth-first.

I basically modified a pre-order to visit the siblings all together, before going down to the child of the first sibling. Note that this is not breadth-first.

Here is an example of the traversal order:

As you can see, in this tree, the traversal would be H, D, L, B, F, A, C, E, G, J, N, I, K, M, O, and grouping for siblings: (H), (D, L), (B, F), (A, C), (E, G), (J, N), (I, K), (M, O).

Some things to ponder:

I think one can also view this as a pre-order traversal of the "dual" of this tree, where the dual nodes are representative of each group of siblings.
Notice the z-shapes. It is like a "z-order-traversal", an analog to a z-order-curve, but for tree traversal. It has the similar property of traversing children together, just like a z-order curve will visit the siblings of the finest level of a full quadtree.

So, what is the name of this traversal order?


texts: Tag storage when using HBM as an L4 cache

texts:
I'm reading through Computer Architecture: A Quantitative Approach, Sixth Edition, and I'm trying to understand the issues surrounding tag storage in using HBM as an L4 cache. The primary concern mentioned in the book is "where do the tags reside?", since the sheer capacity (1 GiB) of the HBM with a small block size (64B) results in a large amount of tag bits (96MiB).

The book first suggests that the tag data might live outside of HBM, in a higher level of the memory hierarchy - except there is not enough SRAM capacity to store them, even in a modern L3 cache. It then goes on to suggest that keeping the tags in HBM as a solution to this. However, in L1-L3 SRAM caches, don't the tags reside in each of the caches themselves? Why would HBM be any different? Is it because we're somehow unable to perform hit detection/tag comparison on the HBM DRAM chips themselves (as is done in SRAM caches), so they need to be processed outside of HBM?


texts:
Time complexity of travelling  salesman problem is $O(n^2*2^n)$ using held-karp algorithm. Now, if don't use dynamic programming and solve it using the recursive procedure, time complexity is still $O(n^2*2^n)$. I know there are overlapping of subproblems and there will be less computations but the time complexity is not getting better with the use of dynamic programming. Moreover, space complexity using held-karp is also $O(n*2^n)$ which is very large. We mostly use dynamic programming when we can improve the time complexity.

So, should we use dynamic programming here?

Here is the recursive approach..

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}


texts: Complexity of finding factors of factors of N number

texts:
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j+=i)
        for(int k = j; k <= N; k+=j)

How to express this mathematically to calculate the complexity of the above code. I guess, its complexity is $O(N\log\log N)$ but couldn't prove it mathematically!


texts: Binary Search Tree – Number of comparisons when element is not found

texts:
I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree.

For example, to search for element "6", would it take 5 comparisons to search for this element?

My understanding is:

Compare root (Not found - move left)
Compare left node (Not found - move left)
Compare left node (Not found - move right)
Compare right node (Not found, move right)
No right node (6 does not exist)

Is my understanding correct? Would it take 5 comparisons to attempt to search for 6 in this BST?


texts: Prefix computation used for lexical analysis?

texts:
I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms.

Several lists of applications of prefix computation include lexical analysis (tokenizing), but do not cite a source for that.  I have failed to find any other reference to it being used that way.

Where has any description of the use of a prefix computation for the purpose or lexical analysis been published?  (Or, what was the origin of this misinformation?)


texts: In a NPDA if the stack is empty, where the start/end state are the same can you go again

texts:
Thoughts

I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I am back in q0 and the $ is removed from the stack I stop


texts:
Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y value for a given x value using the provided points as fix points for a piecewise linear interpolation.

Caveat: The x-axis is cyclic, so it wraps around at a certain known value.

I'm searching a neat algorithm (or way to write this down) which can do this interpolation, so take an x value on the cyclic x-axes and compute the y- value using piecewise linear interpolation.

Example: Given FIX_POINTS = [(10, 50), (90, 100)], and a "cyclic interval" (so the value at which the x axes wraps) of 100, the interpolation would lead to the following results:

  interpolation(10) = 50 # No interpolation necessary, directly on fix points
  interpolation(90) = 100 # Same

  interpolation(50) = 75 # Normal Interpolation
  interpolation(0) = 75 # Wrap around interpolation
  interpolation(1) = 72.5 # Same
  interpolation(99) = 77.5 # Same

I'm not too curious in the actual programming, I'm searching for a way to write this down nicely. Maybe there is even an existing implementation for this? I'm having troubles asking google for the lack of search terms.

I implemented it myself, but it got a lot of code, so I'm in search of something simpler: https://gist.github.com/theomega/9782be548fd452e1f1469757387b35e4 . This implementation also is far from optimal on the computational side (scanning over the array).

I'm not sure if this is the stack exchange for this. Feel free to point me in a different direction.


texts: Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions

texts:
I'm learning for the exam and have problems with this task:

  Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an equivalent NFA without $\epsilon$-transitions with the same condition number. And then determine the maturity of the algorithm. The algorithm should have a running time $O(|Q| · |\delta|)$ where
  $$|\delta| := \sum_{\substack{q\in Q\\ a\in\Sigma\cup\{\epsilon\}}} |\delta(q,a)|$$


texts: Winning strategy for a given game on graphs

texts:
The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h_1$, then player 2 responds with a villain $v_1$ who has played in a movie with $h_1$. Then player 1 responds with another hero $h_2$ who has played in a movie together with $v_1$, and so forth. Each hero and villain can be used at most once. The first player that can not name any character (available heroes/villains do not have a common film with the last choice of the other player), loses the game. Player 1 always starts the game.

The input is a set of heroes $H$, a set of villains $V$ ($|H| = |V| \geq 1$) and a family of movies $M$, where each movie is a set of heroes and villains who appeared in that movie.

The question is: Can you, based on $H$, $V$ and $M$, decide which player wins the game assuming both players are playing optimally?

Example:

Given the following data: the heroes are Iron Man, Captain America, Thor and Spider-Man. The villains are Whiplash, Ultron, Thanos and Vulture. The movies are Avengers: Infinity War (stars Iron Man, Captain America, Thor, Thanos and Spider-Man) and Spider-Man: Homecoming (stars Iron Man, Vulture and Spider-Man). Can you decide which player has the winning strategy?

My approach is to use maximum bipartite matching to find out which player has the winning strategy, because we can split the data in two sets, namely $H$ and $V$ and have relations between those two sets. The Hopcroft-Karp algorithm can take two of such sets and find out the maximum cardinality. Please correct me if I'm wrong: in the cases in which there is a perfect matching, player 2 wins and otherwise player 1 wins. Whenever there is a perfect matching, it means that player 2 has always had an answers to the hero that player 1 named.

How would you solve this? Is there a better, more efficient solution than some maximum bipartite matching.


texts: Rice's Theorem - usage on $DFA$ or $LBA$

texts:
I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.

However I am not sure about one question -

Can I use Rice's theorem on languages which are defined on $LBA$ or $DFA$? For example, the following language -

$$ALL_{LBA} = \left \{ \langle M \rangle \mid \text{$M$ is an LBA and $L(M) = \Sigma^*$} \right \}$$

Since an $LBA$ is a "private case" of a turing machine, I am not sure I can use Rice's theorem here to prove the language is undecidable.


texts:
Not really sure if this is an exact CS question. I'm reading the Patt/Patel Introduction to computing systems Powerpoint presentation and I don't understand about the program counter and instruction register format in LC-2.

On the memory pages section in chapter 5, it writes there:
"Direct mode addressing gets page number from PC[15:9] and page offset from IR[8:0]."
My question is, I don't understand why the format of PC and IR is in [x:y], can anyone explain it to me? I read on Wikipedia and it says that it should be base + offset, but why does the base and offset both have 2 separate values?

Thanks.


texts: Proving that Turing decidable languages are closed under reversal

texts: I need to prove that Turing decidable languages are closed under reversal. I have no idea on how I would prove this. Any suggestions or clues?


texts: Cycles in undirected graph: reducing to minimum

texts:
I am working on the problem of finding cycles in an undirected graph.
I made up my solution by first detecting if any cycles are present with a DFS algorithms and detecting any backtracking, and second, recursively explore all the found backtracked edges until I find the starting vertex.
The problem I have is that this approach gives additional cycles, and I don't know how I can remove them in a post-processing step.

The classical way is to represent the cycles as binary vectors, and then XOR them by pairs: if the result is equal to another cycle, then the latter can be removed.

For example, consider the following graph, that obviously has only two basic cycles:

Exploring all possible cycles will give these 3:

c1: 1-2-3
c2: 2-3-4
c3: 1-2-4-3

Converting to binary vectors:

edge | c1   c2   c3
1-2  | 1    0    1
1-3  | 1    0    1
1-4  | 0    0    0
2-3  | 1    1    0
2-4  | 0    1    1
3-4  | 0    1    1

Computing $c1 \oplus c2$ will give 110011, which is equal to c3, so we can remove c3.

But in many situations, this is not enough.
For example, consider the following graph, having $v=4$ vertices and $e=6$ edges.

A well know result states that for a single-connected graph  with $v$ vertices and $e$ edges, the number of cycles will be $c=e-v+1$, so we have 6-4+1=3 cycles in this example.

But by proceeding with my approach, I get the following 4 cycles:

c1:   1-2-3
c2:   1-2-4
c3:   1-3-4
c4:   2-3-4

If I convert them to binary vectors and XOR them, I am not able to remove the additional cycle.

edge | c1  c2  c3  c4
1-2  | 1   1   0   0
1-3  | 1   0   1   0
1-4  | 0   1   1   0
2-3  | 1   0   0   1
2-4  | 0   1   0   1
3-4  | 0   0   1   1

$c1 \oplus c2 = 011110$
$c1 \oplus c3 = 101101$
$c1 \oplus c4 = 110011$
$c2 \oplus c3 = 110011$
$c2 \oplus c4 = 101101$
$c3 \oplus c4 = 011110$

All these computations produce binary vectors with 4 '1', while all the initial cycles have 3. Thus I can remove none.

Note that this not only a matter of a (single) one additional cycle. For more complex graph (say, Petersen graph for example), I get more than one additional cycles.

I am looking for any ideas on how to remove the additional cycles.

Edit: As suggested in answer, I have build the incidence matrices for the two examples above:

             A1                A2
vert:      1 2 3 4           1 2 3 4
       1 | 1 1 0 0 |     1 | 1 1 0 0 |
       2 | 0 1 1 0 |     2 | 0 1 1 0 |
edges: 3 | 1 0 1 0 |     3 | 1 0 1 0 |
       4 | 0 1 0 1 |     4 | 0 1 0 1 |
       5 | 0 0 1 1 |     5 | 0 0 1 1 |
                         6 | 1 0 0 1 |

Edit 2
For A2, I computed the Reduced Echelon Form (that I understand is useful to find the solutions to $AX=0$):

$A2 = \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}$

But this stills end up with a null vector...

Edit 3: I come back to this question as I still didn't get it.
The answer from @Yuval Filmus suggest to solve $A x = 0$ to find the cycle basis. But what exactly represents the different $x_i$ values?
Because if I make a parallel with linear algebra, then using the matrix $A2$, this would mean I need to solve this:

$
\begin{aligned}
x_1 + x_2 &= 0 \\
x_2 + x_3 &= 0 \\
x_1 + x_3 &= 0 \\
x_2 + x_4 &= 0 \\
x_3 + x_4 &= 0 \\
x_1 + x_4 &= 0 \\
\end{aligned}
$

Beside the fact that the solution to this is $\{0,0,0,0\}$, I don't understant what $x_i$ represents.


texts:
I'm pretty new to the PDA topic.

How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$

I've tried all the possibilities, but I still somehow end up accepting all words.


texts: Minimum number of tests to identify subset of modules that trigger a bug?

texts:
I have an ordered set of $M$ software modules compiled together. The interaction of some  $N$-tuple of these modules is causing a bug when the program is run.

I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests.  Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$).

$N$ is known ahead of time.

For $N=1$, I can efficiently identify the culprit in $\log_2(M)$ tests by binary search.

For other values of $N$, what approach can I take to identify the $N$ culprits?


texts: Who conceived the concept of Discrete Event Simulation, and when?

texts:
I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of discrete-event simulation.

However, I'm unable to verify this as the origin of the term.

Is there further historical information on this?


texts: Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?

texts:
I can compute this easily in the case that $xy < 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$.

I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but I'm not sure where to go from there.


texts:
I read that each segment is 64KB,but how?
If you have address ABCD:EFGH , then 1 segment is 16B if it is addreses by bytes.
How do they don't overlap?
Example:
 0000:0010 = 00010
 0001:0000 = 00010 , is is same address.


texts: Discrepancy between process execution time and CPU speed (lost cycles)

texts:
I'm not sure if this is on topic, but I've seen some hardware related questions here so I'll post it here anyway. If it's off topic I'll take it off.

Compile this C code:

int main() {
  unsigned long long int i;
  for (i = 0; i < 30000000000ull; ++i){}
  return 0;
}

with gcc cycleTimer.c. Then run /usr/bin/time -f "%E %P" ./a.out.

I get the following output:

1:17.04 99%

Meaning the process takes 77 seconds to complete and uses 99% of a CPUs time. Running cpufreq-info during the process gives

current CPU frequency is 2.30 GHz

for all four cores. Now create the assembly instructions for cycleTimer.c with gcc cycleTimer.c -S, and we get the following assembly code:

        .file   "cycleTimer.c"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    $0, -8(%rbp)
        jmp     .L2
.L3:
        addq    $1, -8(%rbp)
.L2:
        movabsq $29999999999, %rax
        cmpq    %rax, -8(%rbp)
        jbe     .L3
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

From this, we can see that on every iteration of the loop, four assembly instructions are being run. Therefore, to work out the instructions per second, we do (4*30000000000)/77 = 1558441558 which is 1.6 GHz, much less than 0.99*2.3 which gives 2.28 GHz of the processor that we are actually meant to be using.

Why is there such a big discrepancy? The kernel is saying that 99% of the CPU is being used. Are there any other hidden instructions being computed by the CPU we don't see with gcc -S? Have I made a mistake somewhere?


texts: How does DFS produce MST and All pairs shortest paths in unweighted graphs?

texts:
I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me.

For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

My doubt: Is there anything  "Minimum spanning tree" for unweighted graph. I mean after all it is unweighted so what is sense of MST here? And I completely don't understand how DFS produces all pair shortest path. Would anybody mind elaborating this a bit.


texts: Visual programming tools, why don’t they work with the AST directly?

texts:
I've found several open source visual programing tools like Blockly and friends, and other projects hosted at Github, but could't find any that work directly with the abstract syntax tree.

Why is that?

I'm asking because once I discovered that every compiler out there has a phase in the compilation process where it parses the source code to an AST, it was obvious to me that some visual programing tools could take advantage of this to give the programer ways to edit the AST directly in a visual way, and also to do the round trip from source to node-graph and then back again to source when needed.

For instance one could think that from the JavaScript AST Visualizer to an actual JavaSript visual programming tool there isn’t too much of a difference.

So, what am I missing?


texts: What is the difference between classical crypto and post-quantum crypto?

texts: Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be needed to change?