title: What does "map" mean?

text:
# Question
Title: What does "map" mean?
I have encountered the term many times, in various CS education materials:

1. L2 CS162 (UC Berkeley):

> Memory-mapped I/O
2. L4 CS162 (UC Berkeley):

> Memory mapped files
3. L24 CS61 (UC Berkeley):

> “Memory mapped I/O”: Device control/data registers mapped to CPU address space
4. Even, after googling "mapping", I got the article Map\_(higher-order\_function), but it wasn't very clear to me.
5. Even more, tried to understand the meaning in the context of `bitmap` by reading the Wikipedia article:

> A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}

I'm not sure, but in the context above it sounds to me about data conversion.
6. Later after reading a CS book, I found only this paragraph but it didn't explain the meaning of "mapping" for me:

> Memory Mapping Linux (along with other forms of Unix) initializes the contents of a virtual memory area by associating it with an object on disk, a process known as memory mapping.
7. I got also MapReduce as a search result: where map is explained as "an idiom in parallel computing where a simple operation is applied to all elements of a sequence, potentially in parallel".

I'm still confused about the term. Can anyone explain what does "map" mean in the contexts I mentioned?

# Answer
> 14 votes
So, there are two distinct uses of the word "map", that I'll unpack here.

1. The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to $2x$", then we're saying $\forall x \ldotp f(x) = 2x$.

This usage includes "memory mapped IO:" there is a (conceptual) function associating each piece of memory with a particular IO action. Nobody actually ever writes out the function, but it is indeed there: for each piece of mapped memory, there's some IO associated with it. Maybe a part of a disk, maybe a hardware register on a peripheral, etc.

Likewise, bit arrays (and arrays in general) fall into this: each index has a single element associated with it (at any given time), so an array is effectively an encoding of a finite-domain function.
2. In functional programming and derivatives (such as MapReduce), map refers to applying a transformation across a structure.

The original `map` comes from Lisp, where it referred to the function that took another function and a list, and returned the result of applying the function to each element of that list.

But, this phenomenon is quite general. In Haskell, a data structure that admits such an operation is called a *functor*, and the operation is called *fmap* (for historical reasons, to avoid conflicts with the list map).

These all are related through the concept of a Functor from category theory, which is an abstraction of structures admitting a "map" operation.

# Answer
> 8 votes
In the following I am going to be less than accurate in a number of ways, sacrificing technical accuracy to provide a basic understanding. It is obvious that you have read a number of technical sources and the very technicalness of the material is making it difficult for you to understand what is a fairly basic and simple concept.

In simple terms the most common use of the word map is to describe a relationship between the things in two different sets. This may be a mathematical function or it may be some other kind of representation and mechanism. The most common that comes immediately to mind is the street map.

A street map is a picture of a particular terrain or area in the real world in which the lines and drawings and words written on the map correspond to actual physical streets and buildings. There is a one to one relationship between the representation of the terrain that is pictured in the street map and the actual terrain.

Looking further we can also see that a street map is a representation of the actual terrain. The actual terrain has objects and details and dynamic processes which the street map does not depict. The street map is an abstract representation of the actual terrain and what is depicted in the street map is only what is needed to fulfill its purpose, to provide a navigational aid for the real terrain.

A number of the examples in the question involve creating a representation with supporting mechanisms so that a person can use the representation and the mechanism translates the person's actions into what is needed for the underlying functionality that is hidden by the facade of the representation.

Memory mapped file I/O allows a programmer to think of a file as a large area of memory, to use a memory representation of a real file. The programmer does not think of the file as a file but instead thinks of it as a large area of memory. The memory mapped file I/O functionality takes care to make sure that when the programmer references a particular memory offset that the corresponding data in the file is accessed.

Memory mapped device I/O allows a device programming interface to be simplified by writing to memory addresses or reading from memory addresses. These writing and reading actions are translated by the underlying memory mapped device I/O functionality into the actual device specific actions needed to carry out the requested service or action.

A bit map is a set of bits which provide a one to one correspondence to the values of some other set. For example the `CreateFile()` function of the Win32 API has several bit map arguments that are used to indicate different kinds of file attributes. Specific bits in a bit map correspond to a specific file behavior such as "Open as Read Only" or "Always Create New Empty File". Special constants are provided which are combined using binary bit operations to specify the actual arguments. See CreateFile function and the example source code at Opening a File for Reading or Writing.

# Answer
> 1 votes
Mapping is simply the process of associating one unit of data with another unit of data. The intent of mapping is to allow simplified access to the mapped data. For example, in classic IBM-compatible systems, the memory address 0xB8000 was mapped to the video memory of the video card. Writing to this memory would update the contents of the screen, and reading from it would retrieve the contents of the screen. File mapping, device mapping, and even data-structure mapping (typically called a Map, HashMap, or Dictionary), are all ways of associating one unit of data with another unit of data.

Mapping has two primary benefits. The first is that mapping reduces the complexity of accessing the associated device or file. For example, file mapping and device mapping allow you to treat those devices as if they were just plain memory. Instead of learning various I/O ports, data commands, and so on, you get one simple interface that is just as natural and obvious as writing to RAM.

The second benefit is that it can reduce memory requirements. For example, a `Map<Integer, SomeDataType>` can produce a "sparse array", which is useful where you want an array that will mostly contain invalid/unused data, and can be accessed in near-linear time. This can be far more efficient than a linked list (where it takes O(*n*) time to access the *n*-th element).

Mapping is primarily used as an abstraction to hide complicated algorithms/functions from the developer so they can focus on the task of implementing the program. Note that mapping may not always be as efficient, in terms of processing time, as accessing the device or file directly, but is always less complicated than doing so (e.g. the mapping reduces the amount of specialized code the developer must write to access the data).

---
Tags: data-structures, operating-systems, memory-management
---


# Question
Title: What are the differences between approximation of AIXI and deep reinforcement learning
AIXI is a theoretical formulation for artificial general intelligence. While AIXI is computationally intractable, there are approximations of AIXI like https://arxiv.org/abs/0909.0801 that are computable.

Some time ago, I stumbled upon theoretical artificial general intelligence, and I would like to know what are the practical differences between approximations of AIXI and deep reinforcement learning methods.

# Answer
> 1 votes
It's a bit of an apples and oranges comparison. AIXI is a proposal for how generalized learning should be structured, while neural networks are a specific learning implementation.

That being said, you probably *wouldn't* want to use an AIXI implementation for a known task such as game AI. Game AI is a specific learning task, so it's better and easier to use an AI specifically tailored to that task. The AlphaGo AI, for example, combined a deep learning neural network for finding interesting looking moves with a positional analysis engine for figuring out the strength of those moves. That sort of architecture works great for learning to play Go, but it's not general.

# Answer
> 0 votes
Deep reinforcement learning is reinforcement learning where you use a deep neural network as the memory component (in RL terminology the Q-function). More details can e.g. be found here: https://www.intelnervana.com/demystifying-deep-reinforcement-learning/

Concerning RL and AIXA: "The general reinforcement learning problem is to construct an agent that, over time, collects as much reward as possible from an initially unknown environment. The AIXI agent (Hutter 2005) is a formal, mathematical solution to the general reinforcement learning problem." Source: https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1722/2048

The problem is that AIXA is not computable so approximations of AIXA are necessary.

Putting it all together:
**Deep reinforcement learning is a particular implementation of an AIXA approximation.**

Personal note: I think it is no coincidence that the author of the abovementioned paper and several other papers in this area (Joel Veness) is now working for Google DeepMind...

---
Tags: artificial-intelligence
---


# Question
Title: Finding the shortest sublist that contains all search terms
I've been trying to get better at writing algorithms and came across a problem that was something like this:

Given a list of words:

```
search_list = ["this", "is", "an", "issue"]

```

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence:

```
given_list = ["this", "tv", "is", "an", "state", "node", "is", "this", "issue", "issue", "an"]

```

Given these two lists, the correct result would be `[6, 10]`, because the closest occurrences of the `search_list`, would start with the `"is"` at index 6, and finish with `"an"`, at index 10.

Having said that, here are more details:

## closest occurrences - definition

closest occurrence is the smallest subset of `given_list` in which all of the words occur. By "smallest subset", I simply mean the smallest absolute difference between the smallest occurring index, and the largest occurring index.

## allowed inputs

1) `search_list` \- a list or set of words that will only contain unique words. Again, no repeating words will be in this input parameter. This is the set of words that will be used to search given\_list to find the shortest/closest subset or occurrences of. 2) `given_list` \- a list or array of words that may contain duplicate words. This is the list that we need to find the smallest/closest subset of `search_list` in.

## expected output

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence.

Here is what I've tried so far: To start, I thought it'd be helpful to find all of the occurrences of each word.

```
def find_sub_list(search_list, given_list):
    result_list = []
    for value in search_list:
        inner_list = [i for i, val in enumerate(given_list) if val == value]
        result_list.append(inner_list)
    return result_list

```

Given the variables above, this would result in:

```
[[0, 7], [2, 6], [3, 10], [8, 9]]

```

From these results, the correct answer would be `[6, 10]`, because 4 is the shortest distance in which the words occur. However, I can't seem to find a better way to find the closest occurrences without checking every possible outcome. Is there a particular data structure that would make this process faster?

# Edit

To further define "closest occurrences", I'll give an example.

search\_list = \["one", "two", "three"\] given\_list = \["one", "black", "two", "blue", "three", "green", "two", "three"\]

The correct answer in this case would be \[0, 4\]. "two" and "three" occur at indices 6 and 7. However, "one" occurs at index 0, and "two" and "three"'s also occurs at 2 and 4. This subset with indices 0, 2, 4 is a smaller or closer subset than that of 0, 6, 7. Hopefully that makes more sense?

## Other notes:

* `search_list` cannot have repeating words. Items must be unique.

# Answer
> 1 votes
Go over the list, and maintain the last occurrence of each word in the search list. Whenever you find a word in the search list, find the minimum last occurrence among all other words in the search list - this gives you a candidate closest occurrence, which you take note of if it's the best seen so far. In the end, return the best closest occurrence observed.

To execute this algorithm efficiently, you need an efficient array-like data structure which supports the following operations:

* Change the value of item $i$.
* Return the minimum value of all items other than item $i$.

When the search list is very short, you can just use an array. For large search lists, you can probably use a modified heap to support all of these operations in $O(\log m)$ time, where $m$ is the size of the search list. The end result is an $O(n\log m)$ algorithm, where $n$ is the size of the main list.

# Answer
> 1 votes
Here's a simple algorithm.

1. For each word $w$ in `search_list`,
    1. find the left-most occurrence of $w$ in `given_list` and label all entries to the right with $\leftarrow\_w$, and
    2. find the right-most occurrence of $w$ in `given_list` and label all entries to the left of it with $\rightarrow\_w$.
2. Find the right-most entry $l$ that is labelled with all $\rightarrow\_w$.
3. Find the left-most entry $r$ that is labelled with all $\leftarrow\_w$.

You can implement the labels as bitmask; assuming you can manipulate bits and compare the whole masks in constant time, this algorithm runs in time $\Theta(mn)$, with $n$ and $m$ be the number of elements in the two lists.

---
Tags: algorithms, optimization, searching
---


title: INOI 2017 Problem 2 - Training

text:
# Question
Title: INOI 2017 Problem 2 - Training
INOI 2017, Problem 2, Training
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they travel they may increase his strength and experience value in a manner to be described below. In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The Gym-leader in ith city has experience E\[i\]. If Pikachu enters a city i with strength S and decides to train, then this increases his strength by the cube of the sum of the digits in his current strength.

For example, if he entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value XV by S\*E\[i\]. Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.

Input
The first line contains two space separated integers, N and Sin, which are the number of cities, and the initial strength, respectively.
The second line contains N space separated integers, which correspond to E\[1\], E\[2\],..., E\[N\].

Output
A single integer which is the maximum XV that Pikachu can attain. Constraints

For all test cases you may assume that: 1 ≤ N ≤ 5000 0 ≤ Sin ≤ 109 0 ≤ E\[i\] ≤ 104

Subtask 1: For 10% of the score, N ≤ 20 and Sin = 1
Subtask 2: For further 40% of the score, E\[i\] = k for all i i.e. E\[i\] is some constant k, for all i Subtask 3: For further 50% of the score, No further constraints.

============================================================================

I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated. Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/

# Answer
It's a 2d dynamic programming question.

Note that if Pikachu trains in a gym, his strength increases, and if he fights a leader his experiences increases.

Also note that his strength depends only on his strength and nothing else

Therefore, it is possible to have a separate array, s\[i\] which computes the value of Pikachu's strength, assuming that he's trained i times.

This can be done using a single loop calling a function to calculate his increase in strength

It's is also possible to have a another array, dp\[i\]\[j\], denoting pikachu's XP at the ith city, assuming that he's trained at j citites.

How would this work? It's easy -

dp\[i\]\[j\] = max(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\]+(s\[j\]\*e\[i\])

What this essentially does is takes the maximum value of pikachu training and pikachu fighting

If Pikachu trains, his XP won't increase, and he ends up training at 1 more gym. As a result, his xp would be the same as what it had been in the last city.

If pikachu fights, the number of gyms the number of gyms he's trained at remains the same(thus j doesn't change, while his a part of his xp would be the xp he had in the city before)

The next part, is essentially calculating whatevers been given to us in the question. It's E\[i\] as that's the E\[i\] is the ith value of the gym leader, as taken from the input and he's in the ith city

It's multiplied by s\[j\] as that's his total strength after training in j gyms

After this just find the maximum over all dp\[i\]\[j\]
> 0 votes

# Answer
Here is how I would approach it. Yes, dynamic programming is a way to solve this problem efficiently.

A few notations to note before hand :

1. prefix\[k\] = sum of all terms from 0 to k ( k included ).
2. best\[k\] = max possible XV till term k ( k included )

Algorithm :

```
 1. prefix[0] = A[i];
 2. best[0] = cubed sum A[i]

 for array A:
    // max ( m,n ) --> max of m and n.
    3. best[i] = max ( cubed sum (prefix[i-1] + A[i]), best[i-1] * A[i]);

 return best[n]. n --> size of array.

```

In other words, you choose the max value of either including the current strength into sum or by competing.
> 0 votes

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


title: Naive argument that P ≠ NP

text:
# Question
Title: Naive argument that P ≠ NP
Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario.

Let $f(x\_1,x\_2,\dots,x\_n)$ be a Boolean function in conjunctive normal form (CNF). The problem SAT is to determine whether there exists a $(x\_1,x\_2,\dots,x\_n) \in \\{0,1\\}^n$ such that $f(x\_1,x\_2,\dots,x\_n)=1$. Nothing is known a priori about the function $f$, so in general, in order to determine this information, it is necessary to plug in each $(x\_1,x\_2,\dots,x\_n) \in \\{0,1\\}^n$ into $f(x\_1,x\_2,\dots,x\_n)$ to test whether $f(x\_1,x\_2,\dots,x\_n)=1$, until one is found to satisfy $f$ or all are found not to satisfy $f$. There are $2^n$ possible $(x\_1,x\_2,\dots,x\_n) \in \\{0,1\\}^n$ to plug into $f(x\_1,x\_2,\dots,x\_n)$ to test. Therefore, any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. So $P \neq NP$. QED

What exactly is wrong with this argument? More importantly, are there any known counterexamples (algorithms that take $o(2^n)$ in the worst case scenario for SAT)?

Caveat: Note that there are known counterexamples if one restricts $f$ to being in 3CNF, but this is only because 3CNF has a special structure that plain CNF does not have. Plain CNF has no special structure at all, since any Boolean function can be placed in CNF.

# Answer
The error in your argument is the claim

> Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values.

, which is simply false. I will demonstrate why it isn't necessary to plug in all possible values and sketch how to arrive at an $O^\*((2^k-1)^{n/k})$ time algorithm, where $k$ is the number of clauses. $O^\*$ 'hides' poly-logarithmic factors, so for fixed $k$, this would be an $o(2^n)$ algorithm.

A key idea is this: If we wish to satisfy some clause of $m$ literals $l\_1 \vee l\_2 \vee \dots\vee l\_m$ by assigning truth-values, then there are $2^m-1$ ways to do this, as exactly one of the assignments does not satisfy the formula. This means we in fact do not have to test every assignment (for this clause).

Not doing a single test seems like a trivial improvement. However, by recursively applying the procedure to only check at most $2^k-1$ assignments, we get a running time $T(n)$ for which we have $T(n)= (2^{m\_i}-1)\cdot T(n-m\_i) + O^\*(n)$, where $m\_i$ is the number of elements of the $i$-th clause. So, $T(n) = (\Pi\_{i=1}^l (2^{m\_i}-1))T(0)+l\cdot O^\*(n)$, where $l$ is the number of clauses. This gives the result $T(n)=O^\*((2^k-1)^{n/k})$.

Of course, our improvement still yields a rather unpractical algorithm, but there are other tricks you can apply. To learn more, these slides by William Gasarch are a good read. (The title states 3-SAT, but most methods can be generalised to $k$-SAT)
> 12 votes

# Answer
The answer is simple, many times the naive impression is wrong, and one can find a more clever method to solve the problem.

This actually happens a lot in computer science. Clearly one cannot share secrets with an unfamiliar party in a public channel, however public key cryptography was developed. Obviously one cannot prove a theorem without revealing the ideas of the proof, well, zero knowledge proofs exist. Obviously in order to reduce the error of a randomized algorithm which uses $n$ coins from $p$ to $p^k$ one needs $nk$ coins, again, using a more sophisticated approach one can do better.

Even for general SAT there is no need to go over every assignment. If some partial assignment $g: S\rightarrow\\{0,1\\}$, where $S\subseteq\\{x\_1,...,x\_n\\}$ is some subset of variables, does not satisfy some clause, then you can tell immediately that every extension of $g$ will not satisfy the given CNF. Note that an $O\left(2^{(1-\epsilon)n}\right)$ algorithm would contradict the strong exponential time hypothesis, so you will not find such an algorithm in the current literature.
> 8 votes

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


# Question
Title: Is there any practical application for arrays that contain themselves?
I'm reading the introduction to Godel, Escher, Bach and and there's heavy discussion of mathematical sets which contain themselves. Being a far better programmer than mathematician, I put it into terms I'm more comfortable with and started to think about arrays which contain/reference themselves.

I know that recursion is a very powerful concept in CS but that it's typically manifested through *functions* which call themselves. I see recursive functions in algorithms all the time, but I've never before run across an array that has itself as an element. I was just wondering if there's any particular "usefulness" or practical application for *arrays* which contain themselves (as there is for functions which call themselves).

# Answer
> 4 votes
If you represent a (directed) graph in an adjacency "list" representation, i.e. each node has an array of (pointers to) its immediate successors, then any cyclic graph would arguably be an example of an array that "contains" (really references) itself. In practice, the "object graph" of references between the objects in a program will often be an example of this albeit not quite so cleanly

Indeed, for non-well-founded set theories with an anti-foundation axioms stating that sets *can* contain themselves, cyclic graph models are quite natural.

---
Tags: recursion
---


# Question
Title: Genetic Algorithm Getting Stuck on Certain Values
I'm attempting to teach myself something about genetic algorithms. I found a simple tutorial on it here, and it made enough sense that I was able implement the suggested example of generating a string of single digit numbers and simple arithmetic operators to total 42.

I then attempted the second suggested exercise described at the bottom of the page here. Basically, in a field of randomly placed circles of random size, write a genetic algorithm to find the largest non-overlapping circle you can place in the field.

I have something that seems to work, but I notice that it seems to get hung up on certain values. My "chromosomes" are composed of 3 pieces of data - x position, y position and radius. I'm using crossover and mutation to reproduce in the population. I then rank the results based on how large the resulting circle it is and whether it fits within the field and whether it overlaps other circles or not.

What I'm seeing is that there's a strong tendency for the radius to tend towards values that are just under a power of 2. For example, it will often get stuck bouncing around a radius of 31, 62, 124, etc.

I was trying to determine why this happens. My "genes" are all single precision floating point numbers. Crossover would cause some portion of the bits from one value to replace the corresponding bits of another value. Usually, this will result in the lowest precision bits of one value getting overwritten with those of another value. Occasionally it will cause part of or all of the exponent to get overwritten as well. Once you get a couple generations in, the values are largely of the same magnitude, so this often does very little. Mutation could flip any bit in the float, meaning it could turn a positive to negative 1/32nd of the time. It could change the exponent 7/32nds of the time, and the mantissa the remaining 3/4ths of the time.

Doubling the magnitude (by mutating or crossing over in the exponent, for example) is likely to have a positive effect up to a certain point. But once the generation contains mostly circles that are slightly over 1/2 the maximum value, they'll be less likely to grow by this method. Changes in the mantissa seem to have little effect overall.

My question - is this normal? This seems problematic when trying to generate better generations. I've let my simulation run for millions of generations, and haven't seen it get any better than the next-lowest power-of-2 for the radius. Have I just laid out my data in an unfortunate way, or does this problem come up often in genetic algorithms? Is there a way around it? I tried switching to a 16.16 fixed point representation and it got slightly better. The radiuses would get larger more frequently, but they still seem to hover around powers-of-2.

# Answer
As @Ray mentioned, the solution was to change how I encode the values. I encoded the positions and radius as floating point values initially. I switch from 32-bit IEEE-754 encoding to a 16.16 fixed point representation, since I didn't need more precision than that. I then converted from the fixed point representation to a 32-bit Gray code to store the genes. That allowed the simulations to converge on a solution much more quickly. It also seemed to help the mutations and crossover produce higher quality variations.
> 0 votes

---
Tags: simulation, floating-point, genetic-algorithms
---


# Question
Title: Why sequential access is faster than random access?
I am currently getting really confused of two documents I read:

one is from Wikipedia that states:

> The opposite is sequential access, where a remote element takes longer time to access.

and this Microsoft's document says:

> Accessing data sequentially is much faster than accessing it randomly because of the way in which the disk hardware works.

I found the two documents contradicting with each other. Maybe they refer to different things. But I would like to know why sequential access is much faster than random access (I don't understand the Microsoft document as I don't understand the concept of seek operation)

# Answer
> 6 votes
They are talking about two different things.

One is about a *medium* that supports sequential access versus random access. The other is about reading data that is arranged sequentially or spread out requiring random access for each chunk.

Imagine a deck of cards. If you had it in a stack, and I said to get the 39th card in the stack, you could take cards off the stack one at a time until you got to the 39th card. You need to skip past 38 cards to get to the 39th. Therefore, getting the 39th card is harder than getting the 3rd. This is like a sequential access medium.

Alternatively, let's say you spread out the cards around you in a circle in order. Now it takes just as much time for you to get any card as any other since you just reach in the appropriate direction. This is like a random access medium.

Sticking with the circle, let's say I asked for cards 1, 17, and 42. You can do this pretty quickly, but if I had asked for cards 1, 2, and 3, you could probably do it much more quickly since once you got the first card, you could just scoop up the next two cards all at once. This is the difference between reading sequentially organized data versus randomly organized data. Sequentially reading sequentially organized data is very easy with the stack organization of the deck too once you find the first card.

A seek operation is moving the reading head of the hard drive to a particular location. Once there the hard drive can (very) quickly read a sequential run of data. If all your data is all in a sequential run, then it can be read very quickly once the hard drive seeks to the beginning. If the data is spread all over the hard drive, then it has to seek after each portion, and while it's seeking it's not reading so you are wasting time.

In practice, hard drives (including solid state drives which don't have to "seek") assume that you probably want a bunch of data when you tell it to seek somewhere, so they just read in a bunch of data even if you haven't (yet) asked for it in the hope that you will ask for it in the near future. Other than needing space to store this pre-fetched data, there's no reason not to do this as it's essentially free. The read head is already there. This makes sequentially organized data perform even better and randomly organized data even more wasteful. Similar to this is the fact that there is usually a minimum "block" size of data that you can read and write at a time, and so you are going to get at least a block's worth of data no matter what. Sequentially organized data will fully utilize these blocks (until the last one perhaps). Randomly organized data may or may not depending on whether the "chunks" match some multiple of the block size.

---
Tags: memory-access
---


# Question
Title: What are some concrete (near-)"worst-case" examples of subset-sum?
I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.

However, I suspect it may be faster than existing solvers in "near-worst" cases, but I don't know how to check this.
What are some concrete examples of near-worst-case subset-sum problems I can try it on?

Note that I'm looking for reasonable examples here (\< 64 bits -- i.e., numbers that actually pop up in the real world), not, for example, an instance with 500 digits. I'm looking for reasonable examples here. The idea is that I'm trying to solve real-world subset-sum problems well in "hard" cases.

# Answer
The naive dynamic programming complexity is $O(sN)$ where $s$ is the integer bit precision, $N$ is the set cardinality. With some slight tricks in memoization cutting the precision constant in half, an instance with 64 bits precision should be solvable without much optimization in a linearly increasing fashion and as fast as memory access allows.

However, the naive method for small $s$ but large $N$ is dynamic programming which has subjectively large memory requirements. In practice this is the constraint that is prohibative for large instances skewed towards small precision, since many of the non-cryptographic applications I can think of deal with embedded systems having low memory and real-time constraints that limit non-uniform memory access.

At the other end of the spectrum if you have PiB subset-sum instances with small $s$ but very large $N$, the same issues arise as in sorting. These instances are incredibly 'easy' from a theory perspective but the micromanagement constant factor details dominate such as cache usage, memory walls, parallelization, bandwidth saturation, and code/data locality. Many of the techniques for fast solvers become invalidated at that size due to either reliance on a central memoization table or chaotic memory access.

The major applications for subset-sum that I know of are cryptographic in nature, which necessitates that the natural 'real-world' integer precision is far larger than 64 bits. In addition, most of the various manufacturing and finance applications do encounter the need for integer precision much larger than 64 bits as a way to actually encode the problem without blowing up $N$ in a very non-linear manner. This is required even though the original 'real-world' quantities are far less than 64 bits.

So hard subset-sum instances with 64 bit precision don't exist in the manner that I think you want to test. If an analogy helps, this is similar a complexity outcome to finding the prime factorization of a *very* large number but limited to prime factors with 64 bits of precision rather than the general case.
> 4 votes

# Answer
It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try.

The idea is to combine the following two tidbits:

1. We know some hard instances for 3SAT.
2. There is a reduction from 3SAT to SUBSET-SUM.

The hard instances for 3SAT are random instances at the correct clause density, which is just below the satisfiability threshold (4.2667). Applying the NP-hardness reduction that shows that SUBSET-SUM is NP-hard should result in hard instances for SUBSET-SUM.

Unfortunately, these instances are probably very large, so these instances might be too hard.
> 2 votes

# Answer
Not actually an answer to my own question, but if no one finds one, I think it would support what the author of this paper had to say, especially given that my own code was backtracking-based:

> The empirical results in \[Figure 4\] do not necessarily reflect worst-case analytical results. **Backtracking is better than DP for all problem instances**, even as the density of the problem instance is increasing. The worst-case analyses lead to the expectation that DP will be better than BT for high-density problem instances. **Apparently, the density never gets high enough to give DP the advantage.** Of course, we need to keep in mind that the empirical data from randomly generated instances is an illustration of average-case complexity, not worst-case complexity. While it is not known that average time complexity differs from worst-case time complexity for either backtracking or dynamic programming, it is known that many algorithms perform far better than worst-case for instances outside the critical region.

In other words, it seems that it's *hard* to find hard instances of subset-sum!
And I have no idea whether it's been done at all.
> 1 votes

# Answer
I'll share what I learned after reading many papers about the subset sum problem, I too implemented a solver and was looking time ago to understand what a 'hard instance' really is (in regards to this problem), and what I'm going to describe worked very well as a test bench for my solver, I personally never tackled the backtracking algorithm so you might need to reconcile this information with BT dynamics, but on the other hand, this way to build up instances are effective for both DP and the 'meet-in-the-middle' approach.

In relationship to subset sum problem, the existing literature, defines usually a hard instance as a random set of equally distributed values across the problem space with $density \approx 1$ (I found a paper settling, after some analysis that in fact the hardest instances have a $density \approx 1.03$ but is not a big of a difference form the practical point of view, that is what it looks you are interested)

Assuming $N$ being the number of elements and $P$ the number of bits for encoding the maximum possible value in your set, to achieve a $density \approx 1$ you must set the same value for $N$ and $P$ as $density=N/P$

For example, as you are constraining the integers resolution to no more than 64 bits, then, $N=P=64$.

Now you need to pick 64 uniquely random values equally distributed between $1..2^{64}$, trying to really equally distribute them (not clustering near-values). This will be your input set.

Then, you need to pick the target value, for this, you must select, again, randomly, unique values from your set, and add them until the sum is around the 50% of the problem space (problem space=the sum of all your values).

Why around 50%? Because if you pick a target value over 50% of the problem space, let's say 80%, by using DP, you can just build up the sums for the subsets and check for the 'negative' subset, as probably you can do with BT, so any target value deviating from the middle location is not that harder (because is near the beginning or the end, in the middle is equidistant, thus is the hardest of the locations for the target value)

However, in my opinion, the concept of 'hard instance' for a subset sum solver depends a lot on the solver implementation details, each solver can face problems with different parameters, e.g: DP can't handle a big $P$ because it blows up the memory need to hold the dynamic table in memory, even with very smart optimizations, the DP 'cost' depends on the target value, and in its worst case the target value for DP is a value around $2^{P-1}\*N$, so any change on $P$ or $N$ will impact the 'cost'.

If we look to the meet-in-the-middle, $P$ is not that important (if we don't consider memory), and $N$ is the real problem, when you get to larger sets, even with the smart split the 'cost' will increase exponentially.

So the bottom line is to know what variables impact your algorithm performance to be able to create proper hard instances for 'test benching'
> 1 votes

---
Tags: knapsack-problems, subset-sum
---


# Question
Title: How to compute (x MOD y) with just SUM and MULT gates?
It is known that $\\{ SUM, MULT \\}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates.

By the way, I could not come up with designing $MOD$ function with $SUM$- and $MULT$-only circuit. How can one construct such a circuit?

P.S. The Turing machine is simple. Assuming $\\#x\\#y\\#$ as the input, it suffices to go back and forth and cross $y$ of the remaining entries of $x$ as much as possible.

# Answer
> 4 votes
Turing machines and circuits are very different models of computation: Turing machines are a *uniform model* and circuits are a *non-uniform model*. Turing machines accept inputs of an arbitrary length, whereas circuits accept inputs of a fixed length. We can convert Turing machines to equivalent circuits in which the properties of the machine we started with are reflected. For example, a Turing machine running in polynomial time can be converted to a sequence of circuits of polynomial size.

If we have a sequence of circuits, one for each possible length of input, we can interpret the sequence as computing a function. As mentioned above, one way of generating such a sequence of circuits is from a Turing machine. Circuits which can be generated *by* a Turing machine, which accepts $n$ as input and outputs the circuit handling inputs of length $n$, are known as *uniform circuits*. (There are various more refined notions of uniformity, in which the Turing machine has some resource restrictions.) However, not all sequences of circuits arise in this way. For example, if $L$ is any length in which membership depends only on the length of the input, then $L$ can be computed by a sequence of circuits. However, $L$ need not even be computable. For example, consider the language of all inputs of length $n$ such that the $n$th Turing machine halts on the empty input.

You say that $\\{SUM,MULT\\}$ is Turing-complete, but there are a few problems with this statement. First, you seem to think of SUM and MULT as *gates*, which are components of circuits. As explained above, a model for circuits can't really be Turing-complete, though a set of gates can be complete in the sense that using it you can compute any function. Second, we usually (but not always) think of circuits as Boolean-valued. You haven't explained what the domain of SUM and MULT is, but I suspect that it is not $\\{0,1\\}$. In that case you have to explain exactly what circuit model you are interested in, and what notion of completeness you are interested in: while Boolean circuits can compute all functions $\\{0,1\\}^n \to \\{0,1\\}$, the same doesn't necessarily hold in other circuit models such as algebraic circuits.

---
Tags: circuits, turing-completeness
---


title: Solving $T(n)=4T(n/4) +(n/\log n)^2$

text:
# Question
Title: Solving $T(n)=4T(n/4) +(n/\log n)^2$
Solving $T(n)=4T(n/4) +(n/\log n)^2$.

When I looked at the question I thought that this can be solved by the 3rd case of the master theorem since $f(n)$ is polynomially larger than $n^{\log\_ba }=n.$ But someone said that this is not polynomially larger since it has $(\log n)^2$ in the denominator.

Then I tried the substitution method. I have found an upper bound of $n^2$ and a lower bound of $n\log n$ but I am unable to proceed any further.

I want a theta bound.

# Answer
> 1 votes
Let $H (m) := T(4^m)$. The recurrence is now $H(m) = 4 H(m-1) + 16^{m} / 4m^2$.

By substituting, we get

$4H(m-1) = 16 H(m-2) + 4\cdot16^{m-1} / 4(m-1)^2$

$16H(m-2) = 64 H(m-3) + 16\cdot16^{m-2} / 4(m-2)^2$

$64H(m-3) = 256 H(m-4) + 64\cdot16^{m-3} / 4(m-3)^2$

...

That sequence ends with $4^mH(0)$. So we need to add $16^{m} / 4m^2$, $4\cdot16^{m-1} / 4(m-1)^2$, $16\cdot16^{m-2} / 4(m-2)^2$, $64\cdot16^{m-3} / 4(m-3)^2$, ..., $4^mH(0)$.

We extract a factor $16^{m} / 4$, then the numbers to add are $1 / m^2$, $1 / 4(m-1)^2$, $1 / 16(m-2)^2$, $1 / 64(m-2)^2$ etc. The sum is slightly larger than $16^m / 3m^2$. And T(n) is slightly larger than $(4/3)(n / log n)^2$.

# Answer
> 1 votes
Case 3 of the master theorem does apply here. Let me state case 3 in its Wikipedia form.

> Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$ Let $c^\* = \log\_b a$. Suppose that:
>
> 1. There exists $\epsilon \> 0$ such that $f(n) = \Omega(n^{c^\* + \epsilon})$.
> 2. There exist $N\_0,k \> 0$ such that $af(n/b) \leq kf(n)$ for all $n \geq N\_0$.
>
> Then $T(n) = \Theta(f(n))$.

In your case, $a=b=4$ and $f(n) = n^2/\log^2 n$. Since $a=b$, $c^\* = 1$. Your function $f(n)$ satisfies $f(n) = \Omega(n^{1.5})$ (any number strictly between 1 and 2 would do here), and so satisfies the first condition with $\epsilon = 0.5$. As for the second condition, $$ af(n/b) = 4\frac{(n/4)^2}{(\log (n/4))^2} = \Theta\left(\frac{n^2}{\log^2 n}\right), $$ and in particular the second condition holds. The conclusion is that $T(n) = \Theta(f(n))$.

# Answer
> 0 votes
If you keep expanding using substitution, you'll sum the general term logn times. This will come out to be a geometric series and for a large n the sum directly tends to $4n^2/{3} \[1-1/(4^{(\log n)^2))}\]$ Which comes out to $n^2$ in terms of theta notation.

Working

General term:

$$ \frac {({\frac{n^2}{4^i}})}{(\log \frac{n} {4^i})} $$

This needs to be summed $k$ times, where $k$ is given by:

$$ \frac n {4^k} = 2$$ $k = \log n$

Sum this up $\log n$ times anad make some simple substitutions, you'll get $n^2.$ We can ignore the base case, because that'll simply contribute a term that will be lesser asympotitically than $n^2$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Reference book for Parallel Computing and Parallel algorithms.
Please suggest some books on Parallel Algorithms which teach efficient programming techniques like the ones taught in Udacity course(Introduction to Parallel Programming with CUDA). Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...? I wish to study more about such techniques which will make me an efficient parallel programmer...!

# Answer
> 9 votes
> Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...?

The History of Parallel Computing goes back far in the past, where the current interest in GPU computing was not yet predictable. Some important concepts date back to that time, with lots of theoretical activity between 1980 and 1990. Compared to the complicated trade-offs for current heterogenous systems, those old theoretical algorithms and concepts feel nice, powerful and easy to understand. Uzi Vishkin is a researcher who worked during that period, who still believes in those concepts (without overly compilicated trade-offs):

> Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future

I recently learned about those old concepts, and corresponding interesting survey articles:

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques (104 pages)
http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf
by Uzi Vishkin – October 12, 2010

A Survey of Parallel Algorithms for Shared-Memory Machines (70 pages)
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5865.html
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-408.pdf
by Richard M. Karp and Vijaya Ramachandran – March 1988

Limits to Parallel Computation: P-Completeness theory (327 pages)
https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf
by R Greenlaw, H Hoover, W Ruzzo – 1995

Parallel Algorithms (347 pages)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.466.8142&rep=rep1&type=pdf
by H Casanova, A Legrand, Y Robert – 2008

# Answer
> 3 votes
Programming Massively Parallel Processors is a good read. NVIDIA has also got some good tutorials. Amazon has got pretty good list.

---
Tags: reference-request, parallel-computing
---


# Question
Title: Approximating a series for asymptotic upper bound
So I stumbled upon a question here to find an asymptotic bound for the recurrence $$ T(n) = 4T(n/4) + \left( \frac {n} {\log n} \right)^2 $$

The solution shows a solution using master method to prove the answer as $O(n)$ However, I tried to solve it using substitution as:

$$T(\frac {n} {4^i}) = 4^{i+1} T(\frac {n} {4^{i+1}} ) + \sum\_{j=0}^{i} \frac {n^2} {4^j {(\log \frac{n}{4^j})^2} }$$

I then get $$ T(n) = 4^{x+1}(Base Constant) + \sum\_{j=0}^{logn -1} \frac {n^2} {4^j {(log \frac{n}{4^j})^2} }$$ $x=\log n$

Now for the summation: $$n^2\sum\_{j=0}^{\log n -1} \frac {1} {4^j {(log(n) - j\log (4))^2} }$$

All logarithms to be taken base 4: $n^2\sum\_{j=0}^{\log n -1} \frac {1} {4^j {(\log (n) - j)^2} }$

Now, the first substitution I made was $t = \log n -j $

$n^2\sum\_{j=1}^{\log n -1} \frac {4^t} {4^{\log n} {t^2} }$

= $n^2\sum\_{j=1}^{\log n -1} \frac {4^t} {n {t^2} }$ = $n\sum\_{j=1}^{\log n -1} \frac {4^t} { {t^2} }$

Using wolfram and wkipedia, the sum comes out to $Li2(4) -n Lerch Function(4,2,\log (n)-1)$

I could simple assume this is constant and that would prove my bound to be $O(n)$ as the master theore suggests, but I ahve no proof to bound the Lerch and dilogarithmic function.

Another substitution I tried was

$$ t=4^j (\log n -j)^2 $$ which gives me $$n^2 H(n) - H((\log n)^2) $$ where $H(n)$ is the nth harmonic number I again could not reach a bound for this, besides $\log (n) - \log (\log n) $ which is quite different from my first substitution.

If someone could help me with what error I'm making, or why the substitutions yield different results that would be great.

# Answer
> 0 votes
To make things a bit simpler, let us assume that we use base 4 logarithm. Following your steps, for $n = 4^k$ and $T(1) = 0$ we get $$ \begin{align\*} T(n) &= \frac{n^2}{(\log\_4 n)^2} + 4\frac{(n/4)^2}{(\log\_4 n-1)^2} + 16\frac{(n/16)^2}{(\log\_4 n - 2)^2} + \cdots \\ &= \frac{n^2}{(\log\_4 n)^2} \left\[ 1 + \frac{1}{4(1-1/\log\_4 n)^2} + \frac{1}{16(1-2/\log\_4 n)^2} + \cdots \right\]. \end{align\*} $$ Let us now use the series expansion $$ \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots. $$ Substituting this in the expression above, we get $$ \begin{align\*} \frac{T(n)}{n^2/\log^2\_4n} &= 1 + \frac{1}{4} + \frac{1}{16} + \cdots \\ &+ 2\left\[ \frac{1}{4\log\_4 n} + \frac{2}{16\log\_4 n} + \cdots \right\] \\ &+ 3 \left\[ \frac{1}{4\log\_4^2n} + \frac{2^2}{16\log\_4^2n} + \cdots \right\] + \cdots \\ &\approx \frac{4}{3} + \frac{8/9}{\log\_4 n} + \frac{20/9}{\log\_4^2 n} + \cdots \end{align\*} $$ The error in the approximation is polynomially small: for example $$ \sum\_{k=0}^{\log\_4 n-1} \frac{1}{4^k} = \frac{4}{3} - \frac{4/3}{4^{\log\_4 n}} = \frac{4}{3} - \frac{4/3}{n}. $$ The error is somewhat larger for the other summands, but still polynomially small. Taylor's theorem (or direct calculation) shows that if we truncate the series for $1/(1-x)^2$ after the term $(d+1)x^d$ then we get an error of $O(x^{d+1})$. Altogether, this shows that the following asymptotic statements hold: $$ \begin{align\*} T(n) &= \frac{4}{3} \frac{n^2}{\log\_4^2 n} + O\left(\frac{n^2}{\log\_4^3 n}\right), \\ T(n) &= \frac{4}{3} \frac{n^2}{\log\_4^2 n} + \frac{8}{9} \frac{n^2}{\log\_4^3 n} + O\left(\frac{n^2}{\log\_4^4 n}\right), \\ T(n) &= \frac{4}{3} \frac{n^2}{\log\_4^2 n} + \frac{8}{9} \frac{n^2}{\log\_4^3 n} + \frac{20}{9} \frac{n^2}{\log\_4^4 n} + O\left(\frac{n^2}{\log\_4^5 n}\right), \ldots \\ \end{align\*} $$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Regularization term moving the hyperbolic plane
When we train a network, we usually have an error function which usually looks like this:

$$Error = (output - target)^2$$

When we add a regularization term, it looks something like this:

$$Error = (output - target)^2 + reg term$$

I understand that there are many different ways of defining the reg term, but in this example, we can make it the sum of all weights.

When we do this, are we just not moving the hyperbolic plane up and down? The slope of it should stay the same everywhere and thus not really make a difference in finding a minimum of the error function.

# Answer
The point of the regularization term is usually to keep the network from overfitting by keeping the weights vector with low absolute values or sparse. Therefore I would say a sum of all weights is not a good regularization term, because even extreme positive and negative weights can sum to zero. In the regularization term, the $L\_2$, $L\_1$, $L\_0$ norms are commonly used (read about it here).

In a side note, if I understood you correctly, I would suggest to avoid imagining the target function (or loss function) as a hyperbolic plane, since usually DNNs contain non linear activation functions like ReLU.
> 3 votes

# Answer
Regularization terms should increase with model complexity, cost, or other undesirable factors. Then when the model's optimized, the optimizer is forced to consider the trade-off between getting a better fit and avoiding additional complexity/cost/etc..

For example, imagine that you're doing a multi-linear regression with 20 different independent variables. Often, you can remove one independent variable without hurting the overall $R^2$ value of the correlation much. If you don't use regularization of some sort, the optimizer would still include all of the independent variables anyway just to get the best fit. But if you penalize the model for using more data, then the optimizer may start to zero-out independent variables that didn't really help.

With neural networks, regularization terms often penalize for increased weights. This is because weights of $0$ effectively remove neural connections, resulting in a simpler model.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Clustered Regions by Each Neuron in Self Organizing Map (SOM)
I was given a question about SOM.

There is a SOM which have 4x4 neurons and each neuron's x1 and x2 values (coordinates) given. Also neighborhood function and weight update rule given. How can i find and show the regions which are clustered by each neuron?

Thanks for answers.

Regards...

# Answer
When clustering an input, one should calculate the Euclidean distance to all neurons, then the input is assign to the cluster of the nearest neuron.

In other words, for an input $v$ and a set of neurons $N$ (in your case $|N| = 16$ ) the cluster is:

$\text{Cluster}(v)=\arg \min\_{i\in A}(||w\_i-v||\_2)$
> 1 votes

---
Tags: machine-learning, neural-networks
---


title: Two's complement addition

text:
# Question
Title: Two's complement addition
I am currently learning about a CPU's status register and was confused about the difference between the carry flag and the overflow flag. Then I found article \[1\] which explains it very well, but I stumbled across one paragraph I don't really understand:

> The rules for two's complement detect errors by examining the sign of the result. A negative and positive added together cannot be wrong, because the sum is between the addends. Since both of the addends fit within the allowable range of numbers, and their sum is between them, it must fit as well. Mixed-sign addition never turns on the overflow flag.

Let's look at 1111 and 0111. Both are valid 4-bit two's component values with a different sign. If I add them, I the carry-flag is turned on because the result of this addition is a 5-bit value.

The author says that errors in twos complement calculations can be found just by looking at the overflow bit. The overflow bit in this example would not get turned on, but in my opinion, this is an error. Why does the author claim this then? Why does the author tell the reader multiple times to ignore the carry bit when doing twos complement calculations?

\[1\] http://teaching.idallen.com/dat2343/10f/notes/040\_overflow.txt

# Answer
> 4 votes
If you perform the addition, you get 1111+0111 = 0110 (ignoring the carry bit). In decimal, this reads $-1 + 7 = 6$, which is indeed correct. There is no error.

You can check that when adding a positive number and a negative number, if the result is non-negative then there will always be carry, which can be safely ignored.

# Answer
> 4 votes
Your confusion is treating overflow and carry as the same thing. In reality $$ \text{carry} \ne \text{overflow}$$

The overflow flag is turned on when there is an incorrect "sign" flip, i.e., when the addition of two positive numbers yields a negative number (one whose MSB is on; ignoring the carry-bit which is not part of the register) or when the addition of two negative numbers yield a positive one. This has nothing to do with the carry bit which is the bit beyond the MSB of the register.

It is not difficult to think of situations in which the carry bit is 1 while overflow is 0, or vice versa.

Once you understand this difference, re-read the reference and it should make better sense.

---
Tags: arithmetic, cpu
---


title: Minimum weight k-induced subgraph

text:
# Question
Title: Minimum weight k-induced subgraph
Let $G$ be *multipartite* directed weighted graph with $k$ independent sets (we will call them "layers"). We select *exactly* one node from each layer and form the induced subgraph $H\_k$. That is, $H\_k$ has exactly $k$ nodes (one from each layer) and contains all edges from $G$ that have both endpoints in $H\_k$.

Our goal is to find $H\_k$ such that the total weight of all of its edges is *minimized*: $$\min\_{H\_k \subset G}\sum\_{e \in H\_k} weight(e)$$

(you can assume that the graph is connected, so a solution always exists)

---

### Case #1: Graph is flat

To better illustrate the problem I will give some examples. Consider a special case where all edges in $G$ are from layer $i$ to layer $i+1$:

This problem can be easily solved, by adding 2 new nodes **entry** and **exit** to $G$. Then we add edges with $0$ weight from *entry* to *every* node in layer #1 and from *every* node in layer #$k$ to *exit*. Finally the solution to our problem is the **shortest path** from *entry* to *exit*.

In our example, the minimum weight 4-induced subgraph will be: $A\_3, B\_1, C\_1, D\_1$, with total weight $20$.

---

### Case #2: Graph has backward edges

In this case, we allow a layer to have *backward edges*; that is, a layer $i$ can have edges to any layer $j$ as long as $i \ne j$. For instance, consider the graph from the previous example, but this time add some backward edges (with blue color):

Unfortunately, the previous approach does not work anymore, as the previous approach will give us the same solution $A\_3, B\_1, C\_1, D\_1$ with a total weight of $70$, but the minimum subgraph is $A\_3, B\_2, C\_1, D\_2$ with total weight $34$

---

### Case #3: Re-define the problem

Clearly, the introduction of "layers" can make the analysis hard. So, we can redefine the problem without requiring $G$ to be multipartite. That is, instead of having layers, we add an edge with $\infty$ weight between every pair on the same layer. Then the minimum weight k-induced subgraph $H\_k$, cannot have two nodes from the same layer, as this would imply that $H\_k$ contains an edge with $\infty$ weight. Back in our example, the previous graph becomes:

---

## The case #3 is NP-hard

Unfortunately in the general case **this problem is NP-hard** (because it is an optimization problem), as there is a reduction from *k-clique*:

Let $R$ be an undirected unweighted graph that we want to check whether it has a $k$-clique. That is, we want to check whether $clique(R,k)$ is **True** or not. Thus, we create a new directed graph $R\space'$ as follows:

* $R\space'$ contains all the nodes from $R$
* $\forall$ edge $(u,v)\in R$, we add the edges $(u,v)$ and $(v,u)$ in $R\space'$ with $weight = 1$
* $\forall$ edge $(u,v)\notin R$, we add the edges $(u,v)$ and $(v,u)$ in $R\space'$ with $weight = \infty$

Then we find the *minimum weight k-induced subgraph* $H\_k$ in $R'$. It is true that:

$$\sum\_{e \in H\_k} weight(e) \< \infty \Leftrightarrow clique(R,k) = True$$ $:\Rightarrow$ If the total edge weight of $H\_k$ is not $\infty$, this implies that for every pair of nodes in $H\_k$, there is an edge with weight $1$ in $R\space'$ and thus an edge in $R$. This by definition means that the nodes of $H\_k$ form a k-clique in $R$. Otherwise (the total edge weight of $H\_k$ is $\infty$) it means that it does not exist a set of $k$ nodes in $R\space'$ that has all edge weights $\< \infty$.

$:\Leftarrow$ If $R$ has a k-clique, then there will be a set of $k$ nodes that are fully connected. This set of nodes will have no edge with $\infty$ weight in $R\space'$. Thus, these nodes will form an *induced subgraph* of $R\space'$ and the total weight will be smaller than $\infty$.

*(proof is not formal; I just describe the general idea)*

---

## The Question

Although the problem that I described is **NP-hard** (assuming that my analysis is correct), I want to find an approximation algorithm (along with a proof) that can give me a solution that is at most $n$ times worse than optimal (obviously we want $n$ to be as small as possible).

There is also a paper that solves a similar problem, but I don not know if that helps.

# Answer
> 2 votes
The problem cannot be approximated. Consider the reduction that you described from k-clique to your problem but this time assign zero weight to the original edges. Any (multiplicative) approximation algorithm also solves the k-clique problem this is because it must return 0 if there is a k-clique.

---
Tags: np-hard, approximation
---


title: Ordered Cartesian Product

text:
# Question
Title: Ordered Cartesian Product
Say I have three sets:

```
A = [banana, apple, grape]

B = [1, 2, 3, 4]

C = [Alice, Bob, Carol]

```

I need to design an algorithm that gives me the Cartesian Product A x B x C, but with any number of sets and any number of elements in each set. Another requirement is that the order of the elements in the Product is such:

```
A x B x C = [(banana, 1, Alice),
             (apple, 1, Alice),
             (banana, 2, Alice),
             (banana, 1, Bob),
              ...]

```

I could only come up with a recursive algorithm that ends up giving me:

```
A x B x C = [(banana, 1, Alice),
             (banana, 1, Bob),
             (banana, 1, Carol),
             (banana, 2, Alice),
              ...]

```

Obviously, A x B x C needs to have every possible combination of the elements of the sets. Also, I need an algorithm that covers the general case of any number of sets, not only three. Is there any well-known algorithm that provides the Cartesian Product in this order that I need?

Any help or tips is much appreciated.

# Answer
You want to enumerate first by sum, then by lexicographic order of some sort (it's impossible to tell which type exactly from your example). Replacing actual elements with indices, here is the order you're interested in for $A \times B$: $$ (0,0) \\ (1,0), (0,1) \\ (2,0), (1,1), (0,2) \\ \ldots $$ It's a simple exercise to generate this order for $A \times B$. Generating the order for $A \times B$ is somewhat more challenging, but still not too bad. When generating the triples summing to $n$, if we focus on just the first two parts of each pair, then we're interested in a list of all pairs $(i,j)$ such that $i+j \leq n$, in some sort of lexicographic order. Whichever variant of the lexicographic order you choose, you should be able to figure out how to generate it by looking at some examples.
> 1 votes

# Answer
If anyone is interested, I was finally able to figure this out. Many thanks to Yuval Filmus for his answer, without it I wouldn't be able to achieve this!

This is my code in Go. Most variables and comments are in portuguese (sorry!), and organization is not perfect, but works!

```
package main

import (
    "fmt"
)

func main() {

    // inicializa os arrays
    var frutas = []string{"banana", "maçã", "uva"}
    var nums = []string{"1", "2", "3", "4"}
    var nomes = []string{"wesley", "rodrigo", "igor", "regina", "marcos", "bernardo"}

    arrays := [][]string{frutas, nums, nomes}

    nMax, indicesOrdenados := indicesOrdenados(frutas, nums, nomes)

    for n := 0; n < nMax; n++{
        l := len(indicesOrdenados[n])

        for k := 0; k < l; k++{
            indices := indicesOrdenados[n][k]

            palpite := ""
            for i, indice := range indices{
                palpite += arrays[i][indice]
            }
            fmt.Println(palpite)
        }
    }
}

func indicesOrdenados(arrays ...[]string) (int, [][][]int){

    nMax := 0
    tamanhos := make([]int, 0)
    for _, array := range arrays{
        nMax += len(array) - 1
        tamanhos = append(tamanhos, len(array))
    }
    nMax++

    // inicializa canal com arrays do produto cartesiano dos indices
    produtoCartesiano := produtoCartesiano(tamanhos)

    // inicializa saida
    saida := make([][][]int, nMax)

    for elemento := range produtoCartesiano{
        soma := 0
        for _, i := range elemento{
            soma += i
        }

        saida[soma] = append(saida[soma], elemento)
    }

    return nMax, saida
}

// gera canal com arrays do produto cartesiano dos indices
func produtoCartesiano(tamanhos []int) chan []int{
    // inicializa canal de saída
    saida := make(chan []int)

    // lança gorrotina recursiva
    go recursao(tamanhos, nil, 0, saida)

    // retorna canal de saída
    return saida
}

// lança os valores do produto cartesiano dos arrays no canal de saída
func recursao(tamanhos []int, contadores []int, profundidade int, saida chan []int){
    // profundidade máxima a ser processada recursivamente
    pMax := len(tamanhos)

    // primeiro nível de recursão... inicializa contadores e tamanhos
    if profundidade == 0{

        // inicializa contadores (todos 0)
        contadores = make([]int, pMax)
    }

    // último nível de profundidade na recursão
    if profundidade == pMax {

        //inicializa array resultado
        resultado := make([]int, 0)
        for p := 0; p < pMax; p++{
            i := contadores[p]
            resultado = append(resultado, i)
        }

        // envia elemento no canal de saída
        saida <- resultado

        // qualquer outra profundidade que não seja a última
    }else{
        // varre array da profundidade atual
        for contadores[profundidade] = 0; contadores[profundidade] < tamanhos[profundidade]; contadores[profundidade]++{
            // processa próxima profundidade recursivamente
            recursao(tamanhos, contadores, profundidade+1, saida)
        }
    }

    // hora de fechar canal?
    // analisa contadores de todos arrays... se todos forem iguais aos respectivos tamanhos,
    // então todos elementos do produto cartesiano foram calculados, e o canal pode ser fechado
    fecha := true
    for i := 0; i < pMax; i++{
        if contadores[i] != tamanhos[i]{
            fecha = false
        }
    }

    // fecha canal
    if fecha{
        close(saida)
    }
}

```

This is the output, which is exactly what I needed:

```
banana1wesley
banana1rodrigo
banana2wesley
maçã1wesley
banana1igor
banana2rodrigo
banana3wesley
maçã1rodrigo
maçã2wesley
uva1wesley
banana1regina
banana2igor
banana3rodrigo
banana4wesley
maçã1igor
maçã2rodrigo
maçã3wesley
uva1rodrigo
uva2wesley
banana1marcos
banana2regina
banana3igor
banana4rodrigo
maçã1regina
maçã2igor
maçã3rodrigo
maçã4wesley
uva1igor
uva2rodrigo
uva3wesley
banana1bernardo
banana2marcos
banana3regina
banana4igor
maçã1marcos
maçã2regina
maçã3igor
maçã4rodrigo
uva1regina
uva2igor
uva3rodrigo
uva4wesley
banana2bernardo
banana3marcos
banana4regina
maçã1bernardo
maçã2marcos
maçã3regina
maçã4igor
uva1marcos
uva2regina
uva3igor
uva4rodrigo
banana3bernardo
banana4marcos
maçã2bernardo
maçã3marcos
maçã4regina
uva1bernardo
uva2marcos
uva3regina
uva4igor
banana4bernardo
maçã3bernardo
maçã4marcos
uva2bernardo
uva3marcos
uva4regina
maçã4bernardo
uva3bernardo
uva4marcos
uva4bernardo

```
> 0 votes

---
Tags: algorithms, word-combinatorics
---


# Question
Title: Why models of computation are primarily focused on machines?
It seems a lot of courses (like this and this) on theory/models of computation (and even formal languages) cover DFA, NDFA, PDA, and TM in the order of increasing computational power. This of course makes sense, but why aren't various other computation models included in general? For example, we could take the route from untyped lambda calculus to simply typed lambda calculus and so on with decreasing expressiveness. (I know they are detailed in PLT, but aren't they models of computation as well?)

In brief, since all the above (and a lot more) count as different models of computation with different powers, is there any specific reason, historical or else, that the machine-like models are adopted, sometimes even exclusively?

# Answer
I suspect that there are two reasons:

* **Historical reasons.** This is how we've always done it. Academia can be slow to change. Also, machines provide a platform for studying concepts like the power of non-determinism. We don't know how to fully understand the power of non-determinism when considering realistic models of computation (for instance, we haven't resolved the P vs NP question), but when we look at more limited models of computation, it's possible to fully work out the power of nondeterminism. So, this gives us a platform for understanding some interesting concepts about computation.
* **Pragmatic reasons.** DFAs, NDFAs, and PDAs are useful and important to understand if you want to build a lexer or parser, so they're very useful when building compilers. A few decades ago, this was a powerful motivation for studying the subject: here is a practical need (how do we structure the front-end of a compiler?) and one where there is some beautiful theory that is directly applicable. Thus, such a course might gain support both from theoreticians who are most interested in the theory, and from compilers folks who are motivated by practical concerns. It's not clear that this is still the most important thing for students to learn these days -- today, how many students are ever going to need to write a lexer or parser for a compiler? -- but academic courses are slow to change.

I'm not trying to argue this is the only reasonable way to do it. A course on variants of the lambda calculus might be quite interesting, too. But I suspect these factors might partly explain why such courses are common.
> 5 votes

---
Tags: turing-machines, lambda-calculus, computation-models
---


# Question
Title: reducing the halting problem to the blank tape problem
I have checked many discussions for understanding this problem.

I understand the reasoning , unfortunately there are some drawback in my understanding.

**The Blank-tape halting Problem**

**Input**: Turing Machine M

**Question** : Does M halt when started with a blank tape?

So this is the reduction :

The construction of Mw is as follows :

* When started on blank tape, writes w
* Then continues execution like M

What i don't undesstand is the step 2 , in my opinion if we execute M on w maybe M will loop !!!

My second question : what the blank-tape do when executed?even if the blanktape machine halt on blank tape , how can we be sure that M halt on w .i miss something here.

Thank you in advance.

# Answer
> 1 votes
The Blank-tape Halting problem, given a Turing machine $\langle M \rangle$, asks whether or not $M$ eventually halts when starts from the empty tape, i.e, its input is the empty string.

It is a decision problem that returns "YES" or "NO". Thus the decider for the Blank-tape Halting problem is another Turing machine $M\_{D}$ that takes as input a Turing machine $\langle M \rangle$ (its description) and returns "YES" or "NO" (prints "YES" or "NO" and halts).

Reducing the Halting problem to the Blank-tape Halting problem means that the we should construct a decider for the Halting problem using the decider for the Blank-tape Halting problem. We could construct it as following.

```
HP-decider(M,w)
  1) generate a TM M' which starts from the empty tape
     then writes w on its tape and runs on w
  2) result = BTHP-decider(M')
  3) if result == "YES" then return YES
  4) if result == "NO" then return NO
end

```

It is not hard to see that $M'$ halts iff $M(w)$ halts.

In fact you don't need to simulate $M$ on $w$. You don't care about how `BTHP-decider(M')` works/decides either. What you must show is that the Halting problem is solvable using the Blank-tape Halting problem.

# Answer
> 1 votes
The reduction does not actually execute $M$, what its actually doing is the following mapping:

$\big(\langle M\rangle,w\big)\mapsto \langle M\_w\rangle$

Where $M\_w$ is the machine that when executed with blank tape, simulates the machine $M$ on input $w$. Preforming the reduction does not require that you execute $M$, you simply need to write down the code of $M\_w$. Obviously $M$ halts on $w$ iff $M\_w$ halts when executed with blank tape (we constructed $M\_w$ specifically for this purpose), and the correctness of the reduction follows.

---
Tags: complexity-theory, reductions, halting-problem
---


title: Cache efficient matrix multiplication

text:
# Question
Title: Cache efficient matrix multiplication
Consider these matrices:

$A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$

$B=\begin{bmatrix}-1 & -2\\\-3 & -4\end{bmatrix}$

**Using standard algorithm:**

$C=\begin{bmatrix}1\*-1+2\*-3 & 1\*-2+2\*-4\\3\*-1+4\*-3 & 3\*-2+4\*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\\-15 & -22\end{bmatrix}$

**Transpose B and do dot product row wise for A and B**

$B^T=\begin{bmatrix}-1 & -3\\\-2 & -4\end{bmatrix}$

$C=\begin{bmatrix}1\*-1+2\*-3 & 1\*-2+2\*-4\\3\*-1+4\*-3 & 3\*-2+4\*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\\-15 & -22\end{bmatrix}$

I'd like to know whether the second version is correct in general?

And whether the second version is more cache efficient than the standard algorithm?

Why has matrix multiplication been defined as row with column?

NOTE: I do know real world implementations such as BLAS use different techniques than the naive implementation.

# Answer
It is correct.

Mathematically, $A$, $B$ and $C$ are foremostly *linear mappings* between vector spaces. Say, $A:W\to X$ and $B: V\to W$, then $C = A\circ B$ is a linear mapping $V\to X$. Practically speaking, and that's where the matrix representation stems from, you represent a mapping $V\to W$ as a member of the tensor space $V^\ast\otimes W$, where $V^\ast$ is the dual space of $V$, that is, any linear mapping $V\to W$ can be written in the form $$ B(v) = \sum\_j\sum\_k w\_j\cdot b\_{jk}\cdot f\_k(v) $$ where $b\_{jk}$ are the coefficients characterising the mapping, and the $w\_j$ form a convention-chosen basis of $W$ and the $f\_k:V\to \mathbb{R}$ (or whatever field you're working over) basis of $V^\ast$. Then, we can see what the composition comes out as: $$\begin{align} C(v) = A(B(v)) =& \sum\_l\sum\_i x\_l\cdot a\_{li}\cdot g\_i\Bigl(\sum\_j\sum\_k w\_j\cdot b\_{jk}\cdot f\_k(v)\Bigr) \\ =& \sum\_{lijk} x\_l\cdot a\_{li}\cdot b\_{jk}\cdot g\_i(w\_j)\cdot f\_k(v) \end{align}$$ The basis of $W$'s dual space will be chosen so that $g\_i(w\_j)=\delta\_{ij}$, so $$\begin{align} C(v) =& \sum\_{ljk} x\_l\cdot a\_{lj}\cdot b\_{jk}\cdot f\_k(v) \\ =:& \sum\_{lk} x\_l\cdot c\_{lk}\cdot f\_k(v) \end{align}$$ where you have your *matrix multiplication* $$ c\_{lk} = \sum\_j a\_{lj}\cdot b\_{jk}. $$ There are two alternative, equivalent ways to look at linear mappings, and one of them you found: you basically group $$ A(w) = \sum\_{li} x\_l\cdot a\_{li}\cdot g\_i(w) = \sum\_l x\_l\cdot \Bigl(\sum\_i a\_{li}\cdot g\_i\Bigr)(w) $$ ...which you can do because the dual space is also a vector space; $\Bigl(\sum\_i a\_{li}\cdot g\_i\Bigr)$ are just the *row vectors* of $A$ which are not in fact vectors but co-vectors—and now $$\begin{align} A(B(v)) =& \sum\_l x\_l\cdot \Bigl(\sum\_i a\_{li}\cdot g\_i\Bigr)\Bigl(\sum\_j\sum\_k w\_j\cdot b\_{jk}\cdot f\_k(v)\Bigr) \\ =& \sum\_{lk} x\_l\cdot \Bigl(\sum\_i a\_{li}\cdot g\_i\Bigr)\Bigl(\sum\_jw\_j\cdot b\_{jk}\Bigr)\cdot f\_k(v) \end{align}$$ ..and there in the middle is that scalar product between a row vector of $A$ and a column vector of $B$ (or, if you will, a row vector of $B^T$).

So yeah, this can be done and *is* often done in algorithms.

Does it help with cache? It can certainly help, if you naturally come by $B$ in transposed form. I think e.g. the Eigen library exploits this a lot, through lazy evaluation and pre-arranging intermediate results to come out transposed in the first place if deemend useful. If all you got is $B$ in un-transposed form though, well, the cost of transposing it (which is also not readily cache-friendly) may outweigh the cache penalty of multiplying in suboptimal order.

There are many approaches to this, it's a well studied field. But there's no silver bullet for the optimal transposition policy. (An interesting approach is to store matrices in Morton order, so that always both rows and columns have some cache coherence.)
> 2 votes

---
Tags: computer-architecture, linear-algebra, memory-access
---


# Question
Title: What is "Containment order"? Could I get a friendly explanation?
Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "ordered by containment" then they will be in roughly the same order with each other?

# Answer
I'll try a down to earth definition \ example:

When speaking of a set $X$, lets say $X=\\{1,...,100\\}$, denote the subset $X\_i = \\{1,...,i\\}$

It holds that $X\_1\subseteq X\_2\subseteq...\subseteq X\_{100}$

So you could say there is a **containment order** over these subsets, because each subset contains the other in an order that I stated. This order came from, and connected to (and isomorphic to) the partial order of $1 \leq 2 \leq ... \leq 100$ or if you prefer more fomally, that $(X,\leq )$ is a poset.
> 4 votes

# Answer
A containment order $\prec$ is a partially ordered set in which the points are labelled by sets, say a point $x$ is labelled by a set $S\_x$, and $x \prec y$ iff $S\_x \subset S\_y$.

As Wikipedia mentions, every partial order can be realized as a containment order. That is, any partial order is isomorphic to a containment order. You can find the proof on Wikipedia, or check the proof below. Because of this, a containment order is a syntactic rather than a semantic property. You can think of a containment order as a partial order which is realized "physically" as a partial order of sets ordered by inclusion.

As an example, let us realize the partial order of the natural numbers $0 \< 1 \< 2 \< \cdots$ as a containment order. This is very simple: we will label a point $x$ by the set $\\{0,\ldots,x-1\\}$. So $S\_0 = \emptyset$, $S\_1 = \\{0\\}$, $S\_2 = \\{0,1\\}$, and so on. You can check that $i \< j$ iff $S\_i \subset S\_j$.

As another example, suppose that we are interested in the partial order on words given by the following rule: $w\_1 \prec w\_2$ if $w\_1$ is a proper prefix of $w\_2$ (for example, $a \prec ab$). In this case, we label a string $w$ with the set of all of its prefixes. For example $S\_a = \\{\epsilon, a\\}$ (where $\epsilon$ is the empty string) and $S\_{ab} = \\{\epsilon, a, ab\\}$. Once again, you can check that $w\_1 \prec w\_2$ iff $S\_{w\_1} \subset S\_{w\_2}$.

More generally, given an arbitrary partial order $\prec$, we can define $S\_x = \\{ z : x \preceq z \\}$. We can then check that $x \prec y$ iff $S\_x \subset S\_y$.

To show this, suppose first that $x \prec y$ and $z \in S\_x$. Then $z \preceq x \prec y$, and so $z \in S\_y$. This shows that $S\_x \subseteq S\_y$. Since $x \prec y$, we know that $y \not\preceq x$, and so $y \in S\_y$ but $y \notin S\_x$, implying that $S\_x \subsetneq S\_y$.

In the other direction, suppose that $S\_x \subset S\_y$. Since $x \preceq x$, we have $x \in S\_x$, and so $x \in S\_y$, implying that $x \preceq y$. Clearly $x \neq y$, since otherwise $S\_x = S\_y$, and so $x \prec y$.
> 1 votes

---
Tags: terminology
---


# Question
Title: Where are 'Base & Bounds' registers located?
I read about virtual memory from L08/CS152 of U.C Berkeley and used to deep dive into the details of VM *hardware* implementation, yet didn't find any document or figure on the course specifying where the 4 “Base & Bounds“ registers (Data Bound Register, Data Base Register, Program Bound Register, Program Bound Register) used in the figure below are located. In order to have more detailed information, I did many searches for “MMU architecture”, “X86 architecture”, “bound register', “base register”, and so on .. But without success.

Are B&B registers located on the MMU or on the CPU? Can anyone provide any related hardware architecture reference?

# Answer
The values for base and limit must be stored in registers somewhere; it would be highly inefficient to read these from memory on every memory access.

The distinction between "CPU" and "MMU" isn't really an important one on the old Cray vector architectures, and also isn't really important today. This is more about older microprocessors where a "processor" lived on more than one die (e.g. the 68000 architecture which had an external MMU). Today, address translation is closely tied to the rest of the CPU. This actually made the news this week, since Meltdown uses the interaction between the MMU and instruction speculation as a side-channel attack against some Intel CPUs. But I digress.

The diagram is talking about Cray vector computers, so probably the best reference is to look at an old Cray manual.

So here is the Cray Y-MP EL (i.e. the "entry level" model) functional description document, and the description of the exchange mechanism in particular:

> **Address Base and Limit Fields**
>
> Four registers in the exchange package define a program's data range and instruction range anywhere in memory and allocate specific amounts of memory to each range. This memory allocation technique has two benefits. First, all programs are relocatable. When a program is written, the programmer does not need to know where in memory the instruction and data fields will be located. Second, each program can have its memory access restricted to certain parts of memory. A program can be halted if it tries to run an instruction outside of its allowed instruction range or if it tries to read or write data outside of its allowed data range. This is especially important where more than one program occupies memory at the same time; programs can be prevented from executing instructions or operating on data that belongs to other programs. The four registers are described in the following list.
>
> * The instruction base address (IBA) register holds the base address of the user's instruction range. It determines where in memory an instruction fetch is made. This is done by adding the contents of the P register to the contents of the IBA register. The sum equals the absolute memory address for the fetch.
> * The limit address (ILA) register holds the upper limit address of the user's instruction range. It determines the highest absolute address that can be accessed during an instruction fetch sequence. If this absolute address exceeds the limit, a program range error flag is set, which generates an interrupt.
> * The data base address (DBA) register holds the base address of the user's data range. It determines where in memory a program's data field is located. This is done by adding the memory address generated by the instruction to the contents of the DBA register. The sum equals the absolute address for any memory read or write operation.
> * The data limit address (DLA) register holds the upper limit address of the user's data range. It determines the highest absolute memory address that a program can use for reading or writing data. If this absolute address exceeds the limit, the memory reference is aborted. The operand range error flag is set, which generates an interrupt if the interrupt-on-operand range error bit is set.

Altering these registers is typically a privileged operation, in that it is reserved for supervisor-level code rather than user-level code. On Cray machines, these registers were set with an "exchange package", which is more or less the equivalent of a process control block, so it was presumably an operating system routine that set the registers when a task was run.

Now let's take a quick look at a modern architecture.

For Intel x86, this is called memory segmentation. The base and limit registers aren't accessed like normal registers, but are stored in a special data structure called a segment descriptor, which is loaded with the LGDT or LLDT instruction. The difference between the two is that the x86 architecture supports two descriptor tables: "global" and "local". Each process can have its own local table, which is used for features such as thread-local storage.

The situation changed completely with the advent of 64 bit CPUs. In 64-bit mode, segment descriptors are, for the most part, no longer used. There are two segment selectors, FS and GS, which support loading a base field using the model-specific register mechanism, as well as a special instruction called SWAPGS, the details of which are only important for operating system implementors. Note that these selectors have no limit field. Protecting memory from unauthorised access is handled using the paging mechanism, not segmentation limits.

This brings the Intel architecture in line with most other modern CPUs, such as ARM, which do not support memory segmentation.
> 6 votes

---
Tags: computer-architecture, memory-management, virtual-memory
---


title: Occupancy of a B+ Tree

text:
# Question
Title: Occupancy of a B+ Tree
If a B+ tree has an occupancy of 67%, does that mean the tree holds all of an index, and has additional empty nodes taking up the remaining 1/3rd?

# Answer
> 2 votes
B+ trees, like all B-tree variants, are typically page-structured. A page size is chosen (which is a multiple of the disk page size and the CPU's page size). Each node or leaf is a page in size. Organising the tree this way eliminates *external* fragmentation.

We pay for it with *internal* fragmentation.

Each node and leaf can have a variable amount of data stored inside it. So for if a node is not full, some of that page is unused. When we say that a B+ tree has 67% occupancy, this means that 1/3 of the allocated space is unused memory at the end of pages.

# Answer
> 0 votes
You are talking about a B\* tree rather than a B+ tree. In general, for a B+ tree of order $d$, each node except the root is required to contain $m$ entries such that $d \leq m \leq 2d$. That is, each node except the root has a maximum capacity $2d$ and has to contain at least $d$ entries. Therefore, the occupancy of a B+ tree in general is at least $m / 2d \geq d / 2d = 50\\%$. However, for a B\* tree, it requires that each internal node to be at least $2/3$ full rather than $50\\%$.

---
Tags: data-structures, database-theory
---


# Question
Title: Conditional Shortest Path Through Weighted Cyclic Directed Graph
Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge represents the destination.

My graph has negative cycles, for example \[A-red, B-red, C-blu, X-grn, D-blu, A-red\] has a cost of -1, comprised of edge costs \[1, 1, -1, -3, 1\].

I want to find the shortest path between arbitrary {source, destination} vertices subject to the following conditions:

1. Each vertex may only be visited once.
2. The count of vertexes visited along the path must be \<= m
3. The count of categories visited along the path must be \<= n

So, for example, assuming a function `shortest_path(source, dest, m, n)` then:

`shortest_path(('A','red'), ('D','ylw'), 100, 100)` would return \[A-red, B-red, C-blu, X-grn, D-ylw\] which has a cost of -2. This path visits 4 vertex categories \[red, blu, grn, ylw\].

`shortest_path(('A','red'), ('D','ylw'), 100, 3)` would return \[A-red, B-red, C-blu, D-ylw\] for a cost of 3. This path visits 3 vertex categories \[red, blu, ylw\].

Any suggestions here? I believe Dijkstra's algorithm and Bellman-Ford are out here as my graph contains negative cycles. So I think i need a brute force search of edges, integrating the stopping conditions mentioned above.

Python code for initializing my graph is here:

```
import networkx as nx

class Vertex(object):
    def __init__(self, name, category):
        self.name = name
        self.category = category
    def __hash__(self):
        return hash((self.name, self.category))
    def __eq__(self, other):
        if isinstance(other, Vertex):
            return other.name == self.name and other.category == self.category
    def __str__(self):
        return '{}-{}'.format(self.name, self.category)
    def __repr__(self):
        return str(self)

d = {
    Vertex('A','red') : {Vertex('B','red') : {'weight':1}},
    Vertex('B','red') : {Vertex('C','blu') : {'weight':1}},
    Vertex('C','blu') : {Vertex('D','ylw') : {'weight':1}, Vertex('X','grn') : {'weight':-1}},
    Vertex('D','ylw') : {Vertex('A','red') : {'weight':1}},
    Vertex('X','grn') : {Vertex('D','ylw') : {'weight':-3}},
}
G = nx.DiGraph(d)

pos = nx.circular_layout(G)
nx.draw_networkx(G,pos, arrows=True, with_labels=True)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos, edge_labels=labels);

```

**Update** Here is my current traversal algorithm, its essentially a DFS but I record both the parent of each vertex I examine, and the cost of traversing from the parent to the vertex. This allows me to reconstruct a path and compute a total cost for the path. However, I'm not sure its a great solution. My aim is to get the algorithm working well then port to cython for performance (my real graph is huge).

```
#DFS
def calcd(parents, distances):
    d = 0
    for v in parents[1:]:
        d+=distances[v]
    return d

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

def dfs(graph, source, target):
    visited = set()
    stack = list()
    parent = {}
    distance = {}

    stack.append(source)

    while stack:
        u = stack.pop()
        uob = graph[u] #edges outbound from u

        for v, eparams in uob.items():
            parent[v] = u
            distance[v] = eparams['weight']

            if v == target:
                path = backtrace(parent, source, target)
                print('Reached Target via {}'.format(path))
                print('calcd', calcd(path, distance))

            if v not in visited:
                visited.add(v)
                stack.append(v)

source, target = Vertex('A','red'), Vertex('D','ylw')
dfs(G, source, target)

```

This prints:

```
Reached Target via [A-red, B-red, C-blu, D-ylw] calcd 3
Reached Target via [A-red, B-red, C-blu, X-grn, D-ylw] calcd -2

```

# Answer
> 1 votes
The problem is NP-hard, even when you ignore the constraints about categories. See https://cstheory.stackexchange.com/q/17462/5038 for a simple proof based on a reduction from the longest path problem (or from the Hamiltonian path problem). Therefore, you should not expect any efficient algorithm.

There are algorithms whose running time is polynomial in the size of the graph but exponential in $m$ (the length of the path). See https://en.wikipedia.org/wiki/Longest\_path\_problem#Parameterized\_complexity.

The categories don't increase the complexity of the problem by more than a constant factor, since there are only 4 categories. For instance, if the path is required to use at most 3 different categories, you can enumerate all ${4 \choose 3}$ subsets of 3 categories, and for each, construct a smaller graph that contains only the vertices in that subset and then solve the problem on that graph without the restriction on the number of categories. So for an algorithm design perspective, I suggest you first solve the problem while ignoring the categories. It will then be straightforward to extend your solution to deal with the categories.

---
Tags: graphs, shortest-path, graph-traversal, python
---


# Question
Title: Why should one not use a 2^p size hash table when using the division method as a hash function?
I don't understand what is meant by:

"m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k." (pg. 231 of CLRS)

Terms defined:

```
m: size of hash table
h(k): hash function = k mod m
k: key

```

I don't understand what the p lowest-order bits of k means. Any clarification would be very helpful.

# Answer
Refresh your knowledge of binary! The $p$ lowest-order bits of $k$ are the last $p$ bits when $k$ is written out in binary (i.e., the $p$ rightmost bits). For example, if $p=3$ and $k=17$ then $k$ is $10001$ in binary and the three lowest-order bits are $001$.

The point is that, in general, computing $k \bmod m$ is a relatively expensive operation. However, if $m=2^p$ is a power of two, the remainder operation is to just look at the $p$ lowest-order bits. That can be done in a single instruction, by taking the bitwise AND with $2^p-1$.

If it's easier, consider the decimal case. If I ask you what is $8237643\bmod 1034$, your response will be to reach for your calculator; if I ask you what is $8237643\bmod 1000$, you'll tell me that it's $643$ with barely a thought. This is because $1000=10^3$ is a power of ten, whereas $1034$ is not. (There's no immediate equivalent of the bitwise AND trick for decimal.)
> 17 votes

# Answer
I think you've got your answer of what does the p lowest-order bits of k means from this answer but answer to the question why m should not be a power of 2 lies behind the concept of

> Choosing a good hash function is of the utmost importance. **An uniform hash function is one that equally distributes data items over the whole hash table data structure.** If the hash function is poorly chosen data items may tend to clump in one area of the hash table and many collisions will ensue. A non-uniform dispersal pattern and a high collision rate cause an overall data structure performance degradation.

When using division method if you are sure that the keys that are going to be used for a particular database have **"All the low-order p bit patterns are equally likely"** then choosing m equal to a power of 2 is not bad; in fact, it is same as choosing some other value of m which is not a power of 2.

But there maybe cases when keys are distributed in such a way that a large number of different keys have ***same low-order p bit patterns***, then choosing m equal to a power of 2 will fail to provide uniform distribution.

> The idea is that, hash function chosen should not be biased to some specific pattern(s) so that it can ensure equal distribution of data items over the whole hash table (without the knowledge of if keys are biased to a specific pattern) fairly in all the possible cases.

---

> "When using the division method, we usually avoid certain values of m (table size). For example, m should not be a power of 2, since if m = 2^p , then h(k) is just the p lowest-order bits of k. **Unless it is known that all low-order p bit patterns are equally likely, it is better to make the hash function depend on all the bits of the key.**"
>
> **--CLRS**

For detailed explanation of hashing using division method check this answer.
> 2 votes

---
Tags: hash-tables
---


# Question
Title: How are the control signals derived in the MIPS pipeline?
**NOTE**: Let me point out that I did try extensively to solve this on my own. The problem is that, based on that circuit, it would appear that this processor cannot jump. At best the jump instruction will propagate through the pipeline with no effect. There is no data path defined for a jump that tells the processor to change the PC. The only thing that changes the PC (aside from the normal PC+4) is a **beq**.

---

I'm learning about MIPS pipelining and stages, but what is excruciatingly unclear is how a jump instruction is executed. On an assignment question, I'm asked to trace the pipeline with the command **"j 16"**, but there does not appear to be any details about how the logic is handled. The closest thing I can find of any relevance is to do with **beq**, but the opcodes are different... **beq** is **000100** and **j** is **000010**. The following table outlines how the control codes work for four classes of opcodes, but it doesn't explain what happens for jump, and subsequently, how the machine knows to jump and what it does with the command...

So, if I have the instruction **000010 00000000000000000000000100**, how does this get handled by the data path?

# Answer
> 2 votes
You are correct. The above data path doesn't have the parts that support `jump` instruction. Yet, those are easy to add.

The pipelined datapath in your question is based on a single-cycle MIPS that doesn't support jumps (Figure 5.21 in Patterson and Hennessy). In order to add jump support, consider the single-cycle MIPS datapath of Figure 5.24; then add the jump parts to the pipelined architecture.

However, note that jumps and branches must be treated correctly in order to avoid control hazards - specifically, new instructions that entered the pipe after the jump should not be executed. The complete datapath that takes care of control hazards (again, for branches only) appears in Figure 6.41.

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


# Question
Title: What is the difference between distributed representations and factors of variation in deep learning
In the field of deep learning, people often talk about factors of variation which, in my understanding (in terms of dimensionality reduction), are the latent variable directions capturing variability in the data. I also often come across the term distributed representations which are basically the features of the input data that are not mutually exclusive.

Sometimes for object recognition, one may wish to extract distributed features of the object that are invariant to small variations (which are a result of combination of many factors of variation).

On the other hand, in case of autoencoder, one needs to extract the factors of variation as completely as possible so as to minimize the reconstruction error.

In the above two cases, factors of variation seem to have two contradicting roles, nevertheless they are both referred to as useful features for intermediate layers of a deep architecture.

So what is the difference between factors of variation and distributed features? I am very confused.

# Answer
> 0 votes
Usually, factors of variation are independent from each other. However, sometimes in feature extraction, some combination of these factors can be helpful to detect better and accurate features to explain the behavior of the observation.

Therefore, factors of variation are used to explain distributed features, and their relation likes the relation between basis of a space and a vector which is defined in the space using these basis or prime factors.

Although, observations change base on the factors of variation and distributed features, distributed features change base on the factors of variation. In the other words, features of variation are prime factors, and distributed features are defined base on the prime factors.

---
Tags: machine-learning, neural-networks
---