texts: Does every data type just boil down to nodes with pointers?

texts:
An array or vector is just a sequence of values.  They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.

Stacks and queues are two abstract data types commonly taught in Intro CS courses.  Somewhere in the class, students often have to implement stacks and queues using a linked list as the underlying data structure, which means we are back to the same "collection of nodes" idea.

Priority queues can be created using a Heap. A heap can be thought of as a tree with the min value at the root.  Trees of all sorts, including BSTs, AVL, heaps can be thought of as a collection of nodes connected by edges.  These nodes are linked together where one node points to another.

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node.  Is that right?  If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers?  How do we go from nodes to binary code?


texts:
I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice?

In other words, I need to test whether any two vertices have a unique least upper bound and greatest lower bound.

From brief browsing, I found an $O(n^3)$ algorithm that explicitly computes the least upper bound of every pair of elements. Is there a better test?


texts: Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?

texts:
I have an example below which seems to lead to a “useless” production.
This is the original grammar:
\begin{align*}
    S&\longrightarrow aX\,|\,Yb\\
    X&\longrightarrow S\,|\,\varepsilon\\
    Y&\longrightarrow bY\,|\,b
\end{align*}
Here is the conversion to CNF:
Step 1: Make sure the start symbol does not occur on the RHS.
\begin{align*}
    S'\!\!\!&\longrightarrow S\\
    S&\longrightarrow aX\,|\,Yb\\
    X&\longrightarrow S\,|\,\varepsilon\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 2: Remove rules that lead to $ \varepsilon $.
\begin{align*}
    S'\!\!\!&\longrightarrow S\\
    S&\longrightarrow a\,|\,aX\,|\,Yb\\
    X&\longrightarrow S\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 3: Remove all unit productions.
\begin{align*}
    S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\
    S&\longrightarrow a\,|\,aX\,|\,Yb\\
    X&\longrightarrow a\,|\,aX\,|\,Yb\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 4: Remove remaining productions which do not conform to CNF.
\begin{align*}
    S'\!\!\!&\longrightarrow a\,|\,AX\,|\,YB\\
    S&\longrightarrow a\,|\,AX\,|\,YB\\
    X&\longrightarrow a\,|\,AX\,|\,YB\\
    Y&\longrightarrow BY\,|\,b\\
    A&\longrightarrow a\\
    B&\longrightarrow b\\
  \end{align*}
It seems that following the algorithm has led to a useless production. The second production will never be invoked from the starting symbol.
Is the production really useless and is it right to remove it from the Chomsky Normal Form grammar?


texts: Find an algorithm to fully consume items with criteria and produce minimal result

texts:
So here are the prerequisites:

There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties.
Items have quantities. Example: Item_1 {size: 10, weight: 15} - quantity 3; Item_2 {size: 11, weight: 2} - quantity 15 etc.
There are consumers. Each consumer has an eligibility criteria, i.e. it can only consume items with specific properties.
Let's call a specific criteria for items a type. So for example {size > 10, weight < 5} is a type, and {weight = 0} is also a type.
Some consumers consume multiple types of items in specific proportions. For example, Consumer_1 consumes pairs of items, where first in a pair should have size > 10 and second in a pair should have weight = 10, and for each first item there should be exactly one item of the second (i.e. propoption is 1:1); Consumer_2 consumes only items of weight = 0, and since it only needs one type of item there's no proportion involved; and Consumer_3 accepts three types of items in proportion 1:2:1. Hope you get the idea.
Every consumer produces a number, that usually (but not always) depends on specific properties of the items it consumes. For better understanding, let's suppose the number represents a price, and it can be calculated as weight*5, for instance. But it can also depend on things not directly related to items, e.g. the day of week.
The number of consumers is around 20-30 if that is important.

The task is to consume all items (all their quantities) fully with the given set of consumers and produce a minimum/maximum result, which is a sum of all numbers that consumers produce.

This reminds me somehow of the Knapsack problem, which lead to thinking of a class of combinatorial optimization - which is obvious, because we need to match combinations of items to the consumers. But the difference is that (1) items need to be consumed fully (we guarantee that by having a fallback consumer that accepts any item), (2) the knapsack problem does not assume any predicates, i.e. a criteria for consumption.

More specifically, we map items to types and types to consumers. Then we can actually solve this as a linear optimization problem, but that proves to be slow and does not guarantee an optimal result, so I'm wondering if there is an algorithm that is better suited.


texts: transformation between two formulations of the mincost flow problem

texts:
According to this slide, the following two formulations of the mincost flow problem are equivalent:

Given directed graph G = (V, E)

  Let u denote capacities
  Let c denote edge costs.
  A flow of f(v,w) units on edge (v,w) contributes cost c(v,w)f(v,w) to the objective function.

...

  Send x units of flow from s to t as cheaply as possible.
  General version with supplies and demands

  No source or sink.
  Each node has a value b(v).
  positive b(v) is a supply
  negative b(v) is a demand.
  Find flow which satisfies supplies and demands and has minimum total cost.

I can see that 2. is a special case of 3. in which only two nodes (s and t) and have non-zero demand. But I cannot figure out how to transform the more general problem 3. into problem 2.

Can anyone help explain how to transform 3. to 2. ?

That is, how to e.g. add edges and/or change capacity/cost, to solve problem 3. with a solver of problem 2.


texts: How to find all topological sortings of a special DAG in O(N^2)

texts:
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
Problem description:

Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.
Since the required answer can be quite large, print it modulo $10^9+7$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.
Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at  position. Assume that there are $X$ outgoing edges to the children from  and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.
Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X_1, X_2, \cdots X_i$ such that  $X_1, X_2, \cdots X_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.
$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$
Note that this $\sum_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.
Now, for $X$ nodes basically you have computed $dp_j$, number of filling up $j$ spaces using subtrees of $X$ nodes such that $X_1, X_2, \cdots X_x$ is included. Lets call this $dp$ as $left[]$ and similary call the $dp$ for $Y$ nodes as $right[]$.
$$DP(i, j) = \sum_{1\le k < j} nCr(j-1, k) \times {left}_k \times nCr(a, b) \times {right}_{a-b}$$
Where $a = SZ_i - j$, $b = SZ_x - k$ and $SZ_i$ denotes the size of subtree rooted at $i^{th}$ node & $SZ_x$ denotes the sum of sizes of all subtrees rooted at all those $X$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $O(N^2)$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.
I believe that the added constraint that the number of edges is equal to $N-1$ simplifies the solution, and I couldn't think of any other possibility.
Could anyone kindly validate the solution?


texts: Notation for average case complexity of an algorithm

texts:
I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis.

For example, I have tested my algorithm and fitted the results to the curve $f(n)=2.65\times 10^{-15}\cdot(2.17^{n})$ and in my report right now I'm saying something like:

  the average case complexity was found to be $\approx 2.65\times 10^{-15}\cdot(2.17^{n})$,

but I would rather say something like

  the average case complexity is $\in \Theta(2.17^{n})$.

But I'm not sure if this is technically correct because the result hasn't been theoretically proven, only empirically tested and fitted to the curve.


texts:
The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K represent the number of lookahead symbols. Thereby it's not making much sense to me.

Kindly help me here

Thanks in advance!


texts:
The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision.

For example, without reading a symbol from the input, we cannot decide in LL(1) grammars which rule must be applied for derivation.

In this point, Some thought like that occurs: we can make a decision without reading a symbol from the input in LR(0) grammars for specific derivation.

However, I do not think like that, because we always need an input character in LR(0) parsers. We decide to apply shift or reduce operation by regarding next input symbol. In this case, why is it regarded as LR(0) ?


texts: What is With High Probability on Probabilistic Algorithms?

texts:
I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn't get it.

They just said, "Event $E$ occurs with high probability (w.h.p.) if, for any $\alpha\geq1$, there is an appropriate choice of constants for which $E$ occurs with probability at least $1 − O(1/n^\alpha)$".

Something from algorithmist.com didn't help, either.

What is $\alpha$ and what is $1 − O(1/n^\alpha)$? Not understanding this thing make me confused of the analysis of why "With high probability, every search in an $n$-element skip list costs $O(\lg n)$".


texts: Why are these features missing in modern day general purpose computer languages?

texts:
I often wondered why languages like c do not have simple syntactical allowances that would help readability.  For example, large numbers such as 1073741823 can be hard to read so my opinion is modern day languages should allow delimiters such as , (comma) so you can write a statement such as x = 1,073,741,823.  That is MUCH more readable.  Perhaps you can do this in some languages using #DEFINE but it seems like such a simple thing should be native to the language.

Another feature I would like to see in general purpose languages are huge ints.  That is, integers that are not limited to 16 or 32 or even 64 bits but some very large number of bits, perhaps 256.  This would help with simulation of certain games with very large state spaces.  Why burden the programmer with such tasks?  I, as a user of a programming language, would expect some complexity to be hidden from me and handled by the compiler itself.  Just like when we drive our cars, many people don't understand the inner workings of it but they don't need to.

It would also be nice if the math library had basic combinatorial functions such as choose(52,5) and the language also had direct syntax for factorial such as x = 52!/47!.  That is "syntactical sugar" compared to Factorial(52)/Factorial(47).

Also when I was in college I proposed a computer language that would optionally use indenting to limit the scope of statement like IF, CASE, LOOP, FOR....  For example:

if cardcount < 52
  ProcessNextCard()
else
  deckfinished = TRUE
next statement goes here and is not part of if statement cuz it is not indented.

Here is an even better example:

for c1 = 1 to 50
 for c2 = (c1+1) to 51
  for c3 = (c2+1) to 52
   ProcessHand()
nextstatement goes here but it is not part of any loop.

Ideally the programming environment would show indentation brackets to confirm the alignment and have a special printing program that does the same.

Of course if there are a lot of lines of code in the body of the if statement then it would be better (clearer) to insert the endif, ifend or fi "missing" part of the if statement.  The compiler should allow both options.  Forcing the programmer to indent is a good way to teach new programmers good programming practice and to penalize lazy programmers.

Also how about a language that self profiles (or at least assists) using a special directive?  For example, if someone wrote a file compressor program and wanted to know where it was eating up most of the time and in what proportion, it would be nice if the language automatically inserted some markers or at least allowed the programmer to insert them easily and then the profiler would tell the programmer what proportion of the runtime was between each set of markers (such as A-A, B-B, C-C... Z-Z).

I could go on and on with a wish list of enhanced features to make programming easier but I will just stick with these few for now.

So my main question is why are many of these features lacking in modern day languages or are they actually there?


texts:
An independent set is a set of vertices in a graph, no two of which are adjacent.
A maximal independent set is an independent set that you can not add any vertex.
I want to know if the number of all maximal independent set is an exponential number.


texts: Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?

texts:
In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u_i \rangle = \sum^n_{j=1} x[j] u_i[j]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?


texts: What mathematics can be interesting for these CS areas?

texts:
For my CS degree I have had most of the "standard" mathematical background:

Calculus: differential, integral, complex numbers
Algebra: pretty much the concepts up until fields.
Number Theory: XGCD and related stuff, mostly for crypto.
Linear Algebra: up until eigenvectors/eigenvalues
Statistics: probabilities, testing
Logic: propositional, predicate, modal, hybrid.

My main interests in the CS area are security, cryptography and artificial intelligence.
I was wondering if there are any suggestions for mathematical topics that could be interesting for these areas, particularly for AI as it is not my main field of study at the moment.


texts:
Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?

I attempted to do as follows: From a PRNG obtain n PRNs in [0.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (used in data compression). But, if the PRNs used are uniform, then I think this would highly favour generation of those Huffman trees that are more flat and Huffman trees corresponding to widely different frequencies of the symbols would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.


texts:
I am at a loss when it comes to understanding how Grover's Algorithm gives any useful information. Suppose we have a 4-qubit states (|0⟩ to |15⟩), and we are searching for the state |3⟩. The oracle would thus be
O=I−2|3⟩⟨3|

And then, at the end, after all the amplitude amplification steps, we would get the state |3⟩ with a high probability, but does this give any new information, since we already used |3⟩ inside the oracle?

I know I am missing out something crucial, but I absolutely cannot put my finger on it.

Please help. Thank you.


texts: One element that differs in two arrays. How to find it efficiently?

texts:
I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.

Let's say we have two arrays consisting of numbers that are unsorted. Array 2 contains a number that Array 1 does not. Both arrays have randomly located numbers, not necessarily in the same order or at the same indices. For example:

Array 1
[78,11, 143, 84, 77, 1, 26, 35 .... n]

Array 2
[11,84, 35, 25, 77, 78, 26, 143 ... 21... n+1]

What is the fastest algorithm for finding the number that differs? What is its running time? In this example, the number we would be looking for is 21.

My idea was to run through Array 1 and delete that value from array 2. Iterate until you are finished. This should be around $O(n \log n)$ running time, right?


texts: Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix

texts:
Ryser has shown that the permanent of an $n \times n$ matrix $A=(a_{ij})$ can be expressed as

\begin{align}
Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij},
\end{align}

where $[n]=\{1,2,\dots,n\}$. This algorithm runs in $\mathcal{O}(2^{n-1}n^2)$ time. I've been trying to derive this, but can't quite get the result. Here's my work so far.

The outer sum is over all non-empty subsets of $[n]$, of which there are $2^n-1$. We recall that the number of subsets of size $r$ is ${n \choose r}=\frac{n!}{r!(n-r)!}$.

For each set $s$ in the outer sum we compute $\sum_{j \in s} a_{ij}$, which uses $|s|-1$ additions. Next, this sum sees the product $\prod_{i=1}^n$, which takes $n-1$ multiplications. This happens for each non-empty subset of $[n]$, so there are the following number of total additions:

\begin{align}
\sum_{s \subset [n]} \left(|s|-1\right) &= \sum_{k=1}^n (k-1) {n \choose k} \\
&= \sum_{k=1}^n k {n \choose k} - \sum_{k=1}^n {n \choose k} \\
&= n \sum_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\
&= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\
&=n2^{n-1} - 2^n -n +1.
\end{align}

The total number of multiplications is $(n-1)(2^n-1)$.

There is also the $(-1)^{|s|}$, which takes another $2^n-1$ operations in total.

This gives us a grand total of $n2^n + n 2^{n-1} - 2^n -2n+1$, which is not correct. It looks like I'm off by a factor of $n$ on the second term here. Where am I going wrong?


texts:
I'm reading Arpaci's Operating Systems: Three Easy Pieces, the chapter on Locks.
At the end of the chapter, they present Two-phase locks (section 28.16). They say

A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.

I understand this may only be useful in a multiprocessor environment, is that right?
Also, it seems a little arbitrary to me to wait the first time and then go to sleep. I mean, I don't see why this would be such a great improvement over going directly to sleep in the case the lock is being held.
Is there anything I'm missing?
Thanks in advance!

Below is the whole paragraph on Two-phase locks:

One final note: the Linux approach has the flavor of an old approach that has been used on and off for years, going at least as far back to Dahm Locks in the early 1960’s [M82], and is now referred to as a two-phase lock. A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.
However, if the lock is not acquired during the first spin phase, a sec- ond phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later. The Linux lock above is a form of such a lock, but it only spins once; a generalization of this could spin in a loop for a fixed amount of time before using futex support to sleep.
Two-phase locks are yet another instance of a hybrid approach, where combining two good ideas may indeed yield a better one. Of course, whether it does depends strongly on many things, including the hard- ware environment, number of threads, and other workload details. As always, making a single general-purpose lock, good for all possible use cases, is quite a challenge.


texts: Correctness of algorithm and its complexity

texts:
I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph.

So, I found this paper proposing an algorithm solving the problem, but I don't really understand the example given on pages 5-6, namely the partition of the graph into complete bipartite subgraph presented on page 6. Also I don't see difference between figures 11b and 11c - it looks that they must differ.

Could anyone explain how authors came to the solution and is it correct?

Paper citation: Mouhoub, Nasser & Benhocine, Abdelhamid. (2012). An efficient algorithm for generating AoA networks. International Journal of Computer Science Issues. 9.

Direct link to pdf: link.


texts: What is the name of the optimization that removes self eliminating multiplication-division statements?

texts:
I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it.

Given an integer x, not known at optimization time, a known constant c and the following program

x_1 = x * c
x_2 = x_1 / c
print(x_2)

It's pretty clear that the code can be optimized to

print(x)

What is the name of this optimization? Is there a paper/book describing it?

Thanks!


texts: Find expression with minimal distance to target

texts:
I will start of with an informal example and give a more formal problem definition later.

Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and multiplication, we can construct expressions like $(\pi + 2.3) * 0.3 + 4.382$ and $(0.3 + \pi) * (2.3 + 4.382)$. We put the following constraints on the expressions:

Each value in the set must be used exactly once in the expression.
We can only use addition, multiplication and brackets in our expression.

The goal now is to get as close to a target value, say $9.5$. For example, the expression $2.3 * \pi * 4.382 * 0.3 = 9.49886...$ gets close. How can we find the expression whose evaluation is closest to $9.5$? Or more formally:

  Given a finite set $V$ of - not necessarily unique - elements, two
  binary operands $f(x, y)$ and $g(x, y)$ that operate on the elements
  in $V$ and a target value $t$, find the expression $E$ containing each
  element of $V$ exactly once, such that the evaluation of $E$ is as
  close to $t$ as possible. $E$ must consist only of the values in $V$,
  the given operands and brackets.

I understand that for small sets, an exhaustive check that checks all possible expressions is feasible. Using heuristics, quickly finding an approximate answer (with small distance to the target) is probably possible for larger sets too. My questions are; does a more efficient method exist to find exact answers for large sets? Do efficient methods exist specifically for certain operands? What fields of mathematics and computer science touch on this subject?


texts: Is selection in genetic algorithm considered to be a genetic operator?

texts:
It is listed as such in wiki, however my literature never refers to it as such.
My gut tells me to follow papers and monographs on the matter, but my concern is that I will make an easily avoidable mistake, or that I simply misunderstood the text.


texts: Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

texts:
Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators.

Is it the case that the construction of the SLR(1) parser and the LALR(1) always yield the same table?

If not, what happens if the grammar G is SLR(1)?

I'm particularly interested in this question about the following grammar:

\begin{align*}
    C &\to E \, \text{rel} \, E \mid C \& C \mid ! \, C \mid \text{pred}\, ( \,Es\, ) \\
    E &\to \text{num} \mid \text{id} \mid E\, +\, E \mid E\, *\, E \mid - \,E \mid ( \,E \,)  \\
    Es &\to E \mid E\, ,\, Es
\end{align*}

Using a custom SLR and LALR table generator I obtain exactly the same table for the above grammar, with some shift/reduce conflicts that can be resolved by giving precedences in the order &, !, rel, +, *, - and left associativity to &, + and *.  I'm in doubt whether my implementation is incorrect or the tables are really the same, and if this is the case whether there is some general rule that applies in certain circumstances.


texts:
I'm given a more restricted version of 3-SAT called 3-SAT-M:

Problem: 3-SAT-M
INPUT: A set of clauses C {c1,...,ck} over n boolean
variables {x1,...,xn}, where every clause contains exactly three
literals (as in 3-SAT).
OUTPUT: YES if there is a truth assignment to
the boolean variables such that the following constraints are
satisfied:

Every clause is satisfied under the assignement
There are at least k/2 clauses in which all 3 literals are set to true under the assignment.

NO otherwise.

So from what I understand it is the same as 3-SAT apart from the second constraint which demands that at least half of the clauses have all 3 variables set to true under the assignment.
I want to prove that 3-SAT-M is NP-Complete by showing how 3-SAT can be reduced to 3-SAT-M in polynomial time.
I'm having a hard time coming up with such a transformation that can show the reduction. I've tried by introducing some extra helper variables but it doesn't seem to be working out.
Any help would be appreciated.
EDIT: What I have tried:
Ok, so say for my 3SAT problem instance I have k clauses each with 3 variables. If I add k new clauses and 3k new variables (which are all set to true). So new k = 2* (old) k.
This means that I now satisfy the 2nd constraint of 3-SAT-M as at least k/2 of the clauses have all variables set to TRUE.
Is this correct?


texts: How can I get O(1) prepend on a random-access list?

texts:
I need a data structure that has the following operation:

$\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$

$\operatorname{prepend}$ should be in $O(1)$.

Assume that you have only randomly-accessible lists available. That is the following operations are available that are all in $O(1)$:

$\operatorname{update}([x_n, ..., x_0], i, y) = [x_n, x_{i + 1}, y, x_{i - 1},  x_0]$
$\operatorname{at}([x_n, ..., x_1], i) = x_i$
$\operatorname{append}(([x_n, ..., x_1], x_0) = [x_n, ..., x_0]$

You could of course reverse the list in $O(n)$ each time but then $\operatorname{prepend}$ would also be in $O(n)$. So the list has to be reversed in real-time at each call of $\operatorname{prepend}$. Is there such data structure?


texts: How priority queue is used in Dijsktra algorithm?

texts:
I have difficulties understanding how the priority queue is used in Dijkstra algorithm. Wikipedia lists 3 operations performed on priority queue:

add_with_priority(),
extract_min(),
decrease_priority().

With the first two I have no problems, both operations are screaming fast. But the last one is executed with the point at hand, not distance. So one has to first lookup the appropriate entry in the queue and if I am not mistaken you do this by simply iterating all elements (slow) or you use additional structure (associative array) which maps points into priority queue elements (but in total this won't be constant time).

So do I miss something or I can forget about constant time for decrease_priority (because it only applies from the moment when you have given entry already found)?

Sorry for not adding Dijsktra tag but I am with low rep here.


texts: Algorithm to find shortest lightest path in a graph from source

texts:
Given a directed graph $ G = (V,E)$  with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $

Problem: Find the lightest path from $s $ to each and every vertex $v \in V$ and that's from the shortest paths from $ s$ to all $v \in V$

Length of a path is the number of edges in the path.

Weight of a path is the sum of all weights of the path's edges

-------- Edit: Elaborating the question: --------

Suppose there are $x$ different paths between $s$ and some $v \in V$.
Each path has its own weight.
Among those $x$ paths, there are $y$ shortest paths(pay attention $ y \subseteq x$ and all the paths in $y$ have the same length).

What I'm trying to find: The lightest path among the above $y$ paths. Also, i want to calculate that weight for every vertex in $V$.

Initially, i thought about this algorithm:

run BFS on $G$ from source $s$
run Dijkestra on the BFS tree from step 1

However, i ran into this problem:

With source vertex $A$, the red path and the black path, both lead to the same vertex $D$.

Pay attention how $ A\rightarrow B\rightarrow D$ and  $A \rightarrow C \rightarrow D$ are both of length 2
Although they are both the shortest paths from $A$ to $D$, the red path is lighter than the black one.

I thought about 'tweaking' BFS:

Each time i arrive at a vertex $v$ which i already discovered, i check whether the "new" path i already walked to $v$ is lighter than the one already set to $v$.

However, i don't want to change in the algorithm, because i need to prove that it actually work from the start.

How can i modify my algorithm so that the problem i pointed won't pop-out?


texts: Growing context-sensitive grammars with context-free rules

texts:
Has anyone ever considered the class of languages $X$ generated
by growing context-sensitive productions which are described by context-free rules?

In particular, I wonder if there is a NP-complete language inside this class.

The proof that any language in GCSF is also in $P$ uses the fact that there is a constant $d>1$ such that for all productions $a ::= b$ we have $|b| > d \cdot |a|$, so it does not work for $X$ directly.

It seems that $X$ lies somewhere between GCSF and general CSF, but I am
not so sure even in the second inclusion.

For example, for generating the language $\{a^nb^nc^n \mid n\ge 0\}$
one may write the grammar
$$
\begin{array}{rcl}
S &\to& \varepsilon \mid aBc\\
aB(b^*)c &\to& aaB(b^*)bcc\\
B &\to& b
\end{array}
$$
where $(b^*)$ have to match the same expression in both parts of the second production.
Note that every instance of this production is growing, so it's plausible that
such grammars are nicer than general CSGs or general W-grammars, and so I thought that they might have already be studied by someone.

Of course, this is only a toy example. In the actual problem I'm dealing with, the left part of productions (which goes for $(b^*)$ in the example above) should satisfy quite a complicated balance condition with a few types of brackets.


texts: How to derive the worst case time complexity of Heapify algorithm?

texts:
I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure.
I am asking this question in the light of the book "Fundamentals of Computer Algorithms" by Ellis Horowitz et al. I am adding some screenshots of the algorithm as well as the derivation given in the book.
Algorithm for Heapify():
procedure $HEAPIFY(A,n)$
   //Readjust the elements in A(1:n) to form a heap//
   integer $n,i$
   for $i\leftarrow\lfloor n/2 \rfloor$ to $1$ by $-1$ do
      call $ADJUST(A, i, n)$
   repeat
end $HEAPIFY$

Derivation for worst case complexity:

I understood the first part and last part of this calculation but I cannot figure out how $2^{i-1}(k-i)$ changed into $i 2^{k-i-1}$.
All the derivations I can find in the internet takes a different approach by considering the height of the tree differently. I know that approach also leads to the same answer but I would like to know about this approach.
You might need the following information:
$2^k-1 = n$ or approximately $2^k = n$, where $k$ is the number of levels, starting from the root node and the level of root is 1 (not 0) and $n$ is the number of nodes.
Also the worst case time complexity of the Adjust() function is proportional to the height of the sub-tree it is called, that is $O(log n)$, where $n$ is the total number of elements in the sub-tree.


texts: Making Candies - HackerRank question - proof of optimality of a greedy approach

texts:
I stumbled across this question in HackerRank:

  Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies.
  Karl just started a level in which he must accumulate $n$ candies starting with $m$ machines and $w$ workers. In a single pass, he can make $m \times w$ candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers. Buying a machine or hiring a worker costs $p$ units, and there is no limit to the number of machines he can own or workers he can employ.

  Karl wants to minimize the number of passes to obtain the required number of candies at the end of a day. Determine that number of passes.

  For example, Karl starts with $m=1$ machine and $w=2$ workers. The cost to purchase or hire, $p=1$ and he needs to accumulate $60$ candies. He executes the following strategy:

  Make $m \times w = 2$ candies. Purchase two machines.

  Make $3 \times 2 = 6$ candies. Purchase $3$ machines and hire $3$ workers.

  Make $6 \times 5 = 30$ candies. Retain all $30$ candies.

  Make $30$ candies. With yesterday's production, Karl has $60$ candies.
  It took $4$ passes to make enough candies.

The hypothesis is that the greedy approach, where we always spend as much money as possible to purchase workers/machines (until the last pass where we wait one more time to gather enough candies) is the optimal one. If this is the case - why?


texts: What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

texts:
In other words, what is the likelihood that a recognizer of a given regular language will accept a
random string of length $n$?

If there is only a single non-terminal $A$, then there are only two kinds of rules:

Intermediate rules of the form $ S \to \sigma S $.
Terminating rules of the form $ S \to \sigma $.

Such a grammar can then be rewritten in shorthand with exactly two rules, thusly:

$$\left\{\begin{align}
&S  \enspace \to \enspace \{\sigma, \tau, \dots\} S = ΤS\\
&S  \enspace \to \enspace \{\sigma, \tau, \dots\} = Τ'\\
\end{align}\right.\\ \space \\
(Τ, Τ' \subset \Sigma) $$

So, we simply choose one of the $Τ$ (this is Tau) symbols at every position, except for the last
one, which we choose from $Τ'$.

$$ d = \frac {\lvert Τ\rvert^{n - 1} \lvert Τ' \rvert} {\lvert\Sigma\rvert^n} $$

I will call an instance of such language $L_1$.

If there are two non-terminals, the palette widens:

Looping rules of the form $ S \to \sigma S $.
Alternating rules of the form $ S \to \sigma A $.
Terminating rules of the form $ S \to \sigma $.
Looping rules of the form $ A \to \sigma A $.
Alternating rules of the form $ A \to \sigma S $.
Terminating rules of the form $ A \to \sigma $.

In shorthand:
$$\left\{\begin{align}
&S  \enspace \to \enspace Τ_{SS} S \\
&S  \enspace \to \enspace Τ_{SA} A \\
&S  \enspace \to \enspace Τ_{S\epsilon} \\
&A  \enspace \to \enspace Τ_{AA} A \\
&A  \enspace \to \enspace Τ_{AS} S \\
&A  \enspace \to \enspace Τ_{S\epsilon} \\
\end{align}\right.\\ \space \\
(Τ_{SS}, Τ_{SA}, Τ_{S\epsilon}, Τ_{AA}, Τ_{AS}, Τ_{S\epsilon} \subset \Sigma) $$

Happily, we may deconstruct this complicated language into words of the simpler languages $L_1$ by
taking only a looping rule and either an alternating or a terminating shorthand rule. This gives us four
languages that I will intuitively denote $L_{1S}, L_{1S\epsilon}, L_{1A}, L_{1A\epsilon}$. I will
also say $L^n$ meaning all the sentences of $L$ that are $n$ symbols long.

So, the sentences of this present language (let us call it $L_2$) consist of $k$ alternating
words of $L_{1S}$ and $L_{1A}$ of lengths $m_1 \dots m_k, \sum_{i = 1 \dots k}m_i = n$, starting
with $L_{1S}^{m_1}$ and ending on either $L_{1S\epsilon}^{m_k}$ if $k$ is odd or otherwise on
$L_{1A\epsilon}^{m_k}$.

To compute the number of such sentences, we may start with the set $\{P\}$ of integer partitions
of $n$, then from each partition $P = \langle m_1\dots m_k \rangle$ compute the following numbers:

The number $p$ of distinct permutations $\left(^k_Q\right)$ of the constituent words, where $Q = \langle q_1\dots\ \rangle$ is the number of times each integer is seen in $P$. For instance, for $n = 5$ and $P = \langle 2, 2, 1 \rangle$, $Q = \langle 1, 2 \rangle$ and $p = \frac{3!}{2! \times 1!} = 3$
The product $r$ of the number of words of lengths $m_i \in P$, given that the first word comes
from $L_{1S}$, the second from $L_{1A}$, and so on (and accounting for the last word being of
a slightly different form):

$$ r = \prod_{i = 1, 3\dots k - 1}\lvert L_{1S}^{m_i} \rvert
   \times \prod_{i = 2, 4\dots k - 1}\lvert L_{1A}^{m_i} \rvert
   \times
        \begin{cases}
            & \lvert L_{1S\epsilon}^{m_k} \rvert &\text{if $m$ is odd}\\
            & \lvert L_{1A\epsilon}^{m_k} \rvert &\text{if $m$ is even}\\
        \end{cases}
   $$

If my thinking is right, the sum of $p \times r$ over the partitions of $n$ is the number of
sentences of $L_2$ of length $n$, but this is a bit difficult for me.

My questions:

Is this the right way of thinking?
Can it be carried onwards to regular grammars of any complexity?
Is there a simpler way?
Is there prior art on this topic?


texts: Intuitive proof for a tree with n nodes, has n-1 edges

texts: I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.


texts: Are all foldable data structures also recursive?

texts:
I was checking what Wikipedia has to say on reduce. It says:

  In functional programming, fold (also termed reduce, accumulate,
  aggregate, compress, or inject) refers to a family of higher-order
  functions that analyze a recursive data structure and through use of a
  given combining operation, recombine the results of recursively
  processing its constituent parts, building up a return value.

This raises the question: Are foldable data structures always recursive (or can be seen as such)?
This is obvious for things such as lists and trees (in Haskell):

data List a = Nil | Cons a (List a)

data Tree a = Empty | Node (a, Forest a)

data Forest a = Nil | Cons (Tree a) (Forest a)

In other words, are all iterable data structures also recursive?*
How would one go about proving this?

*I'm assuming that being iterable is sufficient to be foldable.


texts: Binary Tree Multithreaded Time Complexity

texts:
Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then wouldn't the big O time complexity be O(log n). I was under the impression that you could never traverse an entire tree in less than O(n) since you'll have to search each node. However, it seems like by using multithreading, one can reduce the amount of nodes to be searched in half at each node.

Would the space complexity still be the same O(n)? Also, if the the time complexity really is O(log n), are there any optimizations that could possible make it a bit faster?


texts: Why cant I Just create a TM A that runs a NTM B with a formula to compute the SAT Problem and Just Flip its Output. So when the Input NTM B Returns true (formula is satisfyable) the TM A Return false.


texts: Definitions for Validity, Consistency, Integrity, Soundness and Completeness in Proof Systems

texts:
I have always tried to understand the difference between all the above, but I always ended up being confused. The field I am referring to is cryptography in particular, but I guess this question is valid for all of computer science.

Is there a proper way to understand and differentiate them all?

--

In my notes so far:

Completeness: all the true statements are provable
Soundness: all the false statements are not provable (or no false statement is provable, or every statement that’s proven is true)
Validity: all the statements are true (a system is valid iff it is sound and complete (?))
Consistency: (?)
Integrity: (?)


texts: Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?

texts:
I have an algorithm with this time complexity:
$$ T(n) = O(n) + \frac{n}{\log n} \cdot \log \frac{n}{\log n}. $$
I tried to figure out how to solve this
and I tried to say something like this :
if I have $\frac{\log n}{n}$ then the value is going to be very small, if I switch between them the value becomes very big,
so I came to this: $T(n) = O(n)+$ something very big.
I am trying to determine if the result is larger than linear time or not, but I am lost.


texts:
There is an exceptionally simple way to embed simply typed lambda calculus with de Bruijn indices in a functional host language (discussed by Carette, Kiselyov & Shan, and by Kiselyov). The construction here, expressed in Haskell, is from Kiselyov's paper:

z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

lam :: ((a, b) -> c) -> b -> a -> c
lam e h x = e (x, h)

app :: (a -> b -> c) -> (a -> b) -> a -> c
app e1 e2 h = e1 h (e2 h)

eval :: (() -> a) -> a
eval e = e ()

So, for example eval (lam (lam (app z (s z)))) 2 succ evaluates to 3, as our lam expression eval's to the Haskell value \x -> \f -> f x.

This embedding uses de Bruijn indices: to find the binder of a variable, count upward from the variable. I am curious about whether there is an analogous embedding of de Bruijn levels, where to find a variable's binder we count downward. Concretely, \x -> \f -> f x would be represented in such an embedding as lam' (lam' (app' (s' z') z')).

The above embedding uses (as Kiselyov notes) nothing beyond the Hindley-Milner subset of Haskell 2010. It is not obvious to me whether de Bruijn levels can be implemented in such a simple type system. Indeed, it seems quite difficult: the environment tuples built by lam would need to be turned inside-out, or our variables would need to behave differently depending on the depth of the environment tuple. If we only had variables of one type, we could use lists; given that our variables have multiple types, do we require HLists?

======

Late edit to expand on the points in the last paragraph...

One way to think about de Bruijn levels is that lam append's (rather than cons's) to the environment. This way, from the perspective of a variable, the head of the environment (in a closed term) will always correspond to the highest lam. In terms of homogeneous lists:

zL :: [a] -> a
zL (x:h) = x

sL :: ([a] -> b) -> [a] -> b
sL v (_:h) = v h

lamL :: ([a] -> b) -> [a] -> a -> b
lamL e h x = e (h++[x])

appL :: ([a] -> b -> c) -> ([a] -> b) -> [a] -> c
appL e1 e2 h = e1 h (e2 h)

evalL :: ([a] -> b) -> b
evalL e = e []

This models de Bruijn levels, in the sense that lamL (lamL (sL zL)) [] 2 3 evaluates to 3. But it isn't simply typed lambda calculus, since it only allows variables of one type -- e.g., lamL (lamL (appL (sL zL) zL)) is a type error.

To allow variables of multiple types, we can use HList:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeOperators #-}

import Data.HList

zH :: HList (a ': b) -> a
zH (HCons x h) = x

sH :: (HList a -> b) -> HList (c ': a) -> b
sH v (HCons _ h) = v h

lamH :: HAppendList a '[b] =>
        (HList (HAppendListR a '[b]) -> c) -> HList a -> b -> c
lamH e h x = e (hAppendList h (HCons x HNil))

appH :: (HList a -> b -> c) -> (HList a -> b) -> HList a -> c
appH e1 e2 h = e1 h (e2 h)

Then lamH (lamH (appH (sH zH) zH)) HNil 2 succ evaluates to 3, as desired. But this is a significantly heavier-duty approach than the embedding we began with. Do de Bruijn levels require all this artillery?


texts:
I am working on some lossless compression topic and looking on any resources or prior studies on lossless file entropy predictability.

Assuming we know type of the file (we can tell its belongs to certain group and it is not falsified). Can we predict file entropy of any file in that group of files based on its size?

Groups like:
Books with English text (I am assuming the answer is yes), binary files (like from Apple App Store), maybe some web data, or text snippets for big data (like twitter data). Or even sensor data generated from particular simulation or sensors.


texts: Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?

texts: In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the traversal is completed, we claim that the maximal matching is found. But why don't we need to check again the vertices for which we weren't able to build the increasing chain? How can we prove that if for some vertex v it was not possible to build the increasing chain starting with v during the traversal, then we don't need to check v again? Why shouldn't we perform the second traversal?


texts: Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

texts:
It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example:
$$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n \mid m,n \ge 1 \right\} = \left\{ a^ib^ic^i \mid i \ge 1 \right\} \not \in \mathcal{L_2},$$
where $L_1,L_2 \in \mathcal{L2}$.

I was wondering if this could be proven using the synchronous parallel composition of two (non-deterministic) PDAs, or rather what is wrong with the following construction which seemingly comes to the opposite conclusion:

  Let $PDA_1, PDA_2, PDA_{1,2}$ be, WOLOG, (non-deterministic) PDAs accepting by final state and with total transition functions:
  $$ PDA_1 = \Big(Q_1, \Sigma_1, \Gamma_1, \delta_1, q^0_1, \gamma^0_1, F_1 \Big) \\
PDA_2 = \Big(Q_2, \Sigma_2, \Gamma_2, \delta_2, q^0_2, \gamma^0_2, F_2 \Big) \\
PDA_{1,2} = \Big(Q_1 \times Q_2 \cup \big(q_{\emptyset}, q_{\emptyset}\big), \Sigma_1 \cup \Sigma_2, \Gamma_1 \times \Gamma_2, \delta_{1,2}, \big(q^0_1, q^0_2 \big), \big(\gamma^0_1, \gamma^0_2 \big), F_1 \times F_2 \Big)$$
  where $q_{\emptyset} \not\in Q_1 \cup Q_2$ and $\delta_{1,2}$ is defined as follows:
  $$ \delta_{1,2} \Big(\big(q_1, q_2 \big), a, \big(\gamma_1, \gamma_2 \big) \Big) = \begin{cases}
    \Big(\big(q'_1, q'_2 \big), \big(\gamma'_1, \gamma'_2 \big) \Big) & \big(q'_1, \gamma'_1 \big) \in \delta_1 \big(q_1, a, \gamma_1 \big) \land \\ & \big(q'_2, \gamma'_2 \big) \in \delta_2 \big(q_2, a, \gamma_2 \big) \\
& \text{(if such transitions are defined)} \\
    \Big(\big(q_{\emptyset}, q_{\emptyset} \big), \big(\gamma_1, \gamma_2 \big)\Big) & \text{otherwise} \\
\end{cases} $$

Surely $PDA_{1,2}$ accepts only words from the intersection of languages $L(PDA_1)$ and $L(PDA_2)$. Why doesn't it accept all of them?


texts: Language intersections (set theory) - Understanding better

texts:
I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of the class, which is a specific mathematics level. I am a low level mathematics student, I don't really know formal mathematics or any proofs besides a simple proof like proving that an angle is 90 degrees.

So besides programming, there is this subject we started studying about finite deterministic automatons, stack automatons, turing machines and regular languages, etc.

I understand the concept very well, especially when it comes to building turing machines, finite and stack diagrams. At the class, we solve these automatons with diagrams, not in a formal way.

So besides that, my teacher gives us a lot of questions about union, intersection and I am getting really confused with intersection.

Surely I can understand the basic intersections with set of words:

$L = \{aab, bba, aa\}$
$L' = \{a, bbba, aab, aa\}$

So $L\cap L'$ would be $\{aab, aa\}$

I also understand basic language intersections like this:

$L = \{a^n b^n \mid n \ge 0\}$, $L' =  \{a^n \mid n \ge 0\}$

$L\cap L'$ would be $\{a^n \mid n \ge 0\}$

But when it comes to something like this:

$L = \{a^{2n} b^m a^k \mid n,m \ge 0, k = m \mod 2\}$

$L'$ = set of string elements such that the length $|w|$ is even

$L\cap L'$ = I don't know the answer for

The second part of the language which defines the length of the elements (e.g on $n$, of $m$, of $k$) really confuses me in intersections and unions, I am not really sure why. Does that part matters in intersections? I am always getting lost in these cases.

How can I understand this concept a bit better mathematically?


texts: Why is push_back in C++ vectors constant amortized?

texts:
I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is itself up to linear in the entire size."

Shouldn't this mean the push_back function is $O(n)$, where $n$ is the length of the vector? After all, we are interested in worst case analysis, right?

I guess, crucially, I don't understand how the adjective "amortized" changes the running time.


texts: Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

texts:
I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution.

The degree distribution is the relative frequency of vertexes in the original graph that have a certain degree.

The clustering coefficient distribution is the relative frequency for each vertex degree of two neighbours (of a vertex with that degree) to have a link between them.

Does anybody know any literature and algorithm to do this? The stuff I have found was always very theoretical..

Thanks!


texts:
Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. Consider $f$ to be a symmetric function that takes $k$ arguments.

More specifically, we are given $n = 120$ items, each item being associated with three positive numbers $(A_i, B_i,C_i)$, and we want to choose $k=12$ items within this set such that

$$ \frac{\sum_{k=1}^{12} A_{i_k} \times \left\lceil\frac{\sum_{k=1}^{12} B_{i_k}}{10000}\right\rceil}{\sum_{k=1}^{12} C_{i_k}} $$

is maximal.

If we solve it by exhaustive search it requires $\binom{120}{12} \approx 10^{16}$ operations. Is there faster method to this problem? Approximate solution is also fine.


texts: Minimum path cover--- Disjointed paths with minimum total number of edges

texts:
Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ pairs of nodes in the set $\mathcal{V'}$. For each pair of nodes $(w,w')$ in the set $\mathcal{V'}$, there is a unique path form $w$ to $w'$ lets call it $\text{path}(w,w')$ and it contains all the edges in the path of $w,w'$. I would like to find a collection of pairs of nodes of $\mathcal{V'}$, where each node of $\mathcal{V'}$ appears in one pair exactly, thus we have $m$ pairs in total in the final desired collection. Lets call that collection of pairs $F(\mathcal{V'})$, also, $F(\mathcal{V'})$ should be found such that the total number of edges in the paths $\text{path}(w,w')$ is minimum, where $(w,w')\in F(\mathcal{V'}):$$$\min_{F(\mathcal{V'})} \sum_{(w,w')\in F(\mathcal{V'})} |\text{path}(w,w')|. $$ Notice that a necessary condition for the choice of pairs $F(\mathcal{V'})$ is that the paths should be disjointed (have no common edges), otherwise we have a total number of edges greater than the minimum possible.

I would like to know what the algorithm is that finds $F(\mathcal{V'})$ in polynomial time. Is this related to the Hamiltonian cycle problem? My graph is acyclic which should help to get a polynomial time algorithm.  *By disjointed paths I mean paths with no common edges, they may have common vertices. **By minimum path cover I mean the total number of edges in the collection of paths is minimum since the number of paths is always chosen to be $m$.


texts: Undecidability of the language of PDAs that accept some ww

texts:
I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation,
"Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$. Use the computation history method to show that this problem is undecidable."
I have an attempt at a solution but somehow I just feel kind of foggy on whether it's correct and would appreciate anyone finding flaws in the solution.

For reference, I'm trying to mimic or adapt the solution given earlier in the chapter to
$$ ALL_{CFG}=\{\langle G\rangle | G \text{ is a CFG and } L(G)=\Sigma^*\}$$
Theorem: $ALL_{CFG}$ is undecidable.
The proof given there reduces from $A_{TM}$ the decision problem of checking whether a TM called $M$ accepts a string called $w$.  It does so by, for any fixed $M,w$, constructing a CFG $G$ which produces all possible strings if and only if $M$ accepts $w$.  In particular $G$ is the CFG which generates all the strings that are NOT accepting histories for $M$ on $w$.
It then proceeds to show how to build such a $G$.  For the purposes of the problem I'm asking about, I can just accept that this is possible.

Also for reference, there is this answer to a similar question on here: https://cs.stackexchange.com/q/6629
I particularly want to follow the textbook's guidance in order to practice this method of using a computation history, so I'm ignoring the first answer to the problem. However, I don't understand the answer given for computation histories.  The CFG that he gives (or equivalent PDA) doesn't seem to generate strings with at least one $v!v$ if and only if $M$ accepts $w$.  Supposing $M$ accepts $w$ I don't see a reason why $C_0\#...\#m(C_{2n})\#C_f = C_1'\#...\#m(C_n')$.

My solution is, like in the book's solution for $ALL_{CFG}$, to try to use $M$ and $w$ to build a CFG such that $M$ accepts $w$ if and only if $G$ generates some string of the form $vv$.  In particular $G$ is the grammar defined by the PDA $D$ which on input $x$ checks the first half to see if it's an accepting history of $M$ for $w$, and then checks the second half to see if it equals the first half.  I believe each of these are things any PDA can do, and once built, $G$ will have the properties promised earlier.  Am I making any mistake here?


texts: Generate a unique number for a set of sequences of letters

texts:
A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I need to search if the $w$ exists in the database of words.

The framework of the database and the application is on the web and this job is part of an online game, So may be hundreds of requests come to website in a second so I need to do it as fast as possible. To do so as fast as possible, I want generate a unique number for every word in the database. For every string query, I generate its number using the algorithm used to generate numbers for the database, then check if the new number exists in the database or not using binary search tree.

Here is an algorithm that works perfectly to generate a unique number for a sequence:

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i \in \mathbb{Z^{+}}$ (it is easy to map every letter to a number) the unique number is

$$
\prod_{i=1}^{n}{p_i^{a_i}}
$$

where $p_i$ is the $i$-th prime number. But the problem is, the produced numbers are too large to be stored in current programming language variables.

My Solution

First I set the following mapping:

$MAP: [a=>2, b=>3, c=>5, \cdots, z=>101]$

So I set the $i$-th prime number to the $i$-th letter. (Actually it is not necessary to regard this order, more frequent characters can take smaller prime number)

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i$s are letters this is my formula:

$$
\prod_{i=1}^{n}{MAP(a_i)^i}
$$

For valid words, this formula generally, produces smaller numbers than the first one. I just wanted to know :

if this formula always generates a unique number? I couldn't generate two words with the same numbers, but clearly it is not enough to convince other people
Is there any solution that search for words in $O(\log n)$ (like binary search tree)?

thanks.


texts: Can we think of a non-symmetric product type in Haskell?

texts:
Meta note: I asked this question here a while ago. It got an answer:

type a /\!! b = (a, ((b -> Void) -> Void))

Unfortunately, I do not reckon it to be quite right: () /\!! a ≅ a does not hold.
I do not want to delete the question on Stack Overflow as the answerer still put quite some effort in (and I did not manage to migrate it here). I will close it as a duplicate, if I get the fitting answer here, if that's alright. We discussed this issue on Meta.SE.

Control.Category.Constrained.Cartesian is a class for monoidal categories with some natural transformations (the product is (,) and the unit defaults to (); the product cannot be changed, unlike the sum in Control.Category.Constrained.CoCartesian).

regroup and regroup' are for (a, (b, c)) ≅ ((a, b), c);
attachUnit and detachUnit are for a ≅ (a, unit).

They almost give us the monoid. The only thing that is left is (unit, a) ≅ a. Here we use (,) being symmetrical: (a, b) ≅ (b, a).
As far as I know, it is not a general property. Bartosz Milewski attributes the property to symmetrical monoidal categories (for example, here).
Is there some product type in Haskell which is not symmetrical?


texts: Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

texts:
A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply making the gap larger for example.

UTF-8 is a variable width encoding for text. The first bits of the first byte of a character describes how many bytes are in the character, to a maximum of four.

When describing a cursor position in a string, (specifically a position between characters), we can use a pair consisting of the line number, (let's say we start at zero), and the horizontal character offset (how many characters to the right the cursor is from the position to the left of the first character on the line). It is useful to use this representation to position a cursor.

However, in order to move the byte offsets that determine where the buffer's gap is we need to convert the line number and character offset to a byte index.

The best way I currently know how to do this is the following $O(n)$ algorithm:

Call the line number and character offset we are looking for the byte offset of,
"the target".

Keep track of the current line number and character offset as we go, starting each at 0.

for (the characters before the gap) {
    if the current line number and character offset matches the target,
        return the byte offset.
}

if the space right after the last character before the gap matches the target,
    return the byte offset of the start of the gap.

for (the characters after the gap) {
    if the current line number and character offset matches the target,
        return the byte offset.
}

if the space right after the last character after the gap matches the target,
    return the byte offset of the end of the buffer.

Otherwise, the cursor is out of bounds.

This is all under the assumption that the buffer is well-formed. That is, the gap starts immediately after a UTF-8 character, and the gap ends just before another one, or the end of the entire buffer.

Is there a way to do this with a lower computational complexity than $O(n)$? If I try to imagine one, the closest I can get is to try something like binary search, but that seems like finding a pivot point (past maybe the first one which we could cache,) would involve iterating over the buffer anyway, so it wouldn't actually be $O(\log n)$.


texts: Tag, index and offset of associative cache

texts:
My main issue of a homework problem is trying to figure out the different parts of the chart. I have a 3 way set associative cache with 2 word blocks, total size of 24 words. I am given $3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253$ to try to map.

What I have so far and where I am stuck:

My main problem is trying to figure out how to find the index and offset of associative (3-way set) cache. Since I have 3 sets, is it: $3 \bmod 3 = 0$, so $0$ is the index? $180 \bmod 3 = 0$ index as well? And would it looks like the following:

$$
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\text{Block} & \text{Ix} & \text{Hit/Miss} &
\text{Set 0} & \text{Set 0} &
\text{Set 1} & \text{Set 1} &
\text{Set 2} & \text{Set 2} \\\hline
3 & 0 & \text{miss} & \mathit{mem}[3] \\
180 & 0 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] \\
43 & 1 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] \\
2 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] \\
191 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] & \mathit{mem}[191] \\\hline
\end{array}
$$
etc...

Somehow I feel like this is all wrong, because of some sample problems I have seen. But in class, this is how I remember it being explained. Helping me understand the fundamentals of this problem would be so helpful and I appreciate all the help I can get. Sorry if it doesn't seem like I have put a lot of work into this, but I am familiar with only directly mapped cache and the sample problems I have seen aren't very explanatory.


texts: Converting a number to 16-bit Floating Point Format

texts:
I want to convert the number -29.375 to IEEE 745 16-bit floating point format. Here is my solution:

The format of the floating point number is:
     1 sign bit
     unbiased exponent in 4 bits plus a sign bit
     10 bits for the mantissa plus the explicit 1

First, I realize that 29.375 = 29 + 3/8.
Then realize that:
     29 = 16 +13 = 16 + 8 + 5 = 16 + 8 + 4 + 1
     1 1101.011 = 1.1101 0110 * 2^3

This gives us:
mantissa is: 1101 011000
sign: 1
exp: 00011

Hence in 16 bits, we have:
    1000111101011000

Do I have this right? I was hoping that there would be a calculator on the web that I could use but I could not find one. They were all at least 32-bits.


texts: Fixed base exponentiation with precomputations

texts:
I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm following is Brickell et. al. "Fast Exponentiation with Precomputation: Algorithms and Lower Bounds" which can be found here.

Basically the idea is to precompute $g^{b^i}$ where $b$ is a radix. Now if we write $m$ in the radix base: $m=\sum_{i=0}^k e_i b^i$ then $g^m=\prod (g^{b^i})^{e_i}$. For example: say we want to compute $g^{142}$ and we have chosen as radix $b=3$ (I'm aware of the more natural example of radix 2, but I'm experimenting with different radices to see if there is any speed-up). I write $m=(12021)_3$ and compute $g^{142}=g^{3^4}\times(g^{3^3})^2\times (g^3)^2 \times g^3$.

The pseudo code given in the paper is:

b ← 1
a ← 1
for d = h to 1 by −1
    for each i such that a_i = d
        b ← b ∗ g^{x_i}
    a ← a ∗ b.
return a.

where $h$ is the range of $e_i$, and $a_i=e_i$ and $x_i=g^{b^i}$.

My question is: instead of going through $e_i$ by tier as the pseudo code suggested, why don't we go through the base $b$ representation of $m$ one digit at a time and multiply as we go?

When I looked up fixed-base exponentiation in Henk and Tilborg "Encyclopedia of Cryptography and Security," they say that "there is time saved by multiplying together powers with identical coefficients, and then raising the intermediate products to powers step by step." I believe this is hinting at the answer to my question, but I don't understand the reasoning.


texts:
I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will appreciate if someone could shed the light on this topic so that I will be able to continue by myself.
Few following sentences are questions and my thoughts about relativization, they will help to navigate the discussion.

Very often relativization comes in comparison with diagonalization, which is a method that helps distinguish between countable set and uncountable set. It somehow comes from relativization that $P$ versus $NP$ question cannot be solved by diagonalization. I don't really see the idea why relativization show the useless of diagonalization, and if it's useless why is actually useless.

The idea behind oracle Turing machine $M^A$ at first is very clear. However, when it comes to $NP^A$ and $P^A$ the intuition disappears. Oracle is a blackbox that is designed for special language and answers the question whether the string on the input of the oracle is in the language in time 1. As I understood TM that contains an oracle is just make some auxiliary operations and ask the oracle. So the core of the TM is the oracle, everything else is less important. What's the difference between $P^A$ and $NP^A$, even thought oracle in both of them works in time 1.

The last  thing is the proving the existence of an oracle $B$ such that $P^B \neq NP^B$. I found the proof in several textbooks and in all of them the proof seems very vague. I tried to use "Introduction to complexity" by Sipser, Chapter9. Intractability, and didn't get the idea of construction of a list of all polynomial time oracle TMs $M_i$.

This is more or less everything what I know about relativization, I will appreciate if someonw would decide to share his/her thoughts on the topic.

Addendum: in one of the textbooks I found example of $NP^B$ language (Computational Complexity: A Modern Approach by Boaz Barak Sanjeev Arora. Theorem 3.7. Page 74). $U_B=\left \{ 1^n:some \space string \space of  \space length \space  n  \space is \space  in \space B\right \} $ it's unary language. I believe that (1,11,111,1111,...) are all in $U_B$. Author affirms that such a language is in $NP^B$ which is I cannot understand why, hence oracle for B can resolve everything in time 1. Why do we need nondeterministic TM with oracle. If it's not good example of $NP^B$ please put yours such that to approve the existence of $NP^B$.


texts: Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?

texts:
Let's say I have a ring with four nodes $n=\{0;1;2;3\}$ and three possible states $k=\{0;1;2\}$. A transient failure happens and the system ends up in an illegal state.

I know from the restriction ($k \geq n$) that there should be an execution that makes the system stay in its illegal state indefinitely, but for all the executions I try in my head and on paper, it still stabilises at some point. Could you give me an execution where it loops always back into its illegal state?


texts: Smallest set non-disjoint with other given sets

texts: Given a number of sets, what is the best algorithm to calculate the smallest set S such that S is not disjoint with any of the given sets?


texts: Not understand exchanging argument proof for optimal prefix code

texts:
I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument

Statement: A binary tree corresponding to the optimal prefix code is full

Proof: This is easy to prove using an exchange argument. Let $T$ denote the binary tree corresponding to the optimal prefix code, and suppose it contains
a node $u$ with exactly one child $v$. Now convert $T$ into a tree $T′$ by replacing node $u$ with $v$.
To be precise, we need to distinguish two cases. If $u$ was the root of the tree, we simply delete node $u$ and use $v$ as the root. If $u$ is not the root, let $w$ be the parent of $u$ in T. Now we delete node $u$ and make $v$ be a child of $w$ in place of $u$. This change decreases the number of bits needed to encode any leaf in the subtree rooted at node $u$, and it does not affect other leaves. So the prefix code corresponding to $T′$ has a smaller average number of bits per letter than the prefix code for $T$, contradicting the optimality of $T$.

Number of things I do not understand.

1) I thought in an exchange argument, you assume you have a solution T and an optimal solution $T^{*}$ and you prove that your solution T is no worse than $T^{*}$ implying T is an optimal solution, but they're not doing that here.

2)  They also state that they will "convert $T$ into a tree $T'$ by replacing node $u$ with $v$" but they don't assume that $T'$ is an optimal solution. Why?

3) How does contradicting optimality of $T$ prove that "A binary tree corresponding to the optimal prefix code is full"?


texts:
Just need a little help understanding hardware interrupts.

As I understand (feel free to correct) a hardware interrupts occurs when hardware wants attention of the computer. In basic terms the hardware sends a message down the interrupt line which is then controlled by the PIC. The CPU receives the interrupt and carries out the instruction once it has completed the current one it is on.

Every time I've seen examples of interrupts they have been 'printer running out of paper', 'network adapter receiving data packet' etc. My question is, how is the process of the hardware interrupt any different from pressing a key on a keyboard or moving a mouse? Each of these actions requires attention from the CPU but as I understand they are never used as examples of interrupts. Are they interrupts? Does everything I do with an input device cause an interrupt?

Any clarification would be much appreciated.


texts: How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

texts:
How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:

no or minimal redundancy
only use 1 integer variable or k independent integer variables with a range of [0, ..., j(k)], It means there exist an inverse function f-1(x) to map the encoded sequence, an integer x of the domain [0, 1, ..., |valid sequence| - 1], back the original sequence.
usual integer operations
no or minimal lookup tables
closed form formula to decode back to the sequence without loops or recursions

For example,

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
...
0, 0, 0, m
0, 0, 1, 1
0, 0, 1, 2
...
m, m, m, m

The purpose of this counting function is to enumerate all possible values in the non-decreasing integer sequence later being used in constraints.


texts:
Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?


texts: Can one show NP-hardness by Turing reductions?

texts:
In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions.
Is that possible? How exactly? I thought this was only possible by a polynomial time many one reduction. Are there any references about this?
Are there two different notions of NP-hardness, even NP-completeness? But then I am confused, because from a practical viewpoint, if I want to show that my problem is NP-hard, which do I use?
They started the description as follows:

A  polynomial  time  Turing  reduction from  a problem $P_1$  to  another problem $P_2$  is  an  algorithm  A  which  solves  $P_1$  by  using  a  hypothetical  subroutine A'  for  solving  $P_2$  such  that,  if  A' were  a  polynomial  time  algorithm  for  $P_2$  then  A would  be  a  polynomial  time  algorithm  for  $P_1$.  We  say  that  $P_1$  can  be  Turing  reduced to  $P_2$.
A  problem  $P_1$  is  called  (Turing)  NP-hard  if  there  is  an  NP-complete  decision
problem $P_2$  such  that  $P_2$  can  be  Turing  reduced  to  $P_1$.

And then they use such a Turing reduction from an NP-complete problem to show NP-completeness of some other problem.


texts: Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

texts:
I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG.  (Randomly Generated Number)

Let's begin with the pseudo-code, and then I will go into what I have thought about so far related to this one.

    Func1(A, i, j)
    /* A is an array of at least j integers */

 1  if (i ≥ j) then return (0);
 2  n ← j − i + 1 ; /* n = number of elements from i to j */
 3  k ← Random(n);
 4  s ← 0; //Takes time of Arbitrary C

 5  for r ← i to j do
 6      A[r] ← A[r] − A[i] − A[j]; //Arbitrary C
 7      s ← s + A[r]; //Arbitrary C
 8  end

 9  s ← s + Func1(A, i, i+k-1); //Recursive Call 1
10  s ← s + Func1(A, i+k, j); //Recursive Call 2
11  return (s);

Okay, now let's get into the math I have tried so far.  I'll try not to be too pedantic here as it is just a rough, estimated analysis of expected run time.

First, let's consider the worst case.  Note that the K = Random(n) must be at least 1, and at most n.  Therefore, the worst case is the K = 1 is picked.  This causes the total running time to be equal to T(n) = cn + T(1) + T(n-1).  Which means that overall it takes somewhere around cn^2 time total (you can use Wolfram to solve recurrence relations if you are stuck or rusty on recurrence relations, although this one is a fairly simple one).

Now, here is where I get somewhat confused.  For the expected running time, we have to base our assumption off of the probability of the random number K.  Therefore, we have to sum all the possible running times for different values of k, plus their individual probability.  By lemma/hopefully intuitive logic: the probability of any one Randomly Generated k, with k between 1 to n, is equal 1/n.

Therefore, (in my opinion/analysis) the expected run time is:

ET(n) = cn + (1/n)*Summation(from k=1 to n-1) of (ET(k-1) + ET(n-k))

Let me explain a bit.  The cn is simply for the loop which runs i to j.  This is estimated by cn.  The summation represents all of the possible values for k.  The (1/n) multiplied by this summation is there because the probability of any one k is (1/n).  The terms inside the summation represent the running times of the recursive calls of Func1.  The first term on the left takes ET(k-1) because this recursive call is going to do a loop from i to k-1 (which is roughly ck), and then possibly call Func1 again.  The second is a representation of the second recursive call, which would loop from i+k to j, which is also represented by n-k.

Upon expansion of the summation, we see that the overall function ET(n)  is of the order n^2.  However, as a test case, plugging in k=(n/2) gives a total running time for Func 1 of roughly nlog(n).  This is why I am confused.  How can this be, if the estimated running time is of the order n^2?  Am I considering a "good" case by plugging in n/2 for k?  Or am I thinking about k in the wrong sense in some way?


texts: Intersection of two generative neural networks

texts:
I have an input x (a word), and I have a neural network Y such that Y(x), which is an image always satisfies F(x), and another neural network Z such that Z(x), which is also an image, always satisfies G(x).  Is there any way to turn this into a neural network Q where Q(x), which is also a image, satisfies "F(x) ∧ G(x)"?

Thanks!


texts: Are co-semidecidable languages separated by decidable ones?

texts:
Can I use principles of set theory in order to solve the following question?

  For every $A,B \in \mathsf{co\text{-}RE}$ with $A \cap B = \emptyset$, there is a separating language $C$ with $A \subseteq C$ and $B \cap C = \emptyset$ so that $C$ is recursive.


texts: Using Jaro-Winkler similarity to recognize matching strings

texts:
How do I use the Jaro-Winkler similarity measure to test whether two strings should be considered to match each other?

I tried comparing the Jaro-Winkler score to a fixed threshold: e.g., if the similarity measure is greater than 0.9, consider the two strings to match.  However, this approach does not always work, as shorter strings will return a smaller similarity score.

I also tried the Levenshtein edit distance, but it wasn't adequate for my uses as it did not always guarantee a match.


texts: How to define enumeration of the set of finite state machines?

texts:
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion to the number of states (fewer states more probable). Alphabet = {0,1}
Can you please suggest how to implement this enumeration, encoding / decoding.
Something similar to how in Kolmogorov complexity there is an enumeration for Turing machine programs.


texts: Analysing Dijkstra Algorithm by using different varieties of Data Structure

texts:
Question

  I want to analyse  Dijkstra  Algorithm by using different varieties of Data Structure.

My solution

  Adjacency matrix to Store the Graph and Binary heap for Priority Queue.

    $O(V\,\,log\,V+V^{2}\,\,log \,\,V)=O(V^{2}\,\,log \,\,V)$.

Explanation-:

  In Binary Heap we have $O(log\,\,V)$ for both Extract min and decrease key.

So Extract min for $V$ vertex =$O(V\,\,log \,\,V)$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2}\,\,log \,\,V)$

  Adjacency matrix to Store the Graph and fibonacci heap for Priority Queue.

    $O(V\,\,log\,V+V^{2})=O(V^{2})$.

Explanation-:

  In Fibonacci Heap we have $O(log\,\,V)$ for  Extract min and $O(1)$ for decrease key.

So Extract min for $V$ vertex =$O(V\,\,log \,\,V)$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2})$

  Adjacency matrix to Store the Graph and Sorted Linked List for Priority Queue.

    $O(V\,\,*V^{}+V^{2}\,\,V)=O(V^{3})$.

Explanation-:

  In Sorted Linked list  we have $O(V)$ for both Extract min and $O(V)$ for decrease key.(NOT SURE)

So Extract min for $V$ vertex =$O(V^{2})$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2}*V)$

I am uncertain about point 1 and 2 and  confused regarding sorted linked list's priority queue.Is there some efficent  way through which i can optimize my algorithm.Can anyone please help me out to clear my confusion?
Thanks in advance !


texts: Using AI / Machine learning to find the most time and space efficient solutions to an algorithm

texts:
As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms.

Is it forseeable in the future that we have languages or techniques such as AI/machine learning to automatically find such optimum solutions to any generic algorithm?


texts: How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there?

texts:
For simplicity, we can assume that only NAND gates are allowed.  An asymptotically correct solution is all I really need.

Thanks!


texts: Recognizing finite state machines with repetition

texts:
I'm interested in finite state automata which have the capacity to require repetition.  That is, the machine may be in a state in which the next character may be any character from set $S$, but, whatever character there is, it must be repeated 3 times.  Or it may be in a different state, which requires a character from set $T$ repeated twice.

I could in theory make a different state for each character in set S, and for each character in set T.  But that overcomplicates things and obscures the pattern - it can be any character in set S, but the same character must be repeated.

Is there any standard approach to this? I'm interested both in terminology and in practical code.

Motivation: I do not know the full makeup of the set $S$ or $T$.  I'd like to be able to communicate effectively about the FSM, draw state diagrams, and do implementation, without having to define $S$ or $T$.  In fact, $S$ and $T$ change based on the scenario.  (Now, given a character, it's trivial to tell if it's part of $S$ or $T$ — but, a priori, it's impossible to enumerate them.)

At the least, I'd like a good way to draw a state diagram for these types of machines.  Perhaps I should use a standard FSM with some type of annotation? Could state charts help with this?


texts: Data structure for storing edges of a graph

texts:
I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering exactly how well to represent the edges of the graph.

Each edge is augmented with certain information such as its pheromone value and the number of times an ant has visited that edge. I'll be working with undirected graphs, which can be end up being pretty huge (over a million vertices) and I was wondering what is the most efficient way for me to store the edges and look them up? I was thinking of sticking to a convention and store endpoints according to the one which has a lower vertex id for $v_1$ and the higher one for $v_2$ ($v_1$ and $v_2$ are the endpoints of the edge in the data structure). But I'm wondering how would I perform a look up in this case?

There is a mapping I came up with from the adjacency matrix to the edge array, but that works only if the underlying graph is a complete graph. So I came here for some suggestions as to how I should proceed because I need my lookup to be efficient while at the same time I don't want to blow up the storage space for the edges as the graphs will be huge.


texts:
We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$.
We want to generate a uniform distribution on the set S = $\{0, 1,..., n-1\}$.

Which algorithm gives with probability $1/n$ the value $i\in S$. And how many bits are needed.


texts: Algorithms that run in polynomial time if P=NP

texts: On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking them up and couldn't find any.


texts:
The problem is best illustrated with an example. Consider a trading system in which A sells to B who sells to C.

  A -> B -> C

At some point in the future A needs to deliver the sold goods to B who in turn needs to deliver to C.

From this trivial example it can be seen that A could deliver directly to C without involving B and reducing the number of deliveries:

  A -> B -> C

One constraint is that A might not be able to deliver to C (predefined rules) and in that case the original pathway (A->B->C) would be used

What type of problem is this mathematically? What might I use to assist solving problems of this nature? The inputs to the algorithm would be:

1) A list of all the trades (A sells 99 widgets to B, A sells 31 widgets to C etc)

2) A matrix detailing whether a seller can deliver to any given buyer (A can deliver to B,C,D but not E or F)

Here is another example:

A -> B -> C   (A sells to B who sells to C)

D -> E -> F   (D sells to E who sells to F)

Constraint: A cannot deliver to C

Required:

1) A and D have to deliver

2) C and F have to receive

Answer: A delivers to F; D delivers to C  (2 deliveries)

whereas

Unoptimized: A delivers to B; B delivers to C;D delivers to E;E delivers to F  (4 deliveries)


texts: How many similar binary search trees are made from different permutations?

texts:
If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would have same structure. for example for n=3; we have:

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

In this 2,1,3 and 2,3,1 produce same BST. So for 3 answer is 2.

I have figured out that if I take 3 numbers, and the root is less than one number and greater than other, then the sequence produced is same. ie. for n=9

2,1,3,   5,4,6   8,7,9 and   2,3,1   5,6,4   8,9,7 produce same BST.


texts: Is an error-correcting code where the parity symbols are interleaved with the data symbols considered systematic?

texts:
According to the Wikipedia entry, a systematic code is one

  in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input symbols.

Further down on the same page, it says:

  For a systematic linear code, the generator matrix, $G$, can always be written as $G = [ I_k | P ]$ where $I_k$ is the identity matrix of size $k$.

Consider a systematic code with 4 data symbols ($D_i$) and 2 parity symbols ($P_i$):

$(D_0 D_1 D_2 D_3 \boldsymbol{P_0} \boldsymbol{P_1})$

If we re-order the output symbols such that the parity symbols are interleaved with the data symbols, we get an equivalent code, for example:

$(D_0 D_1 \boldsymbol{P_0} D_2 D_3 \boldsymbol{P_1})$

Would that code still be considered systematic? Clearly, the output does contain the input symbols, but I think the generator matrix could not be written as $G = [ I_k | P ]$.


texts: Algorithm for Dynamic Client Side Throttling

texts:
Problem

I am trying to come up with an algorithm that will dynamically throttle a client's number of outstanding requests based on the response times of completed requests. Response times are unpredictable and can be between 7 and 90 seconds. The response times are greatly affected by the total of outstanding requests, if the server is flooded it bogs down and times increase to very long times.

My specific scenario

My client application has several http requests it needs to send to a server (actually 3 servers that are load balanced and use a round robin distribution, the number of servers and the code running there are out of my control). Each request is a flat object containing 25 parameters. The server uses the parameters to do several look ups which may or may not trigger other look ups and calculations, this is where the server processing time is variable. The server returns a list of corresponding results which can be 0 to approximately 25 in length for most results.

What I have tried

I created a rolling average class that keeps the response times of the last X number of responses and can give the average at any point. Then when each response is received I compare its response time to the average. If the response time is equal or less than the average I increase the number of allowed outstanding requests. If the current response time is greater than the average I decrease allowed outstanding requests.

This approach worked somewhat in scaling up but I had cases where the average just grew over time and allowed more and more outstanding requests which brought everything to a crawl.

I have an implementation question on stackoverflow if you want more details on how I am doing this in code minus the rolling average part.

https://stackoverflow.com/q/30263716/1168353

I have been using a mocked out version of the server that just sleeps a thread before returning a response. I pick a "bestWaitSeconds" that is the fastest time it can return and a "MaxRequestsBeforeDegradation" that determines the maximum number of requests before times increase, anything below that returns bestWaitSeconds. The degradation formula looks like the below and only applies when "currentRequests" is more than MaxRequestsBeforeDegradation.

secondsToWait = (currentRequests - MaxRequestsBeforeDegradation) * (r.NextDouble() + .5) * bestWaitSeconds;

The random is just a way to apply the unknown return time stated in the problem. Times do go well above 90 seconds when the server is overloaded. This formula isn't exactly what the server does but it conveys the idea I think.

So basically the algorithm needs to get as close to MaxRequestsBeforeDegradation as possible. In the real case that MaxRequestsBeforeDegradation would change over long amounts of time so the algorithm also needs to adapt and explore up and down to continually know where the best number of outstanding requests is. Hope this helps.

Summary

How can I dynamically find the optimal number of outstanding requests allowed at a given moment to get the greatest throughput, given only a history of response times?


texts: What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions

texts:
Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the constraint that each run of a value in $i_1...i_m$ must be at least $r$ entries long?
A correct algorithm with time linear in $m$ seems possible with dynamic programming. It would be even nicer to know the name of the problem and some academic reference to a correct solution. This is a minor methodological step in an analysis I'm doing for an interpersonal communication research paper, so ideally I'd like to find a paper to cite. This smells very similar to the dynamic programming homework problems I did in undergrad, so I'd be surprised if there isn't work on it.
In practice, $m \approx 12000$, $n=3$, and $20 \leq r \leq 200$.


texts: Show that the diameter of a MST is sometimes larger by a factor $\Omega(n)$ than the diameter of the graph $G$

texts:
As my title points out, I don't understand how do you show that, in general, the diameter of a MST (minimal spanning tree) can be bigger than the diameter of G, by the factor $\Omega(n)$. $(n:= |V|, G =(V,E)) $.

And I don't understand, how big is $\Omega(n)$ and why $\Omega$?

I made a example where the distance of two nodes in $G$ is smaller than the distance of the two nodes in the MST.

Is it correct to write,

$D_{MST} = D_{G} \cdot \Omega(n)$  ?
$\Omega(n) = D_{MST}/D_{G}$ ?

$D_{G} =$ diameter of graph $G$ and $D_{MST} =$ diameter of MST.


texts: Matrix chain multiplication recurrence and its solution

texts:
We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.
In the classical matrix chain multiplication problem, we wish to minimize the total number of scalar multiplications. In this problem, we consider the all intermediate matrices arising in the computation (including the final result but excluding the original matrices), and the cost of a specific order is the maximal number of entries of such an intermediate matrix. As usual, we want to minimize the cost.
As an example, if $n = 2$ the answer is simply $d_0d_2$, and if $n = 3$, then there are two orders:

$(A_1A_2)A_3$, in which the intermediate matrices are $A_1A_2,A_1A_2A_3$. The cost is therefore $\max(d_0d_2,d_0d_3)$.
$A_1(A_2A_3)$, in which the intermediate matrices are $A_2A_3,A_1A_2A_3$. The cost is therefore $\max(d_1d_3,d_0d_3)$.

Denote by $C_{ij}$ the optimal cost of multiplying $A_i,\ldots,A_j$. We can write the following recurrence for $C_{ij}$:
$$C_{ij}=\min_{i \leq k <j} \max \{C_{i,k},C_{k+1,j},d_{i-1}d_j\},$$
with base case $C_{ii} = 0$.

How do we get this recurrence?


texts: I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?


texts: Proving that a specific Fibonacci heap can't exist

texts:
I was asked to describe how I would build a Fibonacci heap that consists of 1 tree with 7 vertices, 2 of them are leaves, and 2 of them are fathers that have a leaf as their son.

From what I see, this is a heap with 1 tree from degree 2 ($F2$), that has 2 sub-trees from degree 1 ($2 * F1$) and 2 sub-trees from degree 0 ($2 * F0$).

Now, this state cannot be achieved right after insertion, since insertion is lazy, meaning the last inserted node will be it's own tree.

This must mean that this state is due to removing a key, but if so, how can 2 trees have the same degree? which leads to think this cannot be done. Am I right?


texts: Where can I find information on Data Structures used in common software?

texts:
As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this information is not so readily available.

Can someone point me to the right resources that I may share with the students as a starting point for their research?

EDIT

Judging from the received replies, the original question is not sufficiently clear so I am adding more details.

I am looking for resources of the type that state, for example, that service-x uses data-structure-a in order to perform functionality-y because of property-b. This is the ideal case. Other resources that provide similar information are also welcome.


texts: Red black tree partition to $\sqrt{n}$ trees

texts:
This is a question I have stumbled upon in an old Algorithms test I found online:

  A) Plan an algorithm that does the following:
  Input: Red-Black tree
  Output: $\sqrt{n}$ seperate trees, so that every tree has $\sqrt{n}$ nodes.
  What is the complexity of the Algorithm you planned? must show analysis.

  B) Assume that you have started from an empty Red Black tree, and that the input is a
  set of nodes and not a Red Black tree.
  Show how can you make a more efficient algorithm of partitioning the nodes to $\sqrt{n}$
  Red Black trees so that every tree has $\sqrt{n}$ nodes.
  What is the complexity of the new Algorithm you planned and how does it affect existing Red Black tree functions? must show analysis.

Now I have answered A and I am pretty sure that's the best answer there is, but I need your help in telling me if I can do better. This is without analysis:

  Algorithm:
  1. Scan the Red Black tree using In-Order traversal to build a sorted array out of it. < > O(n).
  2. Divide the array to $\sqrt{n}$ sub-arrays and build a Red Black tree out of every sub > array - O(n) total.

Now what I don't really understand is how do I solve B.
I'm not exactly sure if the input in B is a Red Black tree or just a set of nodes, so both will be acceptable if you want to share your answer to B with me.
I have asked a student and he told me that the complexity that I should get in B is $O(\sqrt{n}*log(n))$.

I need help reaching that, or maybe something better (hints and stuff).


texts: Finding subset such that one sum is more than target and another sum is less

texts:
Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in S}b_i\leq B$?

Is this problem NP-hard? I'm thinking there is possibly a reduction from the subset-sum problem, but here there are two lists, and the conditions are inequalities rather than equalities, so I'm not quite sure how to start.

Another remark is that if the condition is just $\sum_{i\in S}a_i\geq A$, then it would be easy because we can check the sum of the whole subset.