texts:
I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I need help with to understand how to prove it's NP-complete. Any help will be much appreciated!

[Background] A directed graph is consisting of people, with an edge from person A to person B if person A is a follower of person B. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself.

The answer of the algorithm is YES if there exists a set S of at most k people reaching at least m people, and NO otherwise.

Prove that this is a NP-complete problem by reducing a known NP-hard problem.

So the first step is to prove that the problem is a NP problem and if I understand correctly I can prove that by finding a cefrtificate that is proved as a solution of the probem in polynomial time. However, I have problems in picking a known NP-hard problem and reducing.


texts: Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers

texts:
I am close to solving question 3.59 from Computer Systems: A Programmer's Perspective 3rd Editionby Randal E. Bryant and David R. O'Hallaron, however I am having difficulties with understanding the result.

Question 3.59 asks you to examine a sample of C and x86_64 assembly code that performs a full, signed multiplication of two 64-bit numbers, producing a 128-bit result, and explain how the code is working. The C and assembly is below.

1  #include <stdint.h>
2  typedef __int128 int128_t;
3
4  void store_prod(int128_t *dest, int64_t x, int64_t y) {
5      *dest = x * (int128_t) y;
6  }

# x in %rsi, y in %rdx
1  store_prod:
2    movq    %rdx, %rax
3    cqto
4    movq    %rsi, %rcx
5    sarq    $63, %rcx
6    imulq   %rax, %rcx
7    imulq   %rsi, %rdx
8    addq    %rdx, %rcx
9    mulq    %rsi
10   addq    %rcx, %rdx
11   movq    %rax, (%rdi)
12   movq    %rdx, 8(%rdi)
13   ret

The book suggests thinking about the problem by recognizing that when $x$ and $y$ are extended to 128-bits, they can be written as $x = 2^{64}x_{h} + x_{l}$ and $y = 2^{64}y_{h} + y_{l}$, where $x_{h}$, $x_{l}$, $y_{h}$, and $y_{l}$ are 64-bit values.

I see that mathematically

$$
\begin{align*}
xy &= (2^{64}x_{h} + x_{l})(2^{64}y_{h} + y_{l}) \\
   &= 2^{128}x_{h}y_{h} + 2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}.
\end{align*}
$$

Since $x_{h}$ and $y_{h}$ are the sign extended parts of $x$ and $y$, we do not care about the $2^{128}x_{h}y_{h}$ term in the final value, so we really only care about $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$, which is how the value is calculated in the assembly code.

My misunderstanding comes about in lines 8 and 10 in the assembly code. Line 8 calculates $x_{h}y_{l} + x_{l}y_{h}$ and line 10 calculates $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$.

My question is why do we not have to worry about overflows when executing the addition instructions on these lines. Even if an overflow occurs, why are the bits of the result correct? Is it because any value resulting from an overflow would en dup going beyond 128-bits, which we then don't care about?


texts: Methods for optimizing short-circuit evaluation for conditions of varying evaluation-cost

texts:
I have a bunch of boolean conditions, let's call them A, B, C, D, ....

In my code, I need to use these conditions to distinguish between several different possible scenarios. For example, I could have something like this (in pseudo code):

if ((A and B) or not (C or D)) then process case 1
if (A and (not B) and (C or D)) then process case 2
otherwise process case 3

Now, I can start to combine these if-statements to optimize the number of evaluations needed, like:

if (A) then {
    if (B) then {
        process case 1
    } else {
        if (C or D) then process case 2
                    else process case 1
    }
} else {
    if (C or D) then process case 3
                else process case 1
}

But I could equally well "short-circuit" (I'm using the term loosely) the evaluations differently, like:

if (C or D) then {
    if (A) then {
        if (B) then process case 1
               else process case 2
    } else {
        process case 3
    }
} else {
    process case 1
}

Let's say that there is a significant difference in the cost of evaluating these conditions, e.g. some require a database call, others are simple variable-null-checks, etc. Then, there is probably an optimal solution for how to break up the code (assuming all cases are somewhat equally likely).

For example, if the evaluation of A and B is cheap while the evaluation of C or D is expensive, the first version above is probably better on average as there is a chance that if A and B turn out true, C and D never need to get evaluated. Whereas if C and D are cheap while A or B are expensive, version two is better on average.

Is there some formal framework or other approach for figuring out this optimization?


texts:
As you see, the string production process never ends.
Can someone explain me if  this language is  regular or not  ?
$ S \to Α Β S $
$ A \to S  $
$ B \to a B b $


texts: linear time nash equilibirum aproximations for two player zero sum games

texts:
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. Given that I have 10s of thousands of entries I can't apply even an $O(n^2)$ algorithm or the result will take too long so I need a linear time algorithm. I've found this note which details an exceedingly simple $\frac{1}{2}$-approximation algorithm that works for any game, not just a zero sum game. It also does so by only looking at $O(\sqrt{N})$ entries in the table which is even faster than what I need.
Zero sum games can have their exact equilibrium computed in polynomial time via linear programming but this is too slow.
What I'm looking for is something in between; Something that uses more computational resources than the simple 1/2-aproximation algorithm but gives a better approximation; Something that uses fewer computational resources than linear programming but only gives an approximate answer. Does a linear time approximation algorithm exist for 2-player zero-sum games that is better than $\frac{1}{2}$-approximation?


texts: Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b

texts:
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?

I'm sorry I can't give any approach of what I did, but it's because I don't even know where to start with this ex. in particular. I tried to search anything on my books, but couldn't find nothing at all. Any suggestion is welcome.


texts: How an I prove if this language is decidable or not

texts:
In the context of computability and turing machines

Let $L_1$ be an undecidable language and $L_2 = \{n \in \mathbb{N} | \exists x \in L_1  |x| \geq n\}$

How can I prove if $L_2$ is decidable or not?

I guess $L_2$ is not decidable in general and it depends on $L_1$ but still nothing proved. \


texts: If two languages are decidable, can one be mapping reducible to the other?

texts: If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?


texts:
It seems that the standard reduction method you see online from 3SAT to 4SAT is that we let $\phi = (a \lor b \lor c)$ be a 3SAT clause, and so there is an assignment that satisfies $\phi$ iff $\phi' = (a \lor b \lor c \lor z) \land (a \lor b \lor c \lor \neg z)$ is also satisfiable.

Is it just as valid to say that $(a \lor b \lor c)$ is satisfiable iff $(a \lor b \lor c \lor c)$ is satisfiable? This seems like a much simple solution..


texts: Edit Distance Algorithm (variant of longest common sub-sequence)

texts:
I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming.

The problem is defined as follows:

suppose that you are making a spell-checker with suggestions for misspelled words.  You would like to be able to find the words that are closest to the string of non-word letters that a user has input.

These words can differ from the typed string by

missing a letter
having an extra letter
having a letter replaced with another letter

the costs are:

$c_i$, the cost of an insert

$c_d$, the cost of a deletion

$c_r$, the cost of a replacement

with the intention of beginning with a recursive approach that can be converted into a dynamic program, the idea is to build up from substrings.

let T(j,k) denote minimum cost to transform
substring A[1...j] to substring B[1...k].

then there are four ways to convert A[1...j]
into B[1...k]

1. delete the jth character of A[1...j] and
convert the first j-1 characters of A into the
first k characters of B.  This equals cost cd +
T(j-1, k)

2. convert the first j characters of A into the
first k-1 characters of B, and insert a kth
character into B[1...k-1].  This equals cost ci
+ T(j, k-1)

3. replace the jth character of A with the kth
character of B and convert the first j-1
characters of A into the first k-1 characters
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)

This can be written as a recursion equation,
taking the minimum over all four alternatives
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

The question is this: suppose we're to add a "swap" function which corrects two letter which are typed in the wrong order.  How would we modify the euation for the cost of changing string A into string B if the the cost of a swap is $C_s$?

My thought is:

T(j-1, k+1) if A[j,k] = B[k,j] ?


texts: About the interpretation of the SOS hardness results of the planted Max-Clique problem

texts:
One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the planted-Max-Clique problem and the second one is improving the detection threshold from $n^{1/3}$ in the first paper to $n^{1/2}$.

Does any of these results imply or do they implicitly contain the hardness threshold for say just the Max-Clique problem w.r.t even just the degree-4 SOS?
Or are both these results totally specific to the planted problem and say nothing about the Max-Clique?

If I say look at the corollary 2.1 (bottom of page 10) in http://arxiv.org/pdf/1502.06590v1.pdf then this seems to be a hardness threshold for just the Max-Clique problem but I am not feeling very sure since the authors never put in these same words. Am I missing something?  The same can be said about Theorem 1.1 (page 2) in the second paper.
If one sees the section 2.4 in the second paper, where they construct the SDP witness it feels that their construction would make sense only in the "planted" setting and then contrary to my feeling from theorem 1.1 now I start feeling that the result applies only with planting.


texts: More efficient maximum bipartite matching

texts:
I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and papers, I've noticed that the Hungarian/Kuhn's algorithm tends to get mentioned a lot as a solution/approach. My sticking point is that it runs in $O(n^3)$ time and I've read in a few sources that there are better implementations.

My challenge is that these sources will often just mention these better approaches at the very end of a discussion and offer little insight into the implementation. So I guess my question is: are there indeed better than $O(n^3)$ runtimes? I think I remember coming across references that $O(nm\log n)$ and better exist, just having a hard time finding either reference implementations or more direction. Any help would be appreciated, especially examples as that's how I tend to grok things best after going through the theory.


texts: Is there a correspondence between the syntaxes and the type systems of programming languages?

texts:
I was reading the first chapter of Robert Harper's Practical Foundations for Programming Languages in which it introduced abstract binding trees, aka abt. It seems pretty like typed lambda calculus.

There are ground sorts, which are similar to ground types in typed lambda calculus.
There are abstractions; they accept multiple arguments. They remind me of uncurried version of lambdas. It's a bit odd that abstractions at the syntax level aren't first-class, though.
Later at the end of the chapter in the book, symbols are introduced. They seem to correspond to data types. (Or do they?)
Indexed operators are $\Lambda$ bounded terms in the sense of system F.

The author of the book seemed to be aware of the similarities. The set of symbols is even written $\mathcal{U}$ in the book!

What I'm asking is, is there known to be a correspondence of abt's and type systems, or is it too good to be true? Are there more advanced systems of abt's that correspond to system Fω or dependent types?

The question is kind of too broad. Hopefully it can be accepted on this website.


texts: How is the Delta Rule derived in neural networks and what is the explanation for the algebra?

texts:
I am currently trying to learn how the Delta Rule works in a neural network. So far I completely understand the concept of the Delta Rule, but the derivation doesn't make sense. My question is how is the Delta Rule derived and what is the explanation for the algebra.
Currently I am writing equations to try to understand, they are as follows:
Desired = (Input * WeightD)
Actual = (Input * WeightA)
Error = (Input * WeightD) - (Input * WeightA)
Error = Input (WeightD - WeightA)
However, as stated Here, the ΔWeight is understood to be Error * Input, where as I derive it to be Error / Input. I fully understand the concept of correcting the weights in a neural network, however, I do not understand how the algebra and derivation of the Dela Rule work to re-adjust the weights to correctly represent the output. I will explain my current understanding to help you understand why I may be confused. Because the Input is constant whilst you attempt to find a correct weight, you can factor it out. This leads me to the equation that the Error is equal to the Input times the difference between the correct and incorrect weights. This is also very clear. However I do not understand where they go from here to get the equation to correct the weights. How is the required net change derived from this? How does the algebra behind simply Input * Error work? Thank you.


texts: Why is my algorithm version so slow with this input?

texts:
Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (or just referencing) the code of both algorithms only to better specify the implementation details, which could be relevant for the comparison.
I've written my F# code to solve Advent of Code Day 18 Part 1.
It is a BFS adapted to find the optimal solution for a weighted graph (last version has been edited since the original question was posted here, but, as already said, ignore this sort of details).
While it seems to work fine with other simple demo inputs, it stucks forever with the following input.

#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

It represents a list of lowercase char vertices with uppercase constrained predecessors and edges weighted by different dotted distances.
So here I'm looking for a comparison based on the time complexity of the algorithms, related to an analysis of the cases where the number of edges increases, at a fixed number of vertices.
There is a reference solution in Python which is correct and fast, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

I've tried with recursion vs a queue, with tree vs grid/map (see my github history) but with no luck until now.

The principal part of the code is described below.
It should fall under a breadth first search (BFS) algorithm, whose implementation details are reported below only to complete the theoretical description already given, because the standard BFS has been adapted to multiple targets, weighted edges and a tentative tree pruning.

Here is how I produce the single step, by which I elaborate the solution.

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

Notice that this is a constrained version of the TSP where each vertex can have as constraint a list of predecessors.

The fullGrid is supposed to contain the matrix of distances and it looks fine to me, in terms of the values it contains when I debug it.
The wrapping solver is simply a recursion or queue based version of the BFS. Again, I'm not interested in the programming details but in understanding, at a conceptual level, why the underlying algorithm is not applicable for an apparently tractable input case (of "only" 16 nodes).

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices

                For each one applies above said single step
                If done updates mindistance and completed alternatives
                Otherwise enqueue such partial solution

    Finally select the min alternative by distance.


texts:
A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if
$$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$
You can find more about universal hashing this wikipedia article.

The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:

  Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?


texts: Designing and implementation a publish subscriber system

texts:
I have to build a simple publish-subscribe system in say C++ for example that can handle multiple subscriber. I have never done anything like that although I have made HTTP server and client, but not a publish subscriber system so  I thought to ask few questions here first. I know I am reinventing the wheel but I need to make it.

I am planning to use boost::asio for an example as networking library as I see many recommendations for this network library on the internet.

Do I have to work on TCP layer or on HTTP layer?
Do I need to keep the connection between client and server persistent? If yes, how frequently I check that the connection is alive? If not how the server initiates the connection to a client? Do I have to implement a  client also as a server?
I also wanted to keep the communication secure (later in future, not an immediate concern). If I do implement it a TCP server, how I do it?

It may possible that some of these questions are stupid or very broad but I wanted a guideline how I could make such a system? Any redirection to any blogs or a tutorial is also ok.

Also, I am perfectly fine with ignoring implementation as of now and thinking in terms of high level design as which networking layer i will be working on, channel persistence and other things.


texts: Selecting k-1 items that divide a sorted array to k equal parts

texts:
Given an unsorted array of $n$ integers, I need to find an $O(n \log k)$ algorithm that finds the $k-1$ items that divide the sorted array to $k$ equal (up to $\pm 1$ items) parts.

For example, if $k=3$, the items we want would be at indices $n/3$, $2n/3$ in the array after we sort it.

I know that you can select those items in $O(nk)$ but I can't think of how to improve that $k$ to $\log k$. I'd appreciate any help.


texts:
Is the following a familiar problem ? Given a graph $G = (V, E)$ and a capacity function $c:V \to \mathbb{N}$ find a spanning subgraph $H$ of $G$ such that $1 \leq deg_H(v) \leq c(v)$ for every vertex $v \in V$.

I would like to know if this is an NP-hard problem so any pointer to a similar problem (NP-hard or not) will be very appreciated as well.

Thank you,

GIlad


texts: What is the meaning and significance of a Turing machine taking a description of itself as input?

texts:
Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on input $\langle M, \langle M\rangle\rangle$.

My question is: What is the significance of giving a description of Turing machine as input as in $\langle M,\langle M\rangle\rangle$?

What is the logical reason behind giving the description of a Turing machine as input to $D$?


texts: Reducibility and Artificial Neural Networks

texts:
I have read (here and here
) about the computational power of neural networks and a doubt came up.

There is a way to reduce an ANN to another ANN (not taking into count the training algorithm) ? e.g. Reduce a Recurrent Neural Network to a Multilayer Perceptron, meaning that if I have a trained RNN, I can get a MP that maps the same inputs given to the RNN to the same outputs produced by the RNN.

And if exists an answer to the above question, we can show the equivalence between neural networks, e.g., all problems solved by an Multilayer Perceptron can be solved by a Recurrent Neural Network but the opposite is not true, i.e., $MP \subset RNN$ (I do not know if this is true, is just an example). So, if we obtain this relationship between all neural networks, we can get a neural network $X$ that is more powerful than others, so, we can throw away all other neural networks because $X$ can solve any problem that other NN can. Is this reasoning correct ?

Thanks.


texts:
Quite possibly this problem is already solved and has it's own name, but I was unable to find any directions.

So, I have a portfolio with some items in it:

| Name   | Price | Amount | Share |
|--------|-------|--------|-------|
| Item 1 | 200   | 1      | 25%   |
| Item 2 | 100   | 2      | 25%   |
| Item 3 | 50    | 4      | 25%   |
| Item 4 | 25    | 8      | 25%   |

After some time, prices changed

| Name   | Price | Amount | Share  |
|--------|-------|--------|--------|
| Item 1 | 220   | 1      | 27.36% |
| Item 2 | 130   | 2      | 32.34% |
| Item 3 | 17    | 4      | 8.46%  |
| Item 4 | 32    | 8      | 31.84% |

but I still want all items to have 25% share.

Assuming amount can be decimal, how do I find the optimal way of rebalancing this portfolio back to 25% shares? How to determine how many of each item to sell so we won't have to buy it back again (sell everything and spend 25% on each item is not an option)?

What if I have extra $100 to spend while rebalancing?

Upd: what I mean by "optimal" is to keep the amount of transactions as less as possible, assuming each transaction costs something.


texts: NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

texts:
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are unconcerned here with whether the states are accepting), then the problem of "deciding whether there exists some $N$-state DFA for which each $s_i$ causes that DFA to end up in state $q_i$" is NP-complete.
A much more well-known result by Gold (1978) is the same as the above, except with the alphabet being arbitrary instead of binary, and the examples being in the form $(s_i, \mathrm{accept})$ and $(s_j, \mathrm{reject})$ instead of having the state $q_i$. That result is discussed in some other threads, like this, this, and this.
If I naively try to reduce from the Gold problem to the Sipser problem, I would try to replace all "accept" with a single "terminal" accept state, and same for reject, but that fails because if you wanted only a single terminal accept state to handle all accepted strings, you would need to have an NFA with epsilon transitions; if you try to convert that back to DFA, the single terminal states may split up into multiple, which would invalidate your examples.
I suspect Myhill-Nerode may be useful here, since the DFA states correspond to the equivalence classes of strings. I think you can rephrase the Sipser result as deciding whether some given set of strings can be partitioned into some given set of Myhill-Nerode equivalence classes.
I searched through the literature, but was not able to find the Sipser result anywhere. What is another decision problem that we can use as a polynomial-time reduction here? Alternatively, is this result derived or discussed anywhere else?


texts:
I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see:

IF TRUE ((λp.p) 3) ↔ IF TRUE 3         (per β red)   (1)
                   ↔ (λx.IF TRUE 3 x)  (per η red)   (2)
                   ↔ (λx.3)                          (3)

Step 1 to 2 is explained as η-conversion. But from 2 to 3 it says "The final step is the reduction rule for IF." I'm not sure what this reduction rule is.


texts:
Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration?

Ex:if you are given the description of the bth machine/language enumerated you could quickly check, by some tag or marker in the description of the bth machine / language, that it was indeed the bth machine/language in the enumeration by an enumerator E.

Can you modify any enumerator for a class of languages so that it does this? Or can such an enumerator E be rigged up to do this for any enumerable class of languages?

To give context, my goal is for a verifier to accept, as one part of its input, the machine/language enumerated, and be able to see, quickly, what position that machine/language was in the enumeration by the enumerator E.

Thank you!


texts:
I have a file with a list of non-overlapping trapezoid covering the entire 2D space (they are adjacent if they share a segment of finite length not a point).
The trapezoid are 4 points polygons which in this case are allowed to have only 90, 45, 135 degrees angles. This means their sides are parallel to x,y axis or tilted 45 degrees with respect to them (these conditions I suppose should simplify the problem).

I would like to plot efficiently the graph edges that connect each shape center point with the adjacents trapezoid center points. Which is the best algorithm to find all the adjacent shapes in x and y directions?

Thank you.

Note: extension of a similar question that you find here with a good answer
Data structure for adjacent rectangles


texts: Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

texts:
I'm struggling with the following question:

  Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and  let $ M =
\max\{a_0, a_1, .... a_n\} $ and $ m = \min\{a_0, a_1, .... a_n\} $.

  a. Prove that there are two numbers in the sequence $x,y$ such that $ |x-y| \leq
 \frac{M-m}n$.

  b. Write an algorithm that finds those numbers in linear time.

I've manage to prove part a, but am struggling with part b. I've tried to find a way to find the two element in the array that have the smallest difference, but couldn't find a way to do it in $\Theta(n)$. It should be something related to select algorithm and medians.


texts:
Let's define a replace query on some string $s$.

Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\},  l \geq r; \quad c_{i}, c_{j} \in C$. The replace query $\left(l, r, c_{i}, c_{j}\right)$ replaces all occurrences of $c_{i}$ with $c_{j}$ on $[l; r]$ segment of $s$.

There is a problem. Given string $s$ and $m$ replace queries $\left(l, r, c_{i}, c_{j}\right)$, perform them on $s$ and print the result.

Originally, the problem has low bounds on string length and queries count: $1 \leq n, m \leq 100$. The bruteforce solution seems to have $O(nm)$ complexity. But what if we increase the upper bound on $n$ and $m$ to, for example, $10^{10}$ or even $10^{100}$? Is there solution with better complexity?


texts: Dynamic Programming - Seemingly unnecessary recursion?

texts:
I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of Revenue Management by Talluri and Ryzin, page 61. (See also errata, there is a small mistake in the equation). The recursion is as follows:

$V_t(x)=V_{t+1}(x) + \sum\limits_{j=1}^n \lambda_j(t)(p_j-\Delta V_{t+1}(x))^+$

Where $V_t(x)$ is the value function of capacity $x=0,1,..,C$ and time $t=1,..,T$, the $\lambda_j(t)$ the probability of an arrival of product $j$ at time $t$ and $\Delta V_{t+1}(x)=V_{t+1}(x)-V_{t+1}(x-1)$, the opportunity cost of having one unit of capacity.

The boundary conditions are $V_{T+1}(x)$=0 for all $x$ and $V_{t}(x)=0$ for $t=1,..,T$.

This is a backwards reduction problem, so we start at $t=T$. Since $V_{T+1}(x)=0$ for all $x$, we have $V_T(x)=0 + \sum\limits_{j=1}^n \lambda_j(t) (p_j-(0-0))= \sum\limits_{j=1}^n \lambda_j(t)p_j$ for all $x>0$.

Working back, at $T-1$:

$V_{T-1}(x)=V_T(x) + \sum\limits_{j=1}^n \lambda_j(t-1) (p_j-(V_T(x)-V_T(x-1)))$

Now, since $V_T(x)=\sum\limits_{j=1}^n \lambda_j(t)p_j$ for all $x$, doesn't this reduce to:

$V_{T-1}(x)=V_T(x) + \sum\limits_{j=1}^n \lambda_j(t-1) (p_j-(0))=V_T(x)+\sum\limits_{j=1}^n \lambda_j(t-1)p_j$

I am fairly sure shouldn't happen - why else include the term in the recursion? However, I've been looking at this problem for the past two weeks now and I just really don't get where I am going wrong.

Any help would be greatly appreciated.


texts: Prove the existence of a proposition logical formula so that following conditions are fulfilled

texts: For two proposition logical formulas $\phi$ and $\chi$ so that $\phi\implies\chi$ is generally valid. How can I prove that there is a formular $\psi$ with $var(\psi )\subseteq var(\phi )\cap var(\chi )$ so that $\phi\implies\psi$ and $\psi\implies\chi$ are generally valid?


texts: Regular expression or automata for language with odd number of 0's and odd number of 1's

texts:
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I guess $L$ is not regular, but I haven't been able to prove it with the pumping lemma.

If it is not regular, can you give me a hint to prove it?


texts: Can we check in polynomial time if the language of a DFA is closed against Kleene star?

texts: I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.


texts:
[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now!

$\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional integer lattice $\ZZ^d$, equipped with the max distance $\dist$: for $s=(s_1,\dotsc,s_d)$ and $s'=(s'_1, \dotsc, s'_d)$, $\dist(s,s')=\max_{1\le t\le d} |s_t-s'_t|$. We extend $\dist$ to sets of points as follows: $\dist(S,S') = \min_{(s,s')\in S\times S'} \dist(s,s')$.

  Definition. Given $\delta\in\ZZ_+$, a set $S\subset\ZZ^d$ of points is a $\delta$-cluster if for all $s,s'\in S$, there exist $s^1=s$, $s^2$, ..., $s^p=s'$ such that $\dist(s^r,s^{r+1})\le\delta$ for $1\le r< p$.

Here is the problem I am interested in:

  $\text{Cluster}(S,\delta)$:
  Input: A set $S\subset\ZZ^d$ and a distance $\delta\in\ZZ_+$;
  Output 1: A partition $S=S_1\sqcup \dotsb\sqcup S_k$ such that each $S_i$ is a $\delta$-cluster and for all $i\neq j$, $\dist(S_i,S_j)>\delta$.
  Output 2: A list of $(k-1)$ couples $[(i_1,j_1),\dotsc,(i_{k-1},j_{k-1})]$, $i_s<j_s$ for $1\le s\le k-1$, such that:

  $S_{i_1}$ and $S_{j_1}$ are the closest clusters: $\dist(S_{i_1},S_{j_1}) = \min_{i,j\in\{1,\dotsc,k\}} \dist(S_i,S_j)$;
  If $S_{i_1}$ and $S_{j_1}$ are merged, $S_{i_2}$ and $S_{j_2}$ are the closest remaining clusters: $\dist(S_{i_2},S_{j_2})=\min_{i,j\in\{1,\dotsc,k\}\setminus\{j_1\}} \dist(S_i,S_j)$, where $S_{i_1}$ has been replaced by $S_{i_1}\cup S_{j_1}$;
  ...
  $S_{i_{k-1}}$ and $S_{j_{k-1}}$ are the last two clusters to be merged.

What is the complexity of (each step of) $\text{Cluster}(S,\delta)$, with respect to $|S|$, $d$, $\delta$ and $N=\max_{s\in S} \|s\|_\infty$?

I am mostly interested in the case $d\ll |S|$ and in the dependence on $|S|$.
One can define from $S$ a graph $G_S=(S,E)$ where $(s,s')\in E$ iff $\dist(s,s')\le\delta$. The graph $G_S$ can be constructed in quadratic time in $|S|$, and the partition is the partition of $S$ into connected components. Can we do better than quadratic time, maybe not constructing the whole graph? And once the partition is computed, what is the complexity of updating it?

For $\delta\in\ZZ_+^d$, we now define a $\delta$-cluster to be a set $S$ of points such that for all $s,s'\in S$, $|s_t-s'_t|\le\delta_t$ for $1\le t\le d$. This allows to construct a graph $G_S$ as above. Does the complexity change with this new measure of distance?

Final remarks.

I am mostly interested in the deterministic complexity of these problems, though any result may be of interest (probabilistic algorithm, fast algorithm in practice, and maybe most used algorithms for these problems, if they are as classic as I guess).
In the literature, all the references I find deal with the problem of finding $k$ clusters, where $k$ is an input of the problem rather than the threshold distance $\delta$.
If one takes the graph approach, there is some literature on updating connected components when edges are added. Though I suspect that this approach cannot do better than $O(|S|^2)$ while ideally I would like to be able to have a subquadratic algorithm.


texts: Is it more effective to vote for a woman?

texts:
A certain political party wants to encourage women to participate in their primary elections, so they decide, that the 4th position is reserved for a woman. That is, if there is no woman in the top 4 positions, then the woman with the largest number of votes will be promoted to the 4th position, and the candidates at positions 4 and below (5, 6, 7...) will be demoted one position (of course, if there is initially a woman in one of the top 4 positions, then no promotion/demotion will take place).

There are two candidates that I support equally, one is a man and the other is a woman. Is it true that, if I vote for the woman, my vote is more effective?

In a more extreme case, where the 1st position is reserved for a woman, it's clear that my vote is most effective when I give it to the woman, because this is my only chance of sending my favorite candidate to the 1st position; voting for the man, in this case, will never bring my favorite candidate to the 1st position.

Intuitively, it seems to be the same with the 4th position reserved, because, if I vote for the man and he enters position <=4, he might be demoted, but if I vote for the woman and she enters position <=4, she might be promoted, so my single vote may be worth a lot.

However, I am looking for a formal proof that this is the case (or maybe a disproof?)


texts: Help with deterministic selection algorithm

texts:
All we know what is Deterministic Selection Algorithm:

Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group $S[i]$, with $i$ ranging from $1$ to $n/5$.

Find the median of each group. (Call this $x[i]$). This takes $6$ comparisons per group, so $6n/5$ total (it is linear time because we are taking medians of very small subsets).

Find the median of the $x[i]$, using a recursive call to the algorithm. If we write a recurrence in which $T(n)$ is the time to run the algorithm on a list of n items, this step takes time $T(n/5)$. Let M be this median of medians.

Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.
In the case of dividing the array into five groups, we get the recurrence: $T(n)=T(n/5)+T(7n/10)$. That simply means that the value returned by partitioning is al least $3n/10−3/2$ and at most $7n/10+3/2$. However, what happens if we divide the array into 3 groups? What will be the upper and lower bounds? And what will be the recurrence of the runtime of the whole algo?

My thoughts: So the upper bound for $k=5$ is $7n/10 +3/2$. However, I do not understand where this $3/2$ come from? So for $k=3$ it should be like $2n/3 +?$. And also please explain what will be the lower bound? Thanks in advance.


texts: Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not

texts:
I am trying to show whether this language is regular or not:

$$L = \{0^m1^n  \mid m \neq n\}$$

Since I cannot create or think of an automaton that recognizes $L$, I am suspecting that $L$ is not regular. From the book I am using, it seems I can use the pumping lemma, I have done this:

Let $p$ be the pumping lemma constant, and let $w=0^p1^{p+1}$

In this case
$$|w|=2p + 1\geq p$$

We can divide $w$ into $xyz$, where $x=0^{p-1}$, $y=0$, $z=^{p+1}$, then $|y|\geq 1$

If L was regular, then $\forall k \geq 0, xy^kz \in L$. Let choose $k=2$, then:

$$xyyz=0^{p-1}001^{p+1}=0^{p+1}1^{p+1}$$

Here is where I am stuck, how do I prove that $L$ is not regular?

Another question, pumping lemma applies only to infinite languages?


texts: Master theorem and constants independent of $n$

texts:
I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):

$$T(n)=4T(n/2)+O(r)$$

$r$ is independent of $n$. Case 1 of the Master theorem applies and tells us that $T(n)=O(n^2)$.

However, this hides a constant dependent on $r$ in the big-oh notation: our recurrence has depth $O(\log_2 n)$ so at the final level we have $O(4^{\log_2 n})=O(n^2)$ subproblems, each of which takes $O(r)$ time to be handled. This means the actual running time is $O(n^2 r)$ (or worse: this analysis only talks about the lowest level).

This is my actual recursion:

$$T(n)=r^2T(n/r)+O(nr^2)$$

Is there a method similar to the Master theorem for these kinds of recursions?


texts: What's the difference between Process Context and Process Control Block?

texts:
I know that Process Context is something that is stored when a process is preempted, containing all the necessary info to restart the process at a later time.

I also know that the Process Control Block(PCB) contains all the necessary attributes of the process.

So, does that mean that the Process Context is a part of the PCB? Or is it the other way around? Or are these separate all together? Please help me understand where one ends and the other begins - as well as how they're used together.

What exactly is a process boundary?

Also, how is the PCB affected during a context switch (if at all)?


texts: How can I match handwritten character segments (including the direction they are written)?

texts: I am trying to test Chinese character production by having users draw the characters on their device. There are plenty of data models that include the character information already, so I will have that. My question is, how do I check if the user drew the stroke that is expected (with some sort of threshold value). Some of these segments may have curves in them, which makes it a little more difficult than just line matching. I have a video here demonstrating what I'd like to achieve. Notice how if I draw the wrong segment, or in the wrong direction, it is not accepted.


texts: Is Semantic Preservation Soundness (or Correctness) or Completeness

texts:
When transforming terms from one language to another, the intuitively desired property is the preservation of semantics (as used e.g. here for a CPS transformatation):

$$ s \Downarrow v \implies c(s) \Downarrow c(v) $$

I am a little troubled, however, by reconciling this with the classical terms correctness (or soundness) and completeness of logic systems. Usually, I would consider the above statement the completeness property of $c$ (and the converse the definition of correctness).

Intuitively, however, a compiler should be correct rather than complete (as e.g. type-checking often rules out correct programs). The converse of the statement above is only true if $c$ is injective:
If the source language contains for instance booleans and operations on them and the compilation replaces them via Church-encoding, the target language can evaluate boolean operations on terms compiled from boolean literals and lambda-abstractions, which the source language cannot evaluate.

Am I right to assume, that the above statement is the completeness property of $c$ (so the intuitive requirement actually has a counter-intuitive name)?
Am I also right in my conclusion that a non-injective compiler then is usually not correct?


texts: How difficult is this matching-like problem?

texts:
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand  "$i$ is matched to $j$" if $f(i)=j$. I am looking to solve
$$ \min_{f: A \rightarrow B} \sum_{j \in B} (\mbox{ number of nodes matched to } j)^2, $$
$$ \mbox{ subject to } |i-f(i)| \leq 2 \mbox{ for all } i \in A. $$
In other words, the function $f$ should not "move" any $i \in A$ too far and should come as close to a matching as possible.
Has something like this been studied before? If so, is it known to be NP-hard, or is there an obvious reduction? Are there any known variations on this (e.g., by changing the cost) that are polynomial-time solvable?


texts: Vertex which is present in all Minimum Dominating Sets for Bipartite graphs

texts: I am working on Minimum Dominating sets for bipartite graphs. There can be many minimum dominating sets of same size and I want vertex which is present in all of them. My approach for generating dominating sets is try all subsets of vertex and check if it is minimum dominating sets and then take the intersection of all the sets(this will give such vertex). Any clever way for doing this?


texts: Is there a way to *round* a nearby point into the feasible set?

texts:
Let $P \subset \mathbb R^d$ be a polytope with interior given by $F$-many linear inequalities. Suppose we have a convex problem with feasible set $P$. For example computing the Euclidean projection of some point onto $P$.

Instead of trying to directly solve the problem we run Langrange multipliers on the dual problem. This gives a sequence $\lambda_n \in \mathbb R_+^F$  converging to the dual solution  $\lambda^*$ and a sequence $x_n \in \mathbb R^d$ converging to the primal solution $x^*$.

We know $x^*$ is feasible but   $x_n$ might not be. In practice we never compute  $x^*$ itself  but only  $x_N$ for some very large $N$. Ideally we have theoretical results that say how big we must take $N$ to make the error less than $\epsilon$.

Doing that, we get an infeasible approximate solution $x_N = p$ that we know is distance $\epsilon$ of $x^*$. That means the ball of radius $2 \epsilon$ around $p$ intersects the interior, and we know $x^*$ is somewhere in that intersection.

To get a feasible point near $p$ the obvious thing to do is project onto $P$ . Unfortunately this amounts to solving another problem on domain $P$ and we're back to where we're started!

However we have in fact simplified the problem as any $y^*$ in the red region is feasible with $\|x^* -y^*\| < 2\epsilon$. Is it any easier to find such a $y^*$ than solving the original problem?


texts: Machine Learning - Support Vector Machines

texts:
I'm looking for good resources regarding Support Vector Machines, or suggestions where to start learning SVM.

Already used references:

Stanford ML course by Andrew Ng is great place to star
A Tutorial on Support Vector Machines for Pattern Recognition, Burges, 1998
SVM tutorials
Neural Networks and Learning Machines, Third Edition  Learning with Kernels - SVM, A. Smola


texts: If A is in P and B is non-trivial, then A ≤p B

texts:
On wikipedia's article on Polynomial-time reduction it states:

  Every nontrivial decision problem in P (the class of polynomial-time
  decision problems, where nontrivial means that not every input has the
  same output) may be reduced to every other nontrivial decision
  problem, by a polynomial-time many-one reduction. To transform an
  instance of problem A to B, solve A in polynomial time, and then use
  the solution to choose one of two instances of problem B with
  different answers

Some looking into the history of this entry reveals a link to math.SE that was referenced as a proof at one time.

However I am still confused as to exactly how this works. I understand polynomial-time reductions but there are some specific questions I have in regards to this statement.

Is it required that A is non-trivial as stated on wikipedia? Some places seem to suggest that the requirement is only B has to be non-trivial, and A doesn't matter if trivial or non-trivial. Based on this question.
Can someone provide me a concrete example of this working. I don't quite understand how there are two instances of problem B with different answers and how it relies on problem A to choose


texts:
Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10
couples.) There was a round of handshaking, but no one shook hand with his or her spouse. Afterwards, Mrs.
Smith asked everyone except herself, “how many persons have you shaken hands with?” All 19 answers were
diﬀerent.

Unfortunately, when I try to simulate a smaller problem with 3 couples, I am getting that each couple is shaking 4 hands. Here is the diagram:

As you can see both a1 and a2 have 4 blue lines each that are "attached" (ie they shake hands) to the other couples. Both b1 and b2 have 2 red lines and 2 blue lines. Do we count the blue lines again adding it to the 2 red lines giving us that b1 and b2 have 4 lines attached or do we just ignore the blue lines connecting to b1 and b2 and say that both b1 and b2 shake 2 hands each?

Both c1 and c2 also have 2 blue and 2 red lines. I meant to have blue lines designated for a1 and a2, and the red lines for b1 and b2. Does that mean that c1 and c2 have shaken 0 hands each? Or do I try another few lines attaching the c's to the a's and b's?

Another problem with the approach above is that each couple has the same number of handshakes even though that is not possible according to the question. I would appreciate any clarification on the question and what exactly am I doing wrong.

Thanks.


texts: What's the name of this problem? (Search for minimal satisfying sets)

texts:
NB:  I've been trying to Google for prior work on the problem described later in this post, but the search results I get for all the keywords I can come up with (e.g. minimal satisfying sets) are inundated with false positives.  In this post I'm just asking for terminology/nomenclature/buzzwords to make my Google searches more specific.

First, some assumptions and definitions.

We restrict our attention to subsets of some finite set $U$.  (IOW, below, a "set" is shorthand for a "subset of $U$".)

Let $p$ be a predicate on sets such that

$$(p(A) \land (A \subseteq B)) \Longrightarrow p(B).$$

Let's say that a set $A$ is satisfying iff $p(A)$.  If $A$ is satisfying, and no proper subset of $A$ is satisfying, then we'll say that $A$ is a minimal satisfying set.

The problem is:

  Find all the minimal satisfying sets.

More specifically, I'm looking for algorithms to find all minimal satisfying sets optimally (or at least efficiently).

I should mention a variant of this problem that I'm particularly interested in, just in case it goes by a different name.  This variant is the special case of the above where $p(U)$ holds.  IOW, we know that there is at least one satisfying set.


texts: Finding a minimum weight perfect matching in Christofides TSP algorithm

texts:
Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible.

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way?

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.


texts: What is a compact way to represent a partition of a set?

texts:
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly space-efficient.

What is a space-efficient way to represent a partition of a set?

Here is one possible starting point:

I know that the number of
partitions
of a set with $N$ elements is $B_N$, the $N$-th Bell
number. So the optimal space
complexity for representing a partition of a set with $N$ elements is
$\log_2(B_N)$ bits. To find such a representation, we could look for a
one-to-one mapping between (the set of partitions of a set of $N$ elements) and
(the set of integers from $1$ to $B_N$).

Is there such a mapping that is efficient to compute? What I mean by
"efficient" is that I want to convert this compact representation
to / from an easy-to-manipulate representation (such as a list of lists) in time
polynomial in $N$ or $\log_2(B_N)$.


texts: Proving non-regular language using the pumping lemma

texts:
I would like to verify that the following language is not regular.

I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in fact regular if the pumping lemma is valid)

So, given the following language,

$\Sigma =\{a,b\}$,
$L=\{v\cdot u\cdot u: v,u\in\Sigma^*,u\neq \varepsilon\}$

Can I show that the pumping lemma is not valid here?

Side note:

I think I can prove that this language is regular by using regular expressions like so:

denote $r= (a\cup b)^*$
now, $L=(a\cup b)^*\cdot (aa\cup bb)\cdot r\cdot r$

Is this true?


texts: Optimization of modular exponentiation using fft

texts:
My math/cs professor said it is trivial to optimize a modular exponentiation ($a^b \bmod c$) problem using fft, yet I am not able to understand how to do this.

I found 3 papers on this ([1], [2], and [3]). Papers 1 and 3 use Montgomery reduction, that too in different ways, and paper 2 seems to use a unique method compared to the other 2. I was not able to fully understand the papers not find any other material on this subject.

How would you optimize modular exponentiation using fft?


texts:
A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen sample from all $\tbinom{n}{k}$ possible samples consisting of seen items. So at each step $n \ge k$ we must decide whether to add the next item to $S$ or not. If so we must also decide which of the current items to remove from $S$ .

State an algorithm for the problem. Prove its correctness.


texts: Composition of polynomial and logaritmic function

texts:
Let $f$ be a computable function in $PSPACE$ It is true that Turing machine that computes $f$ can produce only $EXP$-size output at most. I see that $\log 2^n = n$ we can "control" the output. But, it doesn't convince me.

Please explain


texts: How are the control signals derived in the MIPS pipeline?

texts:
NOTE: Let me point out that I did try extensively to solve this on my own. The problem is that, based on that circuit, it would appear that this processor cannot jump. At best the jump instruction will propagate through the pipeline with no effect. There is no data path defined for a jump that tells the processor to change the PC. The only thing that changes the PC (aside from the normal PC+4) is a beq.

I'm learning about MIPS pipelining and stages, but what is excruciatingly unclear is how a jump instruction is executed. On an assignment question, I'm asked to trace the pipeline with the command "j 16", but there does not appear to be any details about how the logic is handled. The closest thing I can find of any relevance is to do with beq, but the opcodes are different... beq is 000100 and j is 000010. The following table outlines how the control codes work for four classes of opcodes, but it doesn't explain what happens for jump, and subsequently, how the machine knows to jump and what it does with the command...

So, if I have the instruction 000010 00000000000000000000000100, how does this get handled by the data path?


texts: Finding the middle point of the "most populated" area in a set of points?

texts:
I'm working on a game-related application, and I'm trying to find the middle point of the most populated area in my map.
Example:
Positions (format [x, y]) :

[48, 49]
[51, 50]
[49, 50]
[51, 49]
[49, 48]
[130, 150]
[129, 148]

Excepted output : [50, 50] or something close enough like [49, 51], [51, 50]

To create this algorithm I've access to all entities position (X/Y)
I've tried by creating a position using X average and Y average but it's not what i'm looking for (using example values output would have been [75, 75] or something like this and not [50, 50] as excepted)
Here is an example image:
Red dot: Entities
Green dot: Position i'm looking for

Thanks for reading and for your help!


texts: Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma

texts: I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying to prove?


texts:
I'm a student. today I answered a question wrong, the question is this:

Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ elements each time with $O(1)$.
What is the best time complexity we can give from this sort? (you can use just the magical function)

I answered it $O(\frac{n^2}{k})$ because I thought that with $O(\frac{n}{k})$ times using the magical function we can sort the maximum number, so we repeat it $O(n)$ times to sort it completely. that's $O(n)\times O(\frac{n}{k}) = O(\frac{n^2}{k})$.
But seems that I was wrong and the right answer is $O(\frac{n^2}{k^2})$.
So I'm here for some help because I can't solve it myself. thanks in advance.


texts: Formal definition of a language accepted by PDA

texts:
I am a bit confused on how to give a formal definition of the language accepted by A?

I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" and I have tried to give a formal definition by:

L(A) = {a^n c^n b^n | n ∈ N}

Is that the correct way to define it?


texts: Deleting vertices so that largest connected component has at most $n/2$ vertices

texts:
I have a question regarding a graph algorithm which is as follows:

Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such that deleting vertices $1$ through $k$ results in a graph whose largest connected component has at most $n/2$ vertices (when we delete a vertex we also delete all edges incident to that vertex). Give an $O(m \log^* n)$ algorithm that determines $k$.

The graph at the beginning could be disconnected, nor at the end need it be connected.
Since $O(m \log^*n)$ is almost linear, $\log^*n$ grows very very slowly like in union-find data structure so this algorithm is almost linear time like union-find. I am trying to solve it through union find but it seems I am doing something wrong. Now I think that I should use union-find as a black box, but I ca'nt figure it out.

This is a practice problem, not homework.


texts:
I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align*}
\sum_{k=1}^{n} k &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\
&\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\
&= (n/2)^2\\
&= \Omega(n^2)\,\end{align*}$$

I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in other. How does this method work? Can anybody explain?


texts: what does activation function become in spiking neural network?

texts:
In common ANN, nodes are based on a activation function, like a sigmoid or tanh or ReLU. Updates of synaptic weight are based on the derivative of this function.

When node are represented with spiking neurons, what does activation function become ? how updates of synaptic weight are done ?


texts:
Graph invariant is a property that holds for two isomorphic graphs.
For example, degree sequence is graph invariant. We can write
$d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ does not mean that $G \cong G'$.

I search for a name (and maybe some existing examples) for complementary graph invariant. Let $p$ be complementary graph invariant, then $p(G) = p(G') \Rightarrow G \cong G'$; however $p(G) \ne p(G')$ does not imply $G \ncong G'$. For example, for two isomorphic graphs adjacency matrix is such complementary graph invariant as two graphs with the same adjacency matrix are isomorphic, and there exists two isomorphic graphs with different adjacency matrices (take a permutation). So, is there a standard term/name for complementary graph invariants; and if so, where I can read more about them (examples, complexity, etc.)?


texts: Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

texts:
I would like to get some help for finding the context-sensitive grammar for the language:

$$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$

To answer the question before it's written here, yes I've tried to construct it myself, but my attempts are far from promising, so I don't include them, because there is no point (also I've tried to find a similar question - without luck).

Additionally, although I'm familiar with the one question per post rule, I'm adding another language here:

$$L_2=\{a^ib^jc^{i^j} \mid i,j\geq 0\}.$$

(The reason is that I think these two have a similar solution — of course if I'm mistaken, I will erase it.)

Please include the thought process as I've just started learning grammars. Any hint appreciated.


texts: Why don't most websites I visit seem to use TLS with Ephemeral Diffie-Hellman?

texts:
When I click "view certificate," under Public Key Algorithm it usually says "RSA Encryption" or "Elliptic Curve Public Key." I assume this is the algorithm used to agree on a premaster secret (symmetric keys) between the client and server, or steps 4-6 in the image below. Why not use Diffie-Hellman then? Doesn't ephemeral Diffie-Hellman provide forward secrecy?

TLS handshake


texts: Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

texts:
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (an example) that I disagree with:
$M$ is a non-deterministic polynomial by time Turing machine that decide $SAT$, if all that paths   are rejected then $L(\overline{M})=\Sigma^*\in P$
Is it a valid solution, or as I'm thinking $L(M)\in NPC$ and $L(\overline{M})\in P \Leftrightarrow P=NP$


texts: Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

texts:
I have to determine, and prove, whether the language  $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma).

I tried to construct a grammar, but I don't have a working one. I have no problems to construct the language $L=\{a^{2n} \mid$ n is a natural number$\}$. So I tried the pumping lemma, but I don't find the proof, that this is not context free.

Can someone tell me of what type this language is? A hint how to prove this would also be very nice.


texts: Exponential time local search heuristics for Weighted MAX-CUT-Flip

texts:
I have read multiple times [Theorem 5.15, 1][End of page 2, 2] that local search heuristics for $\textsf{Weighted Max-Cut}$ with $\textsf{Flip}$ neighbourhood takes an exponential time in some cases.

In particular, the problem is as follows. Given a partition $(V1,V2)$, its neighbours are partitions which can be obtained by moving one vertex from $V1$ to $V2$, or from $V2$ to $V1$. Such neighbourhood is polynomial in size. At each step algorithm chooses the neighbour with highest value strictly greater than that of the current partition (o/w, it is locally optimal and so the algorithm terminates).

I am asking for a weighted graph and an initial partition of the vertices such that the above local heuristics would need exponential number of iterations to get to a local optimum.

I have not seen a single concrete example.

References

[1] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to
solve. SIAM J. Comput., 20(1):56–87, February 1991.

[2] Lecture notes: https://courses.engr.illinois.edu/cs598csc/sp2011/lectures/lecture_12.pdf


texts: 3-SAT problem with number of clauses equal to number of variables

texts:
Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is this problem still NP-hard?

For example, this formula has $3$ variables and has $3$ clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3 ) \wedge (\lnot x_1 \vee \lnot x_3) \wedge (\lnot x_2 \vee \lnot x_3)$,

and the following formula has three variables but has only two clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3  ) \wedge (\lnot x_2 \vee \lnot x_3)$.


texts: Soft Margin Loss and Conditional Probabilities

texts: Consider the following soft margin loss function: $\max(0, 1-yf(x))$.  I have the problem of needing to compute the conditional probability $p(y|x)$ corresponding to this function and am having trouble making the connection between conditional probability and this function.  I have come across a few papers (e.g. http://www.unc.edu/~yfliu/papers/lum.pdf) that say that "soft classifiers explicitly calculate the class conditional probabilities", but I do not understand how as the output of a classifier is not a probability.  Can someone please explain what I am missing?


texts: How to show that if 0 < $\alpha$ < 1, RP$_\alpha$ = RP using reliability amplification

texts:
Let $0 \le \alpha \le 1$. The complexity classs $\mathsf{RP}_\alpha$ consists of all languages $L$ for which we can find a probabilistic polynomial time Turing machine which satisfies the following conditions:

$w \in L \Rightarrow \Pr[\text{accept}] \geq \alpha$.
$w \notin L \Rightarrow \Pr[\text{accept}] = 0$.

We define $\mathsf{RP}$ to be $\mathsf{RP}_{1/2}$.

How would I show that if $0 < \alpha < 1$ then $\mathsf{RP}_\alpha = \mathsf{RP}$ using reliability amplification?
How would I show that when $\alpha = 1$, $\mathsf{RP}_\alpha = \mathsf{P}$?


texts: ML Algorithms to discriminate "known" from "unknown" instances

texts:
I'm classifying different electrical devices based on features extracted from their electricity consumption into a household-specific model built from around 10 devices. Now I want to detect whether a classified testing instance is coming from a device which has not been present in the training set, i.e. I want to discriminate known from unknown devices.

I'm working with Weka and use the Classifier.distributionForInstance() method to give me the (classifier-specific) probability distribution for those 10 possible classes for each instance.

Now, the problem is that some classifiers (SMO, NaiveBayes, J48 and other trees) most of the time classify a not known device with a high probability of almost 1 to a class, whereas RandomForest (preferably with high amount of trees) and IBk (kNN) perform rather well in giving back lower probabilities of classification/more uncertain results.

The questions I have:
Can you think of alternative approaches or any other algorithms/methods?
Why is it, that the first stated algorithms strongly decide for one class. I would have expected them to return unclearer results.

thx, regards


texts:
I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer.

Initially, I was thinking that in order to make the computations as fast as possible, the GPU would use some kind of lookup table. But then I realized, storing all sin values in a table of the range of doubles between [0, 2 * pi] would be a massive one, and thus not be a valid option.

The table could possible be shrunk down in resolution, and the missing values for a lookup can then be lerped. This however, introduces a possible error which can propagate to bigger and unacceptable errors when performing the computation multiple times.

My last idea is then that they could be using a Taylor approximation, but that would involve quite some arithmetic, which may be too slow for a GPU. So the question is, what do GPUs use to calculate the sines? Are it lookup tables, approximations, or a hybrid of both? And possible, do they use the same method for other computations like sqrt()?


texts: Minimum spanning tree - Prim's algorithm

texts:
I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I did wrong ?

Here is the exercise:

The first solution (using Prim's) is visiting the nodes in the following order: v0,v1,v8,v7,v6,v3,v2,v4,v5 Here the MST has a weight of 37, which is the same result that I got by using Kruskal's on the same graph.

The second solution (again using Prim's) however is the following order of visited notes: v0,v1,v3,v2,v7,v8,v6,v4,v5 , which leads to a MST with a weight of 39. How can this be ? Where is my mistake ?

Thanks in advance


texts: What distributed consensus algorithms don't rely on a time source?

texts:
I'm looking for information about distributed consensus algorithms that:

maintain a consistent transaction log across all healthy nodes
have similar high-availability properties to Paxos (i.e. not liveness, but practically very likely to terminate in reasonable time)
make progress with 2F+1 nodes despite F simultaneous node failures
where failures can include complete/partial/simplex network partitions
work over a reliable, unicast-ordered, but potentially non-timely network
do not use system/wall clock time

Paxos and Raft both fulfil all criteria but the last – I'm wondering if there are any variants or other algorithms that fulfil all? I have looked but all variants I've come across seem to use some form of timeouts.


texts: Probability of hash collision in the case of two parallel hashes

texts:
I understand how to calculate the probability of a hash collision.
I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I could potentially query two hashes to determine probable record matches.
If I have 1 billion records, a 64-bit hash will have $\sim 1:32.5$ collisions. If I have two by 64-bit hashes, how many effective bits will I have?
65-bits seems pessimistic, 128-bits seems optimistic. $\sim 32.5^2$ results in a fraction over 69 bits hash resolution.
How do I calculate this?
ILLUSTRATION
Parent Table
parent id, $\{$ field $1$, field $2$, ... field $n \}\implies$  parent hash
Child Table
child id, parent id, parent hash, $\{$ field $1$, field $2$, ... field $n \}\implies$ child hash
As illustrated, the child table has both parent hash and child hash. Two by 64-bit hashes.


texts: How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing?

texts:
One can define the semantics of one definite word using the references to real world entities, relationships with the other words and other concepts and represent all this knowledge about this one word using logical symbolic expressions. And then one can encode all this set of symbolic expressions into vector of real numbers. This is word embedding that is used in natural language processing, distributional semantics of the word in opposite of the formal semantics of the word.

One can consider function of software program (e.g. functional program or any other program). One can encode this program in the multiple vectors and matrices of real numbers that are used for the definition of neural network.

One can consider symbolic meta-knowledge and encode them into vectors or neural networks as well.

The decoding process can be more tricky. There is more or less elaborate decoding of neural network - e.g. see Google queries "logical program extraction from neural networks" or "symbolic rule extraction from neural networks". But I have not seen the work about extraction of more or less static knowledge base from the word-embedding-vector.

So - I have two questions regarding this matter:

Is there symbolic knowledge extraction from the word-embedding vectors - some kind of decoding algorithm from vector of real numbers to the set of logical formulas?
Is there general theory of mentioned encoding algorithms? The usual approach is to train neural networks and to arrive at the encoded form using non-symbolic methods, non-algorithmic methods, implicit way. I have heard about embedding of symbolic knowledge in neural networks to speed-up training, but such kind of work is scarce. But what about general encoding algorithms?

There are discrete, natural Goedel numbers (encoding algorithms) that can be assigned to any theorem of first order logic. But what about such Goedel numbers for the sets of formulas or for some computational program (as a set of commands)? Can we enumerate all such sets using natural numbers only or maybe the real numbers are needed instead naturally. Or maybe even set of real numbers are required for encoding the set of symbolic formulas or program statements? Is there such research work which I can develop further? If no, then what ideas can be mentioned for such encoding/decoding schemes?

Such encoding-decoding algorithms can be related to biological computing and ultimately they can lead to the explanation of brain activity.


texts: How does these Probing time occurs for hash tables

texts:
I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is given here.

  Let $\alpha = N/M$ (the load factor: average number of keys per array index). Analysis is probabilistic, rather than worst-case.

  Expected number of probes:

  $$\begin{eqnarray*}
&\text{not found} & \quad\text{found}\\
\text{chaining}\quad & 1+\alpha &\quad1+\frac\alpha2\\
\text{linear probing}\quad & \frac12 + \frac1{2(1-\alpha)^2} &\quad \frac12 + \frac1{2(1-\alpha)} \\
\text{double hashing}\quad &\frac1{1-\alpha} &\quad \frac1\alpha \ln\frac1{1-\alpha}
\end{eqnarray*}$$

A clarification of why the numbers are as they are would be appreciated. :)


texts: Finding a 5-Pointed Star in polynomial time

texts:
I want to establish that this is part of my homework for a course I am currently taking.  I am looking for some assistance in proceeding, NOT AN ANSWER.

This is the question in question:

  A 5-pointed-star in an undirected graph is a 5-clique. Show that
  5-POINTED-STAR $\in P$, where 5-POINTED-STAR = $\{ <G>$ $: G$ contains a
  5-pointed-star as a subgraph $\}$.

Where a clique is CLIQUE = $\{(G, k) : G$ is an undirected graph $G$ with a $k$-clique $\}$.

Now my problem is that this appears to be solving the CLIQUE problem, determining whether a graph contains a clique with the additional constraint of having to determine that the CLIQUE forms a 5-pointed star.  This seems to involve some geometric calculation based on knowledge of a 5-pointed star.  However, in Michael Sipser's Theory of Computation, pg 268, there is a proof showing that CLIQUE is in $NP$ and on page 270 notes that,

  We have presented examples of languages, such as HAMPATH and CLIQUE,
  that are members of NP but that are not known to be in $P$. [emphasis added]

If CLIQUE is not in $P$, why five pointed star be in $P$?  Is there something I'm not seeing?
Remember, this is a HOMEWORK PROBLEM and A DIRECT ANSWER WOULD NOT BE APPRECIATED.  Thanks!


texts: What do you call a function from symbols of alphabet to languages?

texts:
Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows:

Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, where $L'$ is some language. I also met this definition: $f:\Sigma \to 2^{\Delta^*}$.

The reason I'm asking this is because I study in a language which is even more foreign to me than English, and it's hard to find what the terminology in the book means. I've only encountered this in connection to context-free languages, but since I don't really know what I'm looking at, I can't tell if that's something specific to them (my guess though is that it's not).

In the book I'm reading from, (which also happens to be in Hebrew) the word used to describe this concept is "הצבה", literally meaning "substitution" or "positioning", "fixing something in place".


texts: What was the first Turing-Complete programming language?

texts:
What was the first turing-complete language? Know about the first machines
and computers, but not the programming language.


texts: Isn't polynomial identity testing over arithmetic *expressions* trivial?

texts:
Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial can be made exponentially large by repeated squaring. This question addresses the issue of how to work around this and keep the problem in randomized polynomial time.

On the other hand, when the problem is initially presented (e.g. here), it is often illustrated over arithmetic expressions containing only constants, variables, addition, and multiplication. Such polynomials have total degree at most polynomial in the length of the input expression, and for any such polynomial the size of the output value is polynomial in the size of the input values. But since a polynomial of degree $d$ has at most $d$ roots, isn't this trivial? Just evaluate the polynomial over the rationals at any $d + 1$ distinct points and check whether the result is zero at each point. This should take only polynomial time. Is this correct? If so, why are arithmetic expressions without shared subexpressions often used as examples, when sharing is essential to the difficulty of the problem?


texts: Why don't compilers automatically insert deallocations?

texts:
In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically? Humans do it in a reasonable amount of time(ignoring bugs), so it is not impossible.

EDIT: For future reference, here is another discussion that has an interesting example.


texts: What is role of parameter learning rate, lr, and momentum constant, mc in Neural Networks?

texts: can anyone describes the more simplified mathematical formulation of learning rate, lr, and momentum constant, mc in Neural Networks while training the data?


texts: The importance of the membership problem

texts: Given a word $w$ and a language $L$, we want to check if $w\in L$.  This is called the membership problem. Why is the membership problem important?


texts: Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?

texts: For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make sense to me since a while program always returns an element of the integers. How can I use code in my proof?


texts: ways to rearrange a closed graph with cycles

texts:
Let's say  we have the following graph defined by its initial node, final node, and edges in a transition table:

what are the possible ways to rearrange this data structure in order to have something easily representable as the following (using dot or graphivz for example):


texts: Big O running time for this algorithm[function call from within a loop]?

texts:
So the basic doubt i had started with this piece of code

def fn2(a,n):
    .
    .
    for i in range(0,n):
        .
        .
        .

def fn1():
    .
    .
    for i in range(1,n+1):
        fn2(a,i)

Would this be considered as a loop within a loop or will this take more than the usual O(n2) or would it take greater time then that ?


texts: How many edges must a graph with N vertices have in order to guarantee that it is connected?

texts:
Possible Duplicate:
  Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

At lesson my teacher said that a graph with $n$ vertices to be certainly connected should have
$ {\frac{n(n-1)}{2}+1 \space }$ edges showing that (the follow is taken from the web but says the same thing):

  The non-connected graph on n vertices with the most edges is a complete graph on
  $n-1$ vertices and one isolated vertex. So you must have $ 1+
{\frac{n(n-1)}{2} \space}$ edges to guarantee connectedness.

My idea: a complete graph $K_{n-1}$ with $n-1$ vertices has ${n-1 \choose 2}$edges,  so ${\frac{(n-1)*(n-2)}{2}}$ edges, added to the edge to connect the complete graph to the isolate vertex,

so shouldn't be ${\frac{(n-1)*(n-2)}{2}}+1$ edges?

What am I doing wrong?

Thanks.


texts: Does the order in which qubits are measured matter in quantum computing?

texts:
I’ll define my question more specifically:

Lets suppose we have an $n$ bit quantum computer, with qubits labelled $q_{1},…,q_{n}$, and let $b$ be any bit string of length $n$ (let’s assume we’ve labelled each qubits’ states $0$ and $1$ so that we obtain an $n$ bit bit string when we measure the qubits).

The question is, is the probability that we obtain $b$ when we measure each qubits’ state dependent on the order in which we measure the qubits?
I have a feeling the probability would be independent of the order the qubits are measured, but am struggling to prove this.


texts: Efficiently find smallest unique substring

texts:
Let's say we have a string $s$. We define a unique substring in $s$ as a substring that occurs only once in $s$. How can we efficiently find such a substring with the smallest length in $s$?
The most obvious solution is in $O(n^3)$ by checking every substring. What if we can preprocess the string?


texts: Dempster-Shafer theory initial belief values

texts:
I am looking to implement D-S Theory in my (computer science) research, I'll be using it to determine the probability that a triggered sensor event is a true positive.

How would you calculate an initial belief value without having the ability to perform data mining on a dataset (a cold start)?

One solution that has been postulated is to use the manufactures performance statistics that the sensors are working correctly and then adjust this over time to take account for false positives. Although this will result is a very high initial belief rate for some sensors (95% belief).


texts: Are Physical 2-Person Lock Systems Informed by The Byzantine Generals Problem

texts:
The Byzantine Generals Problem says a set of generals who are greater than 2/3rds loyal is required to guarantee that securely issuing an order is possible the loyal generals.

Because of this, I am curious why so many physical systems opt for 2-person systems, like the two-man rule for launching nukes in the US (two authorized people are supposed to be required to authenticate any nuclear launch) or two-key systems for things like bank vaults etc. I've never seen 4 or 10 lock systems depicted in media and that seems like something media would play up if it existed.

On the one hand, systems with larger numbers of locks require more defecting "generals", which by itself makes it much harder to gather/orchestrate that many people without being caught. This would also make the system more hardened to defectors, unlike the 2-man rule. If a single soviet spy infiltrates a the launch team for a silo, a launch can be subverted. Not the case with a "four-man rule".

On the other hand, mechanical systems with more keys become more difficult to construct and keep secure. And maybe the process of vetting individuals to be launchers or vault guards doesn't scale well, and you just want put all your eggs in the basket of being really sure that the two launchers are secure.

I asked my advisor, and he told me it's only two because "it's the byzantine generals problem", which I guess it is in the sense that it's distributed consensus. But A) it's also not because most of these considerations are outside the theoretical limits of the problem/solution as far as I can tell (how hard it is to vet people, how hard it is to construct the physical systems which rely on the secure consensus) and B) even to the extent that it is the byzantine generals, it's still unclear to me why that would proscribe a set of 2 generals for these systems.

Does the byzantine generals problem really prove or show that these systems are best left as 2 person systems?

Are physical locking systems with more than 2 people ever used? What, if anything, has gone into deciding that 2 is good, but 4 or 10 lock systems for is difficult to engineer around? Mostly just curious if there is some kind of disagreement across domains on what best practices are for security, and why these differences exist, and mostly if I'm totally missing something about the byzantine generals problem.


texts: Why is the complexity of the BFS O(V + E)?

texts:
Consider the algorithm (from another question):

set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex

The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check if its not visited N-1 times. So, that's N * (N-1) tests, which is quadratic. What is wrong with this view?


texts: 3-Approximation for General position subset

texts:
I am currently studying for an exam and stumbled upon the following task:
Given the following problem:

Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$

Question Find the maximum subset $S \subseteq P$ such that no three points in $S$ are collinear.

The task is to find a polynomial time 3-approximation algorithm that is an algorithm that deletes at most $3$-times as many points as an optimal solution. Unfortunately, I am totally clueless here. How would such an algorithm look like?


texts:
You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$:

  How many elements are there between indexes S and E, that are less than X? $( |L| : \forall l \in L \leftrightarrow A[l] < X  \bigwedge S\leq l \leq E )$

$X, S, E$ will vary from query to query, and there will be at most $1\,000\,000$ queries.

I found a lot of algorithms based on kd-trees, but they have complexity linear in the size of the output. Are there any other options, maybe using the property that X and Y coordinates are unique?


texts: Proving the pigeonhole principle in Cutting Planes

texts:
Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf

  Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i<j\leq n$.

  Find a derivation of $\sum_{i=1}^n x_i\leq 1$ in $O(n^2)$ length.

If it were just algebra I could just show by contradiction that at most one $x_i$ could be 1 and be done but how does it translate it into cutting planes PS? I guess a similar idea would be by obtaining $\sum_{i=1}^n x_i \leq n-1 -(n-2)x_i$ for all $i$ through addition of $x_i+x_j$ for all $1\leq j\leq n$ but I'm stuck there.

Thanks for your help.


texts:
Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how to efficiently apply those algorithms considering the cost of block transfer from external memory ? For example, almost all algorithm textbooks say that B and B+-trees can be used to store data on disk. However, actually how this can be done, especially handling the pointers where the data is present on disk is not explained. Similarly, though many books teach searching techniques, they do not consider data present in secondary memory.

I have checked Knuth's book. Although it discusses these ideas, I still did not understand how to actually apply them in a high-level language. Is there any reference that discusses these details?


texts: Language Accepted by a Turing Machine with a Useless State?

texts:
What language is accepted by a Turing machine which has a state that it does not enter on input I?

Specifically,

1.If the accept state is the state that it never enters then should L={empty}?

2.If the reject state is the state that it never enters then should L={everything}?

3.What if the TM has multiple accept/reject states?

4.What if the state that it never enters is neither the reject nor accept states? How does that affect L?

I have searched around and I have found a couple threads that helped prove that this problem is undecidable but is it Turing-recognizable? Co-Turing Recognizable? Both?


texts: Search Algorithm with two areas of solutions

texts:
I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute force method. So I just enhance the variable by a factor, enter the variable to the algorithm till I get a true.
This really needs a lot of run time. Then I switched to the bisection method. Here I had the problem that sometimes the function is true for some values and then switches again to false. This means if the area is before the half of the interval, the bisection method can not find the area before because the bisection method doesn't get the true in therefore took the second half of the interval.

My question is now: does sb has an idea how I could fix that? Are there any search algorithms which are exactly for that problem?


texts: Induction pitfalls with O notation and recursion

texts:
I read the following in CLRS 3rd Ed:

I'm not sure I understand exactly how to avoid this pitfall.

How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not constant?
What's a good way to systematically avoid this type of pitfall?


texts:
I have a list of patterns with each pattern containing one or more wildcards. For example:

abc*
a*
*a*z*
*z

Wildcard (*) matches one or more characters. For example, any input string starting with 'a' would match a pattern a*.

How can I determine if there exists an input string that would match all of the provided patterns?


texts: Regular Expression for even-odd language of string

texts:
I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'s. I am also interested in constructing a DFA and NFA for the language.

I tried

  Even number of $b$'s = $(a^{\ast}ba^{\ast}ba^{\ast})^{\ast}$

Edit: I got  DFA and NFA for odd number of $a$'s and even numbers of $b$'s and still unable to make regular expression which will allow only even number of $b$'s and odd nubmer of  $a$'s .
I also tried this Regular Expression

  $(a(bb)^{\ast}(aa)^{\ast})^{\ast} $

Note: From above RE only  those strings are generated which start from a but i want that RE which generate string of even number of $b$'s and odd number of $a$'s regardles of starting from a or b


texts:
Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.
Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

Construct the following TM $M_2$:
$M_2$ = “On input $x$:

If $x$ has the form $0^n 1^n$, accept.
If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$.”

Run $R$ (a machine solving $\mathsf{REGULAR_{TM}}$) on input $\langle M_2 \rangle$.

If $R$ accepts, accept; if $R$ rejects, reject.”

I am trying to understand this proof, but I am really confused with step 1 of $M_2$.
The book says "$M_2$ works by automatically accepting all strings in $\{0^n1^n \mid n ≥ 0\}$. In
addition, if $M$ accepts $w$, $M_2$ accepts all other strings."
But I don't understand how could $M_2$ accept all strings. If $x$ is not of the form $0^n 1^n$ and $M$ does not accept $$, wouldn't $L( M_2 )$ be empty?. Or can we assume there are many different $x$ as an input to $M_2$?


texts:
In C++ a simple function like

int id_int(int x){return x;}

has type id_int :: int->int
a class template like

template<class T>
class List<T>{...};

has kind List :: *->*

But what is the type or kind of a function template like

template<class T>
T id(T x){return x;}

Could it be id :: \x. x->x? Does this even make sense?


texts: What future working opportunities do computer science students have?

texts:
If I am right students learning computer science at universities learn very theoretical kind of knowledge. A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?


texts: Closure of context-free languages under "removal of a regular language from the right"

texts:
I have a homework that I can't solve can somebody help me?

If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for some }\beta\in R\}$$ context-free?


texts: Is this the correct "standard form" of nonlinear programming (optimization) problem and if it is why it's in this form?

texts:
Rather a simple question I guess, though makes me wonder. The standard form I've found in the book (and on wiki) is something like this:

$\min f(x)$

s.t.

$h_i(x) = 0$

$g_i(x) \le 0$

Is this considered a "standard form" for nonlinear optimization problems? And if it is why it's defined like this? Why it has to be exactly the min of the function and why constraints have to be either equal or less than 0 or equal to 0? I couldn't find any answer why it is as it is actually. Is there some important thing why it couldn't be max actually for example?


texts:
I have difficulties in understanding the notion of density for distribution.

Notion of density for distribution. A distribution $H$ over $\{0,1\}^n$ has density $\sigma$ if for every $x \in \{0,1\}^{n}$, $Pr[H=x] \leq \frac{1}{2^n\sigma}$.

The following is my desperate tries to understand the notion.
if $H$ is uniform distribution over $\{0,1\}^n$ then  for every $x \in \{0,1\}^n$, $Pr[H=x]=\frac{1}{2^n}$.

if a distribution $H$ has density $\sigma = 1$ then $P[H=x]\leq\frac{1}{2^n}$, so distribution $H$ is upper bounded by the uniform distribution.

if a distribution $H$ has density $\sigma = \frac{1}{2}$ then $P[H=x]\leq\frac{1}{2^{n-1}}$, so distribution $H$ is upper bounded by the uniform distribution over $\{0,1\}^{n-1}$.

if a a distribution $H$ has density $\sigma = \frac{1}{2^n}$ then $P[H=x]\leq 1$.

So density $\sigma$ might determine the part of distribution over $2^n$ where the actual "probabilistic weight" should be placed? However it's always upper bounded, therefore we can always say something about the upper bound?

As you see I don't have intuition behind this notion and I would appreciate any help.


texts: What ML Algorithm can "coloquialize" stings of text?

texts:
I am looking to colloquialize short natural language strings and titles to more proper grammar, and do the same in reverse.

For example, I'd like to find an ML algorithm that, given the proper data set and training, can convert "y'all" to "you all" or "she was like" to "she said". Even professional titles: "Director, Human Resources" becomes "Director of Human Resources".

To be clear, I have many thousands of strings that need to be colloquialized so I can't do this in a deterministic way.

Can someone please tell me what the proper ML algorithm would be for this type of thing so that I can research?

I thought at first that it would be a Naive Bayes classifier until I realized that we would end up with thousands of classification categories and that is no good.

Thanks!


texts: Term for the tree of all paths starting from a given vertex in a graph

texts:
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?

This is the tree that is implicitly or explicitly constructed when doing shortest path search.  It appears, for example, in a lecture on search of an MIT Artificial Intelligence course, but I didn't understand if it has a name.

This is not a search tree and not really a decision tree.

Mathematically, it is a covering tree, but is there a more appropriate term in the context of shortest path search?


texts: Hamming distance necessary for detecting d-bit error and for correcting a d-bit error

texts:
I am trying to understand what hamming distance of a code is needed to detect a d-bit error, or to correct a d-bit error.

This is what I have found around the web:

  If two codewords are Hamming distance $d$ apart, it will take $d$ one-bit
  errors to convert one into the other.

  To detect (but not correct) up to $d$ errors per length n of a codeword,
  you need a coding scheme where codewords are at least $(d + 1)$ apart in
  Hamming distance. Then d errors can't change into another legal code,
  so we know there's been an error.
  To correct $d$ errors, need codewords $(2d + 1)$ apart. Then even with $d$
  errors, bit string will be $d$ away from original and $(d + 1)$ away from
  nearest legal code. Still closest to original. Original can be
  reconstructed

I have seen in my other post that, in the image, the calculation of the bits that can be detected and correct is done using the reversed formula of the above statements 1. and 2:

If we have a hamming distance of $d$, we can detect $d - 1$ errors (inverse of the formula 1.), so to detect a $d - 1$ error, we need a hamming distance of d (same thing said in another way). So for example, if we want to know what is the hamming distance required to detect a 4 errors, we just have to apply the formula 1.

$4 = d - 1$

$4 + 1 = d$

We need a hamming distance of 5.

So to find the hamming distance required to correct $d$-bit errors, we have to apply the formula 1. $2d + 1$, where $d$ are the bit errors.

Am I correct?

If yes, could you explain me what the second part of the point 2. is saying:

  Then even with $d$ errors, bit string will be $d$ away from original
  and $(d + 1)$ away from nearest legal code. Still closest to original.
  Original can be reconstructed

By d-bit errors, we mean d number of errors, right?


texts: How does the assembler translate english assembly to binary machine code instructions?

texts:
My assumptions (please correct me if anything in this part is wrong including wrong usages of jargons)
In MIPS instructions, add t1 t2 t3 translates to 00000001010010110100100000100000 . The add, t1, t2, t3 I suppose first of all get translated to some ASCII value implemented on the hardware level. For example,  t1 is 116 049 in binary by the ASCII convention. But then, these ASCII values gotta map to the instruction. Per the MIPS op code specification, add corresponds to the last 6 100000 bits, t1 corresponds to the 01001 bits in the middle, etc.
Question
Assuming my assumptions are correct, how exactly does the assembler take the 116 049 and map it to 01001? In this course called nand2tetris, I've been writing an assembler in C which is really just a text parser. Obviously, C gets translated to assembly, so the actual assembler has no access to it. Thus came the confusion.