texts: Why is the OS design able to reduce power consumption?

texts:
I have read that OSes like Android and iOS are somehow optimised to improve battery life.

My understanding is that a CPU executes a certain number of operations in a certain time, so I would think that you can speed up applications by reducing number of operations required, but since the CPU will still do x operations in y time, that should not affect power?

Also, if a process occupies more RAM, does it consume more power?


texts: Ordering of operations in a DAG of git commits

texts:
Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug
Summary of the current algorithm and shortcomings
git-bug is a distributed bug-tracker that embed in git, the distributed version control system. To do so, bugs are stored in the native git data structure (commits and branches). Each bug has its own branch and adding commits to it will evolve the bug state. This allows using git as both a database and a transport, in the sense that users can push/pull those branches to distributes updates and collaborate with each other.
More details can be found in this document: https://github.com/MichaelMure/git-bug/blob/master/doc/model.md
Now to deal with the distributed nature of this system and allow merges, the state of a bug can't be stored as-is. Instead, it's stored as an ordered series of operations: adding a comment, changing the title ... When reading a bug, the final state is "compiled" by applying those operations in order to an originally empty state.
I believe (but don't quote me on that) that this is a form of Operational Transformation (OT).
In reality, multiple operations can be stored in a single git commit but for the purpose of this conversation, let's assume that one git commit stores exactly one operation.
To make my life a bit easier at the beginning of this project, I reduced the complexity of this problem by imposing that the series of commit holding the operations would have to be linear, which make the ordering of the operations trivial: the order of the commit implies the order of the operations.
This purely linear restriction has a major implication: when fusing[1] together with two git DAG when doing a git pull, the equivalent of a git rebase has to be used. The commits of one diverging branch are reapplied on top of the other, which means that the data structure is not actually immutable. Not only this is problematic if commits are signed, but I'm also suspecting this can prevent the commits to reach a stable ordering when there is no central server acting as "source of truth". If three users A, B, and C are pulling and rebasing commits in a cycle A->B->C->A, I suspect they will never reach a stable ordering.
Another way to do things would be to use the equivalent of git merge: the diverging branches are fused together with a new commit having both branches as parents and we end up with a DAG. Although and this is important, in the normal git behavior this merge commit holds the fused state. For git-bug, each operation is disconnected from the others, so the merge commit would hold no fused state, just that the branches fused.
The actual question
I'm looking for an algorithm capable of doing this ordering of commits in a git DAG using git merge, in the most stable way possible.

using git merge: git merges are allowed, possibly rebase as well if necessary
most stable way possible: in a perfect world, the operations should be ordered by their real-time creation. Obviously, this is not fully possible in a distributed system, so the goal is to get a logical order as close as possible, despite concurrent editions and merges. Thankfully, bugs in a bug-tracker are slightly malleable and will retain the user's intent even if the ordering is slightly wrong.

As you may have guessed, I'm a bit out of my depth here so, short of an actual algorithm, any pointers for theoretical ground or possible solutions would be helpful.
Things I considered

storing in each operation/commit the reference of the ancestor at the time of the creation
using some form of logical clock, stored in each commit
some sort of topological ordering
a combination of those?

[1]: I'm avoiding "merge" here to avoid confusion, it's not the git merge.


texts: Studies of file access patterns in embedded systems

texts:
I am considering what elements an operating system for Network On Chip systems might have and the issue of file systems looms large. NoCs have an embedded heritage, and their domain of use (at least initially) is likely to be similar tasks to embedded systems.

But I cannot find any studies of embedded system file access patterns - there are a number of published studies on scientific and super computing file access patterns I have been able to read but nothing on embedded systems.

Can anyone point me to some good papers on this?


texts:
I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:

public boolean isAnagram(String firstWord, String secondWord) {
    if(firstWord == null || secondWord == null || firstWord.length() != secondWord.length()) {
        return false;
    }

    Map<Character, Integer> charCounts = new HashMap<>();
    for(char c1 : firstWord.toCharArray()) {
        if(charCounts.containsKey(c1)) {
            int currentCount = charCounts.get(c1);
            charCounts.put(c1, currentCount + 1);
        } else {
            charCounts.put(c1, 1);
        }
    }

    for(char c2 : secondWord.toCharArray()) {
        if(charCounts.containsKey(c2)) {
            int currentCount = charCounts.get(c2);
            if(currentCount == 0) {
                return false; // not an anagram if it has more of one character than the first word
            }
            charCounts.put(c2, currentCount - 1);
        } else {
            return false; // not an anagram if it contains another character
        }
    }
    return true;
}

It's a point of contention because the space used by the method doesn't exactly depend on the input, but a characteristic of the input, namely the number of unique characters in the firstWord.

Let's say m is the length of the first word, and n is the length of the second word. Let's say that k is the number of unique characters in firstWord.

Some of us think that the space complexity is O(k), essentially the number of entries in the map. That is: k is the upper bound on the space used, because k will be the number of entries created in the map, one entry for each unique character.

Some think, it's basically just an O(1) space complexity, because even though the map is dynamically sized in reality, we could also think of it as O(1) and actually just pre-populate the map with counts of 0 for all possible alphabet. The argument against this is that you don't know "all possible alphabet" when latin alphabet is 26 characters, but ascii has 128, and unicode has > 137,000, and other character sets, who knows?

Others argue that we should take into account only m, the length of the first word. In some cases m < k, because it is shorter than k. In the worst case, m > k (because of duplicate characters) and, in very long strings, m will determine the choice of the type of the map's values. e.g. The code given uses "Integer" or 2^32 size counts, but you may need to go to 2^64 or even larger on very long strings. At any rate, this argument contends that m is a factor in how the algorithm scales and so it should be O(m).

A derivative of this last argument is that, on average, for any given character, there are m/k occurrences of that character in the string and the size of a value m/k in computer space is log(m/k), therefore a tighter  Big O is O(k * log(m/k)).

Does anyone have any thoughts?


texts: Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?

texts:
Given: A list of $n$ integers $x_1,x_2,\dots,x_n$ and an integer $k$.

Determine: Is $\sqrt x_1 + \sqrt x_2 \cdots \sqrt x_n \le k$?

Question: Is there any polynomial time algorithm for the above problem? If yes, give an algorithm; otherwise prove it.


texts: I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is that? Just because we could write a non-deterministic algorithm in polynomial time? Can't we do that for every problem?


texts:
This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he put up a basic example, but this one has lots of recursive calls in it.

I know that the first part len(lst)$ \leq 1$ will be linear time because of it will just return whatever in the conditional. How do I tackle the rest, and ultimately come up with the recursive $T(n)$? The question is below:


texts:
Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results.

The chain starts at State x, a uniform distribution of set S = {1,2,3,...30}. If the current state is page P, select page Q uniformly from the union of the results from each search engine. If the rank of Q < rank of P in 2 of the 3 engines that rank both P and Q, move to Q. Else, remain at P.

This results in a number of pairwise comparisons being carried out. result2 is compared with result1 and a count is made of each time result2 ranks better than 1. The results are sorted by the results of the pairwise comparisons, with the lowest score ranked first. e.g.

Engine Rankings:                       Pairwise Comparison:
         eng1   eng2   eng3                    result1  result2  result3  result4  result5
result1   1      2      2              result1    0        1        0        0        1
result2   4      3      1              result2    2        0        1        2        2
result3   2      4      5              result3    3        2        0        1        2
result4   5      5      3              result4    3        1        2        0        1
result5   3      1      4              result5    2        1        1        2        0

The problem with this example is, if we add the total of each row in the pairwise comparison, we get {2,7,8,7,7}, leaving 3 different results with the same score. I'm wondering if there is a method to further sort these results in order to refine the results so that I'm not left with a number of results that have the same score? I've seen Keminization but I can't see how this would apply? Can someone please give me some guidance?


texts: Perform the following 8-bit two's complement arithmetic operation

texts:
How am I supposed to perform this subtraction?

For instance: $01110000_2−11101011_2$

$01110000_2$ has a positive sign, so there is no need to perform two's complement. $11101011_2$ has a negative sign, so I need to perform two's complement.

Two's complement for $11101011_2$ is $00010101_2$

Finally, I must perform the subtraction $01110000_2 - 00010101_2 = 1011011_2$


texts:
I need to develop algorithm for one task.

I have 500 types of object, each type is represented by a group of qualifiers (about 20 for each type, the same qualifier can be used for different types), where qualifier is a simple predicate (but calculation of the predicate can take some time, as you have to check data in data base). When all qualifiers for particular type return true then object has such type.

For now I just came up with idea to use cache and go through all types trying to do qualification. For each type firstly I go through predicates without calculation and check that no of them failed before if some failed I skip the type, otherwise I go through qualifiers and do calculations (for each predicate I take data from cache if I did the same qualifier before).

I think may be there are some data structures for such task, or common approaches how to do that better.

A small update to the question. The classification data I have, has special structure, like not all attributes of the object mentioned for each class.

For example
Type European transaction:

Country one of DE, FR, ES
Color : Blue
Serial type: 2
Currency : EUR

Type UK transaction:

Country: UK
Serial type: 1

It just example out of my head, each object has much more attributes. The main point here that some attributes can present for some objects but not for others. So if we create data set on the objects to build qualification tree, the value of such attributes could be marked as ANY value, that way it's impossible to do qualification, since we can get to the branch where we have two ways to go.

Thanks.


texts: Parsing CFLs (simulating PDA vs CYK algorithm)

texts:
We can simulate the PDA and parse the language with the following operations (vaguely):

  Read the input symbol and top of stack - $O(1)$
  Check all the transition rules (must check all for non-determinism) - $O(|Transition rules|)$
  Update the stack and the set of states - $O(1)$

Due to non-determinism, the problem size increases and so does the complexity.

However, for deterministic context free languages, the complexity of this algorithm seems to be $O(n|Transition rules|)$ which is linear.

The complexity of CYK algorithm is $O(n^3|G|)$. From various sources it seems that the complexity of CYK algorithm is polynomial for deterministic languages.
http://people.csail.mit.edu/madry/docs/linear.pdf

$|Transition rules|$ has a maximum value of around $|G|$ I think.

So, is this method really better than the CYK algorithm for deterministic CFLs or am I making a mistake in my analysis? If so, then where?

I'm assuming that $|G|$ = Number of production rules in grammar.


texts:
As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga coins. I did some research (i.e. googling), found some information, and most notably a paper which describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I succesfully managed to implement Round Robin, BFD and BFDU algorithms and with that I managed to solve the tasks (yay!). However I also wanted to implement DQQD(U) algorithms described there, and I cannot get the implementation right.

Pseudocode for BFD presented on page 9 is rather clear and I managed to implement it without any special problem. Adding one small update step I also got BFDU right. But with pseudocode for DQQD on p. 15, I always get to the point that first iteration seems to produce expected values like in example table, but things start to go wrong on second iteration.

Pseudocode as given in the paper:

Either I am getting things mixed up because of inconsistent indexing used in the paper (1-based for vector A, 0-based for other stuff), or
I am misinterpreting some ambiguous symbols (for example, w mutates through the iteration, and Qw can mean different things, depending on whether we use Qw determined on the beginning of the iteration, or we use different Qw every time w changes), or
there is a typo or some other mistake somewhere in the pseudocode, or
everything is OK there and it's just my mathematical ineptitude getting in the way. Unfortunately, I am not a mathematician, and theoretical basis for the algorithm is beyond my comprehension skills :( Maybe I should just GIT GUD?

I already tried changing here-or-there, but it was just a guessing game. I tried to find other implementations of DQQD, especially one in Mathematica, but they do not seem to be available. I also do not need to have the code written for me. All I need is someone to take a peek at pseudocode of DQQD in mentioned paper, and, if possible, try to implement it or verify it in any way if it's correct and I suck, or if it indeed has some typos, mistakes, or other issues.

Next step: overkilling the problem with FROBENIUS NUMBERS BY LATTICE POINT ENUMERATION :)


texts: For a given k-DNF formula, what is the size of the formula for the purpose of complexity?

texts: I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $n$ in the time complexity would refer to in this case (that is that I don't know how the "size" of a k-DNF is defined, nor was it defined in the assignment). Is it the number of clauses, the number of literals (distinct or nondistinct?) or something else? I think they should all be equivalent for the purpose of complexity, but I would rather adopt the standard convention.


texts: Adding a node between two others, minimizing its maximum distance to any other node

texts:
We are given an undirected graph weighted with positive arc lengths
and a distinguished edge $(a,b)$ in the graph. The problem is to
replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a new
node, such that the length of the path $(a,c,b)$ is equal to the
inital length of $(a,b)$, and such that the choice of the length of
$(a,c)$ minimizes the maximum distance of node $c$ to any other node
of the graph.  Is there any graph-theory based algorithm that can solve such problem rather than brute force?

Actually, the existence of the original edge $(a,b)$ is not
essential. Only the end nodes $a$ and $b$, and the length matter.

For example we have a graph:

1 2 10
2 3 10
3 4 1
4 1 5

In every line the first two values indicate the node number, and the 3rd one is the corresponding edge value. Now I want to find a new node $c$ between nodes 1 and 2. The answer gives
a node $c$ at distance 2 to node 1 (and distance 8 to node 2). The
distance of node $c$ is 2 to node 1, 8 to node 2, 1+5+2=8 to node 3, and
5+2=7 to node 4. The maximum distance is 8, which is minimal for all
possible choices of the length of $(a,c)$.


texts: Looking for a subjective ranking algorithm

texts:
I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order from best to worst, in what way should the judge taste the chili from the individual bowls to complete the task of ranking with as small a number of repeat tastings of the same bowl as possible? The initial approach I thought of was as follows. I've named the bowls A - J:
initial order:

A, B, C, D, E, F, G, H, I, and J

Taste A then taste B. If B is better than A, switch them around in the order.
Judge thinks B is better than A:

B, A, C, D, E, F, G, H, I, and J

Taste A then taste C. If C is better than A, switch them around in the order.
Judge thinks C is better than A:

B, C, A, D, E, F, G, H, I, and J

Already though there is a problem. What if C was also better than B? We could complete the process then repeat again but its not clear to me how many times the process would have to be repeated in order to have everything ranked properly. What kinds of algorithms are these? Where can I learn more about them. Thanks.


texts: Class diagram of an Hotel Management System

texts:
I am given the following system description :

Consider a hotel management system to manage a group of 5-stars
hotels. If this system is modelled using OOP methodology, and the
classes are identified as Hotel, Trip, Room, VIP Room, Regular Room,
Suite, Customer, Payment, Cash_Payment, Credit_Debit_Payment,
Reservation.

Now I need to draw its UML class diagram, here is my solution :

I have related the customer class indirectly with the Hotel using the reservation class which is related to the Room class and Trip class and both of them are related to the Hotel class is this a valid solution ?. Also, did I miss any composition or Aggregation relationships? because I am not sure that is there is a "part of" relationship between reservation class and payment , room  and trip classes? Please, someone, clarify this confusion for me ! Finally, are these multiplicities right? I am just practicing some problems for class diagrams to understand it and get ready for my exam, so please help me.


texts: Pancake Sorting Graph Recursive Definition

texts:
I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough copies of the graph where n=3 with additions of 4 in certain places (where, and how is this defined?). But these copies aren't exact, and I can't find any detail on Wikipedia except for that it is indeed recursively defined. I'm asking with a view possibly to be able to generate a graph algorithmically for n>=4 recursively.

Here is a graph for n=4 (so there are 4! / 24 possible configurations of pancakes, and thus 24 nodes in the graph). Here it is for n=4, on this Wikipedia article: https://en.wikipedia.org/wiki/Pancake_graph.

See this Wikipedia article for more on Pancake Sorting - https://en.wikipedia.org/wiki/Pancake_sorting.


texts: What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?

texts:
I was learning about polymorphic types but I couldn't understand the notation, can someone explain it means (context cs421 UIUC):

$$ \forall \alpha_1, \dots , \alpha_n . \tau $$

its supposed to be a type but I have no idea what it's suppose to mean.

Perhaps writing some of my thoughts or questions might be helpful in clarifying what I'm confused about:

Why is there a dot separating the quantifier and the type
How does this relate to normal FOL? e.g. if I had $$ \forall x \phi(x) $$ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true (assuming the whole expression is true, which it may not be but whatever)
Is $\tau$ a function of the (meta?) variables $$ \forall \alpha_1, \dots , \alpha_n $$?
What do $$ \forall \alpha_1, \dots , \alpha_n $$ stand for?
Are $$ \forall \alpha_1, \dots , alpha_n $$ meta-variables? What is their domain?
Could I have a couple of concrete examples of what they are
I am still confused what entails a monomorphic type vs a polymorphic type. In slide 54 they define that a monomorphic type can be a "type variable $\alpha, \beta, \gamma, \delta, \epsilon $". However, I find that very very confusing because consider the value $e$ with type $\alpha$ ($e:\alpha=<e,\alpha>$). What confuses me is that $\alpha$ can be ANY value, so doesn't that mean $e$ is polymorphic? How is that different from specifying the type value pair for that expression $e:\forall \alpha. \alpha$. They both seem the same to me. This is confusing me a lot. Whats the difference?

I think the lectures assume the definition of them its clear but it really isn't. Can I have a more formal specification of it?

For example when we are told $$x:\tau$$ as a notation its not clear at all it really just means the tuple $$ \langle x, \tau \rangle$$ (until I looked it up at Wikipedia). But Wikipedia didn't save my day for this question, unfortunately...

Crossposted: https://www.quora.com/unanswered/What-does-forall-alpha_1-dots-alpha_n-tau-mean-formally-as-a-type


texts: Why is the commit phase in PBFT necessary?

texts:
I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that

PREPARE phase ensures fault-tolerant consistent ordering of requests within views
COMMIT phase ensures fault-tolerant consistent ordering of requests across views

Some tutorial glosses over that

  The PREPARE phase ensures that a majority of correct replicas has agreed on a sequence number for a client’s request. Yet that order could be modified by a new leader elected in a view change.

Can someone show me an example of how COMMIT interacts with view changes?


texts: Why are Python 2 and 3 so incompatible with each other?

texts: Every software should have backward compatibility (at least some sense of it), this ensures old codes can run in the future updated systems without any problems in most situations. But why did the Python team decide to make the v3 a new language? The community has to split up into two and every computer has to install both v2 and v3 in order to run every python code. This is a huge mess. Is there a computer science reason behind this decision?


texts: $UP^{\ O}\neq P^{\ O}$ for some oracle $O$

texts:
The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$.

I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $L\notin P^{\ O}$, i.e. $UP^{\ O}\neq P^{\ O}$.

I find a lot of struggle of finding an explicit $O$, and more struggle to proof it without finding one. I don't have access to the paper which is in the complexity zoo in the link above, can you please explain why it is true or provide me with access to the paper?


texts:
I don't understand the notion of relativization. I expose with an example. Consider a class $A$ that contains $P$, e.g. $NP$. Why $P^A$ is not necessarily equal to $A$? I can naively think that if one can decide any problem in $A$, one can also decide any problem that uses polynomially many steps in a Turing machine plus calls to $A$. One can have at most polynomially many calls to $A$, thus $P^A$ seems there is only a polynomial overhead compare to $A$. If $A$ is $NP$, I could give a certification for all the (polinomially many) oracle calls, and also easily give a certification of the polynomial rest of the computation.
I understand that if it is true, then $NP$ is the same as $coNP$, both being contained in $P^{NP}$ from the polynomial hierarchy. So, where is the error in my naive argument?


texts: Why does Dijkstra's algorithm not account for updating node distances after expanding a node?

texts:
Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed?

For example, in the accepted answer of this question (link), if the algorithm simply understands that d(b) has been updated and it should re-expand b, the shortest cost would be found.

Am i missing something?


texts:
I'm struggling to understand the purpose of universal and existential quantification of types. I'm playing around with writing a toy language based on the calculus of constructions. I've been reading about Morte and Henk to help me get a better understanding.

I don't understand why the CoC has both lambda and forall abstraction.

$$(\lambda x:A . B)$$
$$(\forall x:A . B)$$

It seems to me that lambda subsumes forall in a system where types are passed manually. In other words, that the following

$$(\forall x : *. \lambda a : x. a)$$

Could be replaced with

$$(\lambda x : *. \lambda a : x. a)$$

If it was first applied to the type being used.

What am I missing? What papers or blogs or articles are there to read that might help me?

Thanks.


texts: Alternative algorithm for minimum spanning tree construction

texts:
Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its
  edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an
  algorithm which replaces an edge $\textit{e}$ in $\textit{T}$ by an edge $\textit{e'}$ not in $\textit{T}$, if $\textit{e' < e}$ and replacing it still maintains $\textit{T}$ to be a spanning tree.

I want to prove that this algorithm results in a minimum cost spanning tree of $\textit{G}$.

I am trying to prove this by contradiction - consider that $
\textit{T}$ is the tree which we obtain when the algorithm ends. We assume that there exists $\textit{T'}$ such that $\textit{W(T') < W(T)}$.

Attempt: I tried considering an edge $\textit{e}$ to be the lowest cost edge which is in $\textit{T'}$ but not in $\textit{T}$ (there is at least one since both are different spanning trees). We add $\textit{e}$ to $\textit{T}$ - thus, creating a cycle (since $\textit{T}$ was a spanning tree). There are two possible cases:

$\textit{e}$ is smaller than all the edges of the cycle it induced. But, in this case, the algorithm would not have stopped at $\textit{T}$, it would have replaced one of the edges of the cycle by $\textit{e}$.
$\textit{e}$ is larger than all the edges of the cycle it induced. I suppose this should contradict the minimality of $\textit{T'}$.

Am I anywhere on the right track? I don't know if considering the cycle is the way to do this.


texts: Why the number of equivalence classes for the intersection of an irregular language L2 and a regular languge L3 (with 3 EC) can't be determined?

texts:
I'm trying to understand why can't we determine the number of equivalence classes of the intersection of L2 which is irregular and L3 which is regular and known to have 3 equivalence classes (L3 can't be empty). Can't we say it has minimum of 1?

Can we determine the number of equivalence classes for an Irregular language L with a star (L*)?


texts: Counting number of states from a regular expression

texts:
Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$.
Let A be a non-deterministic automaton that accepts the language of r.
How many states are in A?
Answer the question without building A explicitly, explain how you got the answer.

I'm having trouble figuring this question out.
The answer that was given is: $5*2+4*2=18$

With the explanation that for the $\epsilon$ regular expression we build an automaton with 2 states.

for each $\sigma \in \Sigma$ for the regular expression $\sigma$ we build an automaton with 2 states

For concatenating we do not add states and for each union or star operation we add 2 states.

But even with this explanation I'm not quite sure did they reach this answer.

I can understand that we have $\epsilon$, so we have 2. Plus we have $\Sigma = \{a,b,c\}$ so we do $2*3$.

Even with the stars, how do we reach $5*2$?

Also I haven't seen this kind of calculation before, are there any additional rules when trying to calculate states from a regular expression?


texts: What is a good reference to learn about state transition systems?

texts:
I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but failed to do so.

Does anybody know a modern introduction to the topic?
Of particular interest would be something dealing with computability.


texts: NP completeness proof of sensor selection problem

texts:
There are $n$ points in a plane.

The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from the selected set of points.

I am trying to use the sensor coverage problem where the idea is to place sensors in the plane where all $n$ points are reached. However, it allows the sensors to be placed at non-$n$ points which my problem doesn't allow. Is there some way I can still show that the problem is NP-complete by subset selection or any other approach.

Thanks!


texts: Turing machine that computes w#w when the input is w?

texts:
Can someone please describe how such a machine would work?

My approach:

Move the head full on the left. Scan the input to verify no # symbol exists. Add # at the end of input. Move the head full on the left. Move one position on the right.

Read character σ and replace it with σ'. Then go right to the 1st empty char and replace it with σ. Then go left till you found the 1st ' char. Remove the ' from that char. Move one position the the right and repeat.

When you do that for all characters stop.


texts:
What is the relation of complexity class $L^L$ to other complexity classes?

(Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in logspace.)


texts:
I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow.
Well-founded induction (WFI) is the following statement:

$\forall x \in A(\forall y \in A(x \stackrel{+}{\to}y \Rightarrow P(y))\Rightarrow P(x)) \Longrightarrow \forall x\in A (P(x))$

Here is the proof I cannot understand.

Theorem: If well-founded induction holds, then the relation $\to$ on a reduction system terminates.
Proof: by WFI, where $P(x):=$ "there exist no infinite chain starting from $x$". The induction step is simple: If there exist no infinite chains starting from any successor of $x$, then there exist no infinite chains starting from $x$. Hence, the premise of WFI holds, and we can conclude that $P(x)$ holds for all $x$ i.e., $\to$ terminates.

Why can we define $P(x)$ to be "there exist no infinite chain starting from $x$"?


texts: What would an exponential reduction from an NP-complete problem to P signify?

texts:
Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what would be it's implications?

Based on Yuval's answer, I wanted to throw this scenario into the place also.

If we have a problem in P which we can reduce in polynomial time to an NP-complete problem for e.g vertex cover, what happens then?


texts:
What are the differences between an implicitly typed programming language and a untyped    programming language?

Let me explain the above question and what I have thought about it.

My question comes from reading
https://stackoverflow.com/a/9159863/156458, where the huge slide says
"untyped = no type declaration".  I don't quite agree with the
definition of untyped, but the author can define a term in his own
way which doesn't need to agree with PLT. Note that I don't know
what definitions mostly make sense with respect to what they are
named as in PLT.

In fact, after reading
https://en.wikipedia.org/wiki/Programming_language#Type_system, I
think implicitly typed means no type declaration when declaring a
name, and is a concept as opposed to manifest i.e. explicitly typed.
Untyped is a concept as opposed to typed. So my questions are based
on the definitions from the wikipedia article.
If I am correct, the programs in both implicitly typed programming languages and untyped
programming languages don't have explicit declaration of the type of
each object, so the programs written in them look the same.  Then
how can you tell if a language is an implicit typed or a untyped
programming language?
Is "implicitly typed" a concept at the level of implementations of programming languages, but not at the level of languages themselves?

I guess it is because for an implicitly typed language, any compiler or interpreter of the language will have to do type inference. If a compiler or interpreter of the language doesn't do type inference, then the language is untyped for this compiler or interpreter. So is untyped also a concept at the level of implementations of programming languages?

So to answer the question in part 2, we need to specify a particular implementation of the programming language under consideration?

Thanks.


texts: An algorithm to split an area into multiple polygons based on other polygons intersection

texts:
I have a list of n polygons (A,B,C,D,E,...) which possibly intersect each other.
I need to find a new list of polygons (or multi-polygons) which looks like this:
(
Area only in A (A difference from the rest)
Area only in B
Area only in C
...

Area only in A and B (A intersection with B and difference from the rest)
Area only in A and C
Area only in B and C
...

Area only in A,B and C (A intersection with B and C and difference from the rest)
Area only in A,B and D
Area only in A,B and E
....

)```

The only way I can find is to iterate all the combinations and run a simple intersection/difference algorithms but the number rapidly increases.


texts: I start to work in the field of computer vision and read a paper in which the author states "When suitable correspondences between salient image structures have been established, the 3D uncerntainty of these structures mainly depends on the triangulation angle between the oberservations and the 3D structures". So what is the triangulation angle? In the wikipedia article on triangulation (http://en.wikipedia.org/wiki/Triangulation_%28computer_vision%29) there is a really nice pictures that explains the triangulation but which angle in this picture is the trinagulation angle?


texts: Maximum independent nodes subset algorithm with strong constraint

texts:
I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints:

The selected nodes must be the optimal solution (maximal sum of weight).
If one node is flagged no adjacent nodes can be flagged.
If a node is flagged it will be called: "directly controlled", the adjacent nodes instead will be called: "indirectly controlled", all nodes must be directly or indirectly controlled.

I think is a dynamic programming problem (a greedy approach didn't find always a optimal solution), the first two constraints are a typical maximum independent subset problems, but i cannot find a solution with the third constraint included.
Any idea? Thanks


texts: The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known.  Is there a similar average case lower bound for sorting in the comparison model and if so, which random distributions does it apply to?


texts: Using oracle machine to speed up tree solution search

texts:
Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for simplicity let's assume we do not apply any cuts).

Let $M$ be an oracle machine able to solve a problem $P^\prime$ sub-problem of $P$ of size $k < n$ in time $O(1)$

Is there a known approach of applying $M$ during searching for solution of $P$ in order to find it in time $O(2^{n-k})$? If speed-up of factor $O(2^k)$ is not possible, what is the best known achievable result for such problem? Are oracle machines limited to problem size $k$ useful at all to solve problems of size $n > k$?

Possible application of such approach could be solving NP-Complete problems using a quantum computer that is limited to $k$ cubits as oracle machine. Of course it wouldn't solve sub-problem in time of $O(1)$ but it is just for theoretical simplification.

This question was inspired by branch and price algorithm for integer programming, but instead of generating columns, at each node an technically advanced problem solving machine could be applied as an oracle.


texts: Application of floors and ceilings to the time complexity of loop with constant index increment

texts:
Consider the number of times that 'statement' runs in the following examples. I am confused as to the applications of floors and ceilings when calculating the loop complexity.
for (int i = 1; i < m; i += a) {
   statement;
}

In this example, I count the loop by establishing a bijection between the loop iteration and the values of i that do not break the termination condition, values identified by sequence 1, 1 + a, 1 + 2a, ..., 1 + (n-1)a.
Solving for the termination condition:
1 + (n-1)a = m => n - 1 = (m - 1)/a, since the only the first n - 1 terms in the sequence are counting the number of iterations.
The number of iterations being an integer becomes floor((m-1)/a), in my understanding. However, in many solutions I see that the number of iterations is just m/a -- the discussion on floors and ceilings is neglected.
How do I get from the ceiling notation to the much simpler looking m/a figure?


texts: What is the complexity of a variation of the Coupon collector's problem?

texts:
I need to know the complexity of the following algorithm:

Draw elements from a set of size $m$, one by one, randomly, with replacement, until coming across $n$ different elements from the set ($n\le m$). We do not care what are the numbers drawn, and halt once $n$ different numbers were seen during this process.

This is a variation of the Coupon collector's problem, where one continues picking until seeing all $m$ elements of the set.

Example:

We draw numbers from the set $\{1,2,3,4,5\}$, $n=3$, $m=5$. The output
$\{1,5,2\}$ is produced by the following series of draws:

$1,1,5,1,5,2$

from the pool $\{1,2,3,4,5\}$. In this case, we halt after $6$ operations.

What is the expected time complexity of this algorithm?


texts: Original literature on adversary argument

texts:
I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.

I cannot find the original papers which invented/advocated adversary argument or the first problems whose lower bounds are obtained by adversary argument. (In particular, I am quite surprised that there are no wiki pages on adversary argument.)

Do you know some original literature on adversary argument?


texts: Big O of this function logn + log((n^3) + 1)

texts:
I did max(logn , log((n^3) + 1) ) = O(log((n^3) +1)).

May I get verification is correct or not?

log(n^3) is a worser algorithm than logn because n^3 grows faster than n.


texts: Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction

texts:
This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete.

If we had a reduction that given an instance of 2CNF-SAT with k clauses over 'i' number of variables, and we create an instance of 3CNF-SAT with 2n clauses by introducing for clause i a new variable y; then for the i'th 2SAT clause we generate two 3SAT clauses.  This is a reduction from a 2CNF-SAT to a 3CNF-SAT.

Is this not a correct reduction because all of the other clauses after the transformation are still 2CNF-SAT except for the i'th clause?


texts:
This is the HMM model considered in the question

And this is the emission probabilities for the respective states. There are two emission values, bringing an umbrella and not bringing an umbrella.

Description of the question:

The question considered the initial state as sunny.
On day 2, the person brought an umbrella.
On day 3, the person didn't carry an umbrella.

We have to find the probability that it's foggy on 3rd day.

Given: Prior probability of the caretaker carrying an umbrella is 0.5.

According to me, the answer to this question was addition of the terms in the red circles.

Where α1 = 0.8 * 0.1, α2 = 0.05 * 0.8, α3 = 0.15 * 0.3

Problem I faced:
But the answer included dividing the answer I got by (0.5)2. That is, I guess they are dividing by the prior probability two times for the two transitions, but I'm not clear as to why they are dividing.


texts: Finding exact corner solutions to linear programming using interior point methods

texts:
The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior point methods walk the inside of the polytope. As a result, when a whole plane of the polytope is optimal (if the objective function is exactly parallel to the plane), we can get a solution in the middle of this plane.

Suppose that we want to find a corner of the polytope instead. For example if we want to do maximum matching by reducing it to linear programming, we don't want to get an answer consisting of "the matching contains 0.34% of the edge XY and 0.89% of the edge AB and ...". We want to get an answer with 0's and 1's (which simplex would give us since all corners consist of 0's and 1's). Is there a way to do this with an interior point method that guarantees to find exact corner solutions in polynomial time? (for example perhaps we can modify the objective function to favor corners)


texts:
As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in practice.

Let me recall the mathematical intuition behind model checking using these techniques.
Buchi automata are the automata associated to $\omega$-regular languages. You can think of these languages as the infinite version of the regular languages (infinite in the sense that they operate on infinite words). As regular languages, they enjoy closure properties under composition and intersection. It is also well known that these Automata are "isomorphic" to proposition of a logic called S1S. This is the logic of Monadic Second Order Logic (i.e. you can have quantification of on the predicates of the logic, but the elements can ranges over a finite set). S1S has the nice property of being decidable, i.e. for each preposition we can tell if it is true or not. To find if a S1S formula is satisfiable, we can find if the associated atomata has an accepting state. In Buchi automata this is done by finding cycles between the starting state and any final state.

To find a "bug" in a software we proceed like this:

we formalize our software as $\mathbb{S}$ using a S1S logic (a monaidic second order logic).
we formalize the security properties of our software in the logic $\mathbb{P}$
now we use closeness properties of $\omega$-languages, whose associated automata are equivalent to S1S logic: we build Buchi automata of $\overline{\mathbb{S}} \cap \mathbb{P}$

In this way, if the software does not comply to the security properties, the resulting automata will have at least an accepting state. In practice, the accepting state of a Buchi automata can be found by finding a cycle in the associated graph between the starting state and any final state.

I suspect in practice an algorithm for cycle detection cannot be used. This is due to the constraint that the cycle should pass from the only starting state and should pass through an accepting state, so the likelihood of finding the cycle you need might be very low. Anyway, the best algorithm for Cycle detection is solved by the Johnson Algorithm in time $O((n + e)(c + 1))$ and space bounded by $O(n + e)$).

In practice, S1S decidibility using Buchi automata might be best to be solved with s-t connectivity. For instance, NetworkX solves s-t connectivity with this algorithm
by Abdol-Hossein Esfahanian.

Am I correct?

Which graph algorithm is used in practice to solve S1S satisfiability using Buchi automata?

I have found this, but it just shows a better reduction from S1S to Buchi, and it doesn't talk about graphs.


texts:
Can someone help me prove the correctness of this algorithm:

MUL(a,b)
   x=a
   y=b
   WHILE x≥b DO
      x=x-b
      y=y+1
   IF x=0 THEN
      RETURN(true)
   ELSE
      RETURN(false)

I had to prove that $x_n + b\cdot y_n = a$ by induction, where $x_n$ and $y_n$ are the values of the variable x and y after the loop has iterated n times.

I have done that, but I am not sure how to prove the correctness of the algorithm.


texts:
Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new encoding is $-0.75\log_2(0.75)-0.25\log_2(0.25)\approx 0.81$, so we should be able to do it in about $1.23n$ bits.

(By 3/4 the bits being 1's, I mean that each bit should be indistinguishable from an event that happens with probability 3/4; as opposed to a long block of unbiased random bits followed by an equal length block of 1's.)

We could try, for each bit, put the next bit of the original data with probability 1/2, and put a 1 with probability 1/2. Then somehow include extra information about which bits encode the original data, and which are filler. But this reqiures at least $2n$ bits, well above the theoretical minimum. So how can the minimum actually be achieved?


texts:
Usually when I see "programming language dialect" it refers to small variations of a language, such as BASIC dialects or different versions of Lisp.
The tidyverse set of packages form their own "universe" that is based on some common ideas, such as function composition in the form of piping, and the so-called "tidy evaluation" framework using quasi-quotation, "quosures", and "data masks". This is all implemented in R, but the tidyverse makes use of significantly more metaprogramming, though the end-user usually does not need to know the details of how it works. But tidyverse code looks significantly different than base R style code.
In fact, when I use R, tidyverse libraries are so widespread that one way to categorize any library I use is whether it's "tidyverse/ggplot2" or "base R" style. The tidyverse implements libraries that supplant almost all functionality of base R.

So given this divide, does the tidyverse form a "dialect" of R?


texts: Maximum number of distinct values for bitwise OR

texts:
You are given an array with $N$ elements. The values of the elements may be any number in the interval $[0,10^9]$. Define $f(a,b)$ as the bitwise or of all the values in the subarray $[a,b]$. Find a bound on the number of distinct values of $f(a,b)$.

Attempts: I have tried to brute force cases to find a pattern but was unsuccessful.

Please explain the reasoning behind your answer. I am a complete beginner.


texts: In "multi hop" network, is computer => computer 0 hop or 1 hop?

texts: Would this here, a computer sending information directly to another computer, count as 0 hops or 1 hop?


texts: Proof of bucket sort worst case being all elements in one bucket

texts:
By bucket sort I mean on dividing numbers between 0 and 1 into $n$ buckets and performing insertion sort on all the buckets.

1| n ← length [A]
2| For i = 1 to n do
3|     Insert A[i] into list B[nA[i]]
4| For i = 0 to n-1 do
5|     Sort list B with Insertion sort
6| Concatenate the lists B[0], B[1], . . B[n-1] together in order.

The time taking task is lines 4 and 5, which on uniform distribution takes $\Theta(n)$ time. So the worst case, by intuition, I can say is $\Theta(n^2)$ when all the elements fall into one bucket (standard insertion sort on $n$ elements).

But how can I prove that the worst case for this algorithm is when I take all elements in one bucket? Bucket sort worst case stuff I've seen online directly say that the worst case is when we have all elements in that one bucket. But how can I prove this in the first place? Thanks!


texts: How to find big-O for an in-place perfect shuffle algorithm

texts:
I've found a simple algorithm to interleave two halves of an array in place.  It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of the items that got moved, then repeating for the remaining 1/2 array.

Unscrambling the permutation uses the fact that left items move into the right side with an alternating "add to end, swap oldest" pattern. We can find the i'th index in this permutation with this this rule:

  For even i, the end was at i/2.
  For odd i, the oldest was added to the end at step (i-1)/2

This gives this O(1) amortized oracle function:

$$
next(i) :=
\begin{cases}
i/2 & \text{if $i$ is even;}\\
next( (i-1)/2) & \text{otherwise.}
\end{cases}
$$

(This is A025480)

The other complication in unscrambling is that while putting items back into place, sometimes the source index has already been used as a destination.
Traditionally, this is where you would use an algorithm to find cycle leaders, guaranteeing minimal data movement at the cost of additional space or time.   This algorithm just advances through the permutation, swapping every item into place, and running the next_index calculation again whenever it encounters a source which has already been swapped elsewhere. See the 'while' loop below.

Given a sequence $A$ of length $n$, consider it as two parts:
$L = A_0 \ldots A_{m-1}$ and $R = A_m \ldots A_{n-1}$ where $m$ is $\lfloor n/2 \rfloor$.  Then interleave($A$) will produce $R_0, L_0, R_1, L_1, \ldots$

$$
interleave(A) := {\\
m \leftarrow \lfloor n/2 \rfloor \\
\text{let }L = A_0 \ldots A_{m-1}     \\
\text{let }R = A_m \ldots A_n  \\
\text{for } i \text{ in } 0 \ldots (m-1): {
j \leftarrow next(i) \\
\operatorname{exchange} L_i, R_j }\\
\text{for } j\text{ in } 0 \ldots ( \lfloor m/2 \rfloor -2): {\\
k \leftarrow next(\lfloor m/2 \rfloor + j) \\
\text{while } k < j : k \leftarrow next(\lfloor m/2 \rfloor + k) \\
\operatorname{exchange} R_j, R_k} \\
\text{if } n - m > 1 : { \\
b \leftarrow 1 \text{ if $m$ is odd; } 0 \text{ otherwise} \\
\operatorname{interleave} R_b \ldots R_{n-m-1} }
}
$$

The number of swaps is strictly 1.5 N.
The question I have is: What's the big O of the index calculation in the unscramble step?

I think, in the hypothetical worst case, where every item is one slot above its destination, you would do 1+2+3+...+N/4 calls to next_index in the first pass. That works out to N^2/32 which is still O(N^2).

But the placement pattern never gets close to that worst case.  Half the items are guaranteed to only need one lookup:  the last half of the permutation contains every other item in increasing order - these will be swapped directly into place.  And the remaining number of lookups depends on the number of cycles in the permutation - which seems to follow A006694.

Empirically it seems to be significantly less than N lg N - Here's a graph of calls to next_index vs N, with N lg lg N overlaid.

I'd like to learn how to calculate the actual growth.

C implementation.

int next_index(int n) {
  while (n & 1) { n = n >> 1; }
  return n >> 1;
}

void interleave(value_t A[], int n) {
  int i, j, k;
  int m = n/2;
  value_t* L = A;
  value_t* R = A+m;

  // Place 1st half
  for (i=0; i < m; i++) {
    j = next_index(i);
    SWAP( L+i, R+j);
  }

  //unscramble step
  for (j=0; j < m/2 -1; j++) {
    k = next_index(m/2 + j);
    while (k < j) {
      k = next_index(m/2 + k);
    }
    SWAP( R+j, R+k);
  }
  if (n-m > 1) {
    int b = (m&1) ? 1 : 0;
    interleave(R+b, n-m-b);
  }
}


texts: An optimization version of 2QBF: is it $\mathsf{NP}^{\mathsf{NP}}$-hard?

texts:
I am studying the computational complexity of the following decision problem related to 2QBF:

Input: a 3-CNF formula $\varphi$ over $X \cup Y$, where $X$, $Y$ are disjoint sets of propositional variables, and an integer $k \geq 0$.
Question: does there exists an assignment of the variables from $X$ such that all assignments of the variables from $Y$ satisfy at least $k$ clauses from $\varphi$?

Is this problem $\mathsf{NP}^{\mathsf{NP}}$-hard?
Despite the problem being in $\mathsf{NP}$ for the case where all clauses in $\varphi$ are required to be satisfied, to me the problem above seems to be $\mathsf{NP}^{\mathsf{NP}}$-hard. But while a number of works can be found when the two quantifiers are reversed (i.e., when the first quantifier is universal and the second quantifier is existential), I cannot manage to find the problem stated above studied in the literature.


texts: Randomly partition an rectangle into N smaller rectangles

texts:
I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

Partitioned into exactly N smaller rectangles
Everything must actually be a rectangle (no L shapes, etc)
No empty space left over

The algorithm as a whole should meet the following criteria:

There is no valid partitioning that the algorithm is incapable of producing
Can be biased towards certain types of  configurations, though the less bias the better.
Preferably works with integer indices.
Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.


texts: DPDA - a language that contains the same number of A and B

texts:
I need help with creating Deterministic pushdown automaton for language:
L = {v1w | v, w ∈ {a, b, c}*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string.

In the first state, I try to load the first string v. But I do not know how to control the same number of "a" and "c" characters.

Thanks for help


texts: Undecidability instance on a "find a proof/disproof" machine

texts:
I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on:

Suppose we built the following machine in attempt to solve the halting problem. It takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I. It then tries every one-page proof that machine M never halts on input I. Then it tries every two-page proof of each, and so on and so on.

It's quite plain that this wouldn't necessarily always work. By incompleteness, there are statements that can't be proven true or false; it makes sense that there might be Turing machines that are equivalent to these statements. The undecidability problem assures that indeed these do exist.

So, let's follow that through. [Begin standard proof.] We have built this function $f(a,b)$ to return $1$ if it finds a proof that program $a$ halts on input $b$, and $0$ if it finds a proof that $a$ doesn't halt. (We note that this function $f$ might never return, so it's not total computable.) We can make a function $g(a)$ that first calls $f(a,a)$, and returns $0$ if $f(a,a)=0$, and enters an infinite loop if $f(a,a)=1$.

If $f(g,g)$ terminated and returned 0, then $g(g)$ would terminate and return 0 -- but $f(g,g)$ terminating and returning 0 implies it found a proof of $g(g)$ not terminating, so this is impossible. If $f(g,g)$ terminated and returned 1, then $g(g)$ would never terminate -- but $f(g,g)$ returning 1 implies it found a proof of $g(g)$ terminating. [End standard proof.]

This pair of paradoxes is used in the standard proof to show that there is no function $f$ that always returns $0$ or $1$. There's no problem here, though, because we allow $f$ to not terminate -- and so indeed, it must never terminate, when given the inputs $g$ and $g$.

Here's where I'm confused. Because $f(g,g)$ never terminates, this implies that there is no disproof to be found, because it tries all of them. Suppose that $g(g)$ terminated at some point. Then by running simply it for that many steps, we can see that terminates, and this constitutes a perfectly valid proof.

Keep in mind that $f$ is a real program, and so is $g$. We know that for these concrete values (in some numbering system), $g(g)$ can't terminate, otherwise $f(g,g)$ would find the dumb proof of simply running it to that point.

The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof, and use it to show that $g(g)$ doesn't terminate, but this is also a problem.

I'm sure there's something here I'm dramatically misunderstanding; I appreciate the time from anyone to answer.


texts: Which method is preferred for storing large geometric objects in a quadtree?

texts:
When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:

Placing the object's reference in every leaf for which it is contained
Placing the object's reference in the deepest node for which it is fully contained
Both #1 and #2

For example:

In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).

For the purposes of querying the quadtree, which method is more commonplace and why?


texts: Generative power and classification of matrix grammars

texts:
[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy.

In here it is stated that:

A matrix grammar is a quintuple $G = (N, T, M, S, F)$, where $N,T$, and $S$ are specified as for a context-free grammar, $M = \{m_1, m_2, \dots m_n \}$ is a finite set of finite sequences of context free rules (i.e. for $1 \leq m_1 \leq n$, $m_i = (A_{i,1} \rightarrow w_{i,1}, A_{i,2} \rightarrow w_{i,2}, \dots A_{i,r_i} \rightarrow w_{i,r_i})$ for some $r_i \geq 1$, $A_{i,j} \in N$, $w_{i,j} \in (N \cup T)*$, and $1 \leq j \leq r_i$) and $F$ is a subset occurring in the matrices $m_i$
$L(MAT)$ denotes the set of all languages that can be generated by matrix grammars  -
Theorem $L(MAT) = L(RE)$
Theorem For each recursively enumerable language $L$, there is a matrix grammar $G$ in normal form such that $L (G) = L$.

While although this paper is about simple matrix grammars, it also states a definition of matrix grammars (not simple matrix grammars) that is a bit different with the above definition. It is stated that

A matrix grammar (MG for short) is a pair $H = (G, M)$ where $G = (N,T,P,S)$ is a context-free grammar; $M$ is a finite language over the alphabet of rules $(M \subseteq P^*)$.
For $x, y \in (N \cup T)^*, m \in M$,
$x \Rightarrow y[m]$
in $H$, if and only if there are $x_0, x_1,\dots, x_n$ such that
$x_0 = x, x_n = y$, and
$x_0 \Rightarrow x_1[p_1] \Rightarrow x_2[p_2]) \Rightarrow \dots \Rightarrow x_n[p_n]$ in $G$, and
$m = p_1 p_2 \dots p_n$, where $p_i \in P, 1 \leq i \leq n$, for
some $n \geq 1$.
Let $MT$ denotes the family of languages that is generated by matrix grammars
$CF \subset MT \subset CS$

Question. How come when matrix grammars can generate recursively enumerable languages but it is still classified as a proper subset of the family of context-sensitive languages? Perhaps because they are different matrix grammars? I also read about it in this book but it is too complicated for me.

Additional Question.  If a grammars $G$ can generate some context-sensitive languages (let's say that the family of languages generated as $XG$ ), is it still possible that the family of languages is going to be classified as a proper subset (strict inclusion) of $CS$, i.e. $XG \subset CS$?


texts: How to group thousand of data points for each user

texts:
I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each data point can have 3 states: true, false, unknown.
What could I do to group these data points so that they don't take too much space?
My initial plan is to basically cluster them. Something like:

unknown: [1-23, 25, 27]
true: [24, 26]
false: [28-30]

Where m-n represents number from m to n.


texts: Why is there a precision loss for floating-point numbers?

texts:
It could be a silly question, yet I'm not able to understand.
In modern day, computers, we have integers with million digits length. Even in my ordinary 2GB laptop, I can calculate values of numbers up to thousand digits long, but the value of a floating-point calculation is often limited to 15 digits or worse, like 0.1 + 0.2 is not equal to 0.3 (in Python, its 0.30000000000000004).

Why do we have such loss of precision in floating-point calculation? Is it due to the limit of binary system to express floating-point numbers?


texts: Cook-Levin theorem proof's requirement of $\phi_{cell}$

texts:
I'm trying to understand the Cook-Levin theorem proof, as it attempts to create a polynomial-time reduction from any NP problem to SAT (as presented in the book by Michael Sipser).

Most requirements are absolutely clear, but I don't understand why the $\phi_{cell}$ formula is required.

Of course, a tableau with improper values, such that fails $\phi_{cell}$, is broken and therefore will not "translate" correctly to the original NP problem on the other side of the reduction. We can easily "break" a tablaue by putting a $q_{accept}$ somewhere where it shouldn't, and the machine's language will change.

But I seem to miss something basic. A reduction says that if A reduces to B, then for each $w\in\Sigma^* $, $w\in A$ iff $f(w)\in B$.

The $f(w)$ part may be the "broken" tableau, but can we really call it $f(w)$? After all, such broken tableaus are never in the image of $f$.

So, why do we care about them?


texts:
Some definitions:

Consider the unweighted directed graph $G$, where each node is uniquely represented by an $n$-bit vector of $0$'s and $1$'s.

Now consider this scenario: we want to 'shrink the dimension' of the index vectors for all nodes. For example, originally, some node has the index vector $\langle 0, 1, 1, 0 \rangle$ (so $n=4$), and we want to shrink the dimension to 2 by removing, for example, the first and third bit. Then the index for this node becomes $\langle x, 1, x, 0 \rangle$, where $x$ represents the removed bits.

$x$'s are considered the same bit. If in the original graph, the bitstrings differ only in these two bits, the two nodes will be merged as the same node after the 'shrinking'.

The edges are changed such that the new graph $G'$ contains an edge $(u,v)$ if and only if there were an nodes $u',v'$ 'shrunk' into $u,v$ such that $(u',v')$ is an edge in $G$.

My problem:

For a fixed source node $s$ and an arbitrary node $u$, we consider the shortest path between them: the distance of the node $u$ from $s$. Our objective is to minimized the longest such distance. Naturally, after the shrinking, the shortest paths can be different. Note that shrinkage can only decrease the objective value if not preserve the value as before shrinkage.

Now suppose we need to shrink $k$ bits out of the total $n$-bit vector and want to maximize the objective value from the source node in the new graph. How to decide which $k$ bits should we choose?

The decision version of the problem is

Given a graph $G = (V, E)$ as described above, a source node $s \in V$, an integer $k$ and an integer $C$, is there a 'shrinkage' of at most $k$ bits that creates a graph of objective value greater than $C$?

I have a feeling this is NP-hard, but failed to prove it by reducing it to some previous problems.

Any suggestions on the algorithms, reference literature, or refining my lousy descriptions are appreciated!


texts:
Consider the algorithm below which calculates a V cut

Initialize $V_1 = V$ et $V_2 = \emptyset$
Attempt to improve the value of the cut in any of the following ways

Check if there is a $v \in V_1$  such as $c(V_1-\{v\}, V_2 \cup \{v\}) > c(V_1,V_2)$

If yes continue with $V_1 = V_1 -\{v\}$ et $V_2 = V_2 \cup \{v\}$.

Check if there is a $v \in V_2$ such as $c(V_1 \cup \{v\}, V_2 - \{v\}) > c(V_1,V_2)$ If yes continue with  $V_1 = V_1 \cup \{v\}$ et $V_2 = V_2 - \{v\}$.
When improvement is no longer possible, return the cut $V_1, V_2$

1 . How can I prove that the algorithm is executed in polynomial time by displaying done at most $|E|$ iterations.

Let $(V_1,V_2)$ be a cut. For a $v \in V_1$ we call $\alpha(v)$ the neighbors of $v$ which are in $V_1$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$.If $v \in V_2$, we set $\alpha(v)$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$ and $V_1$ respectively.

How to prove that if the algorithm can no longer advance then for everything $v \in V$ we have $|\alpha(v)| \leq |\beta(v)|$


texts: How to model an ''affinity constraint'' in assignment problem

texts:
Working on an optimization problem formulated using the well known assignment problem. My decision variable is defined as follows :

$$\alpha _{x}^{r,u} = 1\begin{cases}
 & \text{ 1 if } \mathbf{VM}\: \mathbf{u}\; of\; request \: \boldsymbol{r}\; is\; assigned\; to\; server\; \mathbf{x}\\
 & \text{ 0 } otherwise
\end{cases}
\\\\
$$
$$V_{r}\; is\; the\; of\; VMs,\; V_{p}\; is\; the\; of\; servers, R\;is\;the\;set\;of\;requests$$

The complete model is defined as wit the relevant constraints :
$$Min \sum_{r}\sum_{x}\sum_{u} Cost(u,x)\ast \alpha _{x}^{r,u}$$
$Subjet\;to$
$$\sum_{x}\alpha _{x}^{r,u} = 1\; \; \; \; \; \; \; \; \; \; \; \; \; \forall u\in V_{r},\forall r\in R \;\;\;\;\;\;\;\;\;\;(1)$$
$$\alpha _{x}^{r,u} \in [0,1]\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(2)$$

A request r is composed of a set of VMs and for some reasons (security, performance, reliability) some VMs of a request r has to be put together within the same server if the resources are available, I define this as affinity constraint.
Mathematically, I defined it as :
$$
\sum_{u}\alpha _{x}^{r,u} = Cardinality(\varphi^{r})\; \; \; \; \; \; \; \; \; \; \; \; \; \forall x\in V_{p},\forall r\in V_{r},\forall u\in \varphi^{r} , \varphi^{r}\subseteq V_{r}$$
I implemented the constraint within my model using Gurobi but the model is infeasible and I am wondering why it does not work wether it is related to the way I formulated it or other reason I am not aware of.

Another way to define the affinity constraint might be using the form of if A then B in the following way : If a given VM $u$ belonging to the affinity set say AffinitySet={VM1, VM2, VM3} then all the VMs within that set has to be put within the server x. However, I am not sure how to model this constraint mathematically.

Will appreciate any help, thanks.


texts: Solving the recurrence T(n) = 3T(n-2) with iterative method

texts:
It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given:

$$T(n) = 3T(n-2)$$

My first step was to iteratively substitute terms to arrive at a general form:

$$T(n-2) = 3T(n-2 -2) = 3T(n-4)$$
$$T(n) = 3 *3T(n-4)$$

leading to the general form:

$$ T(n) = 3^k T(n-2k) $$

Now I solve $n-2k = 1$ for $k$, which is the point where the recurrence stops (where $T(1)$) and insert that value ($n/2 - 1/2 = k$) into the general form:

$$T(n) = 3^{n/2-1/2}$$
$$T(n) = O(3^n)$$

I'm not sure about that last step:

I would just "argue" that as $n \to \infty$ one can ignore $-1/2$ and $n/2 \to n$ ?
Is that assumption correct?


texts: Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$?

texts:
I am having problems resolving the following question:

  Given some problem $X$. If there exists a polynomial time reduction from (for example) $\mbox{SAT}$ to $X$, $(\mbox{SAT} \leq_{p} X)$ and since we know that $\mbox{SAT}$ is $\mbox{NP-complete}$, to show that $X$ is $\mbox{NP-complete}$ is it necessary to show that $X\in \mbox{NP}$ via some third party algorithm?

If yes, then why?


texts:
i have to calculate the asymptotic runtime of a nested sum:

Sum $\sum_{n=1}^{log_{4}(n)} \sum_{n=1}^{\sqrt{n}}1$

My solution is $\Theta(log(n) \cdot \sqrt{n})$, which is wrong, because the solution says $\Theta(\sqrt{n})$. I dont understand where my mistake is:

Sum $\sum_{i=1}^{log_{4}(n)} \sum_{j=1}^{\sqrt{n}}1 =  \sum_{i=1}^{log_{4}(n)} \sqrt{n} = \sqrt{n} \sum_{i=1}^{log_{4}(n)}1 = \sqrt{n} \cdot (log(n)+1) =$
 $ log(n) \cdot \sqrt{n} + \sqrt{n} \stackrel{?}{=} \Theta(log(n) \cdot \sqrt{n}) $

Maybe my formula is wrong. Here is the pseudo-code i have to analyse:

someFunc(n)
  i = n
  while (i >= 1)
   i=i/4;
   //we do sqrt(i) operations
   for j=1 to sqrt(i)
     do_some_atomic_op() //O(1)
   end
   //i will reduce in every step!
  end
end


texts: Why is data in computer science considered to be discrete?

texts:
I understand that "structure" of data is totally dependent on Boolean Algebra, but:

  Why is data considered to be a discrete mathematical entity rather than a continuous one?

Related to this:

  What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

I am not an expert in the field as I am an undergrad math student, so I'd really appreciate it if someone would explain this to me like I'm five.


texts: Disk Scheduling for a Fragmented Hard-Drive

texts:
Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule  I/O requests depending on which cylinder number needs to be read and a process will produce only one I/O request whenever it needs to access a file.

This is confusing because apparently I/O requests are scheduled, but the actual algorithms work only with cylinder numbers. What if an I/O request requests a file which is spread over multiple tracks and therefore cylinders?

How can the algorithm schedule I/O requests when it's possible for each I/O request to require multiple cylinders to be read (e.g. if the file is fragmented across multiple cylinders).


texts: Finding optimal multiplication order and optimal binary tree

texts:
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.

Consider the following five matrices A, B, C, D and E along with their dimensions;
A=(6×5)     B=(5×1)     C=(1×7)     D=(7×4)     E=(4×2)

After two hours, I have calculated the final cost matrix as

0   30   72   82   85
    0    35   48   53
         0    28   43
              0    56
                   0

and the split k values that led to a minimum m[i, j] value

0   1   2   2   2
    0   2   2   2
        0   3   4
            0   4
                0

Now I don't know how to calculate optimal order for multiplication from the above table. And also don't know to draw optimal tree for that sequence. Kindly someone help me at this point.


texts: Is it possible to partially decide when will halt given any arbitrary input?

texts:
This is a problem that I think is a reduction from the halting problem. I have on two separate practice exams statements that,

  Given a Turing machine T and a string w, to determine whether T will halt when started on input w.

and

  Given a Turing machine T and a string w, to determine whether T will halt when started on a blank tape.

The answer key states that these problems are both partially decidable, which is astonishing to me given that they are reductions from the halting problem, which is undecidable.

If there was a Turing maching M, that would halt if it's input was another Turing machine T that also halted on an arbitrary string, would that not violate the halting problem? Why are the two above statements considered to be partially decidable?


texts: Has anyone seen a NP graph problem like this before?

texts:
I have a following graph-based problem:

Input: positive integers K and L, undirected graph G
I have to choose K vertices from this graph
In the path between each pair of chosen K vertices there has to be at least L vertices, i. e. there has to be a "space between" each two of chosen vertices made of at least L vertices.

The above of course may not be possible for a given instance of a problem, then I have to check that. I'm quite sure that this problem is NP or even NP-complete, since it has to do with paths with length constraint. Have you ever met a similar problem? Do you have an idea how to reduce it to some more well-known problem, possibly NP, e. g. vertex cover or graph coloring?

Also, note that my graph is a grid graph, which might not be "full" but a subgraph of a full rectangular grid.


texts: Covering a directed graph with particular requirements

texts:
I'm actually trying to solve a task from an old OII (Italian national pre-IOI competition) in which I'm given an unweighted directed graph $G$ with $N$ vertices and $M$ edges and I'm asked to find a set of vertices $S$ which satisfies these conditions.
If we call $S^1$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S$, there can't be any vertex in both $S1$ and $S$.
Then we call $S^2$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S^1$.The set $S$ is a solution to this problem only if every vertex in $G$ is part of at least one of the sets above.
Couldn't think of anything better than an $O(2^n)$ solution, which leads to TLE. I'm given a time limit of 3 seconds, with $N < 1000$ and $M < N(N-1)/2$.

Something I realized is that I have to consider each different connected part on it's own and some vertices simply must be part of $S$ (if there are no edges starting from another vertex that reach them), but this assumptions didn't help much.

I apologize for my english and my poor computer science knowledge, I'm sure some parts should be reformulated but I couldn't find the right words to do that.


texts: Reducing integer-rooted polynomial to natural-rooted polynomials

texts:
First of all, let me define $Dioph(M)$, where $M$ is a set of numbers:
$$Dioph({M})=\{p \mid \text{ $p$ is a polynomial with integer coefficients  and the  zeros of $p$ are in ${M}$}\}.$$

Let $p \in Dioph({Z})$ and  $q\in Dioph({N})$.

I am trying to find a (computable) reduction $f$ from $Dioph(Z)$ to $Dioph(N)$.

My idea for the reduction is as follows. Let $p$ be a polynomial with $k$ variables. There must be a $k$-tuple $(a_1,\dots,a_k)$ so that $p(a_1,\dots,a_k)=0$. I define
$$f(p(x_1,\dots,x_n)) =(x-|a_1|)(x-|a_2|)\dots(x-|a_k|).$$

When I try to prove that $p \in Dioph(Z)$ iff $f(p) \in Dioph(N)$, I have trouble reconstructing $p$ from $f(p)$. I would appreciate any hints.


texts:
Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible.
The following constraints are known:

Each of the two to six squares consists out of 4 vertices (a vertex being a 3D-vector). The vertex-data are stored in such a way, that every vertex can be clearly assigned to it's respective square.
Each vertex is an extreme point of the set (they must all be part of the convex hull).
During the creation of the convex hull vertices may not be connected to other vertices from within the same square (otherwise the squares would "degenerate").

Is there an especially fast/efficient way to create a convex hull for this very specific geometry?
EDIT: For the sake of clarity, with "convex hull" I actually mean a hull in the sense that all vertices have to be connected to form some way of surface topology (e.g. triangles).


texts: Finding a function which is a mapping reduction of A to B

texts:
How do I precisely define the function which is a mapping reduction of A to B for the following examples?

What is the process of figuring this out?

Given: A and B are languages over the alphabet {0,1}.

Examples:

A is the language described by 1*0*, B is the language described by 01*0*
A={w | the length of w is even}, B={w | the length of w is odd}
A=B={w | the length of w is even}
A={0,1}*, B={00,1,101}

I am studying this material and I am not sure of how to 'precisely' define these functions. Could somebody provide me with solutions and a methodology to finding the solution?


texts:
I'm having trouble grokking Cormen's Algorithms book on pg. 120.  The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up:

  "Let X be the random variable whose value equals the number of times we hire a new office assistant."

and later on:

  "...we let $X_i$ be the indicator random variable associated with the event in which the $i$th candidate is hired ... [so that] $X = X_1 + X_2 + \ldots + X_n$"

In particular, Cormen defines $X_i$ as follows:

$$
  X_i =
  \begin{cases}
    1 & \text{if candidate $i$ is hired} \\
    0 & \text{otherwise}
  \end{cases}
$$

Question: Why does $X = X_1 + X_2 + \ldots + X_n$?

First, this equation only makes sense if $X$ and each of the $X_i$ have the same domain. Here I'm assuming the domain of $X$ is $\{1,2, \ldots , n\}$ (i.e., each number representing the number of assistants hired).

That implies that the domain of each $X_i$ must be $\{1,2, \ldots , n\}$. Then it seems that, i.e., $X_2$ will satisfy $X_2(2) = 1$ and be $0$ everywhere else.

But if that's the case, then $X_1 + \ldots + X_n$ will satisfy $X(i) = 1$ for all $i \in \{1, \ldots , 6\}$, which means that $X \ne X_1 + \ldots + X_n$ (since, for example, $X(2) = 2$). What am I missing?

EDIT: The more I think about it, the more I'm convinced that my misunderstanding lies with the way $X$ itself is defined. Is it true that i.e. $X(2) = 2$?


texts: How to prove if an algorithm is reentrant?

texts:
I think, maybe some formalism could exist for the task which makes it significantly easier.

My problem to solve is that I invented a reentrant algorithm for a task. It is relative simple (its pure logic is around 10 lines in C), but this 10 lines to construct was around 2 days to me. I am 99% sure that it is reentrant (which is not the same as thread-safe!), but the remaining 1% is already enough to disrupt my nights.

Of course I could start to do that on a naive way (using a formalized state space, initial conditions, elemental operations and end-conditions for that, etc.), but I think some type of formalism maybe exists which makes this significantly easier and shorter.

Proving the non-reentrancy is much easier, simply by showing a state where the end-conditions aren't fulfilled. But of course I constructed the algorithm so that I can't find a such state.

I have a strong impression, that it is an algorithmically undecidable problem in the general case (probably it can be reduced to the halting problem), but my single case isn't general.

I ask for ideas which make the proof easier. How are similar problems being solved in most cases? For example, a non-trivial condition whose fulfillment would decide the question into any direction, would be already a big help.


texts: Combinator terminology: What is "strong" about strong composition?

texts:
A strong composition operator seems to be very fundamental. (Hindley and Seldin use the notation S for "strong" composition combinator). It abstracts the pattern $f(x, g(x))$, i.e. a direct and a $g$-mediated effect of $x$. It's probably my inexperience but, why is this "strong"? Is it because normal (weak?) composition looks like a special case of this (where $f$ just ignores the argument $x$)?
I'm probably cheating and squeezing in another question here, but is there an intuition for why this form of composition seems to be the more fundamental one in combinatory logic?


texts: Find a non-minimal sequence of elements covering the support set

texts:
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{supp}(s) = \left\{ x \in \mathbb{N} \;|\; x \in s \right\}$, the support set for $s$.

We are interested in obtaining a supporting sequence $s'$ of elements such that  $\text{supp}(s) = \text{supp}(s')$; in other words, we want a sequence of elements, in any order and possibly with repetitions, with appearances of all of elements appearing in $s$ (and no others).

The minimum such sequence is any ordering of the actual support set for $s$. But - we don't need the minimum itself. In fact, we are given a size bound $m$, and must produce an $s'$ with $|s'| \leq m$.

What algorithmic approach would you suggest for producing $s'$, which would have meaningfully better than just obtaining the exact support set - in terms of worst-case time complexity?

This question is related to this one.

Notes:

The algorithm is not limited to just comparisons (so hashing is on the table if you like).
Obviously, the complexity cannot be any better than $\Theta(n)$, since you have to actually read all the input; and it can't be worse than $\Theta(n \log(n))$, with which complexity you can just obtain the exact support.
Constant-factor improvements are significant, e.g. fewer reads of each element, even if the $O(\cdot)$ or $\Theta(\cdot)$ class might be same. I'm hoping for something that depends on $m$ or $m - |s'|$ obviously.


texts:
Let $A,B$ be two languages, for which we know:

$A \in PSPACE$
$A\le_LB$

Can we conclude from the above that $B \in PSPACE$ ?

I think the answer is no, however I don't know how to prove it. I guess I have to write a reduction that proves otherwise, but how?
Thank you!


texts:
I am trying to generate a type of logic puzzle called starbattles. The puzzles consist of an nxn grid that is divided into n distinct regions. The rules of the puzzle are to place stars in the grid such that there are k stars in each column, row, and region of the puzzle. No stars may be adjacent to one another either vertically, horizontally, or diagonally.

Here is an example of 10 x 10 starbattle puzzle where k = 2.

I have been trying to come up with an iterative way of generating all potential starbattle grids, on which I can then use a backtracking based solving algorithm I wrote to verify that there exists a solution and that solution is unique, to confirm that a legal puzzle has been created. I am at a loss for how I can generate more that a small subset of all possible region divisions.

At the moment my approach consists of picking n random points on the grid, and then using a randomized flood fill to allocate the regions. This works and I can generate legal puzzles using it, however I feel there has to be a systematic way of generating all legal grids.


texts: What is the point of this lambda expression?

texts:
Let's take this lambda expression : $\lambda\:x \:\ast\:x\:2$ that "computes" x * 2.

From what I understand, $\ast$ is a constant operator, but since its nothing else than a symbol, how does that let us compute the multiplication x * 2?

I would have thought that we should have defined $\ast$ as some sort of recursive function for instance, but I can't understand why this is a constant and what is the point of using it if it doesn't directly compute the multiplication?

Thank you


texts: Finding a 4-clique among $k$ node groups

texts:
Given a connected graph $G = (V,E)$, assume that there are partitions $\{p_0, p_1, ..., p_k\}$.
Denote the partition set of a vertex $v \in V$ as $p(v)$.
The neighborhood of a vertex $v$ is denoted as $N(v)$

I need to find a 4-clique $V' = \{v_0, v_1, v_2, v_3\}$ such that the total degree of $V'$ is maximum and $\forall v_i, v_j \in V', p(v_i) \neq p(v_j)$.

Is this an NP-Hard problem?

The most straightforward method that comes to my mind is:

pick $v \in V$ with maximum degree.
pick vertex $w \in N(v)$ with maximum degree
pick vertex $u \in N(w) \bigcap N(v)$ with maximum degree
pick vertex $x \in N(u) \bigcap N(w) \bigcap N(v)$ with maximum
degree

Is there any more efficient way to do this?


texts:
Let we have oracle machine. Oracle get boolean formula and answer OK if this formula is feasible. How to explain that we can find satisfying assignment for any formula for polynomial time.

I have аn idea, but I'm not sure it is right.

Let we have formula $~f: \{0, 1\}^n \to \{0, 1\}$ with $n$ parameter and oracle $\Theta$. And we know that $\Theta(f) = 1 $, i.e $f$ is feasible. Then let's check following : if $\Theta (f(1, \dots)) = 1$ then go on to find satisfying assignment i.e check value of $\Theta (f(1, 1, \dots))$ or $\Theta (f(1, 0, \dots))$ else then $\Theta (f(1, \dots)) = 0$ and we also go on to find assignment in same way. Thus, we probably can find satisfying assignment, but I'm not sure.
Am I right? If not, could you give me any tips?


texts:
Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
I have tried to find a pushdown automata and it turned out to be a non-deterministic one.


texts: Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

texts:
I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially taking exponential time (2^P(n) where P is polynomial).

Moreover, can it be generalised to EXPTIME in general?

The reason I am asking this is that I wrote some programs to solve degenerate cases of an NPC problem, and they can consume very large amounts of RAM for hard instances, and I wonder if there is a better way. For reference see https://fc-solve.shlomifish.org/faq.html .


texts: Is this the correct answer for the cardinality of this set?

texts:
This is a question from a practice quiz at my university.

Is the question asking for the cardinality of Σ1 = {a,b} to the power of four?
if that's the case, then the set would still have a cardinality of 2 since elements in a set are unique. It wouldn't be {a,b,a,b,a,b,a,b} right?


texts: How to design a top-1 select algorithm to maximize a variable and minimize other variable?

texts:
I want to implement an algorithm thats select the best group, which maximize the variable A and minimize the variable B.

For instance, I have the following groups:

G1 - A = 10 B = 2

G2 - A = 10 B = 3

G3 - A = 12 B = 1

G4 - A = 10 B = 4

and so on...

One solution could be the sorting the groups by A and resolve ties by selecting the B, but this is not the case here.. it is a tradeoff. I need to select a group with a good tradeoff.
How can I do this tradeoff? any suggestion?


texts:
i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort).

However it is mentioned that the A[i]  has to be a permutation of [1, 2, ..., A.length].

My question is, what if A[i] is not a permutation of [1,2,..., A.length]?
How to solve that?


texts: Generalisation of pancake sorting with arbitrary flipped slices?

texts:
In pancake sort, the primary operation is: flip all pancakes above a given position. What about flipping all pancakes between two given positions? Anybody knows if this has been studied?

To illustrate the problem, here is a quick brute-force, greedy implementation in Python 2.7 (not quite sure it always converges though):

def sort(a):
    entropy = 0
    for i in range(len(a) - 1):
        entropy += abs(a[i] - a[i+1])
    while True:
        max_improvement = 0
        for i in range(len(a) - 1):
            for j in range(i + 1, len(a)):
                improvement = 0
                if i > 0:
                    improvement += abs(a[i] - a[i-1]) - abs(a[j] - a[i-1])
                if j < len(a) - 1:
                    improvement += abs(a[j] - a[j+1]) - abs(a[i] - a[j+1])
                if improvement > max_improvement:
                    max_improvement = improvement
                    (next_i, next_j) = (i, j)
        if max_improvement == 0:
            if a and a[0] > a[-1]:
                a[:] = a[::-1]
                print a
            return
        entropy -= max_improvement
        a[next_i:next_j+1] = a[next_i:next_j+1][::-1]
        print a

a = [7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
print a
sort(a)

Output:

[7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
[7, 6, 8, 3, 1, 0, 4, 9, 2, 5]
[7, 6, 8, 9, 4, 0, 1, 3, 2, 5]
[7, 6, 8, 9, 4, 5, 2, 3, 1, 0]
[9, 8, 6, 7, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


texts: Determine inner angles of twisted polygon

texts:
Is there any way to determine inner angle of twisted polygon? (Here's a picture of "normal" and "twisted" polygon http://courses.be.washington.edu/ARCH/481/1.Tapestry%20Reader/1.Data/6.Problems/graphics.invis/fulltwist.gif )

I know how to determine inner angle of polygon if I know its orientation (CW or CCW), however twisted polygon changes orientation after intersection, so if I check angle for CCW orientation, the CW part will have inverse angle values.

I thought about using winding numbers algorithm and see if values are negative or positive, but it is too slow to check that for every angle.


texts:
This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).

The proof makes a case that considering path $p$ is the shortest path that connects a vertex in set $S$ (set of vertices where the distance of nodes to node $s$, the starting node, is minimal) to  a vertex in set $u$ in $V-S$. It then considers the first vertex as $y$ in set $V-S$ along the path $p$. It argues that $y.d \leq u.d$ which is intuitive as $y$ precedes $u$ in set $V-S$. The second argument that since both $u$ and $y$ were in $V-S$ when $u$ was chosen thus $u.d \leq y.d$. I have following two doubts about the second argument:

Why were $y$ and $u$ both in $V-S$ when $u$ was chosen? We know by our construction that when both $u$ and $y$ are in $V-S$, then $y$ will be chosen before $u$.
The node $u$ is chosen such that when it's added to set $S$ it is not at the minimum distance from node $s$. How is this used in this proof?


texts: Finding square root without division and initial guess

texts: I am trying to look for a division-free algorithms which finds square-root using only addition and multiplication operations, with the initial guess as the number itself. Is there any such algorithms ?


texts:
We are given an interval $I$ and several points $p_1,p_2,...,p_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within the interval can be monitored by the corresponding sensor. The sensors may not have the equal range.

Given the current positions of points and sensors, some (or maybe none) points in $I$ may not be monitored by any sensor. We would like to ask the following question:

  Given a distance $\delta$, is it possible to shift each sensor (to the left or to the right) by a distance at most $\delta$, such that every point in $I$ can be covered by some sensor?

PS: I tried to solve this by greedy algorithm. But there is always an exception to any greedy paradigm I came up with. If we want to cover the whole interval with the sensors, I am sure it can be solved by greedy algorithm. But if we only want to "monitor" finite discrete points, is there an efficient algorithm?


texts: Design considerations of datatypes in early programming languages like C

texts:
Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very engineering-oriented approach. For example, it may have more to do with CPU/bus width than the correctness of reasoning in a program.

Is my guess true? What are the considerations for data types in C, Pascal, ALGOL 68, etc? Any early design documents?


texts: Recursive Selection of Pivot from an Array

texts:
Suppose we have an array of integers $A$ of length $n$, which is assumed to be multiple of 5 for convenience in the discussion below. Now we try to pick a pivot $x$ from $A$ such that $x$ can divide $A$ into two relatively balanced subsequences. Below is the procedure:

Divide $A$ into groups of 5 elements each: for each $1\leqslant i \leqslant n/5$, the $i$- th group should be
$$
A[5(i-1)+1], A[5(i-1)+2], A[5(i-1)+3], A[5(i-1)+4], A[5(i-1)+5]
$$
Find the median of each group directly and denote the median for the $i$-th group by $C_i$.
Recursively select the median $x$ out of $C_1,...,C_{n/5}$.

Also, it is said that

If $x$ is the pivot picked, then both the number of elements smaller than $x$ and the number of elements larger than $x$ is at least $3n/10$.

My question is, how is this lower bound derived? Any formal proofs, ideas, or hints will be greatly appreciated! :)


texts: Algorithm for generating sorting instructions

texts:
Let's say I am to sort a bookcase given a certain sorting condition, for instance alphabetically. I am looking for a way to generate a step-by-step guide on how to do this sorting based on the original order, as well as the final order.

Original order:

B C A D

Final order:

A B C D

Generated step by step instructions (by index):

0 -> 2
0 -> 2

The problem is, of course, each step will alter the sorting order, requiring the algorithm to take into account the new state of each order.

Is there such an algorithm readily available?


texts: Find which bundles can be demanded together

texts:
This question comes from economics. There is a market $M$ that contains $m$ items. There is a value function $v:2^M\to \mathbb{R}$, that assigns a monetary value to each "bundle" (- subset of $M$). The function is given by $2^m$ values - a value per bundle.

A price-vector $p$ is a vector that assigns to each item $x\in M$ a non-negative price $p_x$. Given a price-vector, the net utility of a bundle is its value minus its price, i.e:

$$ u(X) = v(X) - \sum_{x\in X}p_x$$

A bundle is called demanded if its net-utility is maximal - no bundle has larger net-utility.

A pair of bundles is called a demand-pair if there exists a price-vector such that both of these bundles are demanded (i.e, they have the same net-utility and it is maximal).

I am looking for an algorithm that receives the valuation $v$ and finds all demand-pairs.

For example, suppose there are $m=2$ items and the valuation function is:

$v(\emptyset)=0$, $v(\{x\})=2$, $v(\{y\})=3$, $v(\{x,y\})=4$.

Then:

$\{y\}$ and $\{x,y\}$ are demand-pairs, because when $p_x=1,p_y=0$, both these bundles have net-utility 3, which is maximal.
$\{\emptyset\}$ and $\{x,y\}$ are not demand-pairs, because if they have the same net-utility, then this utility must be 0. Then, necessarily $p_x+p_y=5$; but then either $p_x<2$ or $p_y<3$; but then either $\{x\}$ or $\{y\}$ (or both) have a net-utility of more than 0, so $\emptyset$ is not demanded.