# Question
Title: Interview Question with Arrays and Consecutive Subintervals
I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..

The question is:

> "An array of $n$ integers is correctly positioned with respect to an integer $k$ if for any $k$ consecutive indices in the array, there does not exist values at two indices, $x$ and $y$ such that $x \geq 2$ * $y$ (where $x$ and $y$ are values at 2 indices of the array in a subarray of size $k$). What is an $O(n \log k)$ algorithm to determine if an array is correctly positioned?"

For example: $\[5, 6, 7, 4, 5, 9\]$ is not correctly positioned if $k = 4$ since in in the interval $\[7, 4, 5, 9\]$ we have that $9 \geq 4 * 2$.

My thought is to check all potential subintervals like $\[0..k\]$, $\[1..k+1\]$, $\[2,..k+2\]$ using a min-heap but I really can't think that would satisfy the time constraint since it's resulting in building far too many heaps.

Does anyone know how to approach this problem, or have a solution for it?

Having trouble figuring out how to keep track of this sliding window using heaps, and thinking maybe I have to use a min-heap and max-heap? And compare the max to the min for every subinterval using insertions and deletions?

# Answer
Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$.

The trick is done using a monotonic double-ended queue, one where all the elements are either in descending or ascending order. Furthermore, for each element we keep track of the index we encountered it, so we can invalidate it from the queue.

Suppose that we iterate over elements in a stream, and wish to maintain the *minimum* value (the maximum is analogous). Let's call the current value $x$ and the current index $i$. We first initialize an empty double-ended queue $Q$ and start iterating:

1. Remove all elements from the queue that would be made irrelevant by $x$. Since we know our queue is in ascending order, this is very simple, we keep removing elements from the back that are bigger than $x$. They are now irrelevant for the window, as $x$ is newer and smaller.

```
while not empty(Q) and peek_back(Q).value > x:
    pop_back(Q)

```
2. Add $x$ to the back of the queue, but keep track of its index as well.

```
push_back(Q, value=x, index=i)

```
3. Invalidate old items in the queue. We only have to do this if the item is in the front of the queue, otherwise its harmless (this lazy removal is what allows us to keep $O(1)$ time).

```
while peek_front(Q).index <= i - window_size:
    pop_front(Q)

```
4. Now `peek_front(Q)` contains the smallest element in our window, so we can use it and then keep iterating.

Note that steps #2 and #4 are $O(1)$ time, and steps #1 and #3 are $O(r)$ time where $r$ is the number of removed elements from the queue. However since each element is only added once to the queue, the $O(r)$ steps must be amortized $O(1)$.
> 7 votes

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


# Question
Title: Representing a sentence using propositional logic
I am confused regarding a propositional logic representation of a sentence.

Please note that this sentence is not realistic:

"A person who is male (M) is smart (S) if he is tall (T), but otherwise is not smart."

Which of the following propositional logic formulas correctly represents the above:

(a) $(M \wedge S) \iff T$

(b) $M \Rightarrow (S \iff T)$

Note that $\Rightarrow$ and $\iff$ represents "only if/implies" and "iff and only if," respectively.

The solution to the problem is (b)

The solution claims that (a) is NOT an option because it asserts, among other things, that all tall people are male, which is not what is asserted. This makes sense to me, I think (not confident, but this is not the main point of this post).

The solution claims that (b) IS a correct representation because it is saying that if a person is male, then they are smart IF AND ONLY IF they are tall. I don't understand that, and based on my current understanding, I don't agree with this because the "IFF" part is saying that if the person is tall, then they are smart, and that is not what the problem statement said. The problem statement only states that a person who is male is smart if he is tall.

So I feel like (b) is not correct, but if you swap out the $\iff$ for $\Rightarrow$ then it becomes correct.

Am I misunderstanding something here?

# Answer
> 1 votes
The sentence says that a male "is smart (S) if he is tall (S)", that gives $T \Rightarrow S$, but it also says "but otherwise is not smart", which gives $\neg T \Rightarrow \neg S$, and this is equivalent to $S \Rightarrow T$ by contraposition. Thus together this gives $S \iff T$ under the condition $M$. Therefore (b) is correct.

---
Tags: logic, propositional-logic
---


# Question
Title: Computing the minimum distance between each pain of points
I am trying to read an algorithm for computing minimum distance between each pair of points from the book: Algorithm Design

Algorithm Design

It considers the points in a line. If the points are in a line why we need to sort them? We can start from the beginning and compute the distances from starting pint to all the points on the right.

Some body please guide me why we need sorting?

# Answer
Suppose the points are $\[4,1,10,11\]$. The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points.

In this problem, the input is an array containing numbers, not in sorted order.
> 1 votes

---
Tags: euclidean-distance, minimax
---


# Question
Title: How come correctness proofs aren't tautological?
Consider the following function on binary trees, which is supposed to tell whether a given `int` is a member of a binary tree `t`:

```
type tree = Leaf | Node of int * tree * tree;;

let rec tmember (t:tree) (x:int) : bool =
  match t with
      Leaf -> false
    | Node (j,left,right) -> j = x || tmember left x || tmember right x
;;

```

If one wants to prove that this function is correct, one would need to *define* first what tree membership actually means, but then I can find no formal way of doing this except for saying that `x` is a member of `t` if and only if it is either equal to the root of `t`, or it is a member of the left or right subtree of `t`. This is essentially saying that `x` is a member of `t` if and only if `tmember t x` outputs `true`.

What am I missing here?

# Answer
Membership is much more general than this recursive definition you give. At a higher level you could define membership as follows:

> A *tree* can be defined as a collection of nodes, $V$, and edges $E$ where those edges and nodes satisfy particular constraints.
>
> We say a value $x$ is a *member of the tree* if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.

You then *prove* (probably with induction since it's recursive) that your function is equivalent to this definition. That is to say, your function returns true on value $x$ if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.
> 0 votes

---
Tags: logic, correctness-proof
---


title: practise resources for basic sorting

text:
# Question
Title: practise resources for basic sorting
I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms **insertion sort, bubble sort and selection sort** a little.

Last year they had to sort an array with n elements and the elements were integers with values between 0 and m-1 and the complexity had to be of O(n+m).

I did not find any good resources as most of them **deal with more advanced topics** and prepare you for interviews.

So I would be glad if someone could give me a good hint.

# Answer
> 1 votes
What do you mean by "practice sorting"? Sets of data to sort by hand? Just whip something up with a random number generator. Examples showing how the methods work? At least Wikipedia has detailed algorithms with pretty animations, or search for "algorithm animation", it is quite popular.

---
Tags: algorithms, sorting
---


title: Quadratic Probing Infinite Loop?

text:
# Question
Title: Quadratic Probing Infinite Loop?
I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element?

According to https://en.wikipedia.org/wiki/Quadratic\_probing:

> In the case of quadratic probing, with the exception of the triangular number case for a power-of-two-sized hash table\[2\], there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime.

Does this mean that Load Factor should always be 0.5 for a Hash Table that uses Quadratic Probing?

What is the proof of this claim?

# Answer
No. It means you should count how many slots you have checked, and if you have checked more than the available number of slots, you resize the table.

In practice, if you regularly visit more than ten slots, then either the hash function is bad (nothing you can do about it while your program is running), or your load factor is too large. Not finding an empty slot will only happen if an attacker can decide your hash values.
> 2 votes

# Answer
With quadratic probing (assuming table size is a prime) you'll check exactly half the entries for an alternative empty slot (only half of the numbers are squares modulo $p$). In practice, you'll resize the table long, long before you reach such lengths of searches.

For any probing sequence, it should only repeat in a full cycle (like linear probing --full array checked-- or quadratic probing --exactly half of the entries checked before repeating) you *must* check if you ended up at the starting point (and won't find an empty slot).
> 1 votes

---
Tags: algorithms, hash-tables
---


title: Pseudocode for a searching tree

text:
# Question
Title: Pseudocode for a searching tree
I want to describe my search tree in an algorithm and describe how each level of the tree is created. But I cannot find good examples to help me express how to write it in an elegant way. Please if anyone can recommend a good resource for describing a search tree in detail in a pseudo code.

# Answer
> 1 votes
Probably the best way to explain how such an algorithm works is via diagrams showing it step by step for some examples, examples selected to exercise your code more or less fully (need not cover all left/right symmetric cases, for example).

If you use LaTeX, look for a package to typeset algorithms, like `algorithm2e`, and check out Ti*k*Z and it's facilities to draw trees. It's documentation is quite forbidding, search for tutorials or targeted explanations.

Place yourself in the shoes of your gentle reader: What would you like to see? What points of the algorithm are thorny? Any corner cases that need explaining? Any strange/surprising/seemingly useless lines?

---
Tags: algorithms
---


# Question
Title: "Searching and sorting" algorithm to find the natural logarithim of a number?
Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm not allowed to use strategies that involve integration, bit manipulation, approximation formulas, or Taylor Series. Instead, we're asked to generate an array of values where at least one of them will be the answer, and then to find the correct value in that array. There must be some kind of established algorithm for this, but this and other resources haven't been helpful. I'm stuck. What should I be thinking about here?

# Answer
Suppose you have an array $A = \[e^0, e^1, e^2, \dots\]$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $x$.

1. You find this value at position $n$. What is the value of $A\[n\]$?
2. What can you say about $\ln(x)$ in relation to $n$?
3. Can you find the correct $n$ quickly? Does it help that $A$ is sorted?
> 4 votes

---
Tags: algorithms, sorting, algorithm-design
---


# Question
Title: What does "fast-forwarding" mean in the context of CPU simulation?
I'm using a simulator for my thesis and I've come across the term "Fast-forwarding" but I have found no definition anywhere in the documentation or online. From a pdf I've been reading about the simulator I am using (gem5), I've come across this section:

> The gem5 simulator supports four different CPU models: AtomicSimple, TimingSimple, InOrder, and O3. AtomicSimple and TimingSimple are non-pipelined CPU models that attempt to fetch, decode, execute and commit a single instruction on every cycle. The AtomicSimple CPU is a minimal, single IPC CPU which completes all memory accesses immediately. This low overhead makes AtomicSimple a good choice for simulation tasks such as **fast-forwarding**. Correspondingly, the TimingSimple CPU also only allows one outstanding memory request at a time, but the CPU does model the timing of memory accesses.

Does anyone know what this term actually means?

# Answer
> 6 votes
Fast forwarding is used to warm-up microarchitectural state (caches, branch predictors, etc.) in preparation for more accurate simulation of a particular section of interest within an application. Since microarchitectural state can depend on operation ordering (e.g., cache replacement for data accesses and interactions between threads), speculation (e.g., instruction caching behavior), and even timing (e.g., thermal behavior), this is not a *perfectly* accurate warm-up, but "all models are wrong".

# Answer
> 5 votes
Here I will complement the perfectly correct information that Paul gave with more gem5 specifics.

One major use case for fast-forwarding is when you have to boot Linux/Android and only then run your content.

The boot could take a very long time compared to your content, and so it is very important to find a way to not run it for every experiment, since you usually need to run several versions of an executable with several different input parameters.

Checkpoint restore also works on gem5's syscall emulation. I had never used it in that case, since there is no boot to skip, but some people have to skip initialization outside of the region of interest.

The solution is to first run content on a less detailed CPU (e.g. the default `AtomicSimpleCPU`) and then just before you start running the executable, you switch to a more detailed CPU, e.g. `DerivO3CPU`, which is about 5x slower to execute.

gem5 fs.py provides two ways to do this:

* `--fast-forward <time>` option: runs up to a given time cycles on the first (faster) CPU then switches and continues simulation
* `-r` \+ `m5 checkpoint`: you instrument the guest, run boot with the fast CPU, take a checkpoint from instrumentation after `init`, and then restore after boot with the slower CPU

Both of those very likely use the exact same internal implementation, except that the checkpoint method has to serialize and serialize state to/from disk.

Of the two approaches, checkpoint restore is much more convenient because:

* you can restore multiple times with different parameters without re-running the boot on the fast CPU
* it is hard to know the right clock time to switch in the first place

Syscall emulation can actually be seen as an alternative fastforwarding approach, as it always dispenses boot, and I've measured a runtime gain of about 2x speed for it at one point with Dhrystone, the downside being that the system is less representative and you have to implement any possibly missing syscalls yourself: https://stackoverflow.com/questions/48986597/when-to-use-full-system-fs-vs-syscall-emulation-se-with-userland-programs-in-gem

For the actual details of which hardware parameters can be modified or not across a restore see: https://stackoverflow.com/questions/60876259/which-system-characteristics-such-as-number-of-cores-of-cache-configurations-can/60876260#60876260

One question that then comes up, is: how can I set different parameters to the program after each restore, if the checkpoint restore restore memory state exactly to what it was? This tutorial covers several possibilities: https://cirosantilli.com/linux-kernel-module-cheat/#gem5-restore-new-script

The information above valid as of gem5 2235168b72537535d74c645a70a85479801e0651, February 2020.

---
Tags: terminology, computer-architecture, simulation
---


# Question
Title: What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$
What is the time complexity of

$$\sum\_{i=1}^n 1+\lfloor\log\_2 i\rfloor$$

and how do you calculate it?

# Answer
> 4 votes
We can split the sum:

$$S \\;=\\; \sum\_{i=1}^n \left(1 + \lfloor \log\_2 i \rfloor\right) \\;=\\; \sum\_{i=1}^{n/2} \left(1 + \lfloor \log\_2 i \rfloor\right) + \sum\_{i=n/2}^{n} \left(1 + \lfloor \log\_2 i \rfloor\right)$$

Then as a lower bound it is allowed to drop the first sum and only look at the second sum. Furthermore, we are allowed to replace $i$ in the loop body with just $n/2$, as $i \geq n/2$ in the second sum.

$$S \\;\geq\\; \sum\_{i=n/2}^{n} \left(1 + \lfloor \log\_2 n/2 \rfloor\right) \\;\geq\\; (n/2)\cdot\lfloor \log\_2 n/2 \rfloor$$

$$S \\;\geq\\; (n/2)\cdot(\log\_2 n - \log\_2 2 - 1) \\;\geq\\; \frac{1}{2}n\log\_2 n - n $$

$$S \in \Omega(n \log n)$$

As an upper bound we can replace $i$ in every term by $n$ and similarly to above we get:

$$S \\;\geq\\; n(1 + \log\_2 n)$$

$$S \in O(n \log n)$$

Therefore we can conclude that asymptotically $S \in \Theta(n \log n)$.

---
Tags: time-complexity
---


# Question
Title: Sorting array of strings (with repetitions) according to a given ordering
We get two arrays:

```
ordering = ["one", "two", "three"]

```

and

```
input = ["zero", "one", "two", "two", "three", "three", "three", "four"];

```

We want to find the array `output` so that

```
output = ["one", "two", "two", "three", "three", "three", "zero", "four"]
// or
output = ["one", "two", "two", "three", "three", "three", "four", "zero"]

```

The strings (with possible repetitions) should be sorted as in the `ordering` array. Not found/contained strings should be put at the end of the new array and their order doesn't matter.

The $n^{2}$ solution is obvious, can we do better? The memory doesn't matter and it doesn't have to be an in-place algorithm.

# Answer
The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings.

Here are 2 different methods with their specific running times. The first of which is a brief description of the method in the other answers with specific analysis of the running time. The second of which has better running time and is almost optimal.

Let us call the first (ordered) list in the input $A$ and the second (to be ordered) $S$. Let $n$ be the size of $A$ and $m$ the size of $S$. Let $l$ be the maximum length of a string in the input.

**The first method.** This span the methods in the other answers. Note that in both we need to find for each string the whether it lays in the original ordered array and if so at what position exactly. We need either apply a linear search which will cost something like $O(ml)$ per element or we can build some kind of a dictionary data-structure such as search trees and hashing tables or a "trie" (prefix-tree) data structure to achieve each look-up operation in linear time in the size of the strings. Using this we can achieve a running time of $O((m+n)l)$ for finding the positions over all strings. Afterwards we need to sort all strings in $O(n \log n)$ if we assign the indices directly to the strings (using pairs) or $O(l n \log n)$ by applying the look-ups while searching. So the best running time we can achieve using the methods in the other answers would be $O(l (n+m) + n \log n)$.

---

**The second method.** Note that we did not make use of the original sorted array and that is why we had to sort the strings again. We can solve the problem more efficiently by using this extra informaiton. To achieve this, let us bild a dictionary $D$ (for the sake of the theoretical bounds let us define it as a trie but in you can implement it as a hash-table as well). Let us define a new list $L$ (a linked list) and a function $C$ that counts how many times each string appeared in the first array. Assume $D$ assigns to each string a distinct number from $1$ to $m$ and $C$ is an array of length $m$. The algorithm goes as follow:

```
For all i in {1, .., m}
 Set C[i] := 0
// Now build D
Set index := 0
For each string s in A do
 Set D[s] = index
 Increase index by one
// Now find how many times each string occurs
Let L be an empty list
For each string s in S do
 If s in D then
  Find index = D[s]
  Increase C[index] by one
 Else
  Append s to L
//Now output
For each string s in S do
 Find index := D[s]
 Find c := C[index]
 while c > 0
  output s
  decrease c by one
For s in L
 output s

```

This algorithm runs in $O(l(n+m)$ which is linear (optimal) if the lengths of the strings are bounded by a constant.
> 4 votes

# Answer
Assuming the length of both arrays in your question is $\mathcal{O}(n)$, then in terms of required string comparisons:

Create an array of the form `inverse = [("one", 1), ("two", 2), ("three", 3)]` where the additional indices are the array indices and sort it lexicographically on the first pair elements. This can be done in $\mathcal{O}(n \ln n)$ string comparisons with common sorting algorithms.

Then, define a lookup of a string in `inverse` as lexicographical binary search on the first pair element and returning the corresponding second element, or the length of the array plus 1 if the string isn't found. This takes $\mathcal{O}(\ln n)$ string comparisons per lookup.

Then, for each element in `output` lookup the corresponding index from `inverse` as described above, taking $\mathcal{O}(n\ln n)$ string comparisons.

The resulting array can be sorted by any common sorting algorithm, which can be done in $\mathcal{O}(n \ln n)$ integer comparisons.

Afterwards transform the indices back to the strings by directly indexing into `ordering`. This takes $\mathcal{O}(n)$.

This algorithm will then be dominated by $\mathcal{O}(n \ln n)$ string comparisons. The time required for a string comparison will be worst-case proportional to the maximum length of strings involved, so the total time must be multiplied by a factor of that to obtain an upper bound.
> 2 votes

# Answer
I think a straightforward way to accomplish this would be to create a mapping of every element in your `ordering` list to its index i.e. `order["three"] = 3`. Then your comparator for sorting two objects `a` and `b` in the input is `order[a] <= order[b]`

This way, you can easily abstract the pairwise comparisons. For example both Python and C++ (and probably many others) allow you to provide comparators/keys for sorting.
> 2 votes

---
Tags: algorithms, sorting, strings, comparison, string-matching
---


# Question
Title: Is Knapsack restricted to integers between 1 and 100 still NP-complete?
The title pretty much says it all. I want to know if Knapsack is still NP-complete when the weights, values, and weight limit are restricted to a finite set of values. I figure that it wouldn't be because clearly for very small finite sets it isn't. (E.g., if you must use integers from 1 to 3.) That said, I'm struggling to find a polynomial-time algorithm.

One thought I had was since there are a finite set of possible inputs and outputs, could your algorithm just be a massive chain of if statements? I'm not sure whether this even would count as an "algorithm" though.

# Answer
Let $V(i, W)$ be the maximum sum of the values of the items among the first $i$ items so that the sum of the weights is less than or equal to $W$, then we have

$$V(i, W)=\max\\{V(i-1, W), v\_i+V(i-1,W-w\_i)\\}$$

where $v\_i$ and $w\_i$ are respectively the value and the weight of the $i$th item. Suppose there are $n$ items and the capacity limit is $W\_\max$, then the problem is equivalently to compute $V(n, W\_\max)$. We can use the recursion formula above to compute the following values in order: $$V(1,1),\ldots,V(1,W\_\max),V(2,1),\ldots,V(2,W\_\max),\ldots,V(n,1),\ldots,V(n,W\_\max).$$

This is the classical dynamic programming method to solve the Knapsack problem. Since it takes $O(1)$ time to compute each $V(\cdot,\cdot)$ and there are $O(nW\_\max)$ such values to compute, the overall running time is $O(nW\_\max)$. Since you restrict $W\_\max\le 100$, the overall running time becomes $O(100n)=O(n)$, which is indeed polynomial in $n$.
> 6 votes

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


# Question
Title: Incremental View Maintenance for projection
I was reading https://www2.cs.duke.edu/courses/spring02/cps296.1/lectures/08-view.pdf

Or in the paper "Incremental Maintenance of Views with Duplicates," by Griffin and Libkin, SIGMOD, 1995. figure 2.

I don't understand why we need to min(R,ΔR) before -. Is there any counterexample?

# Answer
> 0 votes
Just realize the reason after posting the question. Counterexample: R =

A B

1 2

1 1

1 1

ΔR =

A B

1 1

1 1

1 1

Assume we want ΠA(R - ΔR)

The true answer is first R - ΔR:

A B

1 2

Then project A:

A

1

However, if ΠA(R - ΔR) = ΠA(R) - ΠA(ΔR). ΠA(R):

A

1

1

1

ΠA(ΔR):

A

1

1

1

ΠA(R) - ΠA(ΔR) = ∅

ΠA(R - ΔR) = ΠA(R) - ΠA(R min ΔR).

R min ΔR:

A B

1 1

1 1

ΠA(R min ΔR):

A

1

1

ΠA(R) - ΠA(R min ΔR):

A

1

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: Enumerate all valid orders of subset sums
Given an positive integer $n$, we define an *order of subset sums* (or simply, an *order*, when there is no ambiguity) to be a sequence of **all** subsets of $\\{1,\ldots,n\\}$. For example, when $n=2$, the sequence $\emptyset,\\{1\\},\\{2\\},\\{1,2\\}$ is an order.

We call an order $S\_1,\ldots,S\_{2^n}$ *valid* if there exist real numbers $0\<x\_1\<\cdots\<x\_n$ such that $\sum\_{i\in S\_1}x\_i\<\cdots\<\sum\_{i\in S\_{2^n}}x\_i$. For example, when $n=2$, the sequence $\emptyset,\\{1\\},\\{2\\},\\{1,2\\}$ is a valid order, but the sequence $\emptyset,\\{1\\},\\{1,2\\},\\{2\\}$ is not because we cannot make $x\_1+x\_2\<x\_2$.

The question is, given $n$, how to enumerate all possible valid orders. To output an order $S\_1,\ldots,S\_{2^n}$, it is sufficient to output an algorithm that generates this order, i.e., an algorithm with no input (the parameter $n$ is built-in) that outputs $S\_1,\ldots,S\_{2^n}$ in order, as long as the algorithm runs in $O(n2^n)$ time. Even so, this problem still cannot be solved in time polynomial in $n$, because there may be exponentially many valid orders, thus an algorithm running in exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order is valid.

# Answer
Here is one algorithm that runs in doubly exponential time -- so probably useless. In other words, this answer is probably not useful.

You can check whether an order is valid in $2^{O(n)}$ time (i.e., $\text{poly}(2^n)$ time) by reducing to linear programming: you obtain $2^n+n-2$ linear inequalities in $n$ variables, and you can test for feasibility in time polynomial in the number of inequalities and variables. Then, enumerating over all possible sums and checking if each is valid would yield a $(2^n)! 2^{O(n)} = 2^{n 2^n + O(2^n)}$ time algorithm. This will be ridiculously slow in practice.

---

To improve this, you could use an iterative pruning / branch-and-bound style algorithm. Given a prefix $S\_1,\dots,S\_k$ of an order, we can test whether it is valid using linear programming as above. If it is not, we don't consider any order that starts with this prefix. In other words, do breadth-first search: first choose $S\_1$, then choose $S\_2$, then choose $S\_3$, and so on, at each step checking whether the prefix obtained so far is valid.

This may still be extremely slow, as there is the possibility that a prefix $S\_1,\dots,S\_k$ is valid but there is no way to complete it to a full order $S\_1,\dots,S\_{2^n}$ that is valid, so this might do a lot of wasted work.
> 0 votes

---
Tags: algorithms, enumeration, subset-sum
---


# Question
Title: Hardness of a scheduling/assignment problem
I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020.

Hier is a brief description of the problem. Given a list or libraries and a list of books. Each book $b$ has a number of points $P\_b$. We want to scan a subset of the books in a way that maximizes the total points of the books we scan in $n$ days. We have to choose the books from the libraries. Each library $l$ has a list of books $B\_l$, the number of books we can scan per day in this library $m\_l$ and the number of days needed to register the library (do the paper work) $d\_l$. We can scan books in parallel from many libraries at once but the registration should happen sequentially and we cannot register two libraries at the same time. Moreover, the same book can be fond at many libraries and we have to decide what books should be chosen from which libraries and in which order. We can scan as many books per day as we want (respecting the constraints provided by libraries).

Here is an example: We have two libraries and three books. Assume we have 3 days in total. The books have 40, 40, 40 and 30 points respectively. The first library has the first 3 books. The second library has the first and the forth book. Assume each needs one day to register and can provide one book per day. We can choose the first library at first. In the first day we register this library. In the second day we can scan the second book while registering the second library. in the third day we can scan the third book in the first library and the first book in the second library. This totals in the first three books and a total of 120 points. Note that if we scan the first book in the first library or we start by the second library we would have had to scan the 30-point book instead a 40-point one.

---

Here is what I have tried so far. On one hand, having the correct order of libraries in hand, we can solve the problem in polynomial time, since we can calculate how many books each library can achieve in total (total number of days minus prefix sums of library-registration-time for libraries we have chosen so far all multiplied by the number of books this library can provide per day). Using these values we can turn the problem into a weighted bipartite b-matching problem where each library is connected to the books it has with edge-weights equal to the points of each book. Each library has capacity the total number of books it can provide. This problem can be reduced to maximum-weight bipartite matching and solved in polynomial time. However, finding a correct order of libraries seems to me as a hard scheduling problem.

On the other hand, by assuming $B\_l$ are pairwise disjoint over all libraries $l$, which means each library has its "own" set of books, and assuming each library can provide exactly one book per day, and each book has exactly one point, we turn the problem into a scheduling problem of determining an order of the libraries where each library has registration time and number of points such that it can give one point per day after registration and registrations happen sequentially. This problem seems similar to knapsack problem since we can solve it using dynamic programming over the number of the given days where $d\_{i, j, k}$ is the most number of points we can achieve from the $i$th to the $j$th library in $k$ days where all libraries in the range are registered on the $k$th days and we are free to register a new library. The problem seems similar to the knap-sack probkem. However, I can't find a proper reduction since the number of points we get depends heavily on the the order and that in this special case the number of days is polynomial in the size of the input and hence, psudo polynomial algorithm is a polynomial time algorithm.

---

*Do you think this problem is NP-hard? I appreciate all hints, thoughts and ideas about hardness and/or polynomial solutions* :)

**Disclaimer.** The question is just out of curiosity. The competition is already over and an $O(\sqrt n m)$ matching algorithm is already too slow for the suggested bounds on a typical computer so I am just asking from a theoretical point of view.

# Answer
> 3 votes
The problem is NP-hard, at least for a particular simplified configuration.

Assume that each $m\_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. Let all $d\_l = 1$ \- each library takes one day to get access to, meaning we get access to exactly $n$ libraries. Now if $P\_b = 1$ the thing that maximizes our score is the number of unique books we scan. The order in which we choose to get access to libraries does not matter, but our selection of *which* does.

Now if there was an efficient algorithm to solve this problem you could solve the maximum coverage problem efficiently as well, meaning your problem is NP-hard.

---
Tags: algorithms, reductions, np-hard, scheduling, bipartite-matching
---


title: Lower bound for Merge Sort running time

text:
# Question
Title: Lower bound for Merge Sort running time
I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log\_2 n)$.

Here's my attempt: Suppose there is some $c\>0$ and a positive integer $n\_0$ such that $n\_0 \le k \< n \implies T(k) \ge ck \log\_2 k$.

Then

$$\begin{eqnarray\*} T(n) &=& 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\ &\ge& 2c \left \lfloor \frac{n}{2} \right \rfloor \log\_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\ &\ge& 2c \left ( \frac{n - 1}{2} \right ) \log\_2 \left ( \frac{n - 1}{2} \right ) + n \\ &=& c(n - 1) \log\_2(n - 1) - c(n - 1) + n \\ &=& cn \log\_2(n-1) - c \log\_2(n-1) - c(n - 1) + n \\ &=& cn \log\_2 \left \[ n \left ( 1 - \frac{1}{n} \right ) \right \] - c \log\_2(n-1) - c(n - 1) + n \\ &=& cn \log\_2 n + cn \log\_2 \left ( 1 - \frac{1}{n} \right ) - c \log\_2(n-1) - c(n - 1) + n. \end{eqnarray\*}$$

I can't determine if there is a $c \> 0$ such that $cn \log\_2 \left ( 1 - \frac{1}{n} \right ) - c \log\_2(n-1) - c(n - 1) + n$ is non-negative for $n$ large enough.

Also, I think this approach is too complicated given how easy it is to prove $T(n)=O(n \log\_2 n)$. Am I missing some obvious estimate here?

Any help is welcome. Thanks.

# Answer
$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n\_1$ and $n\_2$ such that

$$\begin{eqnarray\*} n &\ge& n\_1 \implies -\frac{1}{2} \< \log\_2 \left ( 1 - \frac{1}{n} \right ) \\ n &\ge& n\_2 \implies -\frac{1}{2} \< -\frac{1}{n} \log\_2 (n - 1). \end{eqnarray\*}$$

Rewriting $$cn \log\_2 \left ( 1 - \frac{1}{n} \right ) - c \log\_2(n-1) - c(n - 1) + n$$

as

$$ cn \left \[ \log\_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log\_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right \], $$

we have

$$n \ge \max(n\_1, n\_2) \implies -2 + \frac{1}{c} \< \log\_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log\_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{2}$.
> 1 votes

---
Tags: algorithm-analysis, asymptotics
---


title: Can neural network process randomness?

text:
# Question
Title: Can neural network process randomness?
So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is *a lack of knowledge* in most case.

For this question, I've got some examples.

---

**First case, not a real problem?**

We just throw a coin and get the result and we do that a whole bunch of times. For each throw, we get the initial condition (air pressure, force, etc.). Now we put all this data into the neural network for it to process.

*My guess* : The result is not really random since it only depends on the initial conditions so it's possible and the neural network will do a great job. So I guess that example is not a real problem since the "randomness degree" is weak.

**Second case, questioning**

Now, we generate a random list of number and sentences that correspond to each other so we have something like :

```
'zefvkbdl' -> 1613841.009
'nfeovhlzm' -> 963478.29
'jhgcjbklnsczl' -> 1.535953
'ergz' -> 9138630.26
etc ...

```

In a way that everything was randomdly generated (still, the list of sentences and number were not generated seperatly but each number was generated after a sentence and correspond to that sentence). In that case, is it possible to give a neural network the half of the list (the list can be forever long) and expect it to predict the other half with a great precision ?

*My guess* : It depends on the generation algorithm but let's pretend that a letter is just a particular index in an array and that the index was randomly generated. Since most of the time, numbers are randomly generated thanks to the digits of time (the last decimals that are changing extremely fast) *I'm not sure of that* \- I guess it might be possible with an extremly powerful neural network to *theoretically* do that job.

**Third case**

Let's now be even more theoretical and consider it is possible to store somehow the global state of the universe at each moment of time. The only thing that is truly random at my knowledge is quantum mechanics so let's try it out. At each point of time, we store the whole universe state and the outcome of measuring a quantum particle state (like the spin of an electron). Is it possible, after the biggest neural network training, to "predict" the outcome of measuring a quantum particle state knowing the state of the universe ?

---

Since I'm just a curious student, I don't have a lot of knowledge in neural network or quantum mechanics so I probably said a lot of wrong things and I'm sorry for that. I thank you for reading all of this and I hope someone is able to help me anwser or correct me.

Now, the real question I'm asking is : **Do randomness truly exist ?**

# Answer
Purely randomness is not possible but in real-world the most randomness that a neural network can process is enough to discover an approximation pattern; the precision depends on the model of the context (exactitude of the Digital Twins) and processing power.

To extract the exact pattern from the pure randomness (I think) is impossible even with a quantum computer and even having all the time and resources of the universe. The reason is that nothing in the universe happens randomly, every effect has a cause. So regarding to the third case (theoretically) if you can reproduce every cause of a "twin universe" you can predict the future.
> 2 votes

# Answer
This is maybe not the answer you are looking for but I hope it will clear some things up. Humans make models to better understand things and to predict behaviors. Do atoms (electrons, positrons, neutrons) actually exist ? Have we seen them ? Is it able to see them ? The answer is no. BUT, the atom theory explains perfectly all the experiments that have been made so far. Can we predict the outcome of a coin flip ? No. But, probabilistic models perfectly explain the expected outcome. Does randomness really exist ? I cannot answer this question because I am not god.

Now as far as your concern about if neural networks can be trained to predict randomness. This is a more general question and you may have a look here (one way functions) and here (random polynomial algorithms). These topics are both correlated with randomness on their very definition, and they are both open because both are very difficult to deal with. Randomness, entropy, time are concepts which we face at any given point and are truly amazing if you ask me.

Neural networks are trained to detect non linear patterns/rules between data. If the data are randomly generated then neural networks won’t succeed. But, on the other hand, if a neural network is able to achieve some sort of \>50% prediction, then we should ask ourselves, is the generator actually random ? How can we check if a generator is actually random ? (The second link will be more helpful for these kind of questions).
> 0 votes

---
Tags: algorithms, neural-networks, quantum-computing, randomness
---


title: Prove that Hitting Set is NP-Complete

text:
# Question
Title: Prove that Hitting Set is NP-Complete
The Hitting Set Problem (HS) is defined as follow. Let $(C,k$)

* $C = \\{ S\_1, S\_2, ..., S\_m \\}$ collection of subset of S i.e. $ S\_i \subseteq S , \forall i$
* $k \in \mathbb{N}$

We want to know if exists ${S}' \subset S$ where $|{S}'| \< k$ such that $S\_i \cap S' \neq \emptyset $, $i = 1,2,...,m.$

**Prove that HS is Np-Complete.**

*Hint*: When $|S\_i| = 2$, HS becomes Vertex Cover, already know to be NP-complete.

# Answer
3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define

$$S = \\{ x\_1, \dots x\_n, \overline{x\_1}, \dots , \overline{x\_n}\\}$$ $$S\_i=\\{y\_1, y\_2, y\_3\\}, \text{ if } y\_1,y\_2,y\_3 \in S \text { and } (y\_1 \lor y\_2 \lor y\_3) \text{ is a clause.} $$ $$S\_x=\\{x, \overline{x}\\}, \text{ for all variable } x.$$ $$k=n$$

Assume $\phi$ is satisfiable, then there a is true-value assignment for $n$ variables. So, add $x$ to $S'$ if $x=true$, otherwise add $\overline{x}$ to $S'$.

Now, assume the HS problem has a solution $S'$. Then since for every variable $x$, $S' \cap S\_x \neq \emptyset$, $S'$ has at least $n$ literals of the form $x$ or $\overline{x}$ for each variable $x$. Furthermore, no $x$ and $\overline{x}$ may belong to $S'$ at the same time since the size of $S'$ is at most $n$. Also, for each clause $C\_i$, $S' \cap S\_i \neq \emptyset$ and so for each clause we select $y\_i\in S' \cap S\_i$, and set $x=true$ if $y\_i=x$ and $x=false$ if $y\_i=\overline{x}$.
> 9 votes

# Answer
It is easy to show that Hitting Set is in NP. A solution just needs to exhibit the set H – one can easily verify in polynomial time whether H is of size k and intersects each of the sets B1, . . . , Bm.

We reduce from vertex cover. Consider an instance of the vertex cover problem – graph G = (V, E) and a positive integer k. We map it to an instance of the hitting set problem as follows. The set A is the set of vertices V . For every edge e ∈ E, we have a set Se consisting of the two end-points of e. It is easy to see that a set of vertices S is a vertex cover of G iff the corresponding elements form a hitting set in the hitting set instance.
> 1 votes

# Answer
The Hitting Set Problem is equivalent to the Set Cover Problem, that is defined as follow:

INPUT: a collection C of subsets of a finite set S.

SOLUTION: A set cover for S, i.e., a subset $C'\subseteq C$ such that every element in S belongs to at least one member of $C'$.

Given $k$ does it exist a set cover $C'$ such that $\vert C'\vert \leq k$?

This looks like a homework, so I let you figure how, given an instance of Set Cover you can convert it to an equivalent instance of Hitting Set.

Otherwise, if you want to follow the hint, you first show that Hitting Set in in $NP$, that is given a solution you can verify it in polynomial-time.

Then, you show that given a graph $G=(V,E)$, finding a vertex cover of size $k$ is equivalent to find a hitting set of size $k$. That is, if $|E|=m$, you can build a hitting set instance with the same amount of sets.
> 0 votes

---
Tags: complexity-theory, np-complete, decision-problem, information-theory
---


# Question
Title: Time complexity of insertion in linked list
Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:

> What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

In my opinion, the answer should be $O(n^2)$ because in every insertion, we will have to insert the element in the right place and it is possible that every element has to be inserted at the last place, giving me a time complexity of $1 + 2 + ... (n-1) + n = O(n^2)$

However, the solution that I have says that we can first sort the elements in $O(n \log n)$ and then, we can insert them one by one in $O(n)$, giving us an overall complexity of $O(n \log n)$.

From the given wording of the question, which solution is more apt? In my opinion, since the question mentions "linked list needs to be maintained in sorted order", I am inclined to say that we cannot sort the elements beforehand and then insert them in the sorted order.

# Answer
> 3 votes
The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. This is allowed by the problem statement.

A practical reason to do this, rather than insert the elements then sort, would be if the linked list object is shared with another thread that requires it to always be sorted. (In such a scenario, you'd need to ensure that inserting one element is atomic.) So this question isn't just making strange requirements for the sake of being strange. It's the sort of requirements that come up often in the real world of programming.

Another solution with the same complexity would be to insert the elements into the target list as they come, and maintain a parallel data structure mapping element values to node pointers in the target list. To insert each element, find the preceding element in the mapping, and insert the new element after this node. This assumes that the insertion process creates the list nodes as it goes (as opposed to filling existing blank nodes).

This question is more about reading comprehension than about algorithms. The way it's worded, it's a bit of a trick question. It's somewhat poorly worded because it relies on precise reading, but fails to state some key assumptions, such as the fact that obtaining the elements to insert costs $O(n)$, comparing two elements can be done in $O(1)$, and the input domain is effectively unbounded (exercise: come up with an $O(n)$ algorithm if the inputs are integers in the range $\[1,42\]$). But the given answer is correct.

You made the assumption that there's no way to use an auxiliary data structure. Nothing in the problem statement forbids using auxiliary data structures. A simple way to forbid auxiliary data structures would be to require $O(1)$ memory overhead.

Note that even under this assumption, your reasoning is wrong, or at least imprecise. If you happened to know that the elements are given in the correct order, you could maintain a pointer to the tail of the list, and keep inserting there, which would take $O(n)$. The worst case is not if every element has to be inserted at the last position in the target list, but at the last position reached when traversing the list in some way. The worst case is indeed $\Theta(n^2)$, but to prove this, you have to prove that finding the insertion point in the list takes $\Theta(n)$ time, and this requires proving that the distance from *any* pointer you have into the list is bounded below by $\Omega(n)$. This is the case if you have a constant number $A$ of pointers (you implicitly assumed $A=1$, with a single pointer at the start of the list), so that you need to traverse at least $k/A$ nodes after $k$ insertions in the worst case.

# Answer
> 1 votes
Best possible structure which I know of, are Fibonacci Heaps, you can insert elements in $O(1)$ and extract the minimum in $O(\log(n))$, this means if you need a sorted order of all elements it takes you $O(n\log(n))$ while inserting new elements only costs you $O(1)$, I know no other structure which could keep up with this.

# Answer
> 0 votes
It really is a tricky question. First of all, the complexity of O(nlogn) applies only for the algorithms which use comparison between their elements (comparative algorithm). There are also algorithms which are non-comparative such as Radix sort which their complexity depends on the size in bits which the numbers need to be stored in memory. So if we assume that we can sort the numbers beforehand with any algorithm, then we can also assume that the numbers are naturals and the maximum element is M \< 10, so with radix sort you would get worst case O(10n) = O(n). If we cannot make any assumption then you are right. If you are only allowed to use linked lists and nothing more (no indexing of any kind), then the complexity is O(n^2) (bubble sort).

# Answer
> -1 votes
It should be O(n). Follow the algorithm as -

1) If Linked list is empty then make the node as head and return it.

2) If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head.

3) In a loop, find the appropriate node after which the input node is to be inserted.

To find the appropriate node start from the head, keep moving until you reach a node who's value is greater than the input node. The node just before that is the appropriate node

4) Insert the node after the appropriate node found in step 3

---
Tags: sorting, linked-lists
---


title: Amount of k-partitions of a number

text:
# Question
Title: Amount of k-partitions of a number
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions. For example:

The partitions of size 2 for number 5 are:

* \[4, 1\]
* \[3, 2\]

The partitions of size 3 for number 6 exists only of:

* \[3, 2, 1\]

Notice that \[2, 2, 2\] isn't a partition because it has a repeating use of 2.

I currently have implemented a dynamic algorithm that finds the amount of partitions that allow repetition. Here $m$ is is the number and $n$ is the size of the partitions.

```
def count_partitions(m, n):

    def e_at(i,j):
        if i == j and j == -1:
            return 1
        if i < j:
            return 0
        else:
            return p[i][j]

    p = [[-1 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        p[i][0] = 1

    for i in range(m):
        for j in range(1, min(i + 1, n)):
            if i < 2*j:
                p[i][j] = e_at(i-1,j-1)
            else:
                p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j)

    return p[m-1][n-1]

```

I've also got a program to generate all the different distinct k-partitions of a number $n$

```
def generate_partitions(n, k):
    if n == 0:
        return []

    def rec_partition(m, b, n, a, l):
        if m == 0:
            l.append(conj_partition(a[:n]))
        else:
            c = a[n]
            for i in range(1, min(b,m) + 1):
                a[n] = i
                rec_partition(m-i, i, n+1, a, l)
            a[n] = c

    def has_double(l):
        for i in range(len(l) - 1):
            if l[i] == l[i+1]:
                return True
        return False

    l = []
    a = [0] * n

    a[0] = k
    rec_partition(n - k, k,1, a, l)

    return sorted([p for p in l if not has_double(p)], reverse=True)

```

So far the only way I found to get the number of distinct k-partitions is to generate them all and take the length of the returned list.

However I feel like there would be a better way to get the amount without generating them all by modifying the dynamic programming algorithm above. But I haven't had any luck with that.

Anyone has any idea that would help?

# Answer
> 1 votes
You can solve this with DP. Let $DP\[n\]\[k\]\[m\]$ denote the number of partitions of $n$ into $k$ numbers, all of which are distinct and at most $m$. Then we have the recurrence

\begin{align} DP\[n\]\[k\]\[m\] &= \sum\_{v = 1}^{m} DP\[n-v\]\[k-1\]\[v-1\]\\ &= DP\[n\]\[k\]\[m-1\] + DP\[n-m\]\[k-1\]\[v-m\] \end{align}

Since we can take the numbers forming the partition from largest to smallest, so whenever we take some number, all numbers we take after it must be strictly smaller. The base case is $DP\[0\]\[0\]\[m\] = 1$ for any $m$ and $DP\[x\]\[y\]\[m\] = 0$ whenever $x \< 0$ or $y \< 0$. If you care about the order of the elements in the partition, multiply the result by $k!$.

We can calculate this recurrence in $\mathcal{O}(n^{2} k)$, but tighter analysis gives an even better bound:

For a state $(n', k', m')$ to be reachable by this recurrence from $DP\[n\]\[k\]\[n\]$, we must have $m' \leq \frac{n-n'}{k-k'} \leq \frac{n}{k-k'}$ (since our number decreased by $n - n'$, so some number in the current partition of sum $n - n'$ and size $k - k'$ must be at most $\frac{n - n'}{k - k'}$). But this means that for any fixed $k'$, there are at most $\frac{n^{2}}{k-k'}$ reachable DP states, and

\begin{equation\*} \sum\_{k' = 0}^{k-1} \frac{n^2}{k-k'} = \mathcal{O}(n^2 \log k) \end{equation\*}

Thus the actual complexity is $\mathcal{O}(n^2 \log k)$.

---
Tags: dynamic-programming, discrete-mathematics, partitions
---


title: Maximum matching in a bipartite graph

text:
# Question
Title: Maximum matching in a bipartite graph
Given a bipartite graph $G=(V\_1 \cup V\_2, E)$ and a set $V' \in (V\_1 \cup V\_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?

# Answer
Set $V\_i' = V\_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V\_1'$ and at most $x-k$ from $V\_2'$ for all $k \in \[0, x\]$. This in turn can be found with maximum flow.

To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be auxiliary vertices. Add an edge from $s$ to $l$ with capacity $k$, and an edge from $r$ to $t$ with capacity $x-k$. All other edges will have capacity $1$. Add an edge from $l$ to every $x \in V\_1'$, and from $s$ to every $x \in V\_1 \setminus V\_1'$. Add an edge from every $y \in V\_2'$ to $r$, and from every $y \in V\_2 \setminus V\_2'$ to $t$. For $(x, y) \in E$, add an edge from $x$ to $y$. Now the maximum flow gives a maximum matching using at most $k$ vertices in $V\_1'$ and $x-k$ in $V\_2'$.

We can thus solve the problem in $\mathcal{O}(x \cdot M)$ where $M$ is the complexity of maximum flow. The maximum flow problems are very similar, so we can improve on this.

We can increase or decrease the capacity of any edge by $1$ while maintaining the maximum flow in $\mathcal{O}(|E|)$. First calculate the maximum matching using no vertices in $V'$. Then, increase the capacity of the edge from $s$ to $l$ by $x$. Then at every step increase the capacity of the edge from $r$ to $t$ and decrease the capacity of the edge from $s$ to $l$ while maintaining a maximum flow. Output the largest matching produced. The complexity will be $\mathcal{O}(|E| \sqrt{|V|} + x \cdot |E|)$ if we use Dinic to find the initial bipartite matching.
> 5 votes

---
Tags: complexity-theory, graphs, bipartite-matching, bipartite-graph
---


title: Showing on-line P = NP

text:
# Question
Title: Showing on-line P = NP
I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations.

Following that, I have defined an algorithm to resolve the TSP-metric. I agree that $6(n^{12})$ is a lot, but it is $P$ and it is the limit of *n* trending to infinite. For $n \< 45$ the performance is $5(n^9)$.

> First question: Assuming the theorem is correct, Is this enough to proof $P = NP$ ?

Before publishing the results and the method in a paper, I want to show on-line that the algorithm is in $P$. I can produce an exact result of 45 cities in less than a half of a day since the Held-Karp algorithm will need more than 16 days.

I will certify with a cloud computing provider the host hardware used, but source code will be black-boxed. Inputs will be provided by anyone and she/he/they may be the only one(s) that know(s) the solution.

> Second question: Is this "show" good enough/idea to prove that I actually have solid evidence of it is not a fake?

Important to note that its purpose is only to claim attention showing evidence not substituting the proof of the theorem, I´ll make it publish (public-free) as soon as it will be demanded, I won't keep it in secret. The reason to do this "show" is that being no one if I publish the "theorem" no one gives it a chance. I have checked that way.

# Answer
1. Metric TSP is NP-complete - hence *yes*, assuming you can solve the metric TSP in $6(n^{12})$, this is good enough to prove $P=NP$.
2. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure out a reduction of crypto-algos to metric-TSP. It could break ‚secure communication‘, blockchain (bitcoin), etc... All these technologies are based on the assumption computer scientists and mathematicians have had for decades now, namely that that $P \neq NP$
> 3 votes

---
Tags: complexity-theory, computability, proof-techniques, p-vs-np
---


# Question
Title: Good book on the history of programming languages?
I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, object oriented programming etc were developed? I was introduced to programming when OOP was well developed and hence I don't really know what it was like for OOP to be developed for the first time. Similarly for structured programming, procedural etc.

Is there a good book that starts with the first programmers who worked directly in computer code, and goes through the different developments, showing how the developments were non-trivial at the time (even though from our current perspective they might seem natural and obvious)?

# Answer
There is an infrequently held conference series called *History Of Programming Languages (HOPL)*. It was held in 1979, 1993, and 2007, the fourth installment is scheduled for middle of June, 2020.

The Proceedings for HOPL-I and HOPL-II were also published as books, for HOPL-III, both the papers and video recordings of the presentations are available. (Including the highly entertaining, though not necessarily highly scientific *50 in 50* by Guy Steele and Dick Gabriel, presenting 50 language-related ideas from 50 years in 50 words each within (a little bit more than) 50 minutes.)

There is also a website called *Online Historical Encyclopaedia of Programming Languages*, which collects about 9000 languages and presents them in the form of a hypergraph with several kinds of relationships (evolution-of, influence, dialect, …, also people involved, regions where it was developed, institutions, etc.) between them.
> 6 votes

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


title: Embedded arithmetic set expressions

text:
# Question
Title: Embedded arithmetic set expressions
In set builder notation, we can represent the set: $$\\{ 2, 7\\}$$ as: $$\\{ x | x=2 \vee x=7 \\}$$.

Therefore, the PA arithmetic predicate: $$φ(x) := x=2 \vee x=7$$ is capable of representing this set. The boolean expression: $$x=2$$ can also be represented in arithmetic by the function:

$$1-sgn(x-2)²$$

So: $$x=2 \vee x=7$$ is equivalent to: $$(1-sgn(x-2)²) \vee (1-sgn(x-7)²)$$.

Since: $$x \vee y = x+y-xy$$

we can represent:

$$φ(x) := 1-sgn(x-2)² \vee 1-sgn(x-7)²$$

$$φ(x) := 1-sgn(x-2)² + 1-sgn(x-7)²-(1-sgn(x-2)²)(1-sgn(x-7)²)$$

which simplifies to:

$$φ(x) := 1 - sgn((x-7) (x-2))²$$

So, we can have an arithmetic predicate that does not need to use boolean operators and that can represents the set:

$$ \\{ a\_1, a\_2, a\_3, ... , a\_n \\}$$

arithmetically as:

$$φ(x) := 1 - sgn((x-a\_1)(x-a\_2)(x-a\_3)...(x-a\_n))²$$

Now I am stuck trying to use a similar technique to represent the embedded set expression:

$$\\{1, 2, \\{ 4, 9\\}, 7\\}$$

The inner embedded set { 4, 9 } in the expression above may look somewhat like:

$$φ\_2(x) := 1 - sgn((x-4)(x-9))²$$

The outer set may look somewhat like:

$$φ\_1(x) := 1 - sgn((x-1)(x-2)(x-φ\_a(x))(x-7))²$$

But I cannot figure out how to express:

$$φ\_a(x)$$ in terms of: $$φ\_2(x)$$

Can this actually, uberhaupt, even be done?

# Answer
> 3 votes
Your problem is that your trick of representing set membership using arithmetic only applies to sets consisting of numbers only. Say you have a set of colours { red, green } then 1 - sgn (x - red)^2 doesn’t make any sense. Even worse is a set containing other sets as elements.

---
Tags: arithmetic, propositional-logic
---


# Question
Title: Passing a non-mutable argument by value or by reference?
A function can generally be defined to receive parameters by value or by reference. If we want to mutate an object inside the function and have those changes reflected outside the function, then it must be passed by reference.

If we don't want to mutate the object then we can choose between passing by value or by reference. The choice, in my experience, is based on whether or not it's expensive to copy the object. If it's cheaper to copy than to deal with the reference's indirection - pass by value, else - pass by reference.

**1) Are there any other considerations that should be taken into account?**

**2) Wouldn't a compiler be better suited to make this choice instead of the programmer? Why, or why not?**

To illustrate question 2, the programmer could simply indicate whether they intend to mutate an argument or not. If an argument will be mutated then it must be passed by reference. If it won't be mutated, then the compiler can choose between passing by value or by reference - whichever is faster.

**3) Do you see any pitfalls in this approach to language/compiler design?**

# Answer
> 1 votes
Be careful. If I define (C type syntax for familiarity):

```
int var;

void f(const int x)
{
      ...
      var = ...;
      ...
      /* use */ ... x ...
      ...
}

```

Now go `f(var)`. If pass by value, `f` uses the original value (at the call); with pass by reference, the value asigned in `f`. The *language* should specify which one. Only if the compiler can *prove* it makes no difference can it decide (and for that, it has to know all programs calling `f`, or forbid changing global variables).

I'd give *one* option, just for clarity of specification.

---
Tags: programming-languages, compilers
---


# Question
Title: For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)
Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n \>= 0} I’m trying to design a PDA. My aproach is:

-for every 2 ‘a’ push an ‘a’

-for every 4 ‘c’ push a ‘c’

-then pop them to solve the 2nd half of the language

This is the first part to count 2 ‘a’, but the ‘c’part is not very clear:

Any hints or solutions for the problem: **‘’for every 4 ‘c’ push a ‘c’ on the stack‘’**

Thanks!

# Answer
Use states to record how many 'c' you have seen (0 to 3), use transitions that don't change the stack to move among them when reading 'c'; on a 'c' in a state recording 3 'c', push a 'c' and go back to 0 'c' seen. Can mix/combine freely with e.g. counting the 'a' or 'b'.
> 0 votes

# Answer
You can recognise the language $L = \\{c^{4n}|n\geq 0\\}$ with a normal DFA. Use this automata as a base and just use one designated state, that pushes a C onto your stack, for which I would choose the first one. For every transition one c is consumed from the word.

$\\{(q\_1, c, S, CS, q\_2) , (q\_2, c, S, S, q\_3), (q\_3, c, S,S,q\_4), (q\_4, c, S,S,q\_1), (q\_1, d, C, \varepsilon, q\_d)\\} \subset \Delta $ with $S \in \Gamma$
> 0 votes

---
Tags: pushdown-automata
---


title: Tools for modelling compilers

text:
# Question
Title: Tools for modelling compilers
I'm a wannabe mathematician, whose master's thesis is (by the looks of it) going to focus on a certain "compiler", used to produce learning materials from a subset of $\LaTeX$, in the context of mathematics education. I'm of course going to have to talk about the compilation process in general, and was planning to discuss the mathematical abstractions related to it (this being a master's thesis in mathematics), and then use those to describe the compiler.

I have no experience in the field whatsoever, however, and was wondering whether the concepts of regular expressions and languages, automata and the like are actually used to model (and|or) describe the functionality of compilers in a professional setting. Is it typical (even in the industry) to use these methods of modelling compilers, or are there better alternatives available?

I simply stumbled upon these basic concepts in a certain course handout, and they *seem* useful, but I want to be certain.

# Answer
Be careful. Even mastering the tools for compiler construction, handling a *very* complex preexisting language (which LaTeX certainly is) is an arduous task. Add that there is *no* firm syntax for LaTeX (there are certain overall conventions, but lots of special cases) makes it worse.

But to really be of any guidance, we'd need *a whole lot* further detail: What kind of documents? Can you define the format, or is it a corpus of preexisting texts? Do they use the same packages? Are they written to some rigid format or "anything goes? What do you want to extract? (If it is e.g. all the "exercise" environments it is very simple ---but the contents will depend on all sorts of external definitions, finding/including that isn't simple. Solution is to require manual fixups, but that negates the "automation" aspect).

Go also to TeX.SE for LaTeX related questions.

Good luck!
> 1 votes

---
Tags: compilers, modelling
---


# Question
Title: Maximum number of steps a Turing machine makes
Given the Turing machine $M = ( \\{q\_0, q\_1, q\_2. q\_3,q\_4\\}, \Sigma= \\{a, b, c \\}, \Gamma = \\{a, b, c, \\}, \delta, q\_0, , \\{q\_4\\} )$ where $q\_0$ is the start state, $q\_4$ the end state and the blank symbol. $\delta$ is defined as:

Let $w$ be any word of length $n$ accepted by the Turing machine $M$. Is it always true, that $M$ will reach $q\_4$ in maximum of $1.5 \cdot (n+5)$ steps?

Is there a general strategy for this or do we just try different inputs until we find a contradiction? If none is found, how do we go about *proving* such a statement?

# Answer
> 2 votes
In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details.

There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete libraries written on the intricacies of the matter...

---
Tags: turing-machines
---


# Question
Title: DFA accepting strings with at least three occurrences of three consecutive 1's
The problem states the following:

> Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\\{0,1\\}$ with overlapping permitted.

I was able to come up "without overlapping" version as follows:

Regex of this DFA is `(1+0)*111(1+0)*111(1+0)*111(1+0)*`. However this DFA does not accept `11111`. This string should be accepted as the problem says overlapping of groups of three consecutive 1's is allowed. But I am not able to guess how do I do this. I feel I cannot do it with DFA as this will require to have some form of memory (for example, once I read 111, it should remember first occurrence of three consecutive 1's is read and also two consecutive 1's of next occurrence have already been read) which is not what DFA provides. Am I right with this?

If not with DFA, can I do this with non deterministic finite automaton (NFA) or deterministic pushdown automaton (DPDA) or non deterministic pushdown automaton (NPDA)? Or this can be done only with Turing machine?

# Answer
No, you don't need NFA (although it is equivalent to DFA) or PDA or Turing machine to solve this problem. It can be easily done with a DFA.

Lets number the states in given DFA in clockwise fashion starting from start state as Q0 to final state as Q9. First of all, it being a DFA, Q9 should have a self loop with label 1 as all possible transitions should be shown from all the states in a DFA.

Now we need to add two states, lets name them Qa and Qb. The changes in the transitions to be made are as follows:-

1. Instead of having a 1 transition from Q2 to Q3, make a 1 transition from Q2 to Qa.
2. Instead of having a 1 transition from Q5 to Q6, make a 1 transition from Q5 to Qb.
3. Make a new 1 transition from Qa to Qb and a 0 transition from Qa to Q3.
4. Make a new 1 transition from Qb to Q9 and a 0 transition from Qb to Q6.

These changes in the provided DFA will allow it to satisfy given conditions. It simply counts input substring 1111 as two consecutive 111 and skips a step (of three intermediate states), increasing the count be 2.
> 3 votes

# Answer
> I feel I cannot do it with DFA as this will require to have some form of memory.

Why do you feel that a DFA which recognizes 5 1's needs a different kind of memory than one which recognizes three sets of 3 1's each? A DFA has memory (encoded in the state); the limitation is simply that a DFA has only a finite amount of memory. (An NFA is no different.) But in this case, you only need a finite amount of memory. Reading four consecutive 1s puts the automaton in the same state as reading three 1s, some 0s, and another three 1s.
> 1 votes

# Answer
The problem asks to draw a deterministic finite automaton (DFA), not a pushdown automaton or a Turing machine. If you cannot directly come up with a DFA then you can draw a NFA (or NFA with epsilon moves) and then transform it into a DFA accepting the same language as the NFA. Alternatively, if you can write a regular expression for that language then you could transform it into the corresponding NFA and then DFA. NFA, DFA, and regular expressions represent the same class of languages, namely, *regular languages* which means once you have a regular expression you can obtain a corresponding DFA or NFA and vice versa.

As for the pushdown automata and Turing machine, you certainly could design a PDA or a TM accepting that language. But remember, PDA and TM computationally are more powerful than FA, meaning that not all languages accepted by a PDA or TM can be accepted by a DFA/NFA, so you cannot always design a PDA or a TM for a language and then transform it into a DFA/NFA accepting that language. However, the opposite is true, every languages accepted by a FA is accepted by a PDA or a TM, but that is another story.
> 0 votes

# Answer
Quite a handful... as overlaps are allowed, you need pieces to recognize 111 (one trio), 1111 (two trios) and 11111 (three trios right there, done). Begin by 0s, none or as many as you like. Then the above, jumping off on 0 after the third 1 (to machinery to recognize at least two 111 following the same idea), loop back to the start if 10 or 110. After 1111 jump of to similar machinery to get the last 111.
> 0 votes

---
Tags: formal-languages, finite-automata, formal-grammars, compilers
---


# Question
Title: Why does this NFA having an empty symbol
I'm trying to understand the difference of DFA from NFA I have this example in my coursebook  Are the empty symbols at the start necessary? or can we do away with them to have something like this

# Answer
> 3 votes
Yes, in this example, your solution is fine.

Perhaps the example just wanted to show the use of epsilon transitions. Also, your approach would be more complicated in the case where one of the original initial states would have a loop. We cannot transfer that loop to the common initial state.

# Answer
> 1 votes
Whilst your answer correctly solves the tasks of recognising which strings belong to the regular expression, without the epsilon transitions the behaviour is entirely deterministic. This means that strictly speaking you have constructed a DFA, and not an NFA. It's a subtle difference and I would argue that this example probably isn't the best, but a strict professor would be justified in not giving full marks.

---
Tags: automata, finite-automata
---


title: Why do operating systems freeze?

text:
# Question
Title: Why do operating systems freeze?
I am currently writing from a computer on which a VM has just frozen due to exhausted RAM. I am obviously no expert in the field of operating systems but i know that they implement certain memory management methods so why can't my OS handle my alt-f4 request to kill the troublesome process in a reasonable time?

Why can't other processess still run normally?

Shouldn't operating system swap between active tasks so that my keyboard input reaches said process?

Operating system in itself should be of top priority with handling user input isn't that right?

Therefore my question remains: how come, despite all the round-robin and/or other scheduling mechanics my OS still freezes?

Thank You for all the answers. Cheers.

# Answer
> 2 votes
A "system freeze" is normally due to the system running out of some resource and spending it's limited resources left trying frantically to fix up the mess. I.e., too much CPU load, has no processing power left for the user. Memory overload, keeps trying to free memory and gets nowhere, no time left for the user (and no memory to load programs).

It might also be a deadlock (some tasks inside the system are holding resources others require, and are waiting for still others to be released, but that will never happen as everybody is waiting for somebody else's resources).

# Answer
> 1 votes
> Therefore my question remains: how come, despite all the round-robin and/or other scheduling mechanics my OS still freezes?

Despite all the scheduling algorithms,the real world scenario is different. The *freeze* can be seen as a result of resource exhaustion. Since the RAM is limited, OS then uses swapping but it causes thrashing also. Resources necessary for some part of the system to run are not available, due to being in use by other processes or simply insufficient.

Modern OS use pre-emptive multitasking.In these cases, a single thread getting stuck will not necessarily hang the system, it will be preempted when its time slice (time quantum)expires, allowing another thread to run. If a thread does hang, the scheduler may switch to another group of interdependent tasks so that all processes will not hang.However, thread which is stuck will still consume resources: at least an entry in scheduling, and if it is running (for instance, stuck in an infinite loop), it will consume processor cycles and power when it is scheduled, slowing the system further.

However, even with preemptive multitasking, a system can hang, and a misbehaved or malicious task can hang the system, primarily by monopolizing some other resource, such as IO or memory, even though processor time can't be monopolized.

Analyzing the Ubuntu using system monitor, I can say that often processes that blocks the file system will often hang the system. But there are many factors leading to it. It can also driver issues or some hardware malfunctioning. These all can cause the system to slow down.

---
Tags: operating-systems, os-kernel
---


# Question
Title: Prove or disprove {wtw^R | |w| = |t|} is context free
The language $S\_c$ defined as: $S\_c = \\{wtw^R \mid w,t \in \\{0,1\\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \\}$

It looks like the language can be "pumped" by context free pumping lemma, but the pumping lemma doesn't prove the language is context free. So I'm thinking of building a PDA that recognizes it. But I'm stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $w$ and $t$, then compare the values after $t$ which is string $w^R$. But still hard for me to come up a whole construction at this moment, any suggestions?

# Answer
Suppose $S\_c$ is context free. Then let $p$ be the pumping length and choose $s = 0^{2p}0^p1^p0^{2p}$ in $S\_c$ that satisfies the pumping lemma. Thus, we can break $s$ into $uvxyz$, with $|vxy| \leq p$ and $|vy| \geq 1$. And for all $i$, $uv^ixy^iz$ is a string in $S\_c$.

We have three cases.

1. $vy$ contains all 0s and these 0s can be chosen from either the beginning $0^{2p}$ of $s$, middle $0^p1^p$ of $s$ or the last $0^{2p}$ of $s$. Now, by pumping lemma, since $uv^ixy^iz \in S\_c$, for all $i$. We choose $i = 2$, so we have $s' = uv^2xy^2z = uvvxyyz$. Clearly, since $vy$ contains all 0s, and regardless which part of $s$ are chosen from, this string is the form of $wtw^R$ such that $|w|$ = $|t|$ = $w'$ with either $w$ is all 0's and $w'$ is not all 0s or vice verse. This implies that $w' \neq w^R$ or $w' \neq w$.
2. $vy$ doesn't contain any 0s in last $0^{2p}$ of $s$ (We choose in the last part of $s$, but it's essentially the same by choosing first or middle part of $s$). Similarly, either the length of $uv^2xy^2z$ is not multiple of 3 (since pumping will increase the number of 1's), or this string is the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ consists all 0s but $w'$ contains some 1s. Thus $w' \neq w^R$.
3. $vy$ contains some 0s and some 1s in last $0^{2p}$ of $s$. From pumping lemma, since $vxy \leq q$, $vxy$ must be sub-string of $0^p1^p$. Then, by pumping the string $s' = uv^ixy^iz$ for all $i$, the length is string is not multiple of 3 since pumping increases number of 0s or 1s, or the string is in the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ is all 0s but $w'$ is not all 0s.

Thus, we can conclude that all three cases above reach contradiction and hence $S\_c$ is not context free.
> 3 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: Prove {<M> | TM M on input 3 at some point writes symbol "3" on the third cell of its tape} is recursively enumerable but not recursive
Question: Let $$S = \\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape} \\}.$$ Show that $S$ is r.e. (Turing acceptable) but not recursive (decidable).

I'm bit confused about this question, I'm not even sure how exactly should I start an approach to it. As I study from Sipser's book, in general when we prove a language is undeciable, we use contradiction to show that if $S$ is decidable, then by doing some trick, $A\_{\text{TM}}$ is also decidable but it's not. Thus, $S$ is not decidable. However, this question also asked to show $S$ is acceptable. I'm thinking if we show that $S$ is undecidable, it's sufficient to see that $S$ is acceptable?(I'm totally not sure) Any suggestion?

# Answer
First we assume for the $S\_3$ is decidable and let TM $R$ be the decider for $S\_3$. With $R$, we can test whether $M$ writes symbol $\`\`3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $\`\`3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A\_{TM}$. If $R$ indicates $M$ writes symbol $\`\`3"$ on the third cell, we can do the simulation without looping. Thus, if TM $R$ exists, we can decide $A\_{TM}$, but we know that $A\_{TM}$ is undicidable, by contradiction, we can conclude that $R$ doesn't exist. Hence, $S\_3$ is undecidable.

Let's assume $S\_3$ is decidable so we can obtain contradiction by having TM $R$ decides $S\_3$, and construct TM $M'$ to decide $A\_{TM}$ as follows.

$M'$ = $\`\`$On input $\big \langle M, 3 \big \rangle$:

1. Run TM $R$ on input $\big \langle M, 3 \big \rangle$.
2. If $R$ rejects, $reject$.
3. If $R$ accepts, simulate $M$ to write symbol $\`\`3"$ on the third cell of its tape.
4. If $M$ has accepted, $accept$; if $M$ has rejected, $reject$."

Clearly, if $R$ decides $S\_3$, then $M'$ decides $A\_{TM}$. However, since $A\_{TM}$ is undecidable, so we know $R$ doesn't exist and hence $S\_3$ must be undecidable.
> 2 votes

---
Tags: formal-languages, turing-machines, computability, regular-languages, undecidability
---


# Question
Title: How do I determine the basic operation of this algorithm?
Admissions:

* Yes, this is a homework assignment.
* No, this is not me trying to outsource my homework to the internet.

I am honestly fazed by my teacher's explanation of the "basic operation", and the internet is not helpful either. I get lists that say what a basic operation *can be* (e.g. assignment, multiplication, comparison), and what it is *used for* (determining time complexity) but not how to determine it for a given algorithm.

Here is the algorithm in question.

```
// Problem: Search a given value K in a given array A by sequential search
//Input:  array A[0..n − 1] and a search key K
//Output: The index of the first element in A that matches K and −1 if there are no matching elements.

SequentialSearch(A[0..n − 1], K)
{
   i ←0
  while i < n and A[i] ≠ K do
  {
    i ←i + 1
  }
  if i < n
     return i
  else
   return −1
}

```

The question: is the basic operation assignment, or comparison?

Candidates that I see:

* Comparison: `A[i] ≠ K`
* Assignment: `i ←i + 1`

The problem is that both of these would work to determine time complexity. The comparison is executed 1 time in best-case and n times in the worst-case scenario. The assignment is executed 0 times in best-case and n-1 times in worst-case. Towards infinity, constants do not matter, so really they both work equally well.

So the irony is that I know the time complexity of this algorithm, but not the basic operation which I am supposed to determine to figure out the time complexity.

What is the logic to use here to figure out which one is the basic operation, and which one isn't?

# Answer
> 3 votes
"Basic operations" are whatever you choose. You may get different results based on your choice, which is great as it leads to understanding algorithms better! You may have seen the number of comparisons and swaps being analyzed independently in array sorting algorithms.

As a corollary, your professor can pick whatever they want. We can't possibly know their mind; you'll have to ask them.

That said, if you're after "time complexity", you want to count how often a *dominant* operation occurs. See here and here (section "A note on asymptotic cost"). In case of doubt, just count *all* candidate operations.

> Getting different results based on my choice is something I also think is not applicable here, as the two options I am struggling between have identical results in when going towards infinite input sizes.

In that case, the choice doesn't matter. Either both operations are dominant and your result is correct, or they are both not and you need to pick another operation entirely.

# Answer
> 0 votes
Yes, You will get different results base on what you choose as your basic operation. Following this view, this result makes no sense.

To choose a basic operation is to choose a constant unit to measure the complexities between different algorithms. It's like once you want to compare whether China or France is further from you, You can choose miles, meters even the hours you went there as your unit.

So just ensure you choose the same unit between the algorithms which you want to compare, then you can choose whatever you want. And don't forget your conclusion based on your choice may be various.

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


# Question
Title: Finding a Hamilton path in a Complete Euclidean Graph is in P
How is it possible to prove that this assert is not true?

# Answer
> 1 votes
Regarding to Popper's Falsifiability theory you can falsify this proposal by this assertion:

It is false if (and only if) to find (giving the result) **each Hamilton Path** in at least one Complete Euclidean Graph, **for every possible algorithm** has a cost greater than a polynomial expression of the number of items.

# Answer
> 2 votes
This assertion is, in fact, true. A complete graph (which doesn't even have to be Euclidean) always has a Hamiltonian path: number the vertices in an arbitrary order, start at the first one, then proceed in order to the last (and then back to the first to make a cycle if you want). Since the graph is complete, the edges you need will always exist.

Thus, the problem can be decided in $O(1)$, which is polynomial, so it is in $P$. The algorithm is trivial:

```
define doesThisCompleteGraphHaveAHamiltonianPath(G):
    return Yes

```

---
Tags: complexity-theory, graphs, np-hard
---


# Question
Title: How to Calculate Clock Rate for Processor?
Please can anyone help me to solve the following question, I have no idea to solve that .

# Answer
> 0 votes
I found the answer, thanks. Hope answer will help someone

---
Tags: computer-architecture, cache
---


# Question
Title: Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?
Consider the Traveling Salesman Problem: *Input*: $n$ cities, distances $c\_{ij}$ for each ordered pair $(i,j)$ of them.

*Output*: Find a shortest round tour visiting every city exactly once.

I came across the following ILP formulation, where we introduce a variable $x\_{ij} \in \\{0,1\\}$ for each pair of cities $i,j$ where $x\_{ij} = 1$ means arc $i,j$ is part of the tour. Then we have:

**Minimize** $$\sum\_{1 \leq i,j \leq n} c\_{ij} x\_{ij}$$

**Subject to** $$\forall k = 1, \dots, n: \sum\_{1 \leq i \leq n} x\_{ik} = 1$$ $$\forall k= 1, \dots, n: \sum\_{1 \leq j \leq n} x\_{kj} = 1$$ $$\forall \subsetneq S \subsetneq \\{1, \dots, n\\}: \sum\_{i,j \in S} x\_{ij} \leq |S| -1 $$

While I understand the purpose of the first two constraints to make sure there is only one incoming and one outgoing edge per city, I do not understand the purpose of the third constraint. From what I read, this constraint is to make sure that solutions consisting of several disconnected tours are not possible - But how is this enforced by the third constraint and why are disconnected subtours not prevented by the first two constraints already? If we have two disconnected subtours, then at least one vertex must have an incoming edge but no outgoing edge, no?

# Answer
Consider this example:

Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of the two connected components for $S$ it violates the inequality.
> 4 votes

---
Tags: linear-programming, traveling-salesman
---


# Question
Title: How can Kruskal's algorithm return different spanning trees?
We assume that we have the same graph G.

In introduction to Algorithms by Cormen it's said that it\`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

> Suppose that A is an empty set of edges. Then, make any cut that has (u, v) crossing it. Then, since that edge is of minimal weight, we have that (u, v) is a light edge of that cut, and so it is safe to add. Since we add it, then, once we finish constructing the tree, we have that (u, v) is contained in a minimum spanning tree.

What does it mean to make a cut? I\`m familiar with Kruskal's algorithm but nowhere in the process do I see cuts being made. It's either we unite two trees and add the edge to A or we reject the edge and continue on.

# Answer
> 2 votes
Cuts aren't made as part of Kruskal's algorithm; they are used in a proof that it always returns a minimum spanning tree. See e.g. here.

But you don't need them to answer the question in the title; instead, take as your graph a triangle with all 3 edges the same weight. Then any order on these edges is allowed and Kruskal's algorithm will return the tree consisting of the first 2 edges, whichever they are.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Clarification on "clause learning" in DPLL algorithm
I am struggling to understand the idea of conflict-driven clause learning, in particular, I can not understand why the clause we 'learned' is a substantially new (i.e. the clause database does not already contain it, neither any subset of it). Here is what Knuth in his book says:

> A conflict clause $c$ on decision level $d$ has the form $\overline{l} \lor \overline{a}\_1 \lor ··· \lor \overline{a}\_k$, where $l$ and all the $a$’s belong to the trail; furthermore $l$ and at least one $a\_i$ belong to level $d$. We can assume that $l$ is rightmost in the trail, of all the literals in $c$. Hence $l$ cannot be the $d$th decision; and it has a reason, say $l \lor \overline{a}′\_1 \lor ··· \lor \overline{a}′\_k$. Resolving $c$ with this reason gives the clause $c′ = \overline{a}\_1 \lor ··· \lor \overline{a}\_k \lor \overline{a}′\_1 \lor ··· \lor \overline{a}′\_k$, which includes at least one literal belonging to level $d$. If more than one such literal is present, then $c′$ is itself a conflict clause; we can set $c \leftarrow c′$ and repeat the process. Eventually we are bound to obtain a new clause $c′$ of the form $\overline{l}′ \lor \overline{b}\_1 \lor ··· \lor \overline{b}\_r$, where $l′$ is on level $d$ and where $b\_1$ through $b\_r$ are on lower levels.
>
> **Such a $c′$ is learnable, as desired, because it can’t contain any existing clauses. (Every subclause of $c′$, including $c′$ itself, would otherwise have given us something to force at a lower level.)**

I can understand why the clause database has no subset of $c'$ that contains $\overline{l'}$ (because $\overline{l'}$ would have been forced (i.e. unit-propagated) at level lower than $d$), but what contradicts to the existence of clause, let's say, $\overline{b\_1}\lor\overline{b\_2}$?

# Answer
> 3 votes
All the literals in a conflict clause are set *false* by definition, else there would be no conflict. So if the clause $\overline{b\_1}\lor\overline{b\_2}$ existed, one of those false literals would have caused that clause to go unit before we reached the current level, which in turn would have forced one of the $\overline{b\_1}$ or $\overline{b\_2}$ literals true. But we already know that those literals must be false, so we have a contradiction. This contradiction shows that the clause $\overline{b\_1}\lor\overline{b\_2}$ cannot exist. The reasoning is the same for all clauses that are subsets of the conflict clause.

---
Tags: satisfiability, sat-solvers
---


title: Question of checking the $n$th root

text:
# Question
Title: Question of checking the $n$th root
**Problem:** Input : $n$, $k$

Check : Is $\frac{k}{4h -1} = n^{\frac{1}{h}}$? for any $ 0 \le h \<= n$.

**Question:** What is the fastest algorithm for the above problem assuming the model of computation is RAM?

# Answer
The function

$$f(h) = \left( {k \over 4h-1} \right)^h$$

is monotonically decreasing for $h \< k+1/4$, and monotonically increasing for $h\>k+1/4$. (How do I know? Set $f'(h)=0$ and solve for $h$.)

Therefore, one approach is to use a binary search on $h$ within the range $\[0, \min(k+1/4,n)\]$ to search for $h$ such that $f(h)=n$, followed by another binary search on $h$ within the range $\[k+1/4, n\]$. You could also replace the binary search with a method with faster convergence, such as Newton's method.
> 2 votes

# Answer
The right hand side is undefined if h=0, so 1 \<= h \<= n, and there is no solution if n=0. h=1 is a solution if and only if k=3n. So we can assume n \>= 2, h\>=2.

The h-th root of an integer n is an integer if n is an h-th power, and irrational otherwise. So we have 4h-1 dividing k, and n is exactly a a h-th power. We can check which powers of p divide n, for primes p = 2, 3, 5, 7, ..., 97 for example and if any primes divide n, h must be a divisor of the gcd of these numbers. This would vastly reduce the choices for h. If there are no divisors \< 100 then n \>= 101^h which also reduces the choices.
> 0 votes

---
Tags: algorithms
---


title: Stuck on proof in Coq

text:
# Question
Title: Stuck on proof in Coq
This is an exercise from Software foundations for my discrete math & functional programming class. I am a little stuck with the end of the code because it works for the first two examples but it doesn't work for my false case and I can't figure out why...

(** **** Exercise: 2 stars, standard (eqblist)

  Fill in the definition of [eqblist], which compares

  lists of numbers for equality. Prove that [eqblist l l]

  yields [true] for every list [l]. *)

Fixpoint eqblist (l1 l2 : natlist) : bool :=

 match l1, l2 with

 | nil, nil => true

 | (h1 :: t1), (h2 :: t2) => true

 | _,_ => false

 end.

Example test_eqblist1 :

 (eqblist nil nil = true).

Proof. reflexivity. Qed. (works)

Example test_eqblist2 :

 eqblist [1;2;3] [1;2;3] = true.

Proof. reflexivity. Qed. (works)

Example test_eqblist3 :

 eqblist [1;2;3] [1;2;4] = false.

Proof. reflexivity. Qed. (this one doesn't work! )

```

# Answer
Your definition is wrong. Every pair of lists will evaluate to `true`. You need to actually check that h1 and h2 are the same, and that the lists are the same length.

If I recall the exercises correctly, you may want to look back at `beq_nat` and `andb`.
> 1 votes

---
Tags: proof-techniques, coq
---


# Question
Title: Numerical Accuracy & Sorting Algorithms?
Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/25applications/

> Scientific computing is often concerned with accuracy (how close are we to the true answer?). Accuracy is extremely important when we are performing millions of computations with estimated values such as the floating-point representation of real numbers that we commonly use on computers. Some numerical algorithms use priority queues and sorting to control accuracy in calculations.

What "numerical algorithms" use priority queues and sorting like this?

# Answer
I'll give you a simple example.

Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue.

For the purpose of this example, I'm going to use decimal with four significant digits of precision just to illustrate the point.

The numbers are:

```
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e+0

```

That is, ten copies of `1e-4` and one copy of `1`.

This sum can be perfectly represented in our toy floating-point format:

```
1.001e+0

```

But the answer that you get depends on what order you do the additions! If you start at the top of the list and work your way down, the partial sums are:

```
1.000e-4
2.000e-4
3.000e-4
4.000e-4
5.000e-4
6.000e-4
7.000e-4
8.000e-4
9.000e-4
1.000e-3
1.001e+0

```

But if you start at the bottom and work your way to the top, the partial sums are:

```
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0

```

Clearly, you need to add the small numbers first. So here are two possible algorithms.

* Sort the numbers into ascending order, then sum them in that order.
* Insert the numbers into a priority queue. Remove the two smallest numbers, add them, and insert the sum back into the priority queue. Repeat until there is one number left.

Exercises:

1. Is there a set of numbers for which these two algorithms return different answers?
2. Is one of these algorithms better than the other, in the sense of always returning a more accurate final answer?
3. Can we do even better?
> 2 votes

---
Tags: algorithms, data-structures, sorting, floating-point, priority-queues
---


# Question
Title: Find and sort 2d array elements like radar
I don't know relevant keywords about this algorithm. I can show you visually

Any ideas are appreciated

# Answer
> 9 votes
For each of your points in the field, calculate the red angle:

Then sort all the (point, angle)-tuples by the angle.

# Answer
> 2 votes
Here's a way to sort points by angle in Swift:

```
let radarSortedPoints: [CGPoint] = points.sorted { pointA, pointB -> Bool in
    atan2(pointA.y, pointA.x) < atan2(pointB.y, pointB.x)
}

```

---
Tags: sorting
---


# Question
Title: Composition of functions computable in logspace
The **bit-graph** of $f\colon \\{0,1\\}^\* \rightarrow \\{0,1\\}^\*$ is the language:

$\text{BIT}\_f := \\{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\\}$

It is said that $f$ is **logspace computable** if $\text{BIT}\_f$ is decidable in space $O(\log n)$. Decidable means that there exist a Turing Machine $M$ such that:

1. if $\langle x,i \rangle \in \text{BIT}\_f$ then $M(\langle x,i \rangle) = 1$
2. if $\langle x,i \rangle \notin \text{BIT}\_f$ then $M(\langle x,i \rangle) = 0$

Prove that the composition $(f \circ g)(x)=f(g(x))$ of two logspace computable functions $f,g$ is also a logspace computable function.

Any hint on this exercise? What I tried so far is playing with the composition of the two Turing Machines associated with $f$ and $g$, but I didn't succeed because it always end up with a case analysis exercise.

# Answer
> 3 votes
The idea is quite simple. We are going to simulate running $M\_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M\_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M\_f$ attempts to read from the input tape, we invoke the machine computing $\mathrm{BIT}\_g$, which also uses up $O(\log n)$ steps; we know which input $i$ to give, since this is just the location of the head.

---
Tags: complexity-theory, turing-machines, space-complexity
---