title: Algorithm to Compute High Water Mark

text:
# Question
Title: Algorithm to Compute High Water Mark
I saw this algorithm question which is as below. There is a server that receives request Ids that are positive integers. The High Water Mark (HWM) for the server at any instant of time is defined as the highest integer request Id n such that every positive integer request Id less than n has already been received.

For example, if the server gets 5 request Ids as below,
1, 6, 2, 3, 9
Then at the end of the 5th request, the getHWM() method should return 3 as 1, 2, 3 are already received but 4 is not yet received.

Similarly, for the above test case, the HWM at the end of the 3rd request, the HWM would have been 2.

My approach to this problem had been as below.

Maintain a variable `hw` that keeps up with the live HWM at any instant of time. Further, maintain a HashMap that stores all the requests which have been received.
Whenever a new request `x` is received, add `hw` to the HashMap. Start iterating over every positive integer in increasing order from `hw` and check if it is in the HashMap.
If it is in the HashMap, add increase `hw` by 1. Else break the loop.

A disadvantage of this approach is that it might iterate over a large list of integers.

An example can be the test case below.
1, 2, 3, ..., 4445, 4447, ..., 8888, 4446.
(it would need to iterate from 4446 to 8888 to compute `hw` after the last request.)

---

Another approach would be to group the `requestIds` received in a sorted list.
(1-3) -\> (7, 13) -\> (16, 183),
search if the new requestId belongs to a particular group. Else add/merge merge nodes of the list.

Can someone suggest a more efficient approach to this problem?

# Answer
You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem.

We maintain a list of intervals $\[a\_1,b\_1\],\[a\_2,b\_2\],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a\_i,b\_i$ in a hash table.

Given a new integer $c$, we can update the data structure by looking up $c-1$ and $c+1$ in the hash table (details left to you).

To find the high water mark, simply look up $1$, and output the endpoint of the interval (if any).

Altogether, we have managed to implement all operations in $O(1)$.
> 3 votes

---
Tags: algorithms, data-structures, trees, arrays, linked-lists
---


# Question
Title: Finding an Algorithm for the HAPPY-CAT problem
I'm trying to develop an the algorithm for the problem:

The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called “Hole.” Cat wins if the two players ever occupy the same node. Mouse wins if it reaches the Hole before the preceding happens. The game is a draw if a situation repeats (i.e., the two players simultaneously occupy positions that they simultaneously occupied previously, and it is the same player’s turn to move).

In other words, we have to decide: HAPPY-CAT = {\<G, c, m, h\> | G, c, m, h are respectively a graph, and positions of the Cat, Mouse, and Hole, such that Cat has a winning strategy if Cat moves first}.

I came across this algorithm:

1. Mark all nodes (a, a, x) where a is a node in G, and x is turn {cat, mouse} for whoever goes next.
2. If for a node u = (a, b, cat), there is a node v = (c, b, mouse) which is marked and (u, v) is an edge then mark u.
3. If for a node u = (a, b, mouse), all nodes v = (a, c, cat) are marked and (u, v) is an edge then mark u.
4. Repeat steps 2 and 3 until no new nodes are marked.
5. Accept if start node s = (c, m, cat) is marked.

But I'm having difficulty envisioning the first step. For example, in the picture below (where cat starts at 1, mouse starts at 5, and the hole is at 10), cat wins at vertex 4 in two ways:

1. c -\> 12, m -\> 4, c -\> 6, m -\> 2, c -\> 4, m -\> 4
2. c -\> 12, m -\> 4, c -\> 3, m -\> 2, c -\> 12, m -\> 4, c -\> 4

So then at step 1 of the algorithm, would node 4 in our new marked set contain (4, 4, cat) or (4, 4, mouse)?

# Answer
Alike kotu in the comments, I do not fully understand what you want to achieve with your algorithm, but I'm sure that when playing the game you must assume perfect play, and thus the mouse will win in your example by simply moving to the hole.

Determining the game's outcome is not so trivial, so here are my observations:

**Proposition 1**: If the cat reaches the hole before the mouse, the game is not won for the mouse.

**Proof**: By a simple case distinction. If the cat is on the hole and the cat has to move, do one of the following: If the mouse is adjacent to the cat, catch it. Otherwise, move somewhere else. If the cat is adjacent to the hole and the cat has to move, move onto the hole.

Note, that the mouse cannot 'sneak by' while the cat is away, that's an easy exercise. This gives that the game is only lost for the cat whenever the mouse is too quick and we can proceed in analysing only drawn or winning scenarios.

**Proposition 2**: If the graph contains a cycle of proper length at least 5 (i.e. no chords, etc.) and the mouse can reach the cycle before the cat, the game is not won for the cat.

**Proof idea**: If the mouse is on the cycle and the cat is as well, the mouse can always 'run away' from the cat. If the cat is not on the cycle, then the mouse can keep its distance by strategically moving along the cycle.

This gives us quite a strong criterion on when the game is drawn. So in the following, we can assume that there is no proper 5 cycle that the mouse can reach without getting caught. However, proper 4 cycles are relatively hard to handle.

**Proposition 3**: If the mouse cannot reach any proper 4 cycle, then the cat will win.

**Proof idea**: Such a reachability graph only contains areas of triangles and simple paths between them (shrinking these areas gives a tree). In an area of triangles the cat can always catch the mouse. Inbetween areas the cat can chase the mouse. By induction, such a game is won for the cat.

This leaves us with the issue of proper 4 cycles occurring in the reachability graph.

**Proposition 4**: If the graph contains a cylce of proper length at least 4, the mouse and the cat are opposing each other, the cat has to move and there is no way for the cat to triangulate (cf. chess endgames), it's a draw.

**Proposition 5**: If in the above situation the cat can triangulate(\*), the mouse needs to leave the cycle, or it will loose.

You can visualize these two propositions by drawing a square (4 vertices, 4 edges as cyle) and extending it with triangles that share 1 edge and 2 vertices with the square each. The drawn graphs are the square without attached triangles, the square with 4 attached triangles and the square with 2 attached triangles on opposite sides.

(\*) The cat cannot triangulate if by doing so it let's the mouse sneak by. It also isn't able to 'triangulate' if the mouse can do so as well.

This way, you can determine for each proper 4 cycle, if it's a drawn or lost cycle for the mouse. We can focus on the games in which between the cat and the mouse there are no cycles but proper 3 cycles and lost proper 4 cycles. However, in such a graph the same argument as above holds and it's lost for the mouse.
> 1 votes

---
Tags: complexity-theory, game-theory
---


title: Connected Vertex Cover

text:
# Question
Title: Connected Vertex Cover
I'm trying to prove the Connected Vertex Cover problem is NP-complete. That is given a graph $G=(V,E)$ and integer $k$, is there a subset $X$ of $V$ such that $|X|≤k$ and that for every edge $(u,v)\in E$ at least one of $u$ and $v$ are in $X$. Furthermore, the subgraph $G\[X\]$ induced by $X$ must be connected.

I know the structure of an NP-complete proof. But I have no idea what problem to reduce to connected vertex cover and how to go about it.

# Answer
> 1 votes
(First, a side note: it happens that Connected Vertex Cover isn't actually NP-hard for all classes of graphs. In particular, it's solvable in polynomial time in chordal graphs and graphs with maximum degree 3. However, it *is* NP-hard for planar graphs with maximum degree 4 in particular, and that's the easiest case to prove.)

For this, you'll want to reduce from Planar Vertex Cover. This is the special case of Vertex Cover where the input graph is planar, and it itself can be proved NP-hard by reduction from Planar 3Sat. (Planar 3Sat is, similarly, the special case of 3Sat where the input graph is planar. Proved NP-hard by reduction from normal 3Sat, and it itself is used to prove that various games are NP-hard, such as Super Mario Bros, Super Mario Bros 3, and Super Mario World.)

This reduction was first done by Garey and Johnson in 1977. I'm currently trying to find the full details of their proof, but these lecture notes provide a general overview.

# Answer
> 1 votes
Consider the following polynomial-time Karp reduction.

Given an input to VERTEX COVER: \[graph G, integer k\]

Construct a new graph G\* by adding a single new vertex v\* to G. Then connect v\* to all other vertices.

The input \[graph G\*, integer k+1\] is a positive instance of CONNECTED VERTEX COVER if and only if the input \[graph G, integer k\] is a positive instance of VERTEX COVER.

Backwards direction: Any vertex cover (size k) in G gives a connected vertex cover (size k+1) in G\* by also including v\*.

Forwards direction: v\* has an edge to every other vertex in G\*. So any vertex cover in G\* must either include every vertex in G or must include v\* (otherwise it wouldn't cover some of the edges from v\*). Suppose a connected vertex cover (size k+1) of G\* does include v\*, then removing v\* clearly gives a vertex cover (size k) (not necessarily connected) of G=G*-{v*}. Suppose a connected vertex cover (size k+1) of G\* includes all vertices of G. Note every edge has two endpoints so we can discard any one vertex and still have a vertex cover (size k) of G

VERTEX COVER ≤ CONNECTED VERTEX COVER

---
Tags: np-complete
---


# Question
Title: Is every problem with an output's size that grows polynomialy np?
I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$?

My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic Turing machine. (Wikipedia)

Moreover, consider a non-deterministic algorithm, that takes in input an integer $n$ and an integer $k$. This algorithm randomly outputs an $n^k$ bits combination. For example $(2,2)$ could output $0101$

Intuitively, this algorithm as a polynomial complexity.

A problem with an output's size that grows polynomialy could be solved by this algorithm.

Therefore, a problem with an output's size that grows polynomialy could be solved by a non-deterministic algorithm in polynomial time.

Therefore, every problem with an output's size that grows polynomialy is $\textsf{NP}$.

I do not know, if my thinking is correct.

# Answer
> 1 votes
No. All problems in $\mathsf{NP}$ are decision problems and, as such, the size of their output is trivially polynomially bounded (the output is just one bit). Moreover, there are decision problems that are not in $\mathsf{NP}$. Indeed, by time hierarchy theorem $\mathsf{NTIME}(n^k) \subsetneq \mathsf{NTIME}(2^n)$ for every constant $k$.

# Answer
> 0 votes
To add a new perspective to Steven's answer, I think you missed a crucial part of **NP**: Yes, the output's size must be polynomial in the input's size, **but** furthermore, the "guessed" string must allow verification in polynomial time.

For this, it is often helpful to not consider the decision variants, by the search variants for problems, i.e., if possible, don't only output **TRUE**, but also a solution (e.g., for 3SAT, a satisfying interpretation).

The textbook example would be deciding if a Turing Machine M halts in time $O(2^{\langle M \rangle})$. The output for the decision problem is one bit, but the verification string has exponential length and is thus not verifiable in time polynomial in the input's size.

---
Tags: algorithms, complexity-theory, np
---


# Question
Title: What is appearance checking in the context of formal grammars?
As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined. Perfect would be an example using a context free grammar.

# Answer
Appearance checking is a concept in the theory of regulated grammars.

In an ordinary (context-free) grammar we may appay a production to a string if its right-hand side occurs in that string. So for $\pi: A\to \alpha$ we write $x \Rightarrow\_\pi y$ if $x= w\_1 A w\_2$ and $y = w\_1\alpha w\_2$.

In a *regulated grammar* we may specify the order in which the productions should occur in the derivation. As an example, the following context free grammar

$\pi\_0: S\to AC$, $\pi\_1: A\to aAb$, $\pi\_2: C\to cC$, $\pi\_3: A\to ab$, $\pi\_4: C\to c$

generates the language $\\{ a^nb^nc^m \mid m,n\ge 1\\}$. As a regulated grammar we can choose to restrict the sequences of chosen productions to be the (regular) language $\pi\_0(\pi\_1\pi\_2)^\*\pi\_3\pi\_4$. Clearly with this restriction the grammar generates the non context-free language $\\{ a^nb^nc^n \mid n\ge 1\\}$.

Appearance checking is the notion that we are allowed to skip a production if it cannot be applied. Formally for $\pi: A\to \alpha$ we write $x \Rightarrow^{ac}\_\pi y$ if either *(i)* $x$ contains $A$ and $x \Rightarrow\_\pi y$ or *(ii)* $x$ does *not* contain $A$ and $x=y$.

How it this useful? It can be used to check that actually all symbols in the string are rewritten before the derivation continues. Consider the productions $\pi\_1: A\to BB$, $\pi\_2: A\to X$, $\pi\_5: B\to a$ and the "regulator" $\pi\_1^\*\pi\_2\pi\_5^\*$, and starting with the string $A^n$. In this case the variable $X$ cannot be rewritten. So applying the production $\pi\_2$ has to be avoided. This is allowed in *appearance checking mode* when $A$ does not occur in the string. That means we have to rewrite all $A$'s into $B$'s, then we can skip $\pi\_2$, and continue rewriting the $B$'s. This trick can be extended into a grammar that generates $\\{a^{2^n} \mid n\ge 0\\}$:

$\pi\_1: A\to BB$, $\pi\_2: A\to X, \pi\_3: B\to A$, $\pi\_4: B\to X, \pi\_5: A\to a$ and "regulator" $(\pi\_1^\*\pi\_2\pi\_3^\*\pi\_4)^\* \pi\_5^\*$

Informally we repeat the following. First $\pi^\*\_1$ doubles the number of $A$ (temporarily renaming them into $B$'s). We have to rewrite all $A$'s as otherwise we have to apply $\pi\_2$ and this will introduce $X$ a letter that cannot be rewritten, so in that case the derivation will not be successful. Similarly $\pi\_3^\*\pi\_4$ will rename all $B$'s into $A$'s effectively doubling the $A$'s. In the final round $\pi\_5^\*$ renames all $A$'s into the terminal symbols $a$.
> 3 votes

---
Tags: turing-machines, automata, context-free, formal-grammars
---


# Question
Title: WAL rule requires only the undo information in the log have been output to stable storage, and permits the redo information to be written later
I was going through the "**write-ahead logging (WAL)** rule" from the *Database System Concepts* text by *Korth et. al*, where I came across the following excerpt:

> Strictly speaking, ***the WAL rule requires only that the undo information in the log have been output to stable storage, and permits the redo information to be written later.*** The difference is relevant in systems where undo information and redo information are stored in separate log records.

What I have learned after reading the text is that: both the *undo* and the *redo* information is important in restoring the database to a consistent state after some failure. What I feel is that the *undo* and the *redo* operations are equally important and I feel both should be *OUTPUT* to the stable store before actual modifications of the data of the database are made to disk.

What the authors say about *undo* in the context of WAL is fine with me. I feel uneasy with what they say about the *redo*. ***\["permits the redo information to be written later"\]*** In a situation suppose, the database transaction modifications after half done and the *redo* info. are still not written to the stable storage, then once the system becomes functional again, it shall have no idea about the "half done" modifications done by the transaction.

What do the authors actually mean to say?

# Answer
The use of the different Logs depends on the Recovery Algorithms used. In general those algorithms are classified in four different classes:

* Undo-Redo, requires both *undo* and *redo*
* Undo-NoRedo, requires *undo*, but not *redo*
* NoUndo-Redo, requires *redo*, but not *undo*
* NoUndo-NoRedo, requires neither *undo* nor *redo*

The Write Ahead Log (WAL) is strictly necessary when applying the Undo Rule:

If a database page is updated before the transaction has committed, its before-image must have been previously written to the log file in the stable memory.

This means that the if we use, for instance, a recovery algorithm based on the Undo-NoRedo approach, we *must* have the before-image written on the stable memory, but we can defer the writing of the after-image.
> 0 votes

---
Tags: database-theory, databases
---


# Question
Title: Is there any study or theory behind combining binary search and interpolation search?
I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window.

Whilst doing this, I decided to try interpolation search (I didn't know that was what it was called, I kind of stumbled across the idea by myself). Then for some reason I continued to the idea of alternating interpolation steps with binary split steps: On step 0 I would interpolate to decide test point, then step 1 I would take the exact midpoint etc.

I then benchmarked the system using pure interpolation search, pure binary search and my combination attempt. The alternating approach was a clear winner, both in time and number of tests required before finding a set of randomly chosen times.

Inspired by the linked question, I just made a quick search for "alternating interpolation search and binary search" and found nothing. I also tried "hedged interpolation search" as suggested on my comment on one of the answers.

Have I stumbled across a known thing? Is there any theoretical justification for it being faster for certain types of data? The log files were typically large for the time (e.g. 1-2 GB of text with maybe 10 million rows to search), and the spread of dates/times in them was complex with heavy bursts of activity, general peak times and quiet times. My benchmark tests sampled from an even distribution of target times to find.

# Answer
> Have I stumbled across a known thing?

There are various methods, based on a mix of interpolation-search and binary search, with a $O(log\ log\ n)$ average case access time (uniform distribution) and $O(log\ n)$ worst case time (values unevenly distributed):

* **Introspective search** is your method (iterating between an interpolation search and a binary search). I haven't further details.
* **Interpolation-binary search** (IBS) by N. Santoro, J. B. Sidney (1985).

The general idea is that interpolation search is useful only when the array searched is larger than a given threshold. When the considered search segment is smaller than a user-defined threshold, binary search is applied unconditionally. Vice-versa, over that threshold, an interpolation search step is applied, followed eventually by a binary search step.

This has many common points with your approach.
* **Adaptive search** (AS) by Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

Using the authors' words:

> \[Interpolation-binary search\] devised a similar solution that combines (but does not blend) together interpolation and binary search. Although the asymptotic complexity is the same, there are some marked differences.
>
> \[CUT\]
>
> Hence, it is possible to show that for any input AS will not take more elementary operations than IBS.

The algorithm may spend up to double number of operations than "simple" interpolation search in carefully finding out the best halving of the search segment, which in turn will mean that less iterations shall be needed to complete (but you have an even greater overhead).
> 5 votes

# Answer
Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates.

Though theoretically faster, interpolation search has two disadvantages compared to binary search:

* It has terrible (linear) worst case performance
* The overhead of computing the midpoint is rather large; a binary search iteration is hundreds of times faster than an interpolation search one

I would expect that an approach where you do interpolation search while the range is large and switch to binary search when the range becomes small is the most efficient. It would be nice if you could try this experiment.

As your dataset becomes small, the difference between $\log n$ and $\log \log n$ becomes insignificant; $\log n$ is already really small, and $\log \log n$ couldn't possibly be much smaller. At this point, the overhead of doing interpolation search is not worth it compared to the iterations you might save.

I think that your results can be explained by two phenomena:

* Combining with binary search allows you to avoid the worst-case behavior
* The positive effect of switching to binary search on a small dataset
> 6 votes

# Answer
Last study published here and compared with Adaptive search experimentally. Interpolated binary search: An efficient hybrid search algorithm on ordered datasets
> 2 votes

---
Tags: algorithms, search-algorithms, binary-search
---


# Question
Title: In database buffering why is it important : no writes to a block (which is to be moved from the disk buffer section of main memory) be in progress?
I was going through the concept of database buffering from the *Database System Concepts* text by *Korth et. al* where I came across the excerpt below.

> The rules for the output of log records limit the freedom of the system to output blocks of data. If the input of block $B\_2$ causes block $B\_1$ to be chosen for output, all log records pertaining to data in $B\_1$ must be output to stable storage before $B\_1$ is output. Thus, the sequence of actions by the system would be:
>
> 1. Output log records to stable storage until all log records pertaining to block B\ have been output.
> 2. Output block $B\_1$ to disk.
> 3. Input block $B\_2$ from disk to main memory.
>
> ***It is important that no writes to the block $B\_1$ be in progress while the system carries out this sequence of actions.*** We can ensure that there are no writes in progress by using a special means of locking.

What I do not get is, why it is the case that: no writes to a block (which is to be moved from the *disk buffer* section of the main memory) be in progress while the system carries out this sequence of actions?

Since there is a need to remove block $B\_1$ from memory, it might be the case that the CPU is with some other transaction $T\_j$ (with is working concurrently with the transaction $T\_i$ using block $B\_1$). Assuming a single processor system, the transaction $T\_i$ must have been pre-empted. So why do we need to check whether some writing is in progress in $B\_1$ with respect to $T\_i$. Just as it happens in OS paging concept, we could remove $B\_1$ and invalidate all the table entries for each transactions using $B\_1$ and bring $B\_2$ in memory. \[Just like replacing a page in memory, and setting the valid/invalid bit to invalid to the page table of the process\].

# Answer
> 2 votes
First off, let's remember the ACID of transactions:

* *Atomicity* means that either the transaction happens or it does not happen. The transaction never partly happens.
* *Consistency* means that a transaction transforms a database from a valid state to a valid state.
* *Isolation* means that if multiple transactions run concurrently, the resulting state of the database is as if the transactions ran in some sequential order.
* *Durability* means that if a transaction has committed, it stays committed, even if the machine crashes or there is a power outage.

Just looking at the case of a single transaction for a moment, and think about durability. How do we ensure that once a transaction has committed (that is, the client has been *told* that it has committed), it stays committed, even when multiple page updates are involved?

The approach is this:

* We write all changes to the log and ensure that the log has been flushed to disk. When this is done, the transaction can be considered committed.
* We queue dirty the pages for writing. This can happen in any order, which is important for performance on rotating platter disks.
* Once the dirty pages have been written, we no longer need the log.

If a crash occurs, it doesn't matter that not all dirty pages were written, because all of the information is in the log. It can simply be replayed when the database starts up again.

Allowing writes a dirty page before it is written would interfere with the already-committed transaction, because of the way that replay works. The log records just enough information in the log to be able to tell if the modified page has been written or not, and if not, to reconstruct the change given the old page.

Committing a different version of the page to disk, which contains the change and even more changes on top if it, would mean that the replay mechanism would now have to contend with three or more possible versions of the page, and sort them all out.

---
Tags: database-theory, databases
---


# Question
Title: How can I approach a task like this "Dissert about the ordering algorithms in the different order of asymptotic notation"
I am taking an intermmediate course related to programming and analysis of system. I have a teacher that give us two tasks during the semester that are somewhat beyound the purpose of the course that is more toward the basics. The tasks that I am asked is "Dissert about the analysis of complexity of algorithm. In this dissertation,classify the four ordering algorithms (bubble sort,selection sort, merge sort e quick sort) in the different orders in the different order of asymptotic notation".

We have to go and do all research ourselves since this theme was not taught at school. To start off can you help how to tackle this problem. I read about asymptotic notation and it spinned my head.

# Answer
> 0 votes
Asymptotic notation utilizes the idea that we don't really know how much *exact* time an algorithm will run. For instance, we don't know what CPU the user is using, what other programs are running on his computer, etc.

The idea of asymptotic notation is to "capture" how the running time of an algorithm increases with respect to the input size. For example, linear running time $O(n)$ would mean that the running time of the algorithm on an array with 2 million values would be close to twice the running time of the algorithm on an array with 1 million values.

We can define the "running time" of an algorithm to be the number of "steps" it does. You can think of a "step" to be a CPU cycle. In formal computer science this is defined in a different way though.

Let $f$ be some function, that tells us how much "running time" the algorithm we use will require for a problem of size $n$.

Then, we can say that the algorithm we use is linear, if there is a constant $c$ such $f(n)\le c\cdot n$. This is denoted by $f=O(n)$.

Another example, would be when $f(n)\le c\cdot n^2$, and we say that $f=O(n^2)$. This means that the running time of something twice as large will be 4 times higher. and the running time of something 10 times larger will take 100 times more time.

This can be generalized to say that if $g$ is some function and $f(n)\le c\cdot g(n)$ then $f=O(g)$.

I hope I managed to help!

---
Tags: asymptotics, sorting
---


# Question
Title: Could an application capture and log a user's actions on another 3rd party software. If yes, how?
Could an application be built such that it could track a user's actions on a particular software and log them? For example, could an application track a user's actions on MS Word, noting down when the user clicked a particular button?

The question is asked assuming, our application has no access to the code of the 3rd party software.

# Answer
Yes. Read about keyloggers, spyware, and screen capture software. See also related topics on Security.SE, e.g., https://security.stackexchange.com/search?q=keylogger, https://security.stackexchange.com/questions/tagged/keyloggers, https://security.stackexchange.com/questions/tagged/spyware, https://security.stackexchange.com/q/201449/971, https://security.stackexchange.com/q/102434/971, https://security.stackexchange.com/q/238842/971
> 0 votes

---
Tags: software-engineering, security, applications
---


# Question
Title: Boolean algebraic expression vs Propositional logic expression
There is a lot of similarity between Propositional logic and Boolean algebraic expressions.

**Similar aspects :**

1) Both has variables of two states.

2) Operations of Boolean algebra and propositional logic are similar.

3) Simplification of formula expressed in logic can be minimized using Boolean algebra and vice versa.

My doubt is **are they both same**? If same, why studying differently? I mean why can't Propositional logic can be directly applied to digital logic instead of introducing Boolean algebra again(academically)?

# Answer
They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each.

So let's step back, define them separately, and then look at some interesting examples.

Propositional logic is a branch of mathematics that studies propositions, their truth or falsity, and how they combine.

What you probably think of as "propositional logic" is actually just one kind of propositional logic, namely, classical logic. However, this is not the only kind of classical logic and not the only one that is interesting in computer science.

Some theories are built on top of classical logic. Presburger arithmetic, for example, is the theory of natural numbers with addition. Tarski arithmetic is the theory of real closed fields. First-order logic is the theory of quantified variables over non-logical objects.

You can think of these logic systems as types of propositional logic, with more axioms to deal with the extra stuff. Many constraint-type problems are expressible in this framework; you can look up satisfiability modulo theories for more information on how this is used.

But there are also propositional logics that are not "classical". One example of a non-classical logic is intuitionistic logic. This is a logic that models constructive proofs, which is interesting because constructive proofs are the same thing as well-behaved computer programs. ("Well-behaved" in this sense means there is no unbounded recursion.) They are also the basis for modern type systems, such as that of Haskell.

Constructive proofs (e.g. pick any proof from Euclid's *Elements*) are implementable as computer programs. Given some geometric objects as input, you could implement the proof (at least in principle) as a computer program that performs the construction.

You can't do that with non-constructive proofs. Let's look at an example to see what I mean. I'll prove that there are two irrational numbers, $a$ and $b$, such that $a^b$ is rational.

Consider $z = \sqrt{2}^\sqrt{2}$. This number is either rational or irrational.

Case 1: If $z$ is rational, then set $a = b = \sqrt{2}$, and the theorem is proven.

Case 2: If $z$ is irrational, set $a = z$ and $b = \sqrt{2}$. Then $a^b = 2$ and the theorem is proven.

QED

The reason why this proof isn't constructive is that it relies on the law of the excluded middle; $z$ must be either rational or irrational, but we don't (and, in a sense, can't) actually test which of them is true.

Intuitionistic logic systems tend to give you proof systems that are decidable. This is an extremely important practical concern. If you consider, for example, the Java bytecode verifier, or the type system for a programming language (both of which prove that some program is type-correct), they must terminate with an answer, so they must be based on a decidable proof system. By allowing propositions that are neither provable nor refutable, you avoid Gödel-like incompleteness.

That's just one example, of course. Other non-classical propositional logics include modal logic (which can be used to model situations where you have multiple agents who know different things; think about network protocols), and temporal logics (where the truth or falsity of a proposition may change over time).

The thing that connects all of them is the notion of a "proposition". Propositional logic can be thought of as the study of a *family* of logic systems, all of which deal with the notion of a mathematical statement that has a "truth"-type judgment.

Boolean algebra, on the other hand, is a purely algebraic system, characterised by a set of axioms. Saying "Boolean algebra" is like saying "group" or "field" in abstract algebra. Classical propositional logic satisfies the axioms, but so do other mathematical structures.

The subsets of a set $S$, for example, form a Boolean algebra; with the "not" operator corresponding to "set complement", "and" corresponding to "set intersection", and "or" corresponding to "set union". You can think of "true" as being $S$ and "false" as the empty set, but these are not the only "truth values" which the system models.

Lattices form Boolean algebras, and some lattices are important in computer science (e.g. Scott domains). Moreover, some important non-classical logic-like systems naturally form Boolean algebras, such as fuzzy logic.

So what I hope you can see is that while the two notions are related (some Boolean algebras model some propositional logics), they are not exactly the same thing. How they differ is part of what makes them interesting.
> 11 votes

# Answer
I would say an important difference is at least: one cannot add an axiom to Boolean algebra, while one can add one or multiple axioms in propositional logic, although there is not that much one could add since all consistent and interesting axiom set is already known (modulo their interpretations).

— Edit —

Yesterday I thought about two other important ones

Unless I’m wrong, a proposition is not necessarily reducible to True or False, while a Boolean expression, is. This is so, although both evaluate to the same domain, the domain they reduce to is not the same: Boolean for Boolean algebra, proposition (including truth judgment) for proposition calculus. The difference is that a Boolean is just a value in a set of two, while a proposition typically has a meaning attached to it, and this meaning would just vanish if it was reduced to True or False (it can still prove to be tautological). Evaluation and reduction are not the same. Everyone understands evaluation, but the reduction is less common, so I would say it is like a rewriting. When one writes P, it means P, not True or False (\*), although P may be True or False. While when one writes True or False or a Boolean expression, it means True or False, because that is the only thing of interest, in Boolean algebra.

(\*) One would not be happy if someone was to replace his/her P with a Boolean unless he/she is doing Boolean calculus in proposition calculus (which is possible too). But one would be very happy to witness that P may be replaced by Q, as an example, showing P and Q means the same somehow. Anyway, deriving True or False from a proposition, would be useless: what one wants, is a new valid proposition.

Also, I know some logic may have non‑logical constant or variable, but I’m unsure this is the case with proposition calculus. I guess yes, but I’m not sure. If it is indeed this way, then this is another difference: there are no non‑Boolean variables or constants in Boolean algebra.
> 2 votes

# Answer
You are cheating a bit by saying "Boolean algebraic expression" and "propositional logic expression" instead of "Boolean algebra" and "propositional logic". A Boolean algebra is a model of propositional logic, just like a Heyting algebra is a model of intuitionistic propositional logic. The main reason why some models are not Boolean algebras is that Boolean algebra refers to the structures defined within ZFC set theory (or any other given set theory), but it is possible to construct models which are only "meta" Boolean algebras, i.e. which have all the operations and first order properties of a Boolean algebra, but can't be proved to be isomorphic to a ZFC-defined Boolean algebra. This is actually more important for intuitionistic propositional logic, because people there have a more natural tendency to work outside of ZFC.

---

*I intent to rewrite this answer later, give some references, explain it on a more practical level, explain the relation to the fact that Boolean and Heyting algebras are also partially ordered structures, and maybe also try to engage with the "Boolean algebraic expression" view intended and suggested by the question.*
> 1 votes

# Answer
I came to this question because I was struggling with the same question as the OP, but after reading the answers I still didn't feel like I understood the difference. After struggling with it for a while, I think I've got an answer that satisfies me, so I thought I'd share it.

I think the difference (or at least *a* difference) is that in boolean algebra the variables are free to take on any value. An atomic proposition's truth value depends on its meaning, and a composite proposition's truth value depends on the values of the constituent atomic propositions, which may be constrained depending on their meaning. For example, the proposition P:"x=0" depends on the value of x and may be true or false. The proposition Q:"1=2" can only be false, and the proposition R:"1=1" can only be true. The composite proposition (P∧Q)∨R is true when the atomic propositions P, Q and R have the meanings defined above. The value of the analogous boolean algebra expression pq+r depends on the values of p, q and r, which are free to take on 0 or 1, and the resulting values of the overall expression can be evaluated by a truth table. The truth of the proposition as defined above can also be evaluated in a truth table, but some of the rows are missing because the atomic propositions can't take on those particular values due to their meaning.

```
p q r pq+r     P Q R (P∧Q)∨R
0 0 0   0
0 0 1   1      0 0 1       1
0 1 0   0
0 1 1   1
1 0 0   0
1 0 1   1      1 0 1       1
1 1 0   1
1 1 1   1

```

In the above, I've called P a proposition, but actually it's called a formula. It's not a proposition until the value of x is fixed so that P has a definite truth value. But for the purposes of trying to evaluate the potential truth value of a propositional formula, it helps me to think of a formula like P as a "variable proposition" whose value is free to vary in the truth table.
> 0 votes

---
Tags: boolean-algebra, propositional-logic
---


# Question
Title: Obtaining an expectation in uniform hashing
long shot question but I am super stuck.

Donald Knuth has proven (p. 8 here, equation 12) that the probability that the maximum value in uniform hashing is smaller than $n/2$ is equal to 0.288. I wonder if with this information I can recover what is the expectation of the maximum value? Simulation strongly suggest 0.63 n but I would like to understand what I am doing.

# Answer
The probability that the maximum rank $r\_{\max}$ is at most $m$ is $$ (1 - q\_{1m}) \cdots (1 - q\_{nm}), $$ where $$ q\_{km} = \binom{k-1}{m} \bigg/ \binom{n}{m}. $$ Therefore $$ \mathbb{E}\[r\_{\max}\] = \sum\_{m=1}^n \Pr\[r\_{\max} \geq m\] = \sum\_{m=1}^n (1 - \Pr\[r\_{\max} \leq m-1\]) = \\ 1 + \sum\_{m=1}^{n-1} \left\[1 - \prod\_{k=1}^n \left(1 - \binom{k-1}{m}\bigg/\binom{n}{m}\right)\right\]. $$ When $m = (1-\alpha) n$, the $m$'th summand is roughly equal to $$ 1 - \prod\_{i=1}^\infty (1-\alpha^i) = 1 - \phi(\alpha), $$ where $\phi(x)$ is the Euler function, and so $$ \frac{\mathbb{E}\[r\_{\max}\]}{n} \approx 1 - \int\_0^1 \phi(x) \\, dx = 1 - \frac{8\sqrt{3/23}\pi\sinh(\sqrt{23}\pi/6)}{2\cosh(\sqrt{23}\pi/3)-1} \approx 0.631587464068566. $$
> 2 votes

---
Tags: probabilistic-algorithms, hashing
---


# Question
Title: Parallel algorithm for finding the maximum in $O(\log \log n)$ time
With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is:

> 1. If $n = O(1)$, solve the problem trivially;
> 2. Split the array into $\sqrt n$ parts of equal sizes. Give each part $\sqrt n$ processors and recursively use this algorithm to find maxima on these parts;
> 3. Use all $n$ processors to find the overall maximum among the $\sqrt n$ local maxima in $O(1)$.

Because this algorithm uses $n$ processors, it is not work-optimal. But it seems that there does exist a work-optimal algorithm that has $O(\log \log n)$ time complexity while only using $\frac{n}{\log \log n}$ CRCW processors. However I can't have any clue about how this algorithm works. Is there any idea?

# Answer
Each processor gets $\log\log n$ elements, and finds the maximum in time $O(\log\log n)$. Now run the existing algorithm.
> 2 votes

---
Tags: algorithms, search-algorithms, parallel-computing
---


# Question
Title: Proof that R (decidable languages) is not closed under homomorphism
After searching the internet for a bit, I found that the same proof came up over and over again. The thing is, it seems like the proof is incomplete. Here's the proof:

> However, the recursive languages are not closed under homomorphism. To see why, consider the particular language L consisting of strings of the form (M, w, ci ), where M is a coded Turing machine with binary input alphabet, w is a binary string, and c is a symbol not appearing elsewhere. The string is in L if and only if M accepts w after making at most i moves.

> We have defined this particular language to break the closure of recursive language. First lest check that indeed L is recursive. Well, yes it is, because to see whether a string is in the language, we have to simulate M on w for at most i moves. So you can stop the machine after i+1 moves and know for sure you should reject. However, if we apply to L the homomorphism that maps the symbols other than c to themselves, and maps c to ε, we find that h(L) is the universal language, which we called Lu. We know that Lu is not recursive. So in three words, L is recursive, h(L) = Lu is RE but not recursive. So recursive languages are not closes under homomorphism.

(Source: https://www.cs.cornell.edu/courses/cs381/2003fa/asgn12sol/cs381-02-12.pdf)

The last part of the proof states that after mapping L to the homomorphism, h(L) is L\_halt, which is not decidable.

My question is, how is h(L) the same as L\_halt? It seems that the new language is a language of strings of type (M, w, ci), and a string is in h(L) if and only if M accepts w after making at most 0 moves (because we deleted every c).

(Also, I am pretty sure that h(L) is empty because you can't accept a string after 0 steps, because you can't start the TM with q\_accept).

# Answer
You are confusing the langauges here $h(\langle M, w, \varepsilon\rangle) \notin L$ certainly, but this does not mean anything releated to $L\_{halt}$.

Assume $M$ halts on $w$ after $i$ moves. Then $\langle M, w, c^i \rangle \in L$ and $\langle M, w\rangle \in L\_{halt}$. Moreover, $h(\langle M, w, c^i \rangle) = \langle M, w \rangle$.

Otherwise assume $M$ never halts on $w$. Then there does not exist any $i$ s.t. $\langle M, w, c^i \rangle \in L$ and hence, $\langle M, w \rangle \neq h(x)$ for any $x \in L$ (by definition of $h$, these $x$ could only have the form $\langle M, w, c^i\rangle$ for some $i$ to map to $\langle M, w \rangle$).
> 1 votes

---
Tags: turing-machines, halting-problem
---


# Question
Title: Reasoning about resources: "resource logics"?
Are there extensions of predicate logic which focus on resource models, possibly even in actor models?

And if so, would it be possible to reason on a meta-level on how many resources should be expended to find further proofs in the same or other systems?

# Answer
Do you mean a resource-aware logic? If so, yes, there's linear logic \[Girard, 1987\] (as was already noted in the comments). It has had a big influence on the study of concurrency and implicit computational complexity. You might be interested in the latter, where reasoning is focused on the efficiency of programs.

What do you mean exactly by "actor models"? If you mean concurrency, please have a look at: What is the Curry-Howard analogue for linear logics? If you mean identifying who/what uses/implements resources at the level of propositions, we explored an extension of linear logic for that \[Carbone et al., 2016\], but mainly for the notion of communication protocol (who performs which communications). Useful inspiration might also come from hybrid logics that support notions of "worlds", like this one: https://www.cs.cmu.edu/~rwh/theses/reed.pdf
> 1 votes

# Answer
Just learned about Bunched Logic which seems to fit the bill too.
> 1 votes

---
Tags: logic, temporal-logic, resource-allocation
---


# Question
Title: Is this string substitution problem decidable?
We have the following task:

> Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be performed on x if the left is a substring of x. For example $01\rightarrow 10$ means replace one 01 with 10, and can only be applied if 01 is in the string. The algorithm should decide if for the given set there exists a string such that applying a non - zero number of the substitutions yields the initial string.

I am wondering if this is a decidable task. It seems like it should be possible to establish an upper bound on the length of the string and number of substitutions, but I haven't been able to. And from the other end I tried to build a test based on invariants, since invariants can be used to show a lot of sets can't loop. For example

$$ \\{011\rightarrow 101, 101\rightarrow 110\\} $$

Can never produce a loop. We can show this since each rule decreases the average position of 1s in the string when used. Thus it can never produce a string with the same average position as the start thus it can never produce the start.

But there are some cases that I can't think of a clever invariant. For example

$$ \\{1001\rightarrow 0110\\} $$

Which clearly can't form a loop, but I can't think of a property which it always increases.

Is this problem decidable?

# Answer
Your problem is essentially the same as the question of whether a given string can be generated from a given initial string using a given unrestricted grammar (simple reverse all productions). The latter question is known to be undecidable, since you can simulate the running of a Turing machine using an unrestricted grammar.
> 2 votes

---
Tags: undecidability, decision-problem, substrings
---


# Question
Title: How many pixels support each neuron in multi-layer CNN?
I'm studying for a computer vision module and I'm on the deep learning topic, in one past paper we have the following question:

Given that a convolutional neural network has five convolution layers (all the convolution layers are composed of 3×3 convolution filters with stride 1 and no pooling layers), calculate how many pixel(s) in the input image are supporting a neuron in the fifth layer?

without the input size of the image, how is it possible to work this out?

# Answer
> 1 votes
If there is only one convolution layer, then every neuron is supported by $3 \times 3 = 9$ pixels in the input image. This doesn't depend on the size of the image. You can generalize this to more layers.

---
Tags: machine-learning, neural-networks, image-processing
---


# Question
Title: Number of subsequence with k distinct characters
"*A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order.*"

Suppose we have string s="***aabca***" and k=***3***. ( I will refer the three ***a***s as a1,a2 and a3 just to distinguish them). So number of subsequence with 3 distinct characters are -

**7** =\> *(a1)bc*, *(a2)bc*, *bc(a3)*, *(a1)(a2)bc*, *(a1)bc(a3)*, *(a2)bc(a3)*, *(a1)(a2)bc(a3)*

I know how to calculate the answer for number of substring with k distinct character. How to do it for subsequence?

# Answer
Suppose there are $c$ types of balls, and there are $n\_i$ balls of type $i$. Let $S$ be a set of types of balls. In how many ways can we choose balls so that only balls of type $S$ appear, and at least one ball of type $i$ appears for each $i \in S$? The answer is clearly $$ \prod\_{i \in S} (2^{n\_i} - 1). $$ Taking $S = \\{1,\ldots,c\\}$, we get a solution to your problem in the case where $k$ is the number of different characters in the original string (in your example, $n\_1 = 3$ and $n\_2=n\_3=1$).

You are interested in the value of the above when summed over all sets $S$ of size $k$. This is the coefficient of $x^k$ in the generating function $$ \prod\_{i=1}^c (1 + (2^{n\_i}-1)x). $$ This coefficient can be computed using dynamic programming. Details left to you.
> 1 votes

---
Tags: algorithms, dynamic-programming, strings, substrings, subsequences
---


# Question
Title: Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph
I am trying to find an efficient algorithm for the following problem:

Input:

* weighted directed graph **G=(V, E)** in which all edges are weigthed either 1 or 2
* **s,t** ∈ V
* **n** ∈ N

Output

* shortest path from **s** to **t** that contains exactly **n** edges of weight 2

I have been experimenting with different modifications of Bellman-Ford, Dijkstra and even max-flow with no luck.

Is there an efficient algorithm for solving this?

# Answer
When all edges have weight 2 and $n = |V|$ the problem is equivalent to longest path which is NP-complete. So unless P = NP, there is no efficient algorithm for solving the problem.
> 2 votes

---
Tags: shortest-path, network-flow, dijkstras-algorithm
---


# Question
Title: which ip and mac address is added to the header of data packets?
I know that in the Internet layer, the source ip and mac address and destination ip and mac address are added to the header. Is this the ip and mac address of the next router we take to get to the end router or just the ip and mac address of the computer we are sending the data too.

# Answer
A packet only contains the final destination IP address otherwise it would be lost. On a Windows computer, type `route print` in CMD to see the routing table of your computer (which can act just like a router if you enable routing in its settings). Mine looks like such:

```
===========================================================================

IPv4 Route Table
===========================================================================
Active Routes:
Network Destination        Netmask          Gateway       Interface  Metric
          0.0.0.0          0.0.0.0      192.168.0.1    192.168.0.153     55
        127.0.0.0        255.0.0.0         On-link         127.0.0.1    331
        127.0.0.1  255.255.255.255         On-link         127.0.0.1    331
  127.255.255.255  255.255.255.255         On-link         127.0.0.1    331
      192.168.0.0    255.255.255.0         On-link     192.168.0.153    311
    192.168.0.153  255.255.255.255         On-link     192.168.0.153    311
    192.168.0.255  255.255.255.255         On-link     192.168.0.153    311
     192.168.56.0    255.255.255.0         On-link      192.168.56.1    281
     192.168.56.1  255.255.255.255         On-link      192.168.56.1    281
   192.168.56.255  255.255.255.255         On-link      192.168.56.1    281
        224.0.0.0        240.0.0.0         On-link         127.0.0.1    331
        224.0.0.0        240.0.0.0         On-link      192.168.56.1    281
        224.0.0.0        240.0.0.0         On-link     192.168.0.153    311
  255.255.255.255  255.255.255.255         On-link         127.0.0.1    331
  255.255.255.255  255.255.255.255         On-link      192.168.56.1    281
  255.255.255.255  255.255.255.255         On-link     192.168.0.153    311
===========================================================================

```

Terminology is different for every device but normally you have the path to take for every interface. The interface is the actual IP address given to your network card by the DHCP server of your router (or the static IP you gave your machine). What the table above says is that if the packet exiting the computer is going to any IP (0.0.0.0), send it to the gateway which is `192.168.0.1` or the router. It says so with that line:

```
0.0.0.0          0.0.0.0      192.168.0.1    192.168.0.153     55

```

Also, if the destination is 192.168.0.0 to 192.168.0.255, the destination is "On-Link" meaning it has a direct physical link because it is on the local network. You can thus reach it using its MAC address. It says so with this line:

```
192.168.0.0    255.255.255.0         On-link     192.168.0.153    311

```

My configuration is very simple (computers behind one router facing internet). You can have much more complex configurations with LAN networks using switches and several local routers in the same building. Even then, a simplified overview is quite simple. Every router has a routing table, an ARP table and a NAT table. The routing table is like above. It tells the computer if the connection to an IP address is On-Link. If it isn't, then send it to the gateway (more often the router facing internet in simple configurations). To do that, the computer uses its ARP table. Type `arp -a` to see the ARP table of your computer. Mike looks like below:

```
Interface: 192.168.0.153 --- 0x11
  Internet Address      Physical Address      Type
  192.168.0.1           58-d5-6e-91-f0-08     dynamic
  224.0.0.22            01-00-5e-00-00-16     static
  224.0.0.251           01-00-5e-00-00-fb     static
  224.0.0.252           01-00-5e-00-00-fc     static
  255.255.255.255       ff-ff-ff-ff-ff-ff     static

```

The computer uses the ARP protocol to get the MAC address of the computers (or routers) which are On-Link. The computer then sends packets to these machines directly (either in the Ethernet wire or using electromagnetic waves in WIFI configurations).

A router also has a NAT table which makes the link between the external IP of the network and the internal IP (local IP). The NAT specification saves some IP addresses for local use (see RFC 1918). These IP addresses range are to be used locally. When a packet reaches a router facing internet, the NAT table is used to change the local IP address of the machine into the public IP address of your router provided by your ISP. Your router will most often get this IP using the DHCP server of your ISP. The NAT table also saves local ports and changes the local source port to a random port number.

To answer your question, the IP address in the packet is only the final destination IP address. The router takes this IP address and compares it to the routing table entries. If the IP is On-Link, it sends the packet directly using Ethernet or WIFI. Otherwise, it sends the packet to the default gateway. The default gateway for a router facing internet is a special interface often called the WAN interface. The router, uses a NAT table to change the local IP addresses to the public IP of the WAN interface. The WAN interface is connected to your modem which is connected to a wire (either fiber or coaxial) which quits your home to go directly to the ISP which dispatches requests to other bigger ISPs and eventually to the website you try to join. The website you try to join needs to have a fixed port forwarding entry to listen to requests. The port forwarding entries create entries in the NAT table which are saying: if the incoming packet has a certain destination port, send it to the machine with this certain internal IP.
> 2 votes

---
Tags: tcp, ip
---


# Question
Title: What is the grammar for language $L=\{a^nb^m : n \neq m-1\}$?
What is the grammar for language $L = \\{ a^nb^m : n\neq m-1\\}$?

I only know I have to write grammar for both $ n\<m-1 $ and $ n\>m-1 $, so this is what I wrote:

* For $n\<m-1$: \begin{align} &S\to Abb \\ &A\to aAb \mid \lambda \end{align}
* For $n\>m-1$: \begin{align} &S\to aaA \\ &A\to aAb \mid \lambda \end{align}

Yet I can not mix them and get a correct grammar for $L$.

# Answer
> 3 votes
If you split the grammar into two parts for disjoint parts of the language you better take different names for the variables, since they have a different meaning in the two parts.

# Answer
> 0 votes
In your first grammar, change S to X and leave A unchanged. In your second grammar, change S to Y and A to B. Then add S -\> X | Y.

And fix your grammars to handle n \< m-1 instead of n=m-2 and n\>m-1 instead of n = m+2.

---
Tags: context-free, formal-grammars
---


title: polynomial reduction within Np

text:
# Question
Title: polynomial reduction within Np
If $A \le\_p B$ and $B\in NP$, does it necessarily follow that $A\in NP$?
($\le\_p$ is a polynomial many-one reduction)

A quick yes/no comment is enough, a proof would be nice :-)

# Answer
Yes: we know that being in $NP$ is equivalent to having a polynomial verifier.

Let $M$ be the verifier of $B$ (getting an input $x$ and a witness $w$), and let $f$ be the reduction function.

Then, define $M'(x,w):=M(f(x), w)$. Since $x\in A\iff f(x)\in B$, then $\exists w. M(f(x),w) \iff f(x)\in B\iff x\in A$, and thus $M'$ is a verifier for $A$, hence $A\in NP$
> 2 votes

---
Tags: np, polynomial-time-reductions
---


# Question
Title: Use the CFL pumping lemma to show that this language(0^p where p is prime) is not context free
L = {0^p |p is a prime}. So was looking at the explanation at the bottom of page 5 of the following website: https://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW5Sols.pdf

I want to make sure that I understand every component of the problem.

1. Why do they choose at least n + 2 when deciding k?
2. Does the statement |vx| = m mean that m is the total amount of times v and x are pumped combined?
3. I don't get how m(k − m) + m is the length of z' I really need a ELI5 explanation. so k - m is how many times v and x are pumped and m is total pumps and that's pretty much the extent of my knowledge.

# Answer
> 1 votes
1. The reason is explained later: so that $k-m \geq k - n \geq 2$
2. $|vx| = m$ means that the total number of symbols in $v$ and $x$ is $m$. It is unrelated to the amount pumped. $|\cdot|$ is a notation for the size or the length of the word.
3. Actually there is a mistake here: if $|vx| = m$ and $|uvwxy| = k$, that means that $|uwy| = k - m$. So if we pump $v$ and $x$ a total of $k-m$ times, then $z' = uv^{k-m}wx^{k-m}y$ verifies $|z'| = |v^{k-m}x^{k-m}| + |uwy| = (k-m)|vx| + k - m = (k-m)m+k-m$ (and not $(k-m)m + m$ as stated in the document).

---
Tags: automata, pumping-lemma
---


# Question
Title: Semi-streaming algorithm for $s$-$t$ connectivity
Let $G=(V,E)$ be an undirected graph. Given a pair of vertices $s,t \in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $t$ are connected? Is there any way to construct such an algorithm which scans the input stream only once?

**Note** that a semi-streaming algorithm is presented an arbitrary order of the edges of $G$ as a stream, and the algorithm can only access this input sequentially in the order it is given; it might process the input stream several times. The algorithm has a working memory consisting of $O(n\log^{O(1)}n)$ bits.

# Answer
> 3 votes
You cannot do it in a single pass. Consider the set of all graphs of the following form: the vertices are $\\{s,t\\} \cup A \cup B$, where $|A|=|B|=n/2-1$. The only allowed edges are between $s$ and $A$, between $A$ and $B$, and between $B$ and $t$.

Suppose that the algorithm is first presented with the $(A,B)$ edges, and then with the $(s,A),(B,t)$ edges. After reading the $(A,B)$ edges, it must "remember" all of them, since there could be only one $(s,A)$ edge and only one $(B,t)$ edge, in which case the answer depends on whether the corresponding vertices in $A$ and $B$ are connected. Since there are $2^{(n/2-1)^2}$ choices for the $(A,B)$ edges, the algorithm must have a memory of at least $(n/2-1)^2$ bits (since after reading the $(A,B)$ edges, it could be in any of $2^{(n/2-1)^2}$ possible states).

# Answer
> 0 votes
I just wanted to add a comment to Yuval's answer but I don't have 50 reputation yet.

We don't have to distinguish all different $2^{(n/2-1)^2}$ subgraphs since for some subgraphs their answer to $s$-$t$ connectivity would be the same. I believe that we can use a disjoint set union data structure that solves this problem... (imagine that you are running Kruskal's algorithm on a unweighted graph, the goal is to come up with a connectivity witness shows that $s$ and $t$ are connected, you only need $O(n\log n)$ bits of information so store a tree.)

---
Tags: streaming-algorithm, big-data
---


title: degree distribution

text:
# Question
Title: degree distribution
Does anyone know how to compute node degree distribution in a graph ? I am talking about a large graph for example California road network and imagine we have some data such as number of nodes and number of edges and now we want to visualize data by histogram for distribution of nodes degrees.Is there any specific formula ?the link is included : https://snap.stanford.edu/data/roadNet-CA.html

# Answer
To compute the node degree distribution, compute the degree of each node in the graph; then compute the distribution of these numbers (e.g., display a histogram of them). Each of those tasks is a straightforward coding exercise.
> 3 votes

# Answer
I know the question was asked long ago. Just responding to this so that others might get the help.

You can easily plot and visualize the degree distribution using the `NetworkX` library. It is a python based library for doing graph analysis. Here is a sample code that you can use to visualize the degree distribution of `California road network`. Hope you will find it useful.

# import libraries
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import collections as collec
%matplotlib inline

# reading roadNet-CA graph.
G_road = nx.read_edgelist("/data/roadNet-CA.el", nodetype=int, comments='#', create_using=nx.DiGraph)

# Calculate out degrees of roadNet-CA graph
out_degrees = G_road.out_degree() # dictionary node:degree
out_values = sorted([d for n, d in out_degrees])
out_set = set(out_values)

# building the histogram
out_hist = []
for x in out_set:
    cnt = out_values.count(x)
    for i in range(cnt):
        out_hist.append(cnt)

# log-log ploting the out-degree distribution
plt.figure(figsize=(12, 8))
plt.grid(True)
plt.loglog(out_values, out_hist, 'bv-') # out-degree
plt.xlabel('Out Degree')
plt.ylabel('Number of nodes')
plt.title('Out-degree distribution (Log-Log) of RoadNet graph')
plt.show()
```

> 0 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Most scalable distributed consensus mechanism based on message complexity?
One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity.

For example, PBFT message complexity is `O(n^2)` that means that it is only scalable to tens of nodes. Thus, classical BFT (Byzantine Fault Tolerant) consensus mechanisms are not scalable to the large networks.

Nevertheless, I am looking for the most scalable BFT consensus among all.

In other words, is there a distributed BFT consensus with less than `O(n^2)` message complexity?

**P.S.** I brought up this question before in **scicomp.stackexchange.com**, but they suggested me to bring up it here. (https://scicomp.stackexchange.com/q/36087/37225)

# Answer
> 0 votes
You can turn a lot of consensus algorithms that utilize a "leader" into one that takes only O(n) message complexity in the optimistic case, by sending every message in that iteration to the leader, who then broadcasts your message to everyone. (PBFT should fall into this category, except for the view change). Assuming threshold signatures, we can further get O(n) bit complexity. (See Hotstuff, Jolteon, Tendermint).

IIRC in the pessimistic case, Hotstuff still needs a quadratic pacemaker, so the message complexity is still O(n^2), but one could argue (as they do) that they achieve a O(n) \`\`view change''.

I would also look at the Algorand style of protocol, which achieves $O(n\lambda)$ communication, where $\lambda$ is a choice of security parameter. (It will end up being about $2500$ servers each doing a multicast every round, with current concrete notions of security).

---
Tags: time-complexity, performance, consensus, message-passing
---


# Question
Title: If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?
> If $L$ is a regular language, prove that the language $L\_1 = \\{ uv \mid u \in L, |v| =2 \\}$ is also regular.

My idea: $L$ can be represented as a DFA and then you could add 2 consecutive transitions from every final state for the letters of $v$, creating a new NFA diagram. Is that correct? I'm not sure how to make this a formal proof.

# Answer
Your idea is correct.

You should take the following path to formally write it up/prove it. First assume that $L$ is accepted by some DEA $M=(Q,\Sigma,\delta,q\_0,F)$ then define a new NEA $M'=(Q',\Sigma,\delta',q'\_0,F')$ based on $M$. Just express you ideas formally, for example start with

* $Q'=Q\cup\\{q\_\text{new1},q\_\text{new2}\\}$,
* $F'=\\{q\_\text{new2}\\}$,
* ....

Then you should prove, using the acceptance criteria for $M$ and $M'$, that $w\in L(M) \iff wv\in L(M')$, for all $v\in \Sigma^2$.

**Alternative approach**

The following idea will also prove the statement but results in an easier proof. First show that the language of words with exactly two characters is regular, and then argue with the closure properties for regular languages.
> 6 votes

# Answer
If $A$ is the alphabet, $L\_1 = LAA$. Now $A$ is finite and thus regular. Thus if $L$ is regular, then $L\_1$ is the product of three regular languages and hence is regular.

Exercise. Use the same type of argument to show that if $L$ is context-free, then so is $L\_1$.
> 0 votes

---
Tags: regular-languages, automata, finite-automata, closure-properties, check-my-answer
---


# Question
Title: How are boolean circuits used for solving P vs NP?
In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to me in simple terms how boolean circuits are used for solving P vs NP?

# Answer
> 8 votes
First, let me start by explaining what Boolean circuits are. You are probably familiar with Boolean *formulas* — these are formulas of the sort $(a \land b) \lor (\lnot a \land \lnot b)$. We can represent each formula as a *tree*. In our example, the root of the tree will be labeled $\lor$, and its two children are the trees corresponding to $a \land b$ and $\lnot a \land \lnot b$. More generally, there are four types of nodes: nodes labeled $\lor$ or $\land$ have exactly two children, nodes labeled $\lnot$ have exactly one child, and the rest of the nodes are labeled by input variables. We can think of the edges as directed towards the root.

Boolean circuits generalize Boolean formulas by allowing arbitrary directed acyclic graphs instead of directed trees. In the example above, we can, for example, identify the two nodes labeled $a$ and the two nodes labeled $b$. Alternatively, we can identify Boolean circuits with *straightline programs*. These are programs which use the following instructions:

* $x \gets y \lor z$.
* $x \gets y \land z$.
* $x \gets \lnot y$.

For example, the formula above corresponds to the straightline program

* $x \gets a \land b$.
* $y \gets \lnot a$.
* $z \gets \lnot b$.
* $w \gets y \land z$.
* $o \gets x \lor w$.

The value of the formula is the value of the last assignment. Notice that every variable other than the inputs is used exactly once. Straightline programs with this constraint correspond to formulas. If we remove the constraint, the we get circuits.

---

The $\mathsf{P} \neq \mathsf{NP}$ conjecture can be stated equivalently as follows:

> SAT has no polynomial time algorithm.

It turns out that the following conjecture (known as $\mathsf{P/poly} \neq \mathsf{NP}$) *implies* $\mathsf{P} \neq \mathsf{NP}$:

> SAT has no polynomial size circuits.

What does this mean? We can encode CNFs as strings of bits (for example, encode them first in ASCII, and then unfold the ASCII into bits). Let $SAT\_n$ be the collection of satisfiable CNFs of length $n$ bits. A *circuit for $SAT\_n$* is a circuit on $n$ inputs $x\_1,\ldots,x\_n$ which returns True if and only if $x\_1\ldots x\_n \in SAT\_n$, i.e., the CNF corresponding to $x\_1\ldots x\_n$ is satisfiable. We say that a collection of circuits $C\_1,C\_2,\ldots$ solves SAT if $C\_n$ is a circuit for $SAT\_n$. The collection has *polynomial size* if there exists a polynomial $P(n)$ such that the size of $C\_n$ is at most $P(n)$ (the size of a circuit is the number of nodes in its graphical representation).

Why does this imply that SAT has no polynomial time algorithms? The reason is (essentially) the Cook–Levin theorem. This theorem shows that if SAT has a polynomial time algorithm then it also has polynomial size circuits. There is nothing special about SAT here — this reduction works for every problem. The theorem shows how to encode the computation of a Turing machine running in polynomial time as a polynomial size circuit.

---

Unfortunately, we are very far from realizing this program. We only know how to show that polynomial size circuits cannot solve certain problems in the following circumstances:

* When the circuit is *shallow*, that is, has small depth.
* When the circuit doesn’t use $\lnot$ gates at all.
* For non-explicit problems: by counting the number of polynomial size circuits (for any fixed polynomial), you can show that there must be some functions that they cannot compute.

There is some further progress which throws diagonalization into the mix, but that’s about it. It seems that this approach is stuck, and different lines of attack are required to solve this important problem.

# Answer
> 1 votes
Despite being called "circuits", Boolean circuits are essentially the same thing as Boolean formulas. This means that questions about Boolean circuits are exactly questions about SAT, which is the prototypical **NP**-complete problem.

# Answer
> 0 votes
We can represent an algorithm by a Boolean algebra and implement the Boolean algebra using digital gates to form a circuit in digital electronics. The time complexity of executing the algorithm is the number of gate operations the digital circuit got.

This Boolean algebra can be simplified into having only 'Not' operations in the first layer by applying De Morgan's theorem repeatedly at 'Not' operations after every 'And' and 'Or' operations. This pushes all the 'Not' operations to the first layer. The new simplified Boolean algebra has time complexity at most twice the original Boolean algebra.

We can represent a Markov Random Field NP problem as an sum of products form in Boolean algebra with exponential number of 'Or' operations. Note that this Boolean algebra has no 'Not' operation which makes it easy to be factorized. Then we will try to factorize this Boolean algebra to get the Polynomial time Boolean algebra. In the paper below, he has shown that it is impossible to factorize the Boolean algebra into Polynomial time Boolean algebra and therefore NP is not equal to P.

Links to the paper: Prove Np not equal P using Markov Random Field and Boolean Algebra Simplification

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

# Answer
> 3 votes
$\def\co{\mathrm{co}}\def\poly{\mathrm{poly}}\def\N{\mathbb N}$A language $L$ is in $(C/\poly)\cap(\co C/\poly)$ iff there are languages $$L\_0\in C,\qquad L\_1\in\co C,$$ and sequences of advice strings $\\{a\_{0,n}:n\in\N\\}$, $\\{a\_{1,n}:n\in\N\\}$ such that $$|a\_{0,n}|,|a\_{1,n}|=n^{O(1)},$$ and for any $n\in\N$ and $w\in\\{0,1\\}^n$, $$w\in L\iff(w,a\_{0,n})\in L\_0\iff(w,a\_{1,n})\in L\_1.$$ (I’m assuming the class $C$ is robust enough so that the exact representation of $(w,a)$ does not matter.)

In contrast, $L$ is in $(C\cap\co C)/\poly$ iff there exists a *single* language $$L'\in C\cap\co C$$ and a sequence of strings $\\{a'\_n:n\in\N\\}$ such that $$|a'\_n|=n^{O(1)},$$ and for any $w\in\\{0,1\\}^n$, $$w\in L\iff(w,a\_n)\in L'.$$

Thus, we trivially have the inclusion $$(C\cap\co C)/\poly\subseteq(C/\poly)\cap(\co C/\poly)$$ as we can just put $L\_0=L\_1:=L'$, $a\_{0,n}=a\_{1,n}:=a'\_n$. However, there is no a priori reason for the reverse inclusion to hold: while we can easily combine $a\_{0,n}$ and $a\_{1,n}$ to a single advice $a'\_n=(a\_{0,n},a\_{1,n})$, there is in general no way how to unify $L\_0\in C$ and $L\_1\in\co C$ to a single language $L'\in C\cap\co C$.

For the specific examples, it seems reasonable to conjecture that $$\def\np{\mathrm{NP}}(\np\cap\co\np)/\poly\subsetneq(\np/\poly)\cap(\co\np/\poly),$$ but since this implies various hard separations (in particular, $\np\ne\co\np$ and $\np\nsubseteq\mathrm P/\poly$), we don’t know how to prove that.

On the other hand, the Immerman–Szelepcsényi theorem ensures that $\def\nl{\mathrm{NL}}\nl=\co\nl$, hence $$\nl/\poly=\co\nl/\poly=(\nl/\poly)\cap(\co\nl/\poly)=(\nl\cap\co\nl)/\poly.$$

For an example (even if a bit contrived) with an unconditional separation, let $\def\nul{\mathrm{NULL}}\nul$ denote the class of languages of asymptotic density $0$: i.e., if $L\subseteq\\{0,1\\}^\*$, then $$L\in\nul\iff\lim\_{n\to\infty}\frac{|L\cap\\{0,1\\}^n|}{2^n}=0.$$ Then $\nul\cap\co\nul=\varnothing$, hence also $$(\nul\cap\co\nul)/\poly=\varnothing.$$ On the other hand, $$(\nul/\poly)\cap(\co\nul/\poly)$$ is the class of *all* languages: for any language $L$, define $$L\_0=\\{(w,0^n):w\in L,n=|w|\\}\in\nul$$ and $$L\_1=\overline{\\{(w,0^n):w\in\overline L,n=|w|\\}}\in\co\nul.$$ Then we have $$w\in L\iff(w,0^n)\in L\_0\iff(w,0^n)\in L\_1$$ for any $w\in\\{0,1\\}^n$.

---
Tags: complexity-theory, complexity-classes, closure-properties, nondeterminism, circuits
---


# Question
Title: Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$
I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a\_1, \ldots, a\_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b\_1, \ldots, b\_D)$ that minimizes $\prod\_{i = 1}^{D}\left(a\_i + b\_i\right)$ such that $\prod\_{i = 1}^{D}\left(a\_i + b\_i\right)$ is a multiple of $c$.

The brute force search I came up with is

1. Let $t$ be the smallest multiple of $c$ that is $\ge \prod\_{i = 1}^{D} a\_i$.
2. Use depth-first-search to search for values $\hat{b}$, starting at $\mathbf{0}$ and incrementing one element of $\hat{b}$ at a time until $\prod\_{i = 1}^{D} \left(a\_i + \hat{b}\_i\right) \geq t$.
3. If we found $\hat{b}$ such that $\prod\_{i = 1}^{D} \left(a\_i + \hat{b}\_i\right) = t$ then $\hat{b}$ is the optimal solution. Otherwise increment $t$ by $c$ and go back to step 2.

The above algorithm does work, but if $D$ or $c$ are too large then it will potentially take a very very long time. I'm wondering if this maps to any well known algorithm or if there's a more efficient solution. I'm considering that the prime factors of $c$ and $a$ could play a large role in reducing the search space but I can't quite figure it out.

In case anyone wants to play with this, a Python 3 implementation of the brute force algorithm described above is

```
from functools import reduce
from operator import mul

def prod(x):
    return reduce(mul, x, 1)

def ceil_divide(num, denom):
    return -(-num // denom)

def update_memory(b, memory):
    tuple_b = tuple(b)
    if tuple_b in memory:
        return False
    memory.add(tuple_b)
    return True

def dfs(a, b, t, memory):
    if not update_memory(b, memory):
        return False

    p = prod([ai + bi for ai, bi in zip(a, b)])
    if p == t:
        return True
    elif p > t:
        return False

    for i in range(len(a)):
        b[i] += 1
        if dfs(a, b, t, memory):
            return True
        b[i] -= 1

def solve(a, c):
    b = [0 for _ in range(len(a))]
    t = c * ceil_divide(prod(a), c)
    while not dfs(a, b, t, set()):
        t = t + c
    return b

# a few test cases
assert solve([2, 3], 9) == [1, 0]
assert solve([2, 8], 6) == [0, 1]
assert solve([13, 17, 25], 8) in [[1, 1, 1], [0, 1, 3]]
assert solve([5, 13, 19], 6) == [0, 1, 2]

```

Note: One potential use-case of such a thing could be, for example, to find the minimum padding of a $D$-dimensional tensor such that the number of elements of the tensor is divisible by $c$.

# Answer
> 2 votes
If $c$ doesn't have too many factors and is not too large, the following should work reasonably well for typical numbers.

Factor $c$ into its prime factorization, say $c=p\_1^{e\_1} \cdots p\_k^{e\_k}$. Enumerate all tuples $(f\_1,\dots,f\_D)$ of non-negative integers such that $f\_1 \cdots f\_D = c$. For each such tuple $(f\_1,\dots,f\_D)$, and each $i$, find the smallest $b\_i$ such that $a\_i+b\_i$ is a multiple of $f\_i$ (namely, $b\_i = f\_i - a\_i \bmod f\_i$); then compute $\prod\_i (a\_i+b\_i)$ and keep the smallest found so far. By construction, this will explore all possible solutions, and output the best one.

You can use the prime factorization of $c$ to help you enumerate all tuples $(f\_1,\dots,f\_D)$. In particular, the prime factorization makes it easy to enumerate all factors of $c$, so we can enumerate all possibilities for $f\_1$ (namely, all factors of $c$), then enumerate all possibilities for $f\_2$ (namely, all factors of $c/f\_1$), etc.

The running time will be proportional to the number of such tuples you have to enumerate. This number is $\prod\_i {e\_i + D - 1 \choose D - 1},$ which is not too bad if the number of prime factors of $c$ is small, but is horrible if $c$ has many prime factors.

# Answer
> 0 votes
Based on the answer by D.W. I was able to implement an alternative algorithm. This effectively iterates over all permutations of $D$-length factorizations of $c$. Instead of utilizing the prime factorization to explicitly enumerate all the factorizations, I increment one element of $b$ to the next multiple of a divisor of $c$, then divide out that divisor from $c$ and repeat recursively. This effectively explores all $D$-length factorizations of $c$, but has the benefit of being able to ignore a large subset of the search space by abandoning a branch when the objective product becomes larger or equal to the smallest feasible objective found so far. Combined with some simple memoization, the resulting algorithm appears to be much faster on average than my original algorithm.

I've tested this on lots of random cases and tried to construct some pathological cases as well. I think there might be some pathological cases where this is slower than the original brute force, probably when there are tons of prime factors in $c$, but it seems to be much better on average.

My Python 3 implementation of the updated algorithm is

```
from functools import reduce
from operator import mul
from copy import deepcopy

def prod(x):
    return reduce(mul, x, 1)

def argsort(x, reverse=False):
    return sorted(range(len(x)), key=lambda idx: x[idx], reverse=reverse)

def divisors(v):
    """ does not include 1 """
    d = {v} if v > 1 else set()
    for n in range(2, int(v**0.5) + 1):
        if v % n == 0:
            d.add(n)
            d.add(v // n)
    return d

def update_memory(b, c_rem, memory):
    tuple_m = tuple(b + [c_rem])
    if tuple_m in memory:
        return False
    memory.add(tuple_m)
    return True

def dfs(a, b, c, c_rem, memory, p_best=float('inf'), b_best=None):
    ab = [ai + bi for ai, bi in zip(a, b)]
    p = prod(ab)
    if p >= p_best:
        return p_best, b_best
    elif p % c == 0:
        return p, deepcopy(b)

    dc = divisors(c_rem)
    for i in argsort(ab):
        for d in dc:
            db = (d - ab[i]) % d
            b[i] += db
            if update_memory(b, c_rem // d, memory):
                p_best, b_best = dfs(a, b, c, c_rem // d, memory, p_best, b_best)
            b[i] -= db

    return p_best, b_best

def solve(a, c):
    b = [0 for _ in range(len(a))]
    result = dfs(a, b, c, c, set())
    p_best, b_best = result
    return b_best

# a few test cases
assert solve([2, 3], 9) == [1, 0]
assert solve([2, 8], 6) == [0, 1]
assert solve([13, 17, 25], 8) in [[1, 1, 1], [0, 1, 3]]
assert solve([5, 13, 19], 6) == [0, 1, 2]

```

---
Tags: algorithms, optimization, dynamic-programming, integer-programming, modular-arithmetic
---


# Question
Title: Splay Tree: Repeatedly searching for the same key that's not in the Tree
In a splay tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the tree. Since the first search has a worst-case complexity of $O(n)$ and afterwards the node we're looking for is the new root, so further search operations take $O(1)$ time.

How could we prove that $m$ sequential search operations for the same key that is not in the tree also has a time complexity in $O(n+m)$?

# Answer
> 3 votes
In a BST, a lookup for an key that isn't present traces out a path through that tree that ends at either that key's successor or that key's predecessor. We'll use this property to get the desired $O(m + n)$ bound.

To begin with, suppose that what you're searching for is smaller than all other keys in the tree or bigger than all the keys in the tree. In that case, the first lookup will terminate at either the smallest or largest key in the tree, splaying it to the root in time $O(n)$. From that point, each search will be performed by starting at the root and either walking off the tree to the left or walking off the tree to the right, taking time $O(1)$, for a net total of $O(m + n)$ work done with the accesses.

Otherwise, the key $x$ we're looking for is sandwiched between keys $p$ and $s$, representing the key's predecessor or successor. This means that $p \< x \< s$. Consider the first two searches for $x$. The first one will terminate either at $p$ or at $s$, splaying it up to the root. Assume WLOG that it's $p$. The second search will then begin at $p$ and end at $s$, which splays $s$ up to the root. Let's think about what that process looks like. Specifically, focus on the very last splay step that takes $s$ up to the root. It can't be a zig-zig or zag-zag step, since if that were the case there would have to be a key $t$ sandwiched between $p$ and $s$, which is impossible because $p$ is $s$'s predecessor and $s$ is $p$'s successor. Therefore, the last splay operation that carries $s$ up to the root must either be a zig-zag step or a zig step (or one of the mirrors). Either way, the final splay step consists of rotating $s$ directly over $p$. That means that the tree now has $s$ as the root with $p$ as its left child. Importantly, $p$ has no right child, since if $p$ had a right child $t$ then we'd have $p \< t \< s$, which is impossible because $p$ is $s$'s predecessor.

Now, think about the next lookup. It will start at $s$, then move left to $p$, then move right from $p$ off the tree. We then splay $p$ up to the root. This requires only two node visits and one rotation and takes time $O(1)$. We now have $p$ as the root with $s$ as the right child. And, analogously to before, $s$ will not have a left child because $p$ is its predecessor. A search for $x$ now starts at $p$, moves right to $s$, then moves left off the tree, splaying $s$ back up to the root with $p$ as its right child. That process takes time $O(1)$ as well.

Overall, the first two splays to pull $s$ and $p$ up to the top of the tree take time $O(n)$, and each successive search takes time $O(1)$, toggling between whether $s$ or $p$ is the tree root. This makes the overall time spent $O(m + n)$.

---
Tags: time-complexity, data-structures, binary-search-trees, splay-trees
---


# Question
Title: Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$
Given alphabet $\\{0,1\\}$, we want to uniformly sample $x,y \in \\{0,1\\}^n$ such that $ed(x,y)=k$, where $ed$ denotes the Levenstein distance, i.e., the minimum number of edit operations (insert, delete, substitute) that can transform $x$ to $y$.

Clearly, this can be done by brute force over all pairs of strings, which is very costly. To reduce the complexity, my main idea is to use Monte Carlo sampling:

*Monte Carlo sampling:* pick $x\sim\\{0,1\\}^n$ at random, introduce $k$ successive edit operations (equal number of delete and insert to end up with the same length) ending up in string $y$ and reject the pair iff $ed(x,y)\neq k$. The main challenge is to guarantee that the probability of confirmation is not exponentially low. Such a low probability of success forces us to repeat the sampling an exponential number of times, rendering any time savings useless.

*Informal analysis:* Let $x=:x\_0\to \dots \to x\_k:=y$ denote the intermediary strings during our $k$ random edits. Let $S\_i(x)$ for $i\le n$ denote the level set for edit distance from $x$: $$S\_i(x)=\\{y\in \\{0,1\\}^n: ed(x,y)=i\\}.$$ Therefore, $ed(x,y)=k$ implies $x\_i\in S\_i$ for all $i=0,\dots, k$. By construction, if we have $x\_i\in S\_i$, then $x\_{i+1}$ must belong to one of $S\_{i-1}, S\_i, S\_{i+1}$ level sets. Therefore, the probability of failure at step $i$ is bounded by the ratio $\alpha\_i=(|S\_i|+|S\_{i-1}|)/(|S\_i|+|S\_{i-1}|+|S\_{i+1}|)$. It remains to show that if $k$ is small (how small?) the ratio $\alpha\_i$ remains very high, and in fact $\prod\_i^k \alpha\_i$ is not exponentially low.

Two main questions:

* How can we make my hand-wavy argument more rigorous?
* In the regime that $k$ is comparable to $n$ the proposed algorithm provably fails. Namely if $k\>2n/3$, random walks will never get you much further than $ed(x,y)\approx n/2$, as even the edit distance of two randomly generated strings is concentrated around $n/2$. What would be an alternative to sampling for large $k$?

# Answer
There are two considerations: running time, and correctness.

Running time: When $k \< (n-1)/\lg(4n)$, heuristically I expect the running time of your algorithm to be fine and I'd guess you won't experience exponential blowup. We can show $|S\_k| \le (4n)^k$, so when $k \< (n-1)/\lg(4n)$, $|S\_k|/2^n \le 1/2$. This is not a proof; to prove that everything is OK, we need to prove that $|S\_k|/(|S\_0| + \dots + |S\_k|)$ is not too small, and I don't have a proof of that.

For large $k$, I don't know what algorithm might be suitable.

Correctness: Your method is not correct. It does not produce $(x,y)$ with the right distribution. Given $x$, not all $y \in S\_k(x)$ will be equally be likely to be reached by the procedure you give, so your approach introduces a bias in the distribution of $x,y$.

For example, suppose $x=10001$ and $k=2$. If $y=00000$, there is just one edit script that transforms $x$ into $y$ (substitute bits 1 and 5). If $y=10010$, there are seven edit scripts that transform $x$ into $y$ (substitute bits 4 and 5; or, delete one of bits 2-4 and insert a 0 at the end, or do the same in the opposite order). So, if $x=10001$, your algorithm will be seven times as likely to output $(10001,10010)$ as it is to output $(10001,00000)$. This deviates from the uniform distribution.

Incidentally, I believe the procedure you outline is just rejection sampling (i.e., just Monte Carlo), not MCMC.
> 3 votes

---
Tags: sampling, edit-distance, monte-carlo
---


# Question
Title: Question about an answer related to designing an ASM for a sequence detector
The question says:

> Design a sequence detector that searches for a series of binary inputs to satisfy the pattern 01\[0\*\]1, where \[0\*\] is any number of consecutive zeroes. The output (Z) should become true every time the sequence is found.

The answer to this example in the document I am reading is this:

My question is: After going from state 'first', the decision box checks X. If it is 0, then it does not fit the pattern 01\[0\*\]1. So, it should go back to state 'start'. In this answer, it goes back to state 'first' instead, and so a sequence that violates the pattern could eventually get accepted. For example, the sequence 0011 does not match the pattern given, yet it will be accepted by the given ASM. The first 0 will land us in state 'first', and the 2nd 0 will go back to 'first' and then the 1 will lead to state 'second' and the final one will go to state 'success', outputting Z.

Am I correct to think so? If not, why?

The document can be found here: https://www.mil.ufl.edu/3701/classes/joel/17%20Lecture.pdf

The question is tagged with finite automata because there is no ASM tag. The two are similar enough.

# Answer
Yup. It looks like this accepts 0011, and it shouldn't, so it looks to me like the automaton is buggy.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?
I was solving the following problem, just for reference (441 - Lotto). It basically requires the generation all $k$-combinations of $n$ items

```
void backtrack(std::vector<int>& a,
               int index,
               std::vector<bool>& sel,
               int selections) {
    if (selections == 6) { // k is always 6 for 441 - lotto
        //print combination
        return;
    }
    if (index >= a.size()) { return; } // no more elements to choose from
    // two choices
    // (1) select a[index]
    sel[index] = true;
    backtrack(a, index+1, sel, selections+1);

    // (2) don't select a[index]
    sel[index] = false;
    backtrack(a, index+1, sel, selections);

}

```

I wanted to analyze my own code. I know at the top level (level = 0), I'm making one call. At the next level (level=1) of recursion, I have two calls to backtrack. At the following level, I have $2^2$ calls. The last level would have $2^n$ subproblems. For each call, we make $O(1)$ work of selecting or not selecting the element. So the total time would be $1+2+2^2+2^3+...+2^n = 2^{n+1} - 1 = O(2^{n})$

I was thinking since we're generating $\binom{n}{k}$ combinations that there might be a better algorithm with a better running time since $\binom{n}{k}=O(n^2)$ or maybe my algorithm is wasteful and there is a better way? or my analysis in fact is not correct? Which one is it?

# Answer
> 2 votes
Obviously your code will be lower bounded by $\Omega \left(n \choose k \right)$ since you can't skip any combinations, then you wouldn't be generating them all.

With this in mind we can do a little better analysis on the bound. Let's take a look at the recursion tree for this. Let's use a small example like 4 choose 2. Here is how your algorithm would work:

This generates all valid choices of 2 elements from 4 (seen in green). At this point you may realize that your algorithm actually generates some invalid combinations for 4 choose 2 (seen in red).

If we had a completely full tree that never terminated early (at `selections == k`) then it would be easy enough to show that this runs in $O(2^n)$ if you just sum up the levels. However our tree ends early for a lot of branches and when $k$ is small and $n$ is large this would be much less than $O(2^n)$.

Let's say your code doesn't consider invalid possibilities. This should make analysis easier so that there are only $n \choose k$ leaf nodes. We would prune these branches (in red):

This would be easy enough to do with a `if ((a.size() - index) <= (k - selections)) return;` check.

Now if this is the case then we know there are only $n \choose k$ leaf nodes in our recursion tree. We also know that the longest path from root to leaf would be $n$ so we can easily upper bound this by $O(n \binom{n}{k})$ which is better than the $O(2^n)$ we previously discussed.

If you assume printing the combination takes $O(n)$ then this is the best we can do since the printing time complexity would dominate the leaf depth complexity.

---

You could attempt to do a little better if you assume that printing takes $O(k)$ which you may be able to manage.

We can get a little better accuracy with this. For example, we know there's exactly 1 leaf node at depth $k$ (i.e. pick the first $k$ elements). We also know there will be exactly $k$ leaf nodes at depth $k+1$ since this is essentially the scenario where we *do* choose the $k+1$st element and we *don't* choose 1 of the first $k$ nodes (i.e. $k \choose 1$ or equally $k \choose k-1$). Similarly the # of leaf nodes at depth $k+2$ would be $k+1 \choose k-1$. Then we can extrapolate this for all leaf depths. At depth $k \<= i \<= n$ we would have exactly $f(i)$ nodes where:

$$f(i) = \binom{i - 1}{k-1}$$

From this we can determine the time complexity of leaf nodes at depth $i$ as $t(i)$:

$$t(i) = i \cdot f(i)$$

We then sum these up from depth $i = k \ldots n$ for the overall time complexity:

$$\begin{align} T(n) & = \sum\_{i = k}^{n} i \binom{i-1}{i-k} \\ \end{align}$$

It ended up getting pretty messy so I'm not going to work it out completely, but in short this will still be $O(n \binom{n}{k})$ and $\Omega(k \binom{n}{k})$.

# Answer
> 0 votes
If you want to *generate* all items, the runtime is obviously at least O(n over k). To avoid exceeding O(n over k) your algorithm must be quite carefully designed.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Assembly Language Step By Step: Why deviate from the norm and design computers where the presence of voltage encodes a 0 bit?
That the presence of voltage across a switch encodes 12 is purely arbitrary... Jeff Duntemann's book mentions:

> We could as well have said that the lack of voltage indicates a binary 1 and vice versa (and *computers have been built this way* for obscure reasons)

I find this (italicized part) interesting. It would be great if someone could shed some light on what "obscure" reason(s) may motivate people to do so?

# Answer
Quite opposite from what this Mr. Duntemann says, there are no "obscure" reasons for this at all. It is totally arbitrary whether you interpret "no voltage" as 0 or as 1. Anyway, you don't distinguish between "no voltage" and "voltage". You distinguish between "voltage below a low threshold" which is one binary value, "voltage below a high threshold" which is another binary value, "voltage between these thresholds" which is a state that should be avoided because things will not be reliable, and "exceedingly high voltage" which destroys your computer.

Look at your phone. Or your home computer. You have ABSOLUTELY NO IDEA if the processor inside interprets low or high voltage as 0 or 1. And you don't care. It doesn't make a difference. Of course the physical implementation of a NAND or NOR gate would be different.
> 3 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Alphabetical order under which list of strings is lexicographically sorted
We are given an array of $n$ Strings with total Length $K$, and we are asked to find an alphabetical order (if one exists) with respect to which the array become lexicographically sorted. The time complexity should be $O(K)$.

I think we should use some data structure like a trie, but I can't find a way to solve the problem.

# Answer
> 3 votes
For any pair of adjacent strings, you can find a constraint of the form $\sigma \< \tau$ on the order of the symbols which is necessary in order for this pair of strings to be lexicographically ordered. This doesn't require any fancy data structure.

Putting all of these constraints together in a directed graph, you can determine whether such an order exists, and if so, find it.

---
Tags: algorithms, data-structures
---


# Question
Title: Proof that $\{a^ib^jc^k\mid i,j,k\in\mathbb{N}, i<k<j\}$ is not context-free using the Pumping Lemma
$$ L=\\{a^ib^jc^k \\;| \\;i, j, k \in \mathbb{N} \\; \text{and} \\; i \<k\<j\\} $$

I need to show that this language is not context-free with the help of the Pumping Lemma. My first intuition is, that there exist 5 different cases, i.e. the middle part, let's call it vwx, consists of

1. only $a$'s
2. only $b$'s
3. only $c$'s
4. $a$'s and $b$'s
5. $b$'s and $c$'s

and I need to find a pumping constant, which excludes the new word from the above defined language. However, I am having a hard time how show that formally and precisely. Any hints are highly appreciated!

# Answer
Your case analysis seems right and can be used to prove non-contextfreeness.

Not you don't have to find a pumping constant. To the contrary, you have to show no such constant can exist. So, the general argument is usually like "if I assume $N$ is the pumping constant, I can use this word $x\in L$, longer than $N$, and whatever I try, we cannot pump it and stay in $L$."

Usually one choses a string that is "just" inside the language, in this case $a^Nb^{N+1}c^{N+2}$. Now check your cases. What if we pump $a$'s and or $b$'s, but no $c$'s etcetera.

One final hint, which seems necessary here. One cannot only "pump up", but also "pump down".
> 1 votes

---
Tags: context-free, pumping-lemma
---