texts: Show that term cons works by showing all beta reductions

texts:
I'm new to functional programming.
So the terms cons appends an element to the front of the list. Where cons ≜ λx:λl:λc:λn: c x (l c n).
How should I go about proving that cons works correctly using beta reduction for a sample function. For example reducing cons 3[2,1] to [3,2,1]? Is there a formula like for the artihmetic operations in lambda? I'm a bit confused on how to approach this comapred to a arithmetic operation (i.e. addtion or multiplication).
Thanks.


texts: Operating system maintains copy of page table for each process

texts:
I am quoting a paragraph in Operating System Concepts by Silberschatz, in paging chapter,

  In addition, the operating system must be aware that user processes operate
  in user space, and all logical addresses must be mapped to produce physical
  addresses. If a user makes a system call (to do I/O, for example) and provides an address as a parameter (a buffer, for instance), that address must be mapped to produce the correct physical address. The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical addresses to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU.

I don't understand why OS would copy the page table, isn't it the one creating and maintaining it?
And as given further, why does it keep copy of instruction counter and register contents?


texts:
Theorem: (Stockmeyer, 1974)  Any circuit that takes as input a formula
  (in the language of WS1S) with up to 616 symbols and produces as
  output a correct answer saying whether the formula is valid or not,
  requires at least $10^{123}$ gates.

Suppose we have generalized theorem: Any circuit that takes as input a formula
with up to $n$ symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^n$ gates. Is this true that this theorem equivalent to statement that P is not equal to coNP?


texts: Is there a way to determine whether a list of integers can be a prefix function?

texts:
Say you had
(0,0,0,1,2,3,4,5,6,7,8,9,10)
or
(0,1,0,1,0,1,2,3,0,1,0,0,1)
Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a way to find whether a substring exists in a string using KMP, but is there a way to do it the other way around, starting at the apparent prefix function and ascertaining that it is indeed a possible prefix function, without knowing the string/substring itself at the start?


texts: What makes a language "optimized" for a specific task?

texts:
Often there are programming languages that are specialized for specific tasks. Some programming languages are excellent at array arithmetic (such as matrices and the use of multidimensional arrays), yet some are much better at higher-level mathematics that is hard to reproduce in other languages (yet still possible all the same).

What about a language makes it better for a specific task or end-goal than other languages, given that most simply compile down to assembly anyways?

I am talking about Turing complete languages, ones that are Turing equivalent.


texts: Determining the number of iterations needed to find the number of bits in an integer

texts:
I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer.
4 = 100  =  3 bits
3 = 011  =  2 bits
8 = 1000 =  4 bits

I skimmed through this article and it says: A positive integer n has b bits when 2^b-1 ≤ n ≤ 2^b – 1
But when you do the math for an integer 4, you get 2.32 ~= 2. What am I doing wrong?


texts: Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

texts:
Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:

$h_1(n)$ = number of misplaced tiles
$h_2(n)$ = total Manhatten distance

Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to know why the number of nodes generated for $h_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

Source: Informed Search


texts: Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex

texts:
Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to find the connected subgraph (not sure about this terminology) with maximum number of edges, among all the connected subgraph of $C$ that satisfy the following:

includes vertex $v_1$
has exactly $m$ number of vertices (including $v_1$)

By connected subgraph of $C$, I mean a subgraph of $C$, such that each pair of vertices in it are connected by a path.


texts: How do you go from $\log P = \log N$ to the next step?

texts:
Let
  \begin{align*}
    &P=2^{\log_2 N}\\
    &\Rightarrow \log_2 P = \log_2 N\\
    &\Rightarrow P=N\\
    &\Rightarrow 2^{\log_2 N}=N\,.
  \end{align*}

I don't understand how can you just drop the logs and go straight to $P = N$. Can someone please explain this to me? Am I missing a log rule?


texts: Complexity for find pairs with sum - BST

texts:
I have written an algorithm for find all the pairs in a BST which have a given sum.

def getPairsForSum(rootNode : Node, expectedSum : Int) : List[(Node,Node)] = {
    def check(node1 : Node, node2 : Node) : List[(Node,Node)] = {
      if (node1 == null || node2 == null) Nil
      else {
        val actualSum = node1.value + node2.value
        if (actualSum == expectedSum) {
          List((node1, node2))
        } else if (actualSum > expectedSum) {
          check(max(node1, node2).leftNode, min(node1, node2)):::
            check(min(node1, node2).leftNode, max(node1, node2))
        } else {
          check(max(node1, node2).rightNode, min(node1, node2)):::
            check(min(node1, node2).rightNode, max(node1, node2))
        }
      }
    }
    if(rootNode.value > expectedSum/2) check(rootNode, rootNode.leftNode)
    else check(rootNode,rootNode.rightNode)
  }

It works well (though gives nodes like (n1,n2) and (n2,n1) in the result). I would like to know the complexity of this algorithm. I am not sure how do I approach calculating time complexity. Is this algorithm better than n square??

EDIT
Assuming that this bst does not allow duplicates.


texts: What class of problems does this problem belong to

texts:
I recently took a test and I had a particularly difficult time with one problem.  I would like to know more about this problem: what general class of problems does this problem belong to, what are some good resources to learn more about this class of problems, how should I have recognized the problem for what it was?

So here is the problem, distilled down to its essential components.

You have a task you are trying to accomplish.  There are n different ways to to accomplish that task but each approach has a cost and probability of success associated with it.  The problem is to figure out how to order your attempts at the task so that the average cost is minimized.

There is a small twist, if all but your last attempt has failed then you are guaranteed success on your last attempt regardless of the probability of success associated with it.

So here is a concrete example.  The following list of tuples represents three ways to complete a task.  The first value is the cost and the second value is the probability of success:

[(10,0.5),(8,0.25),(5,0.2)]

One possible order would be [0,1,2] (each value is the index of an attempt in the above list).

That has an average cost of:

0.5*10 + (1-0.5)*0.25*(10+8) + (1-0.5)(1-0.25)(10+8+5) = 8.975

But the optimal order is [0,2,1]:

0.5*10 + (1-0.5)*0.2*(10+5) + (1-0.5)(1-0.2)(10+8+5) = 8.8

The obvious way to solve this problem is to simply try every possible order but that has a runtime of O(n!).  What you are supposed to know is that by dividing the cost by the probability and sorting the list using that value as the key you will get the optimal order.

I did figure that out eventually but it was not obvious to me at all, I went down a long and winding route and hit many dead ends before I arrived at that solution.  So what was the trick here to quickly come to this conclusion?


texts: "State of the art" algorithms deciding entailment of propositional formulas?

texts:
I fail to find much about how to efficiently calculate whether a propositional formula entails another.
Considering the following two points...

We can check, for each truth assignment which makes the first formula true, whether it also makes the second true. If all of them do, the first entails the second. It works for disjunctive normal forms, conjunctive normal forms, ... anything really. But this can be prohibitively expensive for large numbers of propositions.
If we translate both formulas to disjunctive normal form we can more efficiently check for entailment, but we need to do the transformation to DNF first.

... what are the best algorithms to check entailment?
I was under the impression that this must be a problem that's long been solved, but where are the papers that deal with entailment of arbitrary propositional formulas? How do I calculate a yes/no answer without using DNFs?


texts: Is the SK2 calculus a complete basis, where K2 is the flipped K combinator?

texts:
Specifically, if I defined a new $K_2$ as
$$K_2 = \lambda x. (\lambda y. y)$$
instead of
$$K = \lambda x. (\lambda  y. x)$$
would the $\{S, K_2,I\}$-calculus be a compete basis?

My guess is "no," just because I can't seem to be able to construct the regular K combinator from the $S$, $I$, and $K_2$ combinators, but I don't have an algorithm to follow, nor do I have good intuition about making things out of these combinators.

It seems like you can define
$$K_2 = K I$$
with the regular $\{S, K, (I)\}$-calculus, but I couldn't really work backwards from that to get a derivation of $K$ in terms of $K_2$ and the rest.

My attempt at a proof that it was not functionally complete essentially attempted to exhaustively construct every function attainable from these combinators in order to show that you reach a dead end (a function you've seen before) no matter what combinators you use. I realize that this isn't necessarily going to be true of functionally incomplete sets of combinators (e.g. the $K$ combinator on its own will never dead end when applied to itself), but this was my best thought. I was always able to use the $S$ combinator to sneak out of what I thought was finally a dead end, so I'm no longer so sure of the feasibility of this approach.

I asked this question on StackOverflow but was encouraged to post it here. I received a few comments on that post, but I'm not sure I understood them right.

Bonus: if it isn't a complete basis, is the resulting language nonetheless Turing-complete?


texts: Bottom-up algorithm to build subset of maximum weight

texts:
I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R of size n: for each j in R[i] we have that  the subset can not contain both P[i] and P[j].
How do I build a DP bottom-up solution for this problem?


texts: A knapsack problem with variable knapsack size

texts:
I've come across this problem and I can't find a decent DP solution for it.

Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), maximize the total 'value' such that the money spent does not exceed the initial money. With the exception that if the total money spent exceeded 2000 dollars, the buyer gets a 200 dollar refund card and can spend precisely that much more. For instance, with an initial money of 1900 dollars, you can spend up to 2100 dollars worth of items.

Any help would be appreciated.

I know that this is just the normal 0-1 knapsack problem, but I'm struggling with coding the part where I need to handle the refund card.

This is as far as I got, but it's not giving me the proper answer:

(I've basically filled the normal knapsack memo table in a bottom-up fashion in such manner that for each element at memo[i][w], I've calculated the most amount of "value" gained using precisely "w" money. Only that I added a one-time flag that if the money I've used exceeded 2000, add 200 dollars to my "reminder" money so "w" iterates up to "original money + 200".)

include <bits/stdc++.h>
using namespace std;

int memo[100][10200], favor[100], price[100];
int totalMoney, itemNum;
int solve(int rem, int idx)
{
    int w;
    bool flag_once = false;
    for (int i = 0; i <= idx; i++)
    {
        for (w = 0; w <= rem; w++)
        {
            if (totalMoney - (w - price[i - 1]) > 2000 && !flag_once)
            {
                rem += 200;
                flag_once = true;
            }
            if (i == 0 || w == 0)
            {
                memo[i][w] = 0;
            }
            else if (price[i - 1] <= w)
            {
                memo[i][w] = max(favor[i - 1] + memo[i - 1][w - price[i - 1]], memo[i - 1][w]);
            }
            else
            {
                memo[i][w] = memo[i - 1][w];
            }
        }
    }
    return memo[idx][rem];
}

int main()
{
    cin >> totalMoney >> itemNum;
    for (int i = 0; i < itemNum; i++)
    {
        cin >> price[i] >> favor[i];
    }
    cout << solve(totalMoney, itemNum) << endl;
}


texts: What is the time complexity of the Edmonds-Karp algorithm for finding a maximum cardinality matching in bipartite graphs?

texts: What is the time complexity of the Edmonds-Karp algorithm (not the Hopcroft-Karp algorithm) for finding a maximum cardinality matching in bipartite graphs? Is it still $O(|V||E|^2)$, or it has a better time complexity in this special case?


texts:
I'm going through a video of EDX course which talks about Big O notation. At the end of the video they have some questions but the $O(n^2)$ answer is confusing me. It feels like a mistake, but I just want to make sure.
The question is :

Imagine that we have a data set of 10 items. We run an algorithm on that data set, and it performs 10 operations.
Now imagine that we doubled the size of the data set to 20 items. Approximately how many operations might now be required if the algorithm is of...

Linear order? 20

Constant Order? 10

Quadratic Order? 40

I don't understand why the answer if 40 if it's quadratic.
At first I thought it would be 400, because n2 is 400. But the drop-down answer menu doesn't have 400. The highest it has is 100.
So I thought it might be 100, because if 10 items take 100 operations, then increasing by 10, would increase by 100. However 100 seems to be wrong as well.
So why is the answer 40?
The course in question is here:
https://www.edx.org/course/introduction-computing-using-python-gtx-cs1301x
Chapter 5.2


texts: When are binary trees better than hashtables in real world applications?

texts:
I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree.
I do understand the algorithms, and how to implement a binary search tree and such. I do so how smart it is that we can do lookups in O(log n) time.

I am however having a hard time finding an example of when I would use a binary tree, where a hash tables would not do the same/better job.
I have been doing some searching around and found that it is used for 3D graphis, something about what items are to be displayed, i do however have a hard time relating to this.

Can any one give me an example where it would be better to user a binary tree over a hash table?


texts: Free and bound variables in a lambda-calculus term

texts:
For this term:
      $\lambda x.(f (g x))$, what are the free and bound variables?

I'm confused as to how to expand this so it will be easier to see.
If I expand this will it be $\lambda x. \lambda f. \lambda g$?


texts: How does the kleene star and union work in a context free grammar?

texts:
Im in a functional languages computer science class and I have a question on the use of the kleene star and the Union in a context free grammar.

for the kleene star I have an idea of how I might do it.
    for example

 {0^n 1^n | n in the set of natural numbers}

I think it would look something like this.

 S-> 0S1 | A
 A-> S | lambda

where lambda would mark closing or ending the string. Is this right?

as for how the union would I dont understand at all how it would work. wer were given an example that looks like this

 {0^n1^n | n in the set of natural nubmer} U
 {0^n1^2n | n in the set of natural numbers}

I know how I would make a context free grammar for either of these alone but I dont know how the union comes into play with this.


texts: MST with half the edges the maximum weight

texts:
I have been cracking my head over the following question -

  You are given an undirected connected graph with an even number of
  edges. Half of the edges have weight less than C (possibly with
  repetitions), and the other half of edges all have weight C. Is it
  true that every MST of the graph includes the same number of edges of
  weight C?

  If Yes, describe an efficient algorithm for finding the number of
  edges of weight C in every MST of the graph. The output is between 0
  and |E| / 2, no need to return the MST.

  If No, show a counterexample.

My work so far -

I've managed to prove to myself that the number of C weighing edges included in a spanning tree (not minimum) can be anywhere between 0 and |E| / 2 (using a cycle with C edges crossing it).

Obviously, I couldn't find a counterexample yet. It feels like what's preventing me from creating two different MST's with a different number of C edges is that for creating a graph that has more than one MST you need to have cycles, and if a C edge is contained in the cycle it won't be chosen (Kruskal). That is the direction I'm leaning towards for a proof, proving a more general claim obviously.

Assuming the above is in fact true, I need to show an efficient algorithm for finding the number of C edges in every MST. The question states there is no need to return an MST, so it seems like there should be a better algorithm than finding the MST and counting the number of C edges in it, meaning this algorithm should be more efficient than sorting. From what I showed above, it could be anywhere between 0 and |E| / 2 so I'm kinda lost here too.


texts:
What are the applications of homotopy type theory to everyday programming?
I know of only two applications, neither of which I understand:

"Homotopical Patch Theory"
"HoTTSQL: Proving Query Rewrites with Univalent SQL Semantics"

Is there a capsule summary of how HoTT is relevant to these problems?
Is there a general kind of programming problem for which HoTT is suited? Based on the applications so far, is it likely that future applications will all have to do with program efficiency? Or might there be applications to distributed systems, for example?
Higher inductive types strike me as the most obviously "new" thing from a programmer's point of view. Is there a capsule summary of why programmers might use higher inductive types? Do these applications only have to do with program correctness, or do they also give us the ability to solve problems differently?
I know it's early days and that we probably don't know what the applications may be, but it's also likely that more is known now than several years ago when the articles above were written.
Update
Found one more application! When implementing APL/J's notion of "rank" (generalized operations over multidimensional arrays), it can help to have a more flexible notion of equality. See Section 3.1 of "Multi-dimensional Arrays with Levels" by Artjoms Šinkarovs

Thanks James Wood for pointing me toward this paper


texts: stable marriage/residency problem with multiple matches

texts:
Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors could choose to go to more than one medical school at the same time.

Is there a variation on the deferred acceptance algorithm to handle this generalization? Can I just have each "doctor" propose to n hospitals at each step, where n is the number of hospitals he is trying to attend at once? Also, what if hospitals do not have preferences?


texts: Finding Minimum Weight Subgraph with k Vertices

texts: Assume a complete graph G={V,E} that has n vertices and $C_{n}^{2}$ edges, and the weights of E are all positive. I am trying to find a complete subgraph containing k vertices, and it has the maximum sum of edge weights among all the complete subgraph with k vertices. My question is, other than the brutal force method that needs to traverse all posible subgraph with k vertices ($C_{n}^{k}$), is there an algorithm that is faster than the brutal force, or has polynomial complexity?


texts: How to construct a NFA that the third symbol and the third from last symbol are same?

texts:
Suppose the alphabet is {a,b}. I have tried coming up with NFA1: third symbol is a, and NFA2: third from last symbol is a. Then NFA3 and NFA4 similar but with symbol of b. Then I use intersection of NFA1, NFA2, and intersection of NFA3, NFA4, and add $\epsilon$ transition. But things seem to go wrong here. When doing the intersection of, say, NFA1, and NFA2, obviously the new NFA would not accept strings such as aba, aaa.

I have been trying different methods but still stuck here for hours. Any help of hint would be much appreciated!


texts:
Amdahl's Law generally divides a task into "things that can be parallelized" and "things that can't".  Now, I know what "things that can be parallelized", and it's not too hard to imagine things whose parallelizations aren't obvious, but it's not clear to me what makes a task fundamentally non-parallelizable, whether such a thing is known to exist, or whether the question is even well-formed.  The best example I can think of is, say, hashing an input 100 times - but I'm not sure it's been proven there is no parallelization, or just that we haven't found one.
One conceivable outcome, if non-parallelization can't be proven - it's vaguely plausible that there could be some way of processing arbitrary algorithms that, at some cost of memory and/or efficiency, allows parallelization across an arbitrary number of cores.
Has it been proven there exist algorithms/tasks cannot be parallelized?  (Or the opposite?)  Have any specific algorithms been proven to be fundamentally serial?  Is there a commonly used set of definitions/rules/assumptions for talking about the issue?


texts: Heap sort best case time - $\mathcal O(n)$?

texts:
It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ?
The argument here is, If my input has all the same keys, then every time I delete the root, I do not need to heapify, I just need to swap with the rightmost leaf.

Why is the above argument not valid ?


texts: prove that NDFA = { | M1 and M2 are DFAs such that there is at least one string x that is accepted by neither M1 nor M2} is decidable?

texts: How can I prove that $NDFA = \{ \langle M_1,M_2 \rangle | M_1$ and $M_2$ are $DFA$s such that there is at least one string $x$ that is accepted by neither $M_1$ nor $M_2\}$ is decidable using the fact that $ANFA = \{\langle N \rangle | N$ is an $NFA$ with some input alphabet $\Sigma$, and $L(N) = \Sigma^*\}$?


texts: Using Amdahl's law how do you determine execution time after an improvement?

texts:
Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches).  If old FP unit took 20% of program's execution time and data cache accesses took 10% of program's execution time, what is the overall speed up?

I solved this problem using amdahl's law:

FeFP = floating point enhanced fraction = .2

FeDC = data cache access enhanced fraction = .1

SeFP = floating point enhanced speedup = 2

SeDC = data cache access enhanced speedup = 2/3

Speedup overall = 1 / (   (1 - FeFP - FeDC)   +   FeFP/SeFP   +    FeDC * SeDC    )

= 1 /  (   (   1 - .2 - .1  ) + .2/2 + (.1) * (2/3)   )
 = 1.154.

I hope I did this correctly, but I'm confused about the next part asking what percentage of execution time is spent on floating point operations after implementing the new FP unit?

I know that T[improved ] = T[affected] / improvement factor   + T[unaffected]

But I'm unclear how to use it in the context of this problem.  Would appreciate all / any advice.


texts: Proving time-complexity analysis for merge-sort-like algorihtm

texts:
I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same operation as merge-sort.

The thing is, I can't understand the exact way to calculate a closed form solution to my recursive formula, which I think is: $$T(n) = T(\frac{1}{4}n) + T(\frac{3}{4}n) + O(n)$$

I've gone through the proof of the standard merge-sort implementation recursion closed-form formula (as seen in a khan academy article) and have noticed that as a way to develop intuition on how the recursive formula acts, a binary tree has been drawn. So I decided to try it for myself and the recursion formula I'm trying to prove. What I got was something like the following:

Where $(\frac{3}{4})^Hn$ is the height of the tree.

Because the tree is not complete, I'm confused on how I should calculate that $H$ value (the height of the tree), so I could use it in my worst-case merge-sort-like algorithm analysis. The confusion, in my estimation, lies in my low confidence with $log$ operations. Just can't seem to wrap my head around them. How do I start writing an induction proof for a closed form formula, and how do I even come up with one?

Help is as always, greatly appreciated. Moreover, if there is a source of further learning and something worthwhile reading that might help in this subject, please write that down for me so I could explore by myself. Thanks!


texts:
I'm making a compiler/interpreter for a language similar to C. I already have a parse tree. I was able to evaluate expression statements by converting my code to another language and then using an evaluation engine. How do I properly evaluate functions using a parse tree? Let's say my function x looks like the following:

x(int a, int b){
    x = <some expression statement using a and b>
    <some function call using x>
}

How can i be able to save the statements so that whenever the function is called, the contained statements will be evaluated?


texts: To what extent is my interpretation of computable numbers correct?

texts:
Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to calculate all of the digits of $\pi$ and begins dismembering the person. This is possible because $\pi$ is a computable number.

In contrast, if the person had asked the robot to calculate Chaitin's constant (assuming the robot didn't say something like "which Chaitin's constant?" or "insufficient parameters") or some other non-computable number, would the people have been able to escape the robot's dismembering?

As far as I understand (1)(2), the robot could make an algorithm to calculate the first $n$ digits for any $n$, but to attempt to compute "all" of Chaitin's constant would take an infinite amount of time, because each new digit would require a new program, or something like this.

Question: Is this interpretation at all correct or am I completely off the mark here? To what extent could one describe computable numbers as numbers which "prevent a robot in this specific situation from dismembering people"?

I.e., do all non-computable numbers have algorithmically random (decimal, binary, etc.) expansions?

Source.


texts: How can I make sense of amortized accounting method?

texts:
Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read).

In the example of the Stack with Multiple Pops (From CLRS, for reference: http://chuck.ferzle.com/Notes/Notes/AlgorithmAnalysis/Amortized.pdf), we arbitrarily "assigns" a credit of 2 two the Push operation, 0 for pop and 0 for multipop, and each push we arbitrarily "spend" 1 credit and the objected pushed onto the stack "stores" 1 credit.

This has to be the most insane thing I have ever seen in my life! Even if I get pass the "why 2 but not 100 credits" stage, how can I rationalize the fact that the object somehow stores a credit? How can we just arbitrarily assign these costs to these operations? Also how could you possibly gain anything insightful from this?

It is like imagining that typing on this computer will earn me $100 USD and shutting off the computer will make me spent 20 USD. Can someone please shed a light on how this technique works?


texts: Does increasing k in a k-way set-associative cache always lead to a better miss rate?

texts: As far as I know a 2-way set-associative cache works better than a one-way one considerably but going to 4 and 8-way caches leads to a marginal improvement. My question is: does increasing K (going more than 8) lead to better miss rate although marginal?


texts: Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$

texts:
Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ or it is less than or equal than the key of the right child.

To prove that if $T$ is BST then for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child I could say that from the definition of BST it follows that given a node $x$ and a node $y$ which belongs to the left sub-tree of $x$ then $key(y) \le key(x)$.

By the hypothesis if we choose any node $z$ of in the left sub-tree of $y$ then $key(z) \le key(y)$ so the relation holds true for all of the nodes of the tree.

I'm not sure how to approach the proof of the second direction: if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child then $T$ is a BST.


texts: What are useful/new areas to work on for recommendation systems?

texts: I am working on a project on recommendation systems, and would like to know about specific areas/research papers on which some new work can be performed, but not something too time/coding intensive. Its for a project due in 2 months.


texts: Does the memory get unallocated when program exits?

texts: I have been trying to manipulate pointers just for the sake of studying. I have had some problems with some programs I wrote where I had memory leak. Does this memory stay allocated even when the program returns? If yes how to deallocate it?If no why, isn't all saved in heap so only the one who has that heap pointer can deallocate? Or does the operating system pull some magic tricks?


texts: What properties of a discrete function make it a theoretically useful objective function?

texts:
A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) global optimum which could be theoretically found by an exhaustive search of the candidate space. I'm also using "theoretically useful" in a slightly misleading way because I really couldn't understand how to phrase this question otherwise. A "theoretically useful cost function" the way I'm defining it is:

A function to which some theoretical optimisation algorithm can be applied such that the algorithm has a non-negligible chance of finding the global optimum in less time than exhaustive search

A few simplified, 1-dimensional examples of where this thought process came from:

Here's a function which, while not being convex or differentiable (as it's discrete), is easily optimisable (in terms of finding the global maximum) with an algorithm such as Simulated Annealing.

Here is a function which clearly cannot be a useful cost function, as this would imply that the arbitrary search problem can be classically solved faster than exhaustive search.

Here is a function which I do not believe can be a useful cost function, as moving between points gives no meaningful information about the direction which must be moved in to find the global maximum.
The crux of my thinking so far is along the lines of "applying the cost function to points in the neighbourhood of a point must yield some information about the location of the global optimum". I attempted to formalise (in a perhaps convoluted manner) this as:

Consider the set $D$ representing the search space of the problem and thus the domain of the function and the undirected graph $G$, where each element of $D$ is assigned a node in $G$, and each node in $G$ has edges which connect it to its neighbours in $D$. We then remove elements from $D$ until the objective function has no non-global local optima over this domain and no plateaus exist (i.e. the value of the cost function at each point in the domain is different from the value of the cost function at each of its neighbours). Every time we remove an element $e$ from $D$, we remove the corresponding node from the graph $G$ and add edges which directly connect each neighbour of $e$ to each other, thus they become each others' new neighbours. The number of elements which remain in the domain after this process is applied is designated $N$. If $N$ is a non-negligible proportion of $\#(D)$ (i.e. significantly greater than the proportion of $\#(\{$possible global optima$\})$ to $\#(D)$) then the function is a useful objective function.

Whilst this works well for the function which definitely is useful and the definitely not useful boolean function, this process applied to the random function seems incorrect, as the number of elements that would lead to a function with no local optima IS a non-negligible proportion of the total domain.
Is my definition on the right track? Is this a well known question I just can't figure out how to find the answer to? Does there exist some optimisation algorithm that would theoretically be able to find the optimum of a completely random function faster than exhaustive search, or is my assertion that it wouldn't be able to correct?
In conclusion, what is different about the first function that makes it a good candidate for optimisation to any other functions which are not.


texts: Runtime analysis of a recursive algorithm with a tricky amount of work per recursive call

texts:
I want to analyze the runtime of this algorithm:

int fun (int arr[], int n) {
    int result = 1;
    int i, j;

    if (n == 1)
        return 1;

    else {
            result = fun(arr, 2n/3);
            for (i = 1; i <= sqrt(n); i=i*2);
                for (j=0; j<sqrt(n)/i; j++)
                    result += arr[j];

            return result;
    }
}

I can see that the runtime recurrence should be something like

$\qquad\displaystyle T(n) = T\left(\frac{2n}{3}\right) + \Theta(X)$

where $X$ is the time of the extra operations per recursion.

I can also see that the extra operations are:

$\qquad\begin{align*}
  \sum_{i=1}^{\log(\sqrt{n})} \sum_{j=0}^{\frac{\sqrt{n}}{i}}1
    &= \sum_{i=1}^{\log(\sqrt{n})}\frac{\sqrt{n}}{i} \\
    &= \sqrt{n} \cdot \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \\
    &= \sqrt{n}\cdot \log(\log(\sqrt{n}))
\end{align*}$

So all in all:

$\qquad\begin{align*}
  T(1) &= 1 \\
  T(n) &= T\left(\frac{2n}{3}\right) + \sqrt{n}\cdot \log(\log(\sqrt{n}))
\end{align*}$

But I could not continue from here to solve this recursion.


texts: Finding unique cubiods with given volume

texts:
I have an interval of intigers and I need to find all unique cuboids which have volume that falls within said interval.

I came up with a loop that goes over all uniqe combinations of 3 numbers (size of the cuboid) (1x1x1, 1x1x2, ...; also 2x1x1 is considered the same as 1x1x2) from 1 to the upper range of the interval. And then checks if the calculated volume falls within the interval. This solution works perfectly if the upper range isnt is too large. But if the interval ends in thousands the solution becomes very slow.

I am not really interested in code as I am in an algorithm on how to solve this differently. How would you go on about solving this?


texts: Representing Computations on Transcendental Numbers

texts:
Consider the set of transcendental numbers that are not compressible to a finite base-2 representation.  How can I compute multiples (more generally, any algebraic computation) of one of these numbers, while maintaining an error less than $\epsilon$?

I'm curious because I know that I can approximately store a transcendental number in a finite computer, however with each subsequent operation that I perform on the preceding result, starting with the original number, my result becomes less accurate against what it's meant to approximate.

That is, assuming I have stored an approximation to $\pi$, $\pi'$, when I multiply it by two I'm left with $2\pi'$ whose error from $2\pi$ is, presumably, twice as large as the original error between $\pi'$ and $\pi$. (And so on, multiplying by two, my error doubles each time.)

What are the usual methods of reducing this error when using transcendental numbers in algebraic computation?


texts: Number of MUX required for Cache Mapping

texts:
I have read that the number of multiplexers required is equal to the number of bits in the TAG field. Is it true? If yes then why?

I know that the size of each multiplexer has to be S to 1, where S is the number of sets in a k-way associative cache (For Direct Mapped, no. of sets = no. of lines). That's because we have to select one of the sets using the set offset (or index) bits.

I'm not being able to reason with the number of multiplexers required though.


texts: Encoding set of At-Most-One constraints as a MAX-SAT problem

texts:
Assume a set of variable $V$ = $\{v_1,...,v_m\}$.
Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$,
$$ AMO \, (v_1, v_4, \neg v_6, v_{10}) \\ ... \\  AMO \, (v_2, \neg v_3, v_7)$$
Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set.

I'm unable to represent it as MAX-SAT problem.
Tried so far (Attempt 1): Using hard constraint for each of At-Most-One constraint. This will not work as encoding of $AMO (v_i,...,v_w)$ will have multiple clauses for each $AMO$ and all of them have assigned same weight (top weight). A solution to this set may not be the maximal one.
Attempt (2): To fix the above problem, I tried relative clause weight; i.e., for each clause assign weight proportional to size of the clause. This will give preference of assigning satisfying shorter clause. But this do not work in extreme situations like if all clause have same length.
I have experience with SAT solvers but this is my first MAX-SAT problem attempt.


texts: Is it a bad idea to require a correctness proof as part of a computable real number?

texts:
At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to compute a certain number of digits) should be part of a computable real number.

I thought the answer to that question would be clearly no. However, a similar idea occurs in section "2.2 Numbers as programs" on page 5 of Exact Real Computer Arithmetic with Continued Fractions by Jean Vuillemin, 1987. That paper appears to be quite good and very reasonable otherwise, so now I wonder whether I might be wrong here. Here is the reasoning:

  Theorem 1 (Cantor) Let $\mathcal R$ denote the subset of $\mathcal L$-expressions which represent numbers, that is the computable reals expressed as programs in $\mathcal L$.

  The set $\mathcal R$ is denumerable.
  No algorithm can effectively enumerate all the elements of $\mathcal R$.

  As equivalent to (2), we see that no algorithm can decide, in finite time, if an arbitrary $\mathcal L$-expression $e$ denotes a number, i.e., $e \in \mathcal R$. Therefore, since we cannot expect the computer to do it for us, we must provide a correctness proof with every real number definition, i.e., program.

My problem is that a correctness proof only makes sense after an axiom system has been specified. And I believe that for any reasonable axiom system, the ("extensional") set of computable real numbers which can be proven correct in that axiom system will be a proper subset of the ("extensional") set of all computable real numbers.

On the other hand, I might be wrong. For example, the ("extensional") set of languages defined by the provably polynomial time algorithms is identical to the ("extensional") set of languages defined by all polynomial time algorithms.


texts: Selecting a polygon within an array of complex polygons

texts:
I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram.

Unlike a Voronoi diagram I cannot simply find the nearest centroid to select a polygon, this returns the correct polygon most of the time but sometimes the point lies within a neighboring polygon.

The developer tools in my chrome browser seem to be able to do it with the selection tool but I have no idea how it is doing it.


texts: How to prove that finding math proofs is $\text{NP}$-hard?

texts:
This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak.

Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a finite description. Argue at a high level that the following language is $\text{NP}$-complete. (You don't need to know anything about ZF.)
$$\text{THEOREMS} = \{ \langle \varphi, 1^n \rangle: \text{math statement } \varphi \text{ has a proof of size at most } n \text{ in the ZF system}. \}$$

It is easy to show that $\text{THEOREM} \in \text{NP}$. However, how to prove it is $\text{NP}$-hard?
In addition, why is it $1^n$ instead of just $n$ in $\langle \varphi , 1^n \rangle$? Does this encoding scheme matter with the $\text{NP}$-hardness proof?


texts: A basic question about approximation algorithms for the Traveling Salesman Problem

texts:
Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard.  The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be decided.  This standard proof is discussed in many places including accepted answers on cs.stackexchange here and here.

Briefly, the standard proof for $k=2$ works as follows.  Suppose a graph $G$ with $n$ vertices is given as input to the Hamilton Cycle problem.  We create a weighted complete graph $H$ with the same $n$ vertices as follows: The edges in $G$ are given weight 1, and the added edges are given a large weight, say $n+2$.  Notice that every Hamilton cycle in $H$ either has total weight $n$, or at least $(n-1) + (n+2) = 2n+1$.  This gap allows a 2-approximation algorithm for TSP to answer the decision problem.  More specifically, if $G$ has a Hamilton Cycle, then the 2-approximation algorithm must return the value $n$ since the other Hamilton cycles have total weight $>= 2n+1$.  On the other hand, if $G$ does not have a Hamilton cycle, then the 2-approximation algorithm will return a value larger than $n$.

I'm uncertain about something even more basic.  What would a 2-approximation algorithm return if we did not add the edges of weight $2n+1$?  In other words, suppose we take graph $G$ and create a weighted graph $G_1$ by assigning weight 1 to each edge in $G$, and we do not add any new edges.  In this case, the Hamilton cycles in $G_1$ (if any) all have total weight $n$, and they all correspond to Hamilton cycles in $G$.  There is no gap in the total weights of the Hamilton cycles.

What exactly would the 2-approximation algorithm return if $G$ has a Hamilton cycle?  And what if $G$ does not have a Hamilton cycle?


texts: If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure

texts:
Let $(E,D)$ be a cipher with message space $M = \{0,1\}^n$ and key space $K = \{0,1\}^n$.
Assume that there is an algorithm $A\colon \{0,1\}^n \to \{0,1\}^n$ of size $T$ that given an
encryption of a message can guess the entire message with probability $0.2$. Namely, for a message $m \in M$  it satisfies $$P[A(E(k,m)) = m] = 0.2$$
I want to prove that $(E,D)$ is not $(T + O(n), 0.1)$-secure.
A cipher $(E,D)$ is called $(T + O(n), 0.1)$-secure if for every two messages $m_1, m_2 \in M$ and every algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size at most $T + O(n)$, it follows that:
$$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | \le 0.1$$
My idea was to assume on the contrary that $(E,D)$ is $(T+O(n), 0.1)$-secure, and then find an algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size $T+O(n)$ that uses $A$ to break this encryption.
Namely I need to show that for any two messages $m_1, m_2 \in M$ it satisfies:
$$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | > 0.1$$
Basically I need to describe such $B$ and two messages $m_1, m_2$ that satisfy this inequality.
My idea was to pick two random messages $m_1, m_2 \in M$. Then, somehow use $A$ to get the probability $P[B(E(k,m_1)) = 1] = 0.2$, and use randomness somehow to get the probability $P[B(E(k,m_2)) = 1] = 0.2 \times 0.5 = 0.1$
However, I don't really know how to do that.
Help or some hint would be very appreciated!


texts: What is the State of The Art of Writer AIs (Deep Learning)?

texts:
Does anyone know if Deep Learning Bots can already, for example, train
  on many books of an author and output a similar but new book?

I've been wanting to get into ML for quite a while but was lacking a project to use as an incentive to keep learning, and this specific AI has caught my interest. It seems feasible from the little I know of ML so far (I'm a beginner who has taken the initial module of Deeplearining.ai course from Coursera), but so far from what I can scoop out of the internet it doesn't seem like AIs are quite there yet. They seem to be somewhat convincing, but sometimes a weird outlier appears in the text; strangely, music composition seems more convincing. Does anyone disagree?

Another relevant question: is this too difficult for a beginner? I've graduated from engineering 1 year ago, so I have some ease with programming, but I don't know how difficult Recurrent Neural Networks (RNN) and Natural Language Programming (NLP) can be.

  Also, on a sidenote, does a more experienced programmer have a
  suggestion of path I should take to learn the necessary skills to
  program such a bot, i.e., online courses and books?


texts:
I'm stuck on this question about context-free languages and was hoping for some clarification.

$\qquad L = \{a^i b^j c^k \mid  i=j, i=k\}$
is not context-free. Show that its complement is context-free.

I understand that the complement basically means everything not in $L$, that is $A^* \setminus L$. However, I have no  idea how to actually take a complement for a language like  this.


texts: Algorithm A vs Algorithm A*: What's the difference?

texts:
I can find quite a bit of literature on A* but very little on A.

What is the difference between the two search algorithms?


texts: Are probabilisitc algorithms deterministic?

texts:
I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?

Initially, I thought only algorithms outputting random numbers are called probabilistic. They are obviously non-deterministic.

However, what about the following algorithm: Take BubbelSort and randomly decide whether to start sorting from left to right or from right to left. If you modify the sorting order, the algorithm is deterministic, because small values will always be on the left and great values on the right side (or vice versa). As there is some randomness in the algorithm, do we call this algorithm probabilistic?

In short: Any algorithm using some randomness is called probabilistic. Is that correct? However, this term has nothing to do with determinism and non-determinism. Is that correct?


texts:
Is the number of final states in a DFA at least the number of final states in its minimal DFA?

Is the answer even yes? Any help would be appreciated.


texts: What's the big deal with the knapsack problem?

texts:
In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic programming.

And all the sudden, bam, there is this whole chapter on the knapsack problem. How is this problem different from weighted interval scheduling? Or longest common sub-sequence?

What's the importance of the knapsack problem?


texts: Can every Turing Machine be translated into a SAT formula?

texts:
For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \{0,1\}^*$, we can create a SAT Formula,  that is satisfiable if and only if $M$ accepts $x$. Could we adopt this construction so that for any Turing Machine $M$ and input $x \in \{0,1\}^*$ we can create a SAT Formula $\phi$ that is satisfiable if and only if $M$ accepts $x$ (even if this SAT Formula has more than polynomial length of $|M|$)? Or would that contradicts Rice's Theorem?

Edit: As dkaeae correctly pointed out, defining a SAT formula that is satisfiable iff a TM $M$ accepts an input $x$ is indeed possible. What I meant to ask though is, whether a reduction in the sense of a computable function exists (albeit not being limited to running in polynomial time, but indeed being somehow limited in the running time).


texts: Correct cost function of multi classification problem using neural network?

texts:
I am going through machine learning course on coursera. While going through the section on neural networks I came across the cost function for multi - classification problem using neural networks ( ignoring the regularization term ):
$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] \end{gather*}$$

where $m$ is the number of training data points $\{(x_1,y_1),...(x_m,y_m)\}$. Each data point is classified into one of the $K$ categories ie. $1\;\le{\;y_i}\;\le{K}$ ( so $y_k^{(i)}$ means if $\;y_k^{(i)} == k\;$ ). And $h_\Theta$ is the hypothesis function.

My doubt is why does the cost function has a summation over $K$. Why aren't there $K$ separate cost functions ( $ 1 \; \le{k} \le K$ ), and we have different $\Theta$ when we minimize each of the $K$ cost functions separately:

$$\begin{gather*} J(\Theta)_k = - \frac{1}{m} \sum_{i=1}^m  \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] \end{gather*}$$

In the second approach we are trying one-vs-all classification. How is it different from first approach. First approach is taking sum over all cost functions of second approach. So minimization problem being solved in both cases are different. But I am unable to pin point what the difference between the two approaches is ? Both seem intuitively correct to me. Am I doing some stupid mistake ?


texts: Making a regular grammar for this language

texts:
I'm trying to make a regular grammar for this language:

Where the alphabet is $ \Sigma $ = $\{a,b,c\}$

It seemed like it would go well with a right-linear grammar.  This may be disastrously wrong, but here's how I started:

$S \to aA$

$A \to aA | cB $

$B \to bC | C $

$C \to cD |$ $\lambda$

$D \to cC$

EDIT:
Corrected for errors. Added $D$ for regular grammar.


texts:
A symmetric matrix $A\in \Bbb{R}^{n\times n}$ is copositive if for every vector $x\in\Bbb{R}^n$ with non-negative entries, we have
$$x^TAx \ge 0.$$
What are known methods to check if a specific matrix $A$ is copositive that are efficient in practice? I'm looking for something which will return an answer for a single instance of a 48x48 matrix in at most a week. I also wish for the implementation to not give false positive due to floating-errors, so I guess I am looking for a quadratic programming method which keeps track of its numerical precision/error bounds.
I have skimmed through this article: A Variational Approach to Copositive Matrices. While it details various methods to check if a matrix is copositive, I am not too familiar with matrix algorithms and could not determine what the expected run times of these methods would be.


texts:
We know that P=NP implies NP=coNP. Does the reverse implication hold?
Does NP equal coNP imply that P equals NP?
If not why not?

I googled but didn't find the answer.


texts: Regular Language - Context Free Language

texts:
I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question

  Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet
  $\sum^*$, which of the following about the langauge
  $R=\overline{A}-B$  is  $TRUE?$

  a. $R$ is necessarily $CFL$ but $not$ necessarily $regular$

  b. $R$ is necessarily $regular$ but $infinite$

  c. $R$ is necessarily $non$ $regular$

  d. $None$

  e. $\phi$

Now I have approached this problem in 2 ways and I am getting 2 different results.

The first way in which I have approached is that, since $A'-B=A'\cap B'$, so it is $Reg$ $L$ $\cap$ $CSL=CSL$ , so answer is $NONE$

On the other hand I have think of it like this, since $A$ is $Regular$ it's complement is also $regular$, Now we know that

So $regular$ $language$ being a subset of $CFL$ must give us $\phi$ when we are doing $A'-B$, so this time I am getting $\phi$ as answer

My question is which of my approach is correct? Is the first one correct? If so, then why the second one is wrong?

Or is the second one correct? If so then why the first one is wrong?

I believe that the second method shown by me is wrong as say we have a regular language  $A=\phi$, so $\overline{A}=\sum^*$ and say $B=a^nb^n$

then $\overline{A}-B=a^xb^y$, where $x\neq y$, so it is a $CFL$ but not $\phi$.

So where did I went wrong in my second proof using $Chomsky$ $hierarchy?$

Downvoters(if any) please mention the reason of downvote in comment. Thank you.


texts: Maximal Minimum Spanning Tree by Removing $k$ Edges

texts:
The problem is as follows:

  Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove at most $k$ edges from $E$ such that the resulting graph $G' = (V, E' \subseteq E, w)$ has a maximal weight minimum spanning tree over all possible $G'$.

I initially thought a greedy algorithm would work with "just remove the $k$ smallest edges as long as the graph remains connected." However, this does not work, consider the following graph and $k = 1$:

The MST of $G$ has weight 9. If we remove the minimal edge $(B, C)$, the MST of the resulting graph has weight 12. However, if we remove the edge $(A, B)$, the MST of the resulting graph has weight 13. So this greedy strategy does not work.

Other strategies, we can first note that it only helps to remove edges that are in the MST of $G$ initially. So we can first determine $T = MST(G)$. The next (inefficient) thing we could do is consider each edge in $e \in T$ and do:

Remove $e$ from $T$, cutting $T$ into $T_1$ and $T_2$.
Determine the next smallest edge $e'$ spanning $T_1$ and $T_2$ in $G$.
Keep track of $e$ such that it maximizes $w(e') - w(e)$.

Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.

I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.


texts: Question about Complete partially Directed Acyclic Graph

texts:
I am reading CPDAG, can anyone please explain why G1 and G3 are not equivalence classes as in the picture below?
Thank you very much!
according to https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html .

"Theorem 1 [59]   Two DAGs are equivalent if and only if they have the
same skeleton and the same v-structures.
The skeleton of a DAG is the undirected graph that results from ignoring the directionality of every edge.
A v-structure in a DAG $H$ is an ordered triplet of nodes,
$(x,y,z)$, such that (1) $H$ contains the arcs  $x\rightarrow y$ and
$y \leftarrow z$, and (2) the nodes $x$ and $z$ are not adjacent in
$H$. A head-to-head pattern (shortened h-h) in a DAG $H$ is an ordered
triplet of nodes, $(x,y,z)$, such that $H$ contains the arcs
$x\rightarrow y$ and  $y \leftarrow z$. Note that in an h-h pattern
$(x,y,z)$ the nodes $x$ and $z$ can be adjacent."
The concept of equivalence of DAGs partitions the space of DAGs into a set of equivalence classes.


texts: (Slightly) faster simulation of quantum Fourier transform

texts:
Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits.  When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine the probability amplitudes, and then perform a Fast-Fourier Transform on the probability amplitudes in time $o(N 2^N)$.  Finally in $o(2^N)$ time I can generate a scan of the partial sums of the probabilities of all the result states.  Then I can choose a random number in the range $[0,1]$ and use it to do a binary search of the partial sums.

This results in a simulator that, each time is run outputs a single $N$ bit binary number with the probability distribution predicted by theory.

Can I do better?  Of course I can't do exponentially better in general, but perhaps I could reduce the time to simulate a single experiment to $o(2^N)$?

I can do significantly better under some circumstances.  For example, Gilbert, Guha, Indyk, Muthukrishnan, and Strauss, "Near-Optimal Sparse Fourier Representations via Sampling", ACM Symp Theory Comp, STOC-44:152-161, 2002, seems to indicate that if there are only $B$ frequencies (or if the $B$ frequencies make up "most" of the power of the signal) then there is a randomized algorithm that will recover all of them (and their amplitudes) in time, space and number of samples polynomial in $B$ and $N$.

I guess I'm hoping for something like that, but only to get one frequency, and to have some guarantee that the probability of getting a particular frequency will be proportional to the amplitude of its coefficient.


texts:
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$
My approach with recurrence tree:
$n \sim n\log(n)$
$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$
$\frac{n}{4} \sim 4 \frac{n}{4}\log(\frac{n}{4})$
Hence the summation must follow as:
$$T(n) = \sum_{i=0}^{\log(n)} n\log(\frac{n}{2^i})$$
$$= \sum_{i=0}^{\log(n)} n(\log(n) - i)$$
$$=(n\log(n) \sum_{i=0}^{\log(n)}i) - (\sum_{i=0}^{\log(n)} i)$$
I can not go further from here, any help is welcome.


texts: Considering a 2-tag system as defined by wikipedia, how do I identify the result  of the computation?


texts: Proving the singleton language {x} is regular for all x ∈ Σ*

texts: So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would also be appreciated! As of now I'm just aware of it as a property, but I don't have a good grasp on why it is regular.


texts: Finding a minimum equivalent graph of a digraph

texts:
It is said that this problem is NP-complete but I couldn't find the proof.
Is there any paper on this problem or not?


texts: Can I assume every clause of 3SAT has one positive literal?

texts: Can we assume that each clause in 3SAT contains at least one positive literal? That is, there is no clause with all negative literals (but it is fine that there is a clause with all positive literals).


texts: Transform values of hash functions like MD5 into numbers

texts:
I have read about the hash function MD5. I found an online calculator which counts the value of MD5 for different data. But the MD5 function returns as result strings like 735b90b4568125ed6c3f678819b6e058, so I can't apply any numerical operation to this value, e.g. mod.

How can I transform values like these into numbers?


texts:
I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens

word1 near(1) word2

where word1, word2 are some words and near(1) is distance operator.
The question is how this expression should be tokenized.
I see two ways

1. <WORD, word1> <WORD, near> <LPAREN> <NUMBER,1> <RPAREN> <WORD, word2>.
2. <WORD, word1> <NEAROP, 1> <WORD, word2>

But should I really try to tokenize NEAR(\d+) during tokenization, or should I go first way and handle NEAR operator at parser level, during building parse tree?


texts: Can a self-learning appliance be developed?

texts:
I have heard of machine learning systems that can learn from trials of data what effect it should have, but I was wondering is it possible to make a learning appliance that builds on past data? Instead of only receiving new entries, once the database is big enough to begin going over it and doing pseudo consideration, drawing conclusions about the data and adding yet more entries to its database purely from looking at its past results? I suppose such a thing would probably eat up memory quickly unless it had a threshold of entries it was allowed to create. (In theory it would take a long time to get it to a state where it can become sentient in that way, through many trial sets before it begins thinking on its own.)

An application of such a thing would go beyond just determining what the best way to optimize code is, or how to beat a player in a game, but a machine that can actually build its own personality.


texts: Prove complexity bound without reduction?

texts:
The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization in terms of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?


texts: What will be big O complexity for this loop?

texts:
I am not able to understand time complexity of this for loop.
While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?

public void function(n) {
                    for(int i = 1; i< n; i++) {
                        for(int j =     1; j <= n;  j += i) {
                                System.out.println("*")
                        }
                    }
                }


texts:
I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I don't know which one. An oracle however knows the true permutation. To find the true permutation, I'm allowed to query the oracle for pairwise comparison between 2 objects (is a before b in the true permutation?).

A naive strategy would be to do a binary search (ask the "right" pairwise comparison question that eliminates half the permutations at every stage), to find the true permutation in log n steps. My question is, can this always be done? Or can I find an adversarial set of permutations such that O(log n) queries aren't enough.

Edit:
Example: Say my objects are 1,2,3,4. The set of permutations is {1243, 2341, 1342, 3412}. I don't know the true permutation. I ask "Is 2 before 4 in the true permutation?". The oracle returns yes. So I know its among the first two permutations. I then ask "Is 1 before 3 in the true permutation?" to find the true permutation.


texts: How do I tell if a comparison network sorts?

texts: I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The intent is to have a comparison network and sort numeric values. If I test 2^n values in this case 2^8. This is a lot of work|non-efficient way to test it. I'm looking for a mathematical model/proof to verify this is a valid sorting network.


texts:
This is an interview question:

Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

Example:

input:

Array : 2, 3, 4, 5, J, K

output:

2, 4, 5, J

2, 4, 5, K

I have a naive solution:

check if two cards' sum is 21;

check if three cards' sum is 21;

check if four cards' sum is 21;

check if five cards' sum is 21;(Max number of cards in blackjack)

However, this is brute force solution.

Can anyone give me a hint to get a better solution? Thanks!


texts: Does integer matrix multiplication with its transpose (A^T)*A have more efficient parallel algorithm than the use of symmetricity?

texts:
Integer matrix multiplication with its transpose (A^T)A gives symmetric matrix, so, only one half of it should be computed. Besides, the formula for the resulting element rik=Sum[aijajk, j] reduces to the simple sum of the multiplication of the the corresponding elements from two columns rik=Sum[ajiajk, j]. As I understand, the last observation is not giving any efficiency, the formulas are just bit more nice, nothing else. So, there are n(n-1)/2 multiplications and nn(n-1)/2 sum operations. Parallelization can improve the speed by simple division of labour, but my thinking is that there is not any sophistication available to improve the speed of this algorithm beyond the naive algorithm. Or maybe there is still any better, more sophisticated algorithm?

I am aware of https://math.stackexchange.com/questions/158219/is-a-matrix-multiplied-with-its-transpose-something-special but that is not discussion about algorithms.

There is also https://en.wikipedia.org/wiki/Strassen_algorithm - so maybe the sophistication I am seeking amounts to the application of the Strassen algorithm for the one half of the resulting matrices only? I am using symmetricity in that case. But can I take advantage of the fact that A enters in both sides of the multiplication?


texts: Is there a method to generate the complement of a context-free grammar?

texts:
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find the grammar for both languages. $G(L_0) = S \to \epsilon | 0S0 | 1S1 | 0 | 1$ is easy to come up with, but $G(L_1)$ is much more complex.
In this case, we have the simple CFG $G_0$ and want to find the CFG $G_1$ that is its complement which can be much more complex. Is there a method to derive the complement of a CFG?


texts: How can finite sets be represented as a type?

texts:
Manually self-migrated from stack overflow.

A set of objects of a type T is often represented using its indicator function (set T = T -> bool).  However, for practical purposes this representation isn't necessarily very useful.  For instance, if T is the natural numbers, there's no way to print0 out all of the numbers in a given set, since it would require checking all of the natural numbers, which is an infinite task.1

However, say I'm only interested in finite sets, and I want to be able to print out all the members of a set.  (Obviously I also want to easily test membership, construct unions and intersections, etc.)  Is there a good way to do this using inductive types?

Edit:
To clarify, I need the set type to encapsulate all of the set invariants (no duplicates, unordered, etc) so that all members of that type automatically satisfy those properties.  The indicator function representation does this, but is impractical to use as a data structure for the above reasons.  Using sorted lists (set T = list T) is possible, but not all lists are valid (sorted without duplicates) representation of a set—I need the type system to enforce that all members of set T are actually sets.

0: Let's assume we're using some monad to encapsulate printing, etc.
1: In exchange, we do of course get the ability to represent infinite sets.


texts: Generalization of a Markov random field and a Bayesian network?

texts:
I am seeking a graphical model that is a generalization of both a Markov random field (MRF) and a Bayesian network (BN).

From the Markov random field wiki page:

  A Markov network or MRF is similar to a Bayesian network in its representation of dependencies; the differences being that Bayesian networks are directed and acyclic, whereas Markov networks are undirected and may be cyclic. Thus, a Markov network can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies); on the other hand, it can't represent certain dependencies that a Bayesian network can (such as induced dependencies).

From the above description, particularly the last sentence, it appears that neither MRFs nor BNs are more general than the other.

Questions:

Is there a graphical model that encompasses both MRFs and BNs? (I think I’ve answered this, see the update below)
What is the form of its factorization?

I believe such a graphical model will need to be directed so as to be able to model the (undirected) dependencies in a MRF (by included a directed edge in each direction). Mixed graphs also may be relevant.

Update:

I believe I've answered the first part of my question. It seems the natural generalization is that of a chain graph (also see: N. Wermuth and S. L. Lauritzen. "On substantive research hypotheses, conditional independence graphs and graphical chain models." J. R. Statist. Soc. B, 52:21–50, 1990.). The second question, on their factorization, still stands. That is, what is the definition of a Markov blanket for a chain graph (the Markov blanket for a Markov random field is the neighbor set whereas for a Bayesian network, it is the parent nodes, children nodes, and parents of the children nodes).


texts: Is there a polynomial time algorithm for this decision problem?

texts:
Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$?

False Result Example

$N$ = 8

$M$ = 16

1, 2, 4, 8, 16

There is no integer that is NOT a factor of $N$ that is $>$ $1$ but < $M$

True Result Example

$N$ = 2

$M$ = 26

1, 2, 13, 26

There is an integer $13$ which is NOT a factor of $N$ that is > 1 but < $M$

Question

I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?


texts: Proving property of a term using Induction

texts:
This is one of the example lemma that has been proved in TAPL
book which I'm unable to grasp.

The objective is to prove |Consts(t)| <= size(t) where t is a term.

Now, Consts is a function defined like this:

Consts(true) = {true}
Consts(false) = {false}
... and so on

Similarly

size(true) = 1
size(false) = 1
... and so on

Now the proof in the book starts with something like "By
induction on the depth of t" and then goes to prove the
lemma. But I think I'm missing something here. Induction can be
applied when we have to prove something over natural number. But
there is no natural number involved in the above lemma. How come
then the induction is applied ?


texts: 'if' and 'while' statements within a SIMD architecture and its memory architecture

texts:
I am doing some past exam papers and I found two interesting questions which I cannot answer due to them not being extensively covered in the lecture notes given to me by my lecturer.

The questions go like this:

  "Explain the mechanism a SIMD computer uses to support conditional statements like if and while."

SIMD is essentially a class of parallel computers in Flynn's taxonomy and it describes computers with multiple processing elements that perform the same operation on multiple data points simultaneously. SIMD is also referred to as vector processing which leads to believe that I should have all my computations made to handle vectors as input than anything else, or am I thinking too much in a 'sequential' manner?

and:

  "Would you regard SIMD as a shared or a distributed memory architecture? Explain your choice."

It is a shared memory architecture as it uses data and instruction pools from which it can do its processes. I am struggling with answering this question as I cannot come up with a proper way of expressing myself in order to answer it.


texts: Formula for sufficiently lengthy encryption key?

texts:
As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many meaningful decryptions just by random chance and you won't be able to determine which was the original message.

As you add length to the message though, these meaningful decryptions become rarer until there is once again a small enough number of them left to figure out which is the right one (if you know what you're looking for, that is).

Has anybody figured out a way to estimate the required key length for this obfuscation by quantity to happen for more popular encryption algorithms?


texts: What is the time complexity of MergeSort without its penultimate merge?

texts: As in, with the two final sublists which are sorted arrays, let's say just for this example (yes it is no longer fully MergeSort but I am interested in the time complexity only), that we finish with a constant time operation involving the two sublists. MergeSort in worst case is $O(n\log(n))$, and not having the final merge would definitely lead to greater efficiency than this, but by how much? Again, I understand that MergeSort has not completed it's full run, I am only interested with its time complexity for my specified run only.


texts: Is O(n log n) exponential speedup over O(n^2)?

texts: I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?


texts: Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?

texts:
What is the difference between the Magnitude and the Phase Spectrum of the Fourier
Transform?


texts: Hindley-Milner type inference for language with implicit type casting

texts:
I've only implemented the HM algorithm on a small academic language with a few primitive types and functions. In that case, the unification algorithm would return a type error if two different primitive types were given. For example, if statements unify their condition with primitive type bool, producing the following results:

if (true) ... // type safe
if ("5") // type error, cannot unify string and bool

I've now been tasked to implement a type inference algorithm on a language that allows type casting on primitive types. For example, one cast is int -> bool such that if(5) ... is now a valid expression.

The problem is, I can't figure out how to adapt the unify algorithm. Specifically, I'm stuck on dealing with the one directional nature of type casts, e.g. int -> bool is defined, but bool -> int is not. The unify algorithm has no notion of direction. Unifying type a and type b is the same as unifying type b and type a. So in the case of the if statement, if I say that unify int with bool is allowed, then unify bool and int must also be allowed, and suddenly the statement true + false is type safe.

I've searched for details of existing type systems that do this, but unfortunately I've only found resources that either show a basic HM inference algorithm similar to the first one I implemented, or are completely off topic.


texts: Solving T(n) = 3T(n/3)+n/2 using master method

texts:
I thought I understood the Master Method quite well till I saw this question

$T(n) = 3T(\frac{n}{3})+\frac{n}{2}$

My approach:
  $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$

$n^{\log_b{a}}$ = $n^{log_3{3}} = n$

This looked like a classic solution of master method using case 1.

But since case 1 implies $f(n) = n^{\log_3{3} - ε}$ and I cannot find any way that ε can be represented, I understand that case 1 is not the way.

However the solution says that this is solvable by case 2 of the master method and the solution is  $T(n) = \theta(n^{log_3{3}} \log^{ n}) $

Case 2 of the master method states that if $f(n) = n^{log_b{a}}  \log^{k}{ n}$ then $T(n) = \theta(n^{log_b{a}} \log^{k+1}{ n}) $

Can someone explain how this is solved using case 2 of the master method and why this fits under case 2?


texts: k-enclosing rectangle in two-colored point set

texts:
I was asked to write an algorithm for the following problem, and discuss complexity:

  There are p points of two colours, black and white, in an n*m grid.
  Any cell in the grid can contain 0 or more points, of any colour.
  We are looking for an axis aligned rectangle, having (0,0) as a corner, containing k black points, and maximizing the number of white points in it.

It was mentioned that this problem is famous and I can use any online resource.

So far, the closest I have found is this paper, which deals with finding exact colored k-enclosing rectangles, that don't necessarily have the origin as a vertex.

Maybe someone here will be able to point me to some resources that discuss this version of the problem?


texts: How much can matrix multiplication algorithm be parallelized?

texts:
You all may know that simple Matrix Multiplication algorithm:

for(i = 0; i < n; i++)
   for(j = 0; j < n; j++)
      for(k = 0; k < n; k++)
         C[i,j] += A[i,k] * B[k,j]
      end for
   end for
end for

When we want to parallelize it, we can, at first, parallelize the outer loop,
which is the most easiest thing to understand, since it is clear that it does not have data dependencies with other loops.

Most tutorial on the web stops here, like we can not parallelize anymore.

But it seems for me that even the second outer loop (the one in the middle):

for(j = 0; j < n; j++)

can be parallelized.

What about the inner loop?

Is thus possible to parallelize all three loops of a matrix multiplication algorithm or must we stop with parallelizing only the first two loops?


texts:
The problem is we have to count number of paths between a source and a destination in a graph. The brute force approach is using backtracking which is $O(n!)$.

Is there any better solution to this problem?

Note that we have to count paths so we can't visit the same node again in a path.

I think this problem is np-hard and is similar to finding hamiltonian path in a graph. So, I can use Held-Karp algorithm to solve it in $O(n^2*2^n)$ using dynamic programming. Am I right?


texts: What is induced matching, maximum induced matching and mim-width?

texts:
I understand the concept of induced subgraph, but could not understan what induced matching is. As appears in this paper, it is defined as

  A matching in a graph is an induced matching if it occurs as an
  induced subgraph of the graph.

However, in this paper, there is a slightly different definition:

  A matching in a graph is a set of edges, no two of which meet a common
  vertex. An induced matching M in a graph G is a matching where no two
  edges of M   are joined by an edge of G.

Thus, I am confused since there are no example figures.

Also, there is a term called mim-width, which is maximum induced matching width and few no none examples exist in the literature.

Could you please give some examples for me to clear things out?


texts: Writing a non-deterministic Turing machine

texts:
I got an exercise in my college in which ive been asked to write a Non deterministic Turing Machine that accepts words of this form:

Ive manage to find some sort of solution but in a Deterministic way

Can anyone help me please?


texts: Which flow algorithm on a graph is used when the capacity is a rational number?

texts:
Does ford fulkerson only use whole numbers? I tried to understand this but without success

Thank you


texts: Mental poker: proving dealt hand is fair

texts:
I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman.

Assuming I have a website, (TTP) how can I prove to the player that the hand dealt to him is fair? Most importantly how can I prove that I didn't bruteforce until an unfair hand is dealt to him to gain house edge, are there any C# implentations of such code?


texts: Why do we create universal turing machines?

texts: Why do we create Universal Turing Machine explicilty to simulate the run of a word (say, $w$) on a Turing Machine $M$, given the description on it? Can't we just run $w$ on $M$ itself? I don't see the point of it.


texts: Interpret bits as a signed integer in 2s complement

texts:
Imagine you load this data as a 4-byte word into a register R. What is the value in R on a big endian machine and what is it on a little endian machine if you interpret the bits as a signed integer encoded in 2s complement

On a big endian machine the register R would be something like this

not considering the last sentence, interpret the bits as a signed integer encoded in 2s complement, which I don't understand completely.

Should I convert all bits, 0s to 1s and 1s to 0s and then sum 1 to all the string or to sum 1 to each byte in the string?

Thanks.


texts: Implementation of QuickSort to handle duplicates

texts:
I have this past year question based on the following scenario:

When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.

Here is the implementation of Quicksort, written in Java. I will not include the code in the main page because it seems that this site requests for description of pseudocode rather than actual code, even if the code is very “simple”.

In particular, this quicksort implementation is similar to the typical one, but choses its pivot on the left of the array.

I have some basic understanding of the quicksort algorithm based on the actual code, but a lot of times I have to break down the code myself to understand it. Whenever I am given pseudocode hints to understand the algorithm[and to be honest I don’t know sometimes whether a hint is a very obvious one or a rather implicit one], I somehow cannot appreciate the “magic” behind the pseudocode.

My understanding of this implementation of quicksort is that the array has to be iterated to make 2 regions of low and high values, while we dynamically decide on where to put the pivot, call it position X, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it adhere to the principles behind the typical algorithm?

Do inform me if more information is required or the formatting of the question doesn't adhere to the standards here.


texts:
I just read about Cross-entropy cost function for my work.
and I see a notation that said "the minimization of cross entropy of some data is equal to maximization of their log likelihood."
How can I achieve this result?
How can I show that?


texts:
I'm confused in trying to solve the following problem:
Find the number of comparisons made by Horspool's string search algorithm in the following case:

String: 001001001001
Pattern: 111

Attempt 1
The shift table value for 0 as per the algorithm should be 3 i.e. length of the pattern, because 0 is not part of the pattern.

001001001001
111

001001001001
---111

... and so on. This leads to 2 comparisons in each of the 4 shifts i.e. 8 comparisons.

Attempt 2
Instead, the answer, and also my intuition, suggests 5 comparisons:

001001001001
111

001001001001
--111

001001001001
-----111

... and so on. 2 comparisons needed in the first run and only 1 in each of the following 3 shifts i.e. total of 5.

Intuitively, it makes sense NOT to slide along the pattern 3 spaces [attempt 1] in the first run of the algorithm because we are not taking into account that the first character of the pattern - 1- is the same as the last character of our previous string match block - 001.

I would like help in correcting my understanding of the algorithm.


texts:
In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the variable.
Can anyone explain to me what exactly this means?


texts: Unifiers modulo commutativity in terms of syntactic unifiers and $\approx_{C}$-class

texts:
I am studying Term Rewriting by reading Baader's book "Term Rewriting and All That". I am in the chapter of Equational Unification, in the section of Commutative Functions. I am trying to do the following exercise:

Let $s, t \in T(\Sigma, V)$. By exercise 10.10 we know that the $\approx_{C}$-classes of these terms are finite. Let $\{s_1, \ldots, s_m \}$ be the $\approx_{C}$-class of $s$, and let $\{t_1, \ldots, t_n \}$ the $\approx_{C}$-class of $t$. Show that:
$$ \mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \})  $$
and that $\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s_i =^{?} t_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \}$ is a complete set of C-unifiers of $s \approx_{C}^{?} t$.

It seems obvious, but how can I prove that:
$$\mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \}) ? \tag{1}$$
After I prove that, I know how to proceed: let $\delta$ be an arbitrary C-unifier of $s \approx_{C}^{?} t$. By the equation (1) above, this means that $\exists_{i, j}: \ s_i \delta = t_i \delta$. Take $\sigma$ the mgu of $s_i =^{?} t_j$ and we have that $\sigma$ is more general than $\delta$.
Therefore, $\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s_i =^{?} t_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \}$ is a complete set of C-unifiers of $s \approx_{C}^{?} t$.
How can I prove (1)? Any hint/suggestion is very much appreciated. Thanks in advance.


texts: Each cycle in the graph, the edge with the minimum weight belongs to MST

texts:
Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$  a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in each cycle in the graph, the edge with the minimum weight belongs to $T$.
I either need to prove it in a positive way or give a counterexample.


texts: Genetic Algorithm Minimum Population Size

texts: Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.


texts: Is there a usable implementation of PBFT?

texts:
In the original Practical Byzantine Fault Tolerance (PBFT) paper they mention they implemented a fault tolerant NFS service. To do that they made a library for PBFT. Does that exist anywhere?

As that paper is quite old now and was well received, I thought it should not be hard to find implementations. However so far I only found incomplete and abandoned experiments.

RAFT has a list of implementations on their website. I am looking for something like this in the byzantine case.


texts: If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

texts:
I am discussing with a friend the following question:

If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable?

I believe it is.
My point is that if the machine that recognizes B never halt in some string, so the bigger machine will never know what to answer.

The image makes my point.

But my friend says that the $A \ cap B$ is a subset of $A$, then it is decidable.


texts: Analogue of disjunction and existence properties for a Turing-complete programming language?

texts:
Quoting from Wikipedia:

In mathematical logic, the disjunction and existence properties are
the "hallmarks" of constructive theories such as Heyting arithmetic
and constructive set theories (Rathjen 2005).
The disjunction property is satisfied by a theory if, whenever a
sentence A ∨ B is a theorem, then either A is a theorem, or B is a
theorem.
The existence property or witness property is satisfied by a theory
if, whenever a sentence (∃x)A(x) is a theorem, where A(x) has no other
free variables, then there is some term t such that the theory proves
A(t).

In the realm of logic [to the best of my understanding], these properties are violated when a logic is "classical", which, through the Curry-Howard lens, corresponds to it having support for capturing undelimited continuations.
For Turing-complete programming languages, the presence or absence of first-class control and undelimited continuations is also a meaningful and important distinction. However, being inconsistent as logics, the disjunction and existence properties in their above form hold trivially: every 'sentence' is a 'theorem'.
So: Is there any formal property that can distinguish Turing-complete programming languages based on whether or not they have undelimited continuations, which is similar in spirit to the disjunction and existence properties for logics? (Let's assume the languages are statically typed and do possess sum types and/or existential types.)


texts: Dynamic algorithm: what's the difference between memorization and bottom-up algorithm?

texts:
Here are two ways to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

I can't see what's the difference between these two algorithms except the first one use a if statement and the second one use a for loop. They both store result in OPT[n] first.


texts: $O(n \log n)$ algorithm to find next interval that is also disjoint

texts: Say there are some intervals $\{1, \ldots ,n\}$ with starting times and ending times, and they're sorted in order of starting time from first to last in an array intervals$[]$. Now I want create an array next$[]$ such that next$[i]$ is the interval after interval $i$ whose starting time is as close to $i$'s ending time as possible. The notes I'm reading says it is possible to do this in $n \log n$, but I don't see how. The fastest algorithm I have come up with would iterate over intervals$[]$, and in each step "look ahead" until it finds a starting time after $i$'s ending time. The worst possible scenario would be when all the intervals are bunched together (none are disjoint), in which case you would have to iterate over all of $i + 1, i + 2, \ldots ,n$ at each step $i$. This would be $O(n^2)$ because the total number of checks would be $0 + 1 + \cdots + n-1$ since we make $n-1$ for first the first number, $n-2$ for the second, etc. Am I missing a way to cut it down to $O(n \log n)$?


texts: Turing NP complete but not Karp NP complete?

texts:
Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction?

Conversely is there some examples of candidate problems that have Turing reduction to SAT but no known Karp reduction?


texts: Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?

texts: I have been trying to understand the difference between normal polynomial evaluation and horner's method. usually it takes 3n-1 operations while horner's method reduces it to 2n operations. I tried a couple of explanations but they were too theoritical. I would be glad if somebody comes up with a decent and simple explanation.


texts: What is a program in self-replicating programs?

texts:
I'm trying to understand the workings of artificial life as exemplified by systems like Tierra or Avida. The idea behind these systems is that organisms are modeled as assembly-language programs that replicate themselves in the memory of a computer, possibly a virtual machine. But here there is already something I don't understand (I'm not a programmer by vocation or by nature).

My idea of a computer's memory is that it's basically just a list of instructions. By default control proceeds from a given instruction to the next one in the list, but the instruction itself can send control someplace else. My question is: which sublists of this list of instructions count as programs?

Presumably the memory can be partitioned (in the set-theoretic sense) into a bunch of programs (actually copies of programs, since distinct "organisms" are allowed to have the same "genome"), plus some empty space; how does one do this?


texts: How does this example violate Liskov substitution principle, which then causes violation of the open-closed principle?

texts:
From Agile Principles, Patterns, and Practices in C# by Robert Martin,

  Listing   10-1.   A   violation   of  LSP causing a    violation  of  OCP

struct    Point   {double x,  y;}
public    enum    ShapeType   {square,    circle};
public    class   Shape
{
      private ShapeType   type;
      public  Shape(ShapeType t){type =   t;}
      public  static  void    DrawShape(Shape s)
      {
              if(s.type   ==  ShapeType.square)
                      (s  as  Square).Draw();
              else    if(s.type   ==  ShapeType.circle)
                      (s  as  Circle).Draw();
      }
}
public    class   Circle  :   Shape
{
      private Point   center;
      private double  radius;
      public  Circle()    :   base(ShapeType.circle)  {}
      public  void    Draw()  {/* draws   the circle  */}
}
public    class   Square  :   Shape
{
      private Point   topLeft;
      private double  side;
      public  Square()    :   base(ShapeType.square)  {}
      public  void    Draw()  {/* draws   the square  */}
}

  DrawShape() violates    OCP.    It
  must    know    about   every   possible    derivative  of  the  Shape  class,
  and it  must    be  changed whenever    new derivatives of   Shape  are
  created.

  The   fact    that     Square   and  Circle   cannot  be  substituted for Shape     is  a
  violation   of  LSP.    This    violation   forced  the violation   of  OCP by
  DrawShape . Thus,   a   violation   of  LSP is  a   latent  violation   of  OCP.

How does it violate Liskov substitution principle (LSP)?
(In particular, why can Square    and  Circle   not be  substituted for  Shape?)

How does violation of LSP cause violation of the open-closed principle (OCP)? (I can  see it directly violates OCP, but I can't understand how violation of LSP causes violation of OCP.)

Thanks.


texts: What is google docs solution to handling multiple users editing and reading at the same time?

texts:
I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time.

I believe this is very similar to the well known readers and writers problem.

In some of the solutions that i have seen, we would need a mutex of some kind whereby the writers will have exclusive lock to the document itself and readers will not be able to read the document at all.

But in the google docs case, it is quite interesting whereby another user can read the document in real time and two users can both edit the same document at the same time without any conflicts which is very impressive to me.