# Question
Title: Hoare Logic: Identifying Hoare Triple given a simple function
> The program is designed to start with values for $x$ and $y$. The variables $u1$ and $u2$ are intended to represent $x$ and $y$ in ascending order.
> Provide suitable preconditions and postconditions for the program.
> Then, using Hoare logic, prove the correctness of the program.
> Specify all proof obligations and justify their correctness.
> Note that formal proofs (e.g., using natural deduction) are not required.

Edit I accidentally left out an important detail: "You should consider that the postcondition should be such that we know the initial values of both x and y occur in the set {u1, u2}."

```
if (x < y) {
    u_1 = x;
    u_2 = y;
} else {
    u_1 = y;
    u_2 = x;
}

```

Is the preconditions: $x\<y\ \lor\ y\<x$ and the postcondition: $u1\<u2$ correct? Right now I only need help with defining correct pre- and postconditions.

# Answer
Postcondition $u\_1 \leq u\_2$ would work, and make in the beginning of the program assertion $ \text{True} $ simply,

Consider the following scheme:

$$ \text{if } \text{cnd then } p\_1 \text{ else } p\_2 $$

where $p\_1$ and $p\_2$ are assertions. Let's derive the Weakest Precondition (WP) for this scheme:

In the $\text{else}$ part, we have $u\_1 = y$ and $u\_2 = x$. From the post-condition, we derive the weakest preconditions:

$$ \text{WP}\\{u\_1=y; u\_2=x\\} (u\_1 \leq u\_2) \text{ will be } p\_2 : y \leq x $$

In the $\text{if}$ part:

$$ \text{WP}\\{u\_1=x; u\_2=y\\} (u\_1 \leq u\_2) \text{ will be } p\_1 : x \leq y $$

Now, these will be assertions in the $\text{else}$ and $\text{if}$ parts, respectively.

Consider the scheme:

$$ \text{if } \text{cnd then } p\_1 \text{ else } p\_2 $$

The WP of this scheme will be:

$$ \text{cnd} \land p\_1 \lor \lnot \text{cnd} \land p\_2, \text{ which equals } (x \< y \land x \leq y) \lor (x \geq y \land x \geq y) = (x \< y \lor x \geq y) = \text{True} $$

Since $ \text{True} \Rightarrow \text{True} $ is true, it means that the Weakest Precondition is satisfied. Our assertion in the beginning satisfies it, implying that our program is locally consistent and terminates since it's loop-free (loop-free $\Rightarrow$ termination needs more formalism). Thus, we have proved that the post-condition $u\_1 \leq u\_2$ is satisfied, and no additional constraints on the variables $x$ and $y$ are needed in the beginning.
> 0 votes

---
Tags: algorithms, logic, discrete-mathematics, hoare-logic
---


# Question
Title: "Term Rewriting and All That" - Exercise 2.3
I am working through the exercises in the book "Term Rewriting and All That" and got stuck on question 2.3. The question reads: find a reduction $\rightarrow$ on $\mathbb{N}$ such that $\rightarrow$ is decidable, but it is undecidable for some $n$ in normal form. A friend and I came up with two different solutions. But we both feel like these answers might not be correct and that there is a simpler solution that we are not seeing.

Our solutions:

> First solution: Let relation $m \rightarrow n$ be any an $n$ such that $m$ is divisible by $n$. Let the normal form be 0. This seems to work because dividing by zero is undefined. Thus, the relation is decidable until we use the normal form 0. Second solution: We transform $x$ to be a program in some way and let $y$ be the number of steps. Then we define the relation $x \rightarrow y$, in which program $x$ halts after $y$ steps. Let the normal form be any program that does not halt. This seems to work because if the program does halt, we can always check if the relation holds. If the program does not halt, it becomes undecidable.

I am not sure if I understand it enough to provide an eloquent question, but I think my confusion boils down to this: In the context of abstract reduction systems. When is a relation decidable? And if a relation is decidable, how can it then also be undecidable at the same time for specific values? Does that not make it undecidable?

# Answer
> 2 votes
I don't know what is the definition for a reduction to be decidable. I would expect it is one of the following two:

Defn 1: $\to$ is decidable iff there is an algorithm $A$ that always halts and, on input $x$, either outputs some $y$ such that $x \to y$; or, if no such $y$ exists, outputs $\bot$.

Defn 2: $\to$ is decidable if there is an algorithm $A$ that always halts and, on input $x,y$, outputs whether $x \to y$ or not.

But I would hope that the book provides a definition or some context to help specify this.

I don't know what "undecidable for some $n$ in normal form" means. I cannot reconstruct any definition that is meaningful and non-trivial. My first attempts to guess at that meaning are as follows:

Defn 3: We say $\to$ is "undecidable for some $n$ in normal form" if there exists some $n \in \mathbb{N}$ such that $n$ is in normal form (i.e., $\not\exists y . n \to y$) and there is no algorithm $A$ that always halts and, on input $n$, either outputs some $y$ such that $n \to y$; or, if no such $y$ exists, outputs $\bot$.

Defn 4: We say $\to$ is "undecidable for some $n$ in normal form" if there exists some $n \in \mathbb{N}$ such that $n$ is in normal form (i.e., $\not\exists y . n \to y$) and there is no algorithm $A$ that always halts and, on input $y$, outputs whether $n \to y$ or not.

However, neither of these seem reasonable to me. Defn 3 is trivial (there is always such an algorithm, namely, the algorithm that always outputs $\bot$, so there does not exist any relation that satisfies Defn 3). Also, Defn 4 is also trivial (there is always such an algorithm, namely, the algorithm that always outputs "yes", so there does not exist any relation that satisfies Defn 4). So I cannot figure out the intended meaning of the exercise.

Until you understand the meaning of what is to be proven, it is premature to ask whether any particular solution is valid. First, I suggest you understand what are the criteria for a proposed solution to be considered valid. That might require reading more context in the book to see what you can figure out and what definitions it presents that might be relevant.

---
Tags: reductions, undecidability, term-rewriting
---


# Question
Title: Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval
PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-odds of observing a letter inside a given positions, so the value of each cell in the matrix could be either a positive or negative float. Follows an example of a PWM.

|  | A | C | D | E | F | G | H | I | K | L |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0.426379 | -2.96691 | -1.137176 | -1.859917 | 1.523913 | -0.404392 | -1.913876 | 0.330149 | 0.065161 | 0.570567 |
| 1 | -1.104135 | -2.96691 | -1.400210 | -1.859917 | -2.012140 | -2.519869 | -2.498838 | 0.165090 | -2.567107 | 2.644822 |
| 2 | -0.186597 | -2.96691 | 1.322256 | -0.637524 | 0.753395 | 1.270208 | -1.176910 | -0.486986 | -1.429604 | 0.093245 |
| 3 | -0.750498 | -2.96691 | 1.005782 | 0.777513 | -1.164143 | 0.180571 | 0.588625 | -1.178864 | 1.177054 | -0.449897 |
| 4 | -0.186597 | -1.96691 | -0.634675 | -0.171861 | 0.189494 | -0.712514 | -0.176910 | 1.003339 | -0.496718 | 0.175707 |
| 5 | -0.573621 | -2.96691 | -1.722138 | 0.255561 | 0.250895 | -2.519869 | 1.086124 | 0.290621 | -0.982145 | 0.253710 |
| 6 | 0.369796 | -1.96691 | -2.137176 | 0.584868 | -0.012140 | -0.934906 | 0.086124 | -0.124416 | 0.783390 | -0.055618 |
| 7 | -0.229666 | -2.96691 | -3.137176 | -2.222487 | -0.427177 | -3.104831 | -1.913876 | 0.478248 | -2.304073 | 1.476102 |

This makes possible to assign a score to a string, which would be the sum of the positional weights. For example:

```
string: DDFGKKLA
score: -3,3616

```

What I was trying to achieve is the following: given a desiderable interval (defined by a `score` ± `tolerance`), I want to obtain all the possible sequences of length `l` (with `l` == `num_rows`) whose score falls inside the interval.
At a first sight it looks like a knapsack problem, despite that weights are defined inside $\mathbb{R}$ and I'm not finding a single, optimal solution.

I've got no formal CS background, so I got a bit lost when looking for similar algorithms on literature. Any idea or suggestion are very well accepted.

# Answer
You're right. It is a sort of 0-1 knapsack problem. It is NP-complete in general. So you will need to settle for approximate solutions or heuristics or algorithms that only work for short strings or make other compromises.

You probably don't want to find all such solutions, as there could be exponentially many. Perhaps you want to find one of them.

If you only care about strings of length 8, then this can be solved fast enough in practice, using a meet-in-the-middle algorithm. Specifically, enumerate all $26^4$ possibilities for the first half of the string (there are about 457,000 possibilities), and for each, compute its score. Sort them by score; call that sorted list $L$. Now, enumerate all $26^4$ possibilities for the second half of the string. For each such possibility, compute its score, check what range of scores for the first half would make the whole string acceptable, and use binary search in $L$ to check whether there is any possibility for the first half of the string whose score falls into that acceptable range. This will be efficient enough for strings of length 8, but in general its running time is exponential in the length of the string, so it will be completely infeasible for strings of length 20 (say).

Another approach is to use dynamic programming to check whether there exists any solutions and, if one exists, to find one. One thing that makes your problem more challenging is that the entries in the matrix are real numbers. So, multiply them all by a large constant $C$, and then round to the nearest integer, so that they are all integers. (You'll need to multiply the acceptable range too.) I suggest you pick $C$ to be something like $100/\text{tolerance}$. Now, the goal is to check whether there is a string whose total score falls into the acceptable range. This can solved using dynamic programming. Define $A\[i,t\]$ to be true if there exists a string of length $i$ whose total score is $t$ (using the integer entries for the matrix). Note that $A\[i,t\]$ is true iff $A\[i-1,t-s\]$ is true for some $s$ that appears in the matrix for position $i$. Therefore, you can fill in the entries of $A$ in increasing order of $i$ and increasing order of $t$. Finally, by checking the value of $A\[n,t\]$ for each $t$ in the acceptable range, where $n$ is the desired length of the string, we can check whether there is any solution whose total score is acceptable, when using the integer scores. You can also extend the dynamic programming algorithm to find such a solution if one exists. This is a pretty good approximation to your original problem.
> 3 votes

---
Tags: algorithms, dynamic-programming, matrices, knapsack-problems
---


# Question
Title: Best algorithm for sequencing reducible control flow graph
I have a reducible control flow graph with only natural loops, produced from a simple DSL. Every node keeps a list of successors and a list of predecessors. I need to make a sequence of nodes out of this CFG with following properties:

1. All predecessors of a block are located before this block, with the exception of backward edges of loops. This implies that all dominators of a block are located before this block.
2. All blocks that are part of the same loop are contiguous, i.e., there is no non-loop block between two loop blocks.

What would be the most efficient algorithm to produce such a sequence?

For illustration consider following CFG (left) with desired output (right).

CFG has been produced from a DSL which is roughly equivalent to pseudocode:

```
    for(; a && b; c++) {
        if (d) {
          dostuff1();
        } else {
          dostuff2();
        }
        dostuff3();
    }
    dostuff4();

```

Here is also CFG itself in python:

```
from collections import defaultdict

class Node:
    def __init__(self, id, name):
        self.id = id
        self.name = name
        self.succ = []

class Graph:
    def __init__(self):
        self.graph = defaultdict(Node)

    def addNode(self, node):
        self.graph[node.id] = node

    def addEdge(self, uid, vid):
        self.graph[uid].succ.append(self.graph[vid])

g = Graph()

g.addNode(Node(0, "Entry"))
g.addNode(Node(1, "For-Loop-Entry"))
g.addNode(Node(2, "Logical-And-Left"))
g.addNode(Node(3, "Logical-And-Right"))
g.addNode(Node(4, "For-Loop-Test"))
g.addNode(Node(5, "If"))
g.addNode(Node(6, "If-Consequent"))
g.addNode(Node(7, "If-Alternative"))
g.addNode(Node(8, "For-Loop-Body"))
g.addNode(Node(9, "For-Loop-Update"))
g.addNode(Node(10, "Body"))
g.addNode(Node(11, "Exit"))

g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(2, 4)
g.addEdge(3, 4)
g.addEdge(4, 5)
g.addEdge(4, 6)
g.addEdge(6, 7)
g.addEdge(6, 8)
g.addEdge(7, 9)
g.addEdge(8, 9)
g.addEdge(9, 10)
g.addEdge(10, 1)
g.addEdge(5, 11)

```

# Answer
I believe you may be looking for the dominator tree of the CFG. Some useful resources:

It could also possibly be the "reverse postorder" mentioned in the first link.
> 0 votes

---
Tags: algorithms, graphs, sorting
---


# Question
Title: How to Prepare for Informatics Olympiad and ACM-ICPC?
As a beginner to competitive programming, I want to know a few things about informatics Olympiad such as the resources and books needed to prepare for the competition. I also want to know which problems should I solve from CodeChef, HackerRank, etc because I was unable to find Olympiad problems and most of the problems are not accessible for free.

**Note**\- I have only started learning the algorithm book by CLRS but the questions do not have solutions for most of the time, so please provide the reference of the solution manual for the problems.

# Answer
> 1 votes
I believe that a good starting point is the following list compiled by Codechef: https://www.codechef.com/certification/data-structures-and-algorithms/prepare

It contains resources and problems for all relevant topics.

It's also important to participate in competitions along the way - you can check both Codeforces and Codechef for that

---
Tags: reference-request, books, programming-contest
---


title: Sorting O(log n) elements in O(n) time

text:
# Question
Title: Sorting O(log n) elements in O(n) time
I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time.

What I am getting from this is that I should find an algorithm to sort $n + O(\log n)$ numbers in $O(n)$ time. I think the first step would be to sort the $O(\log n)$ numbers in $O(n)$ time. But the only sorting algorithm I have learned that can possibly be $O(n)$ is insertion sort, and that is only in the best case when all the numbers are already sorted. The $O(\log n)$ numbers part confuses me as well since $O(\log n)$ isn't an integer as far as I know but a function.

I really don't know where to begin on this, so I'd be very grateful for any and all advice. Thank you all!

# Answer
Merging $n$ sorted numbers and $\text{log}\ n$ unsorted numbers asks you to do two things:

1. Sort the $\text{log}\ n$ unsorted numbers in $O(\text{log}\ n\ \text{log}\ \text{log}\ n)$.
2. Merge $n$ sorted numbers and $\text{log}\ n$ sorted numbers in $O(n + \text{log}\ n)$.

This yields the total time complexity of $O(n + \text{log}\ n + \text{log}\ n\ \text{log}\ \text{log}\ n)$ = $O(n)$.
> 4 votes

# Answer
If you use some primitive algorithm that sorts n items in O(n^2) then it sorts log n items in O(log^2 n), which is much faster than O(n).

Using quick sort, you can sort n items in O(n log n) and (n / log n) items n O(n). In practice, if n = 1,000,000 and log n = 20, you can merge 1,000,000 / 20 = 50,000 items in O(n), not just log n = 20.

O(n) is of course the best you can achieve if you need to insert even one item into your sorted array, because up to n existing elements need to be moved.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Read-once complexity of a matrix problem
Given a binary $n \times n$ matrix, we would like to decide whether there is a row or a column which consists entirely of $1$s. The caveat is that after we read an entry of the matrix, it is erased. How much space do we need in order to solve this task?

If entries do not get erased, the task can be solved in space $O(\log n)$ by going over the matrix twice. With this restriction, we have the following simple algorithm:

* Read the matrix row by row, maintaining the AND of all rows read so far. Return "Yes" if an all-$1$ row is ever encountered, or if the final AND contains a $1$ entry.

This algorithm uses $n + O(\log n)$ bits of space. I am counting space in number of bits, rather than number of words.

> Can this be improved?

(Question due to Yoav Ben-Dov.)

# Answer
> 5 votes
The computation of the erasing machine can be expressed as a *read-once branching program*.

A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". Each non-sink is labelled by an input variable, and has exactly two outgoing edges, labelled $0$ and $1$. Essentially, this is a compressed decision tree, and it computes a function in the same way as a decision tree. A $T$-query space-$S$ algorithm can be converted into a branching program of size $T 2^S$, and so a lower bound on the size of a branching program computing a certain function gives a lower bound on the space needed to compute the function.

A branching program is *read-once* if every execution path reads every input variable at most once. Equivalently, every source-to-sink path reads every input variable at most once (since each such path corresponds to a possible execution path). An erasing algorithm converts into a read-once branching program.

In the rest of this answer, we give a lower bound of $\Omega(2^n)$ on the size of a read-once branching program solving the task in the question. In our model, we only charge the algorithm a time unit for reading an entry, and so $T \leq n^2$. Therefore every algorithm for the task uses space at least $\log(\Omega(2^n)/n^2) = n - O(\log n)$.

The proof uses an idea due to Tal Roth.

---

Suppose we are given a read-once branching program solving the given task. Given an input $X$, its execution traces a path $v\_0 \to v\_1 \to \cdots \to v\_N$, where $v\_0$ is the source and $v\_N$ is a sink. Let $\DeclareMathOperator{\par}{par}\par(X,v\_t)$ denote the partial input which corresponds to the nodes queries on the path $v\_0 \to \cdots \to v\_t$.

In the sequel, we will consider only "No" inputs. For such inputs, some entries can be inferred even if they are not queried directly. This is the case if an entry is the only entry not queried on its row (or column), and all other entries on the same row (or column) are known to be $1$. Let $\inf(X,v\_t)$ denote $\par(X,v\_t)$ together with these inferred entries.

The partial input $\inf(X,v\_t)$ *rules out* a row (or column) if it contains a $0$ on the row (or column). Let $R(X,v\_t)$ be the set of rows rules out by $\inf(X,v\_t)$, and let $C(X,v\_t)$ be the set of columns ruled out.

The proof is driven by the following crucial observation.

**Claim.** If $X,Y$ are two "No" inputs whose execution path goes through the same node $v$, then $R(X,v) = R(Y,v)$ and $C(X,v) = C(Y,v)$.

**Proof.** Let $S\_X,S\_Y$ be the supports of $\par(X,v),\par(Y,v)$. Every path from $v$ to a sink is not allowed to query $S\_X \cup S\_Y$.

The proof is by contradiction. Suppose that $R(X,v) \not\subseteq R(Y,v)$, say $i \in R(X,v) \setminus R(Y,v)$. Let $j$ be such that $\inf(X,v)\_{i,j} = 0$. We consider several cases.

***Case 1: $(i,j) \notin S\_X$.*** In this case, $\par(X,v)\_{i,j}$ was inferred, and so, without loss of generality, all other entries on row $i$ of $\par(X,v)$ are $1$. Since $i \notin R(Y,v)$, there must be at least two entries on row $i$ not in $S\_Y$, and so some entry $(i,j') \notin S\_Y$ with $j' \neq j$. This entry is queried on the source-to-$v$ path taken by $X$, and so cannot be queried by any $v$-to-sink path.

Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. On the one hand, this is consistent with the input obtained from $\par(X,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$. This is a "Yes" input.

On the other hand, this is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ other than $(i,j')$ (which is not queried) with $1$, and all other missing entries with $0$. We claim that this is a "No" input, and so we reach a contradiction. Indeed, by construction, no row is all-$1$. If column $j''$ is all-$1$ then $\inf(Y,v)\_{i,j''} = 0$, which contradicts the assumption $i \notin R(Y,v)$.

***Case 2: $(i,j) \in S\_X$ and $(i,j) \notin S\_Y$.*** Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. This path is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$, which is a "Yes" input.

The path is also consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ other than $(i,j)$ (which is not queried) with $1$, and all other missing entries with $0$. As in Case 1, this is a "No" input, and so we reach a contradiction.

***Case 3: $(i,j) \in S\_X$ and $(i,j) \in S\_Y$.*** Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. This path is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$, which is a "Yes" input.

The path is also consistent with the input obtained from $\inf(X,v)$ by filling all missing entries on row $i$ with $1$, and all other missing entries with $0$. Since $\par(X,v)\_{i,j} = 0$, row $i$ is not all-$1$. Clearly other rows are also not all-$1$. We claim that no column is all-$1$. This is because no column in $\inf(X,v)$ can be missing exactly one entry. Hence this is a "No" input, and we reach a contradiction. $\square$

---

For a permutation $\pi \in S\_n$, let $X(\pi)$ be the input given as follows: entries $(1,\pi(1)),\dots,(n,\pi(n))$ are $0$, and all other entries are $1$. When we execute the branching program on $X(\pi)$, the partial input $\inf(X,v)$ is always a subset of $X(\pi)$, and so $C(X(\pi),v) = \pi(R(X(\pi),v))$, and in particular $|R(X(\pi),v)| = |C(X(\pi),v)|$. Furthermore, each query uncovers at most two $0$-entries in the inferred partial input. Therefore for every odd $s \leq n$, some node $v$ on the execution path of $X$ has $|R(X(\pi))| \in \\{s-1,s\\}$. Let $v\_s(\pi)$ be the first such node.

The Claim proven above shows that if $v\_s(\alpha) = v\_s(\beta)$ then $R(X(\alpha), v\_s(\alpha)) = R(X(\beta),v\_s(\beta))$ and $C(X(\alpha),v\_s(\alpha)) = C(X(\beta),v\_s(\beta))$. Denote by $R,C$ the common values. Thus $t := |R| = |C| \in \\{s-1,s\\}$, and furthermore $C = \alpha(R)$. Hence the number of permutations $\beta$ such that $v\_s(\alpha) = v\_s(\beta)$ (including $\alpha$ itself) is at most $t! (n-t)!$. It follows that the number of vertices of the form $v\_s(\alpha)$ is at least $$ \frac{n!}{\max\\{(s-1)! (n-s+1)!, s! (n-s)!\\}} = \min \left\\{ \binom{n}{s-1}, \binom{n}{s} \right\\}. $$

The Claim also shows that vertices of the form $v\_s(\alpha)$ are different for different values of $s$, and so we deduce that the total number of vertices is at least $$ \sum\_{r=0}^{\lfloor (n-1)/2 \rfloor} \min \left\\{ \binom{n}{2r}, \binom{n}{2r+1} \right\\} = \Omega(2^n). $$ Explicitly, the sum on the left equals $$ 2^{n-1} - \begin{cases} \binom{n-1}{n/2} & \text{if $n$ is even}, \\ \binom{n-1}{(n+1)/2} & \text{if $n \equiv 1 \pmod{4}$}, \\ \binom{n-1}{(n-1)/2} & \text{if $n \equiv 3 \pmod{4}$}, \end{cases} $$ showing that it is indeed $\Omega(2^n)$.

---
Tags: algorithms, complexity-theory, space-complexity, lower-bounds
---


# Question
Title: clock chip (not the CPU clock) replacement on my BEMER medical device
the 24 hour clock/timer on my BEMER PEMF device's microprocessor is keeping erratic time lately. Shortly after I reset to the correct time, it fails to keep accurate time.

I'm wondering if exposing the motherboard will allow me to easily identify and replace the clock chip? I am a newbie and have never done component level replacements, but am seeking to avoid BEMER's solution: Buy a new ($2600.00) control box with microprocessor.

# Answer
Chack battery if there is the provision to do so (as suggested by greybeard)

Check you have latest firmware.

Get a quote from third party repair technician (not always possible with medical equipment).

Pay the money to BEMER.

Attempt repair yourself – there are no youtube videos to help you.

```
If you fail, then BEMER may have to repair damage done by you plus the $2,600.

```

As pointed out by greybeard, as it’s a medical device, consider the legal liabilities if you seem to succeed and later find you haven’t.

This is a general list of some considerations for repairing equipment. I’ve answered, though stated, this isn’t really a CS question.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Small doubt concerning cardinality of set of problems and algorithms?
I write this question because my professor in Algorithm Analysis briefly mentioned some property related to the countability/uncountability of the set of strings/problems/algorithms and the consequent inability to have an "algorithm that can solve it all" which I didn't fully understand...

As I understand: A decision problem $X$ is conceived of as a set of finite binary strings $s$, which are in turn conceived of as "instances" of said problem. We say $s$ is a positive instance of $X$ iff $s \in X$. As $s$ is a finite binary string, it is simply a function $f : n \to \\{0, 1\\}$ for some ordinal $n \< \omega$. Hence, if $S\_k = \\{0, 1\\}^k$ (i.e., the set of all functions from $k$ to $\\{0, 1\\}$), then $S = \bigcup\_{k \in \mathbb{N}}S\_k$.

It is simple to show that $S$, the set of all finite binary strings, is countably infinite: Consider $f : \mathbb{N} \longrightarrow S$ such that $f(2^k + i) = i$th element of $S\_k$ and you've got yourself a nice bijection (with $k \in \mathbb{N}$ and $i = 0, \dots, 2^{k+1}-1$ —one can show that every natural $n$ can be written thus). Hence, $|S| = \aleph\_0$ (i.e., it is countably infinite).

As a decision problem $X$ is a set of strings $s \in S$, it is evident that $|P| = \mathcal{P}(\mathbb{N}) = 2^{\aleph\_0}$, where $P$ is the set of all decision problems (i.e., it is uncountably infinite).

Now here come my doubts: An algorithm $A$ for a decision problem $X$ was briefly disclosed as such that it recieves an input of $s$ a string and outputs $1$ iff $s \in X$. As such, $A$ would have to be conceived of as a function $f : S \longrightarrow \\{0, 1\\}$ and there would thus be $2^{|S|} = 2^{\aleph\_0}$ many algorithms.

However, as I understand it, an algorithm is not just any arbitrary function. It must be representable via a Turing machine, which conforms to a finite tuple of finite sets (here constants and functions being taken as sets also to make matters simpler). Clearly, there are only countably infinitely many Turing machines, hence there must also be only countably infinitely many algorithms? (Additionally, I have a bit of trouble understanding the notion of encoding a whole algorithm as a single binary string —is it just an encoding of the finite-tuple-of-finite-sets Turing machine into a single binary string/number?)

Now this is where I sort of lost my professor. Yes, if the set $\mathcal{A}$ of algorithms is countably infinite, and the set $P$ of decision problems is uncountably infinite, then there is no bijection between the two, but what does this mean exactly? That there does not exist an algorithm $A \in \mathcal{A}$ for every decision problem $X \in P$ which can verify its positive instances correctly? That is, given a decision problem $X$, there may not necessarily be an algorithm $A$ which can solve it (i.e., output $1$ iff its input is an actual positive instance of $X$)?

Any help would be much appreciated.

# Answer
The intuitive reasoning is "there are more problems than algorithms, so it cannot be the case that, for each problem, there exists an algorithm that solves it". More formally, this can be expressed as follows:

The fact that the two sets have different cardinality implies that there is no surjective map $f$ from the smaller set $A$ to the larger set $B$; In fact, let $f$ be surjective: $$\forall y \in B . \exists x \in A . x \mapsto y $$ Since $B$ is larger than $A$, by pigeonhole principle we have that for some $x \in A$: $$ \exists y\_1, y\_2 \in B . (x \mapsto y\_1) \wedge (x \mapsto y\_2) $$ Which implies that $f$ is not, in fact, a function.

So any function from $A$ to $B$ cannot be surjective. If $A$ is the set of algorithms, and $B$ is the set of problems, this means that, if we tried to map every algorithm to the decision problem it solves, there would always be at least a problem that is not the image of any algorithm, i.e. that cannot be solved by any algorithm.
> 8 votes

# Answer
Correct. There are only countably many algorithms (only countably many Turing machines). Yes, this proves that there exists at least one decision problem that cannot be decided by any algorithm (in fact, that there are infinitely many of them).

Some decision problems have an algorithm that "solve" them; some do not.
> 6 votes

# Answer
> Additionally, I have a bit of trouble understanding the notion of encoding a whole algorithm as a single binary string —is it just an encoding of the finite-tuple-of-finite-sets Turing machine into a single binary string/number?

Yes.

First of all, the word "binary" in that sentence is irrelevant. If you can encode the elements of a set as strings, then you can encode the elements of this set as binary strings. Indeed, if you have two alphabets A and B, assuming A and B each have a number of symbols which is finite and greater than or equal to 2, then it's trivial to write a conversion function that converts A strings into B strings. In fact, right now I am typing this post, which is a string in the alphabet {'A', 'B', ..., 'Z', 'a', 'b', ..., 'z', ' ', '.', ',', etc.}, and this post is going to be stored on a computer, even though it is well-known that computers just use 0 and 1 internally. So this post is going to be turned into a binary string! A combination of 0 and 1 represent A, another combination represent B, etc. It's easy to convert from the big alphabet {'A', 'B', ...} to the small alphabet {0, 1}.

Second, now that we don't need to care about binary and can use any alphabet we want, representing a Turing machine as a string can be done in many ways. We're just looking for textual encryption of Turing machines; or using another word, textual descriptions of Turing machines. You just have to find a language that can uniquely describe every Turing machine. Which comes down to listing the states, and listing the transitions, for instance by writing a list of "(state, symbol) -\> (new state)".

In fact, many programming languages have been proven to be Turing-complete, so the argument can be done using any programming language of your liking instead of Turing machines. Choose your favourite programming language. A program in this language is just a finite string of symbols, so the number of possible programs is countable. (Not all finite strings of symbols are valid programs, but the set of valid programs is a subset of the set of all finite strings of symbols, and a subset of a countable set is also at-most-countable).

For instance, brainfuck is Turing-complete. A valid program in brainfuck is a finite string of +-\>\<.,\[\] characters such that the \[\] are balanced. So the number of possible brainfuck programs is countable, which means that only a countable number of problems can be decided by brainfuck programs.
> 3 votes

---
Tags: algorithms, decision-problem
---


# Question
Title: Choose edges in fully connected weighted graph that minimize sum of weights
I was looking at the Advent of Code 2023 day 11 problem and misread it to think that the question ended up asking something akin to what's below (after transforming the positions of the "galaxies"), and I'm wondering what kind of optimization problem this is. See nearly equivalent problem, but with specified values for distance constraint.

> Given a set of $N$ points on a lattice where pairwise distance is $D\_{ij} = |(\Delta x)\_{ij}| + |(\Delta y)\_{ij}|$, select the set of distance pairs, that include at least $N-1$ of the points such that the sum of these chosen distances are minimized and that no point is in more than one of the distance pairs. I.e., in graph $G = (V,E)$, find a perfect or near-perfect matching that minimizes the sum of weights in the matching.

I heard of the vertex cover problem from Numberphile, so I googled for edge cover and got something on wikipedia, but I'm not sure if this is a case of that problem or not.

# Answer
If you just want any polynomial-time algorithm, you can solve this with a maximum weight matching algorithm.

Draw a graph with a vertex per point, and the weight on an edge $(i,j)$ is $C-D\_{ij}$. Here $C$ is a very large constant, chosen to be bigger than $N \cdot \max\_{i,j} D\_{ij}$. Now find a matching of maximum weight, e.g., with Edmonds' blossom algorithm. I claim this gives you the solution to your original problem.

By construction, this matching will contain $\lfloor N/2 \rfloor$ edges and $2 \lfloor N/2 \rfloor$ vertices. (Why? Because any matching with fewer edges will have total weight at most $(\lfloor N/2 \rfloor -1) \cdot C$, and any matching with $\lfloor N/2 \rfloor$ edges will have total weight at least $\lfloor N/2 \rfloor \cdot (C - \max\_{i,j} D\_{ij})$, and the latter is larger.)

Among matchings of such size, maximizing the sum of $C-D\_{ij}$ values is equivalent to minimizing the sum of $D\_{ij}$ values. Therefore, the maximum-weight matching minimizes the sum of $D\_{ij}$ values, among all solutions that include exactly $2 \lfloor N/2 \rfloor$ vertices.

What about the requirement that we include either $N$ or $N-1$ vertices? Well, in any matching, the number of vertices included must be even. If $N$ is even, this means that we only care about solutions that include exactly $N$ vertices. If $N$ is odd, this means we only care about solutions that include exactly $N-1$ vertices. That is equivalent to searching over the space of all solutions with exactly $2 \lfloor N/2 \rfloor$ vertices.

That proves that this algorithm solves your optimization problem.

It's possible there might be a more efficient algorithm, by taking into account the structure of the graph (specifically, that all edge weights are Manhattan distances from a set of points in 2D).
> 1 votes

---
Tags: graphs, set-cover
---


# Question
Title: Can code "run forever" if it contains no loops?
Is it possible to write a piece of code that will run forever without using a loop?

# Answer
> 2 votes
As many others have mentioned in the comments, it would depend on what you define as a loop. In any programming language with recursion, it is possible to define a theoretically non-terminating program by doing something like:

```
def f (x):
   return f(x)

f(5)

```

Which does not contain any explicit loops; (of course this practically does terminate at some point, since the system runs out of memory, but one could argue that it is not possible to define an actual infinite loop, since the computer will not be on forever :) )

On the other hand, if you consider non-well-founded recursion as "a loop", or remove the possibility to write recursive functions - or even all functions - completely, you end up with a language that is only capable to compute only the so called *primitive recursive functions*, i.e. the ones that can be computed without using while loops. With these constraints, **there is no way to define a non-terminating program!**

Note that you could still emulate "true" for loops by copy-pasting your code a bunch of times, since they have a maximum number of iterations; therefore, you don't even need for loops to compute the primitive recursive functions.

# Answer
> 0 votes
Off the top of my head it's a "no, it can't run forever."

I first imagined some Python code in my head without any loops, and I thought, "it must come to an end"

But then I saw the Halting Problem tag, and I realized this would relate to turing machines, and it would give a more definitive proof as well.

All code can be broken down into a Turing Machine. A literal loop in a Turing Machine would be exactly as you expect it.

A Turing Machine is just a directed graph, with arrows telling you which way to move the tape, and which state to go to, based on what the tape says. This directed graph should have some sort of cycle/loop in order to well cycle/loop. So by definition, a Turing Machine cannot cycle let-alone forever, without a cycle existing in the first place. i.e. A well defined turing machine cannot go forever, and must eventually halt if there is no loop present.

That is unless there is an infinite amount of unique states, imagining an infinite chain of nodes, where you start on the left, and are always moving towards to the right to the halt/finish state.

But that would likely be the equivalent to an infinite amount of unique code, which is not possible given that all programming languages have a finite amount of words, and things you're allowed to type. And we might run out of memory first.

# Answer
> 0 votes
Easily with recursion. For example the C function

```
void f() { f (); f (); }

```

will run forever, given arbitrary amounts of memory.

# Answer
> -1 votes
No, it is not possible to write a code that would "run forever" without a loop.

A program that runs forever basically means that it always has some statement to execute. In absence of all kinds of loops (while(1), for(;;), recursion, etc.), you will have to write infinite number of statements so that your program can continue running forever.

Another alternative is that you can put a pause like statement in your program and your program will stop at that pause statement but it will not exit. So, your program has not exited but it is also not doing anything. Now, it depends on you whether you consider this as a program running forever.

---
Tags: halting-problem, loops
---


# Question
Title: $N \times N$ Image Processing Time Complexity: Grayscale to Binary using Median Step Function
In an image processing system, an algorithm processes an $N \times N$ image with each pixel being a number between $0$ and $255$. It finds the median value $M$ in the $N \times N$ image and applies the binary function $f(x)$ to every pixel.

$f(x) = \begin{cases} 1 & \text{if $x ≥ M$} \\ 0 & \text{if $x \< M$} \end{cases}$

What is the time complexity of the algorithm? Is it $O(N^2)$ or $O(N^2\ log\ N)$? I think the answer is $O(N^2\ log\ N)$.

# Answer
It is $O(n^2)$.

Since there are only $256$ possible values, we can use counting sort, a non-comparison sorting algorithm, to count how often each pixel value occurs in $O(n^2)$ time and find the median in $O(1)$ time with at most $256$ steps. Then we can apply the function to each of the $n^2$ pixels in $O(n^2)$.
> 3 votes

---
Tags: algorithms, image-processing
---


# Question
Title: Proving a language is not regular using Pumping Lemma
So I am given the language *qr* where *q* is any combination of a's and b's. *r* is then the reverse of whatever *q* is. For example, abba is in the language because we can make a *q* = ab and *r* = ba

I have to prove, using the Pumping Lemma, that this language is **not** regular.

I can't make any sense of this, because it seems apparent that with *xyz*, we can set *x* = *z* = ε. Then we can just fit the entire expression into *y*. So for example, *y* = abba.

It doesn't matter how many times we repeat this, it will always be in the language.

* With 2 repetitions, abbaabba has *q* = abba and *r* = abba.
* With 3 repetitions, abbaabbaabba has *q* = abbaab *r* = baabba

This will always hold because since *r* is a repetition of *q*, the produced string by pumping will always be divisible by 2 in a way where the middle perfectly creates *q, r* | *r* = REVERSE(*q*)

What am I missing? Thank you for any help...

# Answer
> 2 votes
In the case of the pumping lemma, it is not good for intuition or practice to consider specific strings, such as $abba$. The statement of the pumping lemma says that if a language $L$ is regular, then *every single* string $w \in L$ of length at least $p$ can be written as $w = xyz$ satisfying

1. $|y| \geq 1$
2. $|xy| \leq p$
3. for **every** $n \geq 0$, $xy^nz \in L$.

So your proof should go something like this: in order to derive a contradiction, assume that $L$ *is regular*. Then let $p$ be the length given by the pumping lemma. Consider the string $s = a^pb^pb^pa^p$. Now for the important part: since $s \in L$, the pumping lemma guarantees that $s$ can be partitioned into $xyz$ satisfying the conditions above. In particular, since $|xy| \leq p$ and $|y| \> 0$, it must be that $y$ consists *only of* $a$'s. Thus, we can pump up (or down) and the string will no longer be in $L$.

This is a contradiction so our initial assumption (that $L$ was regular) must be false. Therefore $L$ is not regular.

---
Tags: regular-languages, automata, finite-automata, pumping-lemma
---


# Question
Title: What would be CFG for all strings which does not contain bbb?
Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb.

```
S -> aA | aaB | aB | bA | bbA
A -> aA| aB
A -> epsilon
B -> bA | bbA
B -> epsilon

```

Is this right?

# Answer
> 0 votes
The complement of a context-free language isn't necessarily context-free so there's no general method to produce a grammar for the complement.

# Answer
> 0 votes
Only one way to construct this CFG is that make DFA of the given problem then convert DFA to Grammar that will be a regular grammar and we know every regular grammar is CFG also \[**By Chomsky classification**\].

So following will be the production of the required grammar:

S =\> aS/bA/a/b
A =\> aA/bB/a/b
B =\> aB/bC/a
C =\> aC/bA/b

for any query in this regards feel free to contact me.

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


# Question
Title: Element that occurs more than one third of the time in a sorted array - constant time?
Given a sorted array of positive integers that is guaranteed to have some unique entry that occupies more than $1/3$ of the entries, is there an algorithm to determine this entry in $O(1)$ time?

Some remarks:

(1) If we replaced $1/3$ with $1/2$, then by checking the first, middle, and last entries of the array, we obtain such a constant time algorithm.

(2) There is a $O(\log n)$ time algorithm obtained by looking at the entries of the array whose indices cut the array into three equal pieces and then doing a binary search for each of these entries to find its first/last appearance in the array.

# Answer
> 1 votes
I think it is more difficult. If your array has 3n elements then you could have n times x and n+1 times y, and the solution is y. So even if you find x and y, you then need to prove that y occurs n+1 and not n times, and x occurs n and not n+1 times. That's probably done with binary search, taking O (log n) steps.

# Answer
> 1 votes
I was staring at this question for too long thinking "what's the catch?". But I think I got it

---

If input array contains 2 entries such that one occupies n/3 entries and the other n/3-1 - then the only way to distinguish between them would be determining *exact* borders of their intervals - and that's $O(\log n)$

same applies for all fractions below 1/2

---

fractions above 1/2 don't have the problem, since you can't fit 2 such intervals
and $n/2 - O(f(n))$ is the special case that only has limited placement possibilities, thus needing $O(\log f(n))$

# Answer
> 0 votes
No, there is no $O(1)$ time algorithm.

In the $1/2$ case, we can obtain information when the following occurs:

1. the middle element is equal to the first element
2. the middle element is equal to the last element
3. the middle element is equal to neither the first element nor the last element

In the $1/3$ case, we can obtain information when the following occurs:

1. the first third element is equal to the first element
2. the second third element is equal to the last element

But the crux is that unlike the $1/2$ case, in the $1/3$ case we can't use inclusion-exclusion principle on the information above to cover the following:

1. the first third element is equal to neither the first element nor the last element
2. the second third element is equal to neither the first element nor the last element

This leaves us with binary search to find the remaining information, which runs in $O(log\ n)$ time.

---
Tags: algorithms, arrays, constant-time
---


# Question
Title: How can I model this optimization problem?
We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, but the performance is unacceptable.

**Problem statement**

The problem is set up in two parts. First, there are fixed data:

* a set of objects `S`.
* for each object `o` in `S`, a subset of objects in `S` that are "compatible" with `o`. Being compatible is guaranteed to be symmetric. Typically, each object is compatible with 90% or more of the objects in `S`.

Then there are query-specific data:

* a non-negative weight for each `o` in `S`.
* an integer bound `m`.
* an "available" flag for each `o` in `S`. It's guaranteed that at least `m` objects are available.

The problem is to find a subset `A` of `S` such that the sum of the weights of the objects in `A` is maximized, subject to the following constraints:

* `A` contains at most `m` objects.
* all objects in `A` are available.
* all objects in `A` are compatible with one another.

If more than one such subset exists, find any one.

**Discussion**

We think we can dispense with the availability flags by setting the weights of unavailable objects to something negative. Removing an unavailable object from `A` will then always improve `A`.

We can preprocess the fixed data if that will help. (In fact, we do this for our current algorithm.) The query-specific data are not correlated from one query to the next, so no preprocessing is possible there.

Typically, the size of `S` is 800 or so, while `m` is on the order of 5-10. (The 800 might grow significantly in the future.) However, the number of available objects can be as small as `m` (although typically larger).

**Current status**

We have implemented a solution based on sorting the available objects by weight and using a greedy algorithm with backtracking to add one object at a time to `A`, removing incompatible objects from consideration at each step. A backtracking branch is pruned when no possibility of beating the current best `A` is possible. The problem is that when there are a large number of available objects, there is excessive backtracking (or, rather, not a lot of pruning). We're working on optimizing the current code, but we're also looking for a better algorithmic approach.

**Possibilities**

We've looked at several standard combinatorial problems, but we haven't found one where we can fully map our problem. We can model the compatibility data as a graph with vertices being the objects and edges connecting incompatible objects. Then our problem becomes very similar to the maximum-weight independent set problem, except that problem doesn't bound the size of the independent set. We also looked at the weighted version of the maximum coverage problem, but that doesn't provide for the compatibility data.

Could this be formulated as a constrained linear programming problem? (I'm pretty sure the answer is "yes," but how?) Would that provide the best chance for improving our implementation?

We would also be interested in approximate algorithms provided the approximation was fairly tight. From what we've read about the standard problems, what we are trying to do is pretty hard (probably NP-hard) and not amenable to approximation. But might as well ask the community....

# Answer
> 2 votes
If we ignore the upper bound $m$, this is the problem of finding a maximum weight clique in a weighted graph. Delete all unavailable objects, and create a graph, where each object is a vertex, and you draw an edge between each pair of compatible objects. Then you want a clique where the total weight of the vertices in the clique is maximized.

Consequently, the problem is NP-hard, and also hard to approximate.

A pragmatic approach would be to formulate this as an instance of integer linear programming, and apply an off-the-shelf ILP solver. Let $x\_o$ be a 0-or-1 variable, one per object, with the intended meaning that $x\_o=1$ means you include object $o$ in the set $S$. Add the constraint $\sum\_o x\_o \le m$ to ensure you select at most $m$ objects. Also add the constraint that this solution give you a clique: for each non-edge $(o,p)$ in the graph (each pair of incompatible objects), add the constraint $x\_o + x\_p \le 1$. Finally, maximize $\sum\_o \text{weight}(o) \\, x\_o$. This will automatically provide backtracking and pruning, using the logic built into the ILP solver.

---
Tags: optimization, linear-programming, constraint-programming, independent-sets
---


title: Prove that clique cover is NP Complete

text:
# Question
Title: Prove that clique cover is NP Complete
I want to use Vertex Cover as a known $NP$-complete Problem for the reduction. The claim is that if a have a vertex cover in graph $G$ with size $\le k$, I will have a clique cover in $G^\prime$ with total number of cliques $\le k$

I want to reduce vertex cover problem to clique cover problem in the following way:

1. For each edge in $G$, I will create a corresponding vertex in $G^\prime$. In the picture, each e$\_i$ in G corresponds to v$\_i$ in $G^\prime$ for $1\le i\le5$
2. Two vertices in $G^\prime$ will be connected by an edge if their corresponding two edges in G have one vertex in common. For example, there is an edge between v$\_1$ to v$\_2$ as their corresponding edges e$\_1$ and e$\_2$ have one vertex in common which is **a**.
3. Each clique in $G^\prime$ corresponds to a vertex in G and that vertex belongs to the vertex cover. For example, for the graph in picture I have vertex cover {a,c}. With vertex **a**, I get a clique {v$\_1$, v$\_2$, v$\_5$} and with vertex **c**, I get clique {v$\_3$, v$\_4$} in $G\prime$.

Now I don't know how to prove **No** instance in opposite direction: If $G^\prime$ doesn't have a clique cover with $\le k$ cliques (i.e it needs at least $k+1$ cliques), $G$ doesn't have a vertex cover size which is $\le k$.

Can anybody shed some light on this issue?

# Answer
> 0 votes
Your reduction is incorrect.

The problem is with your claim "Each clique in $G'$ corresponds to a vertex in $G$". This is false, because there could be a clique associated to two different vertices.

For example, consider a 3-clique $G = (\\{v\_1, v\_2, v\_3\\}, \\{v\_1v\_2, v\_2v\_3, v\_1v\_3\\})$. The corresponding graph $G'$ is also a 3-clique, but the 3 edges don't have a unique common vertex. In this case, $G'$ has a clique cover of size $1$, but $G$ doesn't.

---
Tags: np-complete, reductions
---


# Question
Title: Write an Algorithm that Outputs Whether a Number is a Perfect Square
Write an algorithm that takes an arbitrary natural number and returns a boolean of whether the number is a perfect square. Sketch a flowchart of the algorithm.

My approach is that a natural number $n$ is a perfect square if and only if we are able to find a natural number $i$ where $i \< n$ such that $n / i - i = 0$ and write an algorithm with this information.

# Answer
The initial approach of finding a natural number $i$ that satisfies the condition $n / i - i = 0$ may be correct, but inconvenient as we will need to handle floating point division. An alternative condition would be to use the definition of a perfect square itself, $i \cdot i = n$.

The initial approach of checking each natural number $i$ where $i \< n$ means that we need to check $n$ different numbers, yielding time complexity of $O(n)$. Can we do better, faster? We will write an example with $n = 9$ and see if we can make some observations:

$i = 1 \rightarrow 1 \cdot 1 \< 9$

$i = 2 \rightarrow 2 \cdot 2 \< 9$

$i = 3 \rightarrow 3 \cdot 3 = 9$

$i = 4 \rightarrow 4 \cdot 4 \> 9$

$i = 5 \rightarrow 5 \cdot 5 \> 9$

$i = 6 \rightarrow 6 \cdot 6 \> 9$

$i = 7 \rightarrow 7 \cdot 7 \> 9$

$i = 8 \rightarrow 8 \cdot 8 \> 9$

You might have noticed that after $i = 3$, $i$ will always be larger than the required number, meaning $i \cdot i \> n$. In fact, $i$ will always be larger than the required number when $i \cdot i \> n$, since $i$ will be larger than $\sqrt n$. We can skip those cases and replace the initial condition of $i \< n$ with $i \cdot i ≤ n$. Doing so, we will only need to check $\sqrt n$ different numbers, yielding time complexity of $O(\sqrt n)$.

But can we do even better? You might have noticed from the previous example that before $i = 3$, $i$ will always be smaller than the required number, meaning $i \cdot i \< n$. How might we make use of this monotonically increasing property? The same way you might have searched a phone book: look in the middle, see if the name you are looking for is there, or discard the first half, or discard the second half, repeat!

Through all possible $i$ between $1$ and $9$, we might check the middle $i = 5$ and find that $9 \< 5 \cdot 5$, naturally we discard the second half. Through all possible $i$ between $1$ and $5$, we might again check the middle $i = 3$ and find that $9 = 3 \cdot 3$, and conclude our binary search. Since we are repeatedly dividing the search space by half, this yields the optimal time complexity of $O(log\ n)$.
> 4 votes

# Answer
Calculate the square root of n, round to the nearest integer, and check whether the square equals n.
> 0 votes

# Answer
I can suggest a simple algorithm. The psuedocode is below.

```

for (i=1; ((i*i) < n); i++); // this for loop will exit when i*i becomes >= n
if ((i*i) == n) {
    return 1; // true
} else {
    return 0; // false
}

```
> 0 votes

---
Tags: algorithms
---


# Question
Title: I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems
How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data structures. I thinkg solving problems is fun but the begineer phase is really boring and after a year i have almost forgotten all the dsa techniques.

How to start learning it and What to focus on so you don't bored(I know this is relative depending on a person)?

I would really appreciate if anyone has some fun and interesting resources.

# Answer
I don't think this is entirely a matter of opinion like the other commentor has said (though they are right, that it can be a bit opinionated or subjective, everyone finds different things easier/harder after all!).

Personally I've competed in a lot of algorithm-based contests since I was young, I've been a math tutor for 5+ years, and I've taken educational psychology classes in university to help myself "learn how to learn."

I think there are quite a few great and important tips that everyone needs to realize and learn about this field.

If you've already got a good amount of developer experience that's great, as you'll probably already be able to visualize a lot of the data-structures. And you've probably already implemented quite a lot of trees in your time (maybe even without realizing!). And you'll write clean code!

I think I might just have a couple of tips.

Tip 1: It's not useful to cover proofs completely!

Sure, it's amazing if you could prove to me from scratch how a Suffix Array (Learn about it here) can be computed in O(N log N), but to be honest, as long as you can memorize how to code it, and you have the general instinctive understanding of how it generally works, it's better just to code it up and move on.

As you have to realize, I've met some real algorithm pros before, and over 90% of them will never memorize every single proof (there are quite literally potentially ~800 different variations of algorithms and problems that can show up in the University contests).

Of course, if you do have a great deal of understanding of the proofs behind some of them, then you'll be able to code it more easily, and probably better than tutorials online will show you. And some proofs are easy to understand.

But honestly, I'd say, when you read about a data-structure, it's less about proofs, and more just about understanding the properties of it.

An important step of the Network Flow algorithm, is that you keep finding any possible path from the source to sink for water to flow through, and then you push water down that path. That means that you can use any path-finding algorithm, to find the paths for you, whether it be dijkstra, breadth-first search, DFS. Replacing the path-finding algorithm will change the complexity, which is important to learn, but you don't need to be able to calculate this complexity on your own.

Overall if you find yourself too stuck, it's better to either --\> move to an easier variation of the algorithm/problem OR find a question where you can implement the algorithm, and just code it up and move on. Imagine it this way: It took humanity hundreds of years to come up with some of these algorithms, why would you be expected to be able to completely understand it, and recreate it from scratch in a single lesson?

The more problems you do, and the more practice you get, the better you'll be at it.

Tip 2: Don't trust all the code you see on the internet

I think there's a lot of just generally garbage code out there. Sure, there's a lot of working code out there, but is it clean? Does it have a lot of unnecessary code to it? I mean, even in my lectures at university, for Network Flow, we got shown the variation of the algorithm where you keep two copies of the same graph. One being the original, and other being the residual. But for most applications IRL and in contests for Network Flow, keeping a duplicate copy of the graph is both unnecessary, and doesn't give you a real understanding of the algorithm anyway.

Because of what I wrote in Tip 1, you'll find a lot of resources that are just clearly copy-pasted code, and don't give a real understanding of the algorithm. Or are over-engineered, or are just written uncleanly.

For the concepts and algorithms I thoroughly understand, I tend to write much cleaner, and more easily understandable code than most tutorials I've seen.

You'll find a lot of tutorials like this as well, where it feels like the person is just reading a script, and not giving you a real understanding of the concepts.

Please, for these reasons, avoid copy-pasting the code, try to walk through it step-by-step. But of course, it is going to be hard sometimes, and sometimes, if it's small enough, it's better to move on.

It only makes sense though, as when we get to this stage of Science, the topics become more and more niche, with lesser and lesser readily available resources.

Tip 3: For similar reasons above, do not learn to implement every data-structure from sratch. Instead, just learn the STD Library!

Lets say you enter a contest, and there's a very easy question where they want you to implement a priority-queue (or max-heap is it's other name). Do you need to understand the proof behind a priority-queue? Or how it's implemented from scratch?

Usually no. Both Python and C++ have an in-built priority-queue library, and you just have to learn about how to use that library. This will save you a lot of time. Similarly for a Binary Search. I would never usuaully implement a Binary Search myself (Though it's the easiest one to understand), as there's already a library for it in Python and C++.

All the contests allow these libraries, you can use them, and you will get full marks either way. So no need to reinvent the wheel.

Tip 4: Just have fun, and practice on contests.

I like code forces as it has a ranked mode, and it can be competitive. Plus you can just google resources as you're doing the contests, and not take it too seriously. Leetcode is the new popular website over the last 4 years, I don't like it as it costs money, but, if you're willing to pay for it, I think it might be better for learning.

And anyway, that's the best way to learn algorithms right, give a question a go, and if you can't do it, google for the algorithm it might be, and if you still can't do it, just look at the answers, and learn from them.

The only final thing I can tell you, is that Google is your friend. Which I'm sure you were already aware of. Never be scared to Google for what you don't know, and don't think of it as "I'm not learning it right." Any progress, even the smallest amount, is great progress, and an amazing day.

There are many online resources to learn from, including CodeForces, LeetCode, HackerRank, GeeksForGeeks, StackExchange, cp-algorithms. They are all great, so no need to be loyal to one. And all of them have their own pros and cons.
> 4 votes

# Answer
For data structures you need to learn - stack, queue, linked list, and binary search tree. These 4 should be enough for interviews. You can google them and you will know how to implement them.

There are some other data structures as well - set, multiset, map, multimap, etc. but I doubt if you will be asked to write code for them. But obviously, you may be asked questions like - what is a map?, etc. So, google these up too.

For algorithms, I would advise you to read the following book: The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman.

You can also look at the following wikipedia pages:

I am listing some common data structures and algorithms questions asked in the interviews:

* Reverse a linked list.
* Add and delete an element in a linked list.
* Add and delete an element in a sorted linked list.
* Insert and delete an element in a binary search tree.
* Implement stack using linked list.
* Implement queue using linked list.
* Convert a linked list into a tree (each node of the list has an extra pointer).
* Convert a binary search tree into a linked list also (each node of the tree has an extra pointer).
* Implement quicksort.
* Implement mergesort.
* Implement a string search algorithm.

There are many more questions and you can find them on Internet.

Lastly, write code / practice coding as much as possible because interviews and software industry is all about coding, coding, and coding.

There are many coding websites on Internet like - https://www.codechef.com/, https://www.topcoder.com/, etc.
> 2 votes

---
Tags: algorithms, data-structures, dynamic-programming, greedy-algorithms
---


title: Why is this problem not in $P$?

text:
# Question
Title: Why is this problem not in $P$?
I have been trying to figure out why this problem is supposedly not in $P$. Eager to learn where my reasoning is wrong!

**Problem:**

Given a pair of integers ($n$, $m$) in binary, does there exist $2 \leq k \leq m$ such that $k$ divides $n$?

**Reasoning:**

In order to find a potential $k$ we need to loop over all numbers from 2 to $m$, which takes a linear time. For each number we need to perform the modulo computation, which takes a constant time. Hence, in total we require a linear time to loop over all possible candidates, which is within the poly-time and hence this problem is in $P$.

# Answer
Because $n$ and $m$ are given in binary, the length of the input is $O(\log n + \log m)$. Looping from 2 to $m$ will in this case require time not linear, but exponential in the size of the input.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Complexity of insertion into a linked list, single vs double
At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says:

> In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n).

And:

> In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).

Is this not a mistake? Why would the complexity for a singly-linked list be so different from that of a doubly-linked list (specifically for insertion)? Am I missing something?

Apologies if this sounds like a naive question, but I'm learning algorithm/data structures, and sometimes complexity is very confusingly explained.

# Answer
Consider a list and let $e,f,g$ be three consecutive elements. Each element stores a value and has a "forward" pointer to the next element. Additionally, if the list is doubly linked each element also has a "backward" pointer to the previous element.

Consider a singly linked list first. If you want to delete element $f$, then you need to update the pointer of element $e$ (that previously pointed to $f$) to point to $g$. Since you don't know who $e$ is, you have to find it by using an exhaustive search from the beginning of the list. This requires time $\Theta(n)$ in the worst case. Notice that the above discussion holds even if you have a reference to $f$.

Inserting an element in a singly linked list given a reference to the element immediately preceding it can be done in time $O(1)$ (technically, saying that an insertion requires $O(n)$ time is not incorrect since $O(1) \subset O(n)$).

Let's now consider a doubly-linked list. Suppose that you want to delete $f$ and that you have a reference to it. Then you can find $e$ and $g$ in time $O(1)$ by simply following the forward and backward pointers of $f$. To perform the deletion you can update the forward pointer of $e$ to point to $g$ and the backward pointer of $g$ to point to $e$. This can also be done in constant time.

Inserting an element in a doubly linked list given a reference to the element immediately preceding or following it can be done in constant time.
> 1 votes

# Answer
"""In a doubly-linked list, the time complexity for inserting and deleting an element is O(1)."""

The above statement is not correct for all cases. I have explained it below.

I am assuming that you don't want a sorted linked list.

Then, inserting an element in both singly linked list and doubly linked list is O(1) if you insert at the head of the list.

Psuedocode is as follows (for singly linked list):

```

old_head = head;
head = new_element;
new_element->next = old_head;

```

For deletion in both singly linked list and doubly linked list, you will have to search the lists for the element that you want to delete. The time complexity of searching the element in both the lists in O(n). So, deletion in doubly linked list also requires O(n) time.

However, if you have a pointer to the element to be deleted then for doubly linked list, the time complexity is O(1) because you can directly update the previous pointer of the next element and the next pointer of the previous element and then free the desired element.

For deletion in a singly linked list (if you have a pointer to the element to be deleted), you will have to find the previous element (for updating the pointers correctly) by going through the list and hence the time complexity of deletion in a singly linked list, in this case, is O(n).
> 1 votes

# Answer
It depends on exactly what you try to do.

Inserting at the start of the list or deleting the first item is O(1). The same if you are given a pointer to one element of the list and want to insert after that item or delete the next item.

Inserting at the end of the list or before a given item, or deleting the last item or an item given by a pointer is O(n) with a single linked list and constant time otherwise. That’s because the operation requires you to find the item *before* a given item and with a single linked list you need to search starting at the beginning of the list.

And any operation that requires searching the list obviously takes O(n) time.
> 0 votes

---
Tags: algorithms, time-complexity, data-structures, linked-lists
---


# Question
Title: Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language
I'm trying to prove that the following languague is a regular language:

**$L=\\{ w \mid \lvert w \rvert$ is prime $\\}$***

What I have thought is to divide each word $w \in L$ into subwords of length 2 if the word is even and and if the word is odd end with a suffix of length 3, in this way I would get the following regular expression:

**(aa + ab + ba + bb)*** **(aaa + aba + abb + aab + baa + bab + bba + bbb + $\epsilon$)**

Is my reasoning correct?

Otherwise I would appreciate so much any help.

# Answer
> 1 votes
We are provided the language :

$$L=\\{w| |w| \text{ is prime} \\}^\*$$

Let us investigate the type of strings in $L$. We see that $L$ has such strings whose length is either zero or can be expressed as a sum of prime numbers. i.e. if $x \in L$ then we have :

$$|x| = \begin{cases} 0 \text{ or}\\ \Sigma p\_i \text{ where $p\_i$ $\in$ Set of all prime numbers}\\ \end{cases}$$

Now let us consider first the set of all strings of even length. i.e. $|x| = 2k , \text{$k \in \mathbb{N}$ and $k\geq 0$}$

So given any string of even length, we can write it as a concatenation of $0$ or more number strings of length $2$, but we see that $2$ is a prime number. So any string of even length $\in L$ and can be expressed by the regular expression : $$((a+b)(a+b))^\*$$

From the above expression, we can generate strings of length $0,2,4,...$ $\tag 1$

Let us consider the strings of odd length.

Let us consider the string of length $1$. But $1$ is not a prime number. So strings of length $1$ cannot be present in $L$. So we are left with the odd numbers $3,5,7,...$ or $$|x|= 2\lambda+1, \text{$\lambda \in \mathbb{N}$ and $\lambda\geq 1$} \tag 2$$ $$\implies |x| = 3+ (2\lambda+1 -3) = 3+ (2\lambda -2)=3+ 2(\lambda -1)$$ $$|x| = 3+2\mu \text{ , $\mu \in \mathbb{N}$ and $\mu\geq 0$}$$

Now $3$ and $2$ are prime numbers. So any odd length string of length greater than $1$ can be represented by the concatenation of a string of prime length $3$ followed by zero or more numbers of strings of prime length $2$, which can be represented by the regular expression:

$$(a+b)(a+b)(a+b)((a+b)(a+b))^\*$$

From the above two calculations we can say that L:

$$L = ((a+b)(a+b))^\*+(a+b)(a+b)(a+b)((a+b)(a+b))^\*$$

This is how we suggest that $L$ is a regular language.

Now as far as the language is concerned, we see from $(1)$ and $(2)$ we see that strings in $L$ have lengths $0,2,3,4,5,6,...$, which is simply :

$$L= \epsilon + (a+b)(a+b)(a+b)^\*$$

# Answer
> 4 votes
I let you verify that the submonoid of $(\Bbb N, +)$ generated by $2$ and $3$ is equal to ${\Bbb N} - \\{1\\}$. It follows that $$ K = \bigl\\{w \in A^\* \mid |w| = 2 \text{ or } |w| = 3\bigr\\}^\* = A^\* - A $$ Now $K \subseteq L$ and $L \cap A = \emptyset$. Thus $K = L$.

# Answer
> 3 votes
In fact this follows from a general property of the star operation. When we start with an *arbitrary* language $L$ of *all* strings of certain lengths, then the star $L^\*$ of that language is always regular. More precisely:

> Let $A\subseteq \mathbb N$, and $L = \\{w\in \Sigma^\*\mid |w|\in A\\}$. Then $L^\*$ is regular.

This is a consequence of a property of unary languages, i.e., languages over a single symbol. See this question: If $L$ is a subset of $\\{0\\}^∗$ , then how can we show that $L^∗$ is regular?

So for $\Sigma = \\{0\\}$ the statement above is true. For larger alphabets perform an alphabetic substitution (say $\Sigma = \\{a,b\\}$, then in a regular expression for $L^\*$ replace every $0$ by $(a+b)$).

# Answer
> 2 votes
You are correct. However we can simplify this a bit: $\epsilon + (a+b)^2(a+b)^\*$.

The language is all words with length $\neq 1$. Thanks to @Emil Jerabek and @Nathaniel for pointing this out in the comments! (and correcting me multiple times!)

# Answer
> 1 votes
Every integer other than 1 is the sum of primes. So it’s either 0 or \>= 2 symbols.

```
eps + (a+b)(a+b)(a+b)*

```

# Answer
> -1 votes
One way to prove this is to show that the base language $L'=\\{w∣|w|$ is prime $\\}$ is regular. If it is, you can apply the known result that the $A^\*$ of a regular language $A$ is regular.

---
Tags: formal-languages, regular-languages, context-free, pumping-lemma
---


title: Will a FIFO buffer eventually stagnate?

text:
# Question
Title: Will a FIFO buffer eventually stagnate?
Below depicts a FIFO buffer:

So the buffer is there for when the speed of data written into the FIFO buffer is faster than the data read.

But I don't understand one thing. Wouldn't eventually all the free buffers of the FIFO buffer run out after certain amount of time? Because writing speed is faster than the read speed.

And if it will stagnate, what is the purpose of using it?

# Answer
The buffer is useful if data comes in bursts. 1000 items in a second then 10 seconds nothing and repeat, while the reader reads consistently 100 items per second. Without the buffer, it would take ten seconds to process the 1000 items, then ten seconds nothing - about twice as long.

Yes, if the average write speed is larger than the average read speed then eventually the buffer will fill and you are limited to the average read speed.

Something similar happens if you write at consistent low speed, but the reader reads for one second at high speed and then is not available for ten seconds.
> 0 votes

# Answer
If data is coming continuously then if the writing speed is greater than the reading speed then obviously the buffer will become full.

However, it will not stagnate.

What will happen is that if the buffer is full then writing is stopped but reading will continue and then when some space becomes available in the buffer (because some data has been read from the buffer) then writing will resume.

So, basically, nothing is stagnating but you will lose data.

So, if writing rate is W bytes per second and reading rate is R bytes per second and if W \> R, then you will lose W - R bytes per second.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Why is the push operation in incrementally grown array stack is $O(n^2)$
This is from the Narasimha's data structure book

> For nth element (n - 1 index), if we want to push an element, create a new array of size n and copy old array to the new, and at the end assign the value of n-1 index.
>
> After n push operations the total time T(n) is proportional to 1 + 2 + 3 + 4 .... + n ≅ $O(n^2)$.

Shouldn't it be O(n), or I am missing something.

# Answer
The time for pushing in a stack of size $k$ is $O(k)$. Thus the cost of all of the pushes is:

$$\sum\_{k=1}^{n} k \ = \ \frac{n(n+1)}{2} \ = \ O(n^2) \ .$$
> 1 votes

# Answer
People have already explained that the time complexity is O(n^2). I will add something extra to this.

In real life, array storage is not incremented by the size of 1 element.

What happens is that if you have K items in the array and then when the time comes for allocation of new storage (for new elements) then the array will be grown to some N times K.

So, if N is 1.5, then the size of the new array will be N x K x Size\_of\_1\_element. This is done so that time is not wasted in allocating storage. However, it is quite possible that all the allocated storage may not be used. So, its a space vs time tradeoff. However, it had been decided by computer language inventors that wasting some storage is better than wasting time in frequent allocation of storage.

In Java language, N is 1.5 but other languages may have different values of N.
> 0 votes

---
Tags: data-structures, algorithm-analysis, stacks
---


# Question
Title: Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as minimal average cost cycles, but use Bellman-Ford to discover a minimal cycle and augment along the discovered cycle. Let $V$ be the number of nodes in the graph, $A$ the number of edges, $U$ the maximal capacity of an edge in the graph, and $W$ the maximal costs of an edge in the graph. Then, my learning materials claim:

* The maximal costs at the beginning can be no more than $AUW$
* The augmentation along one negative cycle reduces the costs by at least one unit
* The lower bound for the minimal costs is 0, because we don't allow negative costs
* Each negative cycle can be found in $O(VA)$

And they follow from it that the algorithm's complexity is $O(V^2AUW)$. I understand the logic behind each of the claims, but think that the complexity is different. Specifically, the maximal number of augmentations is given by one unit of flow per augmentation, taking the costs from $AUW$ to zero, giving us a maximum of $AUW$ augmentations. We need to discover a negative cycle for each, so we multiply the maximal number of augmentations by the time needed to discover a cycle ($VA$) and arrive at $O(A^2VUW)$ for the algorithm.

Could this be an error in the learning materials (this is a text provided by the professor, not a student's notes from the course), or is my logic wrong?

# Answer
You are correct, using the claims found in the book, we can obtain the time complexity by finding that $O(AUW) \times O(VA) = O(A^2VUW)$.

But, a time complexity of $O(V^2AUW)$ could be considered when we look at the SPFA algorithm to find a negative cycle in $O(E) = O(V^2)$ time on *average*, yielding a time complexity of $O(AUW) \times O(V^2) = O(V^2AUW)$.
> 0 votes

# Answer
According to TopCoder the correct running time is $O( A^2 \cdot VUW)$.
> -1 votes

---
Tags: algorithms, graphs, algorithm-analysis, runtime-analysis, network-flow
---


# Question
Title: Is it possible that an AI bot behave as a human being in the long term?
Is it possible that an AI bot behave as a human being in the long term?

I would like to know what people think but according to me it is not possible.

One example is - Many times humans know what is the right thing to do but they don't feel like doing it. In humans, there is a tussle between heart and mind many times. Can an AI bot mimic this?

Something like - If a human knows that some food is not good for him/her but the food is very tasty then sometimes that person will not eat that food (mind overpowers the heart) and sometimes that person will eat that food (heart overpowers the mind). Can an AI bot mimic this behavior?

We all know that smoking is bad for health but still many people smoke. So, can an AI bot be able to mimic these kinds of behaviors?

By the way, I am not talking about fighting behaviors of humans.

# Answer
You're raising a critical question about the future of AI: whether it can genuinely mimic human behavior, not just in its actions but also in its internal decision-making processes. It's a complex topic with no easy answers, and there are strong arguments on both sides.

**Arguments for AI mimicking human behavior:**

* Advanced AI models: With rapid advancements in machine learning and artificial general intelligence (AGI), some experts believe it's only time before AI can replicate the complexities of human decision-making. These models could incorporate factors like emotions, biases, and even subconscious desires to mimic our internal struggles.
* Data abundance: AI thrives on data, and as we generate more data about human behavior, including emotional responses and decision-making processes, AI models could potentially learn to process and even predict such behaviors.
* Evolutionary advantage: Mimicking human behavior could benefit AI in various contexts. For example, an AI assistant that understands your emotional state might tailor its responses accordingly, leading to better interactions.

**Arguments against AI mimicking human behavior:**

* Different nature: Humans are biological beings with a unique evolutionary history and embodiment. Replicating our emotional and psychological processes in a purely computational system might be difficult.
* Unforeseen consequences: Mimicking human emotions and biases could lead to unintended consequences. An AI with internal conflicts like ours might exhibit unpredictable and potentially harmful behavior.
* Focus on ethical AI: Instead of replicating potentially problematic aspects of human behavior, AI may develop its own ethical framework and decision-making processes.

Ultimately, the answer to your question likely lies somewhere in the middle. AI might develop sophisticated models of human behavior and even predict our choices with high accuracy. However, fully replicating the internal emotional and psychological struggles that lead to those choices might be a different story.

The conversation about AI mimicking human behavior should be open and focused on ethical considerations. While it's fascinating to imagine AI assistants who understand our emotions and cater to our needs, ensuring such developments happen within a safe and responsible framework is crucial.

Furthermore, it's worth questioning whether mimicking human behavior is even desirable. Perhaps AI should focus on its strengths and develop unique ways of processing information and making decisions, potentially surpassing the limitations of our often-conflicted internal struggles.

Remember, the future of AI is still unwritten, and our choices in developing and interacting with these technologies will shape its impact on humanity.
> 2 votes

---
Tags: artificial-intelligence
---


title: Why is CNF-Equivalence coNP?

text:
# Question
Title: Why is CNF-Equivalence coNP?
I have been struggling with the understanding of why this problem is in coNP.

**Problem:**

CNF-Equivalence, denoted as C, takes as input a pair of CNF formulas ($\phi, \sigma$) both are defined over the same set of $n$ variables $x = (x\_{1}, x\_{2}, ... x\_{n})$. The goal is to decide whether these two formulas are *equivalent*, which means they compute the same output for every $x$. Is this problem in P, NP or coNP?

**Reasoning:**

Deciding whether this problem is in NP or coNP. In order to verify the equivalence I have a verifier $V$ which takes as input a certificate $c$ which in our case is an assignment of $x$. The verifier will then run the assignment on both formulas $\phi$ and $\sigma$ and compare the outputs.

*Equivalence:*

In this case we need to check for all certificates for a given $x$

*Non-Equivalence:*

In this case we will be checking for certificates until we find one for which the output is different.

Maybe I got the certificate system wrong, but with such system in place both of the problems seem equally hard to me ...

# Answer
> Non-Equivalence:
>
> In this case we will be checking for certificates until we find one for which the output is different.

To show that the formulas are not equivalent, it suffices to show just a single certificate $c$ for which $\phi(X\vert c)\neq\sigma(X\vert c)$. Clearly, checking a single certificate is possible in polynomial time.

On the other hand, it does not seem that there always is some short single certificate to show equivalence, because you'd need to show it for exponentially many possible assignments.
> 5 votes

# Answer
The question is about CNF-equivalence. This answer, however, chiefly is about CNF-not-equivalence, the complement problem of CNF equivalence. Two formulas $(\phi, \sigma)$ are not-equivalent if they differ on at least one assignment (i.e. if they are not equivalent). In this answer, we will see that CNF-not-equivalence is NP-complete (i.e. in NP and NP-hard). Therefore, we will know that CNF-equivalence is co-NP-complete.

So, the rest of this answer focuses on CNF-not-equivalence. We know that SAT is in NP (even NP-complete). We reduce from it to CNF-not-equivalence, and reduce back:

## Reducing CNF-not-equivalence to SAT:

Given two formulas $(\phi, \sigma)$, construct the formula $\neg (\phi \iff \sigma)$ as a CNF, using the reduction from SAT for arbitrary formulas to CNF-SAT, also known as the Tseytin transformation. If this formula is SAT, then we found a counterexample and thus the input formulas are not equivalent.

## Reducing SAT to CNF-not-equivalence (for NP-hardness):

Given a formula $\sigma$, we compare it to the always-false formula. We then know that $\sigma$ is satisfiable precisely when it is not equal to $\bot$.

---

Thus CNF-not-equivalence is in NP, since it is solvable by SAT. The backward direction establishes it is NP-hard, thus it even is NP-complete.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Good books about the history of computer science and its pioneers?
I have read a book ‘Men of Mathematics’ by Eric Temple Bell, which includes the development of mathematics through ages and the biography of famous mathematicians . I am looking for such an history oriented book about computer science and the computer scientists. Can anyone suggeste me any such books and I am unable to find any proper book through google. Thank you

# Answer
> 2 votes
Disclaimer: I haven't read that book.

I don't think it's quite the book you're after, but Herman Goldstine's *The Computer from Pascal to Von Neumann* might be a good start. It's specifically about computing *machinery* rather than computer *science*, but talks about many of the main players such as Charles Babbage, George Boole, Herman Hollerith, Vannevar Bush, etc.

It stops the story around EDVAC, which is just at the point where software started getting interesting.

---
Tags: history, books
---


# Question
Title: Why when calculating how long it would take to read a file from a harddrive do I not use transfer speed per sector?
I'm working on a problem from my textbook (not homework, just an example), and it asks us to calculate the 'best case' scenario of reading a 1MB file from the hard drive.

I don't know why the right way to calculate the total time involves the max time for a single rotation. Also in the answer they said that a 1MB file would have 10,000 512-byte logical blocks, how is that calculated? Wouldn't a sector have 512-bytes, so wouldn't the file take 1954 512-byte sectors?

This link has a similar question (almost identical), and yet the 1MB file in their example uses 2000 logical blocks.

I suppose my question boils down to, how are the amount of logical blocks determined? And furthermore, what's wrong with my assumptions/calculations?

Here's the information that it gave me:

| Parameter | Value |
| --- | --- |
| Rotational Rate | 13,000RPM |
| TAvgSeek | 6ms |
| Avg # Sectors/track | 5,000 |
| Surfaces | 4 |
| Sector Size | 512-bytes |

# Here's What I Did:

Here's what my thought process was, first calculate the average time it takes to find the first sector of the file in the track:

`Tavg-rotation = (1/2) * 60s/13,000RPM * 1,000ms/sec`
`Tavg-rotation = 2.30ms`

Next, I found the time to transfer a single sector:
`Ttrans = 60s/13,000RPM * (1 Track/5000 sector) * 1,000ms/sec`
`Ttrans = 0.00092308 ms`

And then finally I added the time for the spindle to find the track, plus the time to find the first sector of the file, plus the time it takes to read all the sectors in the file:
`Ttotal = Tseek + Tavg-rotation + Ttrans*1MB*(1sector/512bytes)`
`Ttotal = 6ms + 2.30ms + 1.80ms`
`Ttotal = 10.10ms`
This is apparently the wrong answer...

# Here's What the Textbook Did:

> This is a good check of your understanding of the factors that affect disk performance. First we need to determine a few basic properties of the file and the disk. The file consists of 10,000 512-byte logical blocks. For the disk, Tavg seek = 6 ms, Tmax rotation = 4.61 ms, and Tavg rotation = 2.30 ms.
>
> > A. Best case:
> > In the optimal case, the blocks are mapped to contiguous sectors, on the same cylinder, that can be read one after the other without moving the head. Once the head is positioned over the first sector it takes two \>\>full rotations (5,000 sectors per rotation) of the disk to read all 10,000 \>\>blocks.
> > So the total time to read the file is Tavg seek + Tavg rotation + 2 × \>\>Tmax rotation = 6 + 2.30 + 9.22 = 17.52 ms.
>
> *Computer Systems, A Programmer's Perspective 3ed*, pg 631, pg697
> Briant & O'Hallaron

I hope I provided enough information!

# Answer
For some reason they say the file has 10,000 sectors instead of 2,000 which may explain the difference.

They also forget that the file is most likely stored over three tracks so you need to add a bit of time twice to get to the next track.
> 1 votes

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


# Question
Title: How to check whether a given language is decidable when the definition contains some predetermined machine
> Let $L = \\{\langle M, W \rangle \mid M $ is a Turing machine, w is a string and some Turing Machine $M\_1$ exists such that w does not belong to $L(M) \cap L(M\_1)\\}$

I am unsure of how to deal with the TM $M\_1$. One idea I had was to let $L(M\_1) = \phi$ such that $L(M) \cap \phi = \phi$. So when we simulate $w$ on $M$ we can immediately accept without reading any input at all since all languages belong to the complement of $\phi$.

Hence from this we can prove that $L$ is decidable since we are always accepting the string regardless of what we input. However I am concerened about the correctness and validity of such a proof. Can someone explain whether the proof is correct if what changes I would need to make to make it make sense?

# Answer
> 2 votes
The machine $M\_1$ is not a predetermined machine, but we rather find that $M\_1$ is within the scope of an existential quantor. As you have observed, for all $w$ and $M$ there is some $M\_1$ such that $w \notin L(M) \cap L(M\_1)$, namely some $M\_1$ which always answers "no".

Thus, we can simplify the definition of $L$ to:

$$L = \\{\langle M,w\rangle \mid M \text{ is a Turing machine } \wedge w \in \Sigma^\*\\}$$

As long as our coding of Turing machines is sensible, this shows that $L$ is decidable.

A criticism on your writeup: We never run $M$ on $w$, because there is no point in doing so.

---
Tags: turing-machines, automata
---


# Question
Title: Intersection of a regular and a non-regular language can give a non-regular language?
Determine two languages L and L1 on the alphabet {a,b} with regular L, L∩L1 is non-regular and L1 does not contain L.

I came up with this solution: L = { w | w ends with the string aba} L1 = {w | w = w^r (palindrome) }

**L∩L1 = {w | w ends with the string aba AND w is palindrome}**

I don't know if this is correct as a solution, perhaps you also have simpler examples? Thank you.

# Answer
It’s very easy really.

Take any non-regular language L1, and then the regular language of all strings (a | b)\*. The intersection is L1.

If you want neither language to be a subset of the other, take a short string S in the non-regular language and use the regular language “all strings other than S”.
> 0 votes

---
Tags: regular-languages, finite-automata
---