texts: What do you call a "non-probabilistic Bloom Filter"?

texts:
One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.

It is a technique for caching easy answers for a subset of an input domain before falling back to an expensive computation. In that respect it reminds me of the semantics of a Bloom Filter or the pre-optimization idea of a Karnaugh Map.

Simple description w/ pseudocode:

// Determine whether "foo" is true with respect to the given ComplexThingy,
//   for the inputs bar and baz

boolean isFoo(ComplexThingy t, A a, B b):
    // Let's say A and B are enums, or ints in a limited range, etc.
    return expensive_computation(t, a, b)

// Alternative implementation w/ enhanced ComplexThingy for which
//   "trivial" cases (i.e. those that can ignore all but one dimension of the
//   input space) have been precomputed and stored in a simple bit array

boolean isFoo(ComplexThingyV2 t, A a, B b):
    if t.quickPosLookup[a]
        return true
    if t.quickNegLookup[b]
        return false
    return expensive_computation(t, a, b)

Hopefully I've been able to convey that clearly. Thanks for your time!


texts: Proof-sketch on the language accepted by a Turing machine

texts: Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$


texts: In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a transition could be triggered by a set of events, such as receiving any one of some set of characters?


texts: Time complexity of art gallery-like problem

texts:
Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ such that every vertex in $G$ is being "watched" by some watchman. More formally, we'd like to decide whether there exists a $w$-sized watch set $W \subseteq V$ (with $|W| = w$) such that for any vertex $v \in V$, either $v \in W$ or there exists a (directed) edge in $E$ of the form $(u, v)$, with $u \in W$.

I'd like devise a deterministic polynomial time algorithm for deciding whether, for a given $w \geq n/2$, where $n$ is the number of vertices in $G$, $G$ has a $w$-sized watch set $W \subseteq V$. So the decision problem would be $\{\langle G, w \rangle : w \geq n/2 \mbox{ and } G \mbox{ has a size } w \mbox{ watch set}  \}$.

One approach I'm considering is finding, in polynomial time, a minimum edge covering for $G$. If the size of this edge covering is strictly larger than $w$, then we know a size-$w$ watch set does not exist; otherwise we can easily construct a watch set from this edge covering. However, the polynomial time edge-covering algorithms I've seen are a bit complicated, so I'm looking for a simpler approach.


texts: The fastest algorithm for intersection of two sorted lists?

texts:
Say that there are two sorted lists: A and B.

The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different).

What is the known to be the fastest algorithm for this functionality?

Can any one give me an idea or reference?


texts: Enumerate All Possible Strings Over Alphabet

texts:
I am given the following decision problem:

A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$.
It is guaranteed that $\Pi$ terminates on any input. Does there exist a pair ($I_1,I_2$) of strings such that $\Pi$ terminates on ($I_1,I_2$) with output value $true$?

It is clear that $\Pi$ is semi-decidable and to proof this, I am asked to give a semi-decision procedure. However, how do I enumerate all possible pairs strings? Or how do I enumerate all possbile (single) strings in general? Of course, such a program may never terminate, but that is no problem because I am only asking for semi-decidability.

EDIT2: Solution (Java)


texts: Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$

texts:
Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number of nodes that are present in the list $L(u,d)$.

Prove that the sum of $|L(u,d)|$ over all distinct lists $L(u,d)$ is bounded by $\mathcal{O}(n\sqrt{n})$.

My work

Consider all $L(u,d)$ such that the left most node on the level $Level(u) + d$ is some node $v$. The pairs $u, d$ for all such $L(u,d)$ must be distinct and the sum of all $d_i$ will correspond to the number of nodes $x$ in the tree with $Level(x) \le Level(u) + d$.

This is because if some sequence of nodes $v_1, v_2, \dots v_k$ corresponds to the descendants of some node $u$ at a distance $d$ and the sequence of nodes $v_1, v_2, \dots v_{k'}$ where $k' > k$ corresponds to the descendants of some node $u'$ at a distance $d+1$, then there must also exist a node $u''$ such that $L(u'', d) = v_{k+1}, v_{k+2}, \dots v_{k'}$. This would also mean that $u''$ is not in the subtree of $u$ and thus there are at least $d$ distinct nodes in the subtree of $u''$ upto a distance $d$ from $u''$.

If the distinct distances are $d_1, d_2, \dots d_k$ then, $n \ge \sum_{i}d_i \ge \sum_{i=1}^{k}i \ge \frac{k(k+1)}{2}$. =

$\implies k \le \sqrt{n}$

After this I tried to show that there can be only $\mathcal{O}(\sqrt{n})$ distinct lists $L(u,d)$ so that I can then trivially obtain the upper-boud of $n\sqrt{n}$ but I could not make any more useful observations.

This link claims that such an upper bound does exist but has not provided the proof.

Any ideas how we might proceed to prove this?


texts: computer science in the movies as an educational angle

texts:
recently there have been a few questions on teaching CS in both cs.se & tcs.se and there are many high-rated related questions on the two sites on the topic. thinking over the latest one made me realize that a lot of students get exposed to some aspects of STEM through the media (sometimes inaccurately), and one of the most powerful media outlets is movies.

it seems that maybe instead of rolling ones eyes or recoiling from their unrealism, these have some potential and can be used as a teaching tool (aka "teachable moment") by taking them as a student experience to build on, as case studies for students to learn about certain concepts and how the concepts actually work vs the screenwritten, "hollywood" version, ie address (possible widespread?) misconceptions about the field and its essential aspects.

  what are key or compelling movies introducing CS-type concepts and what is accurate/inaccurate about the portrayal? [or is it roughly correct?]

teaching high school TCS tcs.se
what should I do with a bunch of 16/17yr olds to get them interested in CS cs.se


texts: Algorithm to find slope of line with a modulus

texts: Say I have some data which represents a single line, and I want to determine its approximate slope. This data has a known minimum and maximum on the y-axis. When the line crosses the maximum, it re-emerges at the minimum, or vice versa, so there appear to be many parallel lines in the data. Clearly, the feasibility of this is dependent on the sampling rate and the amount of noise in the data. Also, a slope too steep will put the apparent parallel lines too close to each other such that they'd become impossible to distinguish. So, we'll assume that the sampling rate, noise, and slope are all within reasonable limits. Is there a particularly elegant way to approach this problem?


texts:
So when programming with locks as a synchronization primitives you can ensure no deadlock by ensuring that an ordering exists on the locks and that all acquires of the locks happen in that order (which really just needs to be a well founded quasi-order). This lends itself to lots of different kinds of solutions to dead lock. You can bake this into the type system itself by demanding that locks have a number associated with them at the type level and that acquiring a lock demands that an already acquired lock of a higher level be passed to it.

Deadlock can also occur when working with channels however. For instance I could wait on receiving something on a channel and never ever get it. I could also, in the case of $\pi$-calculus get stuck waiting on something to send too. Additionally cycles of waiting to receive things can occur which is more like the deadlock that occurs with locks. This leads me to think that some kind of ordering constraint plus a constraint that rules there not being an active sender/reciver on the other side might be helpful.

Is there a similarly helpful condition one can impose on channels to disallow deadlock? Is there a process algebra (weather it uses channels or not) that does not have dead lock?


texts: Amortized analysis for disjoint sets' find-set(x) function (from CLRS)

texts:
I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic discusses about the time analysis for disjoint set operations using forests with union-by-rank and path-compression heuristics. In particular, I am stuck at Lemma 21.13 (580) for which the "find-set(x)" subroutine is claimed to run at O(alpha(n)) time where alpha(n) is the inverse Ackermann function. I cannot arrive to the conclusion that there is at most alpha(n)+2 nodes in the find path that satisfy some specific conditions. This node count comes from the maximum number of nodes where the level(x) is constant across the find path if my interpretation is correct. I assume it is an obvious outcome of previously proven lemmas. Unfortunately, I am not so bright to validate this result.

Of course, without the details about the potential function, this question cannot be answered. There is a big problem, besides that I cannot elegantly type it out in latex. There is a ton of lemmas that logically weave this proof. So, I assume that you have the text with you. Just in case if all of this is obvious to you, here are the fundamentals.

A really really big function:
1st arg -> subscript (denotes the "level" (the notation also seems to be native within the book))
2nd arg -> superscript (denotes the number iterations of the same function)
3rd arg -> the actual input

$A(0,1, j) = j+1$
$A(k,1, j) = A(k-1,j+1,j) \mid k \ge 1$

its inverse for j = 1:
$alpha(n) = \min\{k : A(k,1,1) \ge n\}$

two auxiliary functions needed to define potential function:
//note that x is the node and x.p is its parent node, x.rank is its rank (the thing that increments monotonically traversing up)

level(x) = max {k: x.p.rank >= A(k,1,x.rank)}
iter(x) = max {i: x.p.rank >= A(level(x), i, x.rank)}

The potential function is then defined as:
//n is node count, q is the qth operation in the system, x is the node

phi(q,x) = alpha(n) * x.rank ; if x is not a root or x.rank = 0
phi(q,x) = (alpha(n) - level(x)) * x.rank - iter(x) ; if x is not a root and x.rank >= 1

Again, I emphasize that this question is really specific about the literature because it is not so obvious as to how all this and the $alpha(n)+2$ path length is necessary to prove the bound. But, I am open to other proofs where the find-set(x) subroutine (the one which compresses the path in after finding the root) is a superconstant.


texts: Select signals for memory mapped into common address space

texts:
I just got a hobby of studying this topic and it is quite intriguing. In one of the books, I came up with the following question:

A computing hardware is to be designed with a processor generating 32bit address for memory. It requires 2GB of RAM, 128MB of EPROM and 1MB of EEPROM, and these are mapped in the memory address space as follows.
EEPROM: 0 to (1M–1) EPROM: 128M to (256M–1) RAM: 2G to (4G–1).
Write the Boolean expressions for the signals EEPROM Select, EPROM Select, RAM Select.

I couldn't find any solution to this and there is hardly any resource on the internet too.
So can anyone explain me, how we write the Boolean expression for such questions? I am aware of boolean logic to logic gates, but I am unable to make anything out of this question.


texts: Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted

texts:
Determine the worst-case complexity (in number of comparisons of two array elements) that allow you to conclude that a given array with n elements is not sorted.

I sort of have a general idea of what is going on. Suppose I have two element array, then make one comparison between these two elements.

If I have three elements, then i compare the 0th index element with 1st index element, sort it, and then compare 2nd index element with whatever is now the 1st element after sorting. Hence, I obtain 2 total comparisons.

Going on this pattern, I believe I will make n-1 comparisons which becomes my worst-case complexity. But of course, this is not a proof. How can I make this mathematically rigorous? Am I on right track?


texts: Complement of Non deterministic Finite Automata

texts:
It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$.

Is it possible to construct such a complement for a non-deterministic finite automation (NFA)? To my knowledge, it isn't.


texts: Find the cheapest combination of raw foods that fulfill nutritional requirements

texts:
I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples allowed) with the lowest total price.

Does anyone have any advice as to how to approach this problem? Is there a certain algorithm that exists that takes in a list of possible items, and finds a permutation that minimizes one property of the item(s), in this case the price, and also makes sure that the sum of each property meets a certain range, in this case nutritional properties like carbs and protein? Any advice is greatly appreciated. Thanks!


texts: Proving closure under complementation of languages accepted by min-heap automata

texts:
This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

  Is HAL closed under complementation?


texts:
Everyone knows code bloat is a real thing, of course.

Everyone knows that programs are getting bigger too (this may be nothing to do with 'bloat' of course - they are more sophisticated, safer or faster even: maybe).

So why can't I find any papers on Google Scholar or in the ACM Library that back up either claim?

Happy to be guided to good search terms because if the papers exist then my searching is poor. My particular interest is in real-time/embedded software but general discussions of the issue are also useful.


texts: What does the $\leq_{\mathrm{P}}$ symbol mean?

texts: What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?


texts:
I am confused about the statement of the Master theorem in CLRS book.

Here is the link of the book CLRS.

In page 94, the theorem, in case 2, states that:

If $\displaystyle f(n)=\Theta(n^{\log_ba})$, then $T(n) = \Theta(n^{\log_ba}\lg n)$.

What if $T(n) = T(n/2) + \Theta(\lg n)$? We have $f(n)=\Theta(\lg n)\neq\Theta(1)$.

I found the slides of the CLRS book in MIT website here where the statement of the theorem looks different in case 2 (page 5).

If $\displaystyle f(n)=\Theta(n^{\log_ba}\lg^k n)$, then $T(n) = \Theta(n^{\log_ba}\lg^{k+1} n)$.

What am I missing here?


texts: How can I get all representations of an n-ary tree that completely "cover" the tree?

texts:
I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover:

Suppose we have the following tree

        1
     /    \
    2      3
   / \    /|\
  4   6  5 7 8
      |
      9

I want to somehow obtain the following:

1
2, 3
2, 5, 7, 8
4, 6, 3
4, 6, 5, 7, 8
4, 9, 3
4, 9, 5, 7, 8

As you can see 1 completely covers the tree because all leaves are underneath it. Similarly 2, 3 covers the entire tree because all leaves are underneath them. This goes for all of them until finally we get to 4, 9, 5, 7, 8 which covers the entire tree because all leaves are underneath (or are them).

Is there an algorithm to do this or a modification of a classic search algorithm that will produce this?


texts: Why are problems in P easy and other problems not

texts:
Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET).

Problems in $P$ are considered easy while others (most likely) are not.

What does easy mean?
I've always thought of hard and easy this way:

Our computing power grows exponentially over time. A problem is called easy if we can solve exponentially more instances of it (in reasonable time) after each time unit. A problem is hard if we can only solve polynomialy more instances of it after each time unit.

I'm well aware of complexity analysis, the definitions and their meaning. I'm trying to propose a reasonable, intuitive and easy to understand explanation of hard and easy. Would the explaination above explain it correctly and would someone who never heard of the subject understand it?


texts:
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, the agents of $S_2$ have the same preference list. The stability constraints can be modelled as follows:

$ 1 \leq \sum\limits_{j'\in F^{\leq}_{j}(i)}x_{ij'} + \sum\limits_{i'\in C^{\leq}_{i}}x_{i'j};$ $ i \in S_1$, $j \in S_2$

where $ F^{\leq}_{j}(i)$ is the set of agents of $S_2$ that $i$ ranks at the same level or better than $j$ and  $C^{\leq}_{i}$ is the set of $S_1$ that are at the same level or better than $i$.

My question is: is there a way to model the stability constraints with a number of constraints in the order $O(n_1)$ rather than $O(n_1 n_2)$? because $n_2$ is very big and we already have a number of columns in order of $O(n_1 n_2)$.


texts: How to prove that DFAs from NFAs can have exponential number of states?

texts: All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. Therefore, its states should be members of the power set of states of the NFA. This seems to indicate that the number of states of the DFA could scale exponentially in terms of the number of states of the NFA. However, I was wondering how to actually prove this.


texts: Intelligent use of XOR operator to find missing number

texts:
I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a description for XOR solution however I can't grasp it in its entirety.
I just can't wrap my head around why we need to initialize missing variable with length of array, why not initialize it with Zero & when we do initialize it with Zero, why can't this algo find the missing number? Can someone please explain it?

Following was my solution before I learned Leetcode suggested XOR solution is even better & faster
class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1)
            return nums[0] == 0 ? 1 : 0;

        int missing = 0;
        boolean tempNums[] = new boolean[nums.length+1]; //cuz one is missing

        for(int i:nums) {
            tempNums[i] = true;
        }

        for(int i=0; i<tempNums.length; i++)
            if(!tempNums[i]) {
                missing = i;
                break;
            }
        return missing;
    }
}


texts: Must $x$ and $y$ be different in a statement of the form $\forall x \forall y \cdots$?

texts:
Given the following predicate formula $F$:

$$\forall x \forall y [(\text{italian}(x) \Rightarrow (\text{winWC}(y) \Rightarrow \text{happy}(x))]$$

I am having trouble understanding whether $x$ and $y$ must be different elements.

Also, I have been given the following statement:

  "Italians are happy if the Italian National team wins the world cup."

How can I prove that this is not equivalent to what is expressed by $F$? Should I bring both in CNF and then somehow argue they cannot be equivalent?


texts:
The definition of vertex cover is as is:
Set of vertices such that each each has atleast one endpoint in that set.

In the above example, why can't we consider all vertices as vertex cover since all vertices are endpoints to all the edges.


texts: If I can use FIFO queue and read/write registers, can I reach wait free 2 set consensus if I have 3 processes? I thought is I can, but I saw a conclusion from text book says "we cannot achieve 2 set consensus on 3 processes in shared memory system", so I'm confused now.


texts: Is the type inference here really complicated?

texts:
There's a question on SO asking why in Java the right type doesn't get picked in a concrete case. I know that Java can't do it in such "complicated" cases, but I'm asking myself WHY?

The (for simplicity slightly modified) line failing to compile is

Map<String, Number> m = ImmutableMap.builder().build();

and the methods are defined as1

class ImmutableMap {
    public static <K1, V1> Builder<K1, V1> builder() {...}
    ...
}

class Builder<K2, V2> {
    public ImmutableMap<K2, V2> build() {...}
    ...
}

The solution K1=K2=String and V1=V2=Number is obvious to everyone but the compiler. There are 4 variables here and I can see 4 trivial equations, so what's the problem with type inference here?

1I simplified the code piece from Guava for this example and numbered the type variables to make it (hopefully) clearer.


texts: Operation with second-order logic formulas

texts:
I have one or more second-order logic formulas that correct for some finity model. What operation can I perform on them, so that resault is also correct for some finity model?

Just conjunction is impossible, example:
$x$ has finity model, $\lnot x$ has finity model, but $x \wedge \lnot x$ has not finity model. Are there any restriction?


texts: Algorithm to find possible variables in multiple connected equations

texts:
I am new here. I am trying to come up with an algorithm that can give me the unknown values in the following equation.

find lowest possible x, y and z whole number variables where:

2x = y+z &&
6y = x+z &&
3z = x+y

I am trying to come up with a formula that tells me:
What are the possible values of the variable x y z. The values must be positive whole numbers greater than zero and should be the lowest possible whole numbers. If the equation is impossible the formula should tell me the same.

I have tried coming up with a couple of formulas but my efforts have bore no fruit.

PS: I am not so conversant with the tags on this site if I have left any out please add.


texts: Can you apply the induction hypothesis to its outcome?

texts:
Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that:

$P$ holds for all minimal elements of $S$.
For every $b \in P$ and $a < b$ we have: if $P(a)$ then there exists $c < b$ such that $P(c) \Rightarrow P(b)$.

Question: does it follow that $P(c)$ holds for all $c \in S$?


texts: Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

texts:
I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different.

All I managed to think of was the example of the knapsack problem, when the sum of all the weights were less than W (max weight). However, in this solution x=x', and I was looking for an example in which they are different.

I am a computer science undergraduate so if you have something I may understand it would be much appreciated.

Thank you


texts:
Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables.
Find $min(Entropy (x_i | k\,variables))$. Value need not be exact, approximate solutions are fine.

However, I am wondering is it possible to find out the solution to the above mentioned problem. Without resolving to enumerate [brute force approach] all possible subsets of size $k$ from remaining $n-1$ variables. And keep a track of the minimum conditional entropy obtained. $Entropy(x_i | Remaining\,variables)$ is the lowest but I intend to get more tighter bound.


texts: How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the accept state, and this action does not change the acceptance outcome.


texts: Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

texts:
i don't understand the following:

If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time.

The algorithm should get a directed graph and a natural k as an input, and output, if there are k edges as needed, a list of k edges, so that the graph obtained from erasing those k edges is cycles. if there are no such k edges, it simply outputs "no".

Question:my question in addition to the answer already given is this part: " then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time." - what can be this algorithm? how to do it using a turing machine?

Problematic part: I can only use an algorithm that decides ACYCLIC, but it is forbidden to use any other NP-Complete algorithms, and it's running time must be polynomial in regards to its input size.

My attempt: well, to check/decide if a directed graph is ACYCLIC or not, we'll visit it topologically using DFS, then using a stack, we'll traverse edges to see if any edge in the digraph leads back to an edge already visited. if already visited - there's a cycle, if not - there's no cycle.

The algorithm: on an input of a directed graph, to check ACYCLIC:

1)finding an vertex that has only outgoing nodes - if such node doesn't exist - return "graph has cycles"

2)on that node, run DFS and traverse the digraph; add each edge found to a stack. if a vertex is shown twice - return "graph has cycles".

3)if no cycles found, accept.

But, I am not sure how to do it in regards to the algorithm required in the problem(first two paragraphs of the questions - basically, returning a set of k edges, so that by removing them, the graph will be cycles.

would really appreciate knowing how to do it.

thank you very much


texts: How to know that the substrings 01 and 10 does not require an infinite amount of memory to count the substrings

texts:
Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory
to “count” the number of 01 and 10 substrings?


texts: Understanding characterizations of Matching on Graphs

texts:
I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.

Definition:
Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching in $G$ if and only if each vertex $v$ in $V$ is incident to at most one edge in $M$, that is,  $\forall v \in V ( \forall w \in V ( \forall x \in V (( vw \in M \wedge vx \in M) \rightarrow w = x)))$ holds.
Edges may be weighted.
For any matching $M$ and weight function $w: E \rightarrow \mathbb Q$ we define $w(M) := \Sigma_{e \in M} w(e)$.

In the following are the definitions of the two computational problems I am currently working with.
For simplicity sometimes I use bipartite graphs only.

Problem Name: $\text{MAXIMUM-CARDINALITY MATCHING}$

Input: A graph $G = (V, E)$.

Task: Find a matching $M$ such that $|M|$ is maximum.

Problem Name: $\text{MAXIMUM-WEIGHT BIPARTITE MATCHING}$

Input: A bipartite graph $G = (V, E)$ with weights $w: E \rightarrow \mathbb Q$ on the edges.

Task: Find a matching $M$ such that $w(M)$ is maximum.

Definition:
A path $P$ in $G$ is called $M$-alternating if and only if the edges in $P$ are alternatingly out of and in $M$.

Definition:
A path $P$ in $G$ is called $M$-augmenting if and only if $P$ is $M$-alternating and both its end vertices are not covered by $M$.

Thoerem (I think it is due to Peterson):
Let $G = (V, E)$ be a graph and let $M$ be a matching in $G$.
Then either $M$ is a solution to $\text{MAXIMUM-CARDINALITY}$ $\text{MATCHING}$ or there exists an $M$-augmenting path.

Theorem (Egervary):
Let $G = (V, E)$ be a bipartite graph and let $w: E \rightarrow \mathbb Q$ be a weight function.
Then the maximum weight of a matching in $G$ (that is, the weight of a solution to the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem) is equal to the minimum value of $y(V)$, where $y : V \rightarrow \mathbb Q$ is such that $y_u + y_v \geq w_e$ for each edge $e = uv$.
If $w$ is integer, we can take $y$ integer.

My question is: Does there exist a simpler characterization of the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem similar to Peterson's Theorem?
What is wrong with the following characterization?

First, let $A \; \Delta \; B$ denote the symmetric difference of two sets $A$ and $B$.
Further, if $P$ is a path, then let $E(P)$ denote the set of edges in $P$.

Hypothesis:
Let $G = (V, E)$ be a bipartite graph, $w: E \rightarrow \mathbb Q$ a weight function, and $M$ a matching in $G$.
Then either $w(M)$ is maximum or there exists an $M$-alternating (note: not necessarily $M$-augmenting) path $P$ such that $M' := M \; \Delta \; E(P)$ is a matching in $G$ and $w(M') > w(M)$.

Is the hypothesis correct? If not, why is it wrong? What about the hypothesis with respect to non-bipartite graphs? If the hypothesis is correct, why is always Egervary's Theorem used?


texts: Empirical evidence for the Church-Turing thesis in other disciplines

texts:
I am aware of the fact that, since the concept of "effectively calculable function" is not rigorous or formally definable, the Church-Turing thesis may not be proven by symbolic or formal reasoning alone.

My impression, though, is that under the domain of physics, philosophy, cognitive science or other disciplines, we may find empirical evidence that gives us a strong reason for accepting it, for instance in the field of numerical cognition. Even if those disciplines are not directly related to computer science, the importance of this thesis in CS make this, in my opinion, an important issue to consider for us; that's why I'm asking this question here. (If you feel like there are better SE suited for this questions, let me know please.)

So, what is the current state of the research for evidence to support the Church-Turing thesis? Are there any recent developments?

A good answer would also provide a list of all the major efforts to this day to empirically validate or refute the CT-Thesis, and the main problems posed by this issue. Investigations on the notion of "effectively calculable" in cognitive science, or what does it mean to "compute" in physics are also welcome.


texts: Linear programming formulation for the single-source shortest path problem

texts:
In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP):

\begin{align}
\max &\sum d_u \\
\text{subject to} & \\
d_v &\le d_u + l_{uv} \quad \forall (u,v) \in E \\
d_s &= 0
\end{align}

The comment on the objective function is as follows (emphasis added):

  The variables $d_u$ represent the distances from $s$ to each vertex $u$. Maximizing the sum of the $d_u$ is done by maximizing each one individually, since increasing any single $d_u$ never forces us to decrease some other $d_v$.

I can get its basic idea. However, how to argue that $(\max d_u \;\forall u \in V)$ is equivalent to $(\max \sum d_u)$ more rigorously? Specifically, why is that "increasing any single $d_u$ never forces us to decrease some other $d_v$"?


texts: Trying to understand this Dynamic Programming solution

texts:
The problem is as follows.

Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq m$.

So, we can use two list of indexes $\ I$, $J$, such that $I\subseteq [n]$,  $J\subset [m]$, and $|I|=|J|=n$. The notation is $[m] = \{1,2,3,\cdots, m\}$.

Therefore, our goal reduces to:

$$ \min_{k=1,2,\cdots, n}  \{|a_{i_k} - b_{j_k}|\ : i_k\in [n],\ j_k\in J\}.$$

I found the problem above in this question (in other words) and trying to understand how the answer provided there, it attempts to solve the problem with dynamic programming.

This is what I understand:

I believe we are building two indexes and are pairing them.
We first sort boys by height
Somehow we then construct a match, but it's not greedy, is it? it utilizes calculating the sum of the absolute difference in height. How was the pairing constructed?

This paragraph is key and I would love to understand it but I don't get it:

you can use dynamic programming to find the optimal matching by building up
optimal matchings that have the first j boys in sorted height order all
paired up somehow among the first k girls in sorted height order (where
j≤k), and using the optimal matchings for the values (j,k−1) and (j−1,k−1)to
decide the optimal matching for the values (j,k), based on whether you pair
up boy j with girl k or not.

So, the question is how the dynamic programing method is working here based on the answer given and pseudo code of the solution it would be helpful.


texts: Calculating positions of nodes relative to a known point

texts: If I know all the distances between a set of nodes and I also know that one of the nodes is at location (0,0), using the distances between the nodes, can I calculate the absolute positions between all of the nodes? I feel that this will involve some form of trilateration but only a single node position is known. Will I need an iterative algorithm to eventually find a unique solution?


texts: How does a File System handle an internal edit to a file?

texts:
When you edit information in a file, but you add in more information than was already present, how does the file system handle it without an overflow into the next section of the file?

Here's an example. Consider having statements 1-12 in a 512-byte block, and you had statements 13-24 in the next 512-byte block. [Image 1] These blocks are both part of the same file. If you edited the first block, so you add another few New Statements [Image 2] past statement 12, this would overflow into the next block (statements 13-24). How would this condition be handled? Through shifting all the statements ahead of the added statement forward, or putting the new edit in a completely separate new block?

(sorry if the pictures or wording are a bit improper; this is my first time)


texts: I have  an option to learn a new language for parallel computing.  As a parallel programmer what are the reasons one might want to invest time to learn functional programming for parallel computing?


texts:
I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to minimize this number. For example:

1 3 5 9

if k=2, I would partition them into (1 3 5) and (9), the sum of squared error of (1 3 5) is (3-1)^2+(3-3)^2+(5-3)^2=8 and the sum of squared error of (9) is 0. So the total sum of squared error is 8. I think 8 is the minimum sum of squared error in this case.

I want to use the traditional prim's method to solve this problem. i.e. to use connect n-k edges, then stop. But the problem is whenever I add 1 more integers to the subset, the mean changes. So, it seems that I cannot use Prim's method...Anyone give me some insight on this? Thanks!


texts: Why isn't TQBF part of the polynomial hierarchy?

texts:
TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it?

I think this is incorrect because TQBF consists of any number of quantifiers, but each level in the PH has fixed number of quantifiers, so there's no level of the PH that can solve TQBF. Does it have to do with the fact that the number of quantifiers is part of the input in TQBF, whereas in PH only the formula is the input?

So this could also be worded as, if there exists a PH-complete problem, does TQBF reduce to that problem?


texts:
Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is
$${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be
$$P(\mathit{assignment~is~unsatisfiable}) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.


texts: Synchronizing sequence and Synchronizable DFA

texts:
I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A Synchronizing sequence for $M$ and $q'$ is a string $s\in \Sigma^*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
Say that $M$ is Synchronizable if it has a synchronizing sequence for some state $q'$.
Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$. Moreover, can you improve upon this bound?

I'm more interested in proving that the synchronized sequence is of length of at most $k^3$ then trying to improve upon this bound.
I tried to prove (with no success) that there exists $w\in \Sigma^*$ which $|w| \leq k^2 $ so that: $\delta(q_1,w)=\delta(q_2,w)$ for two distinct states in $M$: $q_1,q_2\in Q$ (thus, $w$ can be read from two states in the automaton and get to the same final state).
If I prove it, I could construct a word $w$ which will be a synchronizing sequence in $M$ and $|w|\leq k^3$ as required.
Any suggestions?


texts: Is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node represent?

texts:
this book "Fundamentals of Python: Data Structures 1st Edition" says

  data items in hierarchical collections are ordered in a structure
  resembling an upside-down tree. Each data item except the one at the
  top has just one predecessor
  ...
  A file directory system, a company's organizational tree, and a book's
  table of contents are examples of hierarchical collections

each hierarchical collection has a root node, is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node (one at the top) represent?


texts: Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

texts:
Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$.

This problem is undecidable. To prove this, assume the contrary. We define a term $s$ as follows:

$$s x \equiv \lambda n.j. j y$$

if $x$ is an encoding of the configuration of a Turing machine and $y$ is the encoding of the configuration the Turing machine transitions into in one step and

$$s x \equiv \lambda n.j. n$$

if $x$ is an encoding of the configuration of a Turing machine that has halted.

Now define the term $t_M$ as follows:

$$t_M := Y (\lambda f.x. s x (\lambda a.b. b) f) i_M$$

where $i_M$ is the encoding of the initial configuration of $M$, and $Y$ is the fixed point combinator.

If $M$ halts, $t_mv \equiv (\lambda b. b)$. Otherwise, $t_mv$ does not have a normal form, and every term equivalent to it has $v$ in it. Therefore, $\phi(t, v)$ iff $M$ halts. This algorithm can be used to solve the halting problem, which is a contradiction.

On the other hand, it is semidecidable. For any $t$ and $v$, simply enumerate the $t'$ such that $t' \equiv t$. If a $t'$ is enumerated such that $v \notin FV(t')$, output yes and halt. This algorithm outputs yes iff $\phi(t, v)$.

That said, this algorithm is not very efficient, since you have to use an enumeration that enumerates all $t'$ such that $t' \equiv t$. Is there an efficient algorithm to semidecide whether $\phi(t,v)$ is true?

EDIT: We'll say an algorithm for determining $\phi(t,v)$ is efficient if, when $\phi(t,v)$ is true, it halts in an amount of time that is a polynomial of the minimum number of reduction and conversion steps required to eliminate $v$ from $t$.

An approach one might consider is to normalize $t$, and then check if $v$ is free in the result. Although this would be efficient, it would not be correct. For example, this algorithm would not halt on the input $(\Omega ((\lambda a.b. a) \Omega v), v)$ (where $\Omega := (\lambda x. x x)(\lambda x. x x)$), but $\phi(\Omega ((\lambda a.b. a) \Omega v), v)$ is true.

Another approach would be to use some reduction strategy, and then to check after each step if $v$ is free in the term produced by that step. Although I think this is a good direction to take, it should be noted that neither normal order reduction nor applicative order reduction would work. To see this, consider the input $(t_M(t_Nv),v)$. If $M$ diverges but $N$ halts, $\phi(t_M(t_Nv),v)$ is true, but normal order reduction will never eliminate $v$. Likewise, if $M$ halts but $N$ diverges, $\phi(t_M(t_Nv),v)$ is again true, but applicative order will never eliminate $v$.

The input $(t_M(t_Nv),v)$ is rather tricky in general. To solve this input, an algorithm would probably need to attempt to normalize $t_M$ and $t_N$ in parallel, outputting yes if either normalizes. Attempting to normalize $t_M$ first or normalize $t_N$ first will not work.

On the other hand, by the Church-Rosser theorem, we only need reductions, no expansions. We never need to "undo" a reduction step to eliminate a variable. That is because if $t' \equiv t \land v \notin FV(t')$, there is some term that both $t$ and $t'$ reduce to. It will not contain $v$, since $t'$ does not, and reductions never introduce free variables. Since $t$ also reduces to this term, $t$ can be reduced to a term without $v$.

Alpha conversion does not make a difference. It appears that eta conversion is also irrelevant.


texts: Parameter sharing / weight constraints in Neural Networks

texts:
I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as

$w_{i,j} = w_{i',j'}$,

where $w_{i,j}$ denotes the weight from input node $i$ to hidden node $j$ in the case of a network with a single layer. (In the case of several hidden layers, it is okay to assume that only weights stemming from the same layer can be related to each other).

It seems that a special case of this is known as parameter sharing in the context of convolutional neural networks where weights have to coincide, roughly speaking, across different layers.

Surprisingly, it seems that there is not much work / need for more general parameter constraints. Being not a machine learning expert, I am wondering whether I am using the wrong keywords in my literature research.

It would be great if someone could point me towards a tool / framework which allows for linear parameter constraints. Mathematically speaking, I would like to specify a linear subspace of the parameter space and project, at each step of the backwardpropagation, the update vector $\Delta w$ onto this very subspace.

Any help will be greatly appreciated.


texts: Simple question: Pushdown automata transition

texts:
I am currently constructing pushdown automata.
can I push/pop alphabet more than two in a transition??

For example, $\delta$(a, a/aaa) means, in the state of input alphabet 'a' and stack point 'a' (there is only one item 'a') then it can push two more item 'a' on the stack so that there is three a's in the stack.


texts:
I have to  find an  evaluation function  in which   we evaluate the state of the  game in each round.

The  game is  like  " roborally "  ,  it is 2 player-Game in which there are  a board and  cards that decides my movements on each  cards  there is  number of translations , number or rotations.The goal of the game is to  get  all the Flags before the other player does ( there are 4 Flags). \

each player recives 9 cards and can only play 5 cards in one round  and each field have  some special effects ( some are positive and some are negative), so i must find a heuristic that evaluates the movement  i will play. the question how can i find such function .

The colored fields are the  original  board game ,  the  white  fields are only virtual. \

Let  s say we are on the field (6.0) and  we want to go further ( out of the original board) then we lend to (6.13) which is  virutal, but then  we will  go to the real (6.13)  here is an example .

let  say that i am standing on filed (5.12) and the  flag is on field(4.0)
how to use the function to decide in which order  should i play the 5 cards and  which 5 cards from  the 9 cards  should i play

is there any related   game algorithms that might help to find a solution for my problem .


texts: Sample a scale free subnet from random network

texts:
I already have a network which is like random complex network. Is there any way I can delete some of nodes and reduce the network into a scale-free network?

I notice there are some methods that can sample a scale-free subnet from a scale-free network. But I have not found anyone sampled a scale-free subnet from a random network.


texts: Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.


texts:
Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I pass it (or get a high score) I can write up a paper to announce a new state-of-the-art PRNG to the world. Yeah I know that's unlikely, but by saying this I mean I expect a really "strict" test.

I did some searching and Wikipedia points me to TestU01, which is said to be state-of-the-art, but its latest release is in 2009, or nearly ten years ago. I suppose a lot of things have happened since then.


texts: What is different between Set and Type in Coq?

texts:
AFAIU types can be a Set whose elements are programs or a proposition whose elements are Proofs. So based on this understanding:

Inductive prod (X Y: Type) : Set :=
| pair: X -> Y -> prod X Y.

Following code should compile but it does not due to the following error. If I change Set with Type or the other Type with Set it compiles fine. Can someone help me understand what the following error means? I am trying to teach myself Coq using Software Foundations book.

Error:

Error: Large non-propositional inductive types must be in Type.


texts:
I am trying to solve this problem and I am stuck. I think it is B, but I think I'm wrong. Thanks.

Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?

A.  a != b || b != c

B. (a == b || b == c || a == c)

C. a >=b && b >= c && c >= a

D. a > b || b > c || a > c

E. a != b && b != c


texts:
I know that the first instruction stored in BIOS is "mapped" to memory address 0, and that a signal on the reset pin to the microprocessor causes this instruction to be fetched, beginning the POST and all the chain-loading involved in the boot process.

I also know that there is a Memory-Management Unit (MMU?) at the hardware level. Is it in charge of doing this redirect (away from DRAM to the BIOS firmware) so that the processor can interact with the memory of the computer in a blissfully naive way? If so, what other areas (in addition to BIOS) does the MMU map into the total address space?

I know that for modern operating systems with a GUI, the displays are "bitmapped". Does the MMU map a portion of the video RAM on the video card into the global address space as well?

What about virtual memory and paging? Does the hardware MMU have any intrinsic capabilities that facilitate the virtual memory feature provided by the OS?

I may be way off.


texts: Closure under reversal of regular languages: Proof using Automata

texts:
I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

Under the topic of Reversal, they have tried to prove that the regular languages are preserved under the reversal of closure. They have stated the following (for a regular language $E$):

  $E = E^{*}_{1}$. Then $E^R = (E^{R}_{1})^*$

I wasn't able to get their justification so I took the following approach:

Tried to take up an example, say $E_{1} = 01^{*}$
Draw an NFA that accepts the regular expression $E_{1}$
Draw AN NFA that accepts the Kleene's closure of $E_{1}$, i.e. $E = E_{1}^*$
Convert the NFA into a DFA, and reverse the DFA into an NFA to get $E^{R}$.
Reduce the NFA of step 4 to a DFA again.

This is my work regarding the same:

Now for the right hand side, i.e. $(E^{R}_{1})^*$,

Created an NFA that accepts $E_{1}$ and reducing it to DFA
Created an NFA that accepts $E_{1}^{R}$ by reversing
Created an NFA that accepts $(E^{R}_{1})^*$ by taking the Kleene Closure, and then reduced it to a DFA.

This is my work for the second half:

However, the two DFAs I get at the end are not similar. Can anyone help me with the error I might be making?

Plus, how can we prove the same in a way other than DFA/NFA construction?


texts: What's the difference between $O(1)$ and $o(1)$?

texts: What's the difference between $O(1)$ and $o(1)$ ?


texts: Show that the running time of the build_heap function is $O(n)$

texts:
Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$.

heapify(A, i):

Input: array A of length n, index i

left = 2i + 1 (left child node)
right = 2i + 2 (right child node)
largest = i if left < n and A[left] > A[i] then
    largest = left
end if
if right < n and A[right] > A[largest] then
    largest = right end
if if largest != i then
    swap(A, i, largest)
    heapify(A, largest)
end if

build_heap(A):

Input: Array of length n

for i = floor((n-1)/2) to 0 do
  heapify(A, i)
end for

  Hint: Assume that A has $2^j-1$, for $j \in \mathbb{N}$, elements. You can also use the fact that $\sum_{k=0}^{\infty}\frac{k}{2^k} = 2$.

I don't really understand why the formula is given in the hint, or rather how to explicitly use it to prove that build_heap(A) runs in $O(n)$.

I would say that the worst case for the heapify function is given when a call of `heapify(A,0) calls itself recursively as much as possible. I think a binary tree with n nodes has depth of $\lceil lg(n) \rceil $, so the maximum number of recursive calls should be $\lceil lg(n) \rceil $.

I'm not sure but my guess is that the formula is trying to tell me that the running time of heapify is $O(1)$? But I don't really see how that's possible. If it were a constant then clearly build_heap(A) would run in $O(n)$, but how can it be constant?

Can someone please help me out?


texts: Finite representations and programming languages Countably inifite

texts:
I'm going over some of the pre-requisite math regarding Automata theory, and finite representations.

I read the following:

If ∑ is a finite alphabet the set of all strings over the alphabet
(∑*) is countably infinite.
The set of all possible languages over an alphabet ∑ is uncountably
infinite.

How can the set of languages possible from ∑ be uncountably infinite, yet the possible application of that alphabet to a language be countably infinite?

Can I ask those replying to not use too much complex notation, as I'm not a mathematics wizz.


texts: How do solve assignment of one interval to another?

texts:
Is there an efficient algorithm for the following problem?

Input:  Set of holes and pegs.  Each hole/peg is an interval $[\ell,u]$ with integer endpoints.

Question:  Can all the holes be filled using the pegs given, satisfying the following conditions?

Each peg is assigned to at most one hole.
No hole is assigned more than one peg.
If peg $p$ is assigned to hole $h$, then the interval $p$ must be contained in the interval $h$.

Here's a picture to help clarify:

My algorithm: For each hole, check if any peg can be assigned to this hole.

Issues: Unfortunately, this doesn't work.  See Scenario 3 in the picture above: my algorithm assigns the same peg ($[1,2]$) to multiple holes ($[1,2]$ and $[1,3]$), which is not legal.

My second attempt: I tried to construct an algorithm that marks a peg as unavailable it is used.

Let available_pegs = all input pegs
For each hole, check if any peg from available_pegs can be assigned to this hole.
If a peg is found, remove it from available_pegs and assign it to that hole.

Issues:  Unfortunately, this doesn't work either. It can fail in Scenario 2: if I assigned peg $[1,2]$ to hole $[1,3]$, peg $[1,2]$ will be marked unavailable and now there is now way to fill the hole $[1,2]$.  Thus in this example the algorithm would say that there are not enough pegs to assign to all the holes, which is wrong.


texts:
I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:

  It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

Why does encoding in $O(\log k)$ makes it exponential?
How can we reduce the other problems to our halting problem?


texts: Show that the class of regular languages is closed under shuffle

texts:
For languages A and B, let the shufﬂe of A and B be the language
$ \{w| w = a_1b_1···a_kb_k,$ where $a_1···a_k ∈ A$ and $b_1···b_k ∈ B,$ each$ a_i,b_i ∈ Σ^∗\}$.
Show that the class of regular languages is closed under shufﬂe.

Approach: If A and B are regular, then there exists an NFA R and T that recognizes them. I was thinking I could run R and T in parallel, so I would start running R by processing $a_1$ and then by using non-determinism, I would jump to the NFA T to process $b_1$. In this process I make sure that both NFAs aren't executed the original way because that would result in accepted strings that are not in the language, so I try to disconnect the edges in each NFA to jump to the other NFA and then disconnect again the edges of this NFA to come back to the previos NFA.. Is this process clear?

Here is the proof, but some lines are a bit unclear to me.

I can't understand d)i. I don't understand how the transition function works. How does it detect whether we are at DFA A OR B?


texts: is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$

texts:
$L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$

Alphabet = { a , b }*

Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a machine or grammar which accepts this?


texts: Finding the maximum disjoint weight in a weighted node graph

texts:
I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the sum of the nodes. Any graph that contains edges needs to be reduced by removing one of the two nodes on an edge, until all edges are removed and the graph becomes disjoint. After reducing a graph the total weight should be the maximum possible.

I have already tried an algorithm that simply picks the largest node and discards the connected nodes. This has the problem that it may give a total that is too low.

So I need to find a new algorithm that will be accurate more consistently. My current idea is to look at the graph around each node and determine the difference between that node's weight and the total weight of the connected nodes.

Select the node with the largest difference
A positive difference means select the node and ignore the others
A negative difference means ignore this node and select the others
For a difference of zero it's not as clear which side to select
Repeat

At each stage, at least one node (and it's related edges) will be discarded from the graph. Eventually the graph will be made fully disjoint.

Are there any other approaches, and what are the differing costs in terms of time and memory?

Below are some simple examples

Case 1

AA:2, AB:3

No edges, so total weight is 5.

Case 2

BA:3, BB:2, BC:5, BD:2

BB <> BC, BC <> BD

Total weight is 8 (BA + BC)

Case 3

CA:2, CB:3, CC:5, CD:3

CB <> CC, CC <> CD

Total weight is 8 (CA + CB + CD)

My current approach would report 7 (CA + CC)

Case 4

DA:4, DB:3, DC:3, DD:3, DE:4

DA <> DB, DA <> DC, DA <> DD, DC <> DE, DC <> DE

Total weight is 9 (DB + DC + DD)

My current approach would report 8 (DA + DE)

Case 5:

EA:4, EB:3, EC:3, ED:3, EE:4

EA <> EB, EA <> EC, EA <> ED, EB <> EC, EC <> EE, EC <> EE

Note there is complete sub graph between nodes EA, EB, and EC

Total weight is 8 (EA + EE)


texts:
Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$?  Or equivalently, how quickly can we find

$$
\underset{i}{\arg\max} \; \# \{j \mid a_j > a_i, i < j \le n \}
$$

Can it be done in less than $\Omega(n\,\lg n)$ comparisons in the worst case?

A $\Theta(n\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.


texts: Relationship between graph expansion and conductance

texts:
I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is:

Could someone point me to a reference that discusses both of these notions? (I've found various lecture notes on related topics but these seem to focus either on expansion or on conductance...)

I've read that the expansion of $G$ is a measure for the speed of mixing of a random walk on $G$, i.e., the time for getting close to the stationary distribution. For a $d$-regular graph with constant expansion, for example, the mixing time is $\Theta(\log n)$. The same seems to be true for the conductance $\Phi(G)$, i.e., if $\Phi(G)$ is constant, then a random walk on $G$ will also mix in $\Theta(\log n)$ time. Moreover, this property of conductance holds even in non-regular graphs, and, for $d$-regular graphs the expansion of $G$ can be found by simply dividing the conductance of $G$ by $d$. This begs the following question:

Why should we consider the expansion of a graph $G$, when the conductance seems to be a stronger measure (that subsumes expansion)?


texts: Is there an algorithm to share parts of strings?

texts:
Let's say that we have the strings Hello, World, Hello and World. The algorithm I am thinking of would create an immutable buffer that contains Hello, World and the previous three would then become references or slices of that one like buf[0,11], buf[0,4], buf[7,11].

A way to implement this algorithm would be to compare all new strings to the existing buffer and reuse it if possible or append the new string if that's not the case. This would be very slow, but it should work. However, it does not efficiently handle a case like Hey, Hello because it would either append it to the buffer, adding Hello again, or add Hey, to the beginning and update all the indices.

If saving space is the optimal solution, then the final buffer would be Hey, Hello, World.

Is there any algorithm that does something similar?

I have read about ropes, and read this article, but I do not see how these would help.

EDIT: this is indeed a shortest superstring problem, but the implementations I have found (1,2) assume that no string in the array could be a substring of another one, which is not the case here.


texts:
I had this question in an interview recently. I was unable to answer this question and would really like to start a discussion on how to approach this problem and get the most efficient solution.

You have this matrix. You want to print out how many islands are in the matrix. Assume water is surrounding everything outside of the matrix.

An island is any land completely surrounded by water. Land pieces can be connected to form an island as well. As long there is another piece of land in any of the surrounding blocks, that piece of land is considered a part of that island, and yes this includes diagonals.

M = 'land'
o = 'water'

world = [
  [o,M,o,o,o,M,o,o,o,o,o],
  [o,o,M,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

In this example, there are 5 islands.

I attempted to answer this with for loops but was unable to do so as this seems more of a recursive problem. Unfortunately, I am not the most proficient with recursion and would really like to see the thought process you take to tackle this and the running time of your algorithm :).

Feel free to use your favorite programming language. Also If I didn't describe the problem clearly enough just leave a comment and I'll do my best to clarify.


texts:
I'm trying to see if I got these running times right, are these running times for these algorithms correct.

Algorithm 1:

x=0
for  i=1 to n
   for  j=1 to i
      if( i+j > n) return; //so whenever i+j first reaches n, the algorithm stops

Running time I got: O(n)?

Algorithm 2:

x=0
for  i=1 to n
   for  j=1 to n
      x++

 for i=1 to  n^2
    for  j=1 to i
      x++;

Running time: O(n^4)? I think this one is wrong? Please help

x=101 [in binary]
for  i=1 to n
   x = ADD(x,x)   [in binary]

Running time: O(n)?


texts:
If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.

Can someone give a counter example to the claim that if both Q1 and Q2 are c.e. then so is Q1\Q2?

Since H is semi-decidable and hence also c.e., I was thinking of coming up with examples using it, but no success till now.


texts: How to perform local search on simple paths?

texts:
I have a local search problem.
The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph.

The question is: given a current solution (an $S$-$T$-path), how can I generate a set of neighbour solutions?

To elaborate, I have an optimization (minimization) problem, on which I have to select the "best" path $S$-$T$ path. The evaluation function is complex and can't be evaluated until all the edges in the path are known. This plus the fact that the number of paths is exponential, lead me to draw on local search.

I know how to find an initial solution in polynomial time. The only piece missing in order to be able to use a local search algorithm (i.e. hill climbing) is to be able to generate a set of successors from the current path. I find this not to be trivial because simply switching one random node in the path for one not in it does not necessarily generate a still valid $S$-$T$ path.

Edit: I did not want to enter in the details of my specific problem because I think the question about how to define a relationship of neighbourhood in the space of path graphs is interesting in itself. But since you have asked, this is the evaluation function:
$$\mbox{length}(\mbox{path}) \times \sum_{i=1}^n \left ( p_i \times -\mbox{log}_2(p_i) \right )$$, where $p_i$ is the relative frequency of nodes in the path tagged with the number $i$ (every node in the graph is tagged with a number $1..n$.


texts: Longest Common subsequence theorem in CLRS

texts:
In CLRS in the dynamic programming chapter, there  is a theorem about the longest common subsequence prefix that states the following:

Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be their LCS.
If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.

The theorem has two more points but I am interested particularly in the first point, I don't understand why we only consider $Z_{k-1}$ to be the LCS of $X_{m−1}$ and $Y_{n−1}$ and not $Z$ to be the LCS of all of $X$ and $Y$, if already the last element in all sequences match.


texts:
How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction?
Example:
If sum computes a sum of all elements in a list, and
:type sum = Num a => [a] -> a.
    sum []     = 0
    sum (x:xs) = x + sum xs

How do I take this information to translate it to a lambda calculus expression, or rather an abstraction?
I have tried to find guides online but they just give me the answers. I want to know how to actually make the conversion/translation from a Haskell function like add, sum, map, fold, etc. to a lambda calculus abstraction.


texts: Probability of Attaining the/a Global Optimum

texts:
Suppose for a given optimization problem, $A$, the size of the search space $S$ is |$S$|.
If the fitness landscape defined by $A$ is unimodal, then there is clearly only one global optimum. Given that $G$ is the event "reach the global optimum", can we then infer that $P(G) = \frac{1}{|S|}$, where $P(G)$ denotes the probability of reaching the/a global optimum?
For $N$ ($N < |S|$) such global optima (in the case of a multimodal landscape), the probability increases to $P(G) = \frac{N}{|S|}$
Is this a valid argument or can we not conclude anything regarding the probability of attaining the/a global optimum on the basis of the number of optima and the size of the search space?
I realize that often one cannot know in advance the number of global optima, but say, if the problem was to maximize a simple continuous function over some domain, then the function of interest could easily be plotted and the number of (local) optima examined.


texts: Must a deadlock necessarily occur if the four conditions exist?

texts:
I understand the four necessary conditions, mutual exclusion, hold and wait, no preemption, and circular wait, for deadlock to occur. However, does there exist a situation where the four conditions are true and the system is not in a deadlock state?

If a deadlock occurs, there exist the four conditions. However, if there exist the four conditions, is there necessarily a deadlock? What is an example where the four conditions exist, and a system is not in a deadlock state?


texts: Determining time complexity of this function in python

texts:
I would like to determine the time complexity of this function, in $\mathcal{O}$-Notation.

def g(x):
   if x == 0:
      return 1
   elif x == 1:
      return 2
   else:
      x_div = x//2              # // is integer division
      x_mod = x % 2
      return g(x_div)*g(x_mod)

Because it's recursive, I think it's $\mathcal{O}(\log{}n)$. Is this correct?
A small explanation would be great.

Another question, is there a relation between the return value of the function and the binary representation of $n$?


texts: Numerical stability of linear interpolation

texts:
Is one of these two functions more numerically stable than the other?

def interpolate_a(x, y, z):
    return y + (z - y) * x

def interpolate_b(x, y, z):
    return y * (1 - x) + z * x

If so, which one is better and why? After testing these functions with several million inputs, they have always returned the same value. My concern is that with certain inputs, they may return different values, and one will be more correct that the other. Is this possible?


texts: Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?


texts: Is every CPU instruction ultimately read and write?

texts:
Is every instruction ultimately all read or write instructions? So, how I imagine this is that every place where something can be stored can be either in a read or write state, including the CPU registers.

How this is controlled is by the control unit. Every instruction goes through the control unit which is connected to the control bus and flips memory locations (computer memory addresses) to either read or write state.

I understand that there is much more too this depending on what information the control bus can carry, but is this general overview correct in how data is moved about?


texts: How can I show that a language is Turing-recognizable and decidable?

texts: I was wondering how I can show that the language $\{a^n b^n c^n \mid n \geq 0 \}$ is Turing-recognizable. Also, if it is Turing-decidable?


texts: What is the purpose of manipulating trained layers?

texts:
In my course there are a number of exercises which amount to taking a trained residual network and deleting, swapping or repeating layers (without retraining).
Is there any real application for doing this? An exercise might say to swap two specific layers and I will find that the performance will increase (on a very small test set) but if I try to swap any other two layers the performance decreases.
To me it seems that operations in the exercises are chosen to increase the performance on the specific test set that we have but I don't see how it would improve generalisation. In answering the exercises I can say that the performance increased but I can't say why (because to me it seems to be an arbitrary manipulation of the network).


texts: Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?

texts:
I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that maximizes the number of new elements at each turn (same as the one proposed in the Wikipedia article). However it is not as trivial to reach a result about the approximation ratio of this greedy approach.

So I did some research and found these lecture notes that describe some useful concepts for this problem and also proves a lemma. Now let me iterate what is said in these lecture notes before we get to the lemma.

Maximum Coverage problem
Given a set of sets $U=\{S_{1},\dots,S_{m}\}$ and a number $k$, choose (at most) $k$ sets such that the union of the sets is maximized, or $\max_{I\subseteq U}\vert \cup_{j\in I}S_{j}\vert$ for some index set $I$. The sets may have elements in common. Let $\mathbf{OPT}$ denote the optimal solution, i.e. numbers at most covered by $k$ sets, let $a_{i}$ denote the number of newly covered elements in the $i$:th iteration by the greedy algorithm, let $b_{i}$ be the total number of covered elements in the $i$:th iteration, i.e. $b_{i}=\sum_{j=1}^{i}a_{i}$, and let $c_{i}$ be the number of uncovered elements at the $i$:th iteration, i.e. $c_{i}=\mathbf{OPT}-b_{i}$. Moreover, $a_{0}=0$, $b_{0}=0$ and $c_{0}=\mathbf{OPT}$.

Lemma: The number of newly covered elements at the $(i+1)$:th iteration (i.e. $a_{i+1}$) is always greater than or equal to $(1/k)\cdot$number of uncovered elements at the $i$:th iteration, or $a_{i+1}\geq c_{i}/k$.

Proof: Optimal solution covers $\mathbf{OPT}$ elements at $k$ iterations. That means, at each iteration there should be some sets in $U$ whose size is greater than or equal to the $(1/k)$ of the remaining uncovered elements, i.e., $c_{i}/k$. Otherwise, it was impossible to cover $\mathbf{OPT}$ many elements at $k$ steps by the optimal solution. Since the approximation algorithm is greedy, i.e., choosing always the set covering maximum number of uncovered elements,the chosen set at each iteration should be at least the $(1/k)$ of the remaining uncovered elements. That is, $a_{i+1}\geq c_{i}/k$.

I do not understand this proof, why does it have to be the case there exist such sets? And why is the size of the set important, is it not the number of new elements the set contributes that is important? It all seems arbitrary to me to choose that there is a lower bound of $(1/k)\cdot c_{i}$ for $a_{i+1}$. I am also confused about how the optimal solution is related to the greedy solution, what is the rationale behind the statement that if this is not true then it would have been impossible for the optimal solution to be $\mathbf{OPT}$ in $k$ iterations? Since I have trouble understanding at all, is there any other way to explain this lemma?


texts: Show that the following algorithm takes $O(n)$ time

texts:
You are given a linked list of size $n$.
An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed is at index $i$ and it belongs to a list of size $n$. Once an index $i$ is accessed, the list is broken into two lists. One list contains the first $i$ elements and the second list contains the rest of the elements. It has something to do with cartesian trees, but I am not clear how to proceed with this chain of thought.

Show that the total cost incurred to access all the elements is any arbitrary order is $O(n)$.


texts: NP-Hard vs NP-Complete Why NP-complete so important?

texts:
A problem $L$ is NP-complete when:-

$L\in \text{NP}$
For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$

When at least property 2 is satisfied for a problem $L$ (but not
necessarily property 1), then $L \in \text{NP-Hard}$.

When a problem $L\in \text{NP-Complete}$ is shown to have a polynomial-time solution, we say $\text{P}=\text{NP}$ due to Cook-Levin Theorom.

Wikipedia states:
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.

This can be attributed to transitivity property of polynomial-time reductions.
If we are able to show that a problem $L''$ already known to be in NP-complete to
be polynomial-time reducible to the problem $L$, then $L$ satisfies property 2 by
transitivity.
Well as the property 2 is satisfied by the NP-Hard problems too.
My assumptions -

A known NP-Hard problem is polynomial-time reducible to a unknown problem $L$. Then $L$ should satisfy property 2 too. So, $L$ is NP-Hard. If $L\in \text{NP}$ also true, then $L\in \text{NP-complete}$.
If $L \in \text{NP-Hard}$ but not shown to be NP yet and we have a deterministic polynomial-time algorithm for $L$ then $\text{P}=\text{NP}$.

Now, my questions-

Are my assumptions above true? - Wikipedia says it is true. Please confirm and provide other good references to check my assumptions.
If above is true, why are the NP-Complete class considered so important when the answer to P=NP rests on existence of a deterministic polynomial-time algorithm to any NP-Hard problem (be it NP-Complete or not)?


texts: Realtime hardware/software versus PC software/hardware, how are these distinct and alike?

texts:
This question stems from a few answers and comments on a question I posted in signal processing found here.

I guess I am a little confused. Are there any concrete differences between realtime software/hardware and just a regular PC?

I would try to list what I think the differences are but the list I have come up with is ambiguous and short.

The only thing I think makes sense to separate the two ideas is that PC software can run part of its code part of the time, real-time runs all of its code each time. So a PC can load a program but not all programs and run just that program for however long it pleases, real-time is just a single program with a bunch of if-else, switch logic basically a huge abstract collection of relays (PLC) that gets ran through every time it is called.

Yes I realize this is a pretty poor description, so I ask is there any good concrete ways to separate these ideas?


texts: Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

texts:
Please bear with my unhelpful typesetting.

My question is regarding well known FLP paper
Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson

While discussing Lemma 3, in 4th paragraph, authors make an assumption I am unable to understand.

The assumptions are -

1) There exist two neighbour configurations $C_0$ and $C_1$ both from set $\mathscr{C}$ (which contains configurations on which event $e$ was never applied). So far so good. Till this part we never discuss about valency of $C_0$ and $C_1$.

2) Next assumption is - From $C_0$ taking $e$ causes to go to $D_0$ while from $C_1$ taking an $e$ causes to go to $D_1$.

3) $D_0$ and $D_1$ do not have same valency. (Both are not 0-valent/1-valent simultaneously)

The proof of lemma goes on and uses commutative property to prove that set $\mathscr{D}$ is bivalent.

While I have no problem with rest of proof, I am failing to understand why all three parts of the assumptions should be considered consistent to each other. It is these assumptions (especially 2 and 3) that lead to contradiction.

Here is clarification regarding points 2 and 3.

To me it seems that from the assumption, $e(C_i) = D_i$, we introduced the contradiction by saying that $D_0$ and $D_1$ are of different valencies. How can one justify that this choice is valid? Why should not I think that both $D_0$ and $D_1$ should be of same valency? How do I prove that set $\mathscr{D}$ will still remain bivalent even if $D_0$ and $D_1$ are of same valency?

In other way, question would be, how to prove that all three points mentioned above can actually arise in some consensus protocol with assumptions given in lemma.

The fact that $e(C)$ followed by $e'(e(C))$ or vice-versa; $e'(C)$ followed by $e(e'(C))$ should result in same configuration is achieved due to commutativity, and we knew this before hand. My point is, we specifically chose a scenario which was contradicting in itself and does not does anything more in the bigger picture to draw a contradiction of the statement, that $\mathscr{D}$ is univalent.


texts: Which is the shortest path to share a secret between people?

texts:
My problem looks like a secret sharing problem. That’s to say:

We have N people. Each of those owns a word to share to other people.
The aim is that all people know all the words of other participants.
People can only discuss in houses. There are H houses. Each of those may only accept a limit of L members. In a house, all members share their word to others.
We assume that:

People can only say their word (thus, they may not share words they learnt from other people).
The words never change.

I want to answer the question: For all participants, what is the shortest path (from house to house) to learn all words?

Solution with L=3, N=5 and H=2, let’s call H1 the house number 1 and H2 the house number 2 :

Member 2 : H2 -> H1 -> H1
Member 3 : H2 -> H2 -> H2
Member 4 : H1 -> H2 -> H1
Member 5 : H1 -> H1 -> H2

Does this “secret sharing” problem refer to well-known algorithms?

Many thanks.


texts:
I am working on my thesis which involves using ant based techniques for graph clustering. I am testing the algorithm currently and I was wondering if there is a way that I can visualize the clusters of a given graph.

In this case, I have the graph as a file and another file corresponding to the clustering where each node is given its cluster. Is there a software using which I can visualize this graph where nodes belonging to the same cluster have like the same color or something?

The graph is represented as an edge list, or in the ".net" format or Graph Modelling Language ".gml" format. I know there are a lot of programs out there for networks such as gephi, graphviz, networkx, pajek etc but I don't know how to do this. Any help/ideas would be greatly appreciated!

Thanks!


texts: The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

texts:
In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

min(M,N)
max(M,N)
M+N
MN
Answer given is M+N but my understanding is

According to the given question the communication between sender and receiver is unidirectional or bi directional?

If it is unidirectional then answer should be max (N,M) , as sender will send N frames and each frame should have unique sequence number and if it is bidirectional then it should be M+N as both will have their Frames In transition with unique sequence number.

Is my interpretation is correct? Please correct me if I am wrong!!
If not why M+N is correct?


texts: Algebraic (spectral) algorithms for the minimum spanning tree problem

texts:
Are there any algorithms that use the spectral properties of a graph to solve the minimum spanning tree problem?

To clarify further what I have in mind, starting with the Laplacian matrix I want to algebraically arrive at the required set of edges. This is opposed to Prim's or Kruskal's algorithm where the result is obtained by operating on the edges/vertices sets directly.


texts: How does a buffer overrun corrupt the return address?

texts:
I got stuck on the following note while reading a paper about computer security:

The stack mixes program data and control data
– by overrunning buffers on the stack we can corrupt the return  addresses!

In fact, I didn't understand how a buffer overrun corrupts the return address within a stack frame. Also the use of the term buffers was not very clear to me - what do they mean?


texts: Boundary tracing of simple closed curves?

texts: I have some heavy calculations that essentially takes a point in the plane as input and gives an integer as output. Points in the same region gives the same integer (think about the regions as pieces in a jigsaw (every point in completed puzzle belongs to a specific jigsaw piece), the boundaries being simple, closed curves). I've made a very simple algorithm that first finds a boundary by finding the integers of two neighboring corners of my search rectangle and divides and conquers its way to find a boundary (to within a predefined accuracy). So I find a random boundary in O(log(width)) time, where width is the width of my search rectangle. Now my naive approach is then to sort of take small steps in a circle around that point until the number changes, record that point and repeat. The problem is checking a points number is really expensive (NP-hard) and even worse my algorithm misses forkings in the boundaries. All I can find online is image processing algorithms like floodfill, where checking a point is cheap. Does algorithms like this exist? Or do you have any good ideas to make one?


texts: Variant of (WEAK) PARTITION with 2 distinct solutions

texts:
I am interested in the complexity of the following problem:

Input: A list $a_1\leq ⋯ \leq a_n$ of positive integers.

Question: Are there two vectors $x, x'\in\{−1,0,1\}^n$, with at least one $x_i$ and one $x'_i$ non-zero (the subsets must be non-empty), such that
$$\sum_{i=1}^nx_ia_i=0, \sum_{i=1}^nx'_ia_i=0 \text{ and } x_ix'_i=0 \text{ }\forall i.$$
WEAK PARTITION is a variant of PARTITION where we are looking for a partition of a subset of the input, and not a partition of all the integers. This is the reason why we have $\{−1,0,1\}^n$ and not $\{−1,1\}^n$. Note that the subset must be non-empty, it means at least one $x_i$ must be non-zero.

But I am interested in the problem described above where we are looking for two distinct weak partitions.
For example, with $A=(1,2,3,4,5,7,11,11)$, we have $x=(1,0,1,0,0,1,-1,0)$, $x'=(0,1,0,1,1,0,0,-1)$ and for each component $i$ we have $x_ix'_i=0$. It means we have two disjoint subsets of $A$ where there is a weak partition.

There is clearly a reduction from WEAK PARTITION but I suspect this problem to be NP-hard in the strong sense. Do you see any reduction from a problem which is NP-hard in the strong sense ?

Thank you very much.


texts: Tips on speeding up hierarchical linkage clustering algorithm

texts:
I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.
I read about this algorithm here.
These are the steps:

Compute distance matrix between all points (great-circle distance, not Euclidean)
Find the pair of points with the minimum distance between them
If the minimum distance is larger than a threshold value

the algorithm finishes

Otherwise

The two points are merged, and removed from the list of points.
The center point of this pair is added to the list of points

Go back to 1

I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).
It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.
Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.
Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?
I am using MATLAB R2018b.
Thank you!


texts: Non-deterministic algorithm for solving figure of 8

texts:
I am struggling in trying to figure out a non-deterministic algorithm for the following problem.

Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected graph $G = (V,E)$ with vertices $V$ and edges $E$. $G$ is a yes-instance if there is a sequence of vertices $(v_{0},v_{1},...,v_{k+1})\ (some\ k \geq 6)$ such that

• Each pair $(v_{i},v_{i+1})$ is an edge $(each\ i < k − 1)$ and $(v_{k−1},v_{0})$ is an edge.

• Every vertex in $V$ occurs at least once in the sequence.

• There is $j$ with $2 < j < k − 2$ such that $v_{0} = v_{j}$.

• No other vertex in the sequence is counted twice, i.e. if $v_{s} = v_{t} (any\ s,t < k)$ then either $s = t$ or ${s,t} = {0,j}$.

If there is no such sequence of vertices then $G$ is a no-instance of FOE.

Thanks


texts: Proof that a randomly built binary search tree has logarithmic height

texts: How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't understand it.


texts: Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

texts:
I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [1] that uses a generalised version of EvenShiloach-trees (ES-trees) [2] to maintain shortest path trees for the graph.

I have looked into ES-trees and understand how they work in the setting of undirected graphs, however a modification should allows to maintain a shortest path tree in directed graphs [3] but I can't work out how to do it.

Does anyone know of an example how ES-trees can be modified to maintain a shortest path tree under edge deletion?

[1] Bernstein, A., Probst, M., & Wulff-Nilsen, C. (2019). Decremental strongly-connected components and single-source reachability in near-linear time.

[2] Even, S., & Shiloach, Y. (1979). An on-line edge-deletion problem (No. CS Technion report CS0154). Computer Science Department, Technion.

[3] Henzinger, M. R., & King, V. (1995, October). Fully dynamic biconnectivity and transitive closure. In Proceedings of IEEE 36th Annual Foundations of Computer Science (pp. 664-672). IEEE.


texts: What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?

texts: After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages are delivered in order and no message is lost. In addition to that, the algorithm uses Lamport logical clock, so the requests will always be processed in order.


texts: How does this dependently-typed boolean elimination function work?

texts:
In the companion code to A Tutorial Implementation of a Dependently Typed Lambda Calculus
 - prelude.lp - there is a rather intimidating definition of a boolElim function that's not described in the paper itself:

let boolElim =
  ( \ m mf mt -> finElim ( nat2Elim (\ n -> Fin n -> *)
                                    (\ _ -> Unit) (\ _ -> Unit)
                                    (\ x -> m x)
                                    (\ _ _ _ -> Unit) )
                         ( nat1Elim ( \ n -> nat1Elim (\ n -> Fin (Succ n) -> *)
                                                      (\ _ -> Unit)
                                                      (\ x -> m x)
                                                      (\ _ _ _ -> Unit)
                                                      n (FZero n))
                                    U mf (\ _ _ -> U) )
                         ( \ n f _ -> finElim ( \ n f -> nat1Elim (\ n -> Fin (Succ n) -> *)
                                                                  (\ _ -> Unit)
                                                                  (\ x -> m x)
                                                                  (\ _ _ _ -> Unit)
                                                                  n (FSucc n f) )
                                              ( natElim
                                                  ( \ n -> natElim
                                                             (\ n -> Fin (Succ (Succ n)) -> *)
                                                             (\ x -> m x)
                                                             (\ _ _ _ -> Unit)
                                                             n (FSucc (Succ n) (FZero n)) )
                                                  mt (\ _ _ -> U) )
                                              ( \ n f _ -> finElim
                                                             (\ n f -> natElim
                                                                         (\ n -> Fin (Succ (Succ n)) -> *)
                                                                         (\ x -> m x)
                                                                         (\ _ _ _ -> Unit)
                                                                         n (FSucc (Succ n) (FSucc n f)))
                                                             (\ _ -> U)
                                                             (\ _ _ _ -> U)
                                                             n f )
                                              n f )
                         2 )
  :: forall (m :: Bool -> *) . m False -> m True -> forall (b :: Bool) . m b

The type indicates its behaviour (an if-else), but I can't make any headway with the definition. Can someone break it down for me?


texts: Are there any "complete" languages in $coNP -NP$?

texts:
Suppose $coNP \neq NP$

language B would be called "complete" in $coNP-NP$ if:

$B\in coNP - NP$
$A\in coNP-NP \implies  A\leq_pB$

Are there any "complete" languages in $coNP - NP$?


texts:
I'm working on an e-commerce application where users can add stand-alone products like speaker or they can add a bundle product like desktop that has options like mouse, keyboard etc. All the products and options are finally added as cart items to the cart.
For example
Desktop
  - Mouse
  - Keyboard
Speaker

After adding above the cart will have items like below,
Shopping Cart
  Line item 1 - Desktop - Parent-Line NULL
  Line Item 2 - Mouse - Parent-Line Item 1
  Line Item 3 - Keyboard - Parent-Line Item 1
  Line Item 4 - Speaker - Parent-Line NULL

If I remove the product desktop from the cart all of it's options should also be removed. At the same time we want to access all the line items as an array too.
For example,
for (var items in shoppingCart.items) {
  console.log(item);
}

// "Desktop", "Mouse", "Keyboard", "Speaker"

If I use an array to store the items then I need to work on the logic to remove the child options on removing parent. I couldn't come-up with an excellent data structure to solve this problem. Any ideas would be very helpful.


texts: unambiguous grammar that produce equal number of a and b

texts: is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?


texts: Where is proof that palindrom language is nondeterministic?

texts:
It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but cannot be accepted by any deterministic PDA. The idea of proof is desribed, e.g., by Hopcroft, Ulman, Motwan in 'Introduction to Automata Theory, Languages. and Computation', but I cannot find complete proof. I saw reference for variation of pumping lemma for deterministic CFL, but now cannot find it too.
So. the question: does anyone know where is the proof that the language $\{ww^R: w\in\{a,b\}\}$ is not deterministic?

Thanks in advance


texts: Why doesn't everyone use microkernel-based operating systems?

texts:
From what I have read on operating systems, the impression I have been receiving is that, for at least 30 years, "everybody has known" that microkernel-based operating systems are "better" than monolithic operating systems. And yet, I have a Linux OS at work and am typing these lines on a computer running a Windows OS at home. Moreover, looking at Wikipedia's list of microkernel-based operating systems, it seems most are old and have been discontinued, and none have really broken into the PC space (although FreeRTOS is a player in the embedded space).

Question: Why has no microkernel-based OS broken into the mainsteam? Why is the world still using monolithic OS's 28 years after Tanenbaum-Torvalds? What is the "hard problem" microkernel-based OS's have not been able to solve, and why do people keep trying?


texts:
$$L = \{  \langle M \rangle  \mid  M \text{ takes at least 2016 steps on all input } \}$$

My approach

As $M$ takes atleast 2016 steps, only tape cells 0,1,..2015 are significant. Now we have finite number of strings of length 2016.

As we have finite number of strings with finite length, we can simulate $M$ on each of these strings in finite amount of time.

For all strings with length greater than 2016, the behaviour of TM for these strings would be same as for the prefix of those strings (first 2016 input symbols).

So above language is recursive.

My book says answer as recursive but it doesn't have any explanation so I don't know if my explanation regarding whether the language is recursive is right or wrong.

I have just one doubt with the above intuition. In the question we have atleast 2016 steps. Now according to the intuition, if we have a string of length 2019 and if a prefix of length 2016 doesn't halt within 2016 steps then it doesn't belong to language. But what if the string of length 2019 halts on 2018th step, then it belongs to language but we are not considering that. Should we also consider that ? I know that my intuition is correct if question would have been atmost 2016 steps.

Can someone please help?