# Question
Title: the meaning of heuristics in artificial intelligence
I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The section where the author discusses the mathematical reasons why the particles behave the way they do was entitled 'heuristics'. Does it, in any way, mean ... the mathematical rigour, methodology, convergence, etc?

Your insights would be helpful.

# Answer
Heuristics typically have very little to do with rigor. (But you can surely study them in a rigorous way). They are rule of a thumb methods for solving (usually computationally difficult) problems, and typically they perform quite well in practice. In other words, there might not be any formal guarantees on the solution quality you get by running a heuristic, but experience and empirical analysis shows they can be quite effective. Arguably, it is rarely the case we understand their behaviour well.

Sometimes, when heuristics are analyzed formally, they turn out be to approximation algorithms. That is, methods for solving a problem with a formal guarantee on the solution quality. For example, one might have observed a heuristic usually works well, and an analysis proves it will always give a solution which is at most twice the optimum.

Perhaps in your particular case, the section "Heuristics" contains explanations (more or less formal) as to why the heuristic behaves or is expected to behave in certain ways when run.
> 2 votes

# Answer
Heuristics or Heuristic value(s) are the approximations for your problem to reach the answer(goal). Let's say you have an algorithm that finds the shortest path from point A to Z. Now, if you go by predictions you may get lost as there're several other points in between your start & final position.

For an **analogy**, let's say you are traveling in a city, you don't know anything about the routes. To reach a certain place in that city, what you will do, you keep going on & on by taking advice from the people around you. Now, the time in which you reach the place depends on the quality of advice that the person gives to you.

Now, let's relate it. In the analogy, **you is your algorithm** that is trying to reach a certain place (goal) **&** the **heuristic value is the advice of the person**. Same as in the case of your AI algorithm, the better approximation (heuristic value) you have the less in time you reach your problem goal.

**Hope it helped!**
> 0 votes

---
Tags: terminology, artificial-intelligence, heuristics
---


# Question
Title: Is Artificial intelligence simply taking decisions on the basis of values produced by a machine learning model
I am researching on AI and its working. Whenever I try to search for AI algorithms, ML algorithms come up. Then, I read the differences between ML & AI. One of the key points mentioned was "AI is decision making" & "Machine learning is generating values and learn new things".

I come up with a conclusion that ML allows us to take generate some sort of values and using AI we can make decisions with those values.

But I am confused with "The weather forecast" problem. Our machine learning model will directly generate the decision that will it rain or not? **Is our ML model lies in the AI domain or I am wrong? Help me!**

# Answer
Artificial Intelligence is a very broad area of Computer Science which is intertwined with many other fields, and someone might argue that its definition is *the discipline that develops rationally acting systems*.

When it comes to Machine Learning, the generally accepted definition is programming computers to perform a specific task *without specific instructions* about the problem.

Being that broad of a field, AI comprises Machine Learning problems, but the difference between the two areas relies on **how** you devise your system:

* if you make use of problem-specific knowledge in your algorithm: you're outside the ML field;
* if you formulate your problem in a general-enough manner and use a generic algorithm: most likely you're inside the ML field.

I'm sure you have already seen this image from Nvidia a million times already, but it's intuitive to understand what's the relationship between AI and ML: the latter is part of the former.
> 1 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Is this big O notation format correct? $3^n = 2^{(O(n))}$
I am completing a university exercise deciding whether big notations are true or false.

I am stuck on this question :

> $$3^n = 2^{(O(n))}$$

I want to answer False as the format looks incorrect and I have never seen big O notation written is this way.

Is this a valid way to write big O notation?

# Answer
> 4 votes
Sure, that is a correct notation. It is also a correct statement. Essentially it is a compact way to say the following:

$\exists c\>0, \exists n\_0 \ge 0 : \forall n\>n\_0, 3^n \le 2^{c n} $.

You can pick any $c \ge \log\_2 3$ and $n\_0 = 0$.

# Answer
> 1 votes
Yes, this is a valid way to write big O notation, or at least it is used in multiple research papers that I have read. The notation $f(n) = 2^{O(n)}$ means that there exists a constant $c$ such that $f(n) = O(2^{cn})$, or further simplified that there exists a constant $c$ such that $f(n) = O(c^n)$.

# Answer
> 1 votes
I'd take it as a shortcut meaning: There is a function f(n) such that $3^n = 2^{f(n)}$, and f(n) = O (n).

Since big-O notation is just a handy shortcut for a rather long statement anyway, your statement is slightly pushing the boundaries, but I'd say it is correct.

# Answer
> 1 votes
Big-oh notations can be added, multiplied, and even exponentiated. But this is very confusing, what does it mean? The best way to think of it is as gnasher729 says: whenever you see $O(n)$ in an expression, you can replace that with some function $f(n)$ which is $O(n)$.

For example, $$ O(n) \cdot O(n) $$ means $f(n) \cdot g(n)$, where $f$ and $g$ are some unknown functions and $f \in O(n)$ and $g \in O(n)$. Similarly, $$ 2^{O(n)} $$ means $2^{f(n)}$ where $f$ is some unknown function such that $f \in O(n)$, that is $f(n) \le C n$ for some constant $C$. And for a more complex example, you can write something like $$ O(n^2) - O(n) = O(n^2) $$ What this true statement means is that, given some unknown functions $f$ and $g$ such that $f(n) \in O(n^2)$ and $g(n) \in O(n)$, $f(n) - g(n)$ is in $O(n^2)$, that is, $f(n) - g(n) \le C n^2$.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Is it possible to constract Moore or Mealy machine with a different size of input and output?
Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size.

I want to construct FSMs to produce different transformation patters:

1. copy 2 times: 11 -\> 11011, 101 -\> 1010101
2. trim: 011100 -\> 111, 000110 -\> 11
3. fill zeros by 1 between 1: 01000100 -\> 01111100, 01010 -\> 01110

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine) or should I switch to context free languages?

# Answer
> Can you please suggest is it possible to do it with FSM (Moore or Mealy machine)

The machine you are looking for is called a finite-state transducer. They can be defined in either Moore or Mealy variants. For the Mealy variant (which I believe is more common), you have a finite state machine where the edges are labeled with output, and the initial states are also written as initial edges that can have associated output. (That is so that output can be produced on the empty input, if desired).

There are two types of finite-state transducers: **one-way transducers** and **two-way transducers**. The difference is that:

* One-way transducers just read the input from left to right, like a normal state machine.
* Two-way transducers have, for each edge, a label which says whether they move left, right, or stay still. The input tape also has start and end symbols: for example, the input `001` would be written $\triangleleft 00 1 \triangleright$. The machine has a special "halting" state. It moves back and forth on the input tape, reading symbols and producing output, until it is finished.

Two-way transducers are more expressive than one-way transducers. For some of the tasks you listed, one-way transducers are enough, but all of them can be done with two-way transducers.

> 1. copy 2 times: 11 -\> 11011, 101 -\> 1010101

This can be done with a two-way transducer. It reads the input, producing it as output, then goes back to the start of the tape, produces a zero, and reads the input again, producing it as output again.

> 2. trim: 011100 -\> 111, 000110 -\> 11

A one-way transducer can do this. It only needs one state; then depending on the input symbol, it either produces output or produces no output.

> 3. fill zeros by 1 between 1: 01000100 -\> 01111100, 01010 -\> 01110

A one-way transducer can do this. You should be in a different state depending on whether you want to fill the zeros, or leave them be, and then switch between these states whenever you encounter a 1.

> or should I switch to context free languages?

I hope not! Context free languages are much more complex and difficult to work with, and not necessary for the kinds of tasks you list.
> 3 votes

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


title: Oracle query’s required

text:
# Question
Title: Oracle query’s required
The variables $a,b,c \in \\{0,1\\}$, thus $a^k, b^k, c^k \in \\{0,1\\}$

I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of products such as this one $(1-a+ab)(1-b+bc)(b-bc)$. There could be more variables and more brackets to expand.

Do I require a single FP query to do this or something more?

---

edit:

Input: $(1-a+ab)(1-b+bc)$

Expand: $a b^2 c - a b^2 - a b c + 2 a b - a + b c - b + 1$

Apply property of idempotence: $a b c - a b - a b c + 2 a b - a + b c - b + 1$

Simplify: $1 - a - b + ab +bc$

Extract coefficients: \begin{matrix} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ ac & 0 \\ bc & 1 \\ abc & 0 \end{matrix}

Question: What is the 'weakest' oracle capable of extracting the coefficients above from the input?

# Answer
Your problem is #P-hard. Indeed, given a #SAT instance with variables $x\_i$ and clauses $C\_j$, let $\kappa\_{i,b}$ be the product of the clauses $C\_j$ satisfied by the truth assignment $x\_i=b$, and consider $$ P = \prod\_i (\kappa\_{i,0} + \kappa\_{i,1}). $$ The coefficient of $\prod\_j C\_j$ in $P$ is the number of satisfying assignments.

In the other direction, the special case where the input formula is $\Pi\Sigma\Pi$ (that is, the product of polynomials) is #P-complete. Suppose that we are interested in the coefficient of some monomial $m$ in $\prod\_k P\_k$, where the $P\_k$ are polynomials. Substitute zero in all variables not appearing in $m$. Now guess one term from each $P\_k$, and accept if the terms together cover $m$.
> 2 votes

---
Tags: complexity-theory, complexity-classes, oracles
---


# Question
Title: Encoding System that Assign Same Number of Bits for Each Character
I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that is not what I get (**please see the below python code and corresponding output**). For example, character `i` is represented by `1101001`, which is 7 bits long, but character `!` is represented by `100001`, which is 6 bits long.

Is there any encoding/decoding system where each character takes same amount of bits?

```
content = open('a.txt', 'r').read()
test_str = content
# using join() + ord() + format()  ... Converting String to binary

Binary = ' '.join(format(ord(i), 'b') for i in test_str)

#Decimal=int(Binary, 2)

# printing original string
print("The original string is : " + str(test_str))
# printing result
print("The string after Binary conversion : \n" + str(Binary))

```

**Output:**

```
The original string is : Hi! Is there a solution?
The string after Binary conversion :
1001000 1101001 100001 100000 1001001 1110011 100000 1110100 1101000 1100101 1110010 1100101 100000 1100001 100000 1110011 1101111 1101100 1110101 1110100 1101001 1101111 1101110 111111

```

# Answer
> 0 votes
The usual way to solve this problem is by adding leading zeroes. So `i` would still be represented by `1101001`, while `!` will be represented by `0100001`.

This is similar to how you digital clock might use 06:40 for 6:40, or 12:05 for 12:5.

---
Tags: information-theory, coding-theory, encoding-scheme
---


# Question
Title: Argument in proving that function is not polynomial time in bit length of input seems faulty
I am currently solving a question that asks which of the following functions can be calculated in polynomial time:

$$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor}, \lfloor \sqrt{n} \rfloor, \text{the smallest prime factor of } n, \text{the number of prime factors less than }n.$$

In proving the first one, I thought $n! \geq n$ and the input size is $\log\_2 n$ so the output cannot even be written in polynomial time. So then clearly the calculation cannot be done in polynomial time.

But then I thought I must have some misunderstanding, since by that logic even just calculating $n$ from the input (that is, the identity function) should not be polynomial time. But that's clearly not possible.

What is the problem in my thinking, and instead how should I be thinking about these?

# Answer
You should measure the length of the output in the same way you measure the length of the input.

For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$.

The factorial function, in contrast, has much too long output length. Indeed, if the input is $n$, then by Stirling's formula, the length of the output is $\Theta(n\log n)$, which is exponential in the input length $\Theta(\log n)$.
> 1 votes

---
Tags: complexity-theory, time-complexity, polynomial-time
---


# Question
Title: What is a good method for modelling combinatorial tree (sport competition results)?
Probably newbie question here, please point me out to relevant theories/tutorials if needed :

* let say I want to evaluate the probabilities of the final rankings for a sport competition
* the competition involved 8 teams, but I can simplify the problem to 4 contestants (say A - B - C - D)
    + the competition is splitted into `n` journeys during which every team faces another team (and only one). So with 4 contestants, I have 2 matches per journey
    + at the end of a match, 6 different points attributions are possible (depending on the score)

After one journey, there are 36 different possible combinations in terms of team's points. So the model looks like a tree with a journey at each level.

Even if I simplify the situation to 2 journeys left, I can't think of a elegant way to implement this problem rather than "manually" creating the tree with all the possible combinations at each level and counting the leaves ?

I'm not familiar with this kind of problem so I'm not sure about the path forward.

# Answer
> 0 votes
I can't follow how you get 30 combinations, you have 2 matches per journey each of the 2 matches can result in 5 different attributions, so you get 5\*5 = 25 different attribution per match. At each journey there are 3 possibilities to make 2 matches. So the result would be 25/3 + 25/3 + 25/3 = 25 different point attributions.
Did I got something wrong?

You want to calculate how many different point attributions there are after n journeys and the probabilities to make a match are the same for every combination at every journey?

# Answer
> 0 votes
It is straightforward to write a program that enumerates all 36 different combinations, computes the probability of each, and aggregates them. Or, equivalently, you can think of this as creating the entire tree. A computer can do billions of operations in a second, so doing this for 36 different combinations should be completed so fast it is done before you are even aware it started.

If you're trying to do it by hand rather than with a computer, this isn't a question about computer science and it belongs on Math.SE rather than here.

---
Tags: combinatorics
---


# Question
Title: Articulation points (or cut vertices), but only subset of vertices need to be connected
I know we can find all articulation points efficiently in a graph using DFS.

But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is a path between them). How to efficiently find all nodes (vertices) which removal will cause at least one of the mentioned pairs to be disconnected (can't communicate with each other)?

For example, we can have different cases for image below (undirected graph):

1. If pairs are A-B and C-D, then 2 is not vertex cut, because pairs remain connected.
2. If pairs are A-C and B-D, then 2 is vertex cut, because pairs can't communicate (there is no path between them).

If we know set of pairs that need to communicate, what is the most efficient way to find all "vertices cuts"?

# Answer
> 1 votes
I believe this can be computed in linear time, as follows:

Compute the block-cut tree. This can be done in linear time.

Preprocess the tree so that you can answer least common ancestor queries in constant time.

Given a pair $u,v$ of vertices, find the biconnected components they are contained in, then find their least common ancestor in this tree, call it $a$. Now mark all tree nodes along the path from $u$ to $a$ and from $v$ to $a$ (excluding $u$ and $v$ themselves).

Run this algorithm for each pair.

Finally, output all cut vertices (articulation points) that are marked.

I suggest that you first sort the pairs $(u,v)$ by height of their lca $a$, so that you start first with the pairs whose lca is closest to the root, and then progress on to ones that are farther from the root. With this ordering, one can then apply the following optimization: when traversing upwards from $u$ to $a$, if you encounter a node in the tree that is already marked, you can stop the traversal early.

With these optimizations, the running time will be linear. You can compute the block-cut tree in linear time. You can also compute the least-common ancestor in constant time. Finally, the time to do the traversals will be linear in the number of nodes in the graph plus the number of pairs, since you visit each node at most once during the traversals (if it has been visited previously, you terminate that traversal).

# Answer
> 0 votes
Let $P$ be the set of pairs of vertices that need to communicate and let $n$ be the number of vertices of the graph.

Compute the block-cut tree $T$ of your graph and root it in an arbitrary vertex. Remove from $P$ all pairs that belong in the same block. For any vertex $v$ of the graph, let $b\_v$ be the vertex of $T$ representing the block in which $v$ belongs.

For each of the surviving pairs $(u,v) \in P$, compute the lowest common ancestor $LCA(b\_u, b\_v)$ of $b\_u$ and $b\_v$ in $T$. This requires $O(n + |P|)$ time using, e.g., Tarjan's algorithm.

For every pair $(u,v) \in P$, the cut vertices that disconnect $u$ from $v$ are exactly those that appear in the (unique) path of $T$ from $b\_u$ to $LCA(b\_u, b\_v)$ or in the (unique) path of $T$ from $b\_v$ to $LCA(b\_u, b\_v)$.

These vertices can be found efficiently by visiting $T$ in postorder. While visiting a vertex $x$, keep track of a special vertex $s\_x$. This vertex might not always exist, but if it does it will always be an ancestor of $x$. The meaning of $s\_x$ is the following: all cut-vertices in the path from $x$ to $s\_x$ disconnect at least one pair in $P$.

The visit of a generic vertex $x$ proceeds as follows:

* 1. Let $x\_1, x\_2, \dots$ be the children of $x$ in $T$, and set $s\_x$ to the vertex of lowest depth in $T$ among $s\_{x\_1}, s\_{x\_2}, \dots$, if any.
* 2. If $x$ represents a block $B$:
        + 2.1. For each pair $(u,v) \in P$ such that $\\{u,v\\} \cap B \neq \emptyset$, set $s\_x$ to the lowest vertex among $s\_x$ itself (if $s\_x$ exists) and $LCA(u,v)$.
* 3. If $x$ is a cut-vertex, $s\_x$ exists, and $x$ is a descendant of $s\_x$ (a vertex is a descendant of itself):
        + 3.1. Report $x$ as a cut-vertex disconnecting a pair of interest.

Step 1 requires time proportional to the number of children of $x$ in $T$, therefore the total time spent in this step will be $O(n)$. The overall time required to perform step 2 is $O(n+|P|)$ after a $O(|P|)$ preprocessing that associates the pairs in $P$ to the corresponding blocks. Finally, step 3. requires constant time per vertex (since the ancestor-descendant relation can be checked in constant time after a $O(n)$ preprocessing).

---
Tags: algorithms, graphs, connected-components, depth-first-search
---


# Question
Title: Computational complexity of counting symbols
Consider the counting function $\\{x\\}^\* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$.

I am confused about the (asymptotic) complexity of computing this function, *where the output should be represented in a non-unary system (e.g., binary)*. My intuition strongly suggests that this should be linear, i.e., $O(n)$ where $n$ is the number of occurrences of the symbol $x$ in the input.

As far as my understanding goes there are multiple interpretations of computation - e.g.,

* single-band Turing machines, for which my best idea has run time $\Omega(n^2 \log n)$ I think (the $\log n$ comes from the assumption that the binary successor function has $\Omega(n)$ run time, where $n$ is the length of a binary representation of a natural number, and the $n^2$ comes from the assumption that the Turing machine has to travel over all the $x$'s to reach its current count),
* multi-band Turing machines, for which I think I have an idea of run time $\Omega(n \log n)$,
* random-access machines, which I don't know at all.

So my question is the following.

*What is the computational complexity of the counting function in the various models of computation? Is it linear in any of them?*

If at all relevant, I ask from the point of view of abstract algebra, where I am trying to assess the computational complexity of the word problem in some specific group.

# Answer
Turing machines are a nice model with several advantages, mostly their simplicity, but they are not the first choice when analyzing algorithms. Algorithms are typically implicitly analyzed on the RAM machine model, and in some cases, on the BSS model.

Here are some comments on the computational complexity of counting in various models:

**Single-tape Turing machine:** These are only considered since it is relatively easy to prove lower bounds on them. They are even less realistic a computation model than multi-tape Turing machines.

**Multi-tape Turing machine:** It is a standard example in amortized complexity that an increasing counter can be implemented using $O(1)$ amortized bit operations. This is because half the time, only one bit changes, one quarter of the time, only two bits, and so on, for a total number of changed bits which is $1/2 + 2/4 + 3/8 + \cdots = 2$. The Turing machine complexity is linear in that, and so counting can be implemented in $O(n)$.

**RAM machine:** A RAM machine consists of finitely many registers and a random-access memory. The registers are $O(\log n)$-bits long, where $n$ is the size of the input. Reasonable operations on registers take constant time. In particular, increasing a counter that can count up to $\mathit{poly}(n)$ takes $O(1)$ *worst-case* time. In particular, your function will run in $O(n)$.

**BSS machine:** One has to be careful when performing arithmetic on large numbers. On the RAM machine, arithmetic takes constant time only if the magnitude of the operands is $\mathit{poly}(n)$. A BSS machine allows access to special registers which store values in some field, say the real numbers. You can perform constant-time arithmetic and comparisons, but not functions like floor. You are also not allowed to use such values for indexing. (If you don't limit yourself enough, you will soon be solving SAT in polynomial time.) You can think of a BSS machine as accommodating floating-point operations, which in practice take constant time, while ignoring the finite precision involved in them.
> 6 votes

---
Tags: complexity-theory, turing-machines, computation-models
---


# Question
Title: Can one determinize finite automata over infinite trees?
I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance conditions.

I know that over words, all these automata accept the same languages, except deterministic and universal Büchi automata, as well as deterministic and nondeterministic co-Büchi automata.

I also know that over trees, nondeterministic and alternating Muller, Rabin, Streett, and parity automata accept the same languages, and strictly more languages than nondeterministic and alternating Büchi automata.

But I hardly know anything about deterministic tree automata, and I'm having a hard time finding more in the literature. And this captures my main question, whether one can determinize nondeterministic automata over infinite trees.

After all, they are definitely used. For example, in reactive LTL synthesis, we often convert the formula to a nondeterministic Büchi word automaton, then to a deterministic parity word automaton, from which we derive a deterministic parity tree automaton.

Also note that I didn't mention the co-Büchi case when it comes to trees. I just know that, again in reactive LTL synthesis, we can alternatively convert the negated formula to a nondeterministic Büchi word automaton, then to a universal co-Büchi word automaton for the original formula, from which we can derive a universal co-Büchi tree automaton. But that alone doesn't really say anything about the relation of deterministic parity tree automata and universal co-Büchi tree automata, or does it?

# Answer
> 2 votes
This may be not explicitly spelled at many places in the literature, as deterministic tree automata are unable to capture specifications that are only expressible in branching-time logics.

Take for instance the property "There exists a node in the tree labeled with atomic proposition $x$" - this is equivalent to the CTL formula $\mathit{EF\\,} x$. This one cannot be represented as a deterministic tree automaton, but is easy to express as a non-deterministic Büchi tree automaton. The reason is that a tree automaton accepts a tree $\langle T, \tau \rangle$ if *all* branches in the run tree for $\langle T, \tau \rangle$ are accepting. With non-determinstic tree automata, one can route the obligation to see an $x$ to somewhere in the tree. With deterministic automata, this is just not possible and thus one can only express $\mathit{AF}\\, x$ in this form.

Hence, non-deterministic tree automata cannot be determinized in general.

---
Tags: automata, trees
---


# Question
Title: Finding sequence of pairs with second element of previous pair matching first element of next pair
I am interested in efficient ways of doing certain problem.

I have list of $n$ pairs, where $n$ is usually a few houndred thousands and each pair's element is an integer (let's assume it is integer from $0$ to $10000$) and I am trying to find a sequence such that it start and ends at chosen integer (we can assume it is eg. $0$) and second element of previous pair matches first element of next pair. So as an example, if we have set of pairs $\\{(0,1), (1,3), (3, 2) (3,0)\\}$ the valid sequence would be eg. $(0,1), (1,3), (3, 0)$. If there is a few answers then I can find arbitrary one. Moreover it is no certain that my list of pairs actually has a solution. If it does not have solution, then the method should return no valid solutions.

I think that maybe some kind of dynamic programming could be useful here, but I don't really have an idea for something better than just checking all the options, which I am almost certain is quite bad. Do you have any interesting insight about this problem?

# Answer
> 1 votes
The integers of your problem form nodes, the pairs form directed edges. Then you can use Tarjan's strongly connected components algorithm to find the groups of nodes that form a cycle.

---
Tags: algorithms
---


# Question
Title: Space complexity of Travelling Salesman Problem
I am having trouble coming up with the space complexity of the TSP algorithm.

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($N!$) where N is the number of cities/nodes/vertexes.

Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($N!$), but the site says the space complexity is O($2^{N}$)

Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.

Thank you

# Answer
The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space requirements are $O(n\log n)$.

The dynamic programming solution, as mentioned in the comments, uses a table of size $O^\*(2^n)$. This is much more memory than the brute force solution, but the complexity is exponential instead of factorial, which is much better.

(The notation $O^\*$ means that we ignore polynomial factors.)

In fact, every problem in NP can be solved using polynomial space, using a brute force approach that simply goes over all possible witnesses, and for each of them, verifying (in polynomial time per witness) whether it is a valid witness. This extends the brute force algorithm for TSP.
> 4 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, space-complexity, traveling-salesman
---


# Question
Title: Efficiently remove nodes from a connected graph
Suppose you have a connected graph and want to remove `k` nodes such that the result is still connected. How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind. Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices. If you have more than `k` leaves then you're done, but in any tree you're only guaranteed 2 leaves. So you may need to reiterate the process until you've removed `k` vertices.

That implies `O(k)` runs of a tree search. Does a more efficient algorithm exist? I don't think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren't articulation points now turn into articulation points.

# Answer
> 1 votes
Let $G$ be your graph. Compute any spanning tree $T$ of $G$. Perform a postorder visit of $T$, and keep track of the set $D$ of the first $k$ vertices visited ($T$ and $D$ can be computed by the same DFS visit).

The graph $G'$ obtained by deleting the vertices in $D$ from $G$ is still connected (and $T-D$ is a spanning tree of $G'$). To prove this notice that if $v \in D$, then all descendants of $v$ in $T$ must belong to $D$ as well.

---
Tags: algorithms, graphs, connected
---


# Question
Title: Intersection algorithim for finding the intersection points of two arbitrary mathematical curves
I'm looking for an intersection algorithm for finding the intersection points of two arbitrary mathematical curves. Websites like Desmos, GeoGebra, and WolframAlpha allow you to graph and/or input two(Or more but I'm only interested in two) curves to find their intersection points. I know all of the services I've listed have some form of API, my problems with those APIs are the technical and practical restrictions. Therefore, I'd like to just use the algorithms they use under the hood. Problem comes when I don't even know the names of those algorithms or even whether they're public domain. I've done some searching around but I can't seem to find what I'm looking for. So I guess what I'm asking for are some basic design descriptions/requirements for these algorithms so I can implement one of them. I figured this problem wasn't really a question for the mathematics StackExchange or StackOverflow So I decided to place it here. Let me know if that's a problem.

# Answer
> 1 votes
Nevermind, I am big dumb-dumb. I realized I could easily just use the Newton–Raphson method or the Bisection method.

---
Tags: algorithms, mathematical-programming
---


title: Show that NP∩coNP =∅

text:
# Question
Title: Show that NP∩coNP =∅
I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP? I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find a language that is in both NP and coNP, but I'm not sure how to prove any examples of that.

I know that I can prove L and L complement both exists in P and therefore NP, but I don't know how to relate this to coNP.

# Answer
Read the definition of NP and co-NP. By that definition, every problem in P is automatically both in NP and co-NP. There’s nothing to prove, that’s how they are defined.
> 2 votes

---
Tags: np, co-np
---


title: What are $(S,\Sigma)$-CCCs?

text:
# Question
Title: What are $(S,\Sigma)$-CCCs?
I was reading this and I was trying to understand the definition of $(S,\Sigma)$-CCC. The first requirement says:

> a mapping \[\[\_\]\] : S → |C|, associating some object \[\[s\]\] ∈ |C| to any s ∈ S;

which I find very confusing and having a hard time understanding what it means. What is $S$ and what is $\Sigma$?

why do all the other requirements mean intuitively?

# Answer
The meaning of $S$ and $\Sigma$ is defined on slide 6. $S$ is a set of base types (for example, natural numbers $\mathbb N$, Booleans $\mathbb N$, etc.): these are just formal symbols. $\Sigma$ is a set of operators, which included constants and functions (for example, $0 : \mathbb N$, $\text{true} : \mathbb B$, $\text{not} : \mathbb B \to \mathbb B$, etc.): these are pairs of an element of $S$ and a formal symbol. In the definition on slide 7, they seem to be limiting the operators to just constants.

The mapping $⟦-⟧ : S \to \mathrm{Ob}(\mathcal C)$ gives us an interpretation of a base type in the category $\mathcal C$: given any type $A \in S$, we have an object $⟦A⟧ \in \mathcal C$ interpreting that type.

They overload notation and also define a function $⟦-⟧: \Sigma \to \mathcal C^\to$. We interpret each constant $(c : A) \in \Sigma$ as a morphism $⟦c⟧: 1 \to ⟦A⟧$, where $1$ is the terminal object (called $\star$ in the lecture slides). This aligns with the usual interpretation of terms $\Gamma \vdash t : A$ as morphisms $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Together, both of these mappings $⟦-⟧$ allow us to interpret a signature for a simply-typed $\lambda$-calculus inside a cartesian-closed category, which is the first step in showing the equivalence between simply-typed $\lambda$-calculi and cartesian-closed categories.
> 1 votes

---
Tags: programming-languages, semantics, category-theory
---


title: Is `→` a type operator?

text:
# Question
Title: Is `→` a type operator?
In *Types and Programming Languages* by Pierce,

> The level of types contains two sorts of expressions.
>
> First, there are proper types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true does not.)
>
> Then there are type operators like Pair and λX.X→X, which do not them- selves classify terms (it does not make sense to ask “What terms have type λX.X→X?”), but which can be applied to type arguments to form proper types like (λX.X→X)Nat that do classify terms.

Is  a type operator?  seems to me to take two types as arguments and return a function type.

Does it belong to some kind?

I might miss it, but does TAPL say anything about it?

Similar questions for

* `x` (for pairing two types, e.g. `T1 x T2`, c.f. Ch11).
* `∀X.` in universal type `∀X.T` in Figure 23-1 of Ch23 on p343
* `{∃X,}` in existential type `{∃X,T}` in Figure 24-1 of Ch24 p366
* `λX:: .` in type operator abstraction `λX::K.S` (c.f. Figure 29-1 in Ch29 on p446)
* Space  in type operator application `T1 T2` (c.f. Figure 29-1 in Ch29 on p446)

Thanks.

# Answer
Yes, these can all be viewed as operators at the type level, but they're not all completely analogous. Most of these are type constructors in that they're formation operators for types, though type-level application is simply a type operator.

$\to$ may be viewed as an ordinary type constructor. In Pierce's notation, this is denoted $\lambda X . \lambda Y . X \to Y$. You can just as well think of it as binary algebraic structure on the set of types $(-) \to (-) : \star, \star \to \star$, where $\star$ is the kind of types. (If you have a higher kind above this, it could live there, but this depends on precisely what your calculus is.) The product of types, $\times$, may be viewed similarly. Type-level application is also a type operator.

$\forall X$, $\exists X$ and $\lambda X$ are also type constructors, but they're a little different from the previous two in that they're *binding operators*: just like the $\lambda$ term operator, they bind a variable in the context (though in this case, a type variable). This means these type constructors are no longer algebraic operators à la universal algebra like the simple type constructors $\to$ and $\times$.
> 2 votes

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: What are the differences and relations between a type constructor and a type operator?
What are the definitions of a type constructor and a type operator? What are their differences and relations? I think a type operator is a function whose parameters are n types and return is a type. A type constructor also means the same thing. I use them exchangeably. But some reply used type constructor when my question (I forgot where) used type operator. In *Types and Programming Languages* by Pierce, the index says

> type constructors, see type operators

Ch 29 says **informally** that

> these type-level functions, collectively called type operators, more formally.

Is it correct that type operators/constructors are used only and exactly to create algebraic types, and algebraic types are created only and exactly by type operators/constructors?

Is `Ref` in `Ref T` a type operator/constructor? Is `Ref T` an algebraic type?

Thanks.

# Answer
> 1 votes
These sorts of terms in type theory are not always used completely consistently. However, *type operators* are generally type-level functions: that is, they take as arguments some number of types and return a single type. *Type constructors* are a specific kind of type operator for which the return type is free in the sense that it is a new type on its arguments.

Generally speaking, if you have a type operator $T: \star \to \star$ and for any type $A : \star$, you have a type $T(A) : \star$, which is not prima facie equal to anything else, then it is called a type constructor.

For example, $\times$, $+$ and $\to$ are all type constructors. Type-level application is not, because the application of $(\lambda X . X + X)\ Y$ is reducible to $Y$, i.e. the application of the type operator is equal to some other type.

In your example, $\mathrm{Ref} : \star \to \star$ would be considered a type constructor. If by "algebraic type" you mean "algebraic data type", then $\mathrm{Ref}(T)$ is not an algebraic data type, because it's part of the type system rather than formed as a composite type out of products and sums.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements
Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer. We want to find $k$ *distinct* indices from $\\{1, 2, \ldots, n\\}$, denoted as $i\_1, \ldots, i\_k$, such that

$\sum\_{p, q = 1}^k A\_{i\_p, i\_q}$

is maximized. In words, we seek $k$ rows and the corresponding $k$ columns, such that the intersected $k^2$ elements of $A$ have the largest sum.

This problem can be formulated as a quadratic assignment problem, which is NP-hard and admits no polynomial time algorithm with constant approximation bound. I'm just wondering if for this specific problem (as a special case of quadratic assignment), there exists a poly-time algorithm with constant approximation bound. Thank you.

# Answer
There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to determine whether there is a choice of indices for which the sum equals $\binom{k}{2}$.
> 3 votes

---
Tags: algorithms, matrices, matching
---


# Question
Title: What is the min # of moves to sort an array from 1 to n?
Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is `n - k`, where `k = the length of the longest increasing subsequence`.

Ex: array is `[1, 2, 5, 3, 4, 7, 6]`

Longest increasing subsequence is `[1, 2, 3, 4, 6]`, which is of length `5`. Hence, the answer is `7 - 5 = 2 moves`. You move numbers `5` and `7` to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

# Answer
> 8 votes
There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted. This shows $n-k$ moves is necessary.

# Answer
> -1 votes
Given answer is wrong because for example - let the given array is

```
    3 5 7 1 9 8

```

In the first step, 1 is removed and placed at first position, as a consequence the array becomes

```
    1 3 5 7 9 8

```

In the second step, 9 is removed and placed at the last position in the array, as a consequence the array becomes

```
    1 3 5 7 8 9

```

The array is now sorted. It took 2 steps to sort the array. You have to find out the minimum number of steps required to make the array sorted.

---
Tags: algorithms, proof-techniques, sorting, lower-bounds
---


# Question
Title: Proof by contradiction for greedy algorithms
I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never been great at proofs, and maybe this will help me get on the track to becoming more comfortable with them.

Consider section 3.2, Analysis. https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6note.pdf The algorithm is very intuitive - choose the highest value/weight and only the last item in the knapsack may need be fractional. I don't have any issues with that. Formally proving that this algorithm is the best thing out there I what I have an issue with.

(note proof is available in more detail: https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6.pdf)

The professor shows that our algorithm chooses items p\_1...p\_n in various amounts. ALG = (p\_1, p\_2, ... , p\_n). So we choose p\_1 much of item 1, p\_2 much of item2... all the way to p\_n. Only the last item in the knapsack could be fractional. All good.

Now we assume that there exists a better algorithm, OPT. We say OPT makes the same choices as ALG up to a certain point OPT(q\_1, q\_2,...q\_n). At some point, q\_i, OPT makes a different choice that ALG. Why in the notes **does the professor say q\_i cannot be p\_1**. Surely OPT could take a different choice immediately. Anyway, that aside, I agree that OPT, like ALG will be putting as much of the items it can into the knapsack upto i. After i, OPT starts doing something else. The professor doens't talk about this, but maybe OPT changes the ordering of the items it puts into the knapsack - that wouldn't be a big deal as long as it chose all the same items and put the same amount of the very last item ALG put in the knapsack last.

However changing the order of items chosen wouldn't make OPT better, just the same. Right? (professor doesn't talk about this, at least not explicitly). For OPT to be better there must be some item, i it chooses less than ALG did of. And similarly some item j we take more of than ALG did, to keep the capacity the same. Another aside: haven't we made the implicit assumption that we must use all of the capacity, W, to be optimal. Is this self evident or something? Intuitively I can see why, but formally I cannot.

Anyway we remove a little amount from qj and give it to qi, hence those equations involving epsilon. i.e. if we remove e units of weight of j then we can add (e * wj / wi) units of value. Fine.

Now why on earth is this called OPT'. Isn't this still OPT? I'm confused here. Why did we bring OPT' in there? Why do we need yet another modified version of ALG. I thought OPT (not OPT') is where we modified qi and qj by changing how much of each we picked.

Thanks all!

# Answer
Just think like this. Without loss of generality, assume

$\begin{equation\*} \dfrac{v\_1}{w\_1} \> \dfrac{v\_2}{w\_2} \> \dotsb \> \dfrac{v\_n}{w\_n} \end{equation\*}$

(item types with same $v\_i/w\_i$ can be merged, it doesn't matter in the end).

Let ALGs choices be $p\_1, p\_2, \dotsc, p\_n$, OPTs choices be $q\_1, q\_2, \dotsc, q\_n$.

Assume ALG doesn't give an optimal solution, so $\mathbf{p} \ne \mathbf{q}$. As they are different, there is $i$ such that $p\_k = q\_k$ for $1 \le k \le i$ and $p\_i \ne q\_i$. By the way ALG works, it adds as much of $i$ as it possibly can, so $p\_i \> q\_i$. What OPT looses by this against ALG on $i$ is $(p\_i - q\_i) \cdot v\_i / w\_i$, and it more than makes up the loss by adding $(p\_i - q\_i)$ weight of items that are all worth *less* per weight than $i$. That is impossible.
> 1 votes

# Answer
Basically, the argument is an "exchange argument" and proceeds as the following:

Say that ALG produces a knapsack $P$ with choices $p\_1, p\_2, \dots , p\_n$ which amounts to weight $W$ (the knapsack can only hold this total weight).

Suppose that there is an optimal knapsack such that it maximizes the value per weight added, and this knapsack is optimal and $P$ is not, call this optimal knapsack $OPT$.

So $P$ and $OPT$ have the same weight up until some point, and the same overall value for the total weight in each of the knapsacks (the value/weight is the same for both $P$ and $OPT$ up to some point). Let $W\_i \< W$ be the point prior to where knapsacks $P$ and $OPT$ weight diverges, that is after $W\_i$, knapsacks $P$ and $OPT$ now have different weights.

We claim that at this point, $W\_i$, we can replace the corresponding weight in $OPT$ that leads to divergence, with ***some*** amount of weight (could be fractional) from $P$, while strictly not decreasing the value/weight in knapsack $OPT$. Since the greedy algorithm picks the best weight to put in the knapsack $P$ based on highest value/weight (as stated above, the items are sorted in decreasing value/weight order) then clearly the exchange in weight from $P$ to $OPT$ does not decrease the optimality of value/weight in the knapsack $OPT$. We can keep doing this exchange until $OPT$ is literally the same knapsack as $P$, recall $P$ is the knapsack that ALG (greedy algorithm) produces.

Therefore, we have proved by contradiction there cannot be a strictly more optimal knapsack than the knapsack produced by ALG, so $P$ is optimal and ALG produces the optimal knapsack. $\blacksquare$
> 1 votes

---
Tags: proof-techniques, greedy-algorithms, knapsack-problems
---


title: Complexity of "Subtree of Another Tree"

text:
# Question
Title: Complexity of "Subtree of Another Tree"
I wrote an algorithm for a leetcode question. The question asks:

> Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

My solution for this problem consists of a breadth-first traversal of the first tree `s`, and a function that checks whether any subtree of `s` is the same tree as `t`. The entire solution can be found here.

I am having a tough time figuring out the time and space complexity of this solution.

I understand that the `isSame` function has a time and space complexity of `O(n)`. (See my explanation below), and the `isSubtree` function will call `isSame` for every node in `s`. However, the size of the input to `isSame` changes on each call, and I am having a hard time putting both pieces together to get an overall runtime / space complexity.

### Explanation of isSame time and space complexity:

For the function that checks whether two trees are the same (`isSame`), the worst-case time complexity occurs when the trees are indeed equivalent. In this case, we will check every node and do a constant amount of work for each node, and thus our time complexity is `O(n)`, where `n` is the number of nodes in either tree (they are the same). Furthermore, the function `isSame` function is recursive, and our time complexity will be linear with the height of the smallest tree. In the worst case, both trees are equivalent, and they have degenerated to a linked list, in which case the number of frames on our call stack will be the same as the height, which is the same as the number of nodes, so that's `O(n)` for the space complexity.

# Answer
The time complexity of `isSame` is not linear in the height of the smallest tree. Think for example of two copies of a complete binary tree (where all nodes have the same value).

That said, the time complexity of `isSame` is always $O(m)$, where $m$ is the number of vertices in the smallest of the two input subtrees.

Let me assume that the number of vertices $m$ of $t$ is at most the the number of vertices $n$ of $s$ (as otherwise the answer is trivial).

Your algorithm requires time $\Theta(n m) = O(n^2)$ in the worst case. The upper bound is obtained by simply multiplying the number of vertices of $s$ with the $O(m)$ upper bound to the complexity of `isSame`. The lower bound is obtained, e.g., by letting $s$ be a path on $n$ nodes rooted in one of its endpoints and $t$ be a path on $m$ nodes rooted in one of its endpoints (as before, all vertices have the same value). The first $\lfloor n/2 \rfloor$ invocations of `isSame` require $\Omega(m)$ time each, for an overall time complexity of $\Omega(n m)$. Notice that this is $\Omega(n^2)$ for $m=\Omega(n)$.
> 2 votes

---
Tags: trees, binary-trees
---


# Question
Title: LaTex Text Justification badness penalty
I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number of spaces. The algorithm also works with quadratic times number of spaces as penalty. I have couple of questions 1) Any idea why this works with both cubic & quadratic? 2) Why it should be cubic or quadratic why not just linear?

# Answer
The optimization function is designed in a way to find a solution that:

* uses a small number of lines
* is balanced (the number of extra spaces at the end of each line should be about the same length)

---

Lets look first at the linear optimization function, i.e. the sum of all extra spaces.

It is very clear, that the optimal solution under that function is one that uses the minimum number of lines. However it will not fulfill the second goal. The number of extra spaces is equal in each solution that uses the same number of lines.

For instance if you want to split the string `a.bb.ccc` at line-width 6. The unbalanced solution

```
a.....
bb.ccc

```

has the same penalty 5 (number of extra spaces) as the balanced solution

```
a.bb..
ccc...

```

. So if you only optimize with a linear function, then you might end up with an unbalanced solution.

---

Now lets look at the the sum of squares.

The intuition is, that having lines with a lot of extra spaces will get penalized a lot more than lines with less extra spaces.

Using the same example. The unbalanced solution

```
a.....
bb.ccc

```

will get a bigger penalty $5^2 + 0^2 = 25$ than

```
a.bb..
ccc...

```

which has only a penalty of $2^2 + 3^2 = 13$.

You can actually partially prove that this will give us a balanced solution.

If you fixate the number of lines, than also the number of necessary extra spaces is fixed. Let's assume than we need $n$ lines with $m$ extra spaces. I'll denote $a\_i$ for the number of extra spaces in line $i$.

We want to optimize $$\sum\_{i = 1}^n a\_i^2$$ We know (using the QM-AM inequality), that

$$\sum\_{i = 1}^n a\_i^2 \ge \frac{(\sum\_{i=1}^n a\_i)^2}{n} = \frac{m^2}{n} = \text{const}$$

and that we reach equality for $a\_i = \frac{m}{n}$ for all $i$.

So the minimum of the optimization function is reached, when every lines has exactly the same number of extra spaces.

Notice, that usually this is not possible (because of the different word lengths in the string).

But the result supports the argument, that this optimization function ends up with a solution that we human would call "balanced".

---

The cubic function, and many other ones, will work in exactly the same way. Unbalanced solutions will end up with a higher penalty than balanced solutions.

---

Btw, $\LaTeX$ uses the sum of squares as penalty. At least Wikipedia claims so.
> 4 votes

---
Tags: algorithms, time-complexity, dynamic-programming
---


# Question
Title: How a Data Compression Software Reads a File as pure Binary File and makes Output?
I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,

I read texts from a text file -\>

then convert it to a binary string -\>

then convert it to an encoded binary string.

At this point, I can save the encoded binary string in a text file, but I want to know what is done in general.

For example, when we use *Winrar* software, it -

1. does not read as I said above, it compresses any file
2. makes .rar file as output

So, how a compressor "read" any file as a pure binary form, and how it makes output file?

In another way, what i want is to know how to read any file as a pure binary form and make a output file given that I have a encoding and decoding scheme. **Please comment anything related to question, I am new to the topic.**

# Answer
> 2 votes
## A file is a byte stream

Although OSes provide some bells and whistles (such as metadata, or forks), most define a file as a sequence of 0 or more bytes.

Each byte in the file is a numerical value from 0 to 255 (inclusive). There's nothing more to it.

## A file format is a way of giving meaning to the bytes in a file

For a simple example, you could have a file representing a black-and-white image, where each byte is either 0 (black pixel) or 1 (white pixel), one row after another. Perhaps the first two bytes encode the image width as a 16-bit number, and the second two bytes encode the height as a 16-bit number.

This example is very inefficient, since each pixel byte can never use the possible values 2-255. You may want to read about information theory.

## "Text file" is a file format

In a text file, every possible value 0-255 is given a meaning, a specific letter, number, symbol, or a "special effect" character like newline. Sort of. Strictly speaking, in the ASCII encoding, only values 0-127 have a meaning.

There are many different text encodings, although only a few common ones. In Unicode, characters are not always 1 byte in length.

But let's stick with ASCII. If you store "51a3" as text, the byte values 53, 49, 97, 51 will go into the file, as they correspond to "5", "1", etc.

If you store the hexadecimal value 0x51 and 0xa3 as *bytes*, then there will simply be those two bytes (81, 163 in decimal.) So this is half the number of bytes. However the file is no longer a text file because 163 is not defined in ASCII.

## Other file formats require purpose-built software

Text files are popular because you can open them in any editor (Notepad, nano). As you understand, they are not very space-efficient.

But it is not difficult to write your own software. Here is an example.

```
#!/usr/bin/env python3

# PART 1 - WRITE BYTES TO A FILE

save_hex = "60b725f10c9c85c70d97880dfe8191b3"

print("Saving:", save_hex)

# group save_hex into groups of 2
save_ints = []
i = 0
while i < len(save_hex):
    # the 16 makes int() treat the value as hex
    integer = int(save_hex[i:i+2], 16)
    save_ints.append(integer)
    i+=2

print("Integer values:", save_ints)

# create a bytes object out of an array of numbers
save_raw = bytes(save_ints)

with open('myfile.raw', 'wb') as f:
    f.write(save_raw)

# PART 2 - READ BYTES FROM A FILE

with open('myfile.raw', 'rb') as f:
    contents = f.read()

print("Loaded: ", end='')
for byte in contents:
    print('{:02x}'.format(byte), end='')
print()

```

After running this check the length of the file is half the length of the hex string. Also, learn to use a hexdump tool to inspect the contents of the file.

Python's bytes objects have a lot of features but if you use the basic idea above (list of ints in range 0-255 -\> bytes object) and (iterate over bytes object and get an int in range 0-255) then you don't need to get too deep into the details.

## All-purpose compression software usually doesn't understand the files it compresses

When you put an mp3 file into a ZIP or RAR, the compression software treats it as a sequence of bytes, the same way it would treat a JPEG or EXE or HTML file.

---
Tags: information-theory, data-compression, software-engineering
---


# Question
Title: Is there a described algorithm converting _from_ Continuation Passing Style?
**Continuation Passing Style** (CPS) is a form of code where the control is passed explicitly, by passing the **continuation** of the code at each call point, unlike **direct style**.

There are many descriptions in the literature for how to convert from direct style to CPS. The following pseudo-JavaScript:

```
function direct() {
    var a = foo(1);
    return bar(a);
}

```

becomes:

```
function cps(cont) {
    foo(1, function(a) {
        bar(a, cont);
    }
}

```

But are there any descriptions of the reverse transformation, where the CPS representation is taken back to a direct style?

# Answer
> 3 votes
I did some additional research to answer this question but find nothing better suited.

To do reverse of CPS to direct programming you have to assign functions to variables, this makes direct structural code.

Automated and well described technique comes from compilers - SSA (Single Static Assignment). This has additional bonus like compacting code and constant propagating to some extend.

This is not per se technique to reverse CPS, but structure of assignments creates direct code, so it is usable in your situation.

# Answer
> 3 votes
The transformation to CPS style converts from

```
r = foo_direct(...);
bar(r);

```

to

```
foo_cps(..., bar);

```

If you want to go backwards, I think the following works. In CPS, every function call will have a continuation as its last argument. So, at each function call site, you find the continuation and unwind it. In other words,

```
foo_cps(..., ct);

```

gets translated to

```
r = foo_direct(...);
ct(r);

```

where `ct` can be filled in with any expression of your choice. At the same time the body of `foo_cps()` gets translated by changing

```
function foo_cps(..., c) { ...; c(x); }

```

to

```
function foo_direct(...) { ...; return x; }

```

(Note that `x` might be any expression; in general it might be a tuple of arguments.) You may then have to unwind the call `ct(r)` if `ct` is in CTS style. You might want to follow this with some optimizations to detect variable equivalences, e.g., inter-procedural copy propagation.

# Answer
> 2 votes
From "Back to Direct Style" by Oliver Danvy:

> Much work has been devoted to transforming programs into continuation-passing style (CPS). ... By contrast, programs that are not in CPS (e.g., programs before CPS transformation) are said to be in "direct style" (DS). Their procedure calls can occur anywhere (i.e., not necessarily in tail position). In contrast to the work mentioned above, the present paper studies the transformation of CPS programs into DS. ...

That is expanded upon in "Back to Direct Style II: First-Class Continuations" by Danvy & Lawall:

> The direct-style transformation aims at mapping continuation passing programs back to direct style, ... In this paper, we continue to investigate the direct-style transformation by extending it to programs with first-class continuations.

---
Tags: code-generation
---


# Question
Title: Is this FA really equivalent to the given regular expression?
From the picture, the automata can accept $(\text L|\text D)^\*$ following say $\\\_\text L\text D$, but in the formula above $(\text L|\text D)^\*$ can't follow the $\\\_\text L\text D$.

So the Automata in the picture is not equivalent to the RE?

# Answer
They aren't equivalent. For example, the string "L\__L" is described by the expression, but not accepted by the automaton (no way to have two '\_' in a row).
> 0 votes

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


# Question
Title: Why can't un-journaled filesystems be resized?
I have yet to find an un-journaled filesystem that can be resized without data loss or intermediate conversions, and I'm wondering why that is.

Filesystems like FAT, for example, leave free space at the end of the block device; it seems pretty simple to me to just add more free space onto the end...

Edit: It seems that some filesystems, created without a journal, can still be resized. I created an EXT4 filesystem with `mke2fs -t ext4 -O ^has_journal /dev/loop0p1`, grew the partition, and successfully resized it. I also created an EXT2 filesystem (which to my knowledge doesn't have a journal) and successfully resized it.

My current theory is that it's just a big coincidence that most filesystems without a journal can't be safely resized and most with a journal can.

# Answer
It’s just historical.

Old file systems are not journaled, and they cannot be resized. At some point in time journaling was added, and at some point in two resizing was added. So new file systems have both features.

You obviously don’t need the ability to resize a disk to implement journaling, but there is also no reason why journaling would be needed for resizing a hard drive.

It would be good if the file system was designed in such a way that resizing can be done with a minimal amount of moving files, and in such a way that the disk is a valid (old size) disk for as long as possible, so that only one final change is needed to change it from old size to new size.
> 2 votes

# Answer
The "file allocation table" (which gives the FAT filesystem its name) is a fixed-size array "statically allocated at the time of formatting." Its size is determined by the size of the partition, because "The table contains entries for each cluster, a contiguous area of disk storage." (quoted from Wikipedia).

So if the partition is made larger, the FAT has to be made larger. But in order to do that, whatever pieces of files which happen to occupy the sectors adjacent to the FAT need to be moved elsewhere. That's not a simple procedure, and while it is being performed, the whole filesystem is in an inconsistent state.

That might seem like a suboptimal design, but since FAT was designed for single partition removable media (i.e. floppy disks) whose size was determined at the time of manufacture, there was no need to plan for resizing. The fixed-size immovable allocation table makes for faster, simpler code.

The Wikipedia article provides a lot more details, if you're curious. It's actually not too difficult a project to write a FAT driver, which might provide additional insights.
> 3 votes

---
Tags: filesystems
---


# Question
Title: Recover an array from its insertion indices
An array is built starting with an empty array, and then a sequence of insertions:

1. insert $a\_1$ at index $z\_1=1$
2. insert $a\_2$ at index $z\_2$
3. insert $a\_3$ at index $z\_3$
4. ...

and so on. When we insert element $a\_i$ and index $z\_i$ the result is that $a\_i$ is now at index $z\_i$, whereas everything before index $z\_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence $(3,1), (5,2), (1,2)$ gives $\[3\]$ then $\[3,5\]$ then $\[3,1,5\]$. All of the instructions will make sense, i.e., $1 \leq z\_i\leq i$.

My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions; but in the language I program, insertions have a worst case time complexity of $O(\\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.

Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:

1. the element which ends up at index 1 was the last one which arrived with index 1.
2. the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
3. the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.

... and so on. However I can't think of the algorithms or data structures that would make this information useful.

**Update: There are two $O(n\log n)$ solutions below: the first one, which I accepted, that uses an AVL tree, and one which I learned of afterward that uses a semgent tree, and is somewhat simpler.**

# Answer
> 4 votes
**Prelimiaries**

You can augment an AVL tree to support all the usual operations plus the following:

> Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).

To do so add a value $x\_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).

**Search** The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.

**Insert** To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).

**Rotations** To perform a right rotation on $u$ let $v$ be its left child. "Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x\_u$, add $x\_u$ to the offsets of the children of $u$, and set $x\_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.

**Shift$(a,b)$**. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x\_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x\_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).

---

**Solving your problem**

Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations. Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.

When the operation $(a\_i, z\_i)$ is to be processed do a Shift$(z\_i, 1)$ operation on $T$. Then, insert a new node with key $z\_i$ and satellite data $a\_i$ in $T$.

At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).

The total time required is $O(n \log n)$.

# Answer
> 1 votes
This is an explanation of the correctness of Steven's answer. Of course I would be interested if anyone came up with something simpler but it is a great solution as it stands.

Define the *effective key at a node* to be the node's label + the offsets of all nodes on the (inclusive) path from itself to the root. Our inductive hypothesis is that after processing the $i$-th insertion, we have $i$ nodes with effective keys $1,2,\ldots, i$, in a balanced BST ordered with respect to effective keys. Physically, the effective key for the node associated with element $a$ equals the current index of element $a$ in our array.

Algorithm, at step $(a\_i,z\_i)$. By hypothesis, the tree of size $i-1$ has nodes with effective keys $1$ through $i-1$. In the case $z\_i=i$ we just locate the unique node with effective key $i-1$ and insert $i$ with offset $0$ as a right child. In the other case, $z\_i\<i$, we perform SHIFT($z\_i,1$); the way that it is defined means that SHIFT$(z\_i,1)$ increases the effective key of nodes $z\_i, z\_i+1, \ldots, i-1$ by precisely 1 and leaves all lesser keys unchanged. To insert the effective key $z\_i$, we either put it in the left slot of $z\_i+1$, or the rightmost descendant of $(z\_i+1).left$; in either case, we store it with label $z\_i-(\text{cumulative offset})$ and offset 0. Both SHIFT and this insertion happen in $O(\log N)$ time. Now we have effective keys $1$ through $i$ reprsented in a BST.

So insertions do the right thing to effective keys. Now to keep the BST balanced (and so achieve $\log n$ complexity) AVL and red-black trees use rotations. It is known that rotations preserve the orderings in a BST. The problem here is that the effective keys are calculated using the offsets leading up to the root. A rotation may change the offsets seen on the way from a node to the root, since it may change the path from that node to the root. For instance if the node $v$ is rotated up into $u$'s position, then the offset $x\_u$ that would have been counted in the path from root to $v$, is no longer encountered, while the offset $x\_v$ would now be counted in the calculation for $u$. To see how we might do rotations without messing up the effective keys, we introduce the "push-down" operation on a node $u$. Let $v\_1, v\_2$ be its children. The push down on $u$ increments $x\_{v\_1}$ and $x\_{v\_2}$ by $x\_u$; increments $u$ by $x\_u$; and lastly sets $x\_u=0$.

During a rotation (let's say right rotation for definiteness) about node $u$ with left child $v$, we first push down $u$, then push down $v$, and finally rotate as usual: it can be seen by checking all modified parts of the tree, that the effective keys remain the same after rotation:  (in the above picture, we'd check that the effective keys corresponding to nodes $v,u$ and subtrees $R,S,T$ are unchanged).

# Answer
> 1 votes
I recently learned a weird trick to solve the problem in $O(n\log n)$. It appeared in a comment on a codeforces blog and seems to be well(?) known among competitive programmers. It puzzles me why it works, but I will update this answer with a proof if and when I figure it out. Below is a description of the procedure: (**Update**: proof below)

We are sequentially inserting $n$ elements, with the $i$ element at index $z\_i$ and trying to find the final indices. Initialize an array $s\[\cdot\]$ of length $n$, all zeros. Begin with the $n$-th (final) element and work our way backwards to the 1st element. To start, find the $z\_n$-th "$0$" of $s$, counted from the right, and change it from $0$ to $1$. The final position of the $n$-th element is just $z\_n$, since no elements come after to "bump" its position. We say its "offset" is $0$.

In general, for the $i$-th element; we locate the $z\_i$-th "$0$" of $s$ from the right and change it to "$1$"; let the $i$-th offset equal the $\\#$ of $1$s strictly to the right of the new "$1$". Then the final index of the $i$-th element is $z\_i$ plus its offset.

Example: Insertions at 1,2,1,1. Initialize $s=\[1,1,1,1\]$

* Insertion of the 4th element at index 1: $s=\[0,0,0,0\] \rightarrow \[0,0,0,1\]$. Offset $= 0$, since there are no $1$s to the right. Final index $=1+0$.
* Insertion of the 3rd element at index 1: $s=\[0,0,0,1\]\rightarrow \[0,0,1,1\]$. Offset $=1$, since there was one $1$ to the right. Final index $=1+1$.
* Insertion of the 2nd element at index 2: $s=\[0,0,1,1\]\rightarrow \[1,0,1,1\]$. Offset $= 2$, since there were two $1$s to the right. Final index $=2+2$.
* Insertion of the 1st element at index 1: $s=\[1,0,1,1\]\rightarrow \[1,1,1,1\]$. Offset $= 2$, since there were two $1$s to the right. Final index = 3.

Using a segment tree (or possibly a fenwick tree), queries of the type "count the number of $1$s in the range $\[k,n\]$ of $s$" is a standard range-sum query and can be answered in $O(\log n)$.

Queries of the type "find the $j$-th $0$ in $s$ from the right", can also be answered in $O(\log n)$ time with what is essentially a binary search of the tree starting at the root. First suppose that we have a segment tree with every element of $s$ flipped ($0$s as $1$s and vice versa). In this case we could find the $j$-th $1$ from the right by identifying the rightmost $\[k,n\]$ such that $s\[k\]+s\[k+1\]+\cdots+s\[n\]=j$. The latter problem can be accomplished via a binary search starting from the root. And in this case the desired $1$ is found at $s\[k\]$.

Finally, the updates to individual elements of $s$ (changing a $0$ to a $1$) can be done in $O(\log n)$ time.

---

**Proof of correctness**: Denote $b\_i:=$ the number of elements which bump the $i$-th element; observe that every bump causes the index to rise by $1$. So the final index of the $i$-th element is $z\_i+b\_i$.

> **Lemma: Let $j\>i$. Then the $j$-th element bumps the $i$ iff $z\_j+b\_j\<z\_i+b\_i$**.

The direction $\impliedby$ is basically obvious due to the observation about the final index; for $\implies$, assuming $j$ bumps $i$, we recognize two cases: (1) $z\_j\leq z\_i$; note that anything that bumps $j$ also bumps $i$; furthermore $j$ bumps $i$, so we have $b\_i\geq b\_j+1$, hence the result. (2) $z\_j\>z\_i$; in this case we must have that the $i$-th element was bumped at least $z\_j-z\_i$ times before seeing the $j$-th element (otherwise the $j$-th element would have been inserted to the right of the $i$-th). Then the $j$-th element arrives, bumping the $i$-th. Then anything that bumps the $j$-th element also bumps the $i$-th. So we have $b\_i \geq z\_j-z\_i+1+b\_j$, proving the result.

Now initialize an array $S'$ of length $n$ with all $0$s. Starting from $i=n$ and going down to $i=1$, we set $S'\[z\_i+b\_i\] := 1$. And by the lemma above, we have that $b\_i = \\#\\{k\>z\_i+b\_i \colon S\[k\]=1\\}$.

Now in the algorithm, define $d\_i =$ the offset (i.e. the "number of $1$s to the right" at the step where we process the $i$-th element). Observe that $b\_n = d\_n$ and that otherwise, the sequences $b\_i$ and $d\_i$, from $i=n$ to $1$, are built following the same rules; in particular setting the $z\_j$-th zero of $s$, counted from the right, is equivalent to setting the $(z\_j+d\_j)$-th element of $s$. This shows that $d\_i=b\_i$ for all $i$.

---
Tags: algorithms, arrays
---


title: Dynamic programming problem

text:
# Question
Title: Dynamic programming problem
our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming.

In our algorithms book, there is the following problem: (an example problem for dynamic programming)

> A driver has 3 cars. He wants to use all of the 3 cars, but want to use the least gas. Each car has a different engine, so it will consume different amounts of gas to get to each destination. What is the least amount of gas we can consume while still using each car? After he switches cars, he can't go back to the previous car.
>
> Input description:
>
> First is a number $n$, which is the number of destinations that he wants to reach. Then there are 3 lines, each is the gas consumed while trying to reach each destination (line 1 is car 1, line 2 is car 2, etc..)
>
> Example input:
>
> 7
>
> 2 4 1 5 1 1 2
>
> 3 3 2 5 3 2 2
>
> 1 1 5 4 3 3 3
>
> Example output:
>
> 12 (third car (2 destinations), first car (4 destinations), second car (1 destination).)

However, I can't figure out how to start, as I'm still learning DP. Could you please help me or give me any hints?

I think it's a great good example problem, because other problems are very similar so if I master this one, I should be able to solve other problems.

Thanks!

# Answer
Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c\_1, c\_2, c\_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).

Define $OPT\[i,j\]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c\_1, \dots, c\_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT\[i,j\] = + \infty$.

According to the above definition, you have $$OPT\[1,j\] = \begin{cases} g(1, c\_1) & \mbox{if } j=1 \\ +\infty & \mbox{if } j\>1 \end{cases}$$.

and, for $i=2, \dots, n$:

$$OPT\[i,j\] = g(i,c\_j)+ \begin{cases} OPT\[i-1, j\] & \mbox{if } j=1 \\ \min\\{ OPT\[i-1, j\], OPT\[i-1, j-1\] \\} & \mbox{if } j\>1 \end{cases}.$$

The solution to your problem is $OPT\[n,3\]$, which can be computed in $O(n)$ time using dynamic programming.
> 4 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Graph with exactly 2 Minimum Spanning Trees
> Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in of the 2 MSTs) that at minimum, 2 of the edges in the set which is the union of the edges have equal weight. Also show that either this edge is the largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can't be distinct, otherwise there wouldn't be multiple MSTs. Also the graph $G$ must contain cycles, otherwise, it wouldn't have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $MST\_1$ there is some edge, $e$ that is not in $MST\_2$ and there is also some edge $f$ that is not in $MST\_1$. Using the cut property if $e$ was not placed in $MST\_2$ and $f$ was not placed in $MST\_1$ then then we have that the weight of $f$, and $e$, $w(f) = w(e)$.

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that's actually true. Then from there I felt that there had to be some node, $z$ such that $z$ had 2 edges with the same weights, and when we combine the edges from $MST\_1$ and $MST\_2$ we end up with both the edges from $z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle... Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $G$, in order for it to have exactly 2 MSTs? Or is there some property I'm missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.

# Answer
**Lemma:** Let $C$ be a cycle of $G$ that contains an unique edge $e$ of maximum weight. Edge $e$ does not belong to any MST of $G$.

**Proof:** Suppose that a MST $T^\* = (V, E^\*)$ of $G$ contains $e = (u,v)$. Root $T^\*$ in $u$ and let $f$ be any edge of $C \setminus E^\*$ that has exactly one endpoint in the subtree of $T^\*$ rooted in $v$ (this edge always exists since $C \setminus \\{ e \\}$ is a path from $v$ to $u$ that avoids $e$). The edge $f$ closes a fundamental cycle containing $e$ and is such that $w(f) \< (e)$. Then $(V, (E^\* \setminus \\{e\\}) \cup \\{ f \\}$) is a spanning tree of $G$ that weighs less than $T^\*$. This is a contradiction. $\square$

Let $T\_1 = (V, E\_1)$ and $T\_2 = (V, E\_2)$ be two distinct MSTs of $G$. Let $C$ be a cycle in $(V, E\_1 \cup E\_2$). Let $M = \arg\max\_{e \in C} w(e)$.

If $|M|\>1$ we are done. Suppose then that $M = \\{ e \\}$. By the above lemma, $e$ is the unique heaviest edge of $C$ and hence it cannot belong to any MST of $G$. This is a contradiction since $e$ must belong to at least one of $E\_1$ and $E\_2$.
> 1 votes

# Answer
Consider the typical MST algorithms. You get exactly two MST if at some step you have to choose between two edges of equal weight, and that will happen only if they are part of a cycle. And they have to be cheap enough to get included in the MST, but that is harder to characterize...
> 0 votes

---
Tags: algorithms, graphs, trees, minimum-spanning-tree, spanning-trees
---


# Question
Title: Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree"
I am looking at this question from LeetCode.

There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.

My question is in regards to the **memory requirements** of each solution.

In the case of the recursive solution, we are going to be using the call stack. The call stack will, at its max, be the height of the binary tree. In a worst-case scenario, the tree is skewed, the height is the number of nodes, and our space requirement becomes linear - `O(n)`.

In the case of the recursive solution, we use an explicit queue, instead of an implicit call stack. The largest number of elements that the call stack will hold is when the tree is a perfect binary tree (a complete binary tree has the same analysis), in which case, the queue will hold `2^h`, where `h` is the height of the tree (indexed at 0). However, in a perfect binary tree, we also know that `h = log(n + 1)`, so `2^h ~ 2^log(n +1)`, which means that the space requirements for the iterative case is `O(2^(log n))`.

My question is, which one of these is smaller? Can we make a determination that one of these two algorithms is better than the other in terms of memory?

# Answer
> 1 votes
The obvious recursive solution (compute the maximal depth of both subtrees, add one for the root) has space complexity $O(\operatorname{depth}(T))$ (i.e., $O(\log n)$ for $n$ nodes). If you write it recursively or do the call stack by hand instead of having the language handle it for you is irrelevant.

---
Tags: trees, binary-trees
---


# Question
Title: show that in every infinite computably enumerable set, there exists an infinite decidable set
I came across this problem: *Show that in every infinite computably enumerable set, there exists an infinite decidable set*.

As an attempt to solve the problem, I could only think of a proof by construction. Without loss of generality, let the alphabet be $\Sigma=\\{0,1\\}$. The construction goes as follows, suppose that $TM$ $M$ recognizes an infinite computably enumerable set $L$, we can form a decidable language $D \subseteq L$ as follows:

> 1) lexicographically enumerate all input words $w$ in $\Sigma^\*$ and repeatedly perform steps $a-b:$
>
> > a) at the $k$th step, run $M$ on input words $\\{w\_0,w\_1,...,w\_k\\}$ for $k$ steps, where words $\\{w\_0,w\_1,...,w\_k\\}$ are lexicographically ordered
> >
> > b) if $M$ accepts an input word $w \in \\{w\_0,w\_1,...,w\_k\\}$ from step 2, include $w$ in a temporary language $D\_{temp}$
>
> 2) partition the words in $D\_{temp}$ into two, those starting with $0$ are $\in D$, while those starting with $1$ are $\not \in D$, along with all other words $\Sigma^\* - D\_{temp}$.

Step (1) does not loop in a word $w$ since each run of step (1) is limited for a finite number of $k$ steps. Is this construction okay ? Or did I miss something ...

# Answer
> 8 votes
Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w\_1,w\_2,\ldots$.

Let $D$ consist of all words $w\_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w\_m$ be the last word in $D$. Then all other words have length at most $|w\_m|$. However, this contradicts the infinitude of $L$.

Furthermore, $D$ is decidable. Given a word $w$, run the enumerator for $L$, and halt whenever one of the following events happen:

* If $w\_i = w$, output Yes.
* If $|w\_i| \> |w|$, output No.

Since $L$ is infinite, this algorithm will eventually stop.

# Answer
> 2 votes
Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG
We are given directed weighted graph with edges having strictly positive weight(\>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this graph, finding the single-source-shortest paths from $1$ in the normal graph and the single-source-shortest path from $N$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven't written many proofs on graphs before, so I solved the problem, however I'm not sure why this will always hold.

# Answer
> 1 votes
Suppose there is a cycle $v\_1v\_2\ldots v\_kv\_1$ such that every edge in this cycle belongs to some shortest path. Suppose $v\_1v\_2$ belongs to the shortest path $1\ldots u\_1v\_1v\_2u\_2\ldots N$ and $v\_2v\_3$ belongs to the shortest path $1\ldots u\_3v\_2v\_3u\_4\ldots N$, then the weight of the path $v\_2v\_3u\_4\ldots N$ is no greater than that of the path $v\_2u\_2\ldots N$1. Hence, $1\ldots u\_1v\_1v\_2v\_3u\_4\ldots N$ is another shortest path.

Repeating similar argument for the edges $v\_3v\_4,\ldots,v\_kv\_1$, we can get a shortest path $1\ldots u\_1v\_1v\_2\ldots v\_kv\_1u\_{2k}\ldots N$. This is impossible because $1\ldots u\_1v\_1u\_{2k}\ldots N$ is obviously shorter.

---

1 Otherwise the weight of the path $1\ldots u\_3v\_2v\_3u\_4\ldots N$ is greater than that of the walk $1\ldots u\_3v\_2u\_2\ldots N$, which contradicts to the assumption that $1\ldots u\_3v\_2v\_3u\_4\ldots N$ is a shortest path.

# Answer
> 0 votes
The claim you are trying to prove is not true. Consider a graph that contains a cycle consisting solely of edges of weight 0, where the cycle is reachable from 1 and can reach N.

---
Tags: graphs, proof-techniques, weighted-graphs
---


# Question
Title: Machine has 64 bit architecture and two word long instruction
A machine has a 64-bit architecture, with 2-word long instructions. It has 128 registers, each of which is 32 bits long. It needs to support 49 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is a signed integer, the maximum value of the immediate operand is that can be stored is?

edit: would 1 word long instruction for this case be of 64 bit and 2 word long instruction be of 128 bits? Also do we have to add an extra bit while calculating the total bits required for 49 instructions?

# Answer
> 1 votes
A "64 bit architecture" with 32 bit registers is a bit unusual.

Taking the numbers at face value, a 2-word instruction is 128 bit long, you need 6 bit to encode the instruction, 2x7 bits to specify two registers, leaving 108 bits for an "immediate" operand. The maximum value in the "immediate" operand is $2^{107}-1$.

That's answering the question that you asked. What your instructor actually asked, and what he intended to ask, and what he thinks he asked, and what answer he wants to hear, nobody can know that.

---
Tags: computer-architecture
---


# Question
Title: Prove that this solution to the Closest 3-Sum problem always works
I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.

Here's the problem, transcribed:

> Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
>
> For example, given array S = {-1 2 1 -4}, and target = 1.
>
> The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

The top solution was basically this:

1. Sort the list.
2. Loop over each number using index `i`.
3. Pick `j` to be `i+1`, in other words, the leftmost number of the segment after `i`.
4. Pick `k` to be `n-1`, in other words, the rightmost number of the segment after `i`.
5. If the sum of the numbers at (i, j, k) are less than the target, then `j++`. Otherwise, `k--`.

But isn't it possible that we might prematurely increment `j` (or decrement `k`), dismissing it forever, when in fact it may have been the optimal pairing had we tried a different `k` (or `j`)?

It seems we'll never backtrack to check other combinations.

Can someone provide a minimal, intuitive proof of why such a case never occurs? I'm unable to come up with a counterexample, and I trust the experienced members of Leetcode, so I know I must be wrong, but I can't seem to prove it. I can prove it for the Exact 3-Sum problem, but I don't know how to work with inequalities.

# Answer
> 1 votes
The core of the problem is to solve the **2 sum closest problem for a particular i:**

*Given a target value, find a pair of numbers who's sum is closer to the target value.*

The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right)

Your question is why can we decrease r or increase l.

The answer is as the array is sorted, and suppose nums\[r\] + nums\[l\] \< target, we would not gain any better result comparing nums\[l\] with any of the values of nums between l and r. Because for any other value in nums\[l to r\] the sum is even smaller. As we wouldn't get any better result, why not forget about the value nums\[l\] all together? Right? And that is what we do by increasing l.

This reasoning happens since the beginning of the 2 sum closest search. When l=0 and r=len(nums). We discard values one by one until we are left with l=r-1.

# Answer
> 1 votes
In the explanation, there is one bit missing: You will repeatedly find i, j, k such that a\[i\] + a\[j\] + a\[k\] ≥ target, and a\[i\] + a\[j\] + a\[k-1\] ≤ target. What's missing in the explanation is that for both cases you need to calculate the difference from the target, and keep track of the triple where the difference is smallest. Should you hit the target (by coincidence) then you're done.

---
Tags: algorithms, correctness-proof
---


# Question
Title: NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution
The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.

My question is, if asking for an algorithm that only provides yes/no, or solvable/not solvable, without providing an exact solution of the 3-SAT formula, will this result in another complexity class?

The reason I have in mind of asking this, is a similar situation when looking for prime numbers and factorizations. Where it is known that it's much easier to test if a number is a prime number yes/no, than to find an exact prime factorization of a number.

# Answer
> 2 votes
Check Belare and Goldwasser, "The complexity of decision versus search", SIAM J. Of Computing, 23:1 (feb 1994), pp. 97-119. Belare has notes for a class.

# Answer
> 4 votes
Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression true, it here are any). Thus the cost of the search problem isn't "too much more" (multiply by the size of the input --number of variables-- is polynomial).

# Answer
> 3 votes
NP-completeness is a category of *decision problems*, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete.

There are other types of problems around. The three most common ones are optimization problems, function problems and search problems.

**Optimization problems:** These are problems in which the aim is to maximize or minimize some quantity. The decision problem associated with a maximization problem has as input an instance $I$ of the optimization problem and a threshold $\theta$, and it asks whether there is a solution for $I$ whose value is at least $\theta$. The way we framed the problem guarantees that (in most common cases) the decision problem is in NP. In many cases, the decision problem is NP-hard, and in these cases we also sometimes say that the optimization problem is NP-hard, though this is abuse of notation.

There is a simple way to reduce the optimization problem to the decision problem (that is, a way to solve the optimization problem if you can solve the decision problem): binary search. Assuming that you know lower and upper bounds on the possible answer (this is the case for many problems), you simply perform binary search using the decision oracle. In many cases, the number of steps you have to perform is at most polynomial.

**Function problems:** These are problems in which the goal is to compute some function of the input. Decision problems are a special case, in which the function returns either "Yes" or "No". We can always formulate function problems as decision problems, using an encoding trick: given an input and an index $i$, the decision problems asks us to find the value of the $i$th bit of the output of the function.

**Search problems:** These are problems which are like the "solution" version of 3SAT: given an instance, there are zero or more solutions, and we are interested in finding whether there is at least one solution, and if so, one of the solutions. An important subclass is that of *total* search problems, in which a solution is guaranteed to exist. Function problems are a special case in which the solution is unique. Total search problems have lately been popular in communication complexity.

With each search problem we can associate a decision problem, which asks whether a solution exists or not. Many problems exhibit the phenomenon of *self-reducibility*, in which the search problem reduces to the associated decision problem. This is the case for 3SAT. The idea is very simple. Given a satisfiable 3CNF $\phi$, we execute the following recursive procedure:

* Pick a variable $x$ occurring in $\phi$ (if $\phi$ involves no variables, return immediately).
* Substitute $x = F$ to obtain a formula $\phi\_{x=F}$. If $\phi\_{x=F}$ is satisfiable (this can be determined using a decision oracle), recursively determine a satisfying assignment for $\phi\_{x=F}$, and add to it $x=F$.
* If $\phi\_{x=F}$ is not satisfiable, do the same for $\phi\_{x=T}$ (which must be satisfiable).

You can check that for a formula involving $n$ variables, there are at most $2n$ recursive calls, so this is an efficient reduction.

---
Tags: complexity-theory, time-complexity, computability, np-complete, p-vs-np
---