# Question
Title: Real-time systems and real-time operating systems
Just to understand the topic a little bit better, I would like to know if there is a difference between real-time systems and real-time operating systems.

I know that a real-time system is a system for processes that have to meet deadlines and fulfill real-time requirements. If a deadline isn't met, it can lead to drastic consequences. And a real-time operating system is an operating system that also has to fulfill real-time requirements. The examples I found on the internet are mostly the same and also other details are quite the same.

But are there any major differences, if yes which ones?

# Answer
> 1 votes
A system is several things working together. A real time system might include computer hardware and software. Depending on where you draw the line it might include sensors and actuators reaching into the "real" world (sorry for the pun ). The software might include an operating system, or not.

A realtime operating system is a set of software components with the purpose of making it easier for you as a programmer to write the application software of a real time system. Typically the OS helps in handling hardware and dividing the processor among several tasks. It could include tools used to create the system, to find bugs and to measure performance. This is a kind of software reuse, and I tend to think of it as "me beeing a midget, standing on the shoulders of the titans previous to me".

A real time system can loosely be defined by the statement "even if the response is correct, if it is too late it is as bad as if it was wrong". The concept of too late is the major concept in a real time system. This could be on a time scale of pico- or microseconds (sort of difficult with software), milliseconds or seconds (typical realtime areas) or even minutes, hours, days or years (probably not called realtime, but could be).

Often a real time system includes some mechanism to handle serious errors. The concept of fail-safe is often used. As example, even if the software stops totally, or part of the hardware becomes unserviceable, some hardware function in the system turns outputs to a safe state and maybe restarts the software. Another exemple might be that cars with computer controlled ignition and fuel injection has a special "limp-home" mode allowing you to do something useable even when some of the sensors are broken. Here the computer might be working, but not all parts of the system.

When human life is at risk, say in space exploration, the fail-safe solution might include running several computers in parallell and turning off suspicious ones using external hardware. The space shuttle is a famous example with several computers running in parallell and special hardware selecting to kick out erraneous ones. In addition there was a special fallback computer, using different hardware and software written by a different team to handle if the main computers would go totally off.

---
Tags: operating-systems, real-time
---


# Question
Title: How to find all paths of length up to k between two nodes in a directed graph?
Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$.

What is the most efficient algorithm to find all paths of length $\<=k$ from $u$ to $v$?

I know the number of such paths can be calculated efficiently using Dynamic Programming approach, but I'm looking for an algorithm that allows to get a set of actual paths.

It's clear that such algorithm would have a factor of the number of paths in its time complexity, which has $k$ in the exponent, but still, I would like to know what is the best approach for such a problem.

# Answer
> 0 votes
I'm not sure whether "best" is answerable, but I will describe one simple strategy that appears reasonable. Let $S(u,v,d)$ be the set of all such paths of length $d$. Then

$$S(u,w,d+1) = \\{u \leadsto v \to w \mid u \leadsto v \in S(u,v,d), v \to w \in E\\}$$

Also $S(u,u,0) = \\{u \to u\\}$. This gives a dynamic programming algorithm for computing the set of all such paths, if you evaluate these sets in order of increasing $d$.

As an optimization, you can delete all vertices that aren't reachable from $u$ or that can't reach $v$ before beginning this computation. As another optimization, you can precompute the matrices $A^k$, where $A^k\_{uv}=1$ if there is a path of length $k$ from $u$ to $v$ (these can be obtained from the adjacency matrix by repeated multiplication); then you only evaluate $S(u,w,d)$ for $u,w$ such that $A^d\_{uw}=1$ and $A^{k-d}\_{wv}=1$.

With these optimizations, if there are a total of $Q$ such paths that you want to output, then the running time will be at most $O(kQ \cdot |E|)$. There's not much opportunity to do much better than that; obviously any algorithm must take at least $\Omega(Q)$ time, and since $Q$ will typically be exponentially large compared to $k|E|$, the gap between the upper and lower bounds will typically be a small factor compared to the total running time.

---
Tags: algorithms, graphs
---


# Question
Title: Binary integer programming problem without exponential memory
Consider binary integer programming problem with n variables.
I think the branch and cut algorithm takes exponential memory. What are existing algorithms without much memory? Please suggest.

# Answer
> 1 votes
There is in general not likely to be any algorithm for this problem that will take polynomial time (and polynomial space); the problem is NP-hard, and thus not believed to allow an efficient algorithm. If you just want polynomial space, then exhaustive search works. You're not likely to find any algorithm that uses polynomial space and is guaranteed to be faster than exhaustive search; that would contradict the strong exponential-time hypothesis. All existing methods are heuristics that might work well on some instances but not others.

---
Tags: algorithms, integer-programming
---


# Question
Title: Maximum Capacity Path Problem with constraints
I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is:
Given an undirected graph with two parameters (weight,cost). We need to find the Maximum Capacity path problem from source to destination such that the cost of the path(sum of the edges of path) is within a fixed value specified by the user. In other words, it(sum of cost parameter along the path) is upper bounded by a constant value.
I modified the existing algorithm by adding and extra cost constraint while relaxing the edges but was unable to make it work for all types of graph. I was also wondering if this problem is NP-Complete.

# Answer
> 1 votes
It can be solved in polynomial time. For instance, you can use binary search over the weight. Given a candidate weight, delete all edges with lower weight, then find the lowest-cost path and test whether its cost is below the lower bound; that tells you whether the weight was too high or too low. Repeat until binary search converges.

---
Tags: graphs, np-complete, reductions, path
---


# Question
Title: Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }
I am trying to design a context-free grammar that generates the language { x in {a,b}\* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?

# Answer
> -1 votes
**PDA:**

Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"

**CFG:**

$S\rightarrow b\space | \space xSy$ for every $x,y\in \\{a,b\\}$

Yea, thats everything in the CFG!

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


# Question
Title: Can the structure of a "Complete Binary Tree", be uniquely identified if only its pre-order or post-order or in-order traversals are given?
I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.

The following is the definition of a complete binary tree:

> A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The above definition has been taken from this link: https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

It would be helpful if someone can prove or intuitively explain why we can or cannot uniquely construct a complete binary tree if only one of its 3 traversals is given?

# Answer
> 2 votes
Given $n$, *there is only one shape for a complete binary tree (CBT) with $n$ nodes.*

For any deterministic traversal, the correspondence between a node's position in a CBT and its position during the traversal of that CBT is completely fixed. So if a deterministic traversal is given, we can reconstruct the CBT uniquely. This applies not only to any one of pre-order, post-order, or in-order traversals, it also applies to breath-first-traversal (with the left child visited before the right child), or any other deterministic traversal as mentioned by Hendrik Jan in his comment.

Here is an example. The shape above is the only shape for a CBT with 12 nodes, which are, 1 root (at depth 0), 2 nodes at depth 1, 4 nodes at depth 2 and 5 nodes at depth 3. A pre-order traversal of that CBT visits the nodes in the following order.

1. the root node.
2. the first node of depth 1.
3. the first node of depth 2.
4. the first node of depth 3.
5. the second node of depth 3.
6. the second node of depth 2.
7. the third node of depth 3.
8. the fourth node of depth 3.
9. the second node of depth 1.
10. the third node of depth 2.
11. the fifth node of depth 3.
12. the fourth node of depth 2.

Give the list above, we know the root node is the 1st-node visited, the first node of depth 1 is the 2nd-node visited, ..., the fourth node of depth 3 is the 8th-node visited and the fifth node of depth 3 is the 11th-node visited.

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


# Question
Title: Help with performance and speed-up question related to number of cores and their areas
There is a question in my exam that said:

> Consider the following three processors (x, y, and z) that are all of varying areas. Assume that the single-thread performance of a core increases with the square root of its area.
>
> 1. Processor X, core area = A
> 2. Processor Y, core area = 4A
> 3. Processor Z, core area = 16A
>
> You are given a workload where S fraction of its work is serial and 1 - S of its work is infinitely parallelizable.
>
> a. If executed on a die composed of 16 Processor X's, what value of S would give a speedup of 4 over the performance of the workload on just Processor X?
>
> b. Given a homogenous die of area 16A, which of the three processors would you use on your die to achieve maximal speedup? What is the speedup over just a single Processor X? Assume the same work load as in part b.

My progress with this part so far:

In an area of 16A, 4 cores of Y would fit. The square root of its area is $2\sqrt{A}$, which each of the four cores' performance would increase by a factor of two? Using Amdahl's law,

Overall speed-up for this choice $=\dfrac{1}{\dfrac{1 - S}{4(2)?} + S}$

And likewise, the overall speed-up for choosing 1 core of Z $=\dfrac{1}{\dfrac{1 - S}{1(4)?} + S}$

I am assuming that 1 core of area 4A is like 2 cores of area A, is this a valid assumption? For S = 0.2, 4 cores of Y would yield a higher speedup than one core of Z. Is this reasoning correct?

# Answer
The problem in an exam is that you need the answer that is expected from you - something I’d have a real problem with. So keep this solution to yourself.

Speed up is always hard to calculate - calculating execution time avoids lots of fractions and is equivalent. Assume your task would take one second on one processor X.

Since S is serial, you need at least S seconds. In that time, your 15 remaining cores can do 15S worth of work. If 15S \>= 1-S or S \>= 1/16 then all work is done after S. if S \<= 1/16 then all cores can work on the task simultaneously, so the work takes 1/16 time. So time = max(S, 1/16) and speed up = min (1/S, 16). Speed up = 4 when S = 1/4.

You can have four processors of type Y at twice the speed or 1 of type Z at four times the speed. The work takes half of max(S, 1/4), that is max (S/2, 1/8) on 4 processors of type Y and it takes 1/4 on one processor of type Z.

X is fastest when S \<= 1/8. Y is fastest for 1/8 \<= S \<= 1/2, and Z is fastest for S \>= 1/2.
> 1 votes

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


# Question
Title: how to reduce the time complexity of this code?
I have a graph `G=(V,E)`. A list of nodes `NODE` subset of `V`. I want to find out all the neighbor nodes of each node in `NODE` and add edge if those neighbors have distance greater than 2. Can anyone here please help me to reduce the time complexity of this code to quadratic time or less.

```
import networkx as nx
import random

G = nx.erdos_renyi_graph(30, 0.05)

node=[]
for j in range(5):
        node.append(random.randint(1,30))

for i in node:
    lst=list(G.neighbors(i))
    if(len(lst)>1):
         for j in range(len(lst)):
             for k in range(j+1,len(lst)):
                 if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
                     G.add_edge(lst[j],lst[k])

```

# Answer
To get quadratic time, do the following:

Let $M = N(\text{NODE})$ be the neighbours of NODE in $G$.

Compute $G' = (G - \text{NODE})^3$, the *2nd power graph* of $G$ without the vertices from NODE.

Then you do the following: For every two vertices $u$ and $v$ in $M$, if $uv \notin E(G')$, add $uv$ to $G$.

This way you don't have to compute `shortest_path` anymore.
> 0 votes

---
Tags: graphs, time-complexity, algorithm-analysis, network-analysis
---


# Question
Title: Fast algorithm for clustering groups of elements given their size/time
I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can.

I would like to cluster files into the specified number of groups, where each groups size (= the sum of sizes of files in this group) is as close as possible to each other group in this cluster (but not in other clusters). Here are the requirements:

1. The first group always contain one file, which is the biggest of all groups in the cluster.
2. Any other group but the first can have multiple files in it.
3. The number of groups in each cluster is constrained to a maximum specified by user (but there can be less groups if it's better or there's not enough files).
4. There's no constraint on the number of clusters (there can be as little or as many as necessary).
5. **Goal (objective function): minimize the space left in all groups (of all clusters) while maximizing the number of groups per cluster (up to the maximum specified).**

The reason behind these requirements is that I am encoding files together, and any remaining space in any group will need to be filled by null bytes, which is a waste of space.

Clarification on the objective and constraints that follow from the requirements and the problem statement:

* Input is a list of files with their respective size.
* Desired output: a list of clusters with each clusters being comprised of groups of files, each group having one or several concatenated files.
* There must be at least 2 groups per cluster (except if no file is remaining) and up to a maximum of G groups (specified by user).
* Each file can be assigned to any group whatsoever and each group can be assigned to any cluster.
* The number of clusters can be chosen freely.

Here is a schema that shows one wrong and one good example of clustering schemes on 5 files (1 big file, and 4 files of exactly half the size of the big file) with a number of groups = 2:

The solution needs not be optimal, it can be sub-optimal as long as it's good enough, so greedy/heuristics algorithms are acceptable as long as their complexity is good enough.

Another concrete example to be clear: let's say I have this list of 10 files with their sizes, this is the input (in Python):

```
['file_3': 7,
'file_8': 11,
'file_6': 14,
'file_9': 51,
'file_1': 55,
'file_4': 58,
'file_5': 67,
'file_2': 68,
'file_7': 83,
'file_0': 85]

```

The final output is a list of clusters like this (constrained here to 3 groups per cluster):

```
{1: [['file_0'], ['file_7'], ['file_2', 'file_6']],
 2: [['file_5'], ['file_4', 'file_3'], ['file_1', 'file_8']],
 3: [['file_9']]}

```

And for example here (this is not a necessary output, it's just to check) the total size of each groups (ie, sum of file sizes for each group) for each cluster:

```
{1: [85, 83, 82], 2: [67, 65, 66], 3: [51]}

```

If the problem is NP-complete and/or impossible to solve in polynomial time, I can accept a solution to a reduction of the problem, dropping the first and fourth requirements (no clusters at all, only groups):

Here is the algorithm I could come up with for the full problem, but it's running in about O(n^g) where n is the length of the list of files, and g the number of groups per cluster:

```
Input: number of groups G per cluster, list of files F with respective sizes
- Order F by descending size
- Until F is empty:
    - Create a cluster X
    - A = Pop first item in F
    - Put A in X[0] (X[0] is thus the first group in cluster X)
    For g in 1..len(G)-1 :
        - B = Pop first item in F
        - Put B in X[g]
        - group_size := size(B)
        If group_size != size(A):
            While group_size < size(A):
                - Find next item C in F which size(C) <= size(A) - group_size
                - Put C in X[g]
                - group_size := group_size + size(C)

```

How can I do better? Is there a canonical problem? It seems like it's close to scheduling of parallel tasks (with tasks instead of files and time instead of size), but I'm not quite sure? Maybe a divide-and-conquer algorithm exists for this task?

# Answer
Finally I could devise a better algorithm by turning the problem upside down (ie, using bottom up construction instead of top-down).

In my OP algo, I first create a cluster and its groups, and then I walk through the whole files list until I could either fill completely the groups sizes, or there's no file in the files list small enough to fit.

Here it's the other way around: I walk through the files list, and for each file I either assign it to a group if it fits, or if it's too big I create a cluster and init it with this file. To do that, I continually maintain a list of groups sizes to fill, using insertion sort so that when I pick a file to organize, I just need to check its size against the first item of the "to-fill" list.

Here's the algorithm, running in O(n log(g)) (thank's to insertion sort or binary search trees):

```
For each file:
    - If to-fill list is empty or file.size > first-key(to-fill):
      * Create cluster c with file in first group g1
      * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
    - Else:
      * ksize = first-key(to-fill)
      * c, g = to-fill[ksize].popitem(0)
      * Add file to cluster c in group g
      * nsize = ksize - file.size
      * if nsize > 0:
        . to-fill[nsize].append([c, g])
        . sort to-fill if not an automatic ordering structure

```

Since it's running in O(n log(g)), the number of groups has little impact on the running time, contrary to the algo in the OP. Maybe it's possible to do better, but for now it is fast enough for me, since it can reasonably work on lists of 10M files under 20 seconds.

For those interested, here's a working implementation in Python (I used the sortedcontainers module for the sorted list, which runs in O(log(g)) instead of O(g) for insertion sort):

```
from collections import OrderedDict
from random import randint
from lib.sortedcontainers import SortedList

def gen_rand_fileslist(nbfiles=100, maxvalue=100):
    fileslist = {}
    for i in xrange(nbfiles):
        fileslist["file_%i" % i] = randint(1, maxvalue)
    return fileslist

def group_files_by_size_fast(fileslist, nbgroups, mode=1):
    '''Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.'''
    For each file:
        - If to-fill list is empty or file.size > first-key(to-fill):
          * Create cluster c with file in first group g1
          * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
        - Else:
          * ksize = first-key(to-fill)
          * c, g = to-fill[ksize].popitem(0)
          * Add file to cluster c in group g
          * nsize = ksize - file.size
          * if nsize > 0:
            . to-fill[nsize].append([c, g])
            . sort to-fill if not an automatic ordering structure
        '''
    ftofill = SortedList()
    ftofill_pointer = {}
    fgrouped = [] # [] or {}
    ford = sorted(fileslist.iteritems(), key=lambda x: x[1])
    last_cid = -1
    while ford:
        fname, fsize = ford.pop()
        #print "----\n"+fname, fsize
        #if ftofill: print "beforebranch", fsize, ftofill[-1]
        #print ftofill
        if not ftofill or fsize > ftofill[-1]:
            last_cid += 1
            #print "Branch A: create cluster %i" % last_cid
            fgrouped.append([])
            #fgrouped[last_cid] = []
            fgrouped[last_cid].append([fname])
            if mode==0:
                for g in xrange(nbgroups-1, 0, -1):
                    fgrouped[last_cid].append([])
                    if not fsize in ftofill_pointer:
                        ftofill_pointer[fsize] = []
                    ftofill_pointer[fsize].append((last_cid, g))
                    ftofill.add(fsize)
            else:
                for g in xrange(1, nbgroups):
                    try:
                        fgname, fgsize = ford.pop()
                        #print "Added to group %i: %s %i" % (g, fgname, fgsize)
                    except IndexError:
                        break
                    fgrouped[last_cid].append([fgname])
                    diff_size = fsize - fgsize
                    if diff_size > 0:
                        if not diff_size in ftofill_pointer:
                            ftofill_pointer[diff_size] = []
                        ftofill_pointer[diff_size].append((last_cid, g))
                        ftofill.add(diff_size)
        else:
            #print "Branch B"
            ksize = ftofill.pop()
            c, g = ftofill_pointer[ksize].pop()
            #print "Assign to cluster %i group %i" % (c, g)
            fgrouped[c][g].append(fname)
            nsize = ksize - fsize
            if nsize > 0:
                if not nsize in ftofill_pointer:
                    ftofill_pointer[nsize] = []
                ftofill_pointer[nsize].append((c, g))
                ftofill.add(nsize)
    return fgrouped
fgrouped2 = group_files_by_size_fast(fileslist, nbgroups)

def grouped_count_sizes(fileslist, fgrouped):
    '''Compute the total size per group and total number of files. Useful to check that everything is OK.'''
    fsizes = {}
    total_files = 0
    allitems = None

    for fkey, cluster in enumerate(fgrouped):
        fsizes[fkey] = []
        for subcluster in cluster:
            tot = 0
            for fname in subcluster:
                tot += fileslist[fname]
                total_files += 1
            fsizes[fkey].append(tot)
    return fsizes, total_files

if __name__ == '__main__':
    nbfiles = 10000000
    nbgroups = 10
    fileslist = gen_rand_fileslist(nbfiles)
    fgrouped = group_files_by_size(fileslist, nbgroups)
    fsizes, total_files = grouped_count_sizes(fileslist, fgrouped)
    print total_files
    print fsizes

```
> 2 votes

# Answer
You should look at bin-packing algorithms. Yours is simple as the constraint is only on 1 dimension, the size of the elements. But you have more complex ones with multiple dimensions. I paste the wikipedia here as a start but you can find lots of resources online as it's a famous algorithmic problem
> 0 votes

---
Tags: complexity-theory, optimization, cluster
---


# Question
Title: Procedure for finding if Overflow occurs on addition
I have two 4-bit 2's complement numbers a,b, and their sum in s (Also a 4-bit 2's complement number). Using only the basic logical operations, I need to write a procedure to find if an overflow occurs. If there is an overflow, the output needs to be 1000 otherwise it is 0000.

The inputs in this procedure are a, b, s, and output is 1000 or 0000 depending on the inputs. I am allowed to use AND, OR and NOT operators

I know that there is an overflow if a and b have the same most significant bit and c has a different most significant bit but can't seem to figure out what the expression should be except that whatever the result is, needs to be ANDed with 1000 for the final result. How do I solve this?

# Answer
> 0 votes
I found the solution and have answered it here

The final answer is

`(((NOT a) AND (NOT b) AND s) OR (a AND b AND (NOT s))) AND 1000`

---
Tags: computer-architecture
---


# Question
Title: How many different (full/complete) in-order binary-trees do exist?
Given be a binary tree whose elements printed in-order results in `[1,2,3,4]`.
**Q1:** How many different binary-trees do exist?
**Q2:** How many different **complete** binary-trees do exist?
**Q3:** How many different **full** binary-trees do exist?

For Q1 I was able to find a solution, by using the catalan number formula:
`c(n) = (2n)! / ((n + 1)! * n!)``c(4) = 14`.

For Q2 and Q3 however I was not able to find an answer to those problems.
Do general formulas for `n` elements even exist?

Definition of full and complete.

# Answer
**Q1:** How many different binary-trees do exist?
**A1:** `c(n) = (2n)! / ((n + 1)! * n!)``c(4) = 14`

**Q2:** How many different complete binary-trees do exist?
**A2:** Exact one:

```
;       (3)        L0: full
;      / | \
;   (2)  |  (4)    L1: full
;   /|   |   |
; (1)|   |   |     L2: not full (Node 2 is missing right child)
;  | |   |   |
;  1 2   3   4     Complete?: Yes, because all (but last) levels are full.

```

**Q3:** How many different full binary-trees do exist?
**A3:** If `n` is odd: `c((n-1)/2)` else `0`. `n = 4` therefore `0`. Reference

Thanks to YuvalFilmus for the help!
> 1 votes

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


title: Dependent types vs refinement types

text:
# Question
Title: Dependent types vs refinement types
Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of dependent types which distinguishes them?

If it helps, I came across Refined types via the Liquid Haskell project, and dependent types via Coq and Agda. That said, I'm looking for an explanation of how the theories differ.

# Answer
> 44 votes
The main differences are along two dimensions -- in the underlying theory, and in how they can be used. Lets just focus on the latter.

As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments so that verification (and inference) is completely automatic, meaning one does not require "proof terms" of the sort needed in the full dependent setting. This leads to significant automation. For example, compare insertion sort in LH:

http://ucsd-progsys.github.io/lh-workshop/04-case-study-insertsort.html#/ordered-lists

vs. in Idris

https://github.com/davidfstr/idris-insertion-sort/blob/master/InsertionSort.idr

However, the automation comes at a price. One cannot use arbitrary functions as specifications as one can in the fully dependent world, which restricts the class of properties one can write.

Thus, one goal of refinement systems is to *extend* the class of what can be specified, while that of fully dependent systems is to *automate* what can be proved. Perhaps there is a happy meeting ground where we can get the best of both worlds!

# Answer
> 23 votes
Refinement types are simply usual types with predicates. That is, given that $T$ is a usual type and $P$ is some predicate on $T$

$$\\{v:T \mid P(v)\\}$$ is a refinement type. $T$ in this case is called a *base type*.

AFAIK, in Liquid Haskell, they also allow some *dependend function types*, that is types $\\{x:T\_1 \to T\_2 \mid P\\}$ \[1\]. Notice that fully dependent types (like sigma-types) are not allowed.

Liquid Type system, described in \[1\] is indeed decidable and Liquid Haskell does use SMT solvers. However, Liquid Haskell also requires proof terms (or values,as those are called in a non-dependently typed language): if you sit down to write a Liquid Haskell program, you write your own functions, not just the types.

\[1\] http://goto.ucsd.edu/~rjhala/liquid/liquid\_types.pdf

# Answer
> 16 votes
Dependent types are types which depend on values in any way. A classic example is "the type of vectors of length `n`", where `n` is a value. Refinement types, as you say in the question, consist of all values of a given type which satisfy a given predicate. E.g. the type of positive numbers. These concepts aren't particularly related (that I know of). Of course, you can also reasonably have dependent refinement types, like "type of all numbers greater than `n`".

# Answer
> 12 votes
A refinement type is a type together with a decidable predicate: $$ \\{x:T ~|~ p(x)\\} $$ where $x$ is a variable name, $T$ is a type, and $p(x)$ is a **decidable predicate** over $x$.

A dependent pair type is the product type of two types where the second type depends on the value of the first: $$(x : T) \times q(x)$$ where $x$ is a variable name, $T$ is a type and $q(x)$ is a **type** dependent on x.

Thus, **refinement types are similar to dependent pair types whose second type are restricted to being a decidable predicate**.

**Not every type is a predicate**. For example $p\_1(x) = x\>0$ is a type and a predicate, but $q\_1(x) = \text{list}(\text{list}(x))$ is only type and not a predicate e.g., something that is not possible to describe as a refinement type would be $(x : \text{Type}) \times \text{list}(\text{list}(x))$.

**Not every predicate is decidable**. In Liquid Haskell, only structural recursive functions on a single argument with a single equation per constructor are allowed to be used in decidable predicates, together with operators from the quantifier-free logic of linear arithmetic and uninterpreted functions (namely ==, \<, +, ...) \[1\]. In Coq, all (total) functions can be used inside dependent types. Total in parenthesis, because in Coq all functions have to be total anyway.

---

Let us also look at the inhabitants of the types via their typing rules \[2\]. $$ \frac{e : T ~~~~~~ \text{true} : p(e)}{e : \\{x:T ~|~ p(x)\\}} \text{refinement} ~~~~~~~~~~~~~~~ \frac{e\_1 : T ~~~~~~ e\_2: q(e\_1)}{(e\_1, e\_2) : (x : T) \times q(x)} \text{dependent} $$

All values $e$ which are inhabitants of the refined type are also inhabitants of the type $T$. Refinement types *refine* types, because they put an additional constraint on the values via the predicate. On the other hand, the inhabitants of dependent pair types are pairs of two values.

This is actually directly related to $p$ being restricted to being decidable, whereas $q$ is not restricted. A decidable $p$ means that we can pass $\text{true} : p(e)$ to a SMT-solver who will decide for us whether this formula holds or not. On the other hand, for an unrestricted $q(e)$ no such algorithm to decide it exists, meaning that you have to provide a proof $e\_2$ that $q(x)$ holds, only then we can pass $e\_2 : q(x)$ to a type-checker to decide whether it holds or not. In case the type $q$ is not an arbitrary type (like $\text{nat}$ with its many inhabitants $1$, $2$, $3$,...) but also a predicate (meaning that it has a most one inhabitant, e.g. $\text{true}$) the value $e\_2$ becomes *computationally irrelevant* at run-time and can be erased during program extraction.

---

\[1\] Vazou et al, Haskell'14. LiquidHaskell: Experience with Refinement Types in the Real World

\[2\] Our rule $\text{refinement}$ is rule LT-Sub and DEC-\<:-BASE from \[3\] merged into one rule. In abuse of notation, we omit type contexts for simplicity, and write $\text{true} : f$ instead of $valid(\[\[f\]\])$ to say that formula $f$ is true, making it look more like the dependently typed language. For the rule $\text{dependent}$ see "term introduction" at Dependent Sum Type, although we write $(x:T) \times q(x)$ instead of $\Sigma x:T, q(x)$.

\[3\] Rondon et al, PLDI'08. Liquid Types

---
Tags: terminology, programming-languages, type-theory, functional-programming, dependent-types
---


# Question
Title: Method for combining derivative free optimization results of different data inputs
I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as possible.

What I found, is that when optimizing the parameters for a specific time period, these parameters don't necessarily work well when used on another time period.

The way I see it, is that there are two possible solutions to this problem:

1. use a longer time period when optimizing the parameters
2. find a method of combining the optimal parameters for different time periods, such that these "averaged" parameters work well on all time periods

Option 1. would be incredibly expensive in terms of computational time. And although it makes intuitive sense that this should fix the problem, I am not sure that this would indeed be the case.

Option 2. reminds me of training neural networks, where one would feed in a large number of "data points" and somehow take a (weighted) average of the results to find a set of parameters that work well for all data points. Unfortunately, I know very little to nothing about the algorithms used for this kind of optimization/learning.

Any help or suggestions are greatly appreciated. Please let me know if there is anything you'd like me to expand upon.

Thanks!

EDIT: As suggested in the comments, here is some additional information:

* my loss function is not an actual mathematical function, so I don't know exactly what it looks like, this also means that I can't compute the gradient.
* The optimization method I currently use is differential evolution using the best1bin strategy.
* The reason the predictions fail is because of overfitting.
* There are ~10 parameters
* One iteration takes about 5-8 seconds

# Answer
You say you are overfitting. The usual solution is to use more training data and/or regularization.

The easiest solution is probably going to be to train on all data, not just a limited time window. Perhaps you can find a better mathematical optimization algorithm. You don't give any details on the optimization algorithm you are using or how you compute the loss function; perhaps using a stochastic version (e.g., analogous to SGD instead of GD) would provide better efficiency. You could also consider Bayesian optimization, which constructs a differentiable model to estimate/predict the output of your loss function, and then uses SGD on it. Another option is to use gradient-based methods and estimate the gradient using finite differences; if you have 10 parameters, you can estimate the gradient by evaluating the function 11 times on 11 different inputs. Then you could combine that with gradient descent.

Or perhaps you can use regularization; for instance, if you have a prior on parameters, you might be able to choose a suitable regularization method. I suspect it's going to be hard to say without getting into the specifics.
> 0 votes

---
Tags: algorithms, optimization, machine-learning, learning-theory
---


# Question
Title: Analysis of kd-tree, how is the vertical line L's intersect areas equivalent to sqrt(N)?
I'm trying to understand how the number of intersected areas by a vertical line in a KD-tree is equivalent to sqrt(n)

If you draw a balanced KD-tree with 7 nodes.

And then draw a vertical line l.

The number of areas this line intersects should be equivalent to sqrt(N) where N is amount of nodes. (7)

When I count the areas the vertical line L intersects I get 5. But sqrt(7) = 2,6 not even close.

Both sources get to the recurrence:

Which solves to O(sqrt(N)).

What am I doing wrong?

Sources:

Source 1

Source 2

# Answer
> 0 votes
The claim that the number of such intersections is $O(\sqrt{n})$ does not mean it is $\sqrt{n}$; you are ignoring the hidden constant.

I don't know whether the claim is true. Slides are not a good source for this material. Reading and working through and understanding the analysis in Section 3.2 of the paper you linked would be the best way to resolve this.

---
Tags: algorithms, algorithm-analysis, big-o-notation
---


# Question
Title: assign points to non-overlapping rectangles
I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of any rectangle). I'm looking for a solution that works faster than bruteforce.

In 1D, it is achievable in N * log(M) using binary search. is something like that possible in 2D?

I care about practical performance. Two or more points can and often would be in the same rectangle, but the opposite never happens as rectangles are non-overlapping.

# Answer
> 2 votes
Most spatial indexes should be good, especially if your rectangles are axis aligned.

Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.

For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $M$). R-Trees such as the R\*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library. In the case of Java I can also strongly recommend the PH-Tree (disclaimer: self advertisement).

---
Tags: computational-geometry, polygons
---


# Question
Title: Checking if two statements can be reached in one control flow
Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. **I now want to figure out if it is possible to execute both statements (in order) within the same program execution.**

**Control Flow Graph**: I have a graph with all the statements of the program and edges connecting the statements determining the control flow of the program intra function (i.e., within a function).

**Call Graph**: I also have edges connecting any function call with the start of the function control flow of the called function.

The literature I found concerning control flow covers only intra function flow analysis and the only correct approach I can come up with is a depth first (or breadth first) search starting from the first statement. This, however, hardly feels correct as it is quite cumbersome and I would expect a better solution.

# Answer
> 1 votes
This can be solved with a "context-free reachability" query in a graph. Each function call corresponds to an open parenthesis, each return corresponds to a close parenthesis, and you want to know whether there is a path in the graph such that the sequence of parentheses formed is properly nested and that traverses those two nodes in order. If you search on that term you should find papers with algorithms for that problem.

The exact nature of the context-free language depends on how you formulate the question. Suppose we want to know whether there is a path in the program that respects function calls and returns and visits $u$ and $v$, in that order. One way is to ask whether there exists a path through the graph that starts at $s$ (the start point of the program), then eventually visits $u$, then eventually visits $v$, and where the word formed by this path is in the Dyck language $L$ of properly nested parentheses, e.g., $S = L(S)$ where $S := \varepsilon | (S)$. Equivalently, you can ask whether there exists a path in the graph that starts at $u$ and ends at $v$, and where the word formed by this paths in a different context-free language $L'$, namely, the set of all suffixes of words in $L$. Here $L'$ is context-free, as it can be recognized by the grammar $S' := S | S)$. This then becomes a context-free reachability query on the graph. In practice we have multiple parentheses symbols, one per function. You can find these kinds of details in papers on context-free reachability.

---
Tags: graphs, static-analysis
---


title: Three City Scheduling

text:
# Question
Title: Three City Scheduling
I came across the following interview question

> There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs\[i\]\[0\], and the cost of flying the i-th person to city B is costs\[i\]\[1\].
>
> Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

The solution to this involves greedy approach, where we sort the array based on the "profit" parameter. profit of choosing city A for a candidate `i` is defined as `costs[i][1] - costs[i][0]` and choose the top half elements from the sorted array to go to A and rest to B.

**What if this question is modified to 3 cities and you have find optimal partition of n/3 chunks?** Will greedy algorithm still work?

# Answer
Generalizing with $kn$ people and $k$ cities we can see "move to city $j$" as a task. Furthermore, we have $n$ copies of each task. For all copies of a task $j$, the cost for person $i$ to move to that task is $c\_{i, j}$.

But now the problem is a direct instance of the balanced assignment problem, with complexity $O((kn)^3)$.
> 1 votes

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Testing whether a determinant polynomial is identically zero
Suppose we are given matrices $A\_1, \ldots, A\_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha\_1 A\_1 + \alpha\_2 A\_2 + \cdots + \alpha\_k A\_k)$ is identically zero. How can we do this **deterministically** in polynomial time in $n$ and $k$?

I'm aware that black-box polynomial identity testing is a difficult problem, but then this is not quite a black box.

# Answer
Is this a practical problem or a theoretical problem?

If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.

Your polynomial is a multivariate polynomial of degree $n$ over the field $\mathbb{R}$. Pick a set $S$ of real numbers with cardinality $2n$, draw $k$ numbers uniformly at random from $S$, and evaluate the polynomial at those points (substituting the first for $\alpha\_1$, the second for $\alpha\_2$, and so on). Check whether the result is non-zero. By Schwartz-Zippel, either your polynomial is identically zero or else the result will be non-zero with probability $\ge 1/2$. Thus, we can repeat this test $m$ times. If we get zero every time, output "the polynomial is identically zero". Otherwise output "the polynomial is not identically zero". You'll be wrong with probability at most $1/2^m$.

If you want to have a small seed, use a cryptographically secure pseudorandom number generator to generator the random numbers needed for this procedure. Under a suitable cryptographic assumption, this will allow you to use only 128 bits of true randomness (or so).

This should be good enough for all practical applications. Of course, it doesn't answer the theoretical question of whether this problem has a deterministic polytime algorithm.
> 3 votes

# Answer
This currently **does not** have any deterministic polynomial-time algorithm, not even "whitebox". Moreover, it is expected to be a very hard problem as due to a landmark paper by Kabanets-Impagliazzo Derandomizing Polynomial Identity Tests …, even showing that it is in NSUBEXP would imply strong circuit lower bounds like permanent has no polynomial-size circuit or that NEXP is not contained in P/poly.

There has been a lot of recent progress especially on a subcase called the "non-commutative" version of this in which we consider the $\alpha\_i$ to be non-commuting variables. This was derandomized (whitebox) recently by GGOW (over C) and Ivanyos, Youming Qiao, and Subrahmanyam (over every characteristic fields).

Another recent work gave A Deterministic PTAS to approximate the maximum rank of such a linear combination
> 2 votes

---
Tags: algorithms, linear-algebra, polynomials
---


# Question
Title: Proof that no O(n) multiplication algorithm exists
For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?

# Answer
> 13 votes
There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.

# Answer
> 9 votes
No nontrivial lower bound for the multiplcation is known (clearly, it is $\Omega(n)$) and David Harvey himself does not know if a complexity of $O(n\log(n))$ is the best possible: in his own words: "in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously". See also the original paper al page 1: "If the Schönhage–Strassen conjecture is correct, then Theorem 1.1 is asymptotically optimal. Unfortunately, no super-linear lower bound for $M(n)$ is known."

# Answer
> -11 votes
You could do it in O(1), kinda...

1. Precompute a lookup tables of log and log-1 values.
2. Get absolute values
3. Look up the two numbers,
4. Add the log of the two numbers
5. Look up log-1
6. Change to negative if one of the original numbers was negative.

Boom! O(1)

If you work with 32bit signed ints then that would only take 8gb of of memory for the first table (312 x 4bytes) and 16gb for the second (312 x 8bytes). (It may be possible to compress them a bit for the small logs and log-1s)

Quite a bit of memory yes, but readily available on consumer grade laptops.

If you have lots of 32 signed ints it may be worth the large contact overhead?!

---
Tags: complexity-theory, multiplication
---


# Question
Title: Is it possible to modify the linux assembler in order to modify what fuctions do?
I was wondering if it were possible to modify the linux assembler in order to change the function of "-" to "+" and vice versa.
I was also wondering if this would affect the whole system making it collapse. I apologize if this question is not appropriate here. Please explain why if it is the case.

E.g:
2+2 = 0
2-2 = 4

My objective is to see what applications this could have for a potential computer virus (I hope this is allowed here).

# Answer
While this is trivially possible, the fundamental flaw in your idea is that assemblers are not interpreters. Python programs are run by the Python interpreter, Swapping `-` and `+` in the Python interpreter would likely crash all Python programs. But normal programs are executed directly by the CPU. The assembler is not involved in their execution.
> 0 votes

---
Tags: assembly
---


# Question
Title: How to solve recursion T(n)=T(n/2)+T(n/3)+n?
How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.

# Answer
> 1 votes
This is a straightforward application of the Akra-Bazzi theorem.

You can also show that $T(n) = \Theta(n)$ by induction. First, clearly $T(n) \geq n$. In the other direction, if we have shown that $T(m) \leq 6m$ for $m \< n$, then $$ T(n) \leq 6(n/2 + n/3) + n = 6n. $$ Therefore as long as the base case holds, and if we ignore the fact that $n/2,n/3$ are not necessarily integers, we can prove inductively that $T(n) \leq 6n$.

---
Tags: complexity-theory, time-complexity, recurrence-relation, recursion
---


title: Assembly decision loops

text:
# Question
Title: Assembly decision loops
An high level language such as C has many statements for decision and loops while an assembly such the MIPS' one has few. With `slt`, `slti`, `beq`, `bne` it can create all conditions. What are the advantages and disadvantages of reducing the decision statements?

# Answer
Since C is a high level language in comparison to assembly level so yes they're required to have all those decision and loop statements for use at the appropriate places while the assembly level at its core breaks those statement to branches and loops using limited instructions and that is also foundational to RISC architecture. Hope that helps. P.S-Although there are many statements for decisions and loops in programming languages like C and Java, the bedrock statement that implements them at the instruction set level is the conditional branch.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Why is casting float to double applicable?
This is indeed a Computer Science Question. As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits.

e.g

```
Long: 0x00000000ffffffff casts down to
Int:  0xffffffff

```

However, this does not work with the representation of double and float:

```
Double:  b = 0xa000 0001 1000 0001 should cast down to

Float:   c = 0x1000 1001

```

which is not the same, even if the double is in the boundaries of float.

So how is Casting from any type to another defined?

# Answer
> 2 votes
This is really not a computer science question...

First, you failed to distinguish between "casting" and "conversion". In many computer languages, "casting" is an explicit instruction to convert a value from some type to another type. For example in C,

```
double d = 3.7;
float f = d; // Automatic conversion, no casting

double d = 3.7;
float f = (float) d; // Casting as requested by programmer
double e = (float) d; // Casting to float, followed by conversion to double

```

So what you were really talking about was value conversion, not casting. (Being precise in what you write is arguably part of computer science).

The effect of any conversion is defined by the computer language in question. "Shrinking down (leveraging) the significant bits" is something that doesn't make any sense at all. Bits don't have a size, you can't shrink them. And the word "leveraging" doesn't mean what you think it means. I assume you meant "removing the significant bits".

But that's not how value conversion is defined. In C and C++, it is defined in terms of values. A conversion between scalar types results in the exact same value if the old value can be represented in the new type. If the value cannot be represented, then there are rules for conversions between integer types; in some cases the value is modified according to rules in the language, sometimes the value is modified according to implementation defined rules (and "implementation defined" has a very specific meaning in C and C++ that you need to learn), or it is undefined behaviour.

Converting non-integral floating point values to integer values first rounds the value towards zero, and then other rules apply. Conversion between floating-point values will produce the original value if possible, rounds according to rounding rules in the language if that is not possible, with additional rules if the value is too large to represent.

Do you notice how nothing at all here is talking about bits?

Swift distinguishes between conversions that cannot fail and conversion that can fail. Conversions that can fail produce an *optional* value. Which is a totally different thing. For example, you cannot convert UInt to Int, only to an optional Int. You cannot convert Int64 to Int32, only to an optional Int32. But you can convert Int32 to Int64, because it is a conversion that cannot fail.

# Answer
> 0 votes
Casting is a semantic concept. When you cast the float 1.0 to double, you get a double 1.0. How these are represented are beside the matter.

There are various complications that could happen:

* Loss of accuracy.
* Overflow.
* Underflow.

The "complication" that you describe, however, is no problem at all. It stems from the way that exponents are stored in floating point formats.

# Answer
> 0 votes
Casting is implementation defined. Assembly languages/microprocessors can usually do such conversions in one single instruction. Method and quality of output is arbitrary.

---
Tags: formal-languages, compilers
---


# Question
Title: Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps
If we have the language

$nHALT=\\{\<M,w,n\>;$ $M$ halts on input $w$ in less than $n$ steps$\\}$

Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\notin P$, right?

# Answer
> 0 votes
This language is obviously decideable, just emulate $M$ on $w$ and see whether it halted within $n$ steps or not...

Now, to whether $nHALT\in P$ or $nHALT\notin P$. The length of $n$ here is logarithmic to its "value" (assuming that $\Sigma$ here is not unary). Thus, the number of steps we will need to emulate would be exponential in its size! I dont see a polynomial time algorithm for that, so I **assume it's probably not in P**. But I have not proven that (just gave intuition on why it could be the case), and there is also a chance that showing that is equivalent to some open problem (maybe somehow you could prove its $\mathcal {NP-Complete}$?)

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


# Question
Title: Is there a dynamic programming solution to the student allocation problem?
The student project allocation problem I am trying to solve goes as follows.

* There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
* Each student makes a top $3$ of their preferred projects.
* Each student should be allocated to exactly one project.
* Each project has a maximum number of students which can choose it, $c$.

We want to find some combination of students being allocated to projects so that a maximum of students are allocated their preferred project. Of the students who didn't get their preferred choice, a maximum of them should be allocated their second choice.

This is a optimization problem with constraints. If we assign a priority weight $w\_{ij}$ for the $i^{th}$ student choosing the $j^{th}$ project, where $w\_{ij} \in \\{0, 1, 2, 3\\}$, and $w\_{ij}$ is $0$ when the student $i$ did not include project $j$ in his top $3$, $1$ if it is his third choice, $2$ second choice, $3$ preferred choice.

We can also introduce a variable $x\_{ij} \in \\{0, 1\\}$, which is equal to $1$ when student $i$ has been allocated to project $j$ and $0$ otherwise.

Now we can formulate an objective function, $o$, to maximize in order to reach an optimal allocation.

$$o = \sum\_{\forall (i, j) \in S \times P}{x\_{ij} \cdot w\_{ij}}$$

We must maximize $o$ according to the problems constraints.

$$\forall i \in S : \sum\_{\forall j \in P}{x\_{ij}} = 1 \quad \textrm{every student is allocated to exactly one project}$$

$$\forall j \in P : \sum\_{\forall i \in S}{x\_{ij}} \leq c\_j \quad \textrm{no project is allocated more than its maximum number of students}$$

I think there are no other constraints.

Now, I am stuck. How do I go about actually solving this on a computer given all of the above. Is there a relationship between the optimal allocation for $i$ students and $i + 1$ students? Can I use dynamic programming, and if so how? Or do I have to use some other method, and if so what method?

# Answer
This sounds like it could be solved using a flow network.

Define the graph $G=(V,E)$ such that:

1. Add a starting node $s$. It will be the "source" node in the flow-graph.
2. Add a node $v\_{s\_i}$ for every student $s\_i$.
3. Add a node $v\_{p\_j}$ for every project $p\_j$.
4. Add the final node $t$. It will be the "sink" node for the flow-graph.

Now, start adding the edges and their weights as following:

1. For every $s\_i\in S$, add an edge $(s,v\_{s\_i})$ of weight **1**.
2. For every $s\_i\in S$ and every preferred project of his, $p\_j$, add an edge $(v\_{s\_i},v\_{p\_j})$ with weight **1**.
3. Finally, for every project $p\_j$ add an edge $(v\_{p\_j},t)$ of weight $c$.

Run the Ford Fulkerson algorithm on this graph $G$ we defined, and it will spit out an **integer flow** $f$. Assign a student $s\_i$ to project $p\_j$ if there is flow between $v\_{s\_i}$ and $v\_{p\_j}$ in $f$. Notice there might be students that wont be assigned anything in that way. They cannot be assigned to anything they prefer - so just assign them in any free project.

This algorithm runs in time $\mathcal O(|S||P|)$ since $|V|=\mathcal O(|S|+|P|)=\mathcal O(|P|)$, and each student has up to 3 preferred project so $|E|=\mathcal O(|V|)=\mathcal O(|P|)$ as well and the value of $f$, $|f|\le|S|=O(|S|)$.

It also provides the best possible solution, since it always maximizes the flow's value which is the number you want to maximize (think why).
> 1 votes

# Answer
This is a variation of the assignment problem. You will find several algorithms on the Wikipedia page linked, although none makes use of dynamic programming.

You can transform your formulation into an assignment problem by subdividing each project in $c$ projects of one student each, and creating phantom students with no preferences to fill the remaining places.

Alternatively, you can formulate it as a linear programming or minimum cost flow problem, and solve it with a solver or a dedicated algorithm for those.
> 1 votes

---
Tags: optimization, dynamic-programming, combinatorics, linear-programming
---


title: Scheduling problem

text:
# Question
Title: Scheduling problem
I am trying to find in the literature how to solve the following problem:

Suppose we have a list of $n$ jobs. Some of the jobs should be scheduled after other jobs (i.e., job a should be done after job b), other jobs need to be mutually exclusive (i.e., job c cannot be done concurrently with job e). Each job $i$ has a constant execution time, $T\_i$. Our goal to find a scheduling for the jobs, that minimazes the time to execute all jobs.

I know that when all jobs scheduled after other jobs, this problem can be using topology ordering and dynamic programming. Also, I found this problem is highly related to makespane problem with infinite identical stations, with a contrain on the order of jobs. I did not found yet a problem given a ording/mutual exelcusive relationship between jobs.

How can we solve this problem?

# Answer
> 0 votes
OK, I found that the problem is NP-hard. Given that all jobs have only mutually exclusive relationship, and $T\_i=1$ for every job $i$, the problem is eqivalent to the finding the orientation of a graph $G$, that has the minimal longest path. According to Gallai–Hasse–Roy–Vitaver theorem, this is equivalent to finding a chromatic number of $G$, which is NP-hard.

---
Tags: scheduling
---


title: Is there a name of this problem?

text:
# Question
Title: Is there a name of this problem?
There is $n$ lists (of integers) of the same length. I want to find the zeros global intersections of those lists.

Example:

$A = \[4,6,3,0,7,0,0,0,1,0,0\]$

$B = \[6,6,7,1,7,0,0,0,4,0,0\]$

$C = \[2,4,7,0,7,0,0,0,3,0,0\]$

The output are the position of those intersections:

The positions are $5, 6, 7, 9$ and $10$

Other than "traversing" the list and checking element by element, is there another way ?

# Answer
> 1 votes
There is no asymptotically better deterministic algorithm than the one that just checks, for each position $i=1,\dots,n$ whether $A\[i\]=B\[i\]=C\[i\]=0$.

This is easy to see since any correct algorithm must read at least one entry per value of $i$. To see this, suppose that there is an instance $I = \langle A,B,C \rangle$ for which a correct algorithm $\mathcal{A}$ accesses neither of $A\[i\]$, $B\[i\]$, and $C\[i\]$, for some $i$.

Consider two instances $I' = \langle A',B',C' \rangle$ and $I'' = \langle A'',B'',C'' \rangle$ that are identical to $I$ except (possibly) for the fact that $A'\[i\]=B'\[i\]=C'\[i\]=0$ and $A'\[i\]=B'\[i\]=C'\[i\]\neq 0$. Clearly $\mathcal{A}$ must return the same set $S$ of indices on all of $I$, $I'$, and $I''$. If $i \in S$, then $\mathcal{A}$ fails on $I''$, otherwise $\mathcal{A}$ fails on $I'$.

---
Tags: algorithms
---


# Question
Title: Close To Cook Reduction given NP != coNP
I am struggling to answer these two questions:

Prove or wrong:
Both are given the assumption that NP != coNP.

1. For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there exists a Cook reduction from S' complement to S complement.
2. The class NP intersection coNP is closed under Cook reduction.

Thank you very much!

# Answer
> 0 votes
The assumption of $\text{P} \neq \text{NP}$ is not necessary here.

1. given a reduction $\Phi$ from a language $A$ to a language $B$, (that is polynomial time) then for every $x$ we have, $x\in A $ iff $\Phi(x) \in B$. Then (just as $p\rightarrow q$ is equivalent to $\neg q \rightarrow \neg p$) we have $x\notin A$ iff $\Phi(x)\notin B$.
2. As for why $\text{NP} \bigcap \text{co-NP}$ is closed under poly time reductions, it's just because you can emulate the machine calculating the reduction. I mean that if $\Phi$ is a reduction from $A$ to $B$ and $B\in \text{NP} \bigcap \text{co-NP}$, then to make a machine for $A$, start by calculating $\Phi(x)$ for input $x$ and use $B$'s machine on it afterwards.

---
Tags: reductions, complexity-classes, co-np, polynomial-time-reductions
---


# Question
Title: Function minimization as genetic algorithm stop condition
I have implemented genetic algorithm for a problem where I have an objective function which I need to minimize:

```
Cost = ax + by + cz -> min

```

The genetic algorithm should have found the optimal solution if objective function is satisfied.

The function will never reach 0 or below, so I just need to minimize it. Now, since there are no objective values to be reached, how do I know whether the objective function is satisfied or not?

# Answer
There are three typical stopping criteria:

1. You have reached a sufficient value
2. Your *new optimal value* hasn't changed for the past $n$ minutes/generations
3. Your time (and patience) runs out.

The best case scenario is Case 1. These are the cases where you are looking for a *good enough* solution, and you have found a solution that is good enough. This criterion depends on you actually being able to set such a value, of course.

Typically Case 2 is better than Case 3 when it works out. Here you don't abort your simulation as long as "it's improving" and therefore hasn't found the optimal solution.

But some times you get to borrow the cluster for 2 weeks, and then that's when you shut it off.
> 1 votes

---
Tags: genetic-algorithms
---


# Question
Title: How to find rows of matrix that are zero everywhere except for 1 entry?
I am interested in finding the rows of a matrix where all entries are equal to zeros except for one.

Example: Given the following matrix:

\begin{bmatrix}0 &0 &3 & 8\\ 0 & 4 & 0 & 0 \\ 0 &1 & 0 & 1\end{bmatrix}

Only the second line has this property.

Of course, the brute force way is to go over the entries and check them one by one. But I am wondering if there is another most efficient way I don't know about.

# Answer
There is no algorithm with worst-case running time better than $O(n^2)$. There is a simple adversary argument to prove this.

Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected. Consider a matrix that has 1's in the entire first column. Every time the algorithm inspects any other entry, it will find a 0. After inspecting at most $n^2-1$ entries, the algorithm terminates and outputs some list of rows. Pick any entry that was uninspected. Now we have a freedom about whether to fill it in with a 0 or a 1; and we can always make a choice that will make the algorithm's output wrong (if the algorithm included that row in its output, make it a 1; otherwise make it a 0). So, for any correct algorithm, it must inspect all matrix entries for at least some inputs, so its running time must be at least $\Omega(n^2)$.

There are various optimizations you can use in practice, like using bitwise operations (depending on how the matrix is stored), and if you see more than a single 1 in any row, don't look at any other entries in that row -- but these won't affect the asymptotic worst-case running time.
> 1 votes

# Answer
This is no different than asking for an algorithm for deciding if the entries of an array contain a nonzero. So what you describe is optimal, i.e. an adversary argument shows that any algorithm must examine each entry for otherwise you can't know for sure.
> 1 votes

---
Tags: algorithms, matrices
---


# Question
Title: Is the language of rectangular matrices in MATLAB-style syntax context free?
Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be an arbitrary number of rows, but each row must contain the same number of integers.

For example: $\[3, 5, 6; 8, 9, 10; 7, 3, 6\] \in L$ and $\[3, 5, 6; 7, 8, 10, 12; 7\] \notin L$, because each row contains a different number of integers and so the matrix is not rectangular.

Is this language context-free? I have a very strong hunch that it isn't, given that not even the language $A^{n}B^{n}C^{n}$ is context free, but I don't have much experience with proofs using the pumping lemma for context-free languages and I'm hoping there is a simpler way to prove that $L$ is not context free.

# Answer
Delete all numbers from your language $L$, and replace $,$ with $a$ and $;$ as $b$. Then intersect it with the regular language $a^\*ba^\*ba^\*$. You obtain a new language $L' = \\{a^n b a^n b a^n : n \in \mathbb{N}\\}$. If $L$ is context-free, then $L'$ will be context-free too, as it has been obtained by applying a homomorphism and then intersecting with a regular language, both of which preserve context-freeness. However, $L'$ is a standard example of a non-context-free language, so $L$ must be non-context-free as well.
> 1 votes

# Answer
To convert this question into an easier question to answer, practically, we consider the language $\hat L=\\{(a^nb)^n|n\in\mathbb N\\}$. Proving this is not context free is enough, since we can give a hommomorphism from $L$ to it by $h(",")=a,\space h(";")=b,\space h(x)=\epsilon$ for every other $x$, and then we get $h(L)=\hat L$.

Now, I think it should be easier for you to prove using the pumping lemma. Specifically, we say that if we assume (towards contradiction) that $\hat L$ is context-free, then there is some pumping length $l$, and we will define $w=(a^{l+10000}b)^{l+10000}\in \hat L$ (I chose a big number there for good measure, and for reasons you will se down below. This is usually not required). Now, by the pumping lemma, since $|w| \ge l$ we have some $x,v,y,u,z$ such that $w=xvyuz$ and are satisfying $|vyu|\le l$, $|vu|\ge 1$, $xv^nyu^nz\in \hat L$ for every $n\in\mathbb N$. Let us notice, that taking $n=0$ we get $xyz\in\hat L$ so there is some $k\in \mathbb N$ with $xyz=(a^kb)^k$ but since $|vu|\ge 1$ then $|xyz|\le|w|$ and thus $k\<n$. Notice that when we removed $v,u$, we removes **at most** 2 (or some other small constant compared to 10000) "groups" of $l$ "a" and 1 "b", and since that number is smaller than 10000... there must be some "group" that was not touched. i.e, it still had $l+10000$ "a" in it, therefore we must have $xyz=(a^{l+10000}b)^{l+10000}$ but then $xyz=w$ and so $|vu|=0$ in contradiction!

Thus $\hat L$ is not context free and so is $L$
> 0 votes

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


# Question
Title: Minimum pumping length of concatenation of two languages
there's this small part of my homework that I just can't figure out.

Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that

$$ p(AB)=p(A)+p(B) $$

But whatever I try, I can only find languages so that

$$ p(AB) \< p(A)+p(B) $$

I've been sitting at this the whole day and I'm just going in circles. Can someone please give me a hint?

# Answer
For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.

**Proposition**. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.

**Proof**. Let $w=w\_Aw\_b\in AB$, where $w\_A\in A, w\_B\in B$. Assume $|w|\ge P(A)+P(B)-1$. Then either $|w\_A|\ge P(A)$ or $|w\_B|\ge P(B)$; otherwise, $$|w|=|w\_A|+|w\_B|\le P(A)-1 + P(B)-1\lt P(A)+P(B)-1,$$ which contradicts the assumption.

Now there are two cases.

* $|w\_A|\ge P(A)$. Since $P(A)$ is a pumping length for $A$, $w\_a\in A$ can be written as $w\_a=xyz$, satisfying the following conditions:

+ $|y|\geq 1$
    + $|xy|\leq P(A)$
    + $\forall n\geq 0, xy^{n}z\in A$

Hence, $w$ can be written as $w=xyz\_B$, where $z\_B=zw\_B$, satisfying the following conditions:

+ $|y|\geq 1$
    + $|xy|\leq P(A) + P(B)-1$ (since $P(B)\ge1$)
    + $\forall n\geq 0, xy^{n}z\_B=(xy^nz)w\_B\in AB$.

That is, $w$ can be pumped with pumping length $P(A)+P(B)-1$.
* $|w\_B|\ge P(B)$. This case is similar to the case above.

Combining the two cases, we have proved $P(A)+P(B)-1$ is a pumping length for $AB$.

Let $A=\\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{n-1}, \beta^n, \beta^{2n}, \beta^{3n}, \cdots, \\}$, which is a regular language of minimal pumping length $n$. Let $B=\\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{m-1}, \beta^m, \beta^{2m}, \beta^{3m}, \cdots\\}$, which is a regular language of minimal pumping length $m$. Since $\alpha^{n-1}\alpha^{m-1}$, which is a word in $AB$ of length $n+m-2$, cannot be pumped, $AB$ is a regular language of minimal pumping length $n+m-1$.
> 3 votes

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


# Question
Title: Most cost effective way to traverse a set path
I have a set path of $N$ destinations to be visited in order, knowing the distance $D\_i$ between each one of them. I can traverse one node $i$ with the cost of $D\_i \times r$ or traverse any $5$ nodes in order with a set cost of $B$. How can I find the most cost effective way to visit all the destinations using dynamic programming?

# Answer
> 1 votes
Let us number the destinations from $1$ to $N$ and define an array $c\[N\]$ where $c\[i\]$ is the minimum cost to travel to destination $1 \leq i \leq N$. We wish to calculate $c\[N\]$.

It is clear that $c\[1\] = D\_1 \times r$, because if we find ourselves at destination $1$ we can only have gotten there by travelling one destination at a time, instead of travelling five destinations at a time.

The minimum cost of travelling to destination $2$ must be $c\[2\] = D\_2 \times r + c\[1\]$ for identical reasons ($2 \< 5$) as before. We add the minimum cost of reaching destination $1$ to the minimum cost of reaching destination $2$ because we must have travelled from destination $1$ to $2$.

Now we see that for destinations $i \geq 5$, that we could have reached them by travelling through five destinations at a time instead of the previous one destination at a time. This means $$c\[i\] = \min(B + c\[i - 5\], D\_{i} \times r + c\[i - 1\])$$

Where $c\[0\] = 0$. From this pattern, we can calculate $c\[N\]$ in $O(N)$ time complexity.

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


# Question
Title: MIPS pipeline: choosing between slowing down a stage and adding a new stage
> Suppose a new, more complicated, instruction is desired for this simple pipelined MIPS processor. Suppose, also, it could be implemented by either (a) adding new logic to the execute stage of the pipeline, or (b) adding a new stage (i.e a 6th stage) altogether. Assume that choice (a) would slow the execute stage down by 20%. Since choice (b) increases the number of stages by 20%, is the overall effect on execution the same? If not, describe how each choice affects execution time and indicate which choice is better.

This was a question in my exam, but I'm not sure if my answer to it is correct. Here is what I think:

If the execution stage time increased by 20%, then the new cycle time will likely be the time of the execution stage. So cycle time will increase by 20%.

Adding a new stage to the pipeline wouldn't affect the cycle time (assuming the new stage is shorter than or equal to the longest stage). It would increase the throughput, but also increase the latency of individual instructions by 20%.

So, no, they don't have the same affect on overall performance. The second choice is more efficient.

Now, am I correct?

# Answer
Your answer is probably correct for an exam.

In reality, adding a pipeline stage to MIPS is a major undertaking. The MIPS pipeline is very simple, that’s why it is taught in CS courses. Adding a pipeline stage adds a whole new level of complexity. Take an instruction sequence

```
X = A+B
X = C+D
Z = X+Y

```

In the current pipeline design, Z can just about be made to pick up the correct X - when C+D is stored, it goes directly into the first input of X+Y. With an additional pipeline stage, the second X is nowhere near ready when the third instruction starts. So you must make that instruction wait. But only because X isn’t ready in time. Since you don’t want to *always* wait, you need to detect this and add logic for that. And then the question is how often does this happen.

The alternative is that instructions using the second pipeline stage - and only those - stop all the other stages from progressing. So the timing would be the same as if this instruction was two instructions. In that case you could just make it two instructions.
> 1 votes

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


# Question
Title: Find the n best choices while maximizing value
**Given:**

* A list of slots (A, B, C, ...)
* Every slots supports a list of choices (C0, C1, C2, C3...)
* Every choice has a value

All slots must be filled with at most n different choices. The sum of the values should be maximized.

**Example:**

Choice-Values:

* C0 = 4
* C1 = 3
* C2 = 2
* C3 = 1

Slots:

* A: C1, C3
* B: C0, C1, C3
* C: C2, C3
* D: C0, C1, C2, C3
* E: C1, C2, C3

Solution for n = 1: C3, C3, C3, C3, C3

Solution for n = 2: C1, C1, C2, C1, C1

**Question**

Is this a known problem?

It reminds me of a mix between the knapsack problem and of a scheduling problem, as I want to get the maximum value while filling a certain space using a limited set of items.

# Answer
> 1 votes
Thanks to Yuvals comment i found this site discussing the set cover problem. It's exactly what I needed.

---
Tags: optimization, knapsack-problems, set-cover
---


# Question
Title: How to trigger a thread to start working using semaphore?
How to trigger a thread to start working using semaphore?

I have find a lot of explanation about thread and semaphore but i still don't understand, any help please

# Answer
> 1 votes
When using semaphores or locks, you don't do anything else than *acquiring* the semaphore (resp. the lock), and then do what you want. For example, if you want to use a lock, then you typically have two threads

```
# thread 1
lock.acquire()
# here is all the work for thread 1
lock.release()

```

and the other thread is completely identical:

```
# thread 2
lock.acquire()
# here is all the work for thread 2
lock.release()

```

Now, the *first* to obtain the `lock` gets to run the code first, and the other thread needs to wait until the `lock` is released.

Here's an example of a Python program that prints a series of `0`s and `1`s depending on the order of execution:

```
import time
import threading

lock = threading.Lock()
lst = []

def f1():
    for i in range(10):
        lock.acquire()
        lst.append("0")
        lock.release()
        time.sleep(0.1)

def f2():
    for i in range(10):
        lock.acquire()
        lst.append("1")
        lock.release()
        time.sleep(0.1)

t1 = threading.Thread(target=f1)
t2 = threading.Thread(target=f2)
t1.start()
t2.start()
t1.join()
t2.join()

print("".join(lst))

```

Feel free to run it in your own terminal.

(Note that I used `lock.acquire()` and `lock.release()`, but the "correct" way is to use a context manager and use `with lock: ...`.)

See also: Lock, mutex, semaphore… what's the difference?

---
Tags: threads, semaphore
---


# Question
Title: Asymmetric Transition Probability Matrix with uniform stationary distribution
I am solving a discrete Markov chain problem. For this I need a **Markov chain** whose **stationary distribution** is **uniform(or near to uniform distribution)** and **transition probability matrix** is ***asymmetric***.

\[ Markov chains like Metropolis hasting has uniform stationary distribution but transition probability matrix is symmetric \]

# Answer
Take the matrix $A$ such that for every $i$, we have:

1. $A\_{i,i} =0.5$
2. $A\_{i,i+1}=0.5$ (for $i=n$, set $A\_{n,0}=0.5$)

Then it is not symmetric, but has a uniform stationary distribution.
> 0 votes

---
Tags: markov-chains
---


# Question
Title: Describing the Bool-And monoid in terms of categories
Normally I put the question before the context, but in this case I want to admit the possibility that the context and my understanding nullify the question. Plus it helps me think through my question.

I recently started reading Category Theory for Programmers (Bartosz Milewski), and this is my understanding of categories: they are "algebraic structures" which consist of objects and arrows/morphisms between those objects. The morphisms have to obey the laws of associativity, so

$$ a \rightarrow ( b \rightarrow c ) = ( a \rightarrow b ) \rightarrow c $$

And there must be an identity morphism for each object.

Now, Milewski goes on to explain that monoids (which I'm pretty comfortable with in the set-theoretic sense) are also viewable as categories. This is the part I am having trouble with. One of the exercises in the book is to consider the Boolean-and monoid (booleans with the and operator) as a category:

> Represent the Bool monoid with the AND operator as a category: List the morphisms and their rules of composition.

I want to give some examples, which I'll do in a SML (though I'll borrow Haskell names).

The monoid could be described set-theoretically with the following signature:

```
signature MONOID = sig
  type m
  val mempty : m
  val mappend : m -> m -> m
end

```

Further, the monoid for booleans with the and operator would be given as

```
structure BoolAnd : MONOID = struct
  type m = bool
  val mempty = true
  fun mappend x y = x andalso y
end

```

So, here is my understanding of this monoid as a category and its morphisms: is it correct?

* The objects in the category are booleans (true and false) and functions from booleans to booleans
* `BoolAnd.mappend` is a morphism from the former to the latter
* `mappend true` is an identity morphism for the function objects in the category (I say "an" because isn't the actual identity function `fun id x = x` also an identity morphism for the functions, thanks to polymorphic types? Or does that not count in category-land? I know that `mappend true` is equivalent to the identity function under composition of functions with type `bool -> bool`.)
* the identity morphism for boolean objects appears to be just `fun id (b:bool) = b`
* the given identity morphisms should be associative:

```
(* example, not proof *)
- open BoolAnd;
- (id o (mappend true)) o not;
val it = fn : bool -> bool
- it false;
val it = true
- id o ((mappend true) o not);
val it = fn : bool -> bool
- it false;
val it = true

```

The rules of composition seem to be that `mappend true` is the identity, while `mappend false` is a "sink" of sorts, causing the resulting function to always return false. But `id` and `mappend` don't directly compose, because the types do not align (when `id` is specialized to booleans, as in the bullets above).

Am I missing something? Is something wrong? Did I give too much detail (there seems to be an emphasis on avoiding digging in to the objects too much)?

I ask this both to confirm my understanding so that I have a good foundation for the remainder of the book and also because it took me a long time to identify the objects and morphisms at work; some of them I am still shaky about.

# Answer
> 2 votes
Monoids are *one-object* categories. The elements are morphisms, monoid multiplication is composition and the monoid identity is the identity morphism.

In the case of Booleans-with-AND the monoid is $M = (\\{\top, \bot\\}, \land, \top)$. The category therefore has a single object (we could call it $M$) with two morphisms $\top : M \to M$ and $\bot : M \to M$. Composition is given by $\land$ and the identity morphism is $\top$.

---

To give a little more context, there is a way to view a monoid in such a way that the objects are the elements of the monoid: as a discrete (no non-identity morphisms) monoidal category. *Category Theory for Programmers* covers the topic of monoidal categories in Chapter 22, "Monads Categorically".

---
Tags: category-theory
---


# Question
Title: Theoretical lower bound of finding number of occurrences of a target integer in a sorted array
> Given a sorted array of integers and a target integer, find the number of occurrences of the target integer.

It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the size of the array. For example, given an array $\[1,2,3,3,4,5\]$ and a target $3,$ the algorithm should return $2$ since there are two copies of $3$ in the array.

> Question: Is there a faster algorithms which has time complexity less than $O(\lg n)?$ Otherwise, is there a proof to prove that $\Omega(\lg n)$ is the theoretical lower bound?

# Answer
The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument.

Say that the target is zero. If the first access to the array is left of center, answer $-1$, and mentally set the elements to the left to be $-2,-3,\ldots$. If the first access is right of center, answer $+1$, and mentally set the elements to the right to be $2,3,\ldots$.

Suppose the first access was right of center, say position $i$, and consider the second access. If it it to the right of the first access, then you already know what to answer. Otherwise, there are two cases. If the accessed position $j$ is less than $i/2$, answer $-1$ (and fill in elements to the left). If it was more than $i/2$, answer $+1/2$ (and fill in elements to the right up to position $i$).

Continuing in this way, at each step the number of positions which could contain the target element is at most halved at each step. Finally, when only one element is still at stake, without querying it, the algorithm cannot know for sure whether the array contains the target element or not. It takes $\log\_2 n$ steps to reach this step.

The foregoing actually shows that binary search is optimal for searching a sorted array.
> 4 votes

# Answer
There are $n$ possible answers. Each comparison gives you at most one bit of information. You need at least $\lg n$ bits of information to describe the answer, so you'll need at least $\lg n$ comparisons.
> 3 votes

---
Tags: algorithms, complexity-theory, sorting, search-algorithms, binary-search
---


# Question
Title: How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem
I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:

```
LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

```

A simple path is a path without any repeated vertice, i.e. every vertice can be visited just one time. The length of the path is given from the edges of which it is composed.

So how can I show that LPATH is an NP-Complete problem using the Hamilton path problem as an NP-Hard problem as reference?

# Answer
Welcome to the site!

A Karp reduction from $\mathrm{Hamiltonian Cycle}$ could work as follows: Given a graph $G = (V, E)$, we construct $\mathrm{Long Path}$-instance $(G', v, v', |V|)$ where $G'$ is obtained by adding a copy $v'$ of some arbitrarily chosen vertex $v \in V$ (including its edges). Note that this instance can be constructed from $G$ in polynomial time.

To see that this is a correct reduction mapping, we see that a Hamiltonian cycle $C$ in $G$ induces a path between $v$ and $v'$ of length $|V|$ and vice versa.

Thus, we have a polynomial reduction $\mathrm{Hamiltonian Cycle} \leq\_\mathsf{P} \mathrm{Long Path}$, thus showing that your problem is $\mathsf{NP}$-hard (because $\mathrm{Hamiltonian Cycle}$ is $\mathsf{NP}$-hard already).

To show that $\mathrm{Long Path}$ is in $\mathsf{NP}$ we note that a path in a graph can be efficiently encoded as a list of its edges and checking that a string actually encodes a path in the graph and then counting the number of edges to determine whether it is long enough can be done in polynomial time.

Hence we find that $\mathrm{Long Path}$ is $\mathsf{NP}$-complete.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard
---


# Question
Title: What would be the practical consequences of ZPP=exptime
What would be the practical consequences of ZPP=exptime. It would be pretty ridiculous if the was true but what if it was?

# Answer
If **ZPP** = **EXPTIME** then **NP** $\subseteq$ **ZPP**, which implies **NP** $\subseteq$ **BPP**. As described in Russell Impagliazzo's informal paper "A personal view of average-case complexity", we would be living in a world he calls *Algorithmica*.

> Algorithmica is the world in which $P = NP$ or some moral equivalent, e.g. $NP \subseteq BPP$. \[...\]
>
> Such a method of automatically producing a solution for a problem from the method of recognizing a valid solution would revolutionize computer science. Seemingly intractable algorithmic problems would become trivial. Almost any type of optimization problem would be easy and automatic; for example, VLSI design would no longer use heuristics, but could instead produce exactly optimal layouts for problems once a criterion for optimality was given. Programming languages would not need to involve instructions on how the computation should be performed. Instead, one would just specify the properties that a desired output should have in relation to the input.

And so on. Read the paper for more extrapolation on this topic, along with the consequences of less fantastic algorithmic complexity conjectures being true. And observe @Dmitry's caveat: Knowing a problem is in a tractable complexity class isn't the same as having an efficient algorithm for the problem that takes advantage of that fact.

Theoretically, **ZPP = EXPTIME** implies **EXPTIME** $\subseteq$ **BPP**. Since we already know **P** $\subset$ **EXPTIME** we have **P** $\subset$ **BPP** as well, which means there are some polynomial-time randomized algorithms that cannot be derandomized. This is another way of saying that pseudo-random number generators will never be as effective as true randomness, algorithmically, which would be a very interesting result.

We know that **BPP** is low for itself, i.e. **BPP$^{BPP}$ = BPP**. Therefore an **EXPTIME** no more powerful than **BPP** must be low for itself as well, which removes the separation between some exponential classes, e.g. **EXPTIME = EEXP = EE = EEE**. This in turn makes some decidable but intractable problems simply decidable. For example, deciding the truth of first-order mathematical statements expressed in Presburger arithmetic would now be in **BPP**.

We also know that **BPP** $\subseteq \Sigma^P\_2 \cap \Pi^P\_2$. Together with **EXPTIME** $\subseteq$ **BPP** this means that the polynomial hierarchy collapses to the second level; the oracle calls above that level do not offer any more computational power, as **EXPTIME** is powerful enough to capture all the rest of **PH**. Since **P** is strictly a subset of **BPP** and **P** = **NP** would collapse **PH** completely, bringing **P** and **BPP** together, **ZPP** = **EXPTIME** would imply **P** $\neq$ **NP**.

\[Edit\] **NP** = **co-NP** would also be settled in the affirmative.
> 1 votes

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


# Question
Title: Exercise: Sliding window protocol: Bits for sequence number
This is a task in a lecture on computer networks:

"Suppose you are designing a sliding window protocol for a 1-Mbps point-to-point link to the moon, which has a one-way latency of 1.25 seconds. Assuming that each frame carries 1 KB of data, what is the minimum number of bits you need for the sequence number?"

R = 1-Mbps = 125KBps

d\_prop = 1.25 sec so I assume RTT = 2.5 sec

The solution I was given ignores the transmission delay but I calculated it to be

d\_trans = 1KB/125KBps = 0.008s

Within one second you can put 125 frames into the link if you allow full utilization. I assume the task ignores the size of the acknowledgements as well as the processing and transmission delay of the receiver for simplicity. Nothing else is said about the links properties.

Since within 1 second you could send 125 frames, within 2.5 seconds you could send. 312.5 frames. If we include the senders d\_trans then within 2.508 seconds we could send frames 313.5 frames until the acknowledgement for the first frame should be received. If you complete the LastFrameSent then I think you should need a send\_window\_size(SWS) of 314 to acknowledge each frame individually. In this case you would need Ceil(log2(314)) = 9 bits for the sequence numbers.

The solution given by the tutor says that you need at least 10 bits and part of the explanation I noted down is that (ignoring d\_trans) you can send 312 frames until the first frame is received. And then you can supposedly send another 312 frames until you receive the first ACK back, so you'd need a SWS of 624.

So did I misunderstand anything about the task or did the tutor make an error by doubling the one-way-latency (which I assume to be the same as d\_prop) twice? Can additionals assumptions be made regarding the properties of the link?

I saw a similar question where the link was considered the be a full-duplex link (which wasn't explained in the lecture iirc). But even if you'd consider a full-duplex link which means only the half of the bandwidth may be used then you could only send ~156 frames until you get the ACK and then you'd need 8 bits instead of 10, right?

Thank you for your help.

# Answer
Assuming SWS(sender window size) = RWS(receiver window size)

In this case Assume a scenario where SWS = RWS = 3 so MaxSeqNum = SWS - 1 = 2

LAF(Last Acknowledged frame) LFS(Last Frame Sent)

Sender = { \[ 0, 1, 2 \], 0, 1, 2, 0, 1, 2}

`Note:
Sequence of packets waiting on the queue.
Square bracket represent the window`

Receiver = {0, 1, 2, \[0, 1, 2\], 0, 1, 2}

Here the packets 0, 1, 2 are obtained and window is moved further acks sent by the receiver.

but acks are lost in traffic.

So the sender didnt got the acks thinks that the packets have lost and sends the first window packets with sequence numbers 0, 1, 2. In this case the packets received are actually not distinguished by the receiver.
> 0 votes

---
Tags: computer-networks, protocols
---


# Question
Title: Where should I start to understand how computers work?
I am interested in how computers work but I have no idea how the concept of 0's and 1's converts to making possible for people to control a computer by programming. I would like to understand from very fundamental levels of computer and continue studying more in depth until I am satisfied. Where should I start? Is there a name for this topic? What books should I read?

\**Edit: This was my first post and I think I got a lot of good suggestions on where to start. I will be looking up all the answers posted here. Thanks a lot for everyone who answered on this post.

# Answer
Three books:

### 1. Code: The Hidden Language of Computer Hardware and Software by Charles Petzold

> Using everyday objects and familiar language systems such as Braille and Morse code, author Charles Petzold weaves an illuminating narrative for anyone who’s ever wondered about the secret inner life of computers and other smart machines.

### 2. But How Do It Know by J. Clark Scott

> But How Do It Know? really explains how computers work. They are far simpler than anyone has ever permitted you to believe. It contains everything you need to know, and nothing you don't need to know. No technical background of any kind is required.

### 3. Elements of Computing Systems by Noam Nisan and Shimon Schocken.

Available online to read for free, and also as a free video course by the authors on Coursera: Part 1, Part 2 famously called Nand To Tetris. The course website is nand2tetris.org. While the first 2 books can be read through, this has exercise that you must go through to understand the material. A pre-requisite of a basic programming course in any language.

I recommend picking either of 1 or 2 and then proceeding to 3. Code is more detailed, but How Do it know covers a bit more topics. Both the first books cover fairly similar ground, which is mostly the first half of the nand2tetris course.
> 4 votes

# Answer
You're asking a very broad question that isn't particularly easy to answer "*correctly*".

What you are describing is what you learn if you follow through with a degree in *computer science* or maybe more precisely in *electrical engineering and computer science*.

So I would recommend you to do exactly that: Go to you favorite university websites and look up what the content of a degree in EE/CS is.

For example, I've heard that MIT has a degree in EECS, so I looked it up, and found a long list of courses.

There I found a course called 6.01 — Introduction to Electrical Engineering and Computer Science I which even has a downloadable *lecture notes* document:

> 6.01 Course Notes, Spring 2011 (PDF - 4.9MB)

in which the basics of *circuits* are covered in Chapter 1.

---

**Summa summarum** you're asking for what goes into a degree in electrical engineering and computer science, and the best way to find the answer to that is to go to the source.

Universities and schools exist for a reason. :)
> 10 votes

# Answer
Depending on how narrow we understand the question, the answer might be (parts of) a single university course instead of a whole degree.

A course on the design of digital circuits as taught at ETH Zurich includes how to get from boolean logic (i.e. conceptual ones and zeros, but not their physical implementation) to modern computers that you can program - although only in assembly, i.e. a very simple programming language. The link goes to a lecture website including recorded lectures and practice material.

To get from physics to the boolean logic (conceptual zeros and ones) you would need an electrical engineering or even physics course (depending on the level of detail you want) on semi conductors and transistors in particular.

To go from the simple programming language to more advanced ones you would need a course on compiler design like this one.
> 3 votes

---
Tags: computer-architecture, programming-languages, education, introductory-lesson
---


title: Is every linear language in NL?

text:
# Question
Title: Is every linear language in NL?
I wonder if all the linear languages are in NL?

I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the language can be written in linear normal form, the machine accepts. The work tape only needs to store the current production, so that it works in logarithmic time.

Am I completely lost or is this a good start?

# Answer
The following survey states that the result is proved by Ibarra, Jiang, Ravikumar in Information Processing Letters (1988).

Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits. Niedermeier R., Rossmanith, P., Information and Computation 118(2), 227-245, 1995.
> 2 votes

---
Tags: complexity-theory, context-free, space-complexity, complexity-classes
---