# Question
Title: Can a public key be used to decrypt a message encrypted by the corresponding private key?
From what I have seen about usage of a pair of public and private keys, the public key is used for encrypting a message, and the private key is used for decrypting the encrypted message.

If a message is encrypted by the private key, can it be decrypted by the corresponding public key?

If yes, can you give some examples of when this case is used?

Thanks.

# Answer
Q: If you pedal backwards on a fish, does it go backwards?
A: ???

A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They don't have the right equipment.

With RSA, which is a popular public-key cryptosystem but not the only one, the private key and the public key have the same mathematical properties, so it is possible to use them interchangeably in the algorithms. (They don't have the same security properties, however — the public key is usually easily guessable from the private key.) You can take an RSA encryption algorithm and feed it a private key, or an RSA decryption algorithm and feed it a public key. However, the results are not meaningful according to standard algorithms.

This symmetry between public keys and private keys does not extend to most other public-key cryptosystems. In general, the public key isn't the right type of mathematical object to use for the decryption algorithm, and the private key isn't the right type of mathematical object to use for the encryption algorithm.

This being said, public-key cryptosystems are based on the concept of trapdoor functions. A one-way function is a function that is easy to compute, but whose inverse is hard to compute. A trapdoor function is like a one-way function, but there is a “magic” value that makes the inverse easy to compute.

If you have a trapdoor function, you can use it to make a public-key encryption algorithm: going forward (in the easy direction), the function encrypts; going backward (in the hard direction), the function decrypts. The magic value required to decrypt is the private key.

If you have a trapdoor function, you can also use it to make a *digital signature* algorithm: going backward (in the hard direction), the function *signs*; going forward (in the easy direction), the function *verifies* a signature. Once again, the magic value required to sign is the private key.

Trapdoor functions generally come in families; the data necessary to specify one particular element of the family is the public key.

Even though public-key encryption and digital signatures are based on the same concepts, they are not strictly identical. For example, the RSA trapdoor function is based on the difficulty of undoing a multiplication unless you already know one of the factors. There are two common families of public-key encryption schemes based on RSA, known as PKCS#1 v1.5 and OAEP. There are also two common families of digital signature schemes based on RSA, known as PKCS#1 v1.5 and PSS. The two “PKCS#1 v1.5” are of similar designs, but they are not identical. This answer by Thomas Pornin and this answer by Maarten Bodewes go into some details of the difference between signature/verification and decryption/encryption in the case of RSA.

Beware that some layman presentations of public-key cryptography masquerade digital signature and verification as decryption and encryption, for historical reasons: RSA was popularized first, and the core operation of RSA is symmetric. (The core operation of RSA, known as “textbook RSA”, is one of the steps in an RSA signature/verification/encryption/decryption algorithm, but it does not constitute in itself a signature, verification, encryption or decryption algorithm.) They are symmetric from the 10000-foot view, but they are not symmetric once you go into the details.

See also Reduction from signatures to encryption?, which explains that you can build an encryption scheme from a signature scheme, but only under certain conditions.
> 69 votes

# Answer
Yes, a message which has encrypted using private key can be decrypted using the public key.

In fact, this is implemented to verify the authenticity of the data. In the digital signature, a person encrypts the hash of the data with his private key. Anyone can decrypt the same with the available public key of the person and verify the authenticity of the data.
> 15 votes

# Answer
When the PKE scheme uses a trapdoor permutation as a black box, "encrypting" with the private key followed by "decrypting" with the public key will yield the original message.  For other PKE schemes, one can't necessarily even make sense of that.  (For example, trying to "encrypt" with the private key might be a type error.)

\[Encrypting a message "by the private key" followed by decryption "by the corresponding public key"\] is used when people *think* that case is for digital signatures and are not corrected in time.  See this answer and this question.
> 6 votes

# Answer
> Substitute plaintext data for the trunk and cryptographic keys for the physical keys from this analogy, and this is how public key cryptography works. Only the owner of the private key can encrypt data so that the public key decrypts it; meanwhile, anyone can encrypt data with the public key, but only the owner of the private key can decrypt it.

This is from cloudflare.
> 1 votes

# Answer
Think of the the public key in a asymmetric encryption as a lock instead of a key. Would the hacker who have a lock and a locked box with that lock, unlock the locked box? Of course no, and to unlock that box you need the lock key. Which was never sent in public, and only the sender has it.

However, the answer is **Yes** :D it's actually possible for a hacker to decrypt the message using only the public key (lock and a locked box). But that's extremely hard for any computer today. Because reverting that encrypted message using that public key is a very hard mathematical operation especially when that key is as large as 2048-bit number. The strength of the mathematical operation relies on the hardness of the prime factorization of a large number.

Here's a good video explaining how the RSA algorithm works https://www.youtube.com/watch?v=wXB-V\_Keiu8
> 0 votes

# Answer
The question is valid in terms of eMRTD where AA Public Key is used to de-crypt the Internal Authenticate response encrypted by the eMRTD Private Key. It is part of ICAO 9303 Standard.
> 0 votes

---
Tags: cryptography
---


# Question
Title: What are the differences between Earliest Deadline First (EDF) and Earliest Due Date (EDD)?
From my understanding, the EDF (Earliest Deadline First) rule is essentially an iterative "version" of the EDD (Earliest Due Date) rule, which allows for preemption. At every point in time, EDF looks at all the processes present and sorts them into the processes with the earliest deadlines first and the latest deadlines the last.

This means that if at time `t1` we only have a process `P1` with deadline `d1` running, and no other processes; then `P1` will run. But if at `t2` we have a new process `P2` with deadline `d2` (such that `d1 > d2`), then `P1` will be interrupted and `P2` will be executed. Once `P2` is finished, if only `P1` is present then it is executed otherwise the deadlines of `P1` and the next process are compared and the one with the earliest deadline is executed.

Is this the only difference or any there any more?

# Answer
Yes, that's right. In fact I think we can say that EDD is a special case of EDF, where all the processes have arrived at the same time.
> 2 votes

---
Tags: computer-architecture, scheduling, cpu, process-scheduling, threads
---


title: SICP: Pascal's triangle problem

text:
# Question
Title: SICP: Pascal's triangle problem
I was reading SICP and was solving a problem that asked to create a function in lisp for finding elements of Pascal's triangle. The way I went about it is to take input as the row number and then print each element of the row iteratively, whose value would be found recursively.

```
(define (pascDisp n)
        (define i 1)

        (define (pasc n i)
                (if (or (= i 1)
                        (= i n))
                    1
                    (+ (pasc (- n 1)
                             (- i 1))
                       (pasc (- n 1)
                             i))))

        (define (pascDispIter n i)
                (display (pasc n i))
                (display " ")

                (if (<= i n)
                    (pascDispIter n
                                  (+ i 1))))

        (pascDispIter n i))

(pascDisp 5)

```

This does print out all the elements however, it goes into an infinite loop. I can't seem to find any problem with the logic though. The interpreter shows that `(pasc (- n 1) i)` is being called infinitely. Can you explain why this is happening?

# Answer
Your code has an "off by one" mistake: in the $n$'th row, it prints $\binom{n}{1},\ldots,\binom{n}{n+1}$ (the condition `i <= n` should be corrected to `i < n`).

This highlights another problem with your code: it implicitly assumes that $1 \leq i \leq n$, which is not necessarily correct (and also has a wrong base case: it should be $\binom{n}{0} = 1$; indeed, $\binom{n}{1} = n$). Instead, you should first check whether $i$ is within bounds, and if not, output zero.

(This will not work with negative binomial coefficients, but you're probably not interested in those.)
> 2 votes

---
Tags: lisp
---


# Question
Title: Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?
I do have some intuition(although I would like to be corrected) regarding why $NL!=Dtime(n^{log n})$ as for some $L \in Dtime(n^{log n})$ it might be required for the TM deciding it to read inputs of size $O(n^{log n})$ which isn't possible in logarithmic space constraints. Having an oracle access surely saves a lot of time, but how does it help with space constraints? We're still bounded by logarithmic space. Any help would be much appreciated!! Thanks!

# Answer
First, see that we can prove two things as follows:

* The Time hierarchy theorem relativizes. That is, one can prove that even with any oracle $O$, the following holds when $f(n) \log n = o(g(n))$: $$ DTime (f(n))^O \subsetneq DTime(g(n))^O $$
* The proof that $$ NL \subseteq P $$ also relativizes. So: $$ NL^O \subseteq P^O $$ for any oracle $O$. The reason is that the TM for any language in $NL$, with oracle $O$, can be converted to a polynomial time, by the similar construction used for proof without oracle, and oracle query is replaced as it is.

Using these two one can just conclude that $NL^O \subsetneq DTime(n\log n)^O$
> 1 votes

# Answer
The inclusion $\mathsf{NL\subseteq P}$ relativizes (remains true relatively to any oracle), from here you can apply the time hierarchy theorem.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Are monads a unification of a number of computer science concepts?
The following commentator writes:

> Monads are a unification of a bunch of computer stuff, including sequencing, IO, non-determinism, state, concurrency and exceptions. When I say "unification", I mean it in the sense that Newton's theory of gravity unified the motion of the planets with a falling apple (previously they were considered separate phenomena), or how Maxwell's equations unified electricity and magnetism. Once you grok monads you realise that all those different things I listed are just special cases of one overarching theory.

My question is: **Are monads a *unification* of a number of computer science concepts?**

# Answer
> 2 votes
It depends on your interpretation, I guess.

Is an `Iterator` interface a unification of arrays, lists, sets, strings, and input streams?

Because that is essentially what a monad is: an interface. It is just at a higher level of abstraction than the typical interfaces programmers are used to.

Monads are an abstraction that essentially represents "computation plus some structure". And it turns out that, indeed, many concepts in computer science can be molded into the form of a monad. The `IO` monad represents side-effecting computations, the `State` monad represents computations with mutable state, the `STM` monad represents concurrent computations with transactional state, the `Error` monad represents computations that could fail, the `Maybe` monad represents computations that may or may not return a useful result, the `Continuation` monad represents control flow, the `List` monad represents … and so on and so forth.

For example, in .NET, monads are used to abstract over database queries, collections operations, reactive programming, and many more. And of course in Haskell, you can't really write a useful program without at least the `IO` monad.

What this means is that monads allow you to interact with non-determinism, concurrency, side-effects, errors, etc. through the same interface. Which of course also means that you can write libraries, helpers, programs, and abstractions that only depend on the monad interface and thus automatically work with all of those.

Whether or not you consider that "unification" is probably more a matter of opinion. Like I said: if you say that monads unify all these things, then you also need to say that iterators unify arrays, lists, etc.

---
Tags: category-theory, monad
---


# Question
Title: How C++ and alike maps are actually stored in memory?
I admit I didn't know much before what a *Map* is living with just the terminology *Hash Tables*, even when I first Google it I found this https://www.mathworks.com/help/matlab/matlab\_prog/overview-of-the-map-data-structure.html#:~:text=A%20Map%20is%20a%20type,indexing%20into%20its%20individual%20elements.&text=These%20keys%2C%20along%20with%20the,key%20and%20its%20corresponding%20value. and thought it's just specific to *MATLAB* syntax

Then I found https://www.quora.com/What-is-a-map-data-structure-How-does-it-store-data and knew it is a terminology for probably a hash table (they say or a binary search tree, I'm not sure how as an implementation)

& There is a library in C++ for them https://www.udacity.com/blog/2020/03/c-maps-explained.html

https://www.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/

Now my question how they are actually stored in memory to achieve such a fast indexing on the key as a hash value???

I mean if it's just stored as a 1D array of struct (N\* sum of fields size), then it will not function as a hash table in access time. It must add an extra book keeping space( trading space with time) in addition to the user data to add the hash table fast access time

If possible, give me a fn of N, no of elements, say for

type myStruct struct {.
data myData.
myPointer \*myStruct }

map\[uint64\] \*myStruct

I mean it's kind of "not best choice" to use a map to help in traversing a tree, this way I'm allocating a space for 2 trees, and I'm not sure the running time requirements will follow my tree kind that I worked so hard to think of, or the kind of tree the C++ implementation used???

# Answer
> 2 votes
In C++, `std::map` is an *ordered* map. It requires that keys are comparable with a less-than operator (C++ calls this strict weak ordering), and can traverse all entries in the map in order, in linear time. The requirements were written in such a way that they essentially dictate that the implementation uses some kind of ordered search tree.

All of the implementations that I am aware of use red-black trees, although there's no reason why it needs to be that balancing scheme specifically.

Hash tables do not preserve key order, but they do support constant-time access. For that reason, C++ also supported *unordered* maps, imaginatively called `std::unordered_map`. Keys in an unordered map no not need to be comparable with a less-than operator; an equality operator and a hash function are (unsurprisingly) sufficient.

Once again, the C++ standard is written in such a way that it essentially dictates a hash table with buckets and some kind of separate chaining, but does not dictate any details beyond that. (EDIT: Thanks to @rici for correcting an earlier version on this point.)

# Answer
> -1 votes
I found in this reference

https://www.tutorialspoint.com/cpp\_standard\_library/map.htm

That *maps* are implemented as Binary Search Trees, *unordered maps* as hash tables

To clarify things, I am not trying to implement my own map like this site https://codeforces.com/blog/entry/70947

I was asking how C++ do it.

Anyways, whether it is a Binary Search Tree or a Red Black Tree it is *2N* more pointers (for left&right of the tree) + the pointer already in the struct = *3N* pointers.

(It's also worth clarifying that *Red Black Trees* have a ≥ right subtree condition, they just handle insertion & deletion in a different way hoping to achieve a more balanced tree: https://en.m.wikipedia.org/wiki/Red%E2%80%93black\_tree, https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/)

I was asking for a specific problem where the original designer worked so hard to find & design & prove a certain tree strucutre is better to use than RBT or BST, then come those developers implementing the theoritical idea by adding a map to the original design tree; that's even worse than before we get back to all the problems that motivated the original design (of why not using BST or RBT and design this), + doubling the space of older methods the original design were trying to optimize.

(because developers have already implemented another tree structure in their code; this way the program when running will allocate a space in memory for *their coded tree* and for *the C++ map tree*.

Anyways, this is their problem & has nothing to do with the group. I hope this question has informed/reminded of the fact that a *map* is implemented as a tree, *unordered map* as a hash table, and rang a bell to software developers to check how language library data structures are really implemented in memory to be aware of the consequences when using them.

Thank you all

---
Tags: data-structures, memory-management, c
---


# Question
Title: If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?
I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$.

Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true?

I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, then $f(n) = O(h(n))$.

I can state $h(n) = \Omega(O(h(n)))$ but I don't know what to do from here. Any pointers?

# Answer
For big-$O$ holds property, sometimes called transitivity of big-$O$: $$f\in O(g) \land g \in O(h) \Rightarrow f \in O(h)$$ last of course means, also, $h \in \Omega(f)$: because if we have $f(n)\leqslant C \cdot h(n)$, then this is same with $h(n) \geqslant \frac{1}{C}\cdot f(n)$.

Proof of transitivity can be based on simple note, the $f\in O(g) \Rightarrow O(f) \subset O(g)$ and then used transitivity of subsets.
> 2 votes

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


# Question
Title: Halting problem. Decider “recognising itself” in the input?
This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the halting problem? I want to state clearly I am aware the following argument surely contains errors and is not valid, I wouldn’t like this question to be perceived as pretentious or arrogant.

I’ll call $D$ the decider for the halting problem, and $H$ the pathological program containing $D$ as a subroutine. $D$ is an algorithm we assume can always determine whether the Turing machine described in its input will halt.

I have been thinking about the possibility for a program to recognise instances of itself inside its input. I think that if $H$ has $D$ as a subroutine, when $D$ is running, $D$ could terminate in a halting state, making the whole of $H$ terminate without exiting the subroutine. The decider (the subroutine $D$) has to read the description of some machine $M$ on the tape, then it has to print a symbol, let’s say adjacently to the left extreme of the description (as in Turing 1936): a $1$ if $M$ halts and a $0$ if not. After that, $D$ has to reach some halting state $q(h)$. We can imagine that if $D$ is a subroutine, $H$ has in its description some instructions of the kind “when in state $q(h)$ do such and such and move to state $q(x)$”. The pathological machine $H$ has to have some halting state, say we call it $q(s)$, that stops the entire program: it has to be able to either stop or loop by assumption.

One could argue that for any of the state-symbol pair the machine ends in to go into an halting state, there is a pathological program $H$ that starts from that exact same state-symbol pair and can lead the machine either to a loop or to a definitive halt. But I thought maybe this is not the case if $D$ has as input the source code (the description) of $H$: in this case the final state-symbol pair in which $D$ terminates can be chosen ad hoc as a function of the description given as input. And if $H$ has the possibility of either halting or looping, this means it has to have in its description some state that no instruction takes as starting state to make the halting scenario possible. $D$ can be built so that, if needed, it directly terminates in such necessary state without passing through the rest of $H$’s description. Whatever hardware (namely, possible states and symbols) we program $D$ and $H$ on, we can build $D$ so that, depending on the input, it can terminate in any state it doesn’t use.

Imagine $D$ composed by $A$ and $B$, where $B$ just stores the description of $A$. $A$ could use its description to recognise itself in the description of $H$ given as input in the pathological case. Then $A$ could do something like asking itself “if this was the program in which I am embedded, what actions would make my prediction true?”. If it gets $H$ as description, $A$ is going to recognise that the instance of itself in the simulation always makes the wrong prediction if it allows $H$ to keep running at the end of the subroutine $D$. So, $D$ outputs $1$ (halting), then looks at what is the necessary halting state where the final part of $H$ is not triggered and terminates there to completely stop $H$.

My point is: if $D$ recognises itself in the input, it can also recognise that the simulated $D$ is going to get as input the same input it got, and can "conclude": "in whatever state I alt, the simulated $D$ is going to do the same". Then it predicts "halt", looks at the halting state that globally stops the simulated $H$ and halts in that state.

In what ways do you think this doesn’t make sense?

As asked, some (low quality) pseudocode to try and explain more decently my idea:

```
D(input):
    is_self_and_gets_same_input = D.recognize_self(input)
    if is_self_and_gets_same_input == true:
        prediction, final_state = D.help_self(input)
        return prediction, final_state
    else:
        prediction = analyse_as_usual(input)
        final_state = default_final_state
        return prediction, final_state

def help_self(input):
    for state in D.possible_halting_states:  #looks at scenarios
        for prediction in “halts”, “loops”:
            outcome = D.check_loop(input, prediction, state)
            if outcome == prediction:
                return prediction, state

```

Note: I don’t think it makes too much sense for $D$ to “return” a state. With that I am thinking about the fact that you need the Turing machine to be in some particular state $x$ when the subroutine $D$ ends. $x$ has to be a state for which the rest of $H$ has some instructions to move from there, and if $x$ = $z$, with $z$ being the halting state of $H$, $H$ could not move from there, therefore it could not look at the prediction “halt” that the subroutine $D$ produced, and could not trigger the infinite loop.

Note #2: $D$ doesn’t have to simulate the instance of itself, it can just look at it as a black box and analyse how the rest of $H$ makes use of the information potentially produced by $D$ in different scenarios.

# Answer
> I think that if $H$ has $D$ as a subroutine, when $D$ is running, $D$ could terminate in a halting state, making the whole of $H$ terminate without exiting the subroutine.

I think this is the core of your argument - stated again here:

> $D$ can be built so that, if needed, it directly terminates in such necessary state without passing through the rest of $H$’s description

However, this is not true.

Think about what the sentence "$H$ has $D$ as a subroutine" means. It means that the person who created $H$ looked at $D$, and copy-pasted it into $H$, and then adjusted their copy of $D$ to "wire it up" into $H$ \- such as by renaming states or symbols to avoid conflicts, and importantly for this question, *by making the final states non-final*.

The author of $H$ didn't *want* $D$ to lead directly to random halting states, so they didn't make it do that. The states that used to be the final states of $D$ now lead to whichever other states the author of $H$ wanted to happen next after $D$ finishes.

Part of $D$'s algorithm can include looking for an algorithm isomorphic to $D$, but there is no way for the algorithm $D$ to enforce that the machine halts immediately after the execution of $D$. As long as the "core" of the algorithm remains the same, the author of $H$ will just remove the silly "and then please halt" instruction.

---

Remember this algorithm is supposed to compute a mathematical function, and mathematics has no concept of "the answer is 1 but you must abort the rest of the calculation and the final answer is 1." Forcing an abort is like defining this function:

$$ f(x) = x+2 \textrm{ but then abort the calculation and the final answer is }x+2 $$ so that $$ f(2) = 4 \\ f(2)+2 = 4 \textrm{ because we aborted the +2} \\ f(2)^{500} = 4 \textrm{ because we aborted the }^{500} \\ $$ which is just silly.
> 3 votes

---
Tags: turing-machines, computability, automata, undecidability, halting-problem
---


# Question
Title: Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?
Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V is the number of vertices.

When E\>\>V, such as for a complete graph the time complexity would be V^2 and (V^2)logV. This would mean that the implementation using min heap should be slower.

However I tested both implementations and found that the runtime for min heap is faster. Why is this so?

Here is my implementation:

1. adjacency matrix and unsorted list

```
def dijkstraUnsortedArr(graph, start):
    distances = [math.inf for v in range(len(graph))]
    visited = [False for v in range(len(graph))]
    predecessors = [v for v in range(len(graph))]
    distances[start] = 0

    while True:
        shortest_distance = math.inf
        shortest_vertex = -1
        for v in range(len(graph)):
            if distances[v] < shortest_distance and not visited[v]:
                shortest_distance = distances[v]
                shortest_vertex = v

        if shortest_vertex == -1:
            return [distances, predecessors]

        for v in range(len(graph)):
            edgeweight = graph[shortest_vertex][v]
            if edgeweight != 0 and not visited[v]:
                pathdist = distances[shortest_vertex] + edgeweight
                if pathdist < distances[v]:
                    distances[v] = pathdist
                    predecessors[v] = shortest_vertex

        visited[shortest_vertex] = True

```
2. adjacency list and min heap

```
def dijkstraMinHeap(graph, start):
    distances = [math.inf for v in range(len(graph))]
    visited = [False for v in range(len(graph))]
    predecessors = [v for v in range(len(graph))]
    heap = Heap()

    for v in range(len(graph)):
        heap.array.append([v, distances[v]])
        heap.pos.append(v)

    distances[start] = 0
    heap.decreaseKey(start, distances[start])
    heap.size = len(graph)

    while heap.isEmpty() == False:
        min_node = heap.extractMin()
        min_vertex = min_node[0]

        for v, d in graph[min_vertex]:
            if not visited[v]:
                if (distances[min_vertex] + d) < distances[v]:
                    distances[v] = distances[min_vertex] + d
                    predecessors[v] = min_vertex
                    heap.decreaseKey(v, distances[v])
        visited[min_vertex] = True

    return [distances, predecessors]

class Heap():

    def __init__(self):
        self.array = []
        self.size = 0
        self.pos = []

    def swapNode(self, u, v):
        temp = self.array[v]
        self.array[v] = self.array[u]
        self.array[u] = temp

    def minHeapify(self, index):
        smallest = index
        left = 2*index + 1
        right = 2*index + 2
        if left < self.size and self.array[left][1] < self.array[smallest][1]:
            smallest = left
        if right < self.size and self.array[right][1] < self.array[smallest][1]:
            smallest = right
        if smallest != index:
            self.pos[self.array[smallest][0]] = index
            self.pos[self.array[index][0]] = smallest
            self.swapNode(smallest, index)
            self.minHeapify(smallest)

    def extractMin(self):
        if self.isEmpty() == True:
            return
        root = self.array[0]
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = self.size - 1
        self.size -= 1
        self.minHeapify(0)
        return root

    def isEmpty(self):
        return True if self.size == 0 else False

    def decreaseKey(self, v, dist):
        i = self.pos[v]
        self.array[i][1] = dist
        while i > 0 and self.array[i][1] < self.array[(i - 1) // 2][1]:
            self.pos[self.array[i][0]] = (i-1)//2
            self.pos[self.array[(i-1)//2][0]] = i
            self.swapNode(i, (i - 1)//2 )
            i = (i - 1) // 2;

    def isInMinHeap(self, v):
        if self.pos[v] < self.size:
            return True
        return False

```

Here's the graph of the runtime against the number of vertices v:

# Answer
> 2 votes
Here is a worst-case example of a complete graph where the heap.decreaseKey() operation executes on every edge:

Let the vertices be $V = \\{1,2,\dotsc,n\\}$. The edge set $E$ is such that for every vertex $i$ and $j$ such that $i\<j$, there is an edge of *unit* weight if $j = i+1$; and there is an edge of weight $2(n-i)$ if $j \> i+1$.

Run the heap-based Dijkstra's algorithm on this graph with source vertex $1$. It will decrease the distance of the vertex $j$ every time it traverses the edge $(i,j)$. Moreover, it will take $\Theta(\log |V|)$ time for each call to heap.decreaseKey() operation as per the aggregate analysis. Therefore, the time complexity will be $\Theta(|V|+|E|) \log |V|$. Compare its performance with unsorted array based approach. You will see the difference.

Note that here, the shortest path tree is $1$ -\> $2$ -\> $3$ -\> $\dotsc$ -\> $n$.

# Answer
> 6 votes
It depends on the input graph also. Perhaps, heap.decreaseKey() operation is not happening as frequently as it should. For example, consider a complete graph: $G = (V,E)$ such that all its edge weights are $1$.

In this case, the heap implementation will work faster since `distance[v]` for every vertex will be set to $1$ in the first iteration. The heap.decreaseKey() operation will not happen more than once on any vertex. Therefore, the complexity of the heap based approach here is $O(|E| + |V| \log |V|)$.

On the other hand, in the case of unsorted list approach, you will be computing the shortest distance $|V|$ times and computing it every time takes $\Theta(|V|)$ time. Therefore, in such a graph the time complexity of the unsorted list approach is $O(|E| + |V|^2)$.

You should check with your input graph. Try with random weights on the edges and random source vertex, then you will surely see that *unsorted array* approach will be better than the *heap* approach in the case of complete graphs.

# Answer
> 0 votes
In short: Your test sample is too small or unvaried.

The $O$ notation allows for arbitrary multiplicative and additive constants everywhere, and for edge cases in the input data (i.e., a list being sorted vs. unsorted vs. sorted backwards etc. could introduce very unexpected results; and it does not need to be obvious either).

For things like this I would design some test program which runs for a long time (minutes at least), is pretty random, and varies the input data meaningfully. This may or may not be hard to achieve; sometimes it's best to grab your data from "out of the system" to avoid your test case generator algorithm to somehow mesh with the algorithm under test and thus *always* generating "special" data.

Finally; if you are not designing your algorithm in thin air - i.e., if it's not library code but some application solving a real problem - then by all means test with a large sample size of your *actual* domain data. That way, you can actually exploit those edge cases in the complexities and the algorithm. For example, a Dijkstra-style algorithm pathfinding in OpenStreetMap real world data might just need different optimization than, say, a similar algorithm finding paths for a game character on a board of square or hexagonal fields...

---
Tags: runtime-analysis, shortest-path, dijkstras-algorithm
---


# Question
Title: Reduction from SAT to SAT with exactly k true variables
Let $L$ be defined as follows:

$\small L = \\{(\phi, k) \mid \phi \in SAT \mbox{ and there is a satisfying assignment for $\phi$ having exactly $k$ true variables} \\}$

I am struggling to show that $SAT\leq\_{p} L$, I can't figure what $k$ should be and how to reconstruct $\phi$.

# Answer
> 2 votes
Let $\phi'$ be a SAT formula with $n$ variables.

Consider the pair $(\phi, k)$ where

* $\phi$ is a formula with $2n$ variables that is obtained from $\phi'$ by adding $n$ new variables $x\_1, \dots, x\_n$ (if you want each new variable $x\_i$ to appear in at least one clause you can add the trivial clause $(x\_i \vee \overline{x}\_i)$).
* $k=n$.

If $\phi$ is satisfiable then any satisfying truth assignment for $\phi$ restricted to the variables in $\phi'$ is also a satisfying truth assignment for $\phi'$.

If $\phi'$ is satifiable, consider any satisfying truth assignment $\tau'$ and let $n'$ be the number of true variables in $\tau'$. You can obtain a satisfying truth assignment for $\phi$ by setting all variables of $\phi'$ according to $\tau'$ and any choice of exactly $n-n'$ variables from $x\_1, \dots, x\_n$ to true. Notice that this is always possible since $0 \le n-n' \le n$.

---
Tags: np, satisfiability
---


# Question
Title: How does the Go language implements maps?
To what extent is the *MAP* data type implementation language dependant???

If we know that C++ implements *maps* as *Red Black Trees*, *unordered maps* as *hash tables*, How C++ and alike maps are actually stored in memory? what about other languages?

Go as an example?

# Answer
The Go language implements *MAPS* as *hash tables* using *8 buckets* https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics

*The bucket* represents 3 bits mask of the key value, and each bucket points to a space of size 8; the numbers are doubled with the increase of size (always power of 2)

The details of the bucket struct is as follows  Where the *\_type* is:

The designers describe their Go map as a compromise between C++ unordered maps and JAVA hashmap

*Unlike Java, you can use scalar values like characters and integers without the overhead of boxing. Unlike C++, instead of N runtime.hashmap implementations in the final binary, there are only N runtime.maptype values, a substantial saving in program space and compile time*

I found another helpful, and newer, reference too https://www.fatalerrors.org/a/a-comprehensive-analysis-of-golang-s-map-design.html
> 1 votes

---
Tags: programming-languages, hash-tables, dictionaries
---


# Question
Title: What is the Big-O Time Complexity of this code?
I was wondering if someone could please explain what the time complexity is for the code below.

I think it would be $O(n)$ because the algorithm will take as much time to execute as there are elements in $n$.

```
sample_list = [0, 1, 2, 3, 4, 5, 5, 6]
check_list = []
for i in sample_list:
    if i not in check_list:
        check_list.append(i)
    else:
        print(i,end='')

```

# Answer
The code takes $O(n^2)$. It is tricky to see that, since its very easy to miss the fact that `if i not in sample_list` takes another $O(n)$ time - just by itself.

Here is the breakdown of the complexity:

```
check_list = [] # O(1)
for i in sample_list # repeats n times
    if i not in check_list: # takes an O(n) time to do the check
        check_list.append(i) # takes constant time
    else:
        print(i) # again, constant time

```

Overall, it will take $O(n)$ per call to `if i not in check_list`, which will happen exactly $n$ times - and hence the total complexity is $n\cdot O(n)=O(n^2)$
> 1 votes

---
Tags: time-complexity, big-o-notation, python
---


# Question
Title: Why we need topological ordering for finding shortest paths
This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering.

Suppose we have a DAG (directed acyclic graph). Regarding the problem of finding shortest paths, Dijkstra's and Bellman-Ford algorithms are very popular. While both work with weighted directed graph, Bellman-Ford algorithm can work with negative edges. Dijkstra takes $O(E\log{E})$ while Bellman-Ford algorithm takes $O(EV)$ to execute, where $E$ is the number of edges and $V$ is the number of vertices in graph $G$.

Now here comes my issue, topological ordering works by just numbering the order by which we will visit the vertices of a graph and it works with negative edges as well, so this is a pro over Dijkstra. Because of topological ordering, we speed up shortest path finding to just linear time to $O(E+V)$.

**Problem**: Could you please simply explain the logic behind introducing topological sorting and how it helps cutting down complexity to just $O(E+V)$?

# Answer
> 1 votes
The shortest path between vertices $A$ and $Z$ (where $A\ne Z$) is the minimum over all edges $A\to B\_i$ of the weight of that edge plus the shortest path from $B\_i$ to $Z$.

For general graphs, it isn't obvious how to optimize that, because some paths from $B\_i$ to $Z$ may pass through $A$.

In a dag, that can't happen, and so there is an easy algorithm: compute and cache the shortest path from each vertex to $Z$ the first time you encounter the vertex, and look up the cached value if you reach the same vertex again. If you use a data structure with $O(1)$ insertion and lookup, such as a hash table, or a simple array if the nodes are identified by consecutive integers, then this runs in $O(E+V)$ time, because you do constant work for each first encounter of a vertex, constant work for each edge, and constant work for each subsequent encounter of a vertex, and there are fewer than $E$ subsequent encounters in total.

You don't need to topologically sort the nodes for that algorithm to work in $O(E+V)$ time. If you happen to know the topological order, then you can use it in a dynamic-programming version of the algorithm, which has the same asymptotic run time but may have smaller constant factors. But it isn't topological sorting that enables a linear-time algorithm; it's the fact that you know the graph is a dag.

---
Tags: algorithms, graphs
---


title: Input size in graph algorithms

text:
# Question
Title: Input size in graph algorithms
I know from the book by Neapolitan that for any algorithm input size is defined as the number of bits to encode the input. In graph algorithms, the input size is defined as $|V(G)| + |E(G)|$ for the input graph $G$. On the other hand, we save graphs in computers by their either adjacency lists or adjacency matrices which are of size $2|E(G)|$ and $|V(G)|^{2}$. So how is the input size $|V(G)| + |E(G)|$?

# Answer
The size of adjacency list representation is $\Theta(|E(G)| + |V(G)|)$, and not $\Theta(|E(G)|)$. For example, consider a graph with $n$ vertices and $0$ edges. The adjacency list corresponding to each vertex is empty. But storing the null pointer requires constant space for each vertex. Therefore, the size of the adjacency lists is $|V(G)|$ here.
> 2 votes

---
Tags: graphs
---


# Question
Title: Comparing different versions of Steiner Connected Component Subgraph problem
**Problem 1**
Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected component and the number of edges in $H$ is minimized. Here $V(H)$ stands for the set of vertices of $H$.

**Problem 2**
Everything remains the same, but this time we want to minimize the number of vertices in $H$.

Let $H$ and $H^{'}$ be optimal solutions to problem $1$ and $2$ respectively, for a given $G$. Let the number of edges in $H$ and $H^{'}$ be $e$ and $e^{'}$ respectively. I am trying to find an example of a graph $G$, such that $e\<e^{'}$ and $|V(H)| \> |V(H^{'})|$. I am unable to do so, the example I came up with has $e=e^{'}$ (and $|V(H)| \> |V(H^{'})|$). But I wanted to see a case of strict inequality.

In the example above the red vertices are the terminals. And $e=e^{'}=6$, where as $|V(H^{'})|=4$ and $V(H)=6$ (to be precise $H^{'}$ is also an optimal solution for problem $1$ in this example).

# Answer
In the figure, the bottom four vertices of the graph are red-colored vertices.

$H$ has $5$ edges and $5$ vertices.

$H'$ has $6$ edges and $4$ vertices.
> 2 votes

---
Tags: algorithms, graphs, graph-traversal
---


title: Space complexity of Bubble sort

text:
# Question
Title: Space complexity of Bubble sort
I have the following implementation of Bubble sort where it calls a helper method named `swap`.

```
    public static int[] bubbleSort(int[] array) {
        boolean didSwap = true;
        int j;
        int unsortedUntilIndex = array.length - 1;

        // i goes from 0 to array.length - 2
        // j goes from 1 to array.length - 1
        while (didSwap) {
            didSwap = false;
            // for arrays of size 0 or 1 this for loop will never execute
            for (int i = 0; i < unsortedUntilIndex; i++) {
                j = i + 1;
                if (array[i] > array[j]) {
                    swap(i, j, array);
                    didSwap = true;
                }
            }
            unsortedUntilIndex -= 1; // shortens iterations as numbers at highest indices settle into place with each iteration
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

```

It seems to me that by simply removing the helper method and including its code inline in the main method, I can reduce the space complexity from *O(N)* to *O(1)* since I'd no longer be adding method calls onto the call stack. Am I interpreting this correctly?

# Answer
> 2 votes
The function `swap` is not recursive so the depth of the call stack is always constant. While it is true that the space complexity of your algorithm is $O(n)$, it is also true that it is $O(1)$ (if we don't count the size needed for the input array `array`).

Inlining the function `swap` makes no difference as far as the asymptotic space complexity is considered.

---
Tags: time-complexity, runtime-analysis, space-complexity
---


# Question
Title: Deadlocks: Why if 2 threads are waiting for a lock from each other results in a deadlock?
I am confused as to why 2 threads waiting for a lock from each other will result in a deadlock. Let's say I have a Thread 1 that needs to execute contents in Lock 1 and then Lock 2 and a Thread 2 that needs to execute contents in Lock 2 and then Lock 1. Why does this situation result in a deadlock?

Once Thread 1 is done with Lock 1, it unlocks Lock 1, allowing Thread 2 to execute Lock 1. Once Thread 2 is done with Lock 2, it unlocks Lock 2, allowing Thread 1 to execute Lock 2. Where is the infinite stalling (deadlock)?

# Answer
The situation you are describing is not a deadlock.

A deadlock would be more like this:

* Both Thread A and Thread B require both Lock 1 and Lock 2.
* Thread A first acquires Lock 1, then Lock 2.
* Thread B first acquires Lock 2, then Lock 1.

Then you can get the following interleaving:

1. Thread A acquires Lock 1.
2. Thread B acquires Lock 2.

Now, Thread A can only progress after Thread B releases Lock 2. But in order to progress, Thread B needs Lock 1, which is currently held by Thread A, which can only progress using Lock 2, which is currently held by Thread B, which can only progress using Lock 1, which is currently held by Thread A, which can only progress using Lock 2, which is currently held by Thread B, which …

These are the *necessary conditions* for a deadlock to occur:

> 1. *Mutual exclusion*: At least two resources must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.
> 2. *Hold and wait* or *resource holding*: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
> 3. *No preemption*: a resource can be released only voluntarily by the process holding it.
> 4. *Circular wait*: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, $P = {P\_1, P\_2, …, P\_N}$, such that $P\_1$ is waiting for a resource held by $P\_2$, $P\_2$ is waiting for a resource held by $P\_3$ and so on until $P\_N$ is waiting for a resource held by $P\_1$.

In your example, you are missing condition #2 (your threads are not holding a lock and requesting another, but rather holding a lock, releasing it, and then requesting another) and consequently #4 (because of the fact that the threads release the locks before acquiring the next one, there is no dependency at all, let alone a circular one), so this is not a deadlock.

Or, to put it more simply

> I am confused as to why 2 threads waiting for a lock from each other will result in a deadlock.

In your example, they *aren't* waiting for a lock from each other. At any given point in time, Thread 1 *may* be waiting for Thread 2 to release Lock 1, and at any given point in time, Thread 1 *may* be waiting for Thread 2 to release Lock 2, and at any given point in time, Thread 2 *may* be waiting for Thread 1 to release Lock 1, and at any given point in time, Thread 2 *may* be waiting for Thread 1 to release Lock 2, but at *no point in time* is Thread 1 waiting for Thread 2 to release Lock 1 *and* Thread 2 waiting for Thread 1 to release Lock 1, nor is at any point in time Thread 1 waiting for Thread 2 to release Lock 2 *and* Thread 2 waiting for Thread 1 to release Lock 2.

So, in your example, it is simply never the case that there are "2 threads waiting for a lock from each other", there are only cases where a thread is waiting for a lock from another thread. In other words: your counterexample isn't a counterexample.
> 3 votes

---
Tags: operating-systems, concurrency, threads, deadlocks
---


# Question
Title: The number of ways of insertion in binary search tree
The number of ways in which the numbers $1,2,3,4,5,6,7$ can be inserted in an empty binary search tree, such that the resulting tree has height 5, is \_________.

Note: The height of a tree with a single node is 0.

What I have tried: Since It has height=5, we have 4 options for root $1,2,6,or$ $7$. One element will be alone either on the left side or right side. Now we have 5 elements and we have to make a height of 4 which can be done in 2^4 ways.

So total = $2^2 \times 2^4 = 2^6$

# Answer
Let $T(n)$ denote the number of ways in which $n$ distinct numbers can form a binary tree of height $n-2$.

Let $P(n)$ denote the number of ways in which $n$ distinct numbers can form a binary tree of height $n-1$.

Then, $T(n) = 2 \cdot T(n-1) + 2 \cdot P(n-2)$

The first two $T(n-1)$ terms are due to choosing the smallest and the largest elements as roots. The second two $P(n-2)$ terms are due to choosing the second-smallest and second-largest elements as roots.

Also, $P(n) = 2 \cdot P(n-1)$. Here, the two $P(n-1)$ terms are due to choosing the smallest and the largest elements as roots.

Therefore, $P(n) = 2^{n-1}$ since $P(1) = 1$.

Now, compute the values of $T(n)$ for different values of $n$.

For $n = 3$, $T(3) = 1$ (base case)

For $n = 4$, $T(4) = 2 + 4 = 6$

For $n = 5$, $T(5) = 12 + 8 = 20$

For $n = 6$, $T(6) = 40 + 16 = 56$

For $n = 7$, $T(7) = 112 + 32 =144$

The general formula for $T(n)$ is $2^{n-3} + 2^{n-2} \cdot (n-3)$
> 2 votes

# Answer
The language of the question is a not quite clear to me. The question is open to two possible interpretations.

---

**Interpretation 1:**

***Problem: For a given $n$ we need to find the number of permutations of $\langle 1,2,3,..,n\rangle$ such that if we build a binary search tree using that permutation as an input sequence we shall get a binary search tree of height $n-2$.***

Let $f(n)$ denote the function such that for a given input $n$, it gives the answer to our problem above.

Now we can generate the formula for $f(n)$ in a generalized manner, but it shall be longer. Rather let us consider an example case to get the intuition and the general case could be easily derived from it.

Let $n=7$, then we need to consider permutations of $\langle 1,2,3,4,5,6,7\rangle$. Let us consider the structure of the binary tree formed and using that let us compute the number of required permutations.

If $1$ is the root, (then $1$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the right subtree \[of height (n-3)\] of the root. The number of such permutations shall be given by $f(n-1)$.

Similarly if $7$ is the root, (then $7$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the left subtree of the root. The number of such permutations shall be given by $f(n-1)$.

If $2$ is the root then $2$ has to be first element for the current subproblem. $1$ is to the left of root and the remaining $n-2=5$ elements are to the right of root. Now using these $n-2=5$ elements we can form a chain of length $n-3=4$ and starting from the root we shall have a height of $n-2=5$ for the entire tree. A little work out shall show that there are $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$.

*In the subtree outlined with green the dotted edges shows just the possible structure and not the actual edges.*

But for each of these $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$, $1$ can be interspersed anywhere so we shall have $(n-1)$ possible ways for each such $2^{n-3}$ permutations.

Just as the above situation we shall have have for root $6$, a total of $(n-1)\*2^{n-3}$ permutations.

But for $3,4,5$ as the root we shall not be able to form a desired tree as both the left and right subtree in such cases shall fall short of the required number of elements to form a subtree of height $(n-3)$.

For an arbitrary $n$ we can have only the highest, second highest, lowest and second lowest as the root.

So we have,

$$f(n)= 2\*f(n-1)+2(n-1)\*2^{n-3}$$

Now we require a base case. Which is as follows, for $n=3$, we shall two possible input sequence.

So, $$f(n)=2 \text{ if n=3}$$

So using table method we have,

$f(3)=2$

$f(4)=16$

$f(5)=64$

$f(6)=208$

$f(7)=608$

A simple C program by me which verifies this, the program simply uses brute force method,asks for $n$, then generates all permutations of $\langle 1,2,.. n\rangle$. For each permutation inserts the elements into a empty BST keeping track of the height. If height equals $n-2$ then it outputs $\text{YES}$ beside that permutation and at the end, prints the total count of such $\text{YES}$s.

---

**Interpretation 2:**

***Problem: For a given $n$ we need to find the number of structures of binary search trees of height $n-2$ using permutations of $\langle 1,2,3,..,n\rangle$ as input sequence.***

Let $g(n)$ denote the function such that for a given input $n$, it gives the answer to our problem above.

Now we can generate the formula for $g(n)$ in a generalized manner, but it shall be longer. Rather let us consider an example case to get the intuition and the general case could be easily derived from it.

Let $n=7$, then we need to consider the structure of the binary tree formed using permutations of $\langle 1,2,3,4,5,6,7\rangle$.

If $1$ is the root, (then $1$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the right subtree \[of height (n-3)\] of the root. The number of such subtrees shall be given by $g(n-1)$.

Similarly if $7$ is the root, (then $7$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the left subtree of the root. The number of such subtrees shall be given by $g(n-1)$.

If $2$ is the root then $2$ has to be first element for the current subproblem. $1$ is to the left of root and the remaining $n-2=5$ elements are to the right of root. Now using these $n-2=5$ elements we can form a chain of length $n-3=4$ and starting from the root we shall have a height of $n-2=5$ for the entire tree. A little work out shall show that there are $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$ each of which forms a unique structure of binary search tree.

*In the subtree outlined with green the dotted edges shows just the possible structure and not the actual edges.*

Note that now we need not consider interspersing $1$ in each of $2^{n-3}$ permutations above, each such interspersing shall result in the same binary search tree structure.

Just as the above situation we shall have have for root $6$, a total of $2^{n-3}$ binary search trees.

But for $3,4,5$ as the root we shall not be able to form a desired tree as both the left and right subtree in such cases shall fall short of the required number of elements to form a subtree of height $(n-3)$.

For an arbitrary $n$ we can have only the highest, second highest, lowest and second lowest as the root.

So we have,

$$g(n)= 2\*g(n-1)+2\*2^{n-3}=2\*g(n-1)+2^{n-2}$$

Now we require a base case. Which is as follows, for $n=3$, we shall two possible input sequence but only binary tree structure.

So, $$g(n)=1 \text{ if n=3}$$

So using table method we have,

$g(3)=1$

$g(4)=6$

$g(5)=20$

$g(6)=56$

$g(7)=144$

---

An example using $n=4$,
> 2 votes

# Answer
To have height 5, then it's an almost *degenerate tree*; ie you simply check possible ways to have only one node in left or right

Coming out of root, 1st level, 2nd,...
I think there are 10 options, but you have to check them manually maybe some of them cannot happen for this set of numbers

The point is the main property of

*Binary Search Trees* (left child \< parent, right child ≥ parent)

with the constrain of *height=5*

necessities that 6 nodes must be in sorted order with the 7th in different places; each color in the picture represents a way, and there are other 6 if we reverse the direction

*Total=12*
> -1 votes

---
Tags: data-structures, combinatorics, binary-search-trees
---


title: Master Method: Divide and Conquer

text:
# Question
Title: Master Method: Divide and Conquer
According to my evaluation ,the overall asymptotic running time of the below algorithm is `O(n)`  ,since `x` (number of recursive calls) is 1, and `y` ( the number of splits) is 2 , and finally `z` ( the power of amount of work done outside of the recursion call) is 1, hence x\<y^{d}, but my answer turned out to be wrong . Why?

```
 FastPower(a,b) :
  if b = 1
    return a
  else
    c := a*a
    ans := FastPower(c,[b/2])
  if b is odd
    return a*ans
  else return ans
end

```

# Answer
`FastPower` will compute $a^b$ using the following recurrence:

$$\begin{equation}a^b=\begin{cases}a & \text{if }b=1\\ (a^2)^{\frac{b}{2}} & \text{if }b\text{ is even}\\ a\cdot(a^2)^{\frac{b-1}{2}} & \text{if }b\text{ is odd}\end{cases}\end{equation}$$

This is $O(\log{b})$ since $b$ decreases by at least a factor of $2$ each recursive call. This assumes multiplication takes constant time since we perform $O(\log{b})$ multiplications.
> 1 votes

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


# Question
Title: Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?
The question is basically in the title. I know that a computers hardware is of course some physical object, where as the interpreter is some abstract thing that does something abstract with the code it is given. Yet, can we say that the way the processor is build is the implementation of an interpreter?

Machine language is a sequence of physical states (0s and 1s ) on some physical memory, and if this physical states order follows certain rules (the syntax of the machine language) then the processor is build in a way that naturally leads to performing calculation steps (and changing some of the memory), e.g. "run" the programm.

As this question's answer points out, compilers translate from one language to another, and interpreters for each language "run" the programm. It would be just consistent if this stretches down to machine language as well, and that's why I'm asking.

If one can make the analogy, when would it break down? What features of language semantics (given by the interpreter), for example expressions and values, are there that we can't find at the physical level anymore? In what way does the processor behave differently from what is expected of an interpreter?

# Answer
It's not such a bad way of looking at things.

On most modern CPUs, the instruction set architecture (ISA for short) is abstract, in the sense that it doesn't dictate that it must be implemented using certain hardware techniques or it is not a compliant implementation. Nothing in the ISA specification specifies whether or not it uses register renaming, or branch prediction, or whether vector instructions are parallel or pipeline-streaming, or even whether the core is scalar or superscalar.

Indeed, on many modern CPUs, there is a certain amount of translation from the ISA into an internal representation to be executed more efficiently, such as Intel's micro-operations (uOps for short).
> 33 votes

# Answer
No, it would not be wrong. Indeed, we can use the Futamura projections to help us understand the situation.

The first Futamura projection says that if we specialize hardware with some native machine code, then we get a standalone executable. For example, classic video-game consoles combined an interpreter in the console with native code in each game cartridge, so that plugging a cartridge into a console resulted in an executable system. As other answers point out, computability theory implies that we can write (slow) software which is equivalent to the hardware in effects, and indeed emulators exist for most classic consoles.

Edit: A Futamura specializer is a specific sort of program which takes two unevaluated programs and returns their composition. Sometimes it is called a Kleene compositor due to its relationship with Kleene's parameter theorem (the $S^m\_n$ theorem). For more details, see Piponi (with helpful pictures); for even more details, see "Partial Evaluation and Automatic Program Generation". In older computers, inserting a cartridge would close electronic circuits, connecting daughterboard to motherboard and allowing all of the chips in the cartridge to communicate with the chips in the host. This is Futamura specialization; a piece of non-functional hardware was added to existing hardware in order to create a system which is limited in functionality but relatively fast at execution.

The second Futamura projection says that if we specialize the specialization process itself with the interpreter as the curried argument, then we get a compiler. I'll extend the video-game example. A local bar has a large selection of classic games; if we ask the bartender to load a cartridge, then the bartender will allocate a console and deliver controllers. In essence, the bartender is a Futamura compiler.

Less facetiously, we could imagine a compiler in the traditional sense, compiling high-level programmer expressions to native code, but generated using Futamura projections. If this compiler's underlying interpreter is some hardware, then this implies that the compiler will directly call that hardware in order to partially evaluate the static parts of its input programs. And, if one thinks about it for a moment, any partially-evaluating compiler is doing something morally equivalent to this; Futamura would just require that the emulation of instructions is done in a faithful way, using instructions equivalent to the original hardware.
> 8 votes

# Answer
You could look at it that way. But traditionally, the term "interpreter" is usually used to refer to software, not hardware.

There are CPU emulators, these can definitely be considered to be interpreters of the processor machine language.

The distinction between hardware and software implementations is useful in practice because it dictates how easy it is to make changes. If there's a bug in a hardware CPU, you will likely have to replace the computer or processor chip to address it (unless there are software workarounds). But if there's a problem in a software interpreter, you can just install an update (which has become easier over the years, as digital media became more compact and then migrated to Internet distribution). This means that hardware development requires more stringent specifications and testing -- bugs that make it to customers are much more serious and costly to resolve.
> 7 votes

# Answer
You can build any program as a circuit, check e.g. most texts on computability, they often discuss circuit complexity for solving problems in addition to the more traditional Turing machine models (closer to normal programs). For some problems it makes economic/performance sense to create a custom circuit (look e.g. at FPLGA), most of the time it is much cheaper/flexible to just write a program for a more or less general purpose CPU.

If your CPU is build as a fixed circuit, is a microprogram for a more basic CPU, programmed into a FPLGA, or as a program running on some CPU is really irrelevant. All are doing the job of interpreting the instructions.
> 4 votes

# Answer
> If one can make the analogy, when would it break down? What features of language semantics (given by the interpreter), for example expressions and values, are there that we can't find at the physical level anymore? In what way does the processor behave differently from what is expected of an interpreter?

It's a bit of a semantic argument, but "language semantics" themselves don't exist at the physical level; there are physical states and transformations to which we assign a meaning.

You can generally find *values* in a processor all the way down to the bit level of individual transistors. However *expressions* get dematerialised. Instead you will find a set of enable and selector bits that route the values to a logic block which computes a function, then routes the result to a destination.

There are also processor features that don't map cleanly to language features. Out-of-order execution and speculative execution, for example. Speculative execution in particular is *supposed* to be entirely hidden from the programmer's model but in some circumstances has been used as a security exploit (SPECTRE).

Interrupts and aborts are also outside the simple machine code model, as they provide forced control flow transfer to a different bit of machine code.
> 4 votes

# Answer
If you look too much at words, they'll scurry away. In general the boundaries on meanings of words are soft.

As others said, you are not wrong. But, the word *interpreter* is usually used precisely to mean "not the CPU".

How does an interpreter *effectively* carry out its interpretation? What is it interpreting *on*? (Or *into*?)

As the word is customary used, an interpreter is a bunch of instructions carrying out some other bunch of instructions (the program), but the effective execution of the interpreter code is done by something else (the CPU).

I do not know the details of CPUs inner workings, but at some point (say, after microcode translation) "instructions" turn into activation of different parts of the CPU, data turns into state of internal registers, some circuits are activated, producing (physical) internal states transitions, some internal communication lines (buses) are activated or disabled, states are moved from one register to another or to memory, \[much more complicated real stuff omitted\], and that's execution.
> 4 votes

# Answer
TLDNR: No, not wrong.

The words we use are part of communication: you think - you say - I hear - I interpret. Depending on the context the word "interpreter" may be understood quite differently. So be careful when talking and writing, we do have different bakgrunds and different ways of interpreting words.

In my world, an interpreter is most often a software program so I could become confused. But let´s dive a little deeper.

.1 Executing the machine code: Yes the hardware fetches bits from memory and "interprets" them as code and then does what the code says, perhaps multiplying the values in two registers. A software interpreter would do the same. The hardware does some extra things a "pure" software cannot really do, such as consuming power from the power source and creating intended and unintended signals and electrical noise. It is not unusual for hardware designers to experience bugs due to these unintended things, especially in the edge case of supply voltages or temperatures.

NOTE: both hardware and software interpreters may container bugs of course, but that is a different story...

.2 Executing the machine code in detail: You might know of the Intel CPU-s used in a lot of computers, say the 10th generation i9. This computer executes x86 instructions (I am simplifying here, but bare with me). The x86 instructions are actually "translated" and "reordered" inside the i9 CPU before actually beeing executed. This translation process, from one assembly language to the interna language of the processor may be seen as an interpreter if you wish. The reason for the complicated multistage pipeline with translation and reordering is in order to gain performance.

.3 Conclusion: No, you are not wrong to see the hardware as an interpreter. But beware that this is not the common language usage, so you may end up confusing the listener or reader. I would stay away from using words that way, but that is me.
> 3 votes

# Answer
You can call everything everything - in 2021, all of our components (CPUs, machine code, compilers, interpreters) share so many aspects, that you'll find an argument in almost any direction. Maybe it would not be quite wrong to call a CPU an interpreter, but I feel it would be very weird and discount what actual interpreters are about in the first place.

An all-purpose CPU stupidly *executes* its instructions. If we ignore advanced current-days aspects of lookahead and heavy parallelization - i.e., think of an old, extremely simple, 6502 CPU instead of a current Intel or ARM offering - then you see that the CPU looks at one specific point in RAM or ROM, fetches one instruction, then executes that extremely simple instruction. There is nothing between this execution and the electrons running around on the hardware - at this low level, the machine code *is* the electronic layer.

So, no, in general I would say the processor is an *executor*, not an *interpreter*.

Modern aspects could change this. For example, you could create a CPU which understands CISC commands, but does this by running a microcode preprocessor inside the CPU which translates those CISC commands into RISC commands, which then are executed on the actual machinery of the CPU. In this case you could say the the CPU *interprets* CISC code. I would accept this *especially* in the case that this preprocessor has larger state than just the next command; i.e. if it does complex decisions based on previous and next statements. This also leads to branch prediction, parallelization, power management and so on - complex "management" efforts which may be reordering or optimizing the stream of incoming machine commands. This "preprocessor" then would be an interpreter, shoveling commands to its internal execution engine.

An actual interpreter earns its designation by looping over some more abstract representation of a program (sometimes this can be the source code directly, for example in certain scripting languages close to a shell; sometimes bytecode which can be generated upfront (e.g. Java) or on the fly (e.g. Ruby, Perl)). A common theme is that this bytecode is often compatible between different interpreters; famously you can run Java bytecode anywhere from big servers to embedded little machines, which may have nothing much in common on the machine language level.

Finally, all of this is a moving target anyway, since on each level of abstraction, we are combining all kinds of techniques. Your Java interpreter might have a Just-in-time compiler and your pieces of "bytecode" might in fact just be a compiled-in-the-meantime machine code. Your state-of-the-art CPU might have an interpretion layer for compatibility for some generation of CPU 20 years ago. Your compiler might have a compile-time interpreter able to modify compilation in some way, etc.
> 3 votes

# Answer
If the hardware alone can interpret anything, yes. But with modern electronic digital data-processing the software is separate from the hardware. Even the BIOS or UEFI uses code.

In the mid-Twentiethh Century, the programmer actually rearranged the memory. So the memory was the program. There was no storage, per se. That was WHEN the Chairman of IBM speculated, given time, it might be possible to build a computer that weighed under 5 tons!

Given that he also predicted the world market might reach 8, eight computers in the entire world that is, he was a little off! So, if you have no code in the BIOS cmos memory, nothing stored on anything, just hardware and electricity, and 'that' can interpret; the answer to your question is 'yes'.

Otherwise, it is 'no'.
> -1 votes

---
Tags: automata, computer-architecture, compilers, interpreters
---


# Question
Title: Can breakpoints of the beachline move up in Fortune's algorithm?
In these slides describing Fortune's algorithm for constructing a Voronoi diagram, it is noted on page 7 that break points of the beach line can move upward. How is this so?

In most of the cases I can think of, break points always move downward. I couldn't easily think of a case where a break point would move upward.

Is there an example in which an upward break point is produced as sweep-line moves down?

# Answer
> 1 votes
Consider a situation where the sweep line is just below a site q, whose arc intersects arcs corresponding to the same site p on both ends:

---
Tags: computational-geometry, voronoi-diagrams
---


# Question
Title: What is this linear optimization problem?
Given a $d$-dimensional vector $v = (v\_1,\dots,v\_d) \in \Bbb{R}^d$, we define $f(v) = \min\_{i\in \[d\]} \\{v\_i\\}$ to be the smallest coordinate of $v$.

Let $v^1,\dots,v^n \in \Bbb{R}^d\_{\ge 0}$ be non-negative vectors (meaning $f(v^i) \ge 0$ for $i\in \[n\]$). I want to find non-negative $c\_1,\dots,c\_n \ge 0$ satisfying $c\_1+\dots+c\_n=1$ which maximize $$f(c\_1v^1+\dots +c\_nv^n).$$Is this a studied problem? Are there efficient algorithms to exactly solve this problem? If not, what about numerical heuristics?

# Answer
The problem can be solved using linear programming in polynomial time.

Objective Function: $\max \\,\\, \gamma$

Constraint $1$ : $x\_i \geq \gamma$ for every $i \in \\{1,\dotsc,d\\}$. This constraint is due to $f(X) = \min\_{i} \\{x\_i \\}$ for any vector $X = (x\_1,\dotsc,x\_d)$

Constraint $2$ : $x\_{i} = c\_{1} v^{1}\_{i} + \dotsc + c\_{n}v\_{i}^{n}$ for every $i \in \\{1,\dotsc,d\\}$

Constraint $3$ : $c\_{1} + \dotsc + c\_{n} = 1$, and $c\_{i} \geq 0$ for every $i \in \[n\]$

The variables $x\_1,\dotsc,x\_d$, and $\gamma$ are also greater than $0$.

---

Please check carefully if it makes sense. And, let me know of any issue in it.
> 2 votes

---
Tags: reference-request, linear-algebra
---


title: Solving T(n,m) = 3n + T(n/3,m/3)

text:
# Question
Title: Solving T(n,m) = 3n + T(n/3,m/3)
I have the below recurrence: \begin{align} T(n, 1) &= 3n \\ T(1, m) &= 3m \\ T(n, m) &= 3n + T(\tfrac{n}{3}, \tfrac{m}{3}) \end{align}

How to get a tight asymptotic bound for $T(n, n^2)$ assuming that $n$ is a power of 3?

Using the substitution method for $T(m,n)$, I get a very weird relation:

$$T(n,m) = 3n + \frac{m}{3^{k-1}} + n\left(3 - \frac{1}{3^{k-1}}\right),$$ where $k = \log\_3 n$.

Any suggestion would be helpful.

# Answer
Let $S(N,M) = T(3^N,3^M)/3$. If $N \geq M$ then \begin{align} S(N,M) &= 3^N + S(N-1,M-1) \\ &= 3^N + 3^{N-1} + S(N-2,M-2) + \\ &= \cdots \\ &= 3^N + \cdots + 3^{N-M+2} + S(N-M+1,1) \\ &= 3^N + \cdots + 3^{N-M+1}. \end{align} Similarly, if $N \leq M$ then \begin{align} S(N,M) &= 3^N + S(N-1,M-1) \\ &= 3^N + 3^{N-1} + S(N-2,M-2) + \\ &= \cdots \\ &= 3^N + \cdots + 3^{N-M+2} + S(1,M-N+1) \\ &= 3^N + \cdots + 3^{N-M+2} + 3^{M-N+1}. \end{align} It follows that $$ S(N,M)= \Theta(3^N + 3^{M-N}), $$ and so $$ T(n,m) = \Theta(n + m/n). $$ In particular, $$ T(n,n^2) = \Theta(n). $$
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Prove or disprove: $L^n=M^n\nRightarrow L=M$ where $L$ and $M$ are languages
In a homework assignment, it's asked

> For any alphabet $\Sigma$; for all languages $L$, $M$ on $\Sigma$
> Prove that $\forall n\>1$, $L^n=M^n\nRightarrow L=M$

The student and I tried in vain to make a proof for $n=2$ by exhibiting distinct $L$ and $M$ with $L^2=M^2$; so much that I now think the statement may be wrong. What are your thoughts?

# Answer
> 2 votes
What about $\Sigma^\*$ and $\Sigma^\*\setminus\\{11\\}$?

---
Tags: formal-languages
---


title: Unusual MST variant on bipartite graph

text:
# Question
Title: Unusual MST variant on bipartite graph
On math.se, Sybren Zwetsloot has asked for help with an unusual optimal subtree problem. Here's my understanding of what he's asking:

> We have a weighted bipartite graph on two sets $N$ and $B$, call them "nodes" and "buses", with $|N| \geq |B| + 1$. Furthermore (I believe), every bus $b \in B$ has degree $\geq 2$. We want to choose a maximum-weight subtree (or possibly subforest; Zwetsloot seems to be asking both questions) in which every element of $B$ has degree exactly $2$. Omitting some nodes is fine, but the resulting graph must be acyclic.

(Zwetsloot's original question uses the word "elements" instead of "nodes," but this name can be confused with elements of a set, so I changed it here.)

I proved the following partial result:

> The maximum-weight subtree includes, for each bus $b \in B$, the connection with maximum weight among all connections of $b$. If multiple connections are tied for maximum weight, then each of them can appear in a different optimal tree. This is also true of the maximum-weight subforest.

This result lets us divide the graph into $|N|$ "complexes", each containing one node $n$ plus all the buses $b$ such that the edge from $n$ to $b$ is the highest-weight edge connection to $b$. We now have to make an acyclic graph on these complexes by connecting buses in one complex to nodes in another. The degree constraint on buses, though, precludes the usual MST algorithms that make greedy choices of additional edges: there are simple counterexamples (my answer on math.se provides one) for which adding the highest-weight available connection between two complexes forces suboptimal choices later on. Another possibility might be adapting bipartite matching algorithms for choosing remaining node–bus connections, but the no-cycles constraint also makes this difficult.

In general, the degree-constrained MST problem is NP-hard, but the unusual nature of the degree constraints here—every node either has degree 2 or unlimited degree—makes me hope that the there might still be an efficient algorithm. Are there any similar problems or algorithms that have been better studied?

# Answer
The problem is $\mathsf{NP}$-hard. We will show a reduction from the Hamiltonian path problem on general graphs.

Let $G = (V,E)$ be any hard instance of the Hamiltonian path problem.

**Reduction:** For every edge $e = (u,v)$ in $E$, create a new vertex $x\_{e}$. Replace edge $e$ with two new edges $(u,x\_e)$ and $(x\_e,v)$. Furthermore, create a new vertex $x\_{v}$ corresponding to every vertex $v \in V$ and add the edge $(v,x\_v)$. Let $N$ denote the set of all new vertices added. Note that the new graph is a bipartite graph, with partitions $N$ and $V$. Assign each edge of the graph a unit weight. Here $B = V$. It is easy to see that this graph satisfies $|N| \geq |B|+1$. Also, every vertex in $B$ has degree at least $2$.

**Claim:** There exists a hamiltonian path in $G$ if and only if the bipartite graph has a **subtree** of weight $2|B|$ in which every vertex in $B$ has degree exactly $2$.

**Proof:** **(-\>)** Suppose $h: (v\_1,\dotsc,v\_n)$ be the hamiltonian path in graph $G$. Let $e\_{i}$ denote the edge $(v\_{i},v\_{i+1})$ in $h$. Then, $(x\_{v\_{1}},v\_{1},x\_{e\_{1}},v\_{2},\dotsc,v\_{n-1},x\_{e\_{n-1}},v\_{n},x\_{n})$ forms a subtree of weight $2|B|$ in the bipartite graph such that each vertex in $B$ has degree exactly $2$.

**(\<-)** Suppose that there exists a subtree $T$ in the bipartite graph of weight $2|B|$ in which every vertex in $B$ has degree exactly $2$. Then, this subtree contains all vertices of $B$; otherwise, the weight of the subtree would have been less than $2|B|$. Also, note that the degree of every vertex in $N$ is either $2$ or $1$. Therefore, the degree of each vertex in $T$ is either $1$ or $2$. Therefore, $T$ must be a simple path with its vertices alternating between $V$ and $B$. Suppose this path is $(x\_{1},v\_{1},x\_{2},v\_{2},\dotsc,v\_{n-1},x\_{n},v\_{n},x\_{n+1})$. Then, this path corresponds to a hamiltonian path $(v\_1,\dotsc,v\_n)$ in the original graph $G$.
> 2 votes

---
Tags: graphs, np-hard, minimum-spanning-tree
---


# Question
Title: Does $L_1L_2 \notin RE$ imply $L_2L_1 \notin RE$?
Given two languages $L\_1, L\_2$ such that $L\_1L\_2\notin RE$, is it always true that $L\_2L\_1 \notin RE$?

I wasn't able to prove it or find a valid counterexample.

# Answer
> 4 votes
Let $A \subseteq \mathbb{N}$ be an arbitrary subset containing $0$. Define $L\_1 = \\{0^n 1 : n \in A\\}$ and $L\_2 = \\{0^n : n \in \mathbb{N}\\}$. Then $A$ reduces to $L\_1L\_2$, but $L\_2L\_1 = \\{0^n1 : n \in \mathbb{N}\\}$.

---
Tags: computability
---


# Question
Title: what do the tape contents of a turing machine look like after halting?
what do the tape contents of Turing machine look like after halting? Are there empty symbols after the qaccept or reject?

# Answer
The tape contains whatever the Turing machine wants it to. There's no rule that says it has to have certain contents. It must have a finite number of symbols, and all the spaces outside of a finite region must be blank.
> 1 votes

---
Tags: turing-machines
---


title: Meaning of source here

text:
# Question
Title: Meaning of source here
In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero.

The book CLRS makes these statements:

Given a graph $G = (V, E)$ and a distinguished source vertex $s$, breadth-first search systematically explores the edges of $G$ to “discover” every vertex that is reachable from $s$.

I know this is an amateur question but does source have the same meaning here (at least when the graph is directed) or it's just some word the book uses without any particular reason? Maybe by source it means a root.

# Answer
> 3 votes
In that context *source* is just a way to give a specific name to the vertex $s$. It makes sense to use that word since it is the vertex from which all shortest-paths computed using BFS emanate.

---
Tags: graphs, graph-traversal, breadth-first-search
---


# Question
Title: Proving that deterministic approximate counting uses log(n) space
We just saw the Morris algorithm in class and we were asked the following:

> In class, we saw a constant factor approximate randomized counting algorithm with space complexity $O(\log \log n)$, where $n$ is the maximum value of the counter. Prove that any deterministic algorithm that provides a factor $1\pm\frac{1}{10}$ approximation to the count must use $\Omega(\log n)$ space.

I have no idea on how to solve this problem and I would love to get a hint please, just to get me started.

Note that I am not asking for a full solution, just an intuition.

# Answer
> 1 votes
Suppose that such a counter exists, using $f(n) \< \log\_2 (n+1)$ space for some $n$. When running the counter for $n$ steps, it reaches at most $2^{f(n)}$ different states. The state diagram has exactly one outgoing edge out of each state (since the number of states is at most $n$), and so it must be a path that closes onto itself (together, possibly, with some unreachable states). In particular, there are $a,b \leq 2^{f(n)}$ such that the algorithm is in the same state after $a+kb$ steps, for any $k \geq 0$. Taking $k$ large enough, we see that the algorithm fails to estimate the count up to any bounded factor.

If $f(n) = \log\_2 (n+1)$ then the argument fails. Indeed, the state diagram could look as follows: the origin is state $0$, and state $i$ leads to state $i+1$. State $n$ then has no outgoing edge, and this corresponds to the fact that we are not guaranteed that the algorithm uses only $f(n)$ space after $n+1$ steps.

---
Tags: algorithms, counting
---


# Question
Title: House Robber DP Algorithm (Not three in a row)
This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from houses on both the left and the right at the same time. The problem is modified from leetcode as follows:

*"You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if **three** adjacent houses were broken into on the same night.*

*Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. So for the array `[2, 5, 10, 7, 11]` the max you may rob is 26 by robbing houses with values 5, 10, and 11."*

I came across this by misreading the original question (lol) but after working on the modified version I think there is a DP solution here but it seems somewhat complicated and might involve turning the array into DAGs.

# Answer
Consider the first three houses (assuming $n \geq 3$). Any solution does *not* rob one of them, say the first one (you can enumerate over all three options). The remaining houses form a street, which enables us to solve the problem using a simple dynamic programming: for each $0 \leq i \leq 2$ and $j$, we find out the best solution for the first $j$ houses assuming that houses $j-1,\ldots,j-i$ are robbed.
> 1 votes

---
Tags: algorithms, dynamic-programming, arrays, dag
---


title: What is a student process?

text:
# Question
Title: What is a student process?
According to Galvin and Silberschatz, 5 queues are maintained in multilevel queue scheduling, each for:

* System Process
* Interactive Process
* Interactive Editing Process
* Batch process
* Student Process

where System process has highest priority and Student process has lowest priority.

What is meant by **Student Process**?

Also, I only have a vague idea about the rest except system process. If possible, elucidate them.

# Answer
> 6 votes
My best guess: a student process is a process run by a student.

All users have to log in. The OS may well know various types of users, and may be able to determine from some table that a given user is a student. This can be useful to lower their priority for computer time in a shared machine used mainly for research, or possibly do the opposite during exam period. So having a scheduling queue for student processes would make sense.

As far as I know ... there is no direct relation to learning machines who would run processes that are studying something. But who knows? It may be coming.

# Answer
> 0 votes
i dont know what student processes are all about. what i know is that , they are just one of the category of process in multilevel queue scheduling

---
Tags: terminology, operating-systems, process-scheduling, os-kernel, multi-tasking
---


title: Minimum time to finish all meetings

text:
# Question
Title: Minimum time to finish all meetings
what algorithm would you use to solve this problem which I recently faced in an interview?

There's a council where people go to have meetings. A person comes at time x and needs to be in a meeting for duration y. The council has a set number of meeting rooms where 1 meeting room can only host one meeting/person. You need to calculate the earliest time that all meetings have been completed.

You are given 3 arguments:

1. A list of arrival times (this list is not sorted).
2. A list of durations (this has the same length as the arrival times and both are indexed the same, e.g. if for `arrivals[0]` the duration will be `durations[0]`)
3. The number of rooms available.

My solution was:

1. Sort the arrival times ASC whilst keeping their relation to their corresponding duration.
2. Create a priority queue that holds the rooms and is sorted by their earliest availability (e.g. the first out will be the next available room).
3. For each person (e.g arrival): a) get the next available room from the queue (pop); b) calculate when the room will be next available given the person arrival time and duration and c) add the room back to the queue.
4. return the last item of the queue which holds the room with the latest availability.

My solution worked but wasn't good enough as I didn't proceed with the next interview stages.

# Answer
> 3 votes
The problem is equivalent to job scheduling problem on parallel machines. The problem is $\mathsf{NP}$-hard even when the arrival time for each job/person is $0$ and the number of machines (or meeting rooms) are $2$.

The $\mathsf{NP}$-hardness proof simply follows from the partition problem.

More precisely, your problem is equivalent to $P;m|rj|C\_{max}$, i.e.,

1. **P:** Parallel identical machines. Processing time of job $j$ is $p\_j$, independent of the machine.
2. **m:** Fixed number of machines $m$.
3. **$r\_j$**: Job $j$ cannot be scheduled before given release time $r\_j$.
4. **$C\_{max}$**: also called Makespan. The maximum completion time over all jobs. The goal is to minimize $C\_{max}$.

You can explore related papers in scheduling complexity zoo.

---
Tags: data-structures, priority-queues
---


# Question
Title: Is it possible to use one of the two processors for ML acceleration?
I have two processors (two different physical processors) with base frequencies 3.2 Ghz and 4.0 Ghz.
I want to ask if there exist a method which I can use to the 3.2 Ghz processor for ML acceleration ?
I don't have a good gpu for this task.
Will it be slower than a GPU ?

# Answer
I hope this fits as an answer to your question

---

It depends on what type of ML you are trying to do.

For example, I don't really know how to parralelize reinforcement learning techniques (most likely there is a way to parralelize at least some of them), but it is simple to parallelize a supervized learning technique that uses *batching* \- simply distribute the batch between the two processors, and then aggregate the results.

---

I can't tell you if this will be faster of slower than using GPU, since it really depends on the GPU as well. But taking into consideration that GPUs are good at those kinds of computations, my guess would be that a GPU could still be faster if your supervised model is large.
> 1 votes

---
Tags: cpu
---


# Question
Title: What does it mean for an integer to belong to the halting problem?
I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this notation $\mathcal{H}$ is meant to denote the halting problem.

However, I am not sure what it means for an integer to be a member of the halting problem.

# Answer
Turing machines can be encoded as integers in various ways. With respect to any such encoding, we define $\mathcal{H}$ as the set of integers $n$ such that the Turing machine encoded by $n$ halts on the empty input.

The encoding cannot be completely arbitrary. For example, you can design such an artificial encoding in which the parity of the encoding is its halting status. Instead, we fix some natural string encoding (closely following one of the many equivalent definitions of Turing machines), and convert it into an integer encoding $\alpha$ is one of several natural ways (for example, convert the string into a self-delimiting binary string, which can be interpreted as a natural number). We only consider encodings $\beta$ such that an encoding of type $\alpha$ can be converted into an encoding of type $\beta$ of an equivalent machine, and vice versa, in a computable way (by an algorithm). The difficulty of the halting problem (in terms of computability) is the same for all such encodings (which we could call *admissible*).

For more on the issue of admissibility, check out Wikipedia.
> 2 votes

---
Tags: computability, halting-problem, integers
---


# Question
Title: In RBFS, why should expanded nodes inherit F-value of their parent, if their f-value (g(n)+h(n)) is less than their parent's F-value
Here https://uk.wikipedia.org/wiki/RBFS and here https://www.eecs.yorku.ca/course\_archive/2013-14/F/3401/slides/15b-RBFS.pdf it's said that

> f\[s\] ← max(g(s)+h(s) , f\[node\] )

Why is it so? I can see a point in it, in a way that F-value is responsible for telling us what is the best accessible way along the path, and if the best accessible value from the parent's node is x, then obviously it's not less than x in its child as well. But I can't see why the algorithm couldn't do without this inheritance. Moreover, suppose I expand node (that has been previously expanded) with F-value of 10. Its 2 children have g(n) + h(n) 9 and 8. I would like to go down the node with 8, because its value is better and it has a better chance, however they both now inherit 10 and are the same, so I could go down the node with 9 as well.

# Answer
> 0 votes
I found a great paper where it's explained in details. They actually present a version of RBFS, Simple RBFS (SRBFS). where children nodes don't inherit parent's F-value, explain why it's inefficient (a lot of redundant work that already took place), and also explain in which cases inheritance should take place and in which - shouldn't. https://www.aaai.org/Papers/AAAI/1992/AAAI92-082.pdf

---
Tags: search-algorithms
---


title: Comparison sort algorithm

text:
# Question
Title: Comparison sort algorithm
Consider the following algorithm: The given items are inserted one by one into a list by performing comparisons like a binary search for the right position.

Example: Imagine six elements are already sorted in descending order. We now compare the next element to one of the middle elements. Assume it's smaller than #3 (on the left) so we compare it to the middle one of the remaining elements. Assume it's bigger than #5 so we make one last comparison and find it is smaller than #4 so we insert it as the new #5. On the right is another example.

I couldn't find any resources on this, under what name is it known? Thanks in advance.

# Answer
> 1 votes
This is essentially a variant of insertion sort. The general scheme of both algorithms is: mantaian a sorted collection $S$ of elements (initially this collection is empty) and consider one element at a time. When element $x$ is considered, find the position of $x$ in $S$, and add $x$ in that position.

Notice that if you are using an array to back your "list" of elements, then finding the position using binary search rather than linear search is not providing any improvement over the asymptotic computational complexity since inserting an element into $S$ can require $\Omega(|S|)$ time and the overall running time will still be $\Theta(n^2)$.

If you are using an actual list, then you don't have constant-time element access and each binary search still requires roughly $|S|/2 + |S|/4 + |S|/8 = \Theta(|S|)$ operations to locate the elements to compare $x$ with. The running time will still be $\Omega(n^2)$. If you use a doubly-linked list and/or you take some additional care with your implementation, you can match that lower bound with a $O(n^2)$-time algorithm. Otherwise, a naive implementation will require $\Theta(n^2 \log n)$ time.

---
Tags: algorithms, sorting
---