# Question
Title: Formula to see where a memory address can be depicted in cache?
I've been trying to find a formula that helps us identify where an address can be depicted in cache. I remember my professor talking about some kind of division but I can't find it in my textbook nor internet (maybe I am not searching the right words). For example: I have a cache that has $2^{14}$ blocks, each 32 bytes, and it is 8-way associative with $2^{11}$ sets and each address is 64 bits. So we have 48 bits for the tag, 11 for the index, and 5 for the offset. I would like to answer the following question:

> Where can we find in cache, the addresses 300A21 (hex)?

My obvious answer is to convert it into a binary address: `0011 0000 0000 1010 0010 0001`, and now, we know that index is `0000 1010 001`, so it has to be into the set with this index (it is the 81st), and since `0 0001` is the offset, I guess that since we count from 0, it is the second word on the block (?).

Is there anything else I can say? Something that involves a division or modulo of the address?

# Answer
> 1 votes
## Your Result Is Correct

| Tag | Set | Offset |
| --- | --- | --- |
| 0011 0000 | 0000 1010 001 | 0 0001 |

Don't doubt your methods for finding the address location in a set-associative cache. Your approach is absolutely correct, but first, let's clarify some terminology:

From your question you use the term "index." If I am correct you are using this to refer to the "set" in the set-associative cache? I will use the term "set" from this point forward in place of "index" to avoid confusion since it is more explicit with regard to the type of cache in question.

---

## Your Question. . .

You asked about:

> Something that involves a division or modulo of the address?

### The Short Answer Is. . .

. . .yes! However, just not with set-associative cache. Modulo division is used when attempting to find a block to which a memory address may be mapped using a *Direct Mapped Cache* scheme. Subdividing the cache blocks into sets that map to a main memory location based on a portion of its address removes the necessity to obtain a cache location via modulo division.

### The Long Answer. . .

Direct mapping involves the process where block **X** of *main memory* is mapped to block **Y** of *cache memory, mod* **N**, where **N** is the number of blocks in cache.\[1\]

### Example:

Provided you are given a cache memory consisting of four blocks and a main memory consisting of eight blocks, the direct mapping scheme will be as follows:

| Cache
Blocks | Mapping | Main Memory
Blocks | Mapping
Formula |
| --- | --- | --- | --- |
| CB 0 | **MM 0**
**MM 4** | MM 0 | MM 0 % 4 = **CB 0** |
| CB 1 | **MM 1**
**MM 5** | MM 1 | MM 1 % 4 = **CB 1** |
| CB 2 | **MM 2**
**MM 6** | MM 2 | MM 2 % 4 = **CB 2** |
| CB 3 | **MM 3**
**MM 7** | MM 3 | MM 3 % 4 = **CB 3** |
|  |  | MM 4 | MM 4 % 4 = **CB 0** |
|  |  | MM 5 | MM 5 % 4 = **CB 1** |
|  |  | MM 6 | MM 6 % 4 = **CB 2** |
|  |  | MM 7 | MM 7 % 4 = **CB 3** |

---

## The Difference

*Direct Mapped Cache* does not require any searching and is therefore less expensive. However, main memory is constantly being swapped in and out of cache. In the above example, you can see that either block of cache may only hold one of two blocks of main memory at a time. Imagine the scenario where **CB 0** is polled for **MM 0** but is currently holding **MM 4**. The CPU would need to expunge **MM 4** and bring in **MM 0**. If the next read/store cycle required **MM 4**, the process would occur again leading to cache thrashing.\[1\]

In an ideal world we would use *Fully Associative Cache*, wherein each block of main memory has its own location in cache and does not have to share with any other addresses. The best way of implementing this type of cache is to have each memory address assigned to *any free location at random*. However, this requires additional structures within the CPU that search every cache location in parallel.\[1\] Not only does this translate into a higher monetary expense for the additional hardware structures, it also comes with a look-up cost by having to search each cache block for a hit.

The answer is to strike a happy medium by using *Set-associative Cache* that combines advantages of the two other types. Each main memory block may be assigned to a specific set location similar to direct mapping, but the exact block in cache will differ based upon the next free block within the set similar to *Fully Associative Cache*.

---

## Links Regarding Different Cache Mapping Schemes

https://www.geeksforgeeks.org/cache-memory-in-computer-organization/

https://en.wikipedia.org/wiki/Cache\_placement\_policies

---

\[1\]Null, L., & Lobur, J. (2015). Ch. 6 Memory: Direct Mapped Cache. In *The Essentials of Computer Organization and Architecture* (4th ed., pp. 350-365). Burlington, MA: Jones & Bartlett.

---
Tags: computer-architecture, cpu-cache, memory-hardware, memory-access
---


# Question
Title: How to analysis the complexity of this LIS program?
I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site.

Given a fixed `curr`, the for-loop in `lis_ending_here(...)` will recursively call `curr` times itself will new `curr` range from `0 to curr-1`, then I stuck here and don't know what's the next step to get the conclusion $O(2^N)$. You can also provide me resource (i.e. book name) which is about the technique to analysis the complexity of recursion, since I don't know what are the beginner friendly ones.

```
int lis_ending_here(int arr[], int curr)
{
    // Only one subsequence ends at first index, the number itself
    if(curr == 0)
        return 1
    int ans = 1
    for(i = curr-1 to 0, decrement of -1)
        if(arr[i] < arr[curr])
            ans = max(ans, 1 + lis_ending_here(arr, i))
    return ans
}
int longest_increasing_subsequence(int arr[], int N)
{
    // Because a single number can be a subsequence too
    int max_ans = 1
    for(i = 0 to N-1)
        max_ans = max(max_ans, lis_ending_here(arr, i))
    return max_ans
}

```

# Answer
> 1 votes
The worst case running time of your first procedure satisfies the recurrence $$ T(n) = T(n-1) + \cdots + T(1) + O(1). $$ The worst case running time of your second procedure is $T(n) + \cdots + T(1) + O(1)$, which we can identify with $T(n+1)$. Thus it suffices to understand the first recurrence.

Let us assume replace $O(1)$ with $1$, obtaining the recurrence $$ T(n) = T(n-1) + \cdots + T(1) + 1. $$ Therefore $$ T(n+1) = T(n) + \[T(n-1) + \cdots + T(1) + 1\] = 2T(n). $$ Consequently, $T(n) = 2^{n-1} T(1) = 2^{n-1}$.

If we replace $1$ back with $O(1)$, we get $T(n) = O(2^n)$.

---
Tags: algorithms, time-complexity, algorithm-analysis
---


# Question
Title: Data structure that allows accessing elements by index and delete them in O(logn)
I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(logn) time.

Which data structure should I use to meet this requirement?

Clarification:

Deleting element on index(5) will move element from index(6) to index(5)

the element at index 6 change indexes so that it now has index 5 and 7th element changes to 6th so on ..

# Answer
> 2 votes
Take any self-balancing binary tree (e.g. AVL) and replace every node's key with **the number of left descendants** it has. This is easy to keep up-to-date for tree insertions/deletions (in $O(log n)$ time), and rotations (in $O(1)$ time).

Then to find the node with index $i$ you start at the root and repeatedly compare $i$ with the value of the current node $v$. If $i \< v$ you go to the left child, $i = v$ you found the correct node and $i \> v$ you subtract $i := i - v$ and go to the right child.

# Answer
> 1 votes
You can also use a skip list to do this: https://en.wikipedia.org/wiki/Skip\_list#Indexable\_skiplist

> As described above, a skip list is capable of fast O(log(n)) insertion and removal of values from a sorted sequence, but it has only slow O(n) lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to O(log(n)). For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.

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


# Question
Title: Assigning keys to the nodes of a Binary search tree given its shape
Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of the keys to the nodes unique, given its shape. What is a good $O(n)$ algorithm for assigning each node its correct key? For example, the trees with $n=3$ nodes are shown below. Even if I removed the keys assigned to each node, I could have labeled them manually. Now, I want an algorithm for this. The motivation here is that I'm obtaining a Binary search tree through some mechanism (and the tree has the right shape), but that mechanism is labeling the nodes incorrectly. See: https://math.stackexchange.com/questions/4051677/converting-a-dyck-path-to-corresponding-binary-search-tree.

# Answer
Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.
> 2 votes

# Answer
Perform an inorder traversal. This can be recursively defined as "traverse left subtree, visit root, traverse right subtree".

Alternatively, follow the tree (visiting each node "between" left and right subtrees.)
> 1 votes

---
Tags: binary-trees
---


# Question
Title: Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?
The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.

The author then argues that this is a $log(n)$ time algorithm (where $n$ is the number of nodes in the list) because the span of nodes covered by the "far" pointer doubles on every iteration of the innermost loop. What I don't understand is why the author doesn't seem to factor in the time required for the first two lines of code after the **begin** statement, where a processor is assigned to each node in the list. Assuming the input to the algorithm is just a pointer to the header node to the linked list, wouldn't the assignment of processors require traversing each node in the linked list and thus take time linear in $n$? After all, each node in the linked list may be stored in some highly non-contiguous locations in memory identifiable only by following the chain of pointers from predecessor nodes in the list one at a time.

# Answer
> 1 votes
It seems this paper, which serves as a foundation for subsequent work on list ranking parallel algorithms, handles the oversight of assigning processors by assuming that the input is just given as an array containing the linked list (not necessarily in the order of the nodes in the list). This assumption of contiguous memory storage is implicitly followed in later papers such as this one.

---
Tags: algorithms, algorithm-analysis, parallel-computing, linked-lists
---


# Question
Title: Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one
I was asked this in a hiring challenge that I gave today on HackerEarth:

**Question/Problem statement:**

Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum of difference between maximum and minimum in each of those subarrays.

**Examples:**

```
[1, 2 , 1 , 0, 5]

```

You can split them into 3 subarrays `[1,2] , [1], [0,5]`.

Through this split, you can obtain maximum sum like `(2-1) + (1-1) + (5-0) = 6.`

**Another example:**

```
[1,4,2,3]

```

You can split them into 2 subarrays `[1,4] , [2,3]`.

Through this split, you can obtain maximum sum like `(4-1) + (3-2) = 4`

**Constraints:**

* Array length can be up to 106.
* Array values can be between -109 to 109.

**My attempt:**

I made a brute force DP attempt which was partially accepted. Below is the approach.

```
long[] dp = new long[N + 1];

for(int i = N-1;i >= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j < N; ++j){
        min = Math.min(min, A[j]);
        max = Math.max(max, A[j]);
        dp[i] = Math.max(dp[i],max - min + dp[j + 1]);
    }
}

print(dp[0])

```

**Issue:**

Can anyone share with me how this can be solved efficiently?

# Answer
Yuval's answer explains the initial intuition and analysis. Here is a detailed explanation and an efficient algorithm in Java.

Given a (sub)array $B$, let $\min(B)$ and $\max(B$) be its minimum element and maximum element respectively. $B$'s range is the interval $\[\min(B), \max(B)\]$. Let the difference of $B$ be $d(B)=\max(B)-\min(B)$.

Given $p$ that is a partition of the given array into subarrays, let $sd(p)$ be the sum of differences of those subarrays.

---

**Splitting Lemma**. Given partition $p$, two contiguous elements $n\_1$ and $n\_2$ in some (sub)array $B$ of $p$, let us split $B$ between $n\_1$ and $n\_2$ into subarrays $B\_1$ and $B\_2$, obtaining a new partition, which will be called $p'$. If both $n\_1$ and $n\_2$ are in $B\_1$'s range or both are in $B\_2$'s range, then $sd(p) \le sd(p')$.

Here is how to understand the lemma.

* Subarrays in $p$ other than $B$ are not changed; so their contribution to the sum of differences will not decrease.
* When $B$ is split into $B\_1$ and $B\_2$, the only part of the range of $B$ that might get "missing" is the interval $\[\min(n\_1, n\_2), \max(n\_1, n\_2)\]$. If that interval is covered by either $B\_1$ or $B\_2$, the sum of differences will not miss that range.

---

Let $p$ be some partition of the given array.

* Suppose there is a peak in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a\c$.

+ Suppose $a \le c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
    + Otherwise $a \gt c$. Symmetrically to the above, we will cut between $b$ and $a$.
* Suppose there is a valley in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a\>b$ and $b\<c$.

+ Suppose $a \ge c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
    + Otherwise $a \lt c$. Symmetrically to the above, we will cut between $b$ and $a$.

---

The above shows that whenever a partition contains either a peak or valley in one of its subarrays, we can split that subarray to get a partition that is no less optimal.

In particular, cutting subarrays repeatedly if necessary, we can replace an optimal partition with another one that has no peak or valley in any of its subarrays.

Hence, in order to final the maximum sum, we only need to consider the partitions that has no peak nor valleys in all of its subarrays, i.e, each subarray is (weakly) increasing or (weakly) decreasing.

If two consecutive subarrays are, if considered together, is an increasing array or a decreasing array still, combining these two subarrays into one subarray will not decrease $sd$. So, we only need to consider subarrays each of whose endpoints is the endpoint of a maximal increasing run or a maximal decreasing run or its immediate neighbors.

---

Here is an implementation in Java that runs in $O(n)$ time. It should finish within half of a second when $n=10^6$.

```
    static long maximumSum_simplified(int[] A) {
        int len = A.length;

        // maxSum[i+1] will be the max sum out of A[0..i] for selected `i`s.
        long[] maxSum = new long[len + 1];
        // maxSum[0] = 0;  by Java default.

        // A[start..end] will be a maximal increasing run or a maximal decreasing run.
        for (int start = 0, end; start < len - 1; start = end) {
            end = start + 1;
            if (A[end] <= A[start]) {
                while (end + 1 < len && A[end + 1] <= A[end]) end++;
                for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
                    maxSum[i + 1] = Math.max(maxSum[start] + A[start] - A[i],
                            maxSum[start + 1] + A[start + 1] - A[i]);
                }
            } else {
                while (end + 1 < len && A[end + 1] >= A[end]) end++;
                for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
                    maxSum[i + 1] = Math.max(maxSum[start] + A[i] - A[start],
                            maxSum[start + 1] + A[i] - A[start + 1]);
                }
            }
        }

        return maxSum[len];
    }

```
> 4 votes

# Answer
Some case analysis shows that:

* Without loss of generality, every subarray is monotone.
* Without loss of generality, no monotone subarray is "broken", that is, joining two adjacent subarrays cannot result in a monotone subarray.

This reduces the number of options in dynamic programming to $O(1)$, and so should lead to an $O(n)$ algorithm.

(It seems that some case analysis is still needed. For example, if the array is $a,b,c$, where $a\c$, then the best solution depends on whether $a\<c$ or $a\>c$.)
> 5 votes

---
Tags: algorithms
---


title: What is an Efficient Algorithm?

text:
# Question
Title: What is an Efficient Algorithm?
From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything which is what I might naively call "sub-polynomial", such that $f(n) = o(n^2)$ such as $n^{1+\epsilon}$ would be efficient and anything which is $\Omega(n^2)$ would be "inefficient". However, I've heard anything which is of any polynomial order be called efficient. What's the reasoning?

# Answer
> 11 votes
That depends on context. In theoretical computer science, usually every polynomial time algorithm is considered 'efficient'. In approximation algorithms for example a runtime of $n^{1/\epsilon^{1/\epsilon}}$ would be considered efficient, even though it won't be usable in practice for any reasonable value of $\epsilon$. An algorithm for SAT that runs in $n^{2^{100}}$ would be an amazing breakthrough.

In classic algorithmics, i.e. algorithms from the 80's and before, runtimes below $n^3$ or so (think matrix multiplication, min cost matching, flows, linear programming) are considered efficient. They still are considered efficient by most people, I'd say. Of course a $n^2$ algorithm is not considered efficient if a $n\log n$ algorithm is known, as for sorting for example.

Nowadays there is a trend towards sublinear algorithms or streaming algorithms that are able to deal with terabytes of data. Try using matrix multiplication to compute the page rank of all pages in Google's index. That won't work.

Of course, while certainly useful, the asymptotic runtime of an algorithm doesn't tell the whole story. There are algorithms that have good asymptotic runtime, but constants that are so huge that they effectively can't be used. Ever. Lipton calls them Galactic Algorithms. Robert Sedgewick even states that worst case bounds are "often useless for prediction, often useless for guarantees" and "worst-case analysis is useless for predicting performance" in his talk Putting the Science Back Into Computer Science.

# Answer
> 4 votes
My 2 cents from the angle of distributed algorithms: When looking at large-scale networks (P2P, social networks, etc.) a distributed algorithm is considered to be *efficient* if its running time is $O(\log^c n)$ for some constant $c\>0$ **and** the algorithm uses messages of $O(\log n)$ bits. Note that the requirement on message sizes is usually given even more importance than the running time, in particular for "global" problems that have a larger lower bound on the running time, e.g. distributed MST.

# Answer
> 3 votes
The reasoning behind is that, from the asymptotic behavior perspective, a polynomial rate of growth is trivially less than a super-polynomial rate of growth. In practice, a polynomial time algorithm runs much faster than a super-polynomial time algorithm when the input size grows.

Of course, no one would say that an algorithm with polynomial complexity of, for instance, $O(n^{2000})$ is "efficient", but the majority of algorithms rarely exceeds a complexity of $O(n^5)$.

Practical considerations may even lead you to say that $O(n^2)$ is inefficient to process an extremely large input, and this is why we try to prove lower bounds and to design sequential algorithms matching these lower bounds on one side, and resort to parallel algorithms on the other side. For some problems, if you are willing to accept a probabilistic guarantee, you may even advantage of sub-linear time algorithms (extremely fast, but may fail to provide a correct answer with a very small probability).

# Answer
> 3 votes
In theory, an algorithm is said to be efficient if its worst-case running time is bounded by a polynomial in it's input length. The reasoning being that polynomials have nice closure properties. Adding, multiplying, composing polynomials are operations that yield polynomials and these are good if you are reducing problems to one another.

Of course the gap between polynomial and exponential gets very very big as the input length increases so polynomial-time algorithms are way better. In practice, a polynomial-time algorithm may take a long time before termination but it might be the case that it's an optimal algorithm (the best possible) in which case I would say it's efficient.

# Answer
> 0 votes
Some problems are easy, some are hard. Whether an algorithm is "efficient" depends on how good it is compared to the inherent complexity of the problem. If you find an algorithm that factors any n digit number in O ($n^3$) operations, and I find an algorithm that sorts n numbers in O ($n^2$) operations, then your algorithm is more efficient (because it beats anything known to mankind by a huge factor, while mine is as slow as you would expect from an absolute beginner).

# Answer
> 0 votes
The exact (time) cost of solving a problem depends on the computation model in use: Do you mean Turing machine steps, instructions of your PC, function calls in lambda calculus, ...? It turns out that you can simulate the usual computation models with each other in costs related by polynomials. E.g. $N$ CPU instructions can be simulated in $p(N)$ steps of a Turing machine, for a polynomial $p$. Separating "can be done in polynomial time" from "can't be done in polynomial time" (informally, but very wrongly, called "exponential time") thus allows one to talk independent of the exact computation model. Any algorithm whose running time is not bounded by a polynomial is clearly useless beyond very small instances.

If you take the usual CPU computation model, typical algorithms in use have execution times bounded by low-degree polynomials in the input size. The available techniques allow (somewhat) distinguishing between bounded by a polynomial or not, finer distictions are very hard to come by. When a polynomial time algorithm is called "efficient", this means low degree in practice.

And in the end, this is a *definition*, they could have called them "xglerby algorithms" for that matter. Naming them "efficient" (with the caveat that we typically understand that the polynomial isn't too large a degree in colloquial language) is just leaning on normal usage of the term.

---
Tags: algorithms, terminology, asymptotics, landau-notation
---


# Question
Title: How could i create a multi-threading system in a kernel?
Im trying to figure out if there's an assembler instructions or a bios intruction to get multi-threading in a kernel. In the case that doesn't exist that, how could i set muti-threading in a kernel?

# Answer
In a multiprocessing system the other cores of the CPU are initiated with boot code like UEFI or legacy bootloader just like the first core of the computer.

The CPU is manufactured to use a "core 0" as the first core of the system. After boot, the kernel needs to use the Local APIC of core 0 to send IPI ( interprocessor interrupts) to other cores to start them. As stated on osdev.org,

> IPIs are sent through the BSP's LAPIC. Find the LAPIC base address from the MP tables or ACPI tables, then you can write 32-bit words to base + 0x300 and base + 0x310 to send IPIs. For a init IPI or startup IPI, you must first write the target LAPIC ID into bits 24-27 of base + 0x310. Then, for an init IPI, write 0x00004500 to base + 0x300. For a SIPI, write 0x00004600, ored with the page number at which you want to AP to start executing, to base + 0x300. For more information, see http://wiki.osdev.org/APIC#Local\_APIC\_registers.
> 2 votes

# Answer
That is a overall kernel design issue, not a single assembler instruction. BIOS is an (obsolete) piece of startup machinery for PCs, it had very little incidence on full-fledged kernels (after initializing stuff and stashing away some data for later use befor handing control to the kernel, that is). Such a kernel will have to use synchronization techniques to make sure no part of the code tramples on the work of another thread.

With today's multi-core chips, any non-toy kernel is forced to be multithreaded (running on just one core and making sure no other core can interfere is just too inefficient).
> 1 votes

---
Tags: threads, os-kernel, kernel-functions
---


# Question
Title: Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.

The nondeterministic selection of a permutation of the nodes is done in polynomial time.

How is the choice of a function done in polynomial time? This is not clear to me.

# Answer
The choice of function is done in *nondeterministic polynomial time* which is something you shouldn't try to "make sense of" in the real world.

It is a mathematical model of computing where we assume that the machine can perform many simultaneous operations, kind of in parallel, and if any of these operations "succeed", you get one of those answers out.

---

The point of this exercise is however that you show that Graph Isomorphism is contained in the complexity class NP by showing that you can *solve the problem* in nondeterministic polynomial time; by giving a nondeterministic algorithm for the problem.

The algorithm works as follows. Nondeterministically pick the correct permutation $\pi$, and then in deterministic polynomial time we can verify that $\pi$ is indeed a *witness* or a *certificate* for the fact that the two input graphs are isomorphic, by checking that $\pi(v)\pi(u) \in E'$ if and only if $uv \in E$.

If $\pi$ is *not* a permutation that proves that the graphs are isomorphic, you can therefore conclude that the graphs are indeed not isomorphic.

---

It is important to stress that this does not give rise to an algorithm you can actually implement in the real physical world, not without enumerating every permutation, at least, which as you correctly point out, cannot be done in polynomial time.
> 3 votes

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


# Question
Title: Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?
Suppose there are two strings, $S$ and $T$, and we want to find the length $l$ of the shortest substring of $S$ which contains all the characters in $T$, *in order*. (Assume the length of $T$ is bounded, so it doesn't need to be considered for determining time complexity.)

Here are some examples:

* $S$ = "abcabc", $T$ = "abc", $l = 3$, "\[**abc**\]abc".
* $S$ = "abcabc", $T$ = "acb", $l = 5$, "\[**a**b**c**a**b**\]c".
* $S$ = "ben thinks bananas are the best", $T$ = "bans", $l=7$, "ben thinks \[**ban**ana**s**\] are the best"

I found a solution to this using recursion which I believe is $O(n^2)$.

```
def ordered_moving_window(S, T, include_prefix=False):
    # Recursion base case
    if len(T) == 0:
        return 0

    shortest_length = float("inf")

    for i in range(len(S)):
        if S[i] == T[0]:
            # Recursively find all the other chars in the string
            length = ordered_moving_window(S[i+1:], T[1:], include_prefix=True) + 1

            # If this is being called recursively, then we need to include
            # all the characters before the first character we found
            # in our length calculation
            if include_prefix:
                length += i

            shortest_length = min(length, shortest_length)

    return shortest_length

print(ordered_moving_window("abcabc", "abc")) # 3
print(ordered_moving_window("abcabc", "acb")) # 5
print(ordered_moving_window("ben thinks bananas are the best", "bans")) # 7

```

I believe the worst case for this particular solution is something like $S$ = "aaaaaaaab", $T$ = "ab", where the solution would need to traverse down the list (which is $O(n)$) for each "a" in $S$ (of which there are $n$), leading to a total time complexity of $O(n^2)$.

A few years ago, my professor assigned me a version of this problem, and I submitted this $O(n^2)$ solution. In my solution writeup, I also mentioned that I didn't believe an $O(n)$ solution was possible. My justification was similar to:

> Consider a hypothetical $O(n)$ algorithm where $T$ = "abc". For $S$ = "ababc", the algorithm would need to ignore the first "ab", identify the solution "ab\[**abc**\]", and return $l = 3$. However, for $S$ = "abac", the algorithm would need to consider the first "ab" to identify the solution "\[**ab**a**c**\]" and return $l = 4$. Since the algorithm cannot look ahead to figure out whether it should consider or ignore a certain character, it cannot make this decision, and therefore such an algorithm cannot exist.

However, my professor disagreed with me, stating that an $O(n)$ solution to this problem is possible.

Since then, I've learned of the non-ordered minimum window substring problem, which is similar to the problem I listed earlier, but without the requirement that the characters be in order:

* $S$ = "abcabc", $T$ = "acb", $l=3$, "\[**abc**\]abc"
* $S$ = "ben thinks bananas are the best", $T$ = "bans", $l = 5$, "ben think\[**s** **ban**\]anas are the best"

This can be solved in $O(n)$ time complexity by keeping pointers to the start and end of the window, using a map to keep track of the characters in the window, advancing the end pointer when the sequence is not valid, and advancing the start pointer when the sequence is valid:

```
def moving_window_substring(S, T):
    # Build a table of the count of each character in T
    # (i.e., the chars we need our window to have)
    needed_chars = {}
    for char in T:
        if char in needed_chars:
            needed_chars[char] += 1
        else:
            needed_chars[char] = 1

    # Set up the window
    start = 0
    end = 0
    shortest_length = float("inf")
    needed_chars_count = len(T)

    # Grow the window until we have all the chars we need
    while end < len(S):
        end_char = S[end]

        if end_char in needed_chars:
            # If we needed this character, decrement the number of chars we need
            needed_chars[end_char] -= 1
            if needed_chars[end_char] >= 0:
                needed_chars_count -= 1

        if needed_chars_count == 0:
            # The window is valid, we have all the chars we need
            # Start shortening the window until it is no longer valid
            while True:
                start_char = S[start]

                if start_char in needed_chars:
                    if needed_chars[start_char] < 0:
                        needed_chars[start_char] += 1
                    else:
                        # We need this character, break out of the loop
                        break

                start += 1

            shortest_length = min(shortest_length, end - start + 1)

        end += 1

    return shortest_length

print(moving_window_substring("abcabc", "abc")) # 3
print(moving_window_substring("abcabc", "acb")) # 3
print(moving_window_substring("ben thinks bananas are the best", "bans")) # 5
print(moving_window_substring("ben thinks bananas are the bans", "bans")) # 4

```

Is there a similar $O(n)$-time-complexity solution to the *ordered* version of the problem?

# Answer
> 4 votes
Yes, if the length of `T` can be considered as a constant.

---

Here is an efficient algorithm.

```
def shortest_super_subsequence(S, T):
    if len(T) == 0: return 0
    shortest_length = float("inf")

    indices = [-1] * len(T)
    while True:
        for i in range(0, len(T)):
            if i == 0:
                indices[0] = S.find(T[0], indices[0] + 1)
            else:
                indices[i] = S.find(T[i], max(indices[i - 1] + 1, indices[i]))
            if indices[i] == -1:
                return shortest_length
        shortest_length = min(shortest_length,
                              indices[-1] - indices[0] + 1)

```

---

The algorithm above uses `indices[i]` to track the position of `T[i]` found in each search of a subsequence that contains `T`. Each time we will move to right by one position to search for `T[0]`. For other character `T[i]`, we will start search at the later position of its current position and one position later than the current position of `T[i-1]`.

Let `len(S)` be $n$. The algorithm above runs in time $O(n)$ if the length of `T` is considered as a constant. If `len(T)` is denoted by variable $m$, it runs in time $O(nm)$, since all updates on `indices[j]` need $O(n)$ time for each `j`. The worst case happens in situations like `S="abdabdabdabdabdabdabdc"` and `T="abababc"`.

The algorithm can be speed-up by breaking the inner loop if `indices[j]` stays the same. Although significant, this improvement does not change the asymptotic time-complexity.

The algorithm can be thought as sliding a window (of varying size) from index `indices[0]` to `indices[-1]`.

---
Tags: time-complexity, substrings
---


# Question
Title: $O(n^2)$ running time vs $O(n^2)$ worst case
The use of the phrase "worst-case running time" is really confusing to me. Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of the algorithm is sub-quadratic? If it is then why do we say that $O(n^2)$ is the worst case time? Or do they have different meanings?

Thank you.

# Answer
Suppose that you have an arbitrary array of $n$ numbers, and you give it to Quicksort to sort.

The *expected* running time of the algorithm is $O(n \log n)$. However, if the array is sorted, but in the wrong direction, and you pick the first element as pivot, then the algorithm might actually run in time $O(n^2)$.

That means that if you look at how Quicksort behaves with increasingly larger arrays of reversely sorted data, the time it uses grows as $n^2$.

However, if you spend $O(n)$ time to shuffle the array before sorting it, the *expected* running time is $O(n \log n)$; i.e. very few time will the algorithm spend close to $O(n^2)$ many operations.

---

A different example is with respect to *amortized* complexity. For example, adding a single element to an ArrayList in Java takes $O(1)$ time, most of the time. However, on a rare occasion, Java needs to create a new array and copy all the elements over to this new one. That takes $O(n)$ time.

This means that the *worst case complexity* for ArrayList.add is $O(n)$, but if you do this operation $n$ times, the total complexity is *also* $O(n)$, so we say that the *amortized* complexity is $O(1)$.
> 3 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: The optimized numbers of variables and clauses to encode a graph coloring problem in CNF
## Problem Statement

Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of **graph coloring** is to assign each vertex $v \in V$ a $\text{color} (v) \in C$ such that $\forall \langle v, w\rangle \in E, \text{color}(v) \not= \text{color}(w)$. Now we **encode** an instance of graph coloring problem into a CNF (conjunctive normal formula) $F$.

> Note: The word "encode" means that we'll know a graph coloring problem if a CNF is given, and also will know a CNF if a graph coloring problem is given.

* What is the minimal number of propositional variables in $F$?
* What is the minimal number of clauses in $F$?

## Original Version

A solution to a **graph coloring** problem is an assignment of colors to vertices such that no two adjacent vertices have the same color. Formally, a finite graph $G = \langle V, E\rangle$ consists of vertices $V = \\{v\_1, \cdots, v\_n\\}$ and edges $E = \\{ \langle v\_{i\_1} , w\_{i\_1} \rangle , \cdots , \langle v\_{i\_k} , w\_{i\_k} \rangle \\}$. The finite set of colors is given by $C = \\{c\_1, \cdots , c\_m \\}$. A problem instance is given by a graph and a set of colors: the problem is to assign each vertex $v \in V$ a $\text{color}(v) \in C$ such that for every edge $\langle v, w\rangle \in E$, $\text{color}(v) \not= \text{color}(w)$. Clearly, not all instances have solutions.

Show how to encode an instance of a graph coloring problem into a PL formula $F$. $F$ should be satisfiable iff a graph coloring exists.

1. Describe a set of constraints in PL asserting that every vertex is colored. Since the sets of vertices, edges, and colors are all finite, use notation such as “$\text{color}(v) = c$” to indicate that vertex $v$ has color $c$. Realize that such an assertion is encodeable as a single propositional variable $P^c\_v$.
2. Describe a set of constraints in PL asserting that every vertex has at most one color.
3. Describe a set of constraints in PL asserting that no two connected vertices have the same color.
4. Identify a significant optimization in this encoding. Hint: Can any constraints be dropped? Why?
5. If the constraints are not already in CNF, specify them in CNF now. For $N$ vertices, $K$ edges, and $M$ colors, how many variables does the optimized encoding require? How many clauses?

---

As suggested by @D.W.♦, I copy the original problem here (above is the version simplified by me). This original version is **Exercise 1.6** from:

> Bradley, A. and Manna, Z. (2007). The Calculus of Computation. Dordrecht: Springer, p.34.

## My Analysis

The optimized CNF within my ability is to use propositional variable $P\_v^c$ to indicate that $\text{color}(v) = c$. Here we can only use at most $|V|$ colors of all colors, i.e., the number of colors in our design of propositional variables is $|V|\min (|V|, |C|)$. Then we can build a CNF: $$F\_0 = \bigwedge\_{v \in V} (\bigvee\_{c \in C} P\_v^c) \wedge \bigwedge\_{v \in V} (\bigvee\_{c\_1 \not= c\_2 \in C} (\neg P\_v^{c\_1} \vee \neg P\_v^{c\_2})) \land \bigwedge\_{c \in C \\ \langle v, w\rangle \in E} (\neg P\_v^c \vee \neg P\_w^c)$$

In this variable, there're $|V| \min (|V|, |C|)$ propositional variables and $2|V| + |C||E|$ clauses.

I failed to prove $F\_0$ is the CNF with neither the least propositional variables nor the least clauses. Is there an another CNF $F'$ with less propostional variables or less clauses? How to find the minimal number of propositional variables and clauses of legal CNFs?

# Answer
> 2 votes
The problem statement needs to be specified more precisely to be meaningful.

If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-colorable or not. I suspect this isn't what you're looking for, so you probably need to define the problem statement more carefully to be able to answer the question in a useful way. For instance, perhaps you need to specify exactly what properties you want $F$ to have.

# Answer
> 1 votes
I think optimization is we can drop the second constraint in PL formula. If a node is assigned with multiple colors, we can just have to pick one color, as they will all satisfy the edge constraints. So F is satisfiable iff a graph coloring exists.

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


# Question
Title: Finding infinitely many Myhill–Nerode equivalence classes
I need to prove the following languages are not regular and I'm having a tough time identifying the equivalence class that can have an infinite index.

How would I go about doing these? I know how to prove it after finding the equivalence class but any tips on how to identify the one that has the infinite index?

I know I should find the equivalence class where there are distinct extensions for each string belonging to $L$, but could anyone help me out on these 2:

1. $0^m 1^n$ where $m$ is even or $m$ is greater than $n$
2. $0^m 1^n$ where $\text{gcd}(m,n)=1$.

# Answer
> 2 votes
Let's consider your second example (the first example is easier). We will be interested in $$ F(m) = \\{ n : 0^m 1^n \in L \\} = \\{ n : \gcd(m,n) = 1 \\}. $$ If $F(m\_1) \neq F(m\_2)$, then $m\_1$ and $m\_2$ belong to two different equivalence classes.

From $F(m)$ you can recover the set of primes dividing $m$: $p \in F(m)$ iff $p \not\mid m$. In particular, this shows that if $p\_1 \neq p\_2$ are two different primes, then $F(p\_1) \neq F(p\_2)$. Since there are infinitely many primes, we conclude that there are infinitely many different equivalence classes.

The first example can be analyzed in a similar way (considering only odd $m$).

---
Tags: finite-automata
---


# Question
Title: Regular languages closed under prefix operation
Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$ \mathrm{LANGUAGE}\_2(D) := \\{ d \mid d,t \in A^\* \text{ and } dt \in D \\} $$ (This problem is taken from *Introduction to the Theory of Computation* by Mike Sipser.)

# Answer
> 1 votes
(1) If the regular language is given by a *finite state automaton* $M$ the language of prefixes can be obtaines by extending the set of accepting states. Choose all states that lie on a path from initial state to one of the original accepting states.

The prefix operation is a special case of the operation quotient

$K/L = \\{ x \mid xy\in L, \text{ for some } y\in K\\}$

where we take $L$ to be the language $A^\*$ of all strings. Surprisingly, the regular languages are closed under quotient by *arbitrary* languages. See are regular languages closed under division, and Closure against right quotient with a fixed language.

(2) If the regular language is given by a *regular expression* instead, then we can construct a new regular expression for the prefix language, directly using the inductive definition of regular expressions. See Regularity of “middles” of words from regular language.

(3) Also, there is a characterization in terms of *Myhill-Nerode equivalence classes*: a language is regular iff its number of equivalence classes is finite. In can be observed that $x \equiv\_L y$ implies $x\equiv\_{\text{pref }L} y$, so if $\equiv$ is of finite index, then so is $\equiv\_{\text{pref }L}$. More on this see Myhill-Nerode and closure properties.

(As Yuval noted, the exercise is somewhat standard, but I would like to have some remarks here to close the issue. Feel free to add relevant links.)

---
Tags: formal-languages, regular-languages, finite-automata, closure-properties
---


# Question
Title: Understanding the definition of a language
Could you please help me understand the following Language

$L = \\{ a | a ∈ \\{0, 1\\}^∗, |a| = k ≥ 4, a = a\_1a\_2...a\_{k−1}a\_k, ∃i ∈ N, 1 ≤ i \< k : a\_i = a\_{i+1} \\}$ what does $a\_i = a\_{i+1}$ mean? Could you please give me an example of word in $L$?

# Answer
> 1 votes
The expression "$a\_i = a\_{i+1}$" means "$a\_i$ and $a\_{i+1}$ are equal".

Presumably $a\_i$ is a symbol, that is, $a\_i \in \\{0,1\\}$. Therefore the condition states that $a$ contains at least four symbols, and there are two adjacent symbols which are equal, that is $a$ contains either $00$ or $11$ as a substring. Stated differently, $a$ contains at least four symbols and it doesn't consist of alternating zeroes and ones (i.e. you are not allowing 0101, 01010, ... or 1010, 10101, ...).

# Answer
> 1 votes
Let's break it down

$\\{\\; a \mid a ∈ \\{0, 1\\}^∗$ $\quad$ a language of words over the alphabet $\\{0,1\\}$

$|a| = k ≥ 4$ $\quad$ with length $k$ at least $4$

$a = a\_1a\_2...a\_{k−1}a\_k$ $\quad$ lets call the symbols of $a$ with indices $a\_1$ to $a\_k$ $\quad$

(this is a little implicit here, but OK)

$\exists i \in N$, $1 ≤ i \< k$ $\quad$ there exists a natural number $i$, a position in the string $a$,

$a\_i = a\_{i+1} \\; \\}$ $\quad$ such that the two consecutive letters $a\_i$ and $a\_{i+1}$ are equal.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$
> Define a sequence $c\_1,c\_2,\dots$ by the equations $$ c\_1=0, \quad c\_n = 4c\_{\lfloor n/2 \rfloor} + n \text{ for all } n \> 1. $$ Prove that $\frac{(n+1)^2}{8} \< c\_n$ for all $n \geq 2$.
>
> *Hint:* $\lfloor \frac{n}{2} \rfloor \geq \frac{n-1}{2}$ for all $n$.

How do I solve this question? I have no idea how to start.

# Answer
Let's start with the case $n = 2^k$. We have \begin{align} c\_{2^k} &= 2^k + 4c\_{2^{k-1}} \\ &= 2^k + 4 \cdot 2^{k-1} + 16c\_{2^{k-2}} \\ &= \cdots \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2^1 + 4^k c\_1 \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2 = \\ &= 2^k(1 + 2 + 2^2 + \cdots + 2^{k-1}) \\ &= 2^k(2^k-1). \end{align} It is easy to prove by induction that the sequence $c\_n$ is monotone. Therefore, if $2^k \leq n \< 2^{k+1}$, $$ c\_n \geq c\_{2^k} = 2^k(2^k-1) \> \frac{n}{2}\left(\frac{n}{2}-1\right). $$ Now $$ \frac{n}{2}\left(\frac{n}{2}-1\right) \geq \frac{(n+1)^2}{8} \Longleftrightarrow 2n(n-2) \geq (n+1)^2 \Longleftrightarrow n^2 \geq 6n + 1. $$ This holds for all $n \geq 7$. You can check that your inequality holds for $n=2,3,4,5,6$ directly.

---

You can also likely prove the inequality directly by induction, but the argument above is more similar to stuff you might actually see later on. The idea is that we find a specific type of $n$ for which $c\_n$ is particular easy to calculate and to compare to $n$, and then we try to understand $c\_n$ for all $n$ using these specific values.
> 1 votes

---
Tags: discrete-mathematics
---


title: Show that the Language is irregular

text:
# Question
Title: Show that the Language is irregular
I was solving some problem from past test, there was this question:

Use the closure property of regular language to show the language $L$ is not regular

$$L =\\{ a^3 b^n c^{n-3} \mid n\>3\\} $$

I know how to solve it using Pumping Lemma, but how to solve it with closure property?

Also, I know that to prove that a language L is not regular using closure properties, the technique is to combine L with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, but I can't figure out with whom to combine.

I saw some similar questions but didn't get ideas about how to do this one.

Any hints?

Thanks.

# Answer
> 1 votes
Suppose that $L$ is regular. Then so is $L' = L \circ \\{ccc\\} = \\{a^3 b^n c^n \mid n \ge 3\\}$. This implies that $L'' = (aaa)^{-1}L' = \\{b^n c^n \mid n \ge 3\\}$ is also regular and, in turn, that $L''' = L'' \cup \\{\varepsilon, bc, bbcc\\} = \\{b^n c^n \mid n \in \mathbb{N}\\}$ is regular. This is a contradiction since $L'''$ is known not to be regular.

---
Tags: regular-languages, closure-properties
---


title: Maximize 5-independent gifts on a path

text:
# Question
Title: Maximize 5-independent gifts on a path
**Question**: Assume there are $n$ distinct gifts on the real line. Their positions are $\\{x\_1, ..., x\_n\\}$ and each of them has an individual value $p\_i$.

Now you can choose a subset of them such that any two gifts in your choice are at a distance more than 5. What’s the maximum total value you can get? Design an algorithm to solve this problem, analyze the running time and prove the correctness.

You can assume the gifts are given in order of their locations, i.e., $x\_1 \< x\_2 \< ... \< x\_n$.

I have tried memoization and breaking down the problem into smaller steps but I am not sure what this specific sub case would look like.

# Answer
Here is some pseudocode that illustrates the recursive idea.

1. **If you choose** to take *this* element, then you have to skip ahead 6 steps.
2. **Otherwise** you skip this element and go to the next.

```
def solve(array, index):
    if index >= len(array):
        return 0
    this_one       = array[index]             # the value x_i
    opt_five_steps = solve(array, index + 6)  # the opt of array[i+6:]
    opt_successor  = solve(array, index + 1)  # the opt of array[i+1:]
    return max(this_one + opt_five_steps,
               opt_successor)

```

Clearly, this can be turned into a DP algorithm, or memoized as is.
> 2 votes

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


# Question
Title: Can the maximum single sell profit by divide and conquer be O(n)?
The single sell profit problem is:

> Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day.

There is a solution with a single scan that is easy to implement and runs in $O(n)$. This question is not about that. It's about the divide-and-conquer solution.

I've read twice that the divide-and-conquer solution to this problem is $O(n \log n)$: once when this problem is discussed in *Elements of Programming Interviews in Python* by Aziz, Lee and Prakash (it's problem 5.6), and once in these PDF lecture notes by Kevin Zatloukal of UW (page 23). Both these sources say the divide and conquer solution is slower than a simple scan.

Neither source presents an implementation (it's not the best approach, so fair enough), and the descriptions are a little terse, but reading between the lines they seem to describe a simple divide-and-conquer down to a base case of a single element, whether the merged result is the maximum of the best trade in the two subproblems and the maximum price in the right minus the maximum price in the left.

Here's that in Python

```
def best_trade(prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    else:
        best_left = best_trade_2(prices[: len(prices) // 2])
        best_right = best_trade_2(prices[len(prices) // 2 :])
        return max(
            best_left,
            best_right,
            max(prices[len(prices) // 2 :]) - min(prices[: len(prices) // 2]),
        )

```

The running time of this for a problem of size $n$, $T(n) = 2 T(n/2) + O(n)$ because the `max`/`min` call outside the recursion are O(n). By the Master Method analysis this means the algorithm has time complexity $O(n \log n)$ ($a = 2$, $b = 2$, $d = 1$ so we're in the $a = b^d$ case where the complexity is $O(n^d \log n)$).

My question is: can this problem be solved by divide-and-conquer in $O(n)$?

# Answer
Answering my own question, yes! The trick is to do the work to compute the max and min of the sublists in the divide-and-conquer recursion rather than when merging the results.

To do this, you need an inner function that returns not just the best trade in a subproblem, but also it's min and max. The combine step is then $O(1)$ rather than $O(n)$.

Here's what that looks like:

```
def best_trade(prices: List[int]) -> int:
    """
    Divide-and-conquer in O(n).
    """
    def f(start: int, end: int) -> Tuple[int, int, int]:
        if start == end:
            return 0, prices[start], prices[start]
        else:
            best_left, min_left, max_left = f(
                start,
                start + (end - start) // 2,
            )
            best_right, min_right, max_right = f(
                start + (end - start) // 2 + 1,
                end,
            )
            return (
                max(best_left, best_right, max_right - min_left),
                min(min_left, min_right),
                max(max_left, max_right),
            )

    # `else 0` for the corner case where prices = []
    return f(0, len(prices) - 1)[0] if prices else 0

```

Note that the inner function passes the start and end index of the subproblem down the stack, rather than taking slices, because taking slices is $O(k)$, where $k$ is the length of the slice. By passing pointers we keep the work done outside the recursion to $O(1)$.

With this implementation, $T(n) = 2 T(n/2) + O(1)$ which implies this divide-and-conquer algorithm is $O(n)$.

The general pattern here is to do more work (or return more information) than is strictly necessary in the recursion to reduce the work outside the recursion. In this case, the "extra" work done inside the recursion is trivial, so the running time is significantly reduced, at the cost of a slightly less legible bit of code.

One final point: of course the single scan solution is also $O(n)$ and significantly simpler than either divide-and-conquer solution:

```
def best_trade(prices: List[int]) -> int:
    """
    Single scan in O(n).
    """
    if not prices:
        return 0
    lowest = prices[0]
    best = 0
    for p in prices:
        lowest = min(p, lowest)
        best = max(best, p - lowest)
    return best

```
> 1 votes

---
Tags: time-complexity, divide-and-conquer
---


# Question
Title: Polynomial time algorithm to find an induced cycle in non-chordal graph
Let $G=(V,E),n=|V|,m=|E|$ be a graph. There exists an algorithm with time complexity $O(n+m)$ to test if given graph $G$ is chordal. If I know the graph is NOT chordal, is there a algorithm to find any of the cycles without a chord of length $k\geq 4$ (running in polynomial time of course)?

# Answer
> 0 votes
Since I found a solution myself, I'm gonna post the idea. It suffices to find chordless paths. For a vertex $v$ and $u$ its neighbour, we can delete the edge $\\{u,v\\}$ from $G$ and find a chordless $u$-$v$ paths. Connecting these will result in a chordless cycle.

A very simple algorithm finding such paths is described here. Naive algorithm runs in time $O(n(n+m))$ per $u$-$v$ path, they further give more efficient algorithm with running time $O(n+m)$ per $u$-$v$ path.

---
Tags: algorithms, graphs
---


title: Master's Theorem recurrence

text:
# Question
Title: Master's Theorem recurrence
Given recurrence relation $T(n)=8T(n/6)+n \log n$, I get that the running time of the leaves should be $n^{\log\_6 8}$ and $f(n)$ should be $n \log n$, but how can I know which one is bigger ?

# Answer
$n^{\log\_6 8} = n^c$ for some $c\>1$ (you can tell that $\log\_6 8 \> 1$ from the fact that $8\>6$). Then $n^c = \omega(n \log n)$.

Indeed: $$\lim\_{n \to +\infty} \frac{n^c}{n \log n} = \lim\_{n \to +\infty} \frac{n^{c-1}}{\log n} = \lim\_{n \to +\infty} \frac{(c-1)n^{c-2}}{1/n} = \lim\_{n \to +\infty} (c-1)n^{c-1} = +\infty.$$
> 1 votes

---
Tags: algorithms, master-theorem
---


# Question
Title: Can the lambda string be generated in any grammar?
I'm still quite new to regex, and I've seen topics online of people talking about removing lambda productions, but that has yet to be discussed in the class and the only formal definition of the rules in a grammar that I was given by my teacher:

$rule ∈ V$ $\times$ $(V ∪ Σ)^\*$

where V is the set of variables and Σ is the set of terminals. Going strictly from this definition, I would assume I should be able to generate an empty string since V and Σ are both sets and that I believe the empty string can be generated from either of those sets.

For an exam I was given this definition of a grammar G:

$S \rightarrow aS | Sb | a$

and I was later asked to write a regex that would represent this grammar. I figured that $S \rightarrow λ$ should be implicit. In other words, I should be able to generate the string 'b' from $Sb \rightarrow λb$

The regex I gave was $a^\*b^\*$

The T.A. marked it as incorrect because my regex can generate b, but the grammar G cannot, and because G does not have $S \rightarrow λ$

Can someone explain why $S \rightarrow λ$ would not be included in this grammar based on the definition of $rule ∈ V$ $\times$ $(V ∪ Σ)^\*$?

Thank you!

# Answer
No. $S \to \lambda$ is not implicit. It is only present if it is explicitly listed in the grammar, otherwise there is no such production. There are no implicit rules. You've misinterpreted the definition. The definition says what kinds of rules are allowed to be present in the grammar, not what will definitely be present.
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: Reason behind declaring iteration variables on a method level
Lately, I have been in touch with some C++ snippets, and I have a very strange observation on the tiny detail:

Most of the times, I see, that people declare iteration variables outside of the for/while definitions, and then initialise them inside for/while definitions, like:

```
int i, j, k;

for(i = 0; ..; ..) { } //note, this omits declaration of "i"

```

I wonder what is the reason behind this? why would one want to scope a loop-level temporary variable and its identifier on a method-level?

Is this conventional? does it help compilation's lexical translation? an optimisation for static code analysis? what is the purpose?

It (important) certainly looks ugly, especially when there are numerous variables in the method; it (important) reserves variable identifiers (on a method-level); and (less important) it definitely occupies more space in the memory.

Any points?

Appreciations.

# Answer
No, this is not conventional if writing C++. People who do this might have a C background. Indeed, in old C89, you had to declare all variables at the beginning of your scope. Of course, even if you didn't start programming with C89, you might have been exposed to out-dated guides or material and you might have picked up the habit. As we know, it is sometimes difficult to unlearn something.

In general, variables should be declared as close as possible to their actual site of usage and thus we don't unnecessarily pollute the scope, exactly as you point out. This is also defensive programming, it helps readability and protects from mistakes.
> 1 votes

---
Tags: c++, syntax
---


# Question
Title: For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?
I am stumped on the following question:

For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also contains a sink?

I know that the sink has the highest post-order number, so I am inclined to say False, but I do not know if that reasoning is accurate.

# Answer
The statement is false. Consider the directed graph $G=(V,E)$ where $V=\\{1,2\\}$ and $E=\\{(1,2), (2,1)\\}$.

The graph only contains a single strongly connected component, namely $G$ itself. However no vertex in $V$ is a sink.
> 0 votes

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


# Question
Title: Information on Tavori and Dreizin ranged hash function?
While doing some digging around in the GNU implementation of the C++ standard library I came across a section in `bits/hashtabe.h` that refers to a hash function "in the terminology of Tavori and Dreizin" (see below). I have tried without success to find information on these people, in the hopes of learning about their hash function -- everything points to online versions of the file that the following extract is from. Can anyone give me some information on this?

```
*  @tparam _H1  The hash function. A unary function object with
*  argument type _Key and result type size_t. Return values should
*  be distributed over the entire range [0, numeric_limits<size_t>:::max()].
*
*  @tparam _H2  The range-hashing function (in the terminology of
*  Tavori and Dreizin).  A binary function object whose argument
*  types and result type are all size_t.  Given arguments r and N,
*  the return value is in the range [0, N).
*
*  @tparam _Hash  The ranged hash function (Tavori and Dreizin). A
*  binary function whose argument types are _Key and size_t and
*  whose result type is size_t.  Given arguments k and N, the
*  return value is in the range [0, N).  Default: hash(k, N) =
*  h2(h1(k), N).  If _Hash is anything other than the default, _H1
*  and _H2 are ignored.

```

# Answer
I read that passage as saying that Tavori and Dreizin introduced the terminology/concept of a "range-hashing function". Presumably, that's a name they use for a hash function with some special properties. In other words, I read that as implying not that Tavori and Dreizen introduced a specific hash function, but that they talk about a category of hash functions and gave it a name.

I don't know if that is what the authors actually meant; that's just how i would interpret it.

I tried searching on Google Scholar for these names and found nothing that seemed relevant. A quick search turns up a reference to Ami Tavori at IBM (a past student of Prof. Meir Feder, working on computer science), but I don't know if that's who this is referring to.
> 1 votes

# Answer
Ami Tavory, Vladimir Dreizin (IBM), and Benjamin Kosnik (Red Hat) authored the "Policy-Based Data Structures" library. Ideas developed there were later used in the GNU implementation of the C++ standard library.

Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple way:

https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb\_ds/

In particular, range hashing approach is described here:

https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb\_ds/hash\_based\_containers.html
> 2 votes

---
Tags: hash
---


# Question
Title: Closed-form expression for the sums of the rows of the Trinomial triangle
There is a question in the second chapter of the book that I'm unable to solve, and unfortunately algorist.com does not provide a rigorous enough solution, or maybe I can't quite understand it. Here is the question:

I've noticed the sums of rows are the powers of 3, and it's intuitively obvious that the sums of rows are multiples of 3, however I can't prove that they are **powers** of 3.

Any help would be much appreciated.

*The Algorithm Design Manual* from *Steven S. Skiena* You can get it from here.

Also here is the solution I found on algorist.com .

# Answer
Intuitively, each integer on the $i$-th row participates exactly three times in the sum of the integers on the $(i+1)$-th row. This means that the sum $S\_{i+1}$ of the integers in the $(i+1)$-th row must be exactly $3$ times as large as the sum $S\_i$ of the integers in the $i$-th row, i.e., $S\_{i+1}=3S\_i$ (and $S\_1=1)$. A formal argument is as follows:

Let $x^{(i)}\_j$ be the $j$-th integer on the $i$-th row and define $S\_i = \sum\_{j=1}^{2i-1} x^{(i)}\_j$. For simplicity define $x^{(i)}\_j = 0$ whenever $j \le 0$ or $j \ge 2i$. You can show by induction on $i$ that $S\_i = 3^{i-1}$.

The base case $i=1$ is trivially true since $S\_1 = x^{(1)}\_1 = 1 = 3^0 = 3^{1-1}$. Suppose now that the claim holds for $i\ge 1$. Then, the claim must also hold for $i+1$. Indeed:

$$ \begin{align\*} S\_{i+1} &= \sum\_{j=1}^{2i+1} x^{(i+1)}\_j = \sum\_{j=1}^{2i+1} \left( x^{(i)}\_{j-2} + x^{(i)}\_{j-1} + x^{(i)}\_{j}\right) = \sum\_{j=1}^{2i+1} x^{(i)}\_{j-2} + \sum\_{j=1}^{2i+1} x^{(i)}\_{j-1} + \sum\_{j=1}^{2i+1} x^{(i)}\_{j} \\ &= 3 \sum\_{j=1}^{2i-1} x^{(i)}\_{j} = 3S\_i = 3 \cdot3^{i-1} = 3^i. \end{align\*} $$
> 2 votes

# Answer
This is much like Pascal's triangle of course, but adding three neighbours, rather than two. Here is the combinatorial argument, which works just like the binomial case.

Assume in each cell you can move down, moving to the cell below, or two one of the neightbours of it. Then the numbers in the triangle just represent the number of paths that can be taken to move from the top cell to the cell at a specific position. (That can be proved by induction: the paths to a given cell all go through exactly one of the three neighbours above.) Now the sum of the numbers in the $i$th row, equals the number of paths to the $i$th level. This is a power of $3$, because in each level we can move in three directions: $3\times 3 \times\dots\times 3$ choices are being made.
> 2 votes

---
Tags: books, summation
---


title: Equivalent regular expressions - Proof

text:
# Question
Title: Equivalent regular expressions - Proof
I came across the following two regular expressions $r\_1 = 0^+(10^+0)^∗0^\*$ and $r\_2 = 0^+(10^+0)^∗$.

I know, in general, proving if two regular expressions are equivalent is hard in terms of time complexity, and that there are several algorithms to determine this. (e.g, convert regex to DFAs.) However, I wanted to know if there is a simpler method for this particular example.

Firstly, they seem to be equivalent.

Intuitively, $r\_1$ describes all the words that $r\_2$ does since both expressions are the same except for the $0^\*$ at the end of $r\_1$.

Next, let us rearrange $r\_1$ and $r\_2$ like so:

$r\_1 = 0^+(100^+)^∗0^\*$

$r\_2 = 0^+(100^+)^∗$

Note that although we changed the order of the expression in the parentheses, it still expresses the same idea, which is *zero or more repetitions of one 1 followed by at least two zeroes*.

This english description seems to apply even when we append the $0^\*$ at the end of $r\_1$. Because if we had $m$ zeroes at the end of a word (e.g, 00000100100000), all we would have to do is to use $m$ zeroes for the last repetition of the expression in the parentheses, and just ignore the $0^\*$.

This is kind of like my intuition, but I wanted to know if there is any formal proof for this? Or even, I might be wrong, and these regex are not equivalent and there is a counterexample.

# Answer
> 2 votes
Using $s^\* = \epsilon + s^\*s$, we have $$ 0^+(10^+0)^\*0^\* = \\ 0^+ (\epsilon + (10^+0)^\*10^+0)0^\* = \\ 0^+0^\* + 0^+(10^+0)^\*10^+00^\* $$ Similarly, $$ 0^+(10^+0)^\* = 0^+ (\epsilon + (10^+0)^\*10^+0) = \\ 0^+ + 0^+(10^+0)10^+0 $$ Therefore it suffices to convince oneself that $0^+0^\* = 0^+$ and $0^+00^\* = 0^+0$.

If you want to turn it into a completely formal proof, you'll need to satisfy a list of axioms and derivation rules, but the proof will likely follow similar steps.

---
Tags: regular-expressions
---


title: A problem about asymptotic functions

text:
# Question
Title: A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?

My idea: i think because of for any $f:N\rightarrow N$, and $g:N\rightarrow N$ then $f(n)+g(n)= O(\max \\{f(n),g(n)\\})$ then there are no two such functions. is my argument is valid?

# Answer
Let $f(n) = \begin{cases} 1 & \mbox{if $n$ is odd}\\ n & \mbox{if $n$ even} \end{cases}$, and $g(n) = \begin{cases} n & \mbox{if $n$ is odd}\\ 1 & \mbox{if $n$ even} \end{cases}$.

Then, $h(n)=f(n)+g(n) = n+1 \not\in O(f(n))$.

Indeed, for any $n\_0$ and $c\>0$, there is some $n \ge n\_0$ such that $h(n) \> c f(n)$. Simply pick $n$ as an odd integer greater than $\max\\{c, n\_0\\}$, e.g., $n=2\max\\{c, n\_0\\}+1$. Then $h(n) = n+1 = 2\max\\{c, n\_0\\} + 2 \> c = c \cdot 1 = c f(n)$.

A similar argument shows that $h(n) \not\in O(g(n))$.
> 1 votes

---
Tags: algorithms, complexity-theory, data-structures, asymptotics
---


# Question
Title: Pumping lemma for regular languages. Proof
Please help me understand the following

$L = \\{ a | a ∈ \\{0, 1\\}^∗, |a| = k ≥ 4, a = a\_1a\_2...a\_{k−1}a\_k, ∃i ∈ N, 1 ≤ i \< k : a\_i = a\_{i+1} \\}$

To prove: The language $L$ has regular pumping property

My argumentation:

Let $p = 4 $. Let $z$ in $L$, with $z$ $\geq $ $p$. Set $u$ to $\epsilon$. Than $x$ is the first letter, and $w$ the rest.

$x$ $\neq$ $\epsilon$

For all $i$ $\geq $0$: ux^iw$ is in $L$

But if i set i to 0 the word is not in the language? And therefor does not have the regular pumping property? What am i missing? Example $0010$, after pumping $4$ $\geq $ $010$?

# Answer
I assume that you want to show that the language $L$ **does** satisfy the Pumping Lemma, as it indeed is regular. In words your language consists of all strings that have length at least 4 and contain two consecutive symbols that are the same. The position of a pair of equal letters letters is indicated here with $i$. (Note $i$ in general is not unique.)

So we need to explain that all strings in the language (above a certain length) can be pumped within the language. You must realize that your division into $uxw$ can actually depend on the string $a$ itself.

So if $a$ starts with a repeated letter, e.g., $a = 00\dots$, we can pump the third letter. Otherwise if the repeated pair is assumed to be not in the first position, we can then pump the first symbol and we keep the repetition in the string while pumping.
> 1 votes

# Answer
It suffices to show that the language is regular.

The language $L\_1$ of all words on $\\{0,1\\}^\*$ with at least two identical consecutive symbols is regular (since it can be described be the following regular expression: $(0\mid1)^\*(00\mid11)(0\mid1)^\*$).

The language $L\_2$ of all words on $\\{0,1\\}^\*$ of length at least $4$ is clearly regular (a regular expression is $(0 \mid 1)(0 \mid 1)(0 \mid 1)(0 \mid 1)(0 \mid 1)^\*$).

By the closure properties of regular languages, $L = L\_1 \cap L\_2$ must also be regular.
> 0 votes

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


# Question
Title: Can someone help me understand the time and space complexity?
Can anyone help me understand the time and space complexity here? I know `zip()` is *O(1)* and `sorted()` is *O(n)*. The loop has the operation `min()` inside but is operating on just 2 values so is that also *O(1)*? If so then every operation in the loop is *O(1)* so the overall time complexity is *O(n)* correct? For space, `z` could grow to n as `a` and `b` grow to n as well so space is *O(n)*?

```
a = [3, 1, 2]
b = [1, 2, 3]
c = 4
def foo(a: list[int], b: list[int], c: int) -> int:
    ans = 0
    if not a:
        return ans
    z = sorted(zip(a, b), reverse=True)
    for x, y in z:
        if c > 0:
            x = min(x, c)
            ans += x * y
            c -= x
    return ans

```

# Answer
> 2 votes
Assuming that `sorted()` really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches.

You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is **not** creating a list that contains pairs of elements from `a` and `b` but just returning an **iterator** to these pairs. Going through the list implicitly returned by this iterator takes $O(n)$ time, even just to construct it (e.g., `list(zip(a,b))`). In your particular case this doesn't really matter since the time complexity will be $\Omega(n)$ anyway.

You say that `sorted()` takes $O(n)$ time. This is not impossible, but it's at least suspicious (have you checked in the python documentation/implementation?). There is no algorithm that can sort a list of $n$ elements in time $O(n)$ by only performing comparisons. The implementation of `sorted()` would need to be particularly clever and recognize that you are sorting small integers.

Probably `sorted()` just takes $O(n \log n)$ time and $O(n)$ space, which would result in the same overall time and space complexities for your algorithm.

---
Tags: time-complexity, optimization, space-complexity, python
---


# Question
Title: Break keyword outside a loop is syntax error or semantic error?
I am designing a simple compiler for my university project. In my programming language, the **break** keyword is allowed.

I want to know whether **break** keyword occurs outside a loop should be a syntax error or semantic error. I want to know what is the best approach.

If it is a syntax error I can do it in the grammar file. But if it is a semantic one then I can do it in a pass. But I don't know which one is the better approach.

# Answer
> 13 votes
Both work, so how you do it is up to you. But there are a couple of reasons to consider doing it during a post-parse analysis:

1. While it is certainly possible to define two different types of `block`, one in which `break` is legal and the other one in which it isn't, the result is a lot of duplication in the grammar, and a certain complication because you have to allow `break` inside blocks which are themselves contained inside a looping construct. If you allow compound statements without explicit blocks, like `if (condition) break;`, then you also need to define different `if` statements, etc. This rapidly gets out of hand unless you have a tagged formalism like that used in ECMAScript.
2. Detecting the error in a post-parse scan will allow you to produce better error messages. Rather than just presenting the user with some kind of `syntax error` message (which might be "unexpected token 'break'"), you can actually provide a meaningful error message like "'break' statement cannot be used outside of a loop."

# Answer
> 0 votes
You could do this purely in syntax - you’d have a grammar with two non-terminals for “statement that can contain a break” and one for “statement that may not contain a break”. You duplicate the size of the grammar, making it a right pain.

When you parse a break statement you need semantics anyway to determine what exactly it breaks from, since you may have nested loops and switch statements. Detecting that it has nothing to break from is a tiny part of that, so semantically it’s quite simple. You will save yourself some headache by doing this check in your semantics.

Of course you will use the syntax to prevent things like “x = break + 1;”.

---
Tags: programming-languages, compilers, semantics, syntax
---


# Question
Title: Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$
I'm trying to show that for the following Towers of Hanoi general algorithm that $T\_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my proof.

```
generalTH(n_disks,k_stacks)
  if n<k:
    ### in 2n-1 moves reassemble ###
    return
  m = n-2
  generalTH(n-m,k)
  generalTH(m,k-1)
  generalTH(n-m,k)

```

To solve towers of Hanoi, I know it takes the following number of moves: $$ T\_k(n) = \begin{cases} 2^n-1, & k=3 \\ 2n-1, & n\<k \\ 2T\_k(n-m)+T\_{k-1}(m), & n \geq k \end{cases} $$ Going through it - how can I show that the boundary case of $k=3$ can be within $\Theta(n)$?

Since $m = n-2$ : When I expand the recursion it seems easy to show that the first half is in $n$ \- but I'm not sure how to show the boundary case will be in $n$? $$T\_k(n)=2T\_k(n-(n-2))+T\_{k-1}(n-2)=2T\_k(2)+2T\_{k-1}(n-2-(n-4))+T\_{k-2}(n-4)$$ $$...$$ $$T\_k(n)\approx\Theta(2\cdot\lfloor\frac{k}{2}\rfloor)+\Theta(\text{boundary case})$$

# Answer
If $n\lt k$, we have $T\_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$.

One of the recurrence relations is, $$\quad T\_k(n) =6+T\_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$ where $6$ comes from $2T\_k(2)$, since $T\_k(2)=3$.

Applying the recurrence relation above repeatedly, we have $$\begin{align} T\_k(n)&=6\cdot 1+T\_{k-1}(n-2\cdot1)\\ &=6\cdot 2+T\_{k-1}(n-2\cdot2)\\ &=\cdots\\ &=6\cdot (p-1)+T\_{k-(p-1)}(n-2\cdot (p-1))\\ &=6\cdot p+T\_{k-p}(n-2\cdot p)\\ (\text{let us apply } T\_k(n)=2n-1)\quad&=6\cdot p+2(n-2\cdot p)-1\\ \end{align}$$ if we can choose $p$ such that

* $n-2(p-1)\ge k-(p-1)\ge\dfrac{n-2(p-1)+3}2$,
which ensures all equalities except the last one hold, and
* $n-2p\<k-p$,
which ensures the last equality holds.

Solving $p$ for those inequalities, we find that $p= n-k+1$.

$$T\_k(n)=6\cdot p+2(n-2\cdot p)-1=4n-2k+1$$

---

So, we have $$T\_k(n) =\begin{cases} 2n-1, & n\<k \\ 4n-2k+1, & n \geq k \end{cases}$$ It is easy to check that $n\le T\_k(n)\<4n$, so $T\_k(n)=\Theta(n)$.

---

"How can I show that the boundary case of $k=3$ can be within $\Theta(n)$?"

What is the situation when $k=3$ under the assumption $k\ge\dfrac{n+3}2$? That means $n\le3$. So that situation is rather irrelevant since we are interested in the asymptotic behavior of $T\_k(n)$.
> 1 votes

---
Tags: algorithm-analysis, proof-techniques, towers-of-hanoi
---


# Question
Title: Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V
I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices *V*, and a set of vertices *X**V*.

Between these vertices are given a set of edges where:

* edge(*u*,*v*) with *u**V* \ *X* being weighted \> 0
* edge (*u*,*v*) where *u**X* being weighted = 0
* other edge combinations (i.e. *u*,*v**V* and *u*,*v**V* \ *X*) are allowed, but follow the same rules as above

At most **two** vertices ∈ X are allowed to be visited in the path.

How can this be modeled as a shortest path algorithm problem? I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.

Any help much appreciated!

# Answer
You never say what the goal is. I suspect that you want to find the shortest a path from a given vertex $s$ to a given vertex $t$ that passes through at most two vertices in $X$. In this case you can assume w.l.o.g., that $s,t \not\in X$. Moreover, you can assume that the input graph is directed. If this is not the case, then you can preliminarily replace each undirected edge $\\{u,v\\}$ with the two directed edges $(u,v)$ and $(v,u)$.

Let $G=(V,E)$ be the input graph and let $F = \\{ (u,v) \mid u \in X\\}$ be the set of outgoing edges from some vertex in $X$. Make a new graph $H$ containing three copies $G\_1, G\_2, G\_3$ of the graph $(V, E \setminus F)$. Then, augment the graph as follows:

* For each edge $(u,v) \in F$ add:
    + an edge (of weight $0$) between the copy of $u$ in $G\_1$ and the copy of $v$ in $G\_2$.
    + an edge (of weight $0$) between the copy of $u$ in $G\_2$ and the copy of $v$ in $G\_3$.
* Add a new vertex $t^\*$ and the three edges (of weight 0) between each copy of $t$ in $G\_1$, $G\_2$, and $G\_3$ and $t^\*$.

You can now find a shortest path $P$ between the copy of $s$ in $G\_1$ and $t^\*$. The list of vertices traversed by $P$ (except for the final vertex $t^\*$) will induce the sought shortest path on $G$.
> 1 votes

# Answer
> I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.

Actually, it does. Just create two copies instead of one, linking the top-layer to the middle-layer, and the middle-layer to the bottom, via the nodes in X.

This works because the "copy the graph" trick is simply a way of encoding state by using graph nodes. In your case, each node has 3 copies, and which copy you're in tells you how many nodes in X you've traversed.
> 1 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How are kernels (and operating systems in general) written in C?
I'm trying to understand how you set about writing an OS in something like C.

I've always used C to write applications - using commands like `malloc` and `fork` and so on to request things from the OS. If these methods don't exist when you're programming the OS itself (or perhaps the Kernel in particular), how do you write them?

If I can summarise what I'm stuck on:

* Am I right in thinking that `fork`, `malloc`, etc. are wrapper methods that call the Kernel?
* Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?
* When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?
* Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?
* How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

I can imagine this isn't a small question, so I'm more than happy for an answer that includes some further reading but if you'd be able to summarise the main points related to each question that would be super handy for me!

Thanks in advance!

# Answer
There's a lot to unpack here, but I'll try to keep it as Computer Science as I can.

**Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?**

Yes and no, respectively.

In a typical POSIX-like operating system, `fork` is a system call. This means that there is usually a very thin wrapper, often written in assembly language, which has three jobs:

* Translate between the C calling convention and the system call convention. This usually means transferring arguments between registers.
* Invoke the system call.
* Do any processing needed for the return value from the system call. Again, this is usually just a register transfer today.

Note that Windows does not support `fork`.

This is not true of `malloc`. Modern operating systems manage program memory in terms of *pages*; a program can only allocate or deallocate a whole number of pages. If finer-grained allocation is needed, then the user program needs to implement a data structure on top of this.

This is also how different programming languages can use different allocation models, such as garbage collection. Programming languages don't need to follow the same heap model as `malloc()`. Windows has support for logically separate heaps through heapapi.

Remember that disks and SSD storage don't have a concept of "files"; a disk is just presented as a big array of blocks (to a first approximation). Similarly, operating systems don't have a concept of "heap allocated objects"; address space is just a big array of pages.

**How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)**

What a programmer thinks of as "allocating memory", to an operating system, really means allocating *virtual* memory, so this is understood as a virtual memory operation. Specifically, "allocated memory" is known as "anonymous memory", which distinguishes it, say, memory-mapping a file (which, therefore, has a "name" and is not "anonymous").

Different operating systems provide different ways to achieve the same result.

**Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?**

The "typical POSIX-like operating system" that I mentioned above is how things work in Linux, MacOS, and so on. The C standard library for that platform provides system calls as if they were normal C functions.

Windows is a bit different. System calls are invoked through a system DLL called `kernel32.dll`. (Yes, even on 64-bit platforms!) In Linux, you need to call system calls to load dynamic shared objects (DSO being the generic term for what Windows calls a DLL), which would cause a bootstrapping problem if you needed to load a DSO to invoke a system call. In Windows, DLL loading is partly managed by the kernel, so `kernel32.dll` can be supplied to user programs without needing any system calls to set it up.

**When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?**

**Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?**

"Freestanding" means two things:

1. The entry point to the program need not be `main()`.
2. The C standard library need not be present.

That last one is probably the most important. You see, C compilers are allowed to assume that the C standard library is present, and generate calls to it even if there isn't an explicit function call. One common example is that copying large structures can be implemented with a call to `memcpy()`, as you can see for yourself.
> 4 votes

# Answer
Today, you can definitely write an OS in C because you have compilers readily available on some OSes. You just have to decide with what executable format you are going to go and then parse it from a bootloader like a UEFI bootloader which has to be written in C as well. Linux is compiled to an ELF executable which is then compressed. Linux follows the multiboot specification (https://www.gnu.org/software/grub/manual/multiboot/multiboot.html) which allows one bootloader (GRUB) to boot the Linux kernel by following the specification.

> Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

You are quite right. For example, when you write a C app on Linux, you are probably using gcc to compile your app. gcc comes with glibc which is the library implementation of the C standard on Linux. You can look at the source code of glibc (https://github.com/lattera/glibc) to look at the implementation.

For example, malloc is in malloc/malloc.c. Its definition is a one liner like `strong_alias (__libc_malloc, malloc)` (https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc). I didn't study the source code much but I think this means that a malloc call is a \__libc\_malloc call. The link I provided is good because it has the function definitions to the right that you can click on to go to the line.

\__libc\_malloc definition

```
void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

```

\__libc\_malloc calls \_int\_malloc which does the main work. It is very long so you can browse it on the link I provided. It is defined as:

```
/*
   ------------------------------ malloc ------------------------------
 */
static void *
_int_malloc (mstate av, size_t bytes)

```

I'm pretty sure that this is the malloc you are looking for. In \_int\_malloc there are these lines:

```
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

```

If there are no usable free chunks in already allocated memory, fallback to mmap to get more memory. sysmalloc is again very long but it calls mmap as a macro defined like:

```
#define MMAP(addr, size, prot, flags) \
 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)

```

> Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you write a C app on Linux, you include headers from glibc to use the standard functions like malloc, fork etc. When you compile your app, you either compile it statically or dynamically. When you compile it statically, you include all the kernel code in the executable like mmap's code. Basically, when mmap is called from your main function, the CPU jumps to the function which is mapped in virtual memory. Where it "stops" including the code, is when you jump to kernel code using `int 0x80` on older x86 32 bits processors. I don't know about the system call convention for x86-64 honestly. It is probably similar. When your code calls `int 0x80` on x86, it interrupts the CPU and it jumps to shared-by-all-processes kernel code. This kernel code cannot be included in your executable because it is interrupt code. So mmap is included in your executable up until the system call. The rest of the work is done in the interrupt handler and then returns to mmap which now has the new address of the allocated memory chunk. mmap then returns to the glibc caller which, like you said, is a wrapper around kernel code calls. When you link dynamically, it is the same except linking happens just before runtime.

> When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

You don't need to write the implementation of C in assembly. glibc is written completely in C. Most of the Linux kernel is also written in C. Some parts of the kernel code needs to be written in inline assembly. For example, the system calls need to be done with a `int 0x80` call that you can't make from pure C.

> Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

This is a lot of terminology and I don't get what you mean by freestanding and hosted here. A freestanding implementation means that you use only the base of C because you don't have access to library functions like you would in a development environment like Windows or Linux. For example, an OS needs to be written in static, freestanding C because you need all code to be included in the final executable and because you can't depend on a runtime which includes things like standard libraries, system calls and other stuff like that. Actually, freestanding means that you really use only the components of C that you know are going to be included in the final executable and which are going to be compiled to assembly which doesn't depend on a particular runtime.

> How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

C includes pointers which allow to do all that and more. In a freestanding environment (like when you develop an OS), you can just use absolute addresses and it just works because you don't have things like memory protection. You do have memory protection but you are the one in control of it. If you just type something like `int* pointer = (int*) 0x8000;`, you have a pointer of type int which points to 0x8000. If you type `*pointer = 0x34`, then at the address 0x8000 is now 0x00000034. That is because an int is 4 bytes. If you type `unsigned char* pointer = (unsigned char*) 0x8000`, and then `*pointer = 0x34`, at the address 0x8000 is now 0x34. That is because a char is one byte. You see that you can control memory pretty easily in C. You can put whatever values you want at the byte level. You can even work at the bit level using bitwise operators.

Today, most devices have memory mapped registers. By accessing memory using pointers, you can write commands to the registers of these devices and tell them to do stuff. If you ever need to access some IO ports or to do a system call like with `int 0x80` then you have inline assembly from C which allows to do it. Also, the BIOS builds ACPI tables in RAM in conventional position which allows the OS kernel to find the location of the different registers.

Hope this answers your questions.
> 3 votes

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


# Question
Title: Reducing infinite paths of a transition system to its set of sets of states
Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is at least one outgoing transitions $(s,s') \in T$.

Each path corresponds to a set of states, namely, the states visited along that path. Given a transition system $\langle S,T \rangle$ and an initial state $s\_0 \in S$, I would like an algorithm that outputs the list of all sets of states that can arise from all infinite paths in $\langle S,T \rangle$ that start at $s\_0$.

As a trivial example consider $S = \\{s\_0, s\_1, s\_2 \\}$, $T = \\{(s\_0,s\_1),(s\_0,s\_2),(s\_1,s\_1),(s\_2,s\_2)\\}$, with initial state $s\_0$; I would like the algorithm to output $\\{s\_0,s\_1\\}, \\{s\_0,s\_2\\}$.

Is there an algorithm for this problem? I believe this can be accomplished with strongly connected components, but I don't know what to search for in the literature.

# Answer
Since the set you want to output can be exponential in the size of the transition system, there is clearly no polynomial algorithm to enumerate it.

Thus, let's focus on an exponential time solution. To this end, it is actually quite easy to find a naive algorithm:

For every subset $Q\subseteq S$ (that contains $s\_0$), in order to check whether $Q$ should be outputted by the algorithm, look at the subgraph induced by $Q$, and check whether there is a path from $s\_0$ that goes through all the vertices in the induced subgraph.

One way to do the latter, is to indeed decompose the subgraph to its strongly connected components (SCCs), then look at the tree of SCCs, and make sure it's simply a directed path from $s\_0$. If it is not a path, then you cannot traverse the entire set $Q$, as you would need to select a branching in the tree from which you cannot go back.

Thus, the test of whether $Q$ should be outputted can be done in polynomial time.
> 2 votes

---
Tags: algorithms, graphs, transition-systems, path
---