# Question
Title: Why there must be a relationship between user threads and kernel threads?
The following is an excerpt from OS concepts by galvin.Here is the book.

> **Multithreading Models**
>
> Our discussion so far has treated threads in a generic sense. However, support for threads may be provided either at the user level, for user threads, or by the kernel, for kernel threads. User threads are supported above the kernel and are managed without kernel support, whereas kernel threads are supported and managed directly by the operating system. Virtually all contemporary operating systems—including Windows, Linux, Mac OS X , and Solaris— support kernel threads.
>
> Ultimately, ***a relationship must exist between user threads and kernel threads.***

It then goes on to discuss Many-To-One Model,One-To-One Model and Many-To-Many Model.

Question :
Why there ***must*** be a relationship between user threads and kernel threads?

Does kernel thread here means a thread of the kernel(i.e OS)? I don't think so since it clearly specifies that it relates to support for threads.

# Answer
This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program.

When threading first became popular, most operating systems were Multi-processing OS's, but not "multithreaded" in the sense that the operating system provide support for multiple user code streams sharing the same user address space and allowing these threads to be scheduled separately by the OS. Threading was a concept not dealt with by the OS at all. The OS knew processes, what the processes did with the user mode time they were given was their business.

With User mode threading, support for threads was provided by a programming library and the thread scheduler was a subroutine in the user program itself. The operating system would schedule the process to run and the process would schedule the threads within it. There were problems with this model because an event on one thread that caused the OS to block the process effectively blocked all threads within that process. This model only allowed the threads to run on a single CPU at a time, limiting parallelism. This is the many to one mapping model listed in the book. The single Kernel thread is the user process that the kernel schedules.

With Kernel threads, the OS becomes aware of the threads as separate schedulable entities that share the same address space. The OS can then allow each thread to compete for CPU time separately with other threads in the system. This allows the OS to schedule multiple threads from the same process on multiple CPUs at the same time. It also allows it run threads from a process where one thread is blocked, but the others have computable work to do. In this case each user thread has a backing Kernel thread that is a schedulable entity.

The MUST relationship they are talking about is that even if you are using User threads there is an underlying Kernel thread that the OS can schedule. There MUST be a schedulable entity even if it's at the process level. So your first comment is correct.
> 7 votes

# Answer
There by no means must be. I have devised and written an OS that lacks said distinction. User threads have no correspondence to kernel threads at all. Executing a system call is always asynchronous; the user thread continues in user code and picks up the result when it is ready and the thread feels like it.
> 1 votes

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


# Question
Title: Showing strong connectivity is in DSPACE((logn)^2)
$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$
I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:
$\psi(G,s,t,k) :$
$\hspace{1cm}\text{if k == 1: return 1 if there's edge from s to t, else return 0;}$
$\hspace{1cm}\text{foreach } v \in V(G) \text{:}$
$\hspace{2cm}L=\psi(G,s,v,\lceil{\frac{k}{2}}{\rceil});$
$\hspace{2cm}R=\psi(G,v,t,\lfloor{\frac{k}{2}}{\rfloor});$
$\hspace{2cm}\text{if L == 1 and R == 1, return 1;}$
$\hspace{1cm}\text{return 0;}$
The professor said in class that the algorithm takes at most $\mathcal{O}(\log^2n)$ space, where $n$ is the number of vertices. But don't we pass the entire graph each call? I'll expect to see a $|V|+|E|$ factor in the big-oh, or maybe I miss something here.

# Answer
You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.
> 6 votes

---
Tags: algorithm-analysis, turing-machines, space-analysis
---


# Question
Title: What are the differences between parse and decision trees?
I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a decision tree?

# Answer
A decision tree is an algorithm for computing a function, in your case the truth value of the formula. In your setting, each internal node of the decision tree is labeled by a variable, and it has two children; you go to the left one if the variable is false, and to the right one if it is true. Leaves are labeled by True or False, and this is the returned value.

For example, one decision tree for $a \land b$ is as follows. The root is labeled $a$. Its left child is a leaf labeled False. Its right child $x$ is labeled $b$. The left child of $x$ is a leaf labeled False, and the right child of $x$ is a leaf labeled True.
> 2 votes

---
Tags: logic, trees, propositional-logic, bdd
---


# Question
Title: Why does restricting size of input for NP complete problem imply a runtime of O(1)?
I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.

So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N \<= 1000 can be done in O(1)? That doesn't quite follow.

Can someone shed some light on this concept?

# Answer
> 7 votes
If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.

Even worse: Look at the definition of Big-O. The claim is that there is a constant $c \> 0$, and an integer $N\_0 \> 0$ such that for every problem with a size $N \> N\_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N\_0 = 1001$. There are *no problems* with a size \> 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.

# Answer
> 4 votes
If you restrict any problem at all to inputs of size at most $N$, for some fixed constant $N$, then the language is finite, so it's regular. But don't regular languages take linear time? Not in this case: as soon as you see an $(N+1)$st input character, you can reject because the input isn't an instance of length at most $N$. So you only need to look at a constant number of characters to decide any input.

Note that this applies to *any* problem. The problem doesn't even have to be computable.

# Answer
> 3 votes
While the first part of gnasher729's answer gives a good intuition for how to answer any such problem in a time that anyone can see is clearly $O(1)$, there's another way to see that the $O(1)$ claim holds even if we don't do any precomputation and storing of answers.

The thing about bounding the input size by some constant $k$ is that, if you do this, then regardless of what algorithm you use to solve the problem, provided that it eventually terminates on every input of size $\le k$, its worst-case execution time on a size-$n$ input for any $n \le k$ can be described by *some* function $f(n)$ -- and **if all the things that you put into a function are bounded by constants, then what comes out is also bounded by a (probably different, possibly vastly greater) constant.**

The overall worst-case execution time for such an algorithm is then just the maximum of $f(n)$ over all $0 \le n \le k$ -- and the maximum of a finite number of numbers, each of which is bounded by the same constant $c$, is also bounded by $c$.

IOW, even if the algorithm computes everything "the usual way" instead of precomputing all possible answers and storing them (or even if it computes them in "the dumbest, brute-forciest possible way"), the execution time can still be said to be $O(1)$.

# Answer
> 0 votes
We have a finite number of possible inputs, and a solvable problem. Consider any algorithm that solves this problem. Either the algorithm's run time is O(1) or it is not O(1). If it is O(1), then our proof is done.

So what if it's not O(1)? Well, since there are only a finite number of possible inputs, there must be some number of steps that's sufficient for the algorithm to solve any single input, call that N.

We can now construct an O(1) algorithm:

1) Solve the input. Call the number of steps required P.

2) If P is less than N, do nothing N-P times.

This algorithm can solve any possible input in precisely the same number of steps. Thus it is an O(1) algorithm.

# Answer
> -1 votes
The big O notation is to **approximate** to the upper bound (worst case) and gives an idea about how good is the algorithm.

O(1) is the constant-time (time of execution is known in advance) and it is the best one. The O(1) is when T(N) expression does not contain the input size N.

When restricting the size of the input N (N\<=C) and as we ara approximating to upper bound, in T(N) we can replace N by its **known upper bound** the constant C which gives us O(1).

---
Tags: complexity-theory, time-complexity, np-complete
---


# Question
Title: How does the CPU receive, process and output information?
I was studying the I/O process of a PC...and I think I understood it..but not very much so I will type what I understood giving an example..and I hope that I got it right

e.g. typing with a keyboard

First: The Input, and that is done simply by the keyboard..

Second: The information gets to the CPU in binary, but the logic unit doesn't understand it so the Control Unit gets the Instructions saved in the RAM by the CU it self.. then the instructions is sent to the Logic Unit through the CU

Finally:The Logic Unit understands it that time and do some operations that produces some Outputs. The outputs are saved in the RAM, and viewed on the screen

So, please tell me if that's right or if I missed the whole thing.. Thank you very much in advance.

# Answer
From what I know, and I might be slightly wrong here, each device (Mouse, keyboard, screen etc') has a device driver.

The device driver is the one handling the communications with the CPU. Where usually, each device has its own Data register, Status register and Command register (Where the register are basically mapped areas in memory for the device itself).

What happens is when any action is made (i.e pressing a key on the keyboard) the device "updates its status" to ready to send and stores the data it needs to send in some area of memory specifically saved for it, and then interrupts the CPU to perform the action needed.

The CPU sends "Ack" as acknowledgement and accepts the interrupt, executes it, and goes back to what it did before. (Only if the status is ready, otherwise does nothing).

(There are other methods such as busy wait that the device can notify and interact with the CPU).
> 1 votes

# Answer
An easy way to facilitate understanding the working of a CPU is using the Little Man Computer which provides a visual representation of how instructions are processed to manipulate data. You can find it here http://peterhigginson.co.uk/LMC it may be useful to go through the help section to facilitate understanding. Note that this is a simple model. Good luck.
> 0 votes

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: smn-theorem: Application by instantiating s<m, n> with other function
The smn-Theorem on the basis of Turing Machines and computable functions rather than programs, as in the Wikipedia article for instance, can be defined as follows:

$$ \begin{align\*} &&& s \langle m, n \rangle &&= \lceil M' \rceil \\ &&\implies &\varphi\_{s\langle m, n \rangle} &&= \varphi\_{\lceil M' \rceil}\\ &&&&&= f\_{M'}\\ &&\implies &\varphi\_{s\langle m, n \rangle} (i) &&= f\_{M'}(i)\\ &&&&& = f\_{M\_m} \circ f\_{M\_{\langle n, . \rangle} (i)}\\ &&&&&=\varphi\_m \langle n, i\rangle \end{align\*}$$

where $M\_{\langle n, . \rangle}$ denotes, that machine $M\_{\langle \rangle}$ has $n$ already pre-written on its tape and $\lceil M \rceil$ denotes the Gödel-number of machine $M$.

Now, I am confronted with the claim, that

$$ \varphi\_{h(n)}(i) = f\langle n, i \rangle $$

because

$$ f := \varphi\_m \in \text{set of computable functions}$$ then $$f\langle n, i \rangle = \varphi\_m \langle n, i \rangle = \varphi\_{s \langle m, n \rangle}(i)$$

therefore it has to be that

$$ h(n) = s\langle m, n \rangle $$

so I guess then it has to be like this: $$h(n) = \lceil M' \rceil = \lceil f\_{M\_m} \circ f\_{M\_{\langle n, . \rangle }} \rceil = s\langle m, n \rangle$$

And so $h$ contains $f\_{M\_m}$ ... basically *just because* there can be such a function? Am I interpreting this right?

# Answer
> 2 votes
I think you are reading it backwards.

Usually you want to find $h$ such that $\varphi\_{h(n)}(i) = f(n,i)$, where $f$ is a computable partial function. Further, you want $h$ to be total recursive (or even more: primitive recursive).

In order to prove that such an $h$ exists, as well as to concretely define it, one picks any index $m$ for $f$, so that $\varphi\_m = f$, and chooses $h(n) = s(m,n)$.

Note that, when reading the reasoning above in the other direction, it becomes wrong. That is: it is *not* the case that, since $\varphi\_{h(n)}(i) = f(n,i)$ we can conclude $h(n) = s(m,n)$.

Indeed, $h$ may also be another function, like e.g. $h(n) = pad(s(m,n))$ where $pad$ is a padding function (which returns the Gödel number for an equivalent TM, such that said Gödel number is larger). Infinitely other (computable) $h$ exist.

---
Tags: computability
---


# Question
Title: Efficient algorithm for graph canonization for directed acyclic graphs?
I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed acyclic graph. Or, are there any tricks that allow the canonization of a dag to be computed more efficiently than a general graph?

Determining the canonical form in general is GI-complete, but there are many specialized graphs for which it can be calculated in polynomial time. I didn't have any luck determining whether acyclic digraphs were among those specialized types, however.

# Answer
According to Wikipedia (which references lecture notes of Zemlyachenko, Korneenko and Tyshkevic), isomorphism of directed acyclic graphs is GI-complete. Therefore any polynomial time canonicalization algorithm for directed acyclic graphs would result in a polynomial time algorithm for graph isomorphism. Since no such algorithm is known, one concludes that no polynomial time canonicalization algorithm for directed acyclic graphs is known, and it is conjectured that none exists.
> 5 votes

---
Tags: graphs, time-complexity, graph-isomorphism
---


# Question
Title: Linear time algorithm for finding $k$ shortest paths in unweighted graphs
> **Definition.** Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "*A New Implementation Of Yen's Ranking Loopless Paths Algorithm*" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "*Finding the k shortest paths*" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?

# Answer
> -1 votes
No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers

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


# Question
Title: Generate random point inside a polyhedron
I would like to know if there are *known* algorithms for generating a random point(say following a probability distribution *P*) inside an arbitrary polyhedron(possibly non-convex and may contain holes)?

I find approaches for 2D case like the one described here but none in the case of polyhedrons(3D). Whether extending this approach for 2D is the only way, in which case that *random* point will still be forced to be on the surface of a triangle of a tetrahedron in the 3D triangulation of the given polyhedron?

# Answer
If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow for high dimensions and "unboxy" polytopes though, because the bounding box potentially has a huge volume compared to the region you're interested in.
> 6 votes

# Answer
To implement adrianN's rejection sampling method, you will need a function to determine if a point is inside your polyhedron. This not-completely-trivial problem is discussed in my book *Computational Geometry in C*, and there is code available.

---
> 3 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: NP-hardness of maximum set cover with even/odd coverage requirement
Given universal set $U=X \cup Y = \\{x\_1, \ldots, x\_{n\_1} \\} \cup \\{y\_1, \ldots, y\_{n\_2}\\}$ where $X \cap Y = \emptyset$ and sets $\mathcal{S}=\\{s\_1, \ldots, s\_m\\}$ such that $s\_i \subseteq U$ for all $i=1,\ldots,m$ and integer $k \in \mathbb{Z}^{+}$.

Find $\mathcal{C} \subseteq \mathcal{S}$ (denote $Z = \cup\_{s \in \mathcal{C}} s$) that maximizes

$|\\{ z \in Z \mid (z \in X \text{ and is covered even times by } \mathcal{C}) \text{ or } (z \in Y \text{ and is covered odd times by } \mathcal{C} )\\}|$

s.t

* $|\mathcal{C}| = k$

In other words, we consider an element to be covered if it satisfies the odd/even coverage requirement according to its membership ($X$ or $Y$).

This problem differs from the standard maximum set cover in the definition of "covering an element".

Is this problem **NP**-hard? Is so, how to prove it?

# Answer
> 3 votes
One can rephrase your question as follows:

> Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.

A very similar problem was shown to be NP-complete by Stadnicki on cstheory:

> Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?

This implies that your problem is intractable as well.

---
Tags: optimization, np-hard, np, discrete-mathematics, set-cover
---


title: dining metaphysicians problem

text:
# Question
Title: dining metaphysicians problem
Here is a problem vaguely related to the dining philosophers problem. Three metaphysicians go to a restaurant for dinner. When it is time to pay the bill, they decide that they want one of them to pay the entire bill, but without the other two knowing who paid the bill. Ideally, they'd put three tokens in a bag, one white and two black, and secretly draw a token at random. But this is not allowed. They each have a random generator (coin, dice), and they are limited to exchanging information between each other, either publicly or in private between two of them. For example, all three of them may flip a coin, take note of their coin flip (H or T) and inform their left neighbour of the result. Then the metaphysician whose coin flip equals the coin flip of his right neighbour pays, and the other two don't pay (and don't know who paid). This only works, however, for THH, TTH, HTT, HHT, HTH, and THT; but not for HHH and TTT (since in those cases, all three of them would be paying the entire bill).

Here is my attempt at a solution. Let $R$ be a finite event space for the random generator, ${r\_1,...,r\_n}$, let $S$ be $\\{0,1\\}$, and $T$ be a suitable set. Let $f$ be a mapping from $R$ to $S$ and $g$ be a mapping from $R$ to $T$. $f$ maps the outcome $r\_i$ to heads or tails as in the coin flipping example. $g$ is a function that masks the $r\_i$ while providing enough information to decide whether the procedure needs to be repeated (because the $f$ results are of the HHH or TTT type). The metaphysicians reveal their outcome $f(r\_i)$ only to their left neighbour and announce $g(r\_i)$ publicly. Here is what $f$ and $g$ need to be able to do: (i) knowing all $g$ values determines whether $f(r\_1)=f(r\_2)=f(r\_3)$ or not; in the former case repeat the procedure. In the latter case apply the coin flipping example to determine who pays. (ii) the probability of $f(r\_L)=f(r\_\mbox{me})$ conditional on knowing $(g(r\_L),g(r\_{\mbox{me}}),g(r\_R))$ and $f(r\_\mbox{me})x≠f(r\_R)$ is $0.5$ so that I don't know who pays the bill if my coin flip differs from the coin flip of my right neighbour. $r\_L$ is my left neighbour's outcome, $r\_R$ my right neighbour's outcome. If I had functions $f$ and $g$ fulfilling these constraints, I'd have a solution for my problem, but I don't know what $f$ and $g$ might look like. $g(r\_i)$ could be something like an md5sum, not allowing me to infer $f(r\_i)$ which determines the payor.

# Answer
Using secure multi-party computation, there exists a polynomial-time protocol for this problem.

The functionality is

$$F\_i(r\_1,r\_2,r\_3)=((r\_1 \ne r\_2) \lor (r\_2 \ne r\_3) \lor (r\_1 \ne r\_3), (r\_i = r\_{i+1}) \land (r\_i \ne r\_{i-1})).$$

In other words, in the ideal world, participant $i$ flips a coin to get $r\_i \in \\{0,1\\}$ and sends it to the trusted third party; they receive $F\_i(r\_1,r\_2,r\_3)$ back, and the first bit of the result indicates whether to repeat or not and the second bit indicates whether to pay.

It's a powerful theorem from the cryptographic literature that there exists a protocol for *any* functionality, with computational security and running in polynomial time. Thus, there exists a protocol for this problem, too. It will be secure as long as no more than 1 of the 3 participants are malicious.

See https://en.wikipedia.org/wiki/Secure\_multi-party\_computation and a good textbook on theoretical cryptography.
> 1 votes

---
Tags: cryptography
---


# Question
Title: Newbie: hexadecimal editors to make sense of binary files
As a disclaimer, I am a geophysicist, not a computer scientist.

I have a binary file with a whole bunch of data in it (it is a large file; 221 MB). I am trying to convert this to something usable but I don't want to just find some online converter and hope for the best, I would prefer to actually understand what is going on. As a bonus, I have an ASCII file which was converted from the binary file a long time ago by a former co-worker, so I have a baseline of what is correct.

I have at my disposal a hex editor (not sure if this is necessary). If I open the ASCII file in a hex editor, I can easily understand what's going on: look up a hex-to-ASCII table online and you can easily convert the hex into a readable ASCII.

But what about binary? If I take the binary file into a hex editor, I can convert the hex into binary. But how can I convert the binary into something readable like text, headers, strings, integers, etc?

Really dumb this down for me if possible. For example, the first row in my hex editor reads:

20 02 00 00 26 53 53 42 89 b2 e5 c2 71 3d 76 41.

Can anyone give me a step by step intro into how to take this line and convert it to the matching data I have in my ASCII?

# Answer
> 1 votes
> 20 02 00 00 26 53 53 42 89 b2 e5 c2 71 3d 76 41

Full answer is impossible in your case, instead I'm giving clarifications.

We should know the data format to convert binary file to human readable form or do a work similar to breaking a naive cryptographic protection. At layman's terms, we have an ordered set of senseless bytes without a clue. We need somebody or soft knowing what contained inside. Isn't there some documents? It's unusual to keep a final proceeded scientific data without any explanations how to use it because nobody else will be able to use it.

> I can convert the hex into binary

Hex is a binary representation, not a completely separate format, in general. The hex editor more comfortable way than reading 01100101. Hex editor can presume what these bits mean in integers, floats, rgb, utf-8, ansi and some other common data formats. If the format unknown it is useless as well.

For example, I can't recognize the format with one row. Somebody with a vast hexing experience maybe has a chance to do it. This string isn't looking as an ASCII (as you proposed) as a file header, etc.. It can be hieroglyphs from utf-8, but most of the binaries have some sense in Unicode (桂䉓늉싥㵱䅶). In ASCII it converts into something like (space) EOA NUL NUL SUB S S B Y (the next is not ascii chars at all) "b2 e5 c2".

---
Tags: arithmetic, base-conversion
---


# Question
Title: Number of cycles that arithmetic instruction takes for 25% improvement in performance?
The program has the following proportion of instructions: Arithmetic: 70% Load/Store: 10% Branch: 20%

The question is to `find the number of cycles on average that an arithmetic instruction take for a 25% improvement in performance if load/store and branch instructions are not improved at all?`

How to proceed with such type of questions?

# Answer
Hint: You have 100 fruit: 70 Apples, 10 Lychees and 20 Bananas. You want to reduce the number of apples until you have only 75 fruit left. How many apples do you have to eat?
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: “In object-oriented programming, the program is organized around its data”
In a description of OOP in my textbook, it is written that “in procedure oriented program the program is organized around its code while in object oriented programming, the program is organized around its data”. What is the meaning of this statement? An explanation with an example would be of great help.

# Answer
procedure oriented programming means you can group some operations to finish a task when you know how to do it，step 1，step 2…… object oriented programming means you can inspect a object from two parts，its features (states or data) and its behavior in different states.
> -1 votes

# Answer
Before answering the question you have to understand the difference between code and data. Data(input) is a raw fact that manipulates into a new data(output) and Code defines the behaviour like how that data converts to that form.

As we know procedural programming is to divide the program into pieces(module) and then work on separate piece ; These pieces are distinct and interrelated. Every data is local to its piece i.e data is only manipulated by the code within piece.This Doesn't mean the data never be changed , it cannot be manipulated from outside but can be over written. Now the question arises how data be over written?

It is matter of fact that a new module by a new member can accidentally use the variable(data) that is already be used in other module.Thus the value being return from other module is overwritten. Thus insignificance of a data cause a Procedural programming to be organised around code.

Thus Object Oriented programming is build to focus more over Data (Generally both code & data).Like procedural programming having pieces or modules , OOPs having 'Classes';Code & data are bind as an object thus you can independently use the data regarding the class.To overwrite it you have to use the same object regarding of that same class.So in OOPs if a new class is created then there is no way you can overwritten the values because to overwrite the data you need same class in which the object is created.Thus OOPs is organised around data.
> -1 votes

# Answer
There are different approaches to find solutions to problems in computer science.They are called paradigms. Procedural and OOP are two kind of paradigms.

**Procedural programming**

> uses instructions to tell the computer what to do step by step.
>
> For example: cobol,fortran,c

**Object oriented programming**

> approach to problem solving where all calculations are carried out by objects.
>
> For example: java,php,c#

**What is the difference?**

In Procedural programming The steps of code(instructions) determine and controls the way of working the program.But in Object oriented programming based on objects.An object is a instance of class. Class is a group of objects with common properties and common behaviours. Once you have created class, You can use that class any where in the code.That means , Code doesn't determines the way of working the program.But program is dependant on the internal structure of the class. That means, It is dependant on the attributes and behaviours(data and the way of handling those data). So now It is clear that, **“in procedure oriented program the program is organized around its code while in object oriented programming, the program is organized around its data”**
> -1 votes

---
Tags: programming-languages, object-oriented
---


title: Stereotype in UML

text:
# Question
Title: Stereotype in UML
What is a Stereotype in Unified modelling language?And What are the primary class stereotypes?.I need clear explanation using diagrams or real world scenario.

# Answer
> 0 votes
A stereotype is a mechanism you can use to categorize your classes. You can create new stereotypes and categorize as you like

For example:

> Think if you want to simply find all of the forms in the model. In that case you can create a stereotype called form and assign all of your view classes which consists with a form, this stereotype. To find your forms later You would just need to look for the classes with that stereotype.

There are three primary class stereotype in UML.

1. Boundry class
2. Entity class
3. control class

**Boundary class**

They provide the interface to a user or another System(ie. Interface to an actor)

**Entity class**

They are needed to perform task internal to the system, reflect a real world entity.

**Control class**

Serve as the glue between boundary elements and entity elements, implementing the logic required to manage the various elements and their interactions.

---
Tags: terminology, modelling, software-engineering, object-oriented
---


# Question
Title: Find Divisible Sum Pairs in an array in O(n) time
You are given an array of n integers `a0, a1, .. an` and a positive integer `k`. Find and print the number of pairs `(i,j)` where `i<j` and `i+j` is evenly divisible by k (Which is `i+j % k == 0`). This problem has been taken from Hackerrank.

We need a solution in `O(n)` time.

An explanation is that we can do this by separating elements into buckets depending on their mod k. For example, you have the elements: `1 3 2 6 4 5 9` and `k = 3`

```
mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

```

Now, you can make pairs like so:

> Elements with mod 3 == 0 will match with elements with (3 - 0) mod k = 0, so other elements in the mod 3 == 0 list, like so: (3, 6) (3, 9) (6, 9)

Further:

> There will be n * (n - 1) / 2 such pairs, where n is length of the list, because the list is the same and i != j. Elements with mod 3 == 1 will match with elements with (3 - 1) mod k = 2, so elements in the mod 3 == 2 list, like so: (1, 2) (1, 5) (4, 2) (4, 5)

It makes sense that (3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired) since (a + b)% k = 0 = a % k + b % k.

What isnt clear is how the other pairs `(1, 2) (1, 5) (4, 2) (4, 5)` were generated by combination of elements in the 1st (mod 3 == 1) and the 2nd (mod 3 == 2) bucket and why would there be n * (n - 1) / 2 pairs.

# Answer
Consider in your example the set $S\_1=\\{1, 4\\}$ and the set $S\_2=\\{2,5\\}$. Let $n\_1 = 2$ and $n\_2=2$, the sizes of sets $S\_1$ and $S\_2$. All of the elements $x\in S\_1$ satisfy $x\equiv 1\pmod 3$ and so are of the form $x=3s+1$ for some $s$. Similarly all $y\in S\_2$ are of the form $y=3t+2$ so $x+y=3s+1+3t+2=3(s+t+1)$, which is divisible by 3. The number of such pairs is $n\_1\cdot n\_2$: pick one element, $x$, from $S\_1$ and one element, $y$, from $S\_2$ to form the pair $(x, y)$, rearranging, if necessary so that the first element is less than the second. In sum, there will be $n\_1\cdot n\_2=2\cdot 2$ pairs: $(1, 2), (1, 5), (4, 2), (4, 5)$, which, after arranging the pairs in component orders, gives $(1, 2), (1, 5), (2, 4), (2, 5)$ (your highlighted quote didn't do that).

For a general $k$, then, you'll have sets $S\_i$, for $i=1, \cdots k-1$ (ignoring $S\_0$ for the moment), so if $n\_i$ represents the size of $S\_i$, you'll have pairs $(x,y)$ where $x\in S\_i$ and $y\in S\_{k-i}$. The number of such pairs is $n\_1\cdot n\_{k-1}+n\_2\cdot n\_{k-2}+\dotsc$.

\[You have to be a bit careful, since, first, the sum only should include those products $n\_i\cdot n\_{k-i}$ for which $i\<k-i$, and second, you'll have to account for the cases where $i$ and $k-i$ are equal. You'll also have to deal with the pairs you get from $S\_0$, which have to be counted differently.\]

I'd suggest ignoring the sentence where $n(n-1)/2$ appears: it's true but irrelevant.
> 1 votes

---
Tags: algorithms, arrays, modular-arithmetic
---


# Question
Title: Hardness amplification of PRFs by increasing key length
I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF constructions which take into account key length for increasing hardness? Alternatively, are there any constructions which transform a $(t, \epsilon)$ PRF of key length $k$ to something like $(t^2, \epsilon)$ PRF of key length $2k$ or $k^2$?

# Answer
It's important to be clear about what is the purpose of the GGM construction. The GGM construction is designed to build a PRG out of a PRF: i.e., to construct one primitive, given an instance of a different primitive. It's not designed to increase the security of the underlying primitive.

This is a general theme in a lot of provable cryptography: you have to start with a primitive that is secure; then you can build other things out of it, but the primitive you start with has to be secure, or else you can't do anything. The standard constructions don't increase the security of the basic primitive; instead, that's the job of the person who designed the basic primitive.

Hardness amplification is a different task. Hardness amplification means: given a primitive of type T, build another primitive type T that is more secure (in some sense). In general, provably-secure hardness amplification is very difficult to achieve. Why? Well, we don't know how to build any crypto algorithm that is provably secure; all we know is conditional results (if you give me a secure one-way function, then I can build other things that are secure).

There *are* some examples of techniques that given a $(t,\epsilon)$-scheme construct a new scheme that is something like $(t,\epsilon^2)$-secure, but that's different. (If you're interested in that, spend some quality time with Google and Google Scholar looking at results on "hardness amplification"; see, e.g., Yao's XOR lemma.) I don't know of any techniques that given a $(t,\epsilon)$-scheme construct a $(t^2,\epsilon)$-scheme.
> 2 votes

---
Tags: complexity-theory, pseudo-random-generators
---


# Question
Title: Are basic CS algorithms used in machine learning?
I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement learning etc. Is it true that learning basic algorithms is not necessary for learning machine learning concepts ?

# Answer
I would say that machine learning is a part of computer science.

Machine learning is defined by Tom Mitchell:

> A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

This means that an algorithm on a defined task (e.g. classification, regression) on which you define a measure (e.g. accuracy, mean squared error) is a machine learning algorithm when it improves with more data.

## Which algorithms are used?

* Deep learning: This is machine learning with neural networks. There is much more in machine learning than neural networks, but currently they give the most astonishing results and a lot of progress is happening with neural networks. Neural networks are trained with gradient descent; a numeric optimization algorithm known for a long time.
* Dynamic programming: A very simple way to classify is by comparing a new pattern with all known patterns. For time series, there is an algorithm called "dynamic time warping" which calculates the minimum distance to map a series of points to another series of points. So DP is used in machine learning.
* Graph algorithms: Clustering is a machine learning task. CLARANS is a clustering algorithm which operates on a virtual graph. Good luck understanding this algorithm without knowing what a graph is. Or in automatic speech recognition beam search.
* Sorting: There are fancy approaches like Neural Turing Machines which are able to learn to sort. In fact, they are **theoretically**(!) able to learn any algorithm just by data. However, they are MUCH worse in any respect than simple quicksort. We don't even talk there about Timsort.
* A lot more. And a general knowledge of algorithms and datastructures is very important. Machine learning is awesome if you have really complicated problems where you can't find a solution analytically. Many computer vision tasks, automatic speech recognition, translation, some control problems are examples for this task. However, there are many more tasks which can be solved in an optimal way without machine learning. Knowing about algorithms and when to apply which approach is crucial if you want to design good software.
> 2 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, dynamic-programming, neural-networks
---


title: Time complexity of Depth First Search

text:
# Question
Title: Time complexity of Depth First Search
Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about.

I was reading the DFS algorithm from *Introduction to Algorithms by Cormen*, and this was the algorithm:

```
G        -> graph
G.V      -> set of vertices in G
u.π      -> parent vertex of vertex u
G.Adj[u] -> adjacency list of vertex u

DFS(G)
1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color == WHITE
7         DFS-VISIT(G,u)

DFS-VISIT(G,u)
1   time = time + 1            // white vertex u has just been discovered
2   u.d = time
3   u.color = GRAY
4   for each v ∈ G.Adj[u]      // explore edge u
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)
8   u.color = BLACK            // blacken u; it is finished
9   time = time + 1
10  u.f = time

```

It then said lines `1-3` and `5-7` are `O(V)`, exclusive of the time to execute the calls to `DFS-VISIT()`. In `DFS-VISIT()`, lines `4-7` are `O(E)`, because the sum of the adjacency lists of all the vertices is the number of edges. And then it concluded that the total complexity of `DFS()` is `O(V + E)`.

I don't understand how that came about. `DFS-VISIT()` is called *inside* `DFS()`. So, if lines `5-7` of `DFS()` are `O(V)` and `DFS-VISIT()` is `O(E)`, then shouldn't the total time complexity of `DFS()` be `O(VE)`?

# Answer
The book is counting the number of times each line is executed throughout the *entire* execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear:

```
PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1

```

In each execution of A, line 1 of B is executed $n$ times, and B itself is executed $n$ times. Nevertheless, the running time is $O(n)$ rather than $O(n^2)$.

Here is another example, in which an array $T\[1\ldots n\]$ is involved.

```
PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
4    ADVANCE()
5    count = count + 1
6    index = index + 1
7  return count - 1

PROCEDURE ADVANCE():
1  while index <= n and T[index] == 0:
2    index = index + 1

```

The procedure COUNT counts the number of 1s in the input array T. Even though ADVANCE could be called up to $n$ times by COUNT and the worst-case running time of ADVANCE is $O(n)$, lines 1–2 of ADVANCE run at most $n$ times, and so the overall running time is $O(n)$ rather than $O(n^2)$.
> 8 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, trees, graph-traversal
---


# Question
Title: I can't understand this example of PDA Automata
looking for old tests of Language Theory, I see this exercise:

Give a PDA automata that recognize the language $L = \\{w \in \\{a,b\\}^\*,\ 2|w|\_a=3|w|\_b\\}$

They propose this solution:

Can anyone help me to understand what strategy they used?

Sorry for my english, is not my native language.

Thanks.

# Answer
> 1 votes
The idea of this PDA is very simple. Start with a PDA for $L' = \\{ w \in \\{a,b\\}^\* : |w|\_a = |w|\_b \\}$, and now modify it as follows:

1. Whenever you read $a$, simulate the original PDA reading $aa$.
2. Whenever you read $b$, simulate the original PDA reading $bbb$.

Hopefully you can see why the new PDA accepts $L$ given that the original one accepted $L'$.

The PDA for $L'$ maintains a stack which can be of three different types, depending on the word $x$ seen so far:

1. If $|x|\_a = |x|\_b$ then the stack contents is $Z\_0$. In particular, this is also the initial stack.
2. If $|x|\_a \> |x|\_b$ then the stack contents is $B^{|x|\_a - |x|\_b} Z\_0$.
3. If $|x|\_a \< |x|\_b$ then the stack contents is $A^{|x|\_b - |x|\_a} Z\_0$.

When the top-of-stack is $Z\_0$ we know that $|x|\_a = |x|\_b$, and so we optionally move to the final state; the PDA will accept only if $x = w$, since otherwise it will get stuck.

When converting this PDA to the one for $L$, we use epsilon transitions to simulate reading the second $a$ and the second and third $b$s.

---
Tags: automata, pushdown-automata
---


# Question
Title: Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?
Given a DFA (D1) with P1 states, that accepts a language L1.

Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a palindrome (of maximum length P1).

How many states would the minimized D2 have (worst case)? And time complexity?

Similarly, NFA (N1) with Q1 states that accepts a Language L3. How many states would minimized (N2) have (worst case)? Along with its time complexity?

The generic Palindrome Language is non-Regular hence a DFA/NFA for it is impossible but I am unaware of the limited Palindrome case in DFA/NFA?

# Answer
> 0 votes
For DFAs, the size of $D\_2$ is always at most $O(P\_1|\Sigma|^{P\_1/2})$, and this bound is tight up to the $P\_1$ factor. For the lower bound, take a DFA for $\Sigma^\*$ having $P\_1$ states (you haven't specified that $D\_1$ is minimal). The DFA $D\_2$ accepts all palindromes of length $P\_1$, and so Nerode's theorem shows that for even $P\_1$, the optimal DFA $D\_2$ contains $\Theta(|\Sigma|^{P\_1/2})$ states. The upper bound now follows by using the product construction.

The exact same reasoning works for NFAs as well, although you need to replace Nerode's theorem with a suitable "exchange lemma" in order to show that any NFA for the language of all palindromes of length $P\_1$ requires $\Omega(|\Sigma|^{P\_1/2})$ states (for even $P\_1$).

If you insist on $D\_1$ being minimal as well, then instead of a DFA for $\Sigma^\*$ take a DFA for $(\Sigma^{P\_1})^\*$, to get the exact same results. This construction works also for NFAs.

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


# Question
Title: Algorithm with no closed-form exact complexity
Does there exist an algorithm for which an exact complexity *provably* cannot be expressed in closed-form?

Here closed-form means a *finite* composition of addition, subtraction, product, division, factorial, power with any exponent, logarithm, trigonometric function, inverse trigonometric function, hyperbolic function, and inverse hyperbolic function. You may choose a subset of the above functions to allow in a closed-form expression; this makes the problem easier. However, the larger the set of allowed functions, the better, since this also answers the problem for the subsets.

*Exact complexity* is a function from the input-set to a real number. You may group the input by some property, and then study *exact worst-case complexity* instead (or *exact best-case complexity*).

Any computational model will do, as well as counting any resource (e.g. number of comparisons). To close off a trivial solution, a function without a closed-form expression cannot be a primitive operation of the computational model.

If yes, is there a simple example of such an algorithm?

# Answer
The runtime of an algorithm that computes the Ackermann function can't be expressed using primitive recursive functions. All commonly known named functions (well, besides the Ackermann function) are primitive recursive as far as I know.
> 4 votes

# Answer
Here's a trivial example of an algorithm whose running time has no closed form:

```
let x = f(n)
while x >= 0: x := x - 1

```

where `n` is the parameter and `f` is a function with no closed form and with a running time that has a closed form.

It's always possible to construct an algorithm with any (computable) running time. There are as many ways as you like to do nothing. Sure, this isn't the optimal way to do nothing, but we don't limit the study of algorithms to optimal algorithms. In fact, we need to evaluate the complexity of an algorithm before we can say whether it's optimal.
> 4 votes

# Answer
You can always find the exact number of operations by simulating the algorithm and counting all operations. If you accept that as "closed form" then obviously you can give the exact number of operations for any algorithm.

If not, then I assume that you would want to know if it is possible, after careful human analysis of the algorithm, write a program that looks at any input for the algorithm, and within reasonable time and without simulating the algorithm calculates a reasonable approximation for the running time of the algorithm for that input.

Take a simple algorithm like Quicksort. You choose a pivot, and the choice of the pivot, good or bad, massively affects the runtime. It is possible that some input data *always* produces a really bad choice of the pivot, and excessive runtime. Even if you introduce a pseudo-random generator to pick the pivot, there's still the possibility of excessive runtime. To give a decent approximation for the runtime for some input, you don't really have any choice but simulating the algorithm.

Well, there's probably someone more clever than me, and maybe it is possible to analyse Quicksort, but then Quicksort is a very simple algorithm.

PS. The OP has now stated that he wants the running time of an algorithm **based on some simple parameter**. **That's nonsense**. He's not going to get that. Again the example Quicksort: The runtime depends on the exact ordering of the values in the array in a highly complex way. For any implementation, I can produce an array that maximises the running time, and a single change of one item in that array total changes it.
> 0 votes

# Answer
There are plenty of simple algorithms whose running-time is unknown in *any* form. Therefore, their "complexity" can not be expressed in closed-form either, for suitable notions of "closed-form".

Note that, ironically, some unknown running-time functions *may* have closed forms in the rather vague sense of "using commonly used names for things" since some famous unknown quantities *have* been given names.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: How are the number of bytes less than the number of pixels in an image?
Lets take, for example this jpeg image here

The image there is 400 x 300, or 120000 pixels and The file size of the image (on my computer) is shown to be 65171 bytes.

This means the computer stores about 2 pixels in every byte. How does it do this? Is it due to the same color pixels repeating in the image, so it only has to save the RGB data once, or is there some other trickery going on here?

# Answer
A colour image is typically digitalized using 256 levels for each of the 3 RGB channels. That gives 3 bytes per pixel. The trick to attain smaller file size is to apply some compression, to take advantage of the redundacy (neighbouring pixels tend to have similar colours). That depends on the image format. For example, PNG format applies a "lossless" compression (no information lost). JPEG format applies a more aggresive lossy compression (some information lost). BMP format is a format that does not (by default) compress; you can try to open your image and save it in BMP format and check that the size is approximately the expected (3 bytes per pixel). Other thing you can try is to generate a big "pure noise" image, and check that the size is also about 3 bytes per pixel (compression does not work here).
> 3 votes

---
Tags: image-processing, data-compression, storage
---


# Question
Title: What do you call a "non-probabilistic Bloom Filter"?
One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.

It is a technique for caching easy answers for a subset of an input domain before falling back to an expensive computation. In that respect it reminds me of the semantics of a Bloom Filter or the pre-optimization idea of a Karnaugh Map.

Simple description w/ pseudocode:

```
// Determine whether "foo" is true with respect to the given ComplexThingy,
//   for the inputs bar and baz

boolean isFoo(ComplexThingy t, A a, B b):
    // Let's say A and B are enums, or ints in a limited range, etc.
    return expensive_computation(t, a, b)

```

```
// Alternative implementation w/ enhanced ComplexThingy for which
//   "trivial" cases (i.e. those that can ignore all but one dimension of the
//   input space) have been precomputed and stored in a simple bit array

boolean isFoo(ComplexThingyV2 t, A a, B b):
    if t.quickPosLookup[a]
        return true
    if t.quickNegLookup[b]
        return false
    return expensive_computation(t, a, b)

```

Hopefully I've been able to convey that clearly. Thanks for your time!

# Answer
> 2 votes
This is related to the notion of "fast path, slow path" from computer systems. In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first test whether the input falls into that case and if so solve it and return immediately; otherwise, fall back to the complex computation. For instance, the slow path might have to handle corner cases and difficult situations that arise only rarely.

---
Tags: data-structures, bloom-filters
---


# Question
Title: Sifting algorithm for group generated by a set
On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2).

I have some confusions.

Why it is written that an entry $M\_{i,j}, j \< i$, cannot be referenced? what is the meaning of "reference" here?

Thanks.

# Answer
> 1 votes
One possible explanation is that it is indicating that you should never try to read or use any matrix element $M\_{i,j}$ where $i\<j$. "Referenced" might be talking about "de-referencing" a pointer, i.e., reading a memory cell, i.e., reading an entry of the matrix. Perhaps the text is indicating that the matrix entries $M\_{i,j}$ are only defined for $i \ge j$.

I suggest you read the text with this possible perspective in mind and see if it seems consistent with the surrounding context.

---
Tags: algorithms, group-theory
---


# Question
Title: DFS for all possible walks from a source to a destination with exactly k edges
Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk.

My question is that, say we have a DAG (directed acyclic graph), can DFS be a solution to the problem? I understand that native DFS would fail for the original problem as if there exists a cycle then we cannot traverse over the cycle to increase the path length from source to destination.

I've written the code tweaking DFS which I think solves the problem for a DAG.

I've used the inputs from a similar example, and have also compared the code both of which are based on the same algorithm.

//Pseudocode below:

```
public void printPossiblePaths(int u, int v, int k, int count, Queue queue) {
    Add vertex u to queue;
    Mark u as visited;

    foreach vertex w adjacent to u {
        If w is not visited {
            If count equals k before reaching 'v', ignore this vertex;

            if (count==k) {
                Print the path followed using the elements in the queue;
                Remove last element from the queue;
                return;
            }
            // Recur with the source as the new vertex and the updated queue
            printPossiblePaths(w, v, k, count, queue);
        }
    }
    Mark u as unvisited;
}

```

Gist of the algo:

1) Do a depth first search from the source vertex counting the edges as you go to.

2) Once you have traversed the k-edges, check if the node if we've arrived at the 'v'th node, otherwise come out of that path and check for other paths.

3) Similarly, if we do see the 'v'th node after 'k' edges, print the queue and check for for all other possible paths.

**My question is : Is there a more efficient approach to achieve the same for a DAG or could we further tweak the code to handle cycles as well?**

# Answer
> 0 votes
I found the solution to this question. The idea is based on the following:

Consider an adjacency matrix A, where `A[i][j]` is 1 if there is an edge between i and j, and 0 otherwise.

Then, it can be proved that the number of paths of length k between i and j is just the `[i][j]` entry of `A^k`.

Thus the solution would be to build `A` and construct `A^k` using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.

The final complexity would simply be $O(V^3 logk)$

---
Tags: algorithms, graphs, counting
---


# Question
Title: Why are strings immutable in some languages?
String is an immutable class in Java. An immutable class is simply a class whose instances cannot be modified. Why does the Java programming language choose to make objects of class String immutable?

# Answer
This issue is strongly connected to the notion of what it means to be an instance of a class. In strict Object-Oriented terms, a class has an associated invariant: a predicate which always holds true on exit from a (public) method of the class. Such a notion is central in ensuring that inheritance is well-defined, for example (it's part of the Liskov Substitution Principle).

One of the most pernicious issues with Java is that it is difficult to prevent client code from breaking class invariants.

For example, consider the following 'ZipCode' class:

```
class ZipCode {
    private String zipCode;

    public ZipCode(String value){
        if(!isValidZipCode(value))
            throw new IllegalArgumentException();
        zipCode = value;
        assert(invariant());
    }

    public String get() { return zipCode; }

    public boolean invariant() {
        return isValidZipCode( zipCode );
    }
}

```

If String were not immutable, it would be possible for a user of ZipCode to call 'get' and change the characters at any subsequent time, thereby breaking the invariant and destroying the conceptual integrity offered by the encapsulation of the ZipCode concept.

Since this kind of integrity is essential to ensuring that large systems are valid, this answer to your question really begs the wider one of:

*"Why doesn't Java support an analog of C++ const, or at least offer immutable versions of more of it's library classes?"*
> 9 votes

# Answer
Things like strings and dates are naturally values. In C++ terms, we expect them to have a copy constructor, an assignment operator, and an equality operator, but we never expect to take their address. Hence, we don't expect them to be individually allocated on the heap. Virtual methods make no sense.

Domain objects are naturally references. C++ ones have no copy constructor, assignment operator, or equality operator (they are equal only if identical). We can take their address and we do expect them to be heap allocated. Methods are generally virtual.

Java has no value classes, only reference ones. Values are faked with immutable objects. This is true for strings, but not, unfortunately, for dates. The mutability of Java dates has caused frequent problems, and is now deprecated. Mutable values can't be used as a basis for a hash, for example.
> 7 votes

# Answer
Java was designed to allow execution of subsections of a program's code in security constrained environments. The way this requirement was implemented was by setting a "SecurityManager" on a thread that is given access to the parameters of certain critical operations (eg opening a file) and asked whether or not the operation should be allowed to go ahead. If Java Strings were mutable, a program could circumvent such restrictions by creating two threads, one which performed an open file operation that would be allowed while the other modified the string it stored the filename in to one that would not be allowed. There is then a possibility that the security manager would read the original string, accept the operation, which would be passed on to the file opening code which would then precede to open the second (not permitted) file. There are two possible ways of preventing this scenario:

* immutable strings
* performing defensive copying of any security critical string prior to checking its acceptability.

The latter possibility would make all such operations run more slowly and would be more likely for the implementation to contain bugs, so using immutable strings was the most sensible decision.

More generally, immutable objects are useful because they allow sharing without needing to make defensive copies (which may be necessary even in non-security-critical code to prevent bugs when the source data changes), so even without this requirement the decision would still be a reasonable one.
> 6 votes

---
Tags: programming-languages, language-design
---


# Question
Title: Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?
Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

An asynchronous multiplier is much bigger than an adder. It's about 18\*n^2 NOR gates where n is the number of bits. An adder is about 15\*n NOR gates. But for a 32-bits multiplication, a multiplier with successive additions will need 32 clock cycles, while an asynchronous mutliplier only 1. I think it's a big performance gain.

The same is for BCD to binary converter.

# Answer
> 3 votes
Last time I checked (more than 15 years ago), Wallace trees (and variants such as Dadda trees) were still the state of the art ($O(N^2)$ number of gates, but $O(\log N)$ latency; if you are naive in the way you do the additions, the latency may be $O(N)$).

Note that multipliers may be pipelined so you can still achieve a throughput of one multiplication per cycle but with a latency of more than one cycle if the latency of the multiplier is too big for your target clock rate.

# Answer
> 2 votes
Of course, it depends on the type of CPU. Primitive 8 bits CPUs had no multiplier (until the MC6809 which had a 8bits x 8bits multiplier :-).

Modern CPUs have both fast integer and floating point multipliers. The FP multipliers are replicated for "multimedia" SIMD instructions and there are also plenty of fast multipliers in the GPU.

Depending on the transistor budget, one may make a pipelined 1 cycle throughput double precision (53x53 bits) multiplier, or make only single precision 1 cycle and 2 or 3 cycles for double precision. Some GPUs still have this sorts of limitations.

In a modern FPU, the multiplier is often coupled with an adder and the mul/add operation can be done in 3/4 cycles, pipelined (so that a result can be obtained every cycle, as long as there is no data dependency). The core multiplication part lasts 1 cycle, while the other cycles are used for data algnment, conversion, rounding... There are many tricks for implementing multipliers using fewer gates than cascaded adders. Look for Booth encoding, Wallace trees... but it is more about EE than CS.

**About decimal**

x86 have some decimal parts, now obsoleted but still present. There are the AAA, AAS, AAD, AAM instructions, unavailable in 64bits mode, wich are helpers for BCD arithmetics. The FPU x87 instruction set has instructions to read/write decimal numbers from memory and convert on the fly to/from binary (internal registers are binary).

Some high end CPUs, notably IBM servers/mainframes, feature decimal FPUs specifically for financial operations with are officially based on decimal rounding and cannot be easily implemented exactly on binary FPUs.

# Answer
> 1 votes
I thought a 7/3 adder was 18 gates and you'd need less than 1000 of those for a full 64x64 multiplier. No big deal. And about 4 n^2.

There is absolutely no demand for BCD converters in hardware. Nothing that can't be done quicker with a lookup table.

---
Tags: circuits, cpu
---


# Question
Title: Variation of rank selection in genetic algorithm
I'm looking for a specific variation of rank selection in genetic algorithms.

I came across a python program tailored for a specific problem that uses a variant of "rank" selection. In normal rank selection, all individuals are sorted by fitness (in descending order) so that worst chromosome gets a weight of 1 and the best gets a weight of the population size. Then, usual roulette wheel selection is used based on those "weights".

In the case of that program, a slightly different variation of rank selection is used. Instead of relying on rouletted wheel selection after the chromosomes have beed sorted by rank, that program just pairs chromosome 1 with 2, 3 with 4, 5 with 6 and so on for crossover. Does that rank selection method have a particular name and/or can anyone pinpoint me to a link describing that variation. I googled it but haven't been able to find anything similar so far...

# Answer
For Differential Evolution (DE) there is the **Rank-Based Crossover Operator** that is quite similar.

It has been proposed in "A line up evolutionary algorithm for solving nonlinear constrained optimization problems" by Haralambos Sarimveis, Athanassios Nikolakopoulos (2005):

> The idea is to line up the solutions in each generation in a descending order according to the corresponding values of the objective function. The crossover and mutation operations are then applied to the solutions as follows: during the crossover operation, for each **adjacent pair** the difference vector is computed, weighted by a random number between 0 and 1 and added on the first vector of the pair. The produced solution replaces the first vector, if it produces an objective function value that is lower than the fitness value of the second vector. At the end of the crossover operation, the solutions are lined up again.

Of course DE has a peculiar crossover operator but the general idea of lining up individuals (rank based order) to choose crossover pairs is the same.
> 1 votes

---
Tags: algorithms, reference-request, genetic-algorithms, evolutionary-computing
---


# Question
Title: How to prove that sequences of stack operations are not context-free
By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...\\}$.

This language is not against **Pump lemma** of CFL, right ? But I read from some materials that this language is **NOT** context-free. So why is that ?

# Answer
The language *is* context-free. If we replace $\mathrm{push}(k)$ by $\[\_k$ and $\mathrm{pop}(k)$ by $\]\_k$ and delete the dots, then we get exactly all prefixes of a Dyck language with $N$ different types of brackets.
> 6 votes

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


# Question
Title: Why are these (lossless) compression methods of many similar png images ineffective?
I just came across the following thing: I put multiple identical copies of a png image into a folder and then tried to compress that folder with the following methods:

* `tar czf folder.tar.gz folder/`
* `tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz` (this one works well for identical images, however for similar images the gain is zero)
* `zip -r folder.zip folder/`

When I checked the size of the `.tar.gz`, `.tar.xz`, `.zip` I realized that it is almost the same as the one of `folder/`.
I understand that a png image itself may have a high level of compression and therefore cannot be compressed further. However when merging many similar (in this case even identical) png images to an archive and then compressing the archive I would expect the required size to decrease markedly. In the case of identical images I would expect a size of roughly the size of a single image.

# Answer
> 34 votes
Have a look at how compression algorithms work. At least those in the Lempel-Ziv family (`gzip` uses LZ77, `zip` apparently mostly does as well, and `xz` uses LZMA) compress somewhat *locally*: Similarities that lie far away from each other can not be identified.

The details differ between the methods, but the bottom line is that by the time the algorithm reaches the second image, it has already "forgotten" the beginning of the first. And so on.

You can try and manually change the parameters of the compression method; if window size (LZ77) resp. block/chunk size (later methods) are at least as large as two images, you will probably see further compression.

---

Note that the above only really applies if you have *identical* images or *almost* identical *uncompressed* images. If there are differences, *compressed* images may not look anything alike in memory. I don't know how the PNG compression works; you may want to check the hex representations of the images you have for shared substrings manually.

Also note that even with changed parameters and redundancy to exploit, you won't get down to the size of one image. Larger dictionaries mean larger code-word size, and even if two images are exactly identical you may have to encode the second one using multiple code-words (which point into the first).

# Answer
> 24 votes
**Why this happens.** There are actually *two* different effects happening here:

* **Each file compressed independently.** Some archive programs -- including zip -- compress each file independently, with no memory from one file to another file. In other words, each file is separately compressed, then the compressed files are concatenated into an archive.
* **Short-term memory.** Some archive programs can use information about one file to help compress the next file better. They effectively concatenate the files, then compress the result. This is an improvement.

See also Nayuki's answer for more discussion of this.

However, there's a second problem. Some compression schemes -- including zip, gzip, and bzip2 -- have a limited memory. They compress the data on-the-fly, and remember the past 32KB of data, but they don't remember anything about data that occurred much earlier in the file. In other words, they can't find duplicated data if the duplicates occur farther than 32KB apart. As a result, if the identical files are short (shorter than about 32KB), the compression algorithm can remove the duplicated data, but if the identical files are long, the compression algorithm gets hosed and becomes worthless: it can't detect any of the duplicate in your data. (Bzip remembers the past 900KB or so of data, instead of 32KB.)

All standard compression algorithms have *some* maximum memory size, beyond which they fail to detect patterns... but for some, this number is much larger than others. For Bzip, it's something like 900KB. For xz, it's something like 8MB (with default settings). For 7z, it's something like 2GB. 2GB is more than large enough to recognize the duplicated copies of PNG files (which are typically far smaller than 2GB). Additionally, 7z also tries to be clever about placing files that are likely to be similar to each other next to each other in the archive, to help the compressor work better; tar doesn't know anything about that.

See also Raphael's answer and Nayuki's answer for more explanation of this effect.

**How this applies to your setting.** For your specific example, you are working with PNG images. PNG images are themselves compressed, so you can think of each PNG file as basically a sequence of random-looking bytes, with no patterns or duplication within the file. There's nothing for a compressor to exploit, if it looks at a single PNG image. Thus, if you try to compress a single PNG file (or create a zip/tar/... archive containing just a single PNG file), you won't get any compression.

Now let's look at what happens if you try to store multiple copies of the same PNG file:

* **Small files.** If the PNG file is very small, then everything except for zip will work great. Zip will fail spectacularly: it compresses each file independently, so it has no chance to detect the redundancy/duplication among the files. Moreover, as it tries to compress each PNG file, it achieves no compression; the size of a zip archive will be huge. In contrast, the size of a tar archive (whether compressed with gzip, bzip2, or xz) and a 7z archive will be small, as it basically stores one copy of the file and then notices that the others are all identical -- they benefit from retaining memory from one file to another.
* **Large files.** If the PNG file is large, then only 7z works well. In particular, zip continues to fail spectacularly. Also, tar.zip and tar.bzip2 fail badly, as the size of the file is larger than the compressor's memory window: as the compressor sees the first copy of the file, it can't shrink it (since it has already been compressed); by the time it starts to see the beginning of the second copy of the file, it has already forgotten the byte sequences seen at the beginning of the first file and can't make the connection that this data is actually a duplicate.

In contrast, tar.xz and 7z continue to do great with multiple copies of a large PNG file. They don't have the "small memory size" limitation and are able to notice that the second copy of the file is identical to the first copy, so there's no need to store it a second time.

**What you can do about this.** Use 7z. It has a bunch of heuristics that will help detect identical or similar files and compress really well in that case. You can also look at lrzip with lzop compression.

**How do I know?** I was able to verify this by trying some experiments with 100 copies of a file containing random bytes. I tried 100 copies of a 4KB file, 100 copies of a 1MB file, and 100 copies of a 16MB file. Here's what I found:

```
Size of file      Size of compressed archive (with 100 copies)
                  zip  tar.gz  tar.bz2  tar.xz    7z
         4KB    414KB     8KB     10KB     5KB    5KB
         1MB    101MB   101MB    101MB     1MB    2MB
        16MB    1.6G    1.6GB    1.6GB   1.6GB  401MB

```

As you can see, zip is horrible no matter how small your file is. 7z and xz are both good if your images aren't too large (but xz will be fragile and dependent on the order in which images get placed in the archive, if you have some duplicates and some non-duplicates mixed together). 7z is pretty darn good, even for large files.

**References.** This is also explained well in a bunch of posts over at Super User. Take a look:

# Answer
> 12 votes
Firstly, note that the PNG image format is basically raw RGB pixels (with some light filtering) pushed through the DEFLATE compression format. Generally speaking, compressed files (PNG, JPEG, MP3, etc.) will see no benefit from being compressed again. So for practical intents, we can treat your PNG file as incompressible random data for the rest of the experiment.

Second, note that ZIP and gzip formats also use the DEFLATE codec. (This would explain why zipping versus gzipping a single file will produce essentially the same output size.)

---

Now allow me to comment on each test case individually:

* `tar czf folder.tar.gz folder/`

This creates a (uncompressed) TAR file that concatenates all your identical PNG files (with a tiny amount of metadata and padding added). Then this single file is sent through the gzip compressor to create one compressed output file.

Unfortunately, the DEFLATE format only supports an LZ77 dictionary window of 32768 bytes. So even though the TAR contains repetitive data, if your PNG file is greater than 32 KiB then for sure the DEFLATE compressor cannot remember data far enough back to take advantage of the fact that identical data is recurring.

On the other hand, if you retry this experiement with, say, a 20 KB PNG file duplicated 10 times, then it is very likely you will get a gzip file only slightly bigger than 20 KB.
* `tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz`

This creates a TAR file just like before, and then uses the xz format and LZMA/LZMA2 compressor. I couldn't find information about LZMA in this situation, but from 7-Zip for Windows I know it can support big dictionary window sizes (e.g. 64 MiB). So it is possible that you were using suboptimal settings, and that the LZMA codec might have been able to reduce the TAR file to just the size of one PNG file.
* `zip -r folder.zip folder/`

The ZIP format does not support "solid" archives; that is to say, every file is compressed independently. We assumed every file is incompressible. Hence the fact that every file is identical cannot be exploited, and the ZIP file will be as big as the straight concatenation of all the files.

# Answer
> 7 votes
The problem is, that (most) compression schemes lack the knowledge over the data you have. Even if you decompress your PNGs to bitmaps and compress them in the tarball, you would not get (significantly) smaller results.

In the case of many similar images, a appropriate compression scheme would be a video codec.

Using lossless coding you should achieve nearly the perfect compression result you are expecting.

If you want to test it, use something like this:

```
ffmpeg -i img%03d.png -c:v libx264 -c:v libx264 -profile:v high444 -crf 0 out.mp4

```

https://trac.ffmpeg.org/wiki/Create%20a%20video%20slideshow%20from%20images

# Answer
> 5 votes
PNG is the combination of Filters+LZ77+Huffman (the combination of LZ77+Huffman is called Deflate) in that order:

step 1) if the filter is different from None, the value of the pixels are replaced by the difference from the adjacent pixels (for more details see http://www.libpng.org/pub/png/book/chapter09.html) . That increases the compression of images with gradients (so ...4 5 6 7 becomes ...1 1 1 1) and it may help in areas of the same color (...3 3 3 5 5 5 5 5 becomes 0 0 0 2 0 0 0 0 0). By default filters are enabled in 24-bits images and disabled in 8-bits images with a palette.

step 2) the data is compressed with LZ77 that replaces repeated (matches) strings of bytes with a tuple containing the distance to the match and the length of the match.

step 3) the result of step 2 is encoded with Huffman code that replaces fixed-length symbols with variable-length codes, the more frequent the symbol the shorter the code.

There are multiple issues:

A small change that affects few pixels will result in changes in the results from the 3 steps of png compression:

1) The filtered value of adjacent pixels will change (depending on the filter used). That will amplify the effects of small changes.

2) The change will mean that matches to that area will be different. For example changing 333333 to 333533 causes that another occurrence of 333333 will not longer match so it will select another match to 333333 with a different distance or it will select the same match but with a shorter length and then another match for the last 3 bytes. By itself that will change the results a lot.

3) The largest issue is in step 3. The huffman code use a variable number of bits so even a small change will result in that everything that follows is not aligned any longer. AFAIK Most compression algorithms can't detect matches that are not byte aligned so that will prevent (or at least reduce a lot) compression on the already compressed data that follows the change unless the compressor can detect matches that are not byte aligned.

The other issues are already covered by other replies:

4) Gzip uses the same Deflate algorithm with a 32KB dictionary, so if the png files are larger than 32KB the matches will not be detected even if they are identical. Bzip2 is better in that aspect as it uses a 900 KB block. XZ uses LZMA, which IIRC has a 4 MB dictionary in the default compression level. 5) Zip format doesn't use solid compression so it will not compress similar or identical files any better.

Perhaps compressors from the PAQ or PPMD family will compress better but if you need to compress lots of similar image files then you can consider 3 approaches:

1) Store the images uncompressed (with PNG -0 or in a format without compression) and compress with a compressor with a large dictionary or block size. (LZMA will work well)

2) Another option would be keep the filters but remove the Deflate compression from the PNGs. That can be done for example with the (AdvDef) utility. Then you compress the resulting uncompressed PNGs. After decompression you can keep the uncompressed PNG or compress them again with AdvDef (but that will take time).

You need to test both approaches to see which compresses the most.

3) The last option would be converting the png images in a video, compress it with a lossless video compressor like x264 lossless (taking special care of using the right color format) and then on extraction extract the frames to individual png images. That can be done with ffmpeg. You also would need to keep the mapping between the frame number and the original name.

That would be the most complex approach but if the pngs are all part of a animation it may be the most effective. However you will need a video format that supports transparency if you need it.

Edit: There is also MNG format would it is not used often.

# Answer
> 2 votes
The PNG file format already uses the DEFLATE compression algorithm internally. This is the same algorithm as used by xz, gzip, and zip - just in some variations. `tar.gz` and and `tar.xz` take advantage of similarity between files, which `zip` does not.

So, in fact, you perform DEFLATE compression over DEFLATE compressed files - this is why the files keep almost the original size.

The `bzip2` program (also a related algorithm) is better when it comes to (nearly) identical files.

```
# for i in $(seq 4); do cp test.png test$i.png; done
# tar -cjf archive.tar.bz2 *.png
# ls -l
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test1.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test2.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test3.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test4.png
-rw-r--r-- 1 abcde users  68115 15. Jul 08:47 archive.tar.bz2

```

# Answer
> 2 votes
When you have special datasets you use special algorithms, not multipurpose tools.

The answer is that your chosen lossless compressions aren't made for what you do. Noone expects you to compress the same image twice, and even if you do it (by accident) checking against all previous input would make your algorithm O(n^2) (maybe a bit better, but the naiv approach atleast would be n^2).

Most of your compression programms you tested on run in O(n), they emphazise speed over optimal compression ratio. Noone wants to run his computer for 5 hours just to spare a few mb's, especially these days. For larger inputs anything above O(n) becomes an issue of runtime.

Another issue is ram. You can't access every part of your input at any point in time, when the input gets big enough. Even disregarding this, most people don't want to give up their whole ram or cpu just to compress something.

If you have patterns in your files that you want to compress, you will have to do manuel operations on them, write your own compression or potentially use an "archive"-type-compression (nano). A compression for longterm storage, that is too slow for everyday use.

Another option potentially would be a lossless video compression.

---
Tags: data-compression
---


title: Does a NFA/DFA need a failure state?

text:
# Question
Title: Does a NFA/DFA need a failure state?
I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here:

If I draw a NFA/DFA and I maybe don't need the transition from a state $z\_k \rightarrow z\_{k+1}$ with a $0$ above the alphabet $\Sigma = \\{0,1\\}^\*$ so I only need there a $1$, do I always need a failure state $z\_F$ so that $\delta: z\_k (0) \rightarrow z\_F $. Or can I omit that in the drawing? Or is there a difference between DFA and NFA, so that I need to write this failure function if its an NFA but I can omit it if it's an DFA? In my exercises my prof deducted one point because I had no failure state but just one or two times..

Hope somebody can help

# Answer
> 4 votes
A state in a DFA always needs to have exactly one transition per symbol in the alphabet. I have understood from a few of my classmates that some teachers omit the error-state. I however prefer to show the error-state in graphs, since it simplifies verification of determinism in a graph.

In a NFA there can be no such rule. Therefore it should work to not present a transition for the symbol (0) in this case. If the NFA would be determinized, this non existing transition, along with all other non-looping transitions would point to a error state.

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


# Question
Title: Is unrestricted grammar equivalent to deterministic Turing machine?
Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second rule and so on. Else, if match(es) is found, we return to first rule and start of the string and start loop again.
I have 3 questions:
1. Have anybody studied transformations with similar rules?
2. Which machine accepts language corresponding to such grammars and rules?
3. How one can alter described algorithm to make deterministic Turing machine such a corresponding machine?

# Answer
> 2 votes
Such a grammar system is Turing-complete. I can encode a tag system, and tag systems are known to be Turing-complete.

---
Tags: turing-machines, formal-grammars
---


# Question
Title: Finding a minimal width strip which encloses a set of points in the plane
*Problem*: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points?

*Definitions*: A strip is defined by two parallel lines and the vertical distance is defined as the distance between their intersection points with the $y$ axis.

*3 variables solution*: In the plane itself, this could be solved using a linear program of three variables, $m$, $a$ and $b$ where we look for $y=m\cdot x+a$ and $y=m\cdot x+b$.

*Duality*: If we move to the dual plane, we get a set on $n$ lines which can be transformed to $n$ upper half-planes or $n$ bottom half-planes. Denote $C\_1$ to be the intersection of all upper half-planes intersection and $C\_2$ of the bottom ones. The strip in the dual problem is represented by the two ends of the shortest vertical segment crossing the $C\_1$ and $C\_2$.

My question is - can we express the problem in the dual plane using a linear program of two variables?

# Answer
Take the convex hull of your set of points. Then use "rotating calipers" to find the optimal strip. What is needed here to make this work is a lemma that characterizes a potentially optimal solution: Could the optimum occur without one supporting line through two points ("flush" to the hull)?

*Added*. Yes, that flush-lemma holds, because more-horizontal strips are preferred. So: for each edge $e$ of the convex hull $H$, extend $e$ to a line $L\_1$, and let $L\_2$ be the parallel line supporting $H$ on the other side. Compute the vertical distance between $L\_1$ and $L\_2$. Select the shortest distance among all alternatives.
> 5 votes

---
Tags: computational-geometry, linear-programming, duality
---


# Question
Title: Can a simulation be conducted in which the inhabitants would observe infinite time divisibility?
In this video, a physics theorist talks with his collegues claiming to have found evidence for Simulation Theory. I'm not here to ask about the various proofs for and against ST - that's basically in the realm of philosophy at this point.

But one of the physicists claims that because of the nature of mathematics, it's impossible to simulate a particular aspect of our universe: **infinite divisibility of time.** The theorist responded that math *can* be used to *describe* infinite time division, which is all the simulation would need to do.

My question is this: In Computer Science, can we determine whether it is or is not possible through any currently known medium of computing to create a simulation in which the *inhabitants* would be able to observe infinite time divisibility?

Elaboration:

If you simulate things at a rate of infinite divisions per second of simulated time, you could never simulate the entire second right? The simulation would hang infinitely? The question is whether you could simulate based on something other than an interval, like in quantum physics, things (seem to) happen more or less precisely on a small level based on whether or not they're being observed (Disclaimer: that's a severe oversimplification).

Whether in CS this method of simulation (resulting in observed but perhaps not literal infinite time divisibility) is fundamentally possible via the computing formats we're aware of is my question. I think it's quite an interesting fundamental CS question.

Somehow the simulation would have to describe the occurrence of events via functions, not increments, which make it look like to an observer within the simulation that there is no smallest increment.

# Answer
> 3 votes
Yes, you can compute over continuous quantities. Calculus is an example.

If it was actually impossible to compute how a continuous system would behave, then how did this physicist end up believing reality is continuous? How did they make predictions that were confirmed by experiment, scientifically justifying their belief, if they weren't able to calculate any predictions?

---
Tags: computation-models, numerical-algorithms
---


# Question
Title: How to see how efficient a branch predictor is after designing one?
I want to design a branch predictor and then test it to see how efficient it is. The question is: how to test them? Are there data sets available?

# Answer
One standard way to evaluate a branch predictor is to implement it in a CPU simulator, and then execute standard benchmarks (e.g., the SPEC benchmark) and see what fraction of branches it has predicted correctly on taht workload.
> 1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Algorithm to find the first person in front of $A$ that is shorter than $A$
We have an array of $n$ positive integers $a\_0,a\_1\dots a\_{n-1}$ and let $a\_n=0$.

I need to build an array $b\_0,b\_1\dots b\_{n-1}$ such that $b\_i$ is the first integer larger than $i$ with $a\_{b\_i}\leq a\_i$. (Note that there is no requirement that the $b\_i$ be distinct.)

Does anybody know if this can be done in reasonable time? (say $\mathcal O(n\log n)$ for example)

# Answer
> 1 votes
There is an $O(n)$ solution for building such array using stack.

Starting with a brute force algorithm, you can traverse the array from right to left and for each element in the array, try all elements to the right of it until finding a smaller number. That would be $O(n^2)$.

To get an $O(n)$ solution, instead of each element having to look at all the elements to the right of it. We would just maintain a list of special elements by noticing that whenever a number at position $x$ sees a larger number to the right of it (at position $y$ where $y$ \> $x$), the larger number is of no use anymore.

To prove that, we can assume for contradiction that element at position y was the $b\_i$ of some future number. That means that $a\_y \< a\_i$ but since $a\_x \< a\_y \< a\_i$ and $x$ is between $i$ and $y$, then element $x$ would have been $b\_i$ instead. Hence, a contradiction.

The algorithm to get $b\_i$ would be to do the same as the brute force, but instead of just searching for a smaller element to the right, we will delete the larger elements that we meet on our way and break as soon as we find a smaller number. Simulating this efficiently can be done using a stack, where each $i$ keeps popping elements while the top of the stack is larger than $a\_i$. The top of the stack after the pops will be $b\_i$. $a\_i$ is then pushed to the stack so that it will be seen by the next elements.

## Complexity

The algorithm may still look as an $O(n^2)$ algorithm, but looking at the number of times that an array element is checked, we will find that each element is looked at for a constant number of times, since it is either pushed (once), popped (also once) or selected as $b\_i$ (total of n for all a $b\_i$). So the sum of operations is $O(n)$ for the algorithm.

---
Tags: algorithms, arrays
---


# Question
Title: why & how are BFS nodes goal tested when they are generated?
In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?

# Answer
The question makes sense as is and it, indeed, stands for a very important difference in how search algorithms are implemented.

Before moving further, let us refer to basic concepts that were certainly defined in your course material:

**Definition 1** \[*Generation of a node*\] A node $n$ is *generated* when a data structure representing its contents is created, i.e., when it is allocated in main memory.

**Definition 2** \[*Expansion of a node*\] A node $n$ is *expanded* when all its children are *generated*.

In general, all *brute-force* search algorithms (or *uninformed* as they are usually termed in modern literature) "goal test" nodes when they are generated. There is no reason to modify this decision as it suffices for preserving the main properties of search algorithms. Since you mention *Breadth-First* Search (BFS), let us review its main properties:

**Lemma 1** \[*Completeness* of BFS\] Breadth-First Search is *complete*, i.e., it is guaranteed to find a solution, provided that any exists.

The proof is very simple. It just suffices to observe that by storing nodes in a queue, nodes at depth $d$ are expanded only if all nodes at depth $(d-1)$ have been expanded. Conversely, nodes at depth $d$ *will surely be expanded*, immediately after all nodes at depth $(d-1)$ have been expanded. Hence, it does not matter where the solution node hides, it will be certainly found even if the graph is infinite (but not locally infinite, i.e., solutions might not be found if there are nodes with an infinite number of descendants).

**Lemma 2** \[*Admissibility* of BFS\] Breadth-First Search is *admissible*, i.e., it is guaranteed to find optimal solutions provided that any exist.

This is true if edge costs are neglected. Thus, cost of a solution path equals its depth. Since BFS only expands nodes at depth $d$ after expanding all nodes at the preceding depths, once a solution is found, it can be guaranteed to be optimal since we already tested all paths of shorter lengths (or, equivalently, costs).

There's the trick! If edge costs are neglected, then there is a correspondence between path cost and path length.

Now, what about searching in graphs with arbitrary costs? Best-First Search algorithms (termed also as BFS, but I will not to avoid confusion with the preceding algorithm) are devised to handle this case specifically. Dijkstra is one among many algorithms in the family of Best-First Search algorithms.

In this case (i.e., with arbitrary costs), there is not a correspondence anymore between path length and path cost. Hence, an algorithm can not stop once a goal has been generated if admissibility if desired (i.e., the property that guarantees that solutions found are also optimal). Instead, we keep on generating nodes and inserting them in ascending order of cost. This way, once a goal is about to be expanded (and only when it is about to be expanded!) we can certainly ensure that it is an optimal solution, because: (1) all the other nodes in open have a cost which is larger or equal; (2) path cost is assumed to grow monotonically (i.e., negative edge costs are not allowed).

As I said at the beginning, the stopping condition (whether to stop when the goal is generated, or when it is about to be expanded) is critical for the good behaviour of search algorithms. Indeed, many people believe that A$^\*$ (which is also a Best-First Search algorithm) with a null heuristic ($h(n)=0, \forall n$) is equivalent to Breadth-First Search. This is not true as there is a critical difference in the stopping condition.

For more details about this, I would recommend you to look at Robert C. Holte. Common Misconceptions Concerning Heuristic Search. Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS-2010), pp. 46-51 and, specifically, to page 49.

Hope this helps,
> 3 votes

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


# Question
Title: Does Damas-Milner still have principal types if existential type schemata are added?
In the Damas-Milner type system, type schemata can be formed in two ways:

* $T$
* $\forall X. S$

Where $T$ ranges over monotypes and $S$ ranges over type schemata. The type-checking algorithm for this system is well known, and explanations of it can be found in several places.

What happens if I add a third type schema former?

* $\exists X. S$

In other words, type schemata must still be in prenex normal form, but both universal and existential quantifiers may be used. As in Damas-Milner, only `let`-bound variables may be ascribed type schemata.

My questions are:

1. Does this system still have principal types?
2. How much does the type-checking algorithm change?

# Answer
Yes, adding existentials doesn't add many complications for type inference, if quantifier alternation is controlled carefully. This is not surprising since universals and existentials are dual and the the function space operator gives a form of negation. Small type annotations that can help regaining type-inference are discussed in (4).

Adding existentials to pragmatically viable programming languages was first discussed in N. Perry's dissertation (1). Perry's work was later formalised by Odersky and Läufer in (2). Läufer also described how to integrate existentials with Haskell type classes (3).

<sup> 1. N. Perry, The Implementation of Practical Functional Programming Languages.
2. K. Läufer, M. Odersky, Polymorphic type inference and abstract data types.
3. K. Läufer, Type classes with existential types.
4. M. Odersky, K. Läufer, Putting type annotations to work. </sup>
> 5 votes

---
Tags: type-theory, type-checking, type-inference
---