Bankers algorithm - How does it work? I'm currently studying deadlocks and I'm trying to learn myself the bankers algorithm.
In this example my teacher goes to B first, then C and finally A.
He adds (I think) 2 (row b, Has) with 3 (free) and then gets the new Free value 5.
After that he proceeds to row C where he adds 2 (row c, Has) with the free value 5 which gives us a new free value of 7.
After this he goes to the last row A and adds 3 to seven which gives him the free value of 10.
This does not cause a dead lock and I'm wondering why, Isn't he over the Max value of row A?

Here is another example in which the first image is included, but there is also one scenario when we get a dead lock. I don't really understand why since we still get 10 free like the rest of the examples.
Sorry if this is a bit confusing. I can simplify if its needed.

To understand this problem you have to understand the rules for the safety checks. I am not going to give a detailed explanation of these but you can go here to read more about it. I will try to give an explanation of why C request 1 is safe but A request 1 is not.

There is a value associated with a process and a resource called need. The need is an n-tuple where n is the number of different resources. In this case n is just 1. Calculating the need is just taking the max and subtracting the has for each resource. And there is a safety check that if no process has a need less than or equal to the n-tuple of available  resources after a request then that request should be denied.

For C requests 1 it appears that the previous state is after B requests 1. In this C request 1 step we see A has a need (6), B has a need (1) and C has a need (4). Since there is only one resource the n-tuple of available resources is just (1) so this can be granted as B has a need of (1).

For A requests 1 the previous state is the initial state. We then calculate the need of A is (5), B is (2) and C is (5). And the resulting n-tuple of available resources is (1). There is no need which is less than or equal to this so we should reject it.

Be careful when reading more about the subject. The notation is often different, the letters A,B and C are often used to represent resources and p's will be used for processes. You will also be dealing with n-tuples of greater values.


Why we cannot prove that a computable function is total? We know that we cannot find an algorithm that would prove that a computable function "f" is total if it IS total. How come?

When a function is total, it must have a proof (derived from soundness and correctness of logic). And proof is a finite sequence of symbols, so why does simple enumeration through all the sequences (which ends in finite time) not provide us with a proof?

You misunderstand soundness and completeness of logic. You think that it says:

  A statement is true if, and only if, it is provable.

But it really says:

  A statement is true in every model if, and only if, it is provable.

It can happen that there is a model in which a statement is true but not provable. What if you live in such a model? Then it could happen that in the model in which you live there is a total function $f$, but there is no proof that $f$ is total.

Here is a precise mathematical reason why your thinking does not work. I am going to show that, whatever formal system you are using (so long as it is a reasonable one), there is a total function which your formal system does not prove to be total.

You do proofs in some formal system $T$ (for instance, $T$ could be first-order logic and Zermelo-Fraenkel set theory) whose axioms are computably enumerable (or else you're a mystic guru). Let us also assume that $T$ contains arithmetic, and that $T$ is consistent (or else you're mad).

Define the following function f

def f(n):
    if n encodes a proof of 0 = 1 in formal system T:
        while True: pass
    else:
        return 0

Observe that f is total if, and only if, $T$ is consistent:

if $T$ is consistent then it does not prove $0 = 1$, hence f never enters the infinite while loop.
if f is total, then it never enters the infinite while loop, therefore no $n$ encodes a proof of $0 = 1$ in $T$, therefore there is no proof of $0 = 1$ in $T$, which means that $T$ is consistent.

Because $T$ is consistent, f is total.

But $T$ does not prove that f is total: if it did, then it would prove that, for every $n$, $n$ does not encode a proof of $0 = 1$, but this would imply that $T$ proves its own consistency, which it cannot by Gödel's incompleteness theorem.


Maximizing the sum of selected elements in a matrix I’m trying to find an efficient algorithm for the following optimization problem:

Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such that the sum of the elements is maximized, subject to the constraint that any index of $a_{ij}$ is only used once. In other words: if element $a_{ij}$ has been selected, no other elements from rows and columns i and j can be selected.

Notes:
 - It is allowed to select elements from the diagonal.
 - The order of magnitude of $k$ is 10,000.

I have a dynamic programming algorithm but the downside is that it can't be parallelized.

The problem resembles the assignment problem. This can be solved using the Hungarian Algorithm, which can be easily parallelized using Java 8 streams. However, the assignment problem has the constraint that from each row and column only one element can be selected. This is less strict than above problem since it allows to select both $a_{ij}$ and $a_{ji}$.

Question: do you know how to adjust the Hungarian Problem for the stricter constraint?

Context:
This algorithm is used to optimize large-scale power storage, which can be modelled as a collection of spread options.

The problem you want to solve is (a slight variation of) maximum weighted matching in general (i.e., not necessarily bipartite) graphs.  There are several algorithms with various worst-case bounds:

"Data structures for weighted matching and nearest common ancestors with linking" (Gabow 1990) is the best "in theory" with $O(nm + n^2\log n)$ time complexity.
"Faster scaling algorithms for general graph-matching problems" (Gabow and Tarjan 1991) has time complexity $O(m\log(nN)\sqrt{n\alpha(n, m)\log n})$, where $N$ is the largest cost value and $\alpha(n, m)$ is the very slow-growing "inverse Ackermann" function.
"Computing minimum-weight perfect matchings" (Cooke and Rohe 1999) describes the "Blossom IV" algorithm, which apparently performs well in practice despite a theoretical worst case $O(n^3)$ time.  The paper also gives a good overview of existing algorithms.
"Implementation of $O(nm\log n)$ weighted matchings in general graphs: the power of data structures" (Mehlhorn and Schäfer 2002) apparently performs even better in most cases, and also comes with a better worst-case guarantee.  There is an implementation in LEDA.
"Blossom V: A new implementation of a minimum cost perfect matching algorithm" (Kolmogorov 2009) claims to outperform the previous algorithm a majority of the time.

The above algorithms don't allow "self-edges" (choosing elements along the diagonal).  To accommodate these, for every vertex $v_i$, create an extra vertex $u_i$, and an edge $(v_i, u_i)$ with weight $a_{ii}$.

Note that while some of these papers talk about the maximum weight perfect matching problem, in which we have the additional constraint that every vertex must be incident on an edge in the matching, you can turn any instance of the plain maximum weight matching problem into an instance of the perfect kind by adding, for every existing vertex $v_i$, a new vertex $v'_i$, a zero-cost edge $(v_i, v'_i)$, and another zero-cost edge between every pair ($v'_i, v'_j)$ of new vertices.  (Perhaps another construction using fewer zero-weight edges is possible?)

I found most of the above information in https://people.mpi-inf.mpg.de/~mehlhorn/ftp/WeightedMatchings.pdf, which has a lot of useful information on implementation and theory.


Fastest possible way to check what of X is in a string I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings.

example: I have the matches "dog", "cat" "apple" and the string "The dog chases the cat".

In this example would I like an algorithm that returns "dog" and "cat".
I do not care, how many times, or where in the string it is, I just want to know what of my matches exists.

The fastest algorithm i can think of for this is $\mathcal{O}(nm)$ where $n$ is the length of the string, and $m$ is the count of matches.

But my question is are there an algorithm out there, there can do this faster then $\mathcal{O}(nm)$?

You can do that using Knuth/Moris/Pratt(kmp), the build table portion of algorithm is $O(m)$ and the search part is $O(n)$, being n the size of text and m the size of the pattern, to be more accurate, if you have 3 potential pattern, you'll do that in $3 * O(n+m)$, because you'll probably have to search it 3 times and build 3 tables.

As you problem is about having the pattern or not, once you find one, you can break the loop and that ofc counts as an optimization. If the pattern are static, by this I mean, they probably are always the same, you may store the prefix-table content of each pattern and that will make $O(m)$ one time, next time it'll just be $O(n)$.


Is Turing machine a programmable machine or Is it like a fixed program computer? We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing machines,we give full description of TM including transition table (which is equivalent to stored program in RAM model). So should it be considered like a stored program computer? Because for two different languages L1 & L2 we give two different TMs T1 & T2. We never describe two different transition table for same TM.

Your regular stored program computer could be compared to the Universal Turing Machine (UTM) in that it can be seen as a multipurpose device. Any concrete UTM, nevertheless, still accepts only one base level language, as does the computer that you are using right now. "On top" of that language, other languages can be encoded, and the fact that programs/machines can be processed as data is what gives computers an enormous range of applications, or even "incarnations", which we have just begun exploring.

To answer your question directly: a TM that is programmable is also "fixed", depending on how you see it. Conversely, a machine doesn't have to be as powerful as the UTM to be considered programmable, in some way. In fact, many (very) useful languages are not Turing equivalent.

Regarding computational languages/machines, the notion that there would be something like a "proto-language", or "proto-machine" is misleading. The mythology that has been built around the general-purpose computer obscures its candid nature. The Universal in "Universal Turing Machine" should not be equated to absolute. It is a proposed definition of universality, mathematical in nature, which has been ever since reinstated, repeatedly, in so many ways that it is impossible to describe exhaustively.


Explanation of implementation of an algorithm for Dominating Set I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices...
So, I have found a well developed, gorgeous implementation of the needed algorithm.

It is a bit complicated for me, I would like to ask for some description for code above. How is it working? I would like to get only a short summary.

This algorithm just tries every subset of the vertices and calculates whether it is a dominating set.  It tries the subsets in increasing order of size, and halts whenever it finds one.

Note that the running time is $O(2^n n)$ so it is exponential, and quite badly so.  There are faster algorithms that compute dominating sets in $O^*(1.7^n)$ or even $O^*(1.5^n)$ time, but I don't recall whether they are implementable.

By the way, dominating set, being W[2]-complete, is not expected to have an algorithm running in time $f(k) \cdot \text{poly}(n)$ for any function $f$ where $k$ is the size of a minimum dominating set.


Optimal path - best career I am new and I have to develop an algorithm with a 2d integer array as input to compute the best career path.
Lets consider a network with n nodes, which are numbered from $1$ to $n$.
All are connected one to the other.

To move from node $i$ to node $j$ can have different costs (classical example job changing):

positive value indicates a benefit
negative value indicates a loss
some steps have a cost of $0$

Each entry of $B[i, j]$  indicates the beneﬁt (or the cost, if negative), of a step from node $i$ to node $j$.

I need to find out the maximal gain of a path from i to j is

$$
G(i, j) = \max { \{ g(p) \mid \text{ p is a path from i to j} \}  }
$$

It is not possible to gain from walking in a cycle.
This means, the values in B must be such that for any path p from a node i to itself, we have $g(p) \leq 0$.

Ex of matrix B:

$$
\begin{array}{cc}
 0 & 1 & 0 & 1 \\\\
−2 & 0 & 0 & −2 \\\\
 0 & 2 & 0 & 1 \\\\
−3 & −1 & −3 & 0
\end{array}
$$

Hints:

1) Cycles bring no gain. Therefore, the greatest possible beneﬁt of moving
from $i$ to $j$ can be achieved by visiting any intermediate node at most once.

2) Consider the following variant of the problem. Let $G_{aux}(i, j, k)$ be the maximal gain that can be achieved by walking from $i$ to $j$ along a path that uses only the nodes $1, \ldots, k$ as intermediate points.

The tasks asked:

Explain how $G_{aux}(i, j, k)$ can be used to compute $G(i, j)$. Develop a recurrence for $G_{aux}(i, j, k)$.
Write pseudo-code for algorithms that compute arrays with all values of
$G_{aux}$ and $G$ and explain why your algorithms are correct.

Who can help me with this tasks?
Is the basis of all this task the Floyd-Warshall's algorithm ? right?

Be sure to complete the first task before reading below.

Hint 1:

   What are the conditions necessary to use the Floyd-Warshall's algorithm? Does it match those of your exercise?

Hint 2:

   Well, I think you are ready to write the corresponding pseudo-code :-)


Complexity of an algorithm with multiple inputs I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$.

But what about when the complexity depends on several inputs? For example if an algorithm has complexity $O(n^2k)$, is it 'cubic', or maybe 'quadratic in $n$ and linear in $k$'?

I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

[If I have time, I'll answer the rest of the question later.]

  I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

It's vague, unfortunately, and you should avoid writing anything like this, ever.  It means at the very least, that the complexity depends somehow on $k^3$ and $n^3$ but I'm sure you'd already figured that out.  Beyond that, it's impossible to say much. It's unclear whether it's some function of $k^3+n^3$ or some function of $k^3n^3$ or something else.  It's also unclear whether they're talking about an upper bound or a lower bound: if I told you that a recipe needs a kilo of potatoes, you'd assume that was an upper bound, but if I told you that a restaurant needs kilos of potatoes, you'd assume a lower bound.


How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$ Lately, I asked this question to find the maximal set of elements $S$ of a given array $T$ such that every element of $S$ is greater than or equal to the cardinality of $S$.

My question is now different. How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$.

For example, if $T=[9, 8, 2, 2, 1]$, then all maximal sets that satisfy the condition are $S_1=[9, 8]$, $S_2=[9, 2]$, $S_3=[9, 2]$, $S_4=[8, 2]$, $S_5=[8, 2]$ and $S_6=[2, 2]$.

My recursive solution or the solutions given in the previous question do not generate all maximal sets.

Is there any efficient algorithm that finds all maximal sets of such problem?

I think one way to solve the problem is to find a maximal set $S$ and return its size $|S|$--using any algorithm from this question. Then, generate all combinations $\displaystyle\binom{|T|}{|S|}$ and find which one of these combinations satisfies the condition. But can we do better?

Assuming that by maximal sets you mean sets of maximal size (rather than sets which are inclusion-maximal), then there is a very simple algorithm. First, find the maximal size $s$. Second, filter out all elements smaller than $s$. Third, output all subsets of size $s$ of the remaining elements.


Set theory and computer science It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science?

Is it possible to define algorithms as a first step? More specifically, how to define "if x = 1 then y else z"? How about loops?

It all depends what you consider "computer science."

For what I would call "classical computer science" i.e. the theory of Algorithms, Turing Machines, etc. it can all be modelled in set theory.

A Turing Machine is just a tuple (which can be modelled using sets): a set of states, a tape-alphabet set, a transition function, etc. All of these are set-theoretic constructs, and even with nondeterminism, we replace the transition function with a relation, which is again set theoretic.

Similarly, we can define the semantics of programming languages using sets. Usually this just boils down to a big-step or small-step operational semantics, which again, is just defining relations.

Where things get iffy is with the so-called "alternate foundations of mathematics". This includes things like:

Martin-Lof type theory
Coqand's Calculus of Constructions
Homotopy type theory

They provide alternate sets of axioms from which mathematics can be built up. For example, the usually discard excluded middle and axiom of choice. Homotopy type theory, for example, introduces the Univalence Axiom.

These systems tend to be heavily oriented towards computation through the Curry-Howard Correspondence, so that a proof can "run" on a computer. So they don't quite fit into ZFC, but are generally considered part of computer science.


Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction? Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?

Multiplication can inherently be computed faster than division because it parallelizes better.

If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.

ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.

In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.

If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta_y}{\Delta_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$).
More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,

$$y=\left\lfloor\frac{\Delta_y}{\Delta_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta_yx+\Delta_x\epsilon}{\Delta_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.

The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta_y$ to the remainder, or increment the quotient and add $\Delta_y-\Delta_x$ to the remainder).

When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in fixed-point arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.

$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=[2^n\Delta_y/\Delta_x]$ and $e=[2^n\epsilon]$. The "division" is implemented with a fast shift.


ignoring overflow in two's complement addition of numbers with different signs[specific case] I understand the rule says that overflow cannot happen for two's complement addition of numbers with different signs, but do not understand why this specific case does not cause overflow:

 1001010
+0010101
--------
 1011111

Am I simply misunderstanding the actual rule or missing a step somewhere?
Thanks in advance!

EDIT: removed an extra 1 in the result

Okay, let's take a look at your example:

 1001010
+0010101
--------
 1011111

Your numbers here only have 7 bits, so we have a smaller range than we typically deal with.  Nevertheless:

$1001010$ is

$-64 + 8 + 2$, which is $-54$.

$0010101$ is

$16 + 4 + 1$, which is $21$.

$21-54$ is $-33$.  Let's see whether our answer matches up:

$1011111$ is

$-64+16+8+4+2+1$, which is $-33$.

An intuitive way to think about this is that the number space is divided entirely in half (with $0$ acting as a positive number).  So, with the standard 8 bits, your numbers range from $-128$ to $127$.  There is no positive number from within that set that you could add to a negative number from that set and get a number either above $127$ or below $-128$.


Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only interested in the design, no coding. I believe I can use the approach of kd-trees assuming that the query line is also axis aligned, say x-axis. Any help will be pretty much appreciated. Thanks in advance

If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $(y,z)$-plane and answer the following question:
Given $n$ axis aligned rectangles and a query point $p$, report the rectangles containing $p$.

To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that you start building your segment tree according to the projections of your rectangles on one dimension (say $y$) and instead of having some interval $I$ as a leaf, you replace it with a segment tree storing all projections on the $z$-axis of rectangles whose projection on the $y$-axis contain $I$.

You can then query a point by going down the tree and looking for all rectangles which are potential candidates according to their $y$-coordinates and then check among those which "fit" according to their $z$-coordinates.

This leads to $O(n\log^2(n))$ space used, $O(\log^2(n))$ time per query and $O(n\log^2(n))$ construction time.


Difference between "sort" and "universe" A very basic question.
As title, what is the difference between "sort" and "universe" in type theory?
Are they interchangable?
Or are there only finite number of sorts, but infinite universes?

Sort is (typically, though see Pure Type Systems) a meta-level concept and universes are an internalization of a particular case of a sort.  The second chapter of Bart Jacobs' thesis covers a fairly general case of how sorts interact with a language.  I'll be roughly following that.

I'll use the terminology $T$ is a type of sort $s$ if $T : s$ and $e$ is a term of type $T$ if $e : T$, so terms are always "grandchildren" of some sort, and types are always "children".  $s$ is a sort if we can introduce variables of a type of sort $s$ into the context, i.e. $$\frac{\Gamma\vdash A : s}{\Gamma, x:A\vdash x:A}$$

If there were no dependencies between sorts, we could almost say a sort was an index into a collection of contexts, which leads to the notion of dependencies between sorts.  We say $s_2$ depends on $s_1$ when types of sort $s_2$ can contain terms of sort $s_1$, i.e. if $$\frac{}{\Gamma\vdash A:s_1\qquad \Gamma,x:A\vdash B:s_2}$$ then it can be the case that $x$ occurs free in $B$.  Without the dependency it would necessarily be the case that $x$ was not free in $B$.

That's all that is required to be a sort.  Many additional features can be specified such as the existence of function types of sort $s$ built out of other types of sort $s$.  One feature we can add (called axioms in Jacobs' thesis), is the fact that one sort is a type of another sort, i.e. $s_1 : s_2$.  This internalizes the types of sort $s_1$ as terms of sort $s_2$.  If we want to embed $s_1$ into $s_2$ so that terms of $s_1$ are terms of $s_2$, we can add what Jacobs calls an $(s_1,s_2)$-inclusion.

A universe is then a sort that is closed under all the operations in the language.  A hierarchy of universes means that we further internalize the types of every universe and have an embedding of each universe into (at least) the next higher universe.  Closure typically includes the following rule arising from dependent products: $$\frac{\Gamma\vdash A:\mathbb{U}_n\qquad\Gamma,x:A\vdash B:\mathbb{U}_n}{\Gamma\vdash(\Pi x\!:\!A.B) : \mathbb{U}_n}$$
For this to be interesting, $x$ has to occur free in $B$ meaning $\mathbb{U}_n$ depends on $\mathbb{U}_n$.  Cycles of dependencies between sorts are characteristic of dependently typed languages.

So a (hierarchy of) universe(s) is a (hierarchy of) sort(s) with a variety of additional features many of which imply additional dependencies.  For contrast, we can consider sorts (potentially in addition to a hierarchy of universes) that aren't universes (or at least aren't the universe, i.e. we could have multiple universe hierarchies).  One example is separating compile-time calculation from run-time calculation as in Higher-order ML.  In this we'd have a sort that represents compile-time terms in addition to a sort for run-time terms and a dependency allowing run-time terms to depend on compile-time terms.  Another example is Cloud Haskell's Static type constructor.  We can view it as part of a $(\square,*)$-inclusion where sort $\square$ classifies "static" terms which are terms which only depend on terms bound at the top level.


Check-digit algorithm that includes characters? I have a data set that uses a very simple modulo 10 checksum algorithm which ignores alphabetic characters entirely.  Which wasn't a big deal, as the few  alphabetic characters present weren't critical.

Changes to the data format are upcoming, including characters which will now be critical to the interpretation of the data.  So I'd like to propose a new checksum algorithm that can detect errors in those characters.  And something more powerful then modulo 10 wouldn't hurt either.

I've been looking at the Luhn, Verhoeff and Damm and a few other check digit algorithms, but they all only handle digits, not characters.  Is there anything out there that does both digits and characters [A-Z.+-] ?  I'd rather implement something existing and proven rather then roll my own.  I think the check 'digit' could reasonable be any character from the alphabet in use [A-B.+-], not just [0-9]

Thanks!

Check digit

If the check digit needs to be a digit (0-9), here is one solution:

You could take the SHA256 hash of the character string, modulo 10, and use that as your check digit.  The advantage is that this has good properties on average, and takes into account all characters.

Arguably, a possible disadvantage is that it is not guaranteed to detect all single-digit errors and all transpositions; those are only detected with probability 9/10.  (Some other checksum algorithms for digits achieve the latter guarantee, but they don't work with alphabet characters.  Moreover, there is no hope or possibility of achieving both of those guarantees when you have to deal with alphabetic characters: it's not possible to guarantee detection of either kind of error when you have alphabetic characters and a check digit that is restricted to 0-9.)   Therefore, I'm not sure it is possible to do much better than this.

Check character

If the check digit can be anything from the character set, here is an alternative solution:

Suppose there are $n$ characters, so each character can be thought of as a number in the range $0,1,2,\dots,n-1$.  Let the characters in the string be $x_1,x_2,\dots,x_k$.  Then you can use the following as the check sum:

$$x_1 + 2x_2 + 3x_3 + \dots + kx_k \bmod n.$$

If $n$ is prime, this has the following nice guarantee: any one-character error will be detected (e.g., cooking -> cooling), and any transposition of two characters will be detected (e.g., weird -> wierd) (unless the transposed characters are a multiple of $n$ positions apart).

If $n$ is not prime, you get weaker properties, but it's still a reasonable checksum.

Alternatively, you can use the SHA256 hash of the character string, modulo $n$, as the check sum.  That has no guarantees but is good on average.


what does activation function become in spiking neural network? In common ANN, nodes are based on a activation function, like a sigmoid or tanh or ReLU. Updates of synaptic weight are based on the derivative of this function.

When node are represented with spiking neurons, what does activation function become ? how updates of synaptic weight are done ?

The activation function would be inherent to the spiking model used.

Each model  have a different dynamic which will depend on the proper model and parameters used.


Any way to optimize this with subset caching? I have some algorithm and I wonder whether there is a way to optimize it beyond the naive approach.

Basically I have time steps and the current time is $t_c$. At any given time step, a couple of "ranges" are active from now up to some given time $t_i$ (i.e. $\forall t\leq t_i: r_i\in R(t)$).

   now       -time->
   v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************

At each time $t$ I have to calculate some expensive function of all currently active ranges $f(\{r|r\in R(t)\})$ (in the diagram I'd have to calculated $f(r_1, r_2, r_3, r_4, r_5)$ now and given nothing changes I need $f(r_2, r_4, r_5)$ 9 steps later). Afterwards new ranges are generated and the time moves one step further. Therefore the existing ranges slowly change. Of course, past ranges are irrelevant. That's it.

    now      -time->
    v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************
r6 **********

My function is associative and cumutative, which means I could make use of any cached function results on subsets of the currently active set. It also time-scales with the number of arguments. Therefore given $f(a,b,c)$ I can calculate $f(d,a,b,c,e)$ in only two calculations rather than five.

Can you see any way to optimize this which is faster than calculating the function at each time for each active range?

It sounds like you are not entirely clear on the properties and structure of your function $f$, which makes things harder.  So, my first advice would be to spend a little more time trying to characterize them, as they may help you select suitable algorithms.  That said, I will suggest several methods below, which you might find helpful.  I think you might find Method 3 perfect for your needs: it should help a lot.

Method 1: Memoize $g$

Suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $+$ is some fast monoid operation (i.e., commutative and associative).

Then a very simple approach is: whenever you see a new range $r$, compute $g(r)$, and remember the results of this computation (use memoization so you never need to compute $g(r)$ again).

Now, at each time step, you have some set of active ranges, say $a,b,c,d$.  So, compute $f(a,b,c,d)$ by computing $g(a)+g(b)+g(c)+g(d)$, where you recompute the sum from scratch but you don't need to re-compute $g(\cdot)$ values you've computed before.  If $a,b,c$ were previously present and only $d$ is new, then you'll only need to compute $g(d)$.  You've previously computed $g(a),g(b),g(c)$, so there is no need to re-compute those values -- you can just look them up in your memoization table.  Finally, you apply the $+$ operator three times to sum up the four values $g(a),g(b),g(c),g(d)$.

The running time of this method is $O(n)$ evaluations of the $+$ operator and $O(n_+)$ evaluations of $g(\cdot)$ per time step, where $n$ is the total number of ranges active at that time step and $n_+$ is the number of new ranges introduced at that time step (i.e., which weren't active at the previous time step).

The advantage of this method is that it is extremely simple: it should be very easy to implement.  It might be the best choice when the $+$ operator is very fast and $g(\cdot)$ is very slow, because it avoids re-computing $g(\cdot)$ but it makes no attempt to minimize applications of $+$.  If $+$ is also very slow, then you might do better using one of the more sophisticated methods below.

Method 2: Prefix sums

Suppose $f$ is as above, but now evaluting $+$ is slow.  Then the basic idea of Method 2 is that you can remember prefix sums.  If you've computed the sum $g(a)+g(b)+g(c)+g(d)$, then the prefix sums are the sums of the prefixes of this expression: i.e., the values $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$.  Using the obvious method to compute the sum, it takes no extra effort to find the prefix sums (you generate them along the way).  So, you might as well remember the value of all of those prefix sums, and reuse them whenever possible.

I suggest that initially, you take all of the ranges that are initially active, you sort them by their end date (so that the longest-lived ranges come first in the sequence), and then you compute prefix sums.  Say the initial ranges are $a,b,c,d$, in order of decreasing end date.  Then you compute $g(a)$, $g(a)+g(b)$, $g(a)+g(b)+g(c)$, and $g(a)+g(b)+g(c)+g(d)$.  The latter value is exactly $f(a,b,c,d)$, which you output.  However you also remember the prefix sums.  At some point in the future, $d$ will expire, so now you can throw away the value of $g(a)+g(b)+g(c)+g(d)$ and remember just $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$.  You always use the longest of those prefix sums as the beginning point for adding in new elements.

Unfortunately, it's a bit of a challenge to turn this into a full algorithm that will be really useful, so I'll jump straight to Method 3, which is a generalization of this.

Method 3: binary tree

Here's a better method.  Sort the active ranges by decreasing end date.  We'll maintain a binary tree, with one leaf per active range.

Annotate each node with the result of evaluating $f(\cdot)$ on all of the ranges underneath that node (e.g., if the leaves that are descendants of that node correspond to ranges $a,b,c,d,e$, then that node will be annotated with the value of $f(a,b,c,d,e)$).  Notice that the annotation on the root is just the result of evaluating $f(\cdot)$ on the set of all active ranges, so it is the desired output.

When you move on to the next step, some ranges will expire and some new ranges will be added.  This means you'll need to delete some existing leaves and insert some new leaves (in the appropriate place, maintaining the sorted order).

When you delete a leaf, you'll need to update the value on each of its ancestor nodes, but each ancestor node can be updated with $O(1)$ evaluations of $+$.  Insertion works similarly.  So, inserting or deleting a leaf at depth $d$ takes $O(d)$ work.  If you use a balanced binary tree data structure, then the depth will be $O(\lg n)$, where $n$ is the total number of leaves, so each deleted/inserted leaf will take $O(\lg n)$ work.  There are a variety of possible implementations, e.g., using AVL trees, red-black trees, or other balanced tree data structures.  Or, you can ignore the rebalancing operations and hope that your tree will stay approximately balanced in practice and keep your implementation simple.

Ultimately, this requires $O(n_+)$ evaluations of $g(\cdot)$ and $O((n_+ + n_-) \lg n)$ evaluations of $+$ per time step, where $n$ denotes the total number of ranges active at that time, $n_+$ the number of ranges newly introduced at that time step, and $n_-$ the number of ranges that expired at that time step.  This is significantly better than Method 1, and it generalizes Method 2.

Method 4: Group operation

Finally, for completeness, let me mention one specific situation where one can achieve better running time.  Suppose the $+$ operation has an inverse.  In other words, suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $g$ is a slow function and $+$ is some group operation.  (In other words, $+$ is a binary operator that is commutative, associative, and has an inverse operator $-$ with the obvious properties: e.g., $x+y-y=x$.)  Assume $+$ and $-$ are fast to compute.

In this case, there is a good solution.  You can simply update the value of $f(\cdots)$ on the fly.  At each time step, some new ranges get added and some get removed, so you compute $g$ of each of those ranges and add the values that are being added and subtract the ones that are being removed.

For example, suppose at time step 0 we have $a,b,c$ active; then we compute $f(a,b,c)$.  Now suppose at time step 1 just $b,c$ are active: then we can compute $f(b,c)=f(a,b,c)-f(a)$, using a single computation of $g$ and a single subtraction (since we already know the value of $f(a,b,c)$, no need to recompute it).  Let's say that at time step 2 we have $b,c,d$ active: then $d$ is new, so we compute $f(b,c,d) = f(b,c)+f(d)$, which requires just a single computation of $g$ and a single addition.

You can further improve this using memoization: remember the value of $g$ at all the ranges you've computed it on.  Then to get from $f(a,b,c)$ to $f(b,c)$ requires just a single subtraction: there's no need to recompute $f(a)=g(a)$, since you've previously computed it.

I know you said that this doesn't apply to you, since you don't have any way to compute the inverse operation -- but I'm mentioning this for completeness, in case anyone else comes across a similar situation but does have inverses.

More reading, background, and tangential stuff

Here's some additional reading on topics that might be helpful or interesting to you.

Prefix sums are a helpful way to amortize effort, when dealing with commutative associative operations (like your $+$).
Fenwick trees are a nice generalization of prefix sums that allow certain powerful operations.
A more complex sort of situation with trying to reuse computation, with a monoid operation: Data structure for finding the sum of edge weights on a path.


Is there a term for the general method used in XORed linked list? The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value.  Is there a term for the general mechanism (or a way to describe it very concisely)?

As a related question, are there other somewhat recognized examples of using this mechanism?

In informally studying computer architecture, I have encountered what I think are two or three examples.  One was a suggestion for a MRU-based cache way predictor by XORing the MRU bit with a bit derived from the address; the derived bit is the "known" value.  The other was a similar, XORing the hysteresis bit of a branch predictor with a bit derived from branch information.  A possible third example might be the agree branch predictor which uses a (possibly static) per-branch prediction to bias entries in a dynamic predictor so that aliasing tends to be non-destructive.  A confirmation that these actually should be recognized as the same general mechanism as used by the XOR linked list would also be helpful.

It is a typical example of a space-time tradeoff trading increased time (CPU instructions required) for decreased space (memory required). There are many examples of this.

In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) done to receive the original (and usable) form, but no information is lost.


Number of special paths between two nodes Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between source and sink. Let's define a variable named value. Every path starts with value = label[source]. When we move from node A to B value changes like this: value = lcm( label[B], value ) where lcm is lowest common multiplier. A speical path has two condition:
1- During the move from source to sink value should always change. It means when moving from node A to B, if value before and after the move remains unchanged, that path is not special.

2- value should become some predetermined integer k at the end of the path.

How many ways we can go from source to sink while not contradicting above conditions.

I think we can remove every node that lcm(label[node], k) != k because this node could not be on any special path. Also condition one removes every loop from the graph.

Now the only algorithm I know about counting all the paths between two nodes is to use Dynamic Programming but I can't reduce this problem to that.

Also I can compute the result using backtrack but as there could be exponentially large number of such paths, it's not efficient enough.

original problem statement

To start, notice that a room is only useful if v[i] divides k, where v[i] is the value of the room i. One other important thing to see is that, is the worst case there are at most 7 different primes (2*3*5*7*11*13) in the prime factorization of k and at most 19 primes total (2^19). This gives us a good hint that we can use a bitmask to represent the value of each node in such a way that lcm(v[i], v[j]) = v[i] | v[j] (bitwise or).

After having the graph pre-processed (with only the useful nodes and with the bitmask pre-computed for every node and for k), we can do DP on the graph that can be seen as a DAG because we will never go through the same node twice. Our state will then be (cur_node, cur_bitmask).

There's only one final detail for this to fit in memory. One should notice that for the second dimension of the DP is very sparse so we can use a map for each node to keep the DP results.

Hope my explanation was clear enough, if not, feel free to clarify your doubts :)

Sample implementation: http://pastebin.com/KLfyyvhv


FM-index and pattern search with wildcards in one of my algorithm courses i'm studying the FM-Index.

In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* (where * indicates any character) using backwards search (see here).

How could this be possible? It seems to me that the algorithm already returns all the possible patterns of the form w* (because the starting range in which the search start is $0 - |T|$).And what kind of modification requires the procedure to search pattern in which for example one char is *, for example www*ww?

You are correct that w* is already addressed by fixed-substring search.  I'll give some pointers on general regex search; most text indexes can be searched for variable patterns with a bit of extra work.

First, backwards search is a consequence of the fact that the FM index and most full text indexes use suffix sorting with the most significant digit on the left, because virtually no one thinks in terms of prefix sorting with the MSD on the right.  If the latter were used the FM index would use forward search; it's simply a product of the choices made when setting up the data structure.   Another fact to note is that regex's can be reversed, so any pattern in the forward direction can be reversed and applied using backward search.

Search with wildcards is not hard to do, but it requires multiple branches through the wildcard matches, which must be searched through some sort of tree-traversal strategy, with backtracking and so on. This paper describes pattern-matching on Patricia trees for instance.

It's not that different from searching sequential text; in the FM index case you can always find the characters immediately preceding the matches found so far and determine if they match the pattern correctly.


Estimating the run time of a program according to a given CPU performance When we have a recurrence relation of a program, as an example:

 T(N) = N log N + 9N + 55

and the CPU capability let's say (10^6) or any other number. What is the formula or the method to estimate the run time (in second) if we run a program represented by a function of N, and a given N "inputs"?

If you determined that the runtime of your code, on a certain computer, is T(N) = N log N + 9N + 55 microseconds, then that equation determines the runtime. Just substitute N into that equation.


Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak The book Computational Complexity: A Modern Approach by Arora/Barak provides the following:

Theorem 1.10
There exists a function $UC: \{0,1\}^* \to \{0,1\}$ that is not computable by any TM.

Theorem 1.11
HALT(The halting problem) is not computable by any TM.

Table 1.7 that shows how Theorem 1.10 can be proved using diagonalization. Essentially this table says that there exists an uncomputable function UC that can always reverse the output of any TM, therefore, function UC is uncomputable.

The proof of Theorem 1.11 essentially creates a TM $M_{UC}$ that computes UC by assuming that HALT is computable and also by using a universal TM to simulate $M_{UC}$ and thus contradicts Theorem 1.10 and concludes that HALT is uncomputable.

My question is this: Since $M_{UC}$ is a TM, it already exists as a part of Table 1.7. In this case (as explained by the note attached to this table), function UC will (by definition) reverse the output of $M_{UC}$. Thus the $M_{UC}$ does not compute function UC even if we assume that HALT is computable.

Also, it seems that $M_{UC}$ will go into a type of recursion when the input to $M_{UC}$ is a bit representation of $M_{UC}$, i.e., each simulation on a universal TM will lead to another call on the universal TM and thus lead to a type of loop. Perhaps this is the reason the proof of Theorem 1.11 invokes a call to the HALT function (which is assumed to be computable).

Since neither HALT nor UC is computable, the machine $M_{UC}$ actually does not exist. The proof by contradiction assumes that HALT is computable and then constructs a machine $M_{UC}$, which contradicts the preceding theorem. This machine is hypothetical, and the proof of Theorem 1.10 indeed shows that it doesn't exist. That's why HALT cannot be computable.


Is there a useful algorithm with a decreasing asymptotic time? Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the larger the input the more steps are needed to handle that input.

I want to know if there is an algorithm that does not increase with input size but rather decreases.

You could make an algorithm with decreasing asymptotic time by for example, making it loop -n + 10000 times, where n is the size of an array of integers.

This however doesn't do anything other than cycling, it shows that you could make such an algorithm, if the algorithm doesn't do anything useful. Is there an algorithm that decreases asymptotically as the size of the input increases, that solves an actual problem (theoretical or other)?

EDIT:

Some people seem to be getting confused by the question so i want to clarify.

Is there a non-trivial algorithm that executes less steps as the size of the input increases?

No. If the running time is approaching zero as the input size grows, then the algorithm can’t even perform a single step.

If you mean that the running time approaches some positive constant, then this is just $O(1)$, because $\Omega(1)$ is a lower bound for any algorithm.


Does there exist an equivalent arithmetic circuit for each computable function? Does there exist an equivalent arithmetic circuit for each computable function?

I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe the statement to be false.

What has made me curious is that I've read some theorems stating that a protocol (cryptograhy protocol theory) can compute any computable function, but then requires that the function should be specified as an arithmetic circuit.

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit.  Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$.  Then there exists a multivariate polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\mathbb{F}_2=\{0,1\}$).  Now every multivariate polynomial can be computed by a an arithmetic circuit, so $f$ can be computed by an arithmetic circuit.

In some sense the restrictions to fixed-length inputs is unavoidable, as any circuit inherently has a fixed number of inputs and a fixed number of outputs.   So once you decide to focus on boolean functions, then the statement you saw in the crypto literature is justified: any boolean function that can be computed by a circuit, can be computed by an arithmetic circuit.  And, any computable boolean function can be computed by arithmetic circuits, where we understand "computed" to mean that there is a family of arithmetic circuits, one per input length (the non-uniform model; this is unavoidable if you want to compute using circuits, as any one circuit can only have a fixed input length).


Why is O(n log n) the best runtime there is? I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good.

However, there are faster runtimes such as (from now on just assume it is in big o notataion), such as $1$, $n$, and $\log n$. I understand that it is almost impossible to have a algorithm in $O(1)$ as that is for trivial tasks such as adding or multiplication.

However, why is there no algorithm in $O(\log n)$ time? Mergesort is considered to be a great algorithm and in its best and worst case scenario it is $O(n \log n)$ (I could be wrong). Why is merge sort considered to be a great algorithm when $O(n \log n)$ is only faster than $n^2$, $n!$, and $2^n$?

Also, why is there no sort with a time of $\log n$? This is not a homework question by the way, I am just purely curious as to why no sorting algorithm is in $\log n$ time.

Your confusion seems to stem from several misconceptions. I'll try to address some.

There are several ways an algorithm can be "best". Which is applicable depends on the context and on what you want to say.

An algorithm is provably the best one, period. (Hint: impossible)
An algorithm is the best we know. (Best in what metric?)
An algorithm is provably optimal. (W.r.t. what metric? What about others? Proven under which assumptions?)
An algorithm is probably asymptotically optimal. (W.r.t. what metric? What about others? Proven under which assumptions? What about the constant factor? What about small inputs?)

And probably more. Note that all these need an addition: "for problem P". Every algorithm solves some specific problem, and it does usually not make sense to compare algorithms for different problems.

Now, in the case of Mergesort, here are two facts.

Mergesort takes $O(n \log n)$ operations to sort $n$ elements in the worst case.
Sorting $n$ pairwise distinct elements (from an unknown range) by comparing
element in a pairwise fashion requires $\Omega(n \log n)$ comparisons.

Hence, Mergesort is an asymptotically worst-case-optimal algorithm for sorting pairwise distinct numbers whose range is unknown (or huge), among all comparison-based sorting algorithms.

However:

On average (again, model assumptions apply), Quicksort is faster Mergesort.
For some input classes, there are linear-time sorting algorithms.
On small inputs, even Insertion Sort is faster.

As you see, Mergesort is "best" in a certain sense, but not universally.

Regarding your specific question in the end, proving an $\Omega(n)$ lower bound for general sorting is easy.
Try to imagine an algorithm that does not even look at every input element.
Can it sort the input?


Matrix permanent, #P-hard problems and NP First of all, I'm not a computer scientist so I apologize if this is a stupid question.

I know that the problem of computing the permanent of a matrix is #P-hard, which as I understand it this implies that if you can solve an arbitrary instance of the problem in polynomial time then you can in principle solve any problem in #P in polynomial time.

What I'm wondering is if it also implies being able to solve NP problems in polynomial time (I'm guessing not).

Let's take SAT, the quintessential NP-complete problem, as an example. An instance of SAT is a formula, and the answer is whether the formula is satisfiable. The corresponding #P-hard problem #SAT is instead to count the number of satisfying assignment. Clearly if you can count the number of satisfying assignments then you can tell whether one exists. In particular, if you can solve #SAT in polynomial time, you can solve SAT in polynomial time.

This shows that if some #P-hard problem can be computed in polynomial time, then all problems in NP can also be solved in polynomial time.


Flow graph with non zero lower bound or 0 capacity I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate
Here is the problem
Given 'n' machines

Each machine has a set of capabilities
Each machine has max availability (A(m))

Given 'm' tasks

Each task requires a set of capabilities
Each task takes a certain time (D(t))
A task has to be performed on one machine only

The problem is to determine whether all tasks can be completed.
I get stuck with the 'one machine only' requirement. The only flow graphs I can come up with do not guarantee a task is not linked to more than one machine.
It's sort of a bipartite matching problem but with capacities > 1
I also ran into XOR-like behavior in flow networks which is similar but has the 'xor' requirement on the 'source' end where I would need it on the target end.
Would anyone have any tips? Is it at all possible to model this as a flow graph?
Tx!
Peter
PS Trying to clarify requirements with more concrete example
Assume digital print systems and print jobs

Each digital press can run for a number of hours
Each press has some finishing possibilities: e.g. 'sheet cutter', 'laminate', 'laser cutter', 'page folding', ....
Each print job requires a number of hours
Each print job needs one or more of the finishing possibilities

Given a set of machines, the availability for each and the finishing possibilities and also a set of print jobs (duration, finishing options needed) determine whether all print jobs can finish
So e.g.

Printer p1 is available for a duration of 10 hours and has features f1 and f2
Printer p2 is available for a duration of 10 hours and has features f2 and f3
Job1, requiring features f1 and f2 takes 8 hours to run
Job2, requiring features f2 and f3 takes 8 hours to run
Job3, requiring feature f2 requires 4 hours to run

A printer that is available for e.g. 10 hours can run 10 x 1 hour jobs or 5 x 2 hour jobs, or 1 x 8 hr job and 1 x 2 hr job, ... Jobs always have to run on a single printer
The flow diagrams I could come up with always result in cases where
8 hours of p1 is assigned to job1 (leaving 2 hours for printer p1)
8 hours of p2 is assigned to job2 (leaving 2 hours for printer p2)
(so far so good)
but then
The 2 hours of p1 and p2 left are used to flow to job3 and the max flow seems to indicate the three jobs can be run (which is not ok)

Your problem is NP-hard.  In the special case where no job requires any particular features, and all printers have the same availability, this becomes just the bin packing problem, which is (strongly) NP-complete.
You could try adapting standard algorithms for bin packing to your situation.  For instance, one approach would be to use integer linear programming and hope the ILP solver can handle the resulting problem instance.


Interpreting a proof of $2^\mathbb{N}$ being uncountable Suppose I have the following proof:
open import Agda.Builtin.Equality
open import Data.Nat.Base

data ⊥ : Set where

data  : Set where
  I :
  O :

inv :  →
inv I = O
inv O = I

invNeq : ∀ d → d ≡ inv d → ⊥
invNeq I ()
invNeq O ()

data Idx : Set where
  at : ℕ → Idx

ℝ : Set
ℝ = Idx →

_≈_ : {a b : Set} → (f₁ f₂ : a → b) → Set
_≈_ f₁ f₂ = ∀ x → f₁ x ≡ f₂ x

diagEx : (f : ℕ → ℝ) → ℝ
diagEx f (at n) = inv (f n (at n))

doesn'tBelong : (f : ℕ → ℝ) → (n : ℕ) → (f n ≈ diagEx f) → ⊥
doesn'tBelong f n funEq = invNeq (f n (at n)) (funEq (at n))

We encode real numbers as functions from natural numbers to binary digits, then (in diagEx), given some mapping f from natural numbers to reals (or, rather, some subset of those), we build a function that doesn't belong to said mapping, and then prove (in doesn'tBelong) that, for any mapping f, there exists a function (built by diagEx f) that isn't equal to any real number enumerated by the f. This, of course, includes f's claiming to be surjective, so that's largely the diagonal argument for proving uncountability of reals. Yay!
Or at least that's the intent of the proof. But what have we really proven? Could it be that we've only proven that there doesn't exist a terminating numbering of reals? Or a computable one?
My concern is that we're working in some language, and said language only allows terminating functions (modulo some irrelevant details, but even with them it's about computable functions). On the other hand, we don't rely on the computational behaviour of f at all, so, in theory, this f could be postulated (or, stretching it a little, it could even go ahead and consult some external oracle about each next digit without making the system inconsistent, I guess).
So what's the power of this proof? What's the right tool to reason about this kind of questions? It feels related to model theory, but I have very passing familiarity with that subject.

There is no assumption in your proof that the functions involved are computable, so it would be quite stingy to interpret the proof that way merely because Agda allows you to compute with its terms.
Rather, yes how it should be interpreted depends on the model, and constructive (in the sense of just removing axioms) proofs like the one you've given enable an even wider range of models. So it applies to classical functions, because we can (I believe) interpret all the operations you used as operations on classical functions. It's just that when those operations are used to combine classical functions, they don't produce computable functions, even though the operations are in a sense computable.
When you do interpret the proof in a computable setting, what you get is actually a stronger result. The classical reading is, "the reals (or, Cantor space really for your example) are uncountable." The computable reading is, "the computable reals are computably uncountable." The latter means that we can actually compute a real that is left out of any alleged computable enumeration.
A good write up of this is here, although it applies equally well to types that aren't inductive, even though the title doesn't emphasize it. The first part of the author's thesis also gives a pretty good description of modest sets, which are a way of thinking about the 'computable operations on non-computable data' angle.
So, don't make the mistake of thinking that Agda and the like are only for reasoning about their own terms. It's an easy mistake to make coming from a computer programming background, but I think it's a mistake even there.
The reason why is your oracle example. One could imagine a model where there is an extra $^ℕ$ sequence added as a sort of brute fact (also all sequences computable from it, of course). When you ask about its bits, the computer accesses some sort of physical sensor and determines the answer based on that (and memoizes it). This bit sequence is not 'computable' in the sense of being described by some term, but as long as you haven't added axioms that depend on bit sequences being describable by terms, your proofs should hold for it. So this sort of 'open world' assumption seems to match aspects of actual computers.


Proof of existence of prefix in NFA Let $$A= (Q,Σ,δ,s,F)$$ be a NFA. Prove the following statement:

$∀q ∈ Q: (∃ w_2 ∈ Σ^* :δ (q, w_2) ∩ F \ne  ∅ ⇒ ∃w_1 ∈ Σ^*:w_1w_2 ∈ L(A))$

I figured out that it means that if all the states have a path to the final state, that the word describing their path is a suffix of a word that is accepted from the NEA.

The thing is: How can I be sure that the NEA accepts all words with that suffix if it doesn't start from the s state.

Any leads?

The statement is false. Consider the NFA on the alphabet $\{a\}$ having two states: an initial state $q_0$, and the unique final state $q_f$. The transition function is given by $\delta(q_0,a) = \{q_0\}$ and $\delta(q_f,a) = \{q_f\}$. For every word $w_2$ it is the case that $\delta(q_f,w_2) \cap F = \emptyset$, yet $w_1 w_2 \notin L(A)$ for all $w_1$.


Are the No Free Lunch theorems useful for anything? I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here, because I have not found a good discussion of it anywhere else.

The NFL theorems are very interesting theoretical results which do not hold in most practical circumstances, because a key assumption of the NFL theorems is rather strong. This assumption is, roughly speaking, that the performance of an algorithm is averaged over all problem instances drawn from a uniform probability distribution. In realistic applications the problems an algorithm typically encounters are NOT drawn from a uniform distribution, and are instead drawn from what is likely a very interesting and complicated distribution specific to the general problem setting.

So, while the NFL theorems are quite interesting results, do they have any practical implications? Or are they merely theoretical results?

EDIT: By practical implications, I mean novel or improvements over existing algorithms, improved hyper-parameter selection, and things of that nature. I would even be interested to learn of NFL-inspired theorems that do apply to realistic search/optimization/learning problems.

A practical implication is that there is no silver bullet: we shouldn't expect any single optimization method to be perfect for all problems.  Rather, we should try to design optimization methods that are tailored to the problem we're trying to solve.

For instance, if you want to use local search, you'll probably need to define a neighborhood relation (a set of moves that makes "small" changes to the current solution) that is informed by the problem domain.  See, e.g., https://cs.stackexchange.com/a/88016/755 for a recent example of this here on this site.

A practical implication is that machine learning won't work if there is no structure at all on the space of possible models/hypotheses.  Instead, we need some kind of prior that makes some models more likely than others.

Often, we assume a prior that assume "simpler" models are more likely than complex one's (Occam's razor: all else being equal, the simpler explanation is more likely to be true).  This leads to use of regularization in machine learning, as it effectively applies Occam's razor to candidate models.  So, you can think of the NFL theorems as providing some kind of theoretical justification for regularization or theoretical understanding that helps us see what the role of regularization is and provides some partial explanation for the empirical observation that it seems to often be effective.

You could characterize these as "NFL theorems tell us some directions that won't work", which arguably has value as it helps us avoid wasting time on something that won't work and helps point us towards directions that are more likely to work.


Connection between max independent set and graph coloring Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices in the largest independent set in the same color, but we know nothing about the rest of the vertices (besides being a vertex cover). Am I wrong?

Let $n$ be the number of vertices of a graph $G$, $\chi(G)$ be its chromatic number, and $\alpha(G)$ be the size of its maximum independent set. Then
$$
\alpha(G) \chi(G) \geq n.
$$
The reason is that every color class in a legal coloring is an independent set.

The bound can be tight – simple examples are complete graphs ($\alpha(G) = 1$ and $\chi(G) = n$) and empty graphs ($\alpha(G) = n$ and $\chi(G) = 1$). More generally, if $G$ is a union of $m$ many $n/m$-cliques, then $\alpha(G) = m$ while $\chi(G) = n/m$; and if $G$ is a complete $m$-partite graph in which all parts have size $n/m$, then $\alpha(G) = n/m$ and $\chi(G) = m$.

The bound can also be far from tight. A simple example is the union of an independent set of size $n/2$ and a clique of size $n/2$: $\alpha(G) = n/2+1$ and $\chi(G) = n/2$.


Memory allocation of priority queues So, i faced this question during a pratice quiz
i have no idea why " all of the elements are located contiguously in memory " wrong!!
My logic is that priority queues are made of binary heaps and binary heaps are made of arrays ( according to introduction to algorithms by CLRS ) , so this means that elements are located contiguously in memory is true for PQ since it's true for arrays
so, what am i doing wrong ?!

An associative dictionary is any data structure which maps keys to values. Binary search trees, hash tables, and B-trees are all examples of associative dictionaries. It is incorrect to say that an associative dictionary must be a binary search tree.
Similarly, a priority queue is any data structure which allows insertion in any order and removal in priority order. A binary heap is an example of a priority queue, but it is incorrect to say that a priority queue must be a binary heap.
There are lots of other data structures which implement priority queues, including n-ary heaps (for n greater than 2), binomial heaps, Fibonacci heaps, Brodal queues, van Emde Boas trees, and many more besides.
And that's leaving aside the issue that a binary heap doesn't strictly need to be stored in contiguous memory. Any storage scheme can be used as long as it can be indexed like an array and supports $O(1)$ access time.


Random walks on Complete Binary Trees Let $T$ be a complete binary tree of height $n$ and root $r$.

A random walk starts at $r$, and at each step uniformly at random moves on a neighbor.

There are $m$ random walkers all starting at $r$ and let denote with $H_1,\dots,H_m$, the heights reached by the walkers after $n$ steps.

Show that, for some constant $C$ which do not have to depend on $n$
 and $m$, it holds that

$\mathbb{P}\left(\underset{i \in [m]}\max\left|H_i - \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 - \frac{1}{m}$

I have been trying several strategies, to appropriately define $H_i$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

Thanks in advance!

This answers a previous version of the question, in which the goal was to prove that with high probability, $\max |H_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$ for some constant $C > 0$.

When a particular walker is not at the root, it has a probability of 2/3 to go down a step, and a probability of 1/3 to go up a step. This is where $n/3$ comes from. However, when it is at the root, it always goes down. This suggests comparing $H_i$ to a sum of $n$ i.i.d. variables whose distribution is $+1$ w.p. $2/3$ and $-1$ w.p. $1/3$. Indeed, if $X_i$ is a variable with that distribution, then $H_i$ stochastically dominates $X_i$. Hence it suffices to show that
$$
\mathbb{P}\left(\max_{i \in [m]} X_i \geq \tfrac{n}{3} + C\sqrt{n\ln m}\right) \geq 1-\frac{1}{m}.
$$
(More formally, we can construct a coupling of the $H_i$ and $X_i$ in which $H_i \geq X_i$.)

Up to an affine transformation, the distribution of $X_i$ is binomial, so it should be easy to obtain whatever bound you wish. You can take a look at Lower bounds on binomial and Poisson tails: anapproach via tail conditional expectations by Pelekis, for example.


Build a regular expression to define a regular language The language is an infinite set of chains that are defined by the next conditions.

Conditions:

1) The language chains may consist of symbols from the set {1,a,b}.
2) The language chains always start from subchain '1a'.
3) Every languange chain has to include at least one subchain 'aa'.

For example:

1aa, 1abaa, 1aaab, 1aab1a, ... etc.

My current solution is this:

1a ((1+b)* a)* (a (1+b)*)* a (1+b+a)*

My solution seems to pass tests like these:

Allowed chains    : 1aa, 1aaa, 1abaa, 1aaba, 1aabaa, 1aab, 1aaab, 1aaabaaa
Not allowed chains: 1aba, 1abab, 1ababab

But I'm not quite sure if it's still correct. Is it correct?

If not, please offer your solution using only the type of formal language used in my solution.

One way to do it by hand, in such a simple case, would be to build a FA for
condition 2, i.e. strings that start with $1a$, and another FA for
condition 3, i.e. strings that contain $aa$.  Both FAs have only 3
states.

Then you use the intersection construction to have an automaton that
obeys both conditions. That remains simple enough if you organize your
state pairs as a 3 by 3 matrix.

From that you can easily deduce a regular expression:
 $1(a+a(a+b+1)^*a)a(a+b+1)^*$

Your solution can be proved consistent (compliant with the stated conditions) with a case analysis over the two main star operators (cases depending on whether there is zero occurrence or at least one). One also has to prove it is complete, i.e. that it does cover all compliant strings.

If you have a constraint regarding the use of parentheses, you should state it in your question. Is there a reason for the constraint ?

Find more details in the answer to your other question about this language, and a comment on how to better write the question.


Bounded Integer Edge Weights, Dijkstra's Algorithm I'm trying to understand how we can get the time complexity of Dijkstra's Algorithm down from O(V²) (for a matrix-implemented Dijkstra's) to O(V) if the edge weights of our graph are bounded by a constant C. I've read up on this MIT lecture but can't really wrap my head around the explanation.

It says that all paths are less than (|V|-1) * C, but why can't they be equal to (|V|-1) * C? For example, if the graph has one edge between each node and the weight on every node is C. Shouldnt it be less than or equal to?

In the case of your example, the shortest path is of length C since all paths are 1 edge long; there is an edge between each pair of node.

The figure of (|V|-1)C comes from the situation where all your nodes form a single chain, with edge weights of C. Then, the path between the first and last node on the chain is of length (|V|-1)C.


When using the Pumping lemma, how do I deal with different cases of y? I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$

I am sure I can do so using pumping lemma. I used  $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know how to handle different cases of y in pumping lemma.

To review, the PL says that if a language $L$ is regular, then there is an integer $p$ such that for any string $s\in L$ of length, $|s|\ge p$  we can write $s=xyz$ with

$|y|>0$
$|xy|\le p$
$xy^iz\in L$, for all integers $i\ge 0$

Assume your language is regular and select the string $ab^pab^pab^p$ to pump. Now, where can $y$ live? Since $|xy|\le p$ you know that $xy$ lives in the first $p$ or fewer characters of $s$, namely $xy=ab^k$ for some $k<p$. We then have two possibilities for $y$: it either contains the first $a$ or it doesn't, so we have two possibilities, where I've colored the string y:
$$\begin{array}{c}
(\color{red}{ab\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)\\
(a\color{red}{b\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)
\end{array}$$

Then for each case we argue thus:

$y$ is $ab^n$ (i.e., $x=\epsilon$), with $0\le n\le p$. Then $xyz=ab^pab^pab^p=(ab^n)b^{p-n}ab^pab^p$. Then $xy^2z=(ab^n)(ab^n)b^{p-n}ab^pab^p=ab^nab^pab^pab^p$. It's not difficult to see that this cannot be in $L$, so we've reached a contradiction.
$y$ is $b^n$ (i.e., $x=ab\dotsc b$). Then $xy^2z = ab^pb^nab^pab^p$ and again, this string can't be in $L$.

In all cases, we reach a contradiction, so our initial assumption, that $L$ was regular, was false.

By the way, it's easier to use the candidate string $a^pba^pba^pb$, since for this we only have one possibility for where $y$ could live, namely among the first string of a's.


For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes? When we consider multi-tape Turing machines, we can assume that each tape is accessed with a separate head and each head can move independently of the other heads. But can we assume that each tape can be in its own state independently of the other tapes (for example, tape 1 in state A, tape 2 in state F, tape 3 in state X simultaneously)?

Then, for example, the table of instructions for some three-tape two-symbol ("0" and "1") machine can look like this:

    | 000         | 001         | ...
----------------------------------
AAA | 011/BXZ/LRL | 010/XYB/RRR | ...
----------------------------------
AAB | 001/TSH/LLR | 110/AET/LLL | ...
----------------------------------
...

where the first cell of the table can be interpreted as follows: if the first tape is in state A, the first head is over the cell with symbol 0, the second tape is in state A, the second head is over the cell with symbol 0, the third tape is in state A, the third head is over the cell with symbol 0, then the first head writes "0" instead of "0", then the first tape goes into state B, then the first head moves to the left, then the second head writes "1" instead of "0", then the second tape goes into state X, then the second head moves to the right, then the third head writes "1" instead of "0", then the third tape goes into state Z, then the third head moves to the left.

A Turing machine has just one state, even if it has multiple tapes. If you give each tape a separate state, it’s easy to forget that the action of each tape head can depend on the global state and on the character under every head, which is crucial, because it is the only way the tapes can communicate with each other. A multi-tape TM is a single computer with multiple I/O devices, not multiple computers each with one I/O device.

xskxzr’s answer shows that one state per tape doesn’t actually change the computational power of Turing machines. But it’s important to note that this requires the actions of all tape heads to be allowed to depend on every tape’s state and every tape’s current character. Thinking about each tape having its own state is likely to make you forget this, resulting in a less powerful machine. Conceptually, it’s usually not a good way to think about Turing machines.


Forward checking vs arc consistency on 3-SAT If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From what I gathered forward-checking is $O(n)$, while Arc consistency is about $O(8c)$ where c is the number of constraints (According to this page). So perhaps forward -checking is faster somehow? How should I determine which to use?

Both forward checking (FC) and arc consistency (AC) are methods of inference. Regardless of the problem you are solving, choosing a specific method of inference is always a tradeoff. Basically, the more you are willing to pay in terms of time, the more you gain in terms of strength of inference. So yes, it is faster to perform forward checking than arc consistency, but arc consistency is more effective at pruning the search space. If you are willing to pay even more, there are even stronger forms of consistency. The book by Russell & Norvig gives a nice, quick introduction.

Both FC and AC are relatively cheap and easy to implement, too. The suitable choice depends on the specific structure of your problem. I think at least in general, it is best that you experiment with both.


directed graph data structure with fast in/out neighbor query If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all the vertices $j$ such that $(i,j)$ is an edge of $G$. On the other hand, if I want to find all the in-neighbors of $i$, i.e. the set of all vertices $j$: $(j,i)$ is an edge, then this takes $\mathcal O(n)$.

If I want to answer both in- and out-neighbor queries fast, I could just store the graph $G'$ obtained from $G$ by reversing all the edges, but that doubles memory usage. Is there a graph storage scheme for which both in- and out-neighbor queries take $\mathcal O(d)$ time, but doesn't require double the memory?

If you care about constant factors, then big-Oh notation is not a useful tool to help you compare or measure possible data structures.  If you want to minimize storage as much as possible, you need to think about the layout of the bits -- and then it would help to know concrete parameters and information, like roughly how big $n$ is, a rough estimate of the average degree (averaged over all vertices), a rough estimate of the largest degree and the distribution of degrees, etc.

For instance, one scheme is to represent the list of out-neighbors using something more efficient than a plain linked list (e.g., a linked list of buckets, where each bucket contains $c$ elements, and where you choose an optimal value of $c$ to minimize expected space usage).  Or, you can pack these lists of out-neighbors and in-neighbors into a single big array, with each vertex having a pointer to the first index in that array where the sequence of out-neighbors or in-neighbors exist.  You can also arrange that each entry needs only $\lceil \lg n \rceil$ bits, where $n$ is the number of vertices.

Another scheme is to use a multi-linked list as Patrick suggests, but with a slight twist.  Instead of storing a pair of vertices $(a,b)$ in each linked-list node, store $a \oplus b$ (the xor of the identifier for vertex $a$ and the identifier for vertex $b$).  This will be present in two linked lists: the out-neighbors of $a$, and the in-neighbors of $b$.  Each linked-list node will have two next pointers.  Notice that, when traversing the list of out-neighbors of $a$, all of the nodes will have $a$ as one of the two vertices, so if the value $x$ is stored in the node, we know it represents an edge to $a \oplus x$ (since $a \oplus (a \oplus b) = b$).  Similarly, when traversing the list of in-neighbors of $b$, the value $x$ in a node represents an edge from the vertex $x \oplus b$.  This doesn't reduce the number of pointers compared to a naive scheme, but it halves the amount of space for storing the data (the vertex identifiers) in each linked-list.

There are many more such bit-packing tricks and considerations that can be tried when you care about constant factors.


Is any superset of an undecidable set is uncountable? This statement really made me confused, Is any superset of an undecidable set is uncountable?

All sets of words over a finite alphabet are countable. Stated differently, no set of words over a finite alphabet is uncountable.


Algorithm To Process Purchases Efficiently and Apply Constraint I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows:

customerId  itemId  cost

The customer could have purchased the same item more than once in a day and at different times so there will be multiple entries for a customer and item combination. At the end of the processing, the program should print the customerId and the total cost of all their purchases, but with a discount applied so that the cost of the most expensive item is removed.

My algorithm is as follows:

Create a map, call it M-1, with the customerId as key and a running total cost as the value i.e. customerid -> running_total_cost.
Create another map, call it M-2, with the key as (customerId and itemId) and for the value the running subtotal. That is, it keeps a tab on how much of this item this customer has bought.
For each line in the file, upsert into M-1 the customerId and add the cost of this item to the running total. Also upsert an entry in M-2 containing the running total of this customer and item purchased. So M-1 has this structure:

customerId  RunningTotal

And M-2 has this structure

customerId ItemId RunningTotal

After the file has been completely processed in step 3, for each entry in M-1, get the customerId and look-up the customer in M-2. In M-2, run a loop so that it finds the most expensive purchase this customer made. This can be done by creating a temporary variable and looping through the purchases the customer made and comparing the current value of this variable with the next value. Replace the value of the variable with the new highest total At the end, the highest value will remain.
Print table

My question is whether this can be processed any faster than this?

UPDATE

I believe I have an optimal solution for this now. The algorithm is as follows:

Make one pass through the file. For each line, create a map with the following structure

Map[CustomerId, Map[ItemId, subtotal]]

After processing the file completely and making the above map, then do the following loop

for each customerId
  count = 0
  total = 0
  highestSubtotal = 0
  for each itemId
     total += subtotal
     highestSubtotal = max(highestSubtotal, subtotal)
     count += 1
print CustomerId, if count > 1 then total - highestSubtotal else total

I don't think I can optimise that anymore unless anybody can think of something else.

The algorithm I posted above doesn't work. It's the same as trying to load all the file upfront which blows up as the heap memory is exhausted.

Another solution would be to sort the file before processing it. The UNIX sort command is able to sort files much bigger than the RAM available on the machine. It does this using external sort I believe.

So my new solution is to sort the file first on the customerId. This ways a one pass can be done on the file and the data for each customer calculated on the fly. As each customer is encountered in order, before computing the next customer's data the memory consumed for the previous customer is freed.


What does $\text{dom}(\Gamma)$ mean in the context of an inference rule? In the wikipedia page on pure type systems, it gives the following inference rule:

$\frac{\Gamma \vdash A : s \quad x \notin \text{dom}(\Gamma)}{\Gamma, x : A \vdash x : A }\quad \text{(start)}$

What does $\text{dom}(\Gamma)$ mean here? These are string rewriting systems, so $\Gamma$ is supposed to be a string of symbols, a purely syntactic object. I'm not sure what a "domain of a string" is.

There are various ways to define contexts in type theories. In this style, we assume there is some infinite set of variable names $V$ and define the context $\Gamma : V \rightharpoonup S$ as a partial function from the set of variable names to the set of types. $\mathrm{dom}(\Gamma)$ is then the subset of $V$ on which $\Gamma$ is defined, i.e. the variables in the context $\Gamma$. To require that $x \notin \mathrm{dom}(\Gamma)$ is asking for $x$ to be a fresh variable for the context $\Gamma$.


nlp: phonetic edit distance between a word and the closest of a set of words Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large set of words and I'm certain the speaker is trying to say one of these words. However, the voice recognition system is not perfect, so sometimes the voice recognition engine will spit out a word that is phonetically similar to what the user intended, but that is not in the set.

In other words, I have a word X, and a set of words Y. I want the member of Y which sounds the most like X.

I know that phonemes are the most basic sound unit of sound, so I've attempted to use CMU's Pronouncing dictionary to break X into phonemes, and use something similar to an edit distance algorithm to alter these phonemes until they match one of the members of Y. However, there are some huge issues:

There are at least 40 phonemes in CMU's system, which makes for a huge branching factor when you consider adding or replacing at any given position. I can't thoroughly search beyond three changes or so, which isn't sufficient.
Phonemes are perhaps too 'low-level' in the sense that there are many combinations of phonemes which are not words at all.

Building on complaint #2, I was thinking it would be nice to have a weighted graph of at least the most common words to other reasonably similar words, and I could run a search algorithm on this graph to find words in Y more quickly, and with a less explosive branching factor. Precomputing such a graph is on the table, as it could just be loaded at runtime.

Are there any sort of methods for doing this which exist currently? Or should I be thinking in a different direction?

Building on the comments, there's something called the Needleman–Wunsch algorithm, for which you can find the lowest 'cost' alignment of two sequences (phonemes). You can get a good 'confusion cost matrix' by taking a normal confusion matrix and taking the log-odds of each confusion pair.

As long as your set of words is less than 33k or so, you should be able to find the lowest cost match in about a second or so. Multiply that by N if you multithread across N cores...

Full disclosure: not my ideas here, I got them from Phonemic Similarity Metrics to Compare Pronunciation Methods (Hixon, Schneider and Epstein, in Interspeech 2011).


Path optimization in a DAG: maximizing number of least cost arcs I've got the following problem.

I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$.

The optimal path has to maximize the number of least cost arcs.
In the example:

R->B->S is the least cost path but it's not the optimal.
R->-A->D->S costs less than R->A->C->E->S , but the latter is the optimum as it goes through more, least cost arcs.

My current problem, which constitute the object this question, is to find a way of defining formally how to compare two paths according to my intuitive understanding, as comparing them comes before choosing the optimal one.

Of two paths, the better one is the one that traverses the highest number of least cost arcs.

I have been considering three ways, some that seem not fully adequate for my purpose, but would welcome other suggestions.

My three  ideas are the following:

Minimizing the average of the cost of arcs on the path.

Minimizing the average is not fully ok: imagine to have a path with cost [3,12], and a path with cost [3,10,10]. The average of the first path is less than the average of the second, but the second is the optimal as it traverses more paths.
Comparing individually the arcs of the paths

Given two paths $A$ and $B$:

Let $A$ = [$a_1,\ldots,a_n$] and
$B$ = [$b_1,\ldots,b_m$] where $a_i$ and $b_i$ are the arc costs of $A$ and $B$ respectively.

Then $A$ is better than $B$ if $\sum_{i=0}^n card(B < a_i)$ <  $\sum_{i=0}^m card(A < b_i)$ where $card$ represents the cardinality of the set, and $B < a_i$ is defined as $\{b_j  \in B \mid b_j < a_i\}$, the comparison being on the weight of the concerned arcs.

However, with this second approach I get many ties between different paths, increasing the risk of getting a suboptimal path.
Comparing the min-max of the arcs weights for each path.

Another possibility is to compute the min-max of the arcs of each path, and choose the smaller one. It is intrinsically different from the other approaches.

But it is  not fully what I seek to achieve.
For example, min-max over [1,1,1,3] and [2,2,2,2] chooses the latter one, while the best one is the first.

To motivation behind my intuition is the following: each node is a "checkpoint" that the solution may traverse on its way from the node $R$ to node $S$.
The goal is to output a sequence $Q$ with an associated "precision"

if the chosen path is R->A->D->S, then $\;Q\;$ is $\;\;$A $\pm$ 10, D $\pm$ 5, S $\pm$ 7

Clearly, the optimal solution has to be as precise as possible, so the optimal path has to emit the maximum number of least cost arcs.

Once the comparison of paths has been formalized precisely, my problem will be to compute the optimal path on a given graph. But right now the  question is only to find a proper way of comparing paths. The role of the graph structure is only, possibly, to help convey the intuition of my problem.

I've not thought completely through it, but some thoughts on 1) which might be useful:

If you add a constant value k to each edge traversed, you could take into account the number of nodes traversed. In your case, this constant value k should be negative (e.g. the negative value of the maximum edge weight, in your example 11).

Then you might be able to state the following:

The path maximizes the number of least links if $\sum_{i=0}^n (a_i + k)$ < $\sum_{i=0}^m (b_i + k)$.

For your example: (let $P_i$ denote the $i$-th path and $C_i$ denote the costs of path $P_i$)

$P_A=[R, B, S], C_A = -2$

$P_B=[R, A, D, S], C_B = -11$

$P_C=[R, A, C, E, S], C_C = -20$

So $C_C < C_B < C_A$ and hence $P_C$ is your optimal path.

As mentioned, I've not spent too much time to look if there is an example where this approach does not work, but maybe it's a good point to start with.

Of course you get some ties with this approach as well but I think all of these ties are equivalent in the sense that the least cost arcs are traversed and the number of traversed vertices are equivalent. Correct me, if I'm wrong.


(0+ 11*0) + (0 +11*0)(1 +01*0)* (1 +01*0) =1*0(1 +01*0)* I needed help with the following question which belongs to Arden's theorem as I am having a hard time solving it. Please find the question below

Prove:
$$(0+ 11^*0) + (0 +11^*0)(1 +01^*0)^* (1 +01^*0) = 1^*0(1 +01^*0)^*$$

Call $(0+11^*0)$ as A and $(1+01^*0)$ as B. Then what you have on left-hand side is just: $$ R = A + AB^*B$$
Using Arden's Theorem we know that in this case: $$R = AB^*$$

Then what we have simplified is: $$(11^*0+0)(1+01^*0)^*$$
Another simplification using Arden's Theorem would give us:
$$(11^*+ \epsilon)0(1+01^*0)^*$$
Which is finally equivalent to: $$1^*0(1+01^*0)^*$$


Concatenation property of regular languages If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L;  Are there any other languages that, when concatenated with sigma star will result in the same language?

$L \Sigma^* = \emptyset \Sigma^* = \emptyset = L$

$\Sigma^*L = \Sigma^* \emptyset = \emptyset = L$

$L \Sigma^* = (S \Sigma^*)\Sigma^* = S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S) = \Sigma^* S = L$ for all languages S

$L \Sigma^* = (\Sigma^* S \Sigma^*) \Sigma^* = \Sigma^* S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S \Sigma^*) = \Sigma^* S \Sigma^* = L$ for all languages S.

In short: there are infinitely many distinct languages where appending the language to $\Sigma^*$ (front or back) will yield the same language. An infinite family of such languages is given by $\Sigma^* S \Sigma^*$ where $S$ can be any language whatsoever.


Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just trying to understand what it does.

 Main
  begin
   process_number=1;
   parbegin
    process1;
    process2;
   parend;
  end

Process1;
  begin
   while process_number=2 do;
   critical_section1;
   process_number=2;
   other_stuff;
  end;

Process2;
 begin
  while process_number=1 do;
  critical_section2;
  process_number=1;
  other_stuff;
 end;

After the code he says the following:

"Algorithm Guarantees mutual exclusion.

Price is high: P1 must go first, so if P2 is ready
to enter its critical section, it must wait.

When P1 enters and leaves its CS, P2 must go
next even P1 is ready, and P2 is not ready.

If one of the processes is terminated, then
eventually the other will not be able to proceed"

I don't even know what's going on. My best guess is that since process 1 and process 2 are running concurrently, and the variable process_number is originally equal to 1, Process 1 is going to stop at the condition (while process_number = 2). But for process 2 the condition (while process_number = 1) is true, so...it will do whatever lines of code follow it. But the lines of code that follow it are (critical_section2;) and why in the world would it be running critical_section2 if it the variable process_number = 1 is true. I..honestly have no idea what my professor was trying to get across in this confusing code.

Note that the while bodies are empty, i.e., if the condition is false, they just fall through to the next line.

Horrible, horrible code; extremely restrictive (taking turns!), and very inefficient (busy waiting), if you ask me.


Bipartite maximum matching with added constraints Suppose you have two lists as follows
List $A$ = $(a_1, a_2, ..., a_m)$
List $B$ = $(b_1, b_2, ..., b_n)$
Each element in list $A$ can be paired with many or no elements in list $B$. I have a function $f(a_i, b_j)$ that returns true or false depending on whether the match is valid or not.  However, if you pair element $i$ in list $A$ then you also have to pair the $i$-th element in list $B$. So, for example, the pair can be $(a_i, b_2)$ and $(a_1, b_i)$ or even $(a_i, b_i)$.
I want to find the maximum number of pairings between the two lists with the added constraint of if the $i$-th element of list $A$ is paired, then the $i$-th element of list $B$ must also be paired.

My intuition says that modifying the maximal matching bipartite algorithm might be useful for this. However, I am stuck in actually figuring out how to do this. Any help would be appreciated.

Let me start by modifying the problem statement to use standard graph theory terminology, according to my interpretation of the original post:

Let $G=(V, E)$ be a bipartite graph, with $V= A \cup B$, with $A=\{a_i\}_{1\leq i \leq m}$, with $B=\{b_j\}_{1 \leq j \leq n}$, and with $E \subseteq A \times B$. For an edge set $S \subseteq E$, let $f(A, S)$ denote the set of integers $i$ such that $(a_i, b_k) \in S$ for some $k$, and let $g(B, S)$ denote the set of integers $j$ such that $(a_k, b_j)\in S$ for some $k$. Find a maximal edge set $S^*\subseteq E$ with the property that $f(A, S^*)\subseteq g(A, S^*)$.

Assuming that this interpretation is correct, this algorithm should work:
Initialize $S = E$. Construct $m$ lists $A_1, A_2, \ldots A_m$, where $A_i = \{j \ |\ (a_i, b_j) \in S\}$, and construct $n$ lists $B_1, B_2, \ldots B_n$, where $B_j = \{i \ |\ (a_i, b_j) \in S\}$. Compute $f(A, S)$ and $g(B, S)$, and take some $c \in f(A, S) - g(B, S)$. Remove all edges of $S$ of the form $(a_c, b_k)$, and update $\{A_i\}, \{B_j\}, f(A,S)$, and $g(B, S)$ accordingly. Repeat until $f(A, S) - g(B, S)$ is empty.
It is easy to see that the resultant $S$ is maximal, as every edge removed was necessary. It is also easy to see that the running time is $O(\lvert V \rvert+\lvert E \rvert)$, as each edge is processed $O(1)$ times.