texts: Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC

texts:
Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover.

Define ALG: simple 2-approximation deterministic algorithm for the vertex cover problem in an unweighted graph.
Output of ALG: vertex cover which is at most twice the size of minimum vertex cover.

How will we show that?

My struggle: I tried to solve this in the following way(below), BUT I'm not sure that my proof is correct, meaning that, will there always exist a bipartite graph when n is even?

How I will approach the proof: We’ll show that maximum matching in a graph is equal to the size of minimum vertex cover, and then we’ll show that the output of ALG is exactly twice the size of maximum matching, and thus is twice the size of minimum vertex cover. And thus, there always exists a bi-partite graph which is divided to two distinct sets of size n/2 which contains a minimum vertex cover that is exactly half the vertex cover.

My proof:

Step 1: There always exists a graph, which is bipartite, that maximum matching in it is equal to the size of minimum vertex cover, in that graph.
Proof: Kőnig's theorem states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.

Step 2: A matching in graph G is a set of edges such that no two edges share a common vertex. A maximal matching M is a matching such that we cannot add any of the remaining edge into M while maintaining the matching constraint, in other word, if we add any of the edge then M will not be a valid matching anymore. Note that maximal matching is different with maximum matching. Maximum matching deals with the largest possible matching set. So, maximum matching is a maximal matching, but the converse is not necessarily true (see figure below for clarity).

Figure 4 corresponds to a maximum matching (we cannot do better than 3), but both Figure 4 and Figure 5 are valid maximal matchings (we cannot add any of the remaining edge to the set while not violating the matching condition).

We can conclude that is it’s maximum matching is ALWAYS maximal matching. (vice versa not always true).

Define C: the output of ALG – which is the vertex cover set of the “2-approx for minimum vertex cover problem”.

Let’s add also the ALG  algorithm for more clarity:

1: C = Ø
2: while there is uncovered edge (u,v)
3:   add vertex u into C
4:   add vertex v into C
5: return C

That’s it! For all uncovered edges (in any order), we only need to add both endpoints into the cover set (line 3 and 4).
In other words,

Define: If a graph has a minimum vertex set of size C*, then the algorithm will always provide a solution of cost C such that C <= 2C*.

Proof:

Claim: The approximation ratio of the algorithm is 2.
Let S* be a vertex cover of optimal size |S*| = C*.
Let E# be the set of edges picked by the algorithm.
Every edge in E# has at least one vertex in S*.
Every edge in E# has 2 vertices in S.
There are no other vertices in S.
Thus, the size of S is at most twice the size of S*.
C/C* <= 2

Step 3:

Lemma: The proposed algorithm ALG produce a maximal matching.
Every pair added into C in the algorithm is unique, it will not add edge (u,v) and (u,w) because when it encounters edge (u,v), it will add both vertex u and v, hence edge (u,w) will be covered by vertex u. Therefore, the algorithm will produce a matching in G, and it is maximal because it iterates until there is no uncovered edges.

Define: M – maximal matching.

Step 4:

From the algorithm and Lemma, we can conclude that the algorithm produce a vertex cover with size 2|M| (for each matching, we pick both vertices).
Thus,because of step 4 and step 1, the algorithm produce a vertex cover with size 2 * number of vertices in a minimum vertex cover.
And because n is even, the graph that will exist is bipartite with distinct sets of size n/2.

Q.E.D


texts: Enumerate subtrees of a given size in a graph

texts:
Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree?

Other than brute forcing the problem, it there an algorithm that can create the partitions of a graph that satisfy these conditions?

Furthermore, is there a way to enumerate all such possible partitions that lead to a set of subtrees?

Note I am not looking to prove existence. I actually want to use such an algorithm, so I am really looking for its description.


texts:
I'm currently reading about algorithms and big O notation.

I have come across som examples which for instance says the following:

n is O(n^2)

3n^2 + 7n is O(2n^2 + n)

5n^7 is O(2^n)

3^n is not O(n^4)

(1/n)^2 is not O((1/n)^3)

n^2 is not Ω(n^3)

Can somebody explain to me what is meant with these sentences?

I know what it means when an algorithm has running time O(1), O(N), O(N^2) etc.

But why is n equal to O(n^2) and why is 3^n not equal O(n^4) etc.?

Is there a way to calculate whether a formula containing n (the left side) is equal to another formula containing big O notation (the right side)?


texts: Theoretical question about Zobrist hashing and chances of collision with slight modification

texts:
I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any transpositions, but I still want to store the position in the hash table. So I'm trying to make the position's hash unique by XOR'ing it with the memory address of the object that holds the position structure. Here is some pseudocode:

hash = zobristHash(position);
if (makeItUnique)
    hash := h XOR [memory address of position object]

Is there any reason to suppose that what I'm doing will increase the likelihood of hash collisions?


texts: Is the set finite words over an alphabet a final coalgebra*?

texts:
I am studying what coinduction is. In particular, I am reading that coinductive datatypes can be defined as elements of a final coalgebra for a
given polynomial endofunctor on $\tt Set$. I've seen that $A^w$, infinite streams over an alphabet $A$, is the final coalgebra of the functor $FX \rightarrow A \times X$, and similarly $A^\infty$ (finite and infinity streams over $A$) is the is the final coalgebra of $FX = {\tt id} + A × X$.

I'm wondering if the set of finite streams over $A$ is a final coalgebra for some polynomial endofunctor on $\tt Set$. In other words, if there is a way to apply coinduction over the set of finite streams over $A$. I've seen that there must exist a so called $\textit{structure map}$ that maps $X \rightarrow A \times X$ and such that for $X=$our coalgebra, the previous map is an isomorphism (Lambek’s lemma).

Our object of study is $\bigoplus A$ and clearly $A \times \bigoplus A$ is isomorphic to it, so in principle $\bigoplus$ could be a coalgebra (Lambek’s lemma is currently my only source for providing counterexamples).

I find the notion of coinduction a bit counterintuitive because I don't know yet why it is well founded, but I think it would be a bit enlightening to know if you can use coinduction over streams of finite length.


texts: How to predict the next image in a sequence, or predict the deblurring of an image?

texts:
I have 3 versions of an image at lower resolutions - 480p, 720p, and 1080p. Is it possible to use those 3 images to predict the next highest resolution image (the 4k image)?

My first guess was that I could calculate the difference (or momentum or acceleration?) of each pixel between images and use that to predict the new 4th image. I assume this would require me to give all pictures the same number of pixels. I also assume that the differences in each pixel between images would need to be smooth. Would this work?

My other guess was that maybe there is some kind of statistics or machine learning technique that I could use, but I don't know anything about that stuff.

Thanks!

Ps - this man is not my real data. My real images are an intensity map (temperatures over an area) at different resolutions. I suspect that the introduction of colors might complicate things, so should we pretend that the images below are black-and-white images?

Here are the pictures:


texts:
I get the main ideas of Turing machines. But I can't construct a Turing machine to solve a given question.

The question I'm trying to solve is "Construct a Turing machine that recognises the set of all strings that contain an even number of $1$s."

How can I think about all the cases? Is there a way to do it?


texts: Which algorithm suits this problem best?

texts:
I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following:

There are several points of interest (POI), each has a value (for the user), the distance to each other POI is also known.
Now I want to generate the best tour (ordered list of POIs) with the most value for the user given a maximum distance he has to travel.

At first I was thinking about the knapsack problem where the distance would be the weight. The problem is, the order of the POIs is important and the weights vary according to the POIs already selected (more specifically, they depend on the last POI selected). Another idea is using TSP, where I first need to somehow select the subset of nodes which should be visited.

Does anyone have an idea, which known problem is similar to the one described and/or if there is an algorithm solving this. I'm not looking for an ideal solution, a good approximization is fine as well. Also perfomance is not an issue (for now).


texts: Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?

texts:
The description of this game is already exists in this link

I am quoting from this link the description of the game to ease the reading of this question:

In a game, where there are m active bombs, each one with a number above zero, and n standing levers, where each can be either pushed forward or pulled backward, and each lever is connected to some bombs with green wires/cables and connected to some bombs with red wires/cables.

If any lever is pushed forward then all bombs that are connected to this lever via green wire/cable are defused and all bombs that are connected to this lever via red wire/cable, their number is decremented by 1.

If any lever is pulled backward then all bombs that are connected to this lever via red wire/cable are defused and all bombs that are connected to this lever via green wire/cable, their number is decremented by 1.

A defused bomb cannot explode, but any active bomb that it's number reaches zero explodes immediately.

Only standing levers can be touched (either pushed forward or pulled backward). You shouldn't touch already touched (either pushed forward or pulled backward) levers.

To win/beat the game the purpose is to defuse all the active bombs without exploding any of them.

My greedy algorithm described in this question suppose to run in polynomial time, but it's not proven if it is correct.

Even though proving it's correctness is very difficult for me I am attempting to prove it, but this question isn't about this greedy algorithm at all.

Now this question is more general:

Can deterministic Turing machine beats/wins the game described in this question in polynomial time?

If yes, then there should exist polynomial time algorithm that returns all steps that should be followed to beat/win the given instance of this game (if it is possible).

The deterministic Turing machine or the algorithm doesn't have to be greedy necessarily.


texts: What am I missing in this application of Dijkstra?

texts:
When running Dijkstra against the following graph:

   1   3
A -- B -- C
 \      /
2 \    / 1
   \  /
    D

...I come up with the following:

   Current
                A      B          C          D
         A      1(via A)   -          2(via A)
         B      1(A)       4(via B)   2(via A)
         C      1(A)       4(via B)   2(via A) (5 via C ignored)

The shortest path from A to B is 1 via A.
The shortest path from A to C is 4 via B.
The shortest path from A to D is 2 via A.

...but there is a path from A to C via D that is of magnitude 3 (2 + 1).

What am I missing here?


texts: Minimum cost max flow network problem with an alternative flow cost

texts:
Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow * edge.weight over edges, but rather sum of  [edge.flow > 0] * edge.weight over edges, where [edge.flow > 0] equals one if the flow is greater than zero, and zero otherwise? Is it intractable, as I suspect?

I'll tell you about the original problem that I believe reduces to this problem. A bunch of friends have a dinner, and agree to split the bill evenly. But not everyone has enough money to cover their share at that moment, so some pay more than their share, some less, with the intent to settle later. Later on, they want to settle with a minimum number of transactions, where one transaction is money changing hands between a pair of friends.

This clearly maps to a bipartite network with edges of unlimited capacity from all the ones who underpaid going to all of those who overpaid, and edges of capacity equal to the amount underpaid going from source to the underpaid nodes, and edges of capacity equal to the amount overpaid going from overpaid nodes to the sink. To minimize the number of transactions we need to minimize the number of nonzero flow edges between the under- and overpaid.


texts: I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these two links which talk about LL(0): 1 and 2. These answers are quite satisfiable in explaining LL(0) grammars. However I still dont find anything on SLR(0) and LALR(0). Do they even exist? If yes, in what form?


texts: TSP genetic algorithm: what mutation function for adjacency representation?

texts:
When implementing TSP GA I decided for adjacency representation (i.e. $j$ value in $i$-th index means that node $j$ goes right after node $i$), as it enables interesting heuristical crossover operation (see Greffenstette, 1985). However this source, like many others, is silent about a sensible option of mutating solutions written in this way.

Traditional approaches (taken from path representation) usually result in incorrect solutions. For example, let's take permutation 5 4 1 3 2 (path rep. 1 5 2 4 3) and try swapping second and third position, namely giving 5 1 4 3 2. Path representation would start with 1 5 2 1 and oops, we're stuck. Another methods are similaringly disappointing.

So, is there an elegant and fast (emphasis on the latter) idea to mutate? Of course, I can switch between representations, but it might strongly impact performance (a switch is linear complexity, though I believe there's a chance of finding something with $O(1)$) and it's a worst-case scenario.


texts: Is undecidability contained in $PSPACE / o(exp(n))$?

texts: It is not hard to show that $DSPACE(n+1)/2^n$ contains undecidability. But is it possible to make the advice string subexponentially long (while the machine is allowed to have any $poly(n)$ space) using some succinct representations? Or is this an open problem with potentially interesting results?


texts: Proving that a word is *not* generated by a context-free grammar

texts:
I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF...

How did they get the answer so that ab is in the language and aaaa is not in the language here ?

S -> aSb |ab

ab     Yes
aaaa   No
aabb   Yes

edit:
is aaaa No because it has b in aSb and ab is yes because obviously ab is there in aSb |ab

also aabb is in the language because of aSb cause you would add same amount of a's and b's to both sides


texts: For given set of integers, find and count the pairs with maximum value of bitwise or

texts:
Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of bitwise or operation of all possible pairs $(x_i, x_j)$

We define bitwise or as bitwise operation that returns true if atleast one of the bits is turned on, in most programming languages it is declared as "|".

Edit: We assume that the numbers in the set can be written with at most 17 bits, or they are smaller than $2^{17}$.

For example, we have: $n=4, A = \{12, 3, 4, 11\}$ the maximum value of bitwise or will be $15$, because $12|3=15, 11|4=15, 12|11=15$ so the result is $15$ and we have exactly $3$ pairs that give this result.

My thinking

Obviously we can take each pair and see what is their bitwise or, but this leads us to solution in $O(N^2)$, and I think that there is much faster solution, I think that we don't need to calculate the bitwise or of all numbers, and we can only calculate it for some numbers.


texts:
I've been learning regular expressions as part of a class on automata and formal languages. I am still fine tuning and trying to figure out the algebra and the identities.
I am struggling with the regular expression
$$ (b^*a)^+.(b^*a) $$
It's supposed to come out as $$(b^*a)^*$$
I believe I have to use some identity between Kleene star and Kleene plus.


texts:
I am faced with the following question:

  Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram.

I started doing this using $Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$, and setting up a 7 tuple but I cannot come up with the state diagram.


texts:
I am trying to find the lowest common ancestor of 2 nodes in a graph with more than 250000 nodes and million edges. The graph is directed and has many cycles. Each node may or may not have an edge comping back to it from the child node. I tried finding an Euler tour using Hierholzer’s algorithm for directed graphs. But gave up on it. Most LCA algorithms in the public domain are for binary trees, DAGs, n-ary trees. I did not come across an algorithm for LCA for a large directed graph with cycles.
I am interested in the approach to take to solve this problem.


texts:
TL;DR

What revolutions have there been in computer science, which entirely changed our view about the subject, due to 'one way of thinking' being replaced by 'a new (incompatible) way of thinking' (such as Einsteinian physics replacing Newtonian physics).

To explain a bit further:

I was trying to think about revolutions in computer science, and which one there have been.
To clarify on what I mean by scientific revolutions:

  "Those non-cumulative developmental episodes in which an older
  paradigm is replaced on whole or part by an incompatible new one"
  (Kuhn, 1970 p.92)

To give perhaps the most famous example. Einstein's theories of relativity have shown that Newtonian physics is incorrect (it makes metaphysical assumptions, which turned out to be wrong). The paradigm in which General Relativity operates is incompatible with the Newtonian mechanics. Which then led to the reconstruction of science (Vienna circle).

A friend of mine (I believe correctly) pointed out that Quantum Computing could be one such revolution in computer science. But it has not actually happened yet.

As a software engineer myself, every time I thought of something that I'd consider a revolution, I became unsure if it really was a revolution as the 'paradigms' (methodologies) are not actually replaced and often even compatible with older ways of doing things. And some are pure technological advances (Functional programming after OO, or OO after procedural). Perhaps the application of Lambda Calculus in computer science (programming languages, type theory, ..?)

(Sure VCS was kind of a technological revolution, so if possible, let's keep the answers in computer science theory and not the applications in software engineering)

PS: I could not really find a suitable tag :-(


texts: Design patterns for simple text based scripting language?

texts:
In my current application I am trying to determine the best way to implement a simple scripting language. This language would allow a user to create a script that controls a machine with various inputs and outputs. I have defined most of the commands and created a nice editor for the language though I am stuck now trying to figure out how to verify, parse, and "compile" it.

I currently treat the commands as const String and plan to parse the input script text with regex and these strings. Most of the commands have the syntax

COMMAND Arg1 Arg2 Arg3 etc.

The types and numbers of arguments are currently not defined anywhere in my code, only in my head. I need a design pattern that would allow me to take a line from the script and determine if it is valid; check the command versus some list and check its arguments against the match in that list.

Are there any known design patterns for situations like this; scripting languages in general?

I feel like I need a class Command that holds the command string and information about its arguments, also the translation from string to "action" (performing the actual real life action the command describes). Then if I am to encounter the string representing the command I can lookup the command class instance, pass in the line, and get some result if it is valid. Though I feel like I would end up (in my case) with quite a few Command sub classes.

Any ideas or recommendations?


texts: Count elements of a sorted matrix that fall into a given interval

texts:
I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$.
Each row and each column of M is sorted in the increasing order.

I would like to know if there is way I can count the number of its elements which are inside $[k_\min, k_\max]$, using a $O(n)$ algorithm.


texts: Is packing a bag of presents easier for Rupert than Santa?

texts:
Or: Do we need Rupert in order to get presents at all?
Routing issues aside, Santa faces the following problem (many, many times over):

Given a bag with capacity¹ $C$ and a set of presents $\{p_1, \dots, p_n\}$, each with size $s_i$, he wants to make children $\{c_1, \dots, c_k\}$ happy. He knows from all the wish lists that child $c_j$ values present $p_i$ exactly $v_{i,j} \in \mathbb{Q}_{\geq 0}$ much.
Which (pairwise disjoint) sets of presents $I_j \subseteq [1..n]$ to pick for each child so that everything fits, i.e.
$\qquad\displaystyle \sum_{j \in [1..k]} \sum_{i \in I_j} s_i \leq C$,
and as much happiness as possible ensues², i.e.
$\qquad\displaystyle \max! \sum_{j \in [1..k]} \sum_{i \in I_j} v_{i,j}$ ?

This is clearly not easier than Bin Packing or Knapsack, so poor Santa may have to spend a long time packing bags³.

Now, as we know, his assistant Rupert does not give as unconditionally. He has knowledge about $V_j$, the maximum value child $c_j$ may receive based on behaviour during the year; that is, he adds an additional constraint

$\qquad\displaystyle \forall j \in [1..k].\ \sum_{i \in I_j} v_{i,j} \leq V_j$.

Does that make the problem of packing bags easier? If not always, then under which conditions?

If the chimney diameter is the limiting factor, a similar framework can be established.
Let's not concern ourselves with fairness and other ridiculuous ideas.
Hence, only one Christmas per year. Q.E.D.


texts: why & how are BFS nodes goal tested when they are generated?

texts: In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?


texts: Is language bin(n)bin(2^(k+1) n + 1)^R context-free

texts: I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N  \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R  \},$$ where $\cdot^R$ reverses a string and $\text{bin}(n)$ is the representation of $n$ in base 2. I need to determine if this language is regular, context-free or not and prove. I thought I could use the complement of $L_1$, but I can't get any intuition in this approach.


texts:
I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.

Each seat has neighbors. A person on a seat can talk to persons on neighboring seats (note that these neighbors normally sit next to each other or on the opposite side of the table).

Example of a table with 4 seats on each side:

1 2 3 4
8 7 6 5

6 has neighbors 2, 3, 4, 5 and 7, 8 has neighbors 1, 2, 7

There's a matrix describing how well two persons get along with each other. This is a value between 0 and 9 (the relation value). Relations are symmetrical.

Example of a relation matrix with four people:

  A B C D
A 0 2 0 5
B 2 0 3 6
C 0 3 0 1
D 5 6 1 0

The happiness of a single person is the sum of the relation values of all neighboring persons.

How would you find a solution that maximizes the overall happiness?


texts: Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

texts: Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over the data (for $p \in \{1, \dots , 2^\ell\} $) solve the number of distinct elements problem using only $O(\frac{n}{p}\ell)$ bits of memory? Not looking for probabilistic algorithms.


texts:
I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the root being the most accessed node.

The professor gave me the BST and node struct to work with, but trying to get my head around the algorithm to update the tree as things are being inserted is confusing me.

I know that as the insert is happening, it checks if the current node's data is less or greater than the current node, then recursively goes in the correct direction until it finds a null pointer and inserts itself there. and after it is inserted it increases the priority by 1.

template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

Now I need to figure out when the node is equal, how to re-order the tree so that the current node (who is equal to an already existing node) finds the existing node, increases that node's priority, then shifts it up if the root is a lower priority.

I think I have the idea down that the AVL logic would work, and when a shift would take place, it would be a single rotation right or a single rotation left.

Here's where I'm confused,  don't really know where to start with creating an algorithm to solve the problem. Since the AVL algorithm works with keeping track of the balance of a tree, then rotating nodes left or right accordingly, this tree doesn't need to worry about being balanced, just that the nodes with the highest priority not have children with a higher priority.


texts: Difference between Quick sort, Merge sort and Heap sort

texts:
We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\mathcal{O}(\mbox{N}^2)$. So what is the main difference between these algorithms? Which algorithm is preferable for sorting at any time?

Actually, I have been asked this in an interview. I replied Merge sort is not good with space. So we can consider Quicksort. But I couldn't figure out the difference between quick sort and heap sort. I need your help to figure it out.


texts: Determining when equal 2CNF has pure literal

texts:
Let us assume that we have a 2CNF $\varphi(X,y)$. Then we want to see if there is equal formula where $y$ (or $\overline y$) is pure literal. Can this be done in polynomial time? Are there some criteria for understanding this? Can we say if any minimal CNF has $y$ as pure literal, then all of them do?

Simple example:

$\varphi(x_1,x_2,y)=(x_1\lor y)\land(x_1\lor\overline y)\land(x_2\lor y)$.

Equal minimal 2CNF: $x_1\land(x_2\lor y)$.

Pure literal - literal that has only negative/positive appearances in formula.

Equal formula. We say formulas $\varphi$ and $\psi$ are equal if $\varphi\oplus\psi\equiv0$.

Minimal formula - shortest equal formula.

P.S. Last question is the most significant because it also answers if minimal 2CNF has all pure literals.


texts: Advice on using DRAMSimm2 or other DRAM simulation tools

texts:
As part of my PhD research I am currently building a simulation of a 256 core NoC and really want to model its interaction with the memory system.

My supervisor has suggested using the University of Maryland's DRAMSim2 tools, but it looks like work on that stopped a couple of years ago and the tool is not complete, while version 1 (even older) is complete but is not in a library form. I want to try to avoid reinventing the wheel by porting this to a library if at all possible.

I was wondering if any fellow researchers had been using DRAMSim2 effectively and/or if they have discovered good replacements?


texts: Simplification of Sum of Hamming Weight Sets

texts:
Let $k,n,K,m \in \mathbb{N}$ such that $k<n$. Let $l\in \mathbb{R}$, such that $0 \leq l \leq 1$. I am analyzing an algorithm and I need $O(N)$. Could you help me with the reduction of the expression $N$:
$$N=\log_S(1-\sqrt[K]{l})$$

where

$S=(\sum_{i=1}^m 2^{k-n}\binom ni)/2^{k}$

Using hint of DW, I try.

$$N=\log_S(1-\sqrt[K]{l})=\dfrac{\log_2(1-\sqrt[K]{l})}{\log_2S}=\dfrac{\log_2(1-\sqrt[K]{l})}{\log_2(\sum_{i=1}^m 2^{k-n}\binom ni)-\log_2(2^{k})}.$$

Using inequality of this answer, I get

$$N=\dfrac{\log_2(1-\sqrt[K]{l})}{nH(m/n)-1},$$

where $H$ is the binary entropy function. In my case $m<<<n$. At this point Could you help me please?


texts: Finding the linear mapping between homogeneous coordinates of affine camera

texts:
If I have an affine camera with a projection relationship governed by:

\begin{equation}
 \begin{bmatrix}
x & y
\end{bmatrix}^T  = A
\begin{bmatrix}
X & Y & Z
\end{bmatrix}^T + b
\end{equation}
where A is a 2x3 matrix and b is a 2x1 vector. How can I form a matrix representing the linear mapping between the world point $(X,Y,Z)$ and image point $(x,y)$ if they are represented by homogeneous vectors?


texts: What is the difference between a Transition System and a Program Graph? (model checking)

texts:
As the above question says.

I'm wondering if a transition system is the same as a program graph or they are two different things?

Thank you.


texts: How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue?

texts: A process in an Operating System is considered to occupy several states and a process transitions between these states. A scheduler is responsible for assigning CPU time to a process. However, a process that is performing an Input Output Operation and has gone into the blocked state must transition to the ready state or the ready queue to be more precise to be considered for scheduling by the scheduler. Which component of the operating system handles this transition? And does this transition require any CPU time for operation?


texts: How the closure properties of the formal languages dictate decidability of their problem

texts:
Consider the following problem:

Is $L_1 * L_2$ is of $LType$?
where we know that both  $L_1$ and $L_2$ are of type $LType$ and $LType$ is  closed under $*$ operation.

Above, by $LType$, I mean any type of language that is known to belong to any type of Chomsky hierarchy. So it may be regular (Chomsky Type 3), CFL or DCFL (Chomsky Type 2) etc.
Also by operation $*$, I mean any binary operation that results in another language, say intersection $\cap$, union $\cup$, difference $-$ etc.
Given all these pre-information of the type of languages and their closure under the specified operation, is the above problem decidable?
For example

Does the problem:

"Given that $R_1$ and $R_2$ are regular, is $R_1 \cap R_2$ too a regular language?"

is decidable, especially when we know that regular languages are closed under intersection?

Also can we comment in the same manner about undecidability of operation when  we know that the type of operand languages is not closed under that operation? That is

Does the problem

Is $L_1*L_2$ is of $LType$?

is undecidable?, especially when we know that $LType$ is not closed under the operation $*$ and that $L_1$ and $L_2$ are of type $LType$?

For example

Does the problem

Is $CFL_1\cap CFL_2$ is CFL?

is undecidable?, especially when we know that CFLs are not closed under intersection.

I feel both of above facts are correct/obvious/intuitive. But I am confused because no book on the theory of automata states it clearly.


texts: Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?

texts:
It is known that $\mathrm{SPACE}(o(\log \log n)) = \mathrm{SPACE}(O(1))$ (see e.g. these lecture notes by Christian Scheideler).

One inclusion is trivial, so I'm trying to show that $\mathrm{SPACE}(o(\log \log n)) \subseteq \mathrm{SPACE}(O(1))$ as follows.

Let $L$ be a language and $A$ is a Turing machine with alphabet size plus tape symbol is equal to $c$, to solve the problem $L$. We know that number of configurations is going to be at most $c^ {o(\log \log n)}\times\mathrm{poly} (o(\log \log n))$ (roughly), but even $c^ {o(\log \log n)}  \notin O(1)$.

For example, $ s(n) = \log \log \log n \in o(\log \log n)$ but $c^{s(n)} \notin O(1) $. I don't know, how to proceed further.

My question: How to prove that $\mathrm{SPACE}(o(\log \log n))\subseteq \mathrm{SPACE}(O(1))$?


texts:
I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to proceed:

Define 1/3-CNFSAT as follows: given a set of boolean variables and clauses in Conjunctive Normal Form, (this isn't 3-CNF SAT, as each clause may contain an arbitrary number of variables), does there exist a set of assignments to each variable such that exactly one-third of the clauses are satisfied?

Prove via reduction that 1/3-CNFSAT is NP-complete.

My initial thought process: Reduce CNF-SAT to 1/3-CNFSAT (Given: since any SAT formula can be reduced to CNF form, CNF-SAT is NP-complete).

So I was thinking, given some formula in CNF form, which contains C number of clauses, I was thinking we could add to it an additional 2C clauses, all of which are unsatisfiable. Then CNF-SAT would be satisfiable IFF 1/3-CNFSAT would be satisfiable.

Please let me know if my thoughts thus far are incorrect.

My problem now is how to come up with an additional 2C clauses all of which are false, and express each of them in CNF form. Obviously, something like the following clause would be inherently false:

(x1 AND ~x1)

But if I were to express it in CNF form, I'd have to do something like the following:

(x1 OR x1) AND (~x1 OR ~x1)

Or, even more simply:

(x1) AND (~x1)

But the problem is, only one of the above clauses is false for some given boolean assignment to x1. So, how do I come up with 2C false clauses and express them all in CNF form?

I hope this question makes sense. Thanks for help.


texts:
I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

They say that the above theorem is per Rice theorem which states that:

"Every nontrivial property of the RE languages is undecidable."

How are these two statements equivalent? The former deals only problems while the later deals with non trivial property.


texts: Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$?

texts:
I am trying to find the worst-case complexity of the following algorithm. The input to the algorithm is a list of positive integers $a_1,\ldots,a_n$ and a bound $C$.

$S\gets$ empty set
$k\gets0$
for $i\gets1$ to $n$ do

add $i$ to $S$
$k\gets k+a_i$
if $k>C$

$j\gets\arg\max_{i\in S}a_i$
$k\gets k - a_j$
remove $j$ from $S$

In the worst-case, at each iteration $i$, we go to the if condition and calculate the max. So, if the max operation requires $\Theta(n)$, then the worst-case complexity is $\Theta(n^2)$. As suggested in the comments, $\Theta(n)$ is not the best possible.

Here, I use an array to represent $S$. I can use a heap instead as a data structure to find the max in $\Theta(\lg n)$. So, the worst-case complexity is $\Theta(n\lg n)$. Am I right?

EDIT: I found this article https://cstheory.stackexchange.com/questions/18119/finding-smallest-k-elements-in-array-in-ok which finds the $k$ smallest elements in $O(k)$ time. My algorithm computes the $|S|$ smallest elements. Hence, it can be done in $O(|S|)$ time. But the $|S|$ is not given apriori. This is another issue now. Any help?


texts: FPTAS, except not polynomial in size: which class?

texts:
Problems in FPTAS require time which is (at most) polynomial in problem size. Suppose this last requirement is relaxed. What is the corresponding approximability class and where can one read about it? To be more specific, I am interested in learning about problems that can be approximated in time that scales polynomially with (inverse) relative error regardless of how it scales with problem size.

Second attempt.
Consider an instance of some optimization problem having size N. From now on, N is fixed. Consider an algorithm A that produces a solution with a relative error of epsilon after time T(epsilon). I am interested in scaling of T in 1/epsilon. In particular, I wonder if there is a (known? named?) class of problems that admit algorithms with T(epsilon) bounded by a polynomial in 1/epsilon (for each N). Clearly, near epsilon=0 power-law scaling of T(1/epsilon) breaks down as T reaches a finite limit for small epsilon (as was rightfully pointed out below by Yuval). Likewise, for very large epsilon T is not defined (no approximation is worse than the worst one). My question is if T can remain a power-law in 1/epsilon for “most of” epsilon’s range. I guess any instance in FPTAS provides an example. Are there instances not in FPTAS?


texts: Path in a graph with a given xor of weights of edges

texts: I have an undirected weighted graph with $V$ vertices and $E$ edges. Weight of a path is a xor of weights of the edges on this path. Paths can pass through the same vertices and edges many times. Given two vertices $a$, $b$ and some number $x$ I want to tell if there exists a path of weight $x$. What is the fastest algorithm to solve this problem?


texts: Adding ground rules to term rewriting system

texts:
Suppose we have a term rewriting system $\mathcal{R} = (\Sigma, R)$ with signature $\Sigma$ and set of basic rewrite rules $R$. Suppose we also have a set $S$ of ground rewrite rules, i.e. rewrite rules where both terms are ground terms. For my specific application, we can also assume that the right-hand sides of all rules in $S$ are single constants of $\Sigma$, and that the left- and right-hand sides of all rules in $S$ are distinct (so we don't have any rules in $S$ like $c \to c$, for some constant $c$). Now let $\mathcal{R}' = (\Sigma, R \cup S)$. If we know that the initial rewriting system $\mathcal{R}$ is confluent and terminating, are there any sufficient conditions on the rules $S$ and/or on the original system $\mathcal{R}$ that will ensure that the new system $\mathcal{R}'$ is still confluent and terminating?

In short: if we take a confluent and terminating term rewrite system and add some ground rules to it (subject to the extra conditions mentioned above), are there any conditions that will ensure that the new system is still confluent and terminating?


texts: Is it possible to write an HTML compiler with no mutable state?

texts:
That's probably a vague question but allow me to try and give an example:

My compiler does transformations on HTML (from HTML to HTML). It scans a flattened DOM tree, and relies on lookbehinds (on elements pushed onto a stack) to decide what transformation to apply. I can give more detail if necessary but I don't want to lose the reader.

Can such logic be alternatively implemented with no mutable state? I have become a big believer in functional programming and have made it a point to make my code as functional-style as possible. I don't like loops that perform actions based on the content of a previous iteration, by saving the information from a previous iteration in stacks or booleans. I need to augment the functionality of this routine and will probably tip the code from being "just about understandable" to "only the author will understand this, everyone else don't touch".

But I have little background in compiler theory & development so am wondering if the problem domain necessitates mutable state in practice.


texts: Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree

texts:
I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton z-curve.

Using only this information:

The level of a node can be computed by traversing to the root of the tree.
Neighbor searches are performed by traversing the tree up until a common parent is found, and then traversing the tree back down again.

I can compute the following constants depending on the number of spatial dimensions $n_d$:

the #of children of a node: $2^{n_d}$,
the #of $n_d - m$ dimensional neighbors for each node (in 3D, $n_d - 1$ neighbors are faces, $n_d - 2$ neighbors are edges, $n_d - 3$ neighbors are corners):

$2^{n_d} \begin{pmatrix} n_d \\ m \end{pmatrix}$

The neighbors sharing a $n_d - 1$-dimensional face with each Hypercube form the set $\mathcal{N}_{n_d - 1}$. They are numerated within this set as follows. The neighbor at the negative side from the node center comes first, then it comes the neighbor at the positive side. That is, for $n_d = 1$ I just have $\mathcal{N}_{n_d - 1} = \lbrace 0, 1 \rbrace = \lbrace \mathrm{Left}, \mathrm{Right} \rbrace$.

In $n_d = 2$, $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{Top}, \mathrm{Bottom} \rbrace$.
In $n_d = 3$ it is $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3, 4, 5 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{T}, \mathrm{B}, \mathrm{Front}, \mathrm{Back} \rbrace$

and so on.

I haven't been able yet to generalize the algorithm for finding the $n_d - 1$ neighbor located at a given position to arbitrary dimensions. My current algorithm traverses the tree up until a common parent node is found. During the up traversal it stores the child positions w.r.t. their parents of the nodes traversed. Then it traverses the tree back down using the reversed path of the up traversal. The child positions are found by finding the siblings of the child positions during the up traversal in the inverted neighbor direction, which can be computed as:

$\mathrm{inverted\_neighbor\_position}_{n_d - 1}(p) = (p + 1) * (p \% 2 = 0) + (p - 1) * (p \% 2 \neq 0)$

However, to know if a common parent has been found, it checks if a parent node has a childe at a given relative position of another child which expressed as a neighbor position, i.e., it checks if a node has a sibling in a given neighbor direction within its parent. I have only a hand-coded stencil for this check and haven't been able to generalized.

Can this check for a "common parent" be generalized to arbitrary dimensions? How?
Example up to 3D: for a child and a neighbor position, returns the child position of the sibling:

// i means, there is no sibling for that child in that direction
//0  1  2  3  4  5     << nghbr position
{ i, 1, i, 2, i, 4},  // child 0
{ 0, i, i, 3, i, 5},  // child 1
{ i, 3, 0, i, i, 6},  // child 2
{ 2, i, 1, i, i, 7},  // child 3
{ i, 5, i, 6, 0, i},  // child 4
{ 4, i, i, 7, 1, i},  // child 5
{ i, 7, 4, i, 2, i},  // child 6
{ 6, i, 5, i, 3, i}   // child 7

Assuming that the $n_d - 1$ dimensional neighbors can be found:

How can I find $n_d - m$ dimensional neighbors?

Right now, I hand-coded traversals that perform $m$ times searches for $(n_d - 1)$ neighbors. Is there a general way to generate these traversals for $n_d$ dimensions and the $n_d - m$ neighbors?

What is a suitable order for $n_d - m$ dimensional neighbors where $m > 1$ ?

Most of the research I've found in the literature uses hand coded stencils for, 1,2,3 and 4 dimensions, but no general ways of generating these stencils. So if anyone can point me to relevant literature I would appreciate it.


texts: Least number of comparisons needed to sort (order) 5 elements

texts:
Find the least number of comparisons needed to sort (order) five elements and
devise an algorithm that sorts these elements using this number of comparisons.

  Solution: There are 5! = 120 possible outcomes. Therefore a binary
  tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$
  ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number
  of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?


texts: Does a weighted Breadth First search have "memory" when moving to the next vertex?

texts:
I'm in a programming course and one Problem given to us is to mark the order in which BFS visits nodes in a weighted graph.

My question is whether BFS adds the distance of the previous path while adding a new vertex, as that will definitely change the order in which the vertices are added?


texts: Probability of data loss for mirrored,3 disk system

texts:
I am reading the book Database Systems the Complete Book 2nd Edition.
A slightly modified Question 13.4.5 states:

  Suppose we use three disks as a mirrored group; i.e., all three hold
  identical data. If the yearly probability of failure for one disk is
  F, and it takes H hours to restore a disk, what is the yearly probability
  data loss?

My answer is $(F*(F*H/365*24)^2)*6$

I would like to know if I am right. I will explain the reasoning behind my answer:

In order for data loss to occur, all 3 disks must fail within a time period of H hours.

The probability that the first disk fails is $F$. The probability that the second and third disks fail within $H$ hours of the first disk failing is $(F*H/365*24)^2$.

Thus the probability of all disks failing within a time period of H hours is $F*((F*H/365*24)^2)*6$.

The reason we multiply by 6 is because there are 6 ways in which this event could happen:

123
132
213
231
312
321

I have trouble with probability when dealing with events that can occur in multiple ways. So the only part of the reasoning that I am unsure about is the part where I multiply by 6. Are all 3 disks failing one event, or are they 6 different events?


texts:
In the below image, the graph is being triangulated (added edges are in red). My question is simple :
Is the red edge between nodes 7 and 10 necessary in order to obtain a chordal graph?

(this image comes from Yaroslav Bulatov's excellent answer on https://cstheory.stackexchange.com/questions/5018/the-origin-of-the-notion-of-treewidth/5020#5020)


texts: What are the simplest examples of programs that we do not know whether they terminate?

texts: The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?


texts: Satisfiability of first-order logic is undecidable?

texts:
I struggle with understanding why the satisfiability in the first-order logic is undecidable. Could you explain it with some examples? I've also seen that satisfiability in some first-order formulas are decidable.

Please explain it with as much as many examples.


texts: Is there a reason to NOT wrap preprocessor macros in parens?

texts:
I'm writing a design document for a macro expansion language that is specifically intended for arithmetic operations on integers. I've already determined that not wrapping macros with parens can lead to unexpected behavior. Rather than expect users to practice impeccable code hygiene, implementing automatic parens will save the users time and reduce bugs.

If a preprocessor adds enclosing parentheses every time a macro is expanded, is any useful functionality lost?


texts: Reason to learn propositional & predicate logic

texts:
I can understand the importance that computer scientists or any software development related engineers should have understood the study of basic logics as a basis.

But is there any tasks/jobs that explicitly require the knowledge about these, other than the tasks that require any kind of knowledge representation using Knowledge Base? I want to hear the types of tasks, rather than conceptual responses.

The reason I ask this is just from my curiosity. While CS students have to spend certain amount of time on this subject, some practicality-intensive courses (e.g. AI-Class) skipped this topic entirely. And I just wonder that for example knowing predicate logic might help drawing ER diagram but might not be a requirement.

Update 5/27/2012) Thanks for answers. Now I think I totally understand & agree with the importance of logicin CS with its vast amount of application. I just picked the best answer truly from the impressiveness that I got by the solution for Windows' blue screen issue.


texts: How to understand and remember proofs in automata theory?

texts:
Automata theory has a lot of proofs. Sometimes I don't get how this is a proof. Take for example the equivalence of NFAs and DFAs: the proof for this statement (two-way hypothesis and conclusion) shows how to "convert an NFA to DFA" and vice versa. How can this be a proof given that we ourselves have done changes in the construction of one from the other?

Similarly, there is this pumping lemma which I understood how to apply but not well enough to prove it. I need to understand these proofs in a very detailed manner so that I can write it myself.

Also, if we are to look at Sipser's textbook, it skipped a lot of topics in automata theory, for example:

Finite automata with output (Mealy and Moore machines).
Greibach normal form.
Closure properties.
Decision algorithms for context-free languages.
Equivalence of pushdown automata accepted by final state and accepted by empty stack.
Equivalence of PDAs and CFGs.
Converting regular grammars to finite automata and vice versa.

Where can I find a detailed description of the above topics with their respective proofs?


texts: How to solve cubing, batching, and routing problem together?

texts:
I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing.

The input data has some orders with items. Items have locations, 3 dimensions. Each tote has the same size. One trolley can fit 4 totes.

The cubing part could just use approximate volume.

The goal is to create batches with planned picking route.

The size of the problem: about 50-80 items per order. 5-10 orders during
the picking window.

The problem is intertwined if we want to minimize the distance. Should the cubing part solved separately without considering the batching and routing? If so, is this a VRP?

I assumed the cubing is a bin backing/multiple knapsack problem, and is first fit algorithm good enough? Which heuristic performs better?


texts:
I have an unlabeled dataset: 500 X-rays of seeds in husk. In each image there are different number of seeds, for instance, from $10$ to $50$.

A seed has some features. The main features are a seeds' square and a husks' square in pixels. I need to calculate the these features ratio.
I am looking for an objects recognize algorithm.
My problem is: I don't know what is a task type.

The dataset is unlabeled and I can use unsupervised learning and identify a similarity in groups (clustering task). Or I should to label data and use supervised learning and identify a real values (regression task)?
Question What is a task type?
Literature

The Plant Pathology 2020 challenge dataset to classify foliar disease of apples
Exploring Survival on the Titanic


texts: Upper bound on the covering radius of a code

texts:
Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \leq n-k$.

Could you give me a hint how we could show this?

The covering radius is defined as follows:

$$\rho=\max_{x \in \mathbb{F}_q^n} d(x,C) \\ d(x,C)=\min_{c \in C} d(x,c)$$


texts: Why does the neural network logistic regression cost function sum for all layers only for lambda?

texts:
I'm taking Andrew Ng's machine learning course and week 5 covers the training of neural networks. The modified cost function for neural network training is derived from the logistic regression cost function, and is described as follows:

$$\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] + \frac{\lambda}{2m}\sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}} ( \Theta_{j,i}^{(l)})^2\end{gather*}$$

Here, K is the number of output units, L is the total number of layers in the network, and ${s_l}$ is the number of units in layer l.

I don't understand why the second half of the cost function, intended to prevent over-fitting by minimizing the values of the theta parameters, is summed across the entire network while the first half of the equation which actually determines theta is only for a specific layer. If each layer's cost function already includes a minimization parameter for that layer's theta values, why is it necessary to perform this minimization globally for every layer in the cost function J?

As I understand it, in training a neural network you mainly treat each layer as completely separate from the next (and in fact, that is one of the major selling points of the NN approach, wherein solving L layers independently of one-another lets you use a simple approach to obtain powerful results) - so why are we summing the second half of the equation over all layers?


texts: Maximum number of positive literals in 2SAT

texts:
MAX 2SAT is NP complete.

Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (such that all the clauses are satisfied, of course).

What is the difficulty of this problem?


texts: what is the difference between an adapter and a controller?

texts:
1- why do have a USB controller but a display adapter ?

2- I have heard the terms network adapter and network controller being used, is there a differance between those ?


texts: Easy reduction from 3SAT to Hamiltonian path problem

texts:
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.

  Is there a simpler reduction?

By simpler I mean a reduction that would be easier to understand (for students).

  Is there a reduction that uses linear number of variables?

The reduction in Sipser uses $O(kn)$ variables where $k$ is the number of clauses and $n$ is the number of variables. In other words, it is possible for the reduction to blow the size from $s$ to $O(s^2)$. Is there a simple reduction where the size of the output of the reduction is linear in the size of its input?

If it is not possible, is there a reason? Would that imply an unknown result in complexity/algorithms?


texts: How to find the best exploration parameter in a Monte Carlo tree search?

texts:
I've developed a Monte Carlo tree search algorithm in checkers.

Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in Monte Carlo Tree Search (MCTS)?

$$ S_i=x_i+C\sqrt{\frac{\ln (t)}{n_i}}$$

General consensus is that a value of $\sqrt 2$ should be used, but when I use a value of 10 it works, which save me a lot of time.

So, how can I find the best value for $C$, that best suits my problem?


texts: generate all unlabelled trees up to size n

texts:
Who has published an answer to these problems?

An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define such a signature.

Many thanks
Keith Paton
Independent researcher


texts: Is there such a thing as an algorithm that runs in asymptotic time?

texts: For example: $O(-e^{-x} +1)$. Basically as the size of the input increases, the time it takes to run converges.


texts: Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

texts:
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al. where I came across the following excerpt.

Example 4.11. Consider the abstract language $L_1 = \text{ { $wcw$ | $w$ is in $(a|b)^*$}}$. $L_1$ consists of all words composed of a repeated string of $a$'s and $b$'s separated by a $c$, such as $aabcaab$. It can be proven this language is not context free. This language abstracts the problem of checking that identifiers are declared before their use in a program. That is, the first $w$ in $wcw$ represents the declaration of an identifier $w$. The second $w$ represents its use. While it is beyond the scope of this book to prove it, the non-context-freedom of $L_1$, directly implies the non-context-freedom of programming languages like $\text{Algol}$ and $\text{Pascal}$, which require declaration of identifiers before their use, and which allow identifiers of arbitrary length.
For this reason, a grammar for the syntax of $\text{Algol}$ or $\text{Pascal}$ does not specify the characters in an identifier. Instead, all identifiers are represented by a token such as $\text{id}$ in the grammar. In a compiler for such a language, the semantic analysis phase checks that identifiers have been declared before their use. □

I can understand that since $\text{Algol}$ and $\text{Pascal}$, require declaration of identifiers before their use we cannot check this property using context free grammar. But what is the connection of this with the point of "allowing identifiers of arbitrary length"?
Moreover the authors add, that instead of using the characters in an identifier, identifiers are represented by the token class $\text{id}$. That the identifiers are represented by the token class $\text{id}$, was known to me as a fact, but I did not quite know what is the significance of this as far as the explanation in the example of the text is concerned.
Please explain me.


texts: How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem)

texts: I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.


texts: Understanding the P2||CMax scheduling problem

texts:
I have a problem with understanding the $P_2 \mid \mid C_\max$ problem which is also known as Tasks Scheduling on Multiple Processors.

In fact, in my case I need only one processor (but the problem is usually described for 2 or more so let it be). I understand what is all about: given a set of tasks with constant delay time and priority the algorithm should find the best permutation of them so that the total delay time is the smallest one.

And now is my question: if the delay is constant for each task, so how come different permutations provide different total delay?


texts:
I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution.
The problem is as follows:

Half-SAT is a problem where C is a CNF boolean formula with n variables and m clauses, where m is even. We have to determine if there exists an interpretation that satisfies exactly half of the clauses. Prove Half-SAT intractability with a reduction from SAT.
Clues: A formula can have duplicated clauses It's possible to write clauses that are always true.

I'd be very grateful if you could give me any clue on how to approach this problem.


texts: Divide and conquer algorithm to sort nk items in n lists that runs in O(nk*logn) time?

texts:
In trying to write pseudocode for it, this is my attempt:

I'm just trying to write a pseudo-code for it and explain the run time.

So far this is what I have:

k-merge-sort(L)
  { if length(L1) <2 return L1
   else
     { split L into L1, L2, L3
     A1 = k-merge-sort(L1)
     A2 = k-merge-sort(L2)
     ....
     An = k-merge-sort(Ln)
     Bn = k-merge(A1..An)
     }

Thoughts? Thank you! As for the run time, the logn part of it comes for it being a complete binary tree's height, the height being the number of lists and the n*k part from the items.


texts: Are regular languages and their regular expressions part of computer science?

texts:
I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular.

In math discourse there was always the question like "Are mathematics discovered or invented?".
I am quite sure regel-regex is not a mathematical theory but a linguistics theory (even though it was first theorized by a mathematician - Stephen Cole Kleene).

Is regex part of computer science and if so, is it generally accepted as "discovered" or as "invented", and what could be one example of what's being further researched in regards to matching information on a computer document?


texts: Condition for perfect matching in bipartite graphs

texts:
Let $G = (S, T, E)$ be a bipartite graph without isolated vertices.

For each edge $e ∈ E$, $e = st$ (where $s ∈ S$, $t ∈ T$), the inequality
$d_G (s) ≥ d_G (t)$ holds. Prove that there is a matching in $G$ saturating all
of $S$'s vertices.


texts: Calculation of Inorder Traversal Complexity

texts:
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research it is $O(n)$. Can you show it how come and my wrong?

void printInorder(Node node)
    {
        if (node == null)     // I think it is T(0) = 1
            return;           // constant c

        /* first recur on left child */
        printInorder(node.left);     // T(n-1)

        /* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

        /* now recur on right child */
        printInorder(node.right); //T(n-1)
    }


texts:
today I found this term in our exercises: ((^fx.f(f(f x)) ^gy.g(g y )) ^z.z + 1) (0)

I am quit unaware how to solve this type of question.
I know this is the church numeral 3 , 2 , the identity function +1 and zero.
But for my understanding it lacks an operator like +-*/
as ex.

(λmn.m (succ n)) to connect two church numerals?

Some hints will be greatly appreciated.


texts:
I'm trying to make non deterministic automata for specific language .
I cant understand my mistake!
Rules:
1){a,b,c}
2) if I have the sequence "bb" and later in the word I have the sequence "cc" so this is not possible that I have the sequence "cba" between them.
Thank you !


texts: Are modern programming languages context-free?

texts:
Which language class are today's modern programming languages like Java, JavaScript, and Python in?
It appears (?) they are not context-free and not regular languages.
Are these programming languages context-sensitive or decidable languages? I am very confused!
I know that context-free is more powerful than regular languages and that context-sensitive is more powerful than context-free.
Are modern programming languages both context-free and context-sensitive?


texts: Why is self-information defined the way it is?

texts:
The self-information of an event of probability $p_x$ is defined as $I(p_x)=-\log_2(p_x)$.¹

I fully understand this for equiprobable events of the form $p_x = \frac{1}{2^k}$.
In that case, we want to encode $2^k$ events so we need $\log_2(2^k)=k$ bits.
So $I(p_x)$ should be $\log_2(\frac{1}{p_x}) = -\log_2(p_x)$

However I am confused about the generalization to events of different probabilities and probabilities where $p_x \neq \frac{1}{2^k}$.
Then, I am wondering why $\log$ is a good choice.

I've never come farther as to such tutorials:
http://www.i-programmer.info/babbages-bag/213-information-theory.html
But as I read it they just think about what they want, namely a function $I$ with $I(xy)=I(x)+I(y)$ and then find that $-\log_2(p_x)$ satisfies all their needs. But is $\log$ the only choice they have? $I(x)=0$ works too! What are the exact requirements that we need? And why do we finally choose $I(p_x)=-\log_2(p_x)$?

¹I know $2$ is just the special case for bits, chosen for simplicity.


texts: What is discrete mathematics and why am I learning about it?

texts: I started computer science in university. And we started learning about Discrete and it's mathematics which is completely based on logic, which I understand. however, how is predicates, sets, proofs are related to computers ? I want to know the reason for learning these stuff?


texts: What is a list of "reasonable but undecidable" theorems?

texts:
There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples:

Rice's Theorem: "all reasonable semantic properties of programs are undecidable."
Adian–Rabin Theorem: "all reasonable properties of finitely presented groups are undecidable."

Even though I only know of two examples, I suspect that there are many theorems like these. Is there a list of these kinds of theorems?


texts:
I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets.  If there are ties for the most common subset, I want the one of them whose size is as large as possible.

For example if I have:

s1 = {A, B, C   }
s2 = {A, B, C, D}
s3 = {   B, C, D}

Then the most common subset of size $\ge k=2$ is {B, C}. As another example, if I have:

s1 = {A, B, C  D}
s2 = {A, B, C, D}
s3 = {   B, C, D}

Then the most common subset of size $\ge k=2$ is {B, C, D}. It's important that in this instance the algorithm would give me {B, C, D} and not {B, C}, {B, D} etc. Note that I'm not interested in the longest common subset (a different problem), I'm interested in the longest most common subset if you will. I also don't care about enumerating all the different subsets, I just want to find the most common.

Is there an efficient algorithm for this problem?

I have an algorithm for this problem, but I don't think it's very efficient. For $k=2$ I enumerate all subsets of size 2 and count how many times each one appears in the collection. If the most-frequently occurring pair is more frequently occurring than any other pair then that must be the most common subset. If there is more than one with the same (maximum) frequency then I look at the sets they are contained in. If these overlap exactly then I take the union of the pairs and that gives me the most common subset (with size > 2).

I think this could be related to the maximum clique problem but I'm not certain.

Note that just taking the intersection does not give the correct answer.  For instance, if I have

s1 = {A, B      }
s2 = {      C, D}
s3 = {A,    C, D}

then the intersection is the empty set, but the most common subset is {C, D}.


texts: Being stuck and frustrated with my masters project

texts:
I'm doing a masters in CS that requires me to implement from scratch most of the neural network models and because python libraries aren't applicable to what i want.

The problem is that i don't feel capable of implementing those from scratch. Even the MLP seems very difficult, i always try but get stuck and restart. Meantime, i feel that my supervisor think it's a natural thing and i shouldn't have problems implementing those algorithms.

I know that when we are talking about research, it shouldn't be easy - because anyone else would do it if so - but i'd be glad to receive some advices about this process i am going  through: Am I not prepared enough for this or is it an overambitious idea to implement all these networks from scratch? Should i continue this? I've already thought about giving up.

Ps: any good materials (books, videos, etc) focusing in implementation of neural networks are welcome.


texts:
I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator.

Let swap : {a, b}∗ → {a, b}∗ be the function that exchanges the a’s and b’s in a string. For
example, swap(baaba) = abbab and swap(aaaa) = bbbb.
For L a language over {a, b}, define swap(L) as follows:
swap(L) = {swap(w) | w ∈ L}.

Show that the class of regular languages over {a, b} is closed under the swap
operator. Let M = (Q, {a, b}, δ, q0, F) be a DFA. Define DFA M'
such that L(M'
) =
swap(L(M)).

So far I have M' = (Q, {a, b}, δ', q0, F) where δ'(q, a) = δ(q, b) and δ'(q, b) = δ(q, a) meaning that in the transition function states q given a that map to q in M would map to q given b in M'. Am I missing anything?


texts: Why is BNF considered an unsatisfactory technique for describing a language?

texts:
I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part highlighted by me):

  Faced with the situation as it exists today, where there is a generally known method of describing a certain class of grammars (known as BNF or context-free), the first instinct of these mathematicians seems to be to investigate the limits of BNF—what can you express in BNF even at the cost of very cumbersome and artificial constructions? This may be a question of some mathematical interest (whatever that means), but it has very little relevance to programming languages where it is more important to discover better methods of describing the syntax than BNF (which is already both inconvenient and inadequate for ALGOL) than it is to examine the possible limits of what we already know to be an unsatisfactory technique.

Is there a specific reason the author considers the BNF to be an unsatisfactory technique for describing languages? Could it be because you can only describe syntax and not semantics with a single BNF grammar (though, you can extend it to describe operational semantics via turning it into an attribute grammar)?


texts: Attack on hash functions that do not satisfy the one-way property

texts:
I am revising for a computer security course and I am stuck on one of the past questions. Here is it:

  Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to authenticate that the message has come from her. She proposes to send a single message with two pieces:
  $$ A \to B: \quad M, h(M \mathbin\parallel S_{ab})$$
  where $h$ is a hash function and $\parallel$ denotes concatenation.

  Explain carefully what Bob does to check that the message has come from Alice, and why (apart from properties of $h$) he may believe this.
  Suppose that $h$ does not satisfy the one-way property and it is possible to generate pre-images. Explain what an attacker can do and how.
  If generating pre-images is comparatively time-consuming, suggest a simple countermeasure to improve the protocol without changing $h$.

I think I know the first one. Bob needs to take a hash of the received message along with his shared key and compare that hash with the hash received from Alice, if they match then this should prove Alice sent it.

I am not sure about the second two questions though. For the second one, would the answer be that an attacker can simply obtain the original message given a hash? I'm not sure how that would be done though.


texts: It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

texts:
S->aAB

  A->bBb

  B->A|epsilon

It seems that the string abbbb can be derived by using more than one ways.
After using the starting production and the production for A, we get:
S=>abBbB.

From here, either of the B's can be replaced with epsilon and the other one replaced with bBb. So, there are two ways of deriving abbbb.

Isn't this ambiguous grammar?

It's a question from Formal Languages and Automata by Peter Linz (5th edition) Exercise 5.2.16


texts: What is difference between nondeterministic polynomial time and exponential time?

texts: I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank you


texts: Algorithms to match regular expressions containing backreferences

texts:
I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like:

([a-c])x\1 which would match axa, bxb and cxc but nothing else.

While I've seen a number of posts about the theory about what is the class of languages this type of regexes describe, I didn't manage to find some more concrete implementation details beyond the fact that matchers for Context Sensitive Languages are Linear Bound Automata.

Could you point out some resources about the implementation of such matchers?

UPDATE: Currently this is my best reference: "Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions"

PS: These regex features are supported by most standard libraries of modern programming languages (Perl, Java, C# etc), but I wouldn't start there since I believe those implementations are quite terse.


texts: DLOGTIME complexity class and testing the length of the input string

texts:
I read that testing the length of the input string is in DLOGTIME.

The question is how can testing the length of the input string be in DLOGTIME?

$\text{DLOGTIME} = O(\log n)$, so what number would be in $n$? (as it seems that $n$ is definitely not the length of the input string..... or is it?)

So, to summarize, can anyone show me how the algorithm performs and how it is in DLOGTIME? At this point, it seems to me that $n$ is just an arbitary number..

Note: I know what binary search is :) so you do not need to explain me about what that is.


texts: Nth number in a infinite sequence of numbers

texts:
This was interview question.

When the input is a infinite sequence of numbers starting from 1, what is the nth digit?

e.g.) 123456789101112131415161718192021.....

here 28th digit is 1.


texts: Proving the lower bound of compares in comparison based sorting

texts: I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help is appreciated!


texts: Subarray whose (sum × length) is maximum

texts:
Consider the following problem:

  Given an array of $n$ integer numbers (positive and negative), find a (contiguous) subarray for which the product $(\text{sum of the elements})\times(\text{length of the subarray})$ is maximum.

Is there an algorithm with complexity less than $O(n^2)$?

For instance, if the array is
$$-2,\ 3,\ 7,\ -8,\ -15,\ \underline{1,\ 1,\ 7,\ -2},\ -3$$
then the underlined subarray would be the one we are looking for (its "score" is 7×4 = 28).

I tried everything I know (dynamic programming, greedy, divide and conquer, the general "fix one endpoint and find the other"), and asked many people, but nobody could find an answer.


texts: What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?

texts:
The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can be (and usually is) lifted for regular and context-free grammars (i.e. they are allowed to have productions of the form $X \to \epsilon$) without altering the class of languages generated.
The rule, however, remains for context-sensitive grammars.
My question is, given a grammar with productions $\alpha X \beta \to \alpha \xi \beta$ where $\alpha, \beta, \xi\in (N \cup T)^*$ (i.e. a context-sensitive grammar with $\epsilon$-rules), what class of languages does that describe? The recursively enumerable ones (same as unrestricted grammars) or something else?


texts:
I cannot solve this exercise:
"If a processor has a cache hit rate of 99.5% and a cache miss penalty of 160 core processor cycles, what will the average CPI be for 1,000 instructions?"
how can i do this?


texts: Is the difference of a non-recursive and recursive set recursive?

texts:
I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$?

$B-A$ is obviously recursively enumerable (to generate its elements, I can generate B's elements and check if they are in A).

If A is the empty set or $A \cap B$ is the empty set, it's easy. Otherwise, I believe $B-A$ is not recursive (I can't tell if a number is in B, since B is not recursive) and $A-B$ is not recursively enumerable (I can generate A's elements, but I can't check if they are in B), so it's not recursive either.

Am I wrong? How can I actually (and formally) prove any of those?


texts: Algorithm for specific load balancing/arbitration problem

texts:
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could point me in the direction of further reading or prior work (or, of course, develop a complete answer should you wish) that would be immensely helpful.
The problem
Find an output which satisfies the conditions below for a given input. Previous inputs and outputs need not be considered. (I've specified this for simplicity.) The idea is to preserve the input grouping while maximising the output occupancy and prioriting higher values over lower values. The exact requirements are set in stone, cannot be changed, and are described below.
Input: N lists of zero to M positive integers.
Output: a selection of between 1 and k of the input data accompanied by their position in the nested lists, identified by (x,y), x ∈ [0,M-1], y ∈ [0,N-1], with y indexing the list of lists and x indexing the individual list.
The whole, flat set of valid input integers can be identified by their indices (x,y) ∈ U, with |U| = N ✕ M.
Constraints:

let S be the set of (x,y)'s output simultaneously.

maximise |S|, up to k (which may be less than N ✕ M)
among the solutions that maximise |S| (discounting those that do not), minimise the number of distinct y's in S (i.e. minimise the number of different input lists represented in the output) as far as possible while satisfying (1).

let f be an arbitrary function from (x,y) to the strictly positive integers (i.e. the integers described in the input section).

for each (x,y), let (x,y) belong to a class T(y'), (x,y) ∈ T(y') iff y = y' and (x,y) ∈ U.

∀j ∀(x,y) ∈ (S ∩ T(j)), f((x,y)) >= f((x',y')) ∀(x',y') ∈ (T(j) ∩ (U - S)). In other words, all list elements output must have a greater integer than those from the same list that are left behind.

(and here's the problem) Each input list from which at least one integer (and x,y) is output can be described as a "selected list." A list from which no element is output is a "deselected list." The integers inside the input lists affect which lists are "selected" in the following way. Among the list combinations that could be selected without violating the need to maximise the number of outputs and to minimise the number of selected lists, the algorithm must choose a combination which selects higher integers in favour of lower ones. Specifically, allow the lists to be ordered by their highest integer. Where a choice exists subject to requirements 1 and 2, choose lists that are higher in this ordering over ones which are lower. (Note that as a consequence of 3, the greatest element of a selected list will always be output.)
Proposed formalism to follow tomorrow.

So as you can see, requirement 4 (choose lists with higher max numbers) affects which lists get chosen. A greedy approach, either with respect to list length, or with respect to the integer value, does not yield a correct result, since many lists (of potentially differing lengths) could be used to fill the k slots; choosing natural numbers first and then choosing lists based on those fails to minimise the number of input lists selected from.


texts: What is the complexity of my algorithm to solve this kind of system of nonlinear equations?

texts:
My algorithm solves the following problem:

$n\in\mathbb{N} \land n\ge1$

$\{v_1, \ldots , v_n\}\subset\mathbb{Q}$

$
\begin{eqnarray}
\left\{
\begin{array}{}
\square\cdot\square\cdot\square = 0 \\
\vdots \\
\square\cdot\square\cdot\square = 0 \\
\end{array}
\right.
\end{eqnarray}
$

$\square\in\{v_1,\ldots,v_n,1-v_1,\ldots,1-v_n\}$

The algorithm works as follows:

First of all open up all brackets (), i.e. eliminate them so they are not appear in the system anymore without changing the equations, i.e. the consistency of the system.

This part should take polynomial time I guess.

As you can see all equations are equal to zero, so the algorithm solves the problem by doing the substitution method.

It chooses the smallest equation and substitutes it in a larger equation and thus it eliminates and removes subexpressions and simplify the system.

The algorithm repeats the substitution method until it cannot be done anymore.

If $1=0$ was discovered then return as answer: The system is inconsistent.

Otherwise return as answer: The system is consistent.

For example let's apply my algorithm to the following system of nonlinear equations:

$
\begin{eqnarray}
\left\{
\begin{array}{}
v_1 \cdot v_2 \cdot v_3 = 0 \\
(1-v_1) \cdot v_2 \cdot v_3 = 0 \\
v_1 \cdot (1-v_2) \cdot v_3 = 0 \\
(1-v_1) \cdot (1-v_2) \cdot v_3 = 0 \\
v_1 \cdot v_2 \cdot (1-v_3) = 0 \\
(1-v_1) \cdot v_2 \cdot (1-v_3) = 0 \\
v_1 \cdot (1-v_2) \cdot (1-v_3) = 0 \\
(1-v_1) \cdot (1-v_2) \cdot (1-v_3) = 0 \\
\end{array}{}
\right.
\end{eqnarray}
$

here in this example $n=3$, because there are only three variables, which are $v_1$, $v_2$ and $v_3$.

First of all let's open up all the brackets (), so they are not appear in the system. After doing that the system should look like this:

$
\begin{eqnarray}
\left\{
\begin{array}{}
v_1 \cdot v_2 \cdot v_3 = 0 \\
v_2 \cdot v_3 - v_1 \cdot v_2 \cdot v_3 = 0 \\
v_1 \cdot v_3 - v_1 \cdot v_2 \cdot v_3 = 0 \\
v_3 - v_2 \cdot v_3 - v_1 \cdot v_3 + v_1 \cdot v_2 \cdot v_3 = 0 \\
v_1 \cdot v_2 - v_1 \cdot v_2 \cdot v_3 = 0 \\
v_2 - v_2 \cdot v_3 - v_1 \cdot v_2 + v_1 \cdot v_2 \cdot v_3 = 0 \\
v_1 - v_1 \cdot v_3 - v_1 \cdot v_2 + v_1 \cdot v_2 \cdot v_3 = 0 \\
1 - v_3 - v_2 - v_1 + v_2 \cdot v_3 + v_1 \cdot v_3 + v_1 \cdot v_2 - v_1 \cdot v_2 \cdot v_3 = 0 \\
\end{array}{}
\right.
\end{eqnarray}
$

Now let's substitute $v_1 \cdot v_2 \cdot v_3 = 0$ from the first equation and we get:

$
\begin{eqnarray}
\left\{
\begin{array}{}
v_1 \cdot v_2 \cdot v_3 = 0 \\
v_2 \cdot v_3 - 0 = 0 \\
v_1 \cdot v_3 - 0 = 0 \\
v_3 - v_2 \cdot v_3 - v_1 \cdot v_3 + 0 = 0 \\
v_1 \cdot v_2 - 0 = 0 \\
v_2 - v_2 \cdot v_3 - v_1 \cdot v_2 + 0 = 0 \\
v_1 - v_1 \cdot v_3 - v_1 \cdot v_2 + 0 = 0 \\
1 - v_3 - v_2 - v_1 + v_2 \cdot v_3 + v_1 \cdot v_3 + v_1 \cdot v_2 - 0 = 0
\end{array}{}
\right.
\end{eqnarray}
$

Now let's substitute $v_2 \cdot v_3 = 0$, $v_1 \cdot v_3 = 0$ and $v_1 \cdot v_2 = 0$:

$
\begin{eqnarray}
\left\{
\begin{array}{}
v_1 \cdot v_2 \cdot v_3 = 0 \\
v_2 \cdot v_3 = 0 \\
v_1 \cdot v_3 = 0 \\
v_3 - 0 - 0 = 0 \\
v_1 \cdot v_2 = 0 \\
v_2 - 0 - 0 = 0 \\
v_1 - 0 - 0 = 0 \\
1 - v_3 - v_2 - v_1 + 0 + 0 + 0 = 0
\end{array}{}
\right.
\end{eqnarray}
$

Now let's substitute $v_3 = 0$, $v_2 = 0$ and $v_1 = 0$:

$
\begin{eqnarray}
\left\{
\begin{array}{}
v_1 \cdot v_2 \cdot v_3 = 0 \\
v_2 \cdot v_3 = 0 \\
v_1 \cdot v_3 = 0 \\
v_3 = 0 \\
v_1 \cdot v_2 = 0 \\
v_2 = 0 \\
v_1 = 0 \\
1 - 0 - 0 - 0 = 0
\end{array}{}
\right.
\end{eqnarray}
$

And we have got $1=0$ on the last equation so this system is inconsistent and we're done.

Now my question is:

What is the complexity of my algorithm?

I guess that it's exponential, i.e. all the substitutions take exponential time, but I have no proof.


texts:
I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand".

I do not see a simple way how to draw such a tree. Is there a simple step by step method for people not knowing the algorithms?


texts: Why does functional map() operation not permit operating on two elements of a list at a time?

texts:
Mathematically it seems so easy to use two elements of a vector as two arguments to a function.
$$f(\boldsymbol{x_{i+1}},\boldsymbol{x_{i}})$$
In functional programming however a map (function) allows to work with one element at a time only, so one would need to create vector of pairwise 2-tuples from a single initial vector fisrt. Why is that? Is it also more proper mathematically?


texts: Size of Maximum Matching in Bipartite Graph

texts: Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?


texts: What is linear relaxation in the context of bayesian networks?

texts:
To add onto the question, how are elliptical differential equations applicable in this context?

I was listening to a talk about Bayesian networks and someone asked if they were using differential elliptical equations in the context of linear relaxation.


texts: Can someone tell me what the recurrence equation for this code is?

texts:
Consider the algorithm below

Precondition: n is a non-negative integer

function f ( n )

{

temp = 0

if (n != 0)

{

for (i = 1; i <= 3; i++)

temp = temp + n * f(n-1)

return temp

}

else

return 1;

Solve for the closed form by repeated substitution


texts:
I'm a little confused about how monotone priority queues work.

As far as I understand:

A queue is a FIFO data structure
A priority queue is a queue where the current element of highest (or lowest) priority is served before an item of lower (or higher) priority

Now, for monotone queues, I read the following on Wikipedia (also here):

  Monotone priority queues are specialized queues that are optimized for
  the case where no item is ever inserted that has a lower priority (in
  the case of min-heap) than any item previously extracted.

I'm a little confused here. Does this mean that a monotone priority queue is nothing else than a regular priority queue with an enqueue method that simply prevents anyone from adding elements that are lower (monotone increasing) or higher (monotone decreasing) than the min (or max) element that was previously extracted?

If so, in what ways are these FIFO queues "optimized" for monotonicity?


texts: Random uniform sampling of position restricted permutations

texts:
Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions?

Consider $N \times N$ restriction matrices $R$, that is matrices over $\{0,1\}$. Each such $R$ defines a set of permutations $\Pi_R$ according to

$\qquad\displaystyle \pi \in \Pi_R \iff \forall i \in [1..n].\ \pi(i) = j \implies R_{i,j} = 1$.

Note that $R$ is not permutation matrix but a general restriction matrix.
I want to sample uniformly from $\Pi_R$ given $R$.

So far I am using Hungarian's assignment algorithm to produce random permutations consistent with restriction matrix $R$, but these permutations are significantly non-uniformly sampled.

Examples:

Every $R$ that has one one per row and column admits only a single permutation.
For

$\qquad\displaystyle R = \left( \begin{array}{ccc}
0 & 1 & 0 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array} \right) $

there are only two permutations:
$\pi_1 = (2 1 3)$ and $\pi_2 = (2 3 1)$.
If $R$ contains only ones, $\Pi_R$ is the set of all permutations.


texts:
Why is the recurrence formula for insertion sort is T(n-1) + n?

I understand the T(n-1) part but the why does the cost for merging results is n or linear. Do we have to merge in insertion sort?


texts: Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"?

texts:
The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard).

Another possible way of making it into a decision problem would be:

Instance: Graph $G=(V,E)$ and vertex $v\in V$.
Question: Does there exist a clique $C\subseteq V$ in $G$ that contains $v$ and is of maximum cardinality among cliques?

If P = NP, this problem is polynomial-time solvable. The problem is also contained in $\Sigma_2^p$ (does there exist a clique such that all other cliques are not bigger?). Has its precise complexity been studied?

(Very similar questions can of course also be asked about vertex cover, dominating set, independent set and the like).


texts: Understanding DIQKD protocol, a few questions

texts:
I'm refering to this paper here "Fully Device-Independent Quantum Key Distribution" (Umesh Vazirani and Thomas Vidick) and unfortunately there are many things I don't understand.

1) Page 3: by the word round, what do the authors actually mean? Is it right to say it's basically how many times Alice and Bob use their own devices?

2) Page 3, Testing section: this equality aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ I was told it describes the requirement of the CHSH game. Alice input can be anything belonging to the set {0,1,2} while Bob's input can only be an element of the following set{0,1}. Their output can be 0 or 1, respectively.
The paper says "They compute the fraction of inputs in B that satisfy the CHSH condition aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ..". My understanding is: if ⊕ is exclusive OR and ∧ is logical AND then the following makes sense:  aᵢ=1 bᵢ=0    1 ⊕ 0 = 1 ∧ 1 Is that correct? If I'm right what does the following expression mean? "If this fraction is smaller than cos2 π=8 − η they abort the protocol"

Cross-posted on quantumcomputing.SE


texts: How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?


texts:
I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is.

The approach is to:

Convert the message to a number
Find the smallest equation to represent the number

The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value.

The process can be reversed by evaluating the equation, and then converting the number back into the message.

Step 1. is similar to base conversion but has the following numerical sequence...

Given an alphabet of "abc"...

Message, Value
a,       0
b,       1
c,       2
aa,      3
ab,      4
ab,      5
ba,      6
...

Value "aa" shows the difference between base conversation. In normal base conversion the value of "aa" would be 0 because "a" is the first letter of the alphabet and has a value of 0, so two of them would also be zero.

The value is really the permutation sequence number for when the alphabet is iterated over (or "bruteforced"). (Aside: Useful when distributing "bruteforce" problems.)

For step 2. I plan on using state space search to generate the equation. The goal state will be the smallest equation. The search will be performed by applying and accepting a single math operation on the "remaining" value. Initially, the "remaining" value will the original number. By the end of the search it will be reduced to zero.

Non-answer feedback is welcome as comments on the question.


texts: How to rank functions in increasing order

texts: I mean I could just start putting values in each function and arrange them according to their corresponding values. But is there a better way of doing this.


texts: Guessing the best choice to maximize returns

texts:
There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the value of the object is shared among the people. For example, If there are 2 objects and 3 people, one of the objects will be chosen by at least 2 people, thus the value of the object is divided over 2.

Each round the people make their decisions with new objects and new values, how can a person maximize their expected values accumulated from their choices in Q number of rounds, in order to win(i.e accumulated most value)? ($Q$ belongs to [1, +infinite).

Note that keeping track of other player's decisions and their accumulated values can help in future decision making.

Note: An approximation would be great as well, so far my strategy is to choose a random object at each round, I am looking for ways to maximize this strategy.


texts: How to create an LR($k$) grammar for a given language?

texts:
How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:

$$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = vu \wedge |w|_u \operatorname{mod} 2 = 0\right\}$$

($|w|_u$ denotes the number of $u$'s in $w$).

Please note that I don't want a right or left linear grammar although I KNOW that the language is regular. I am interested in the process of creating an LR($k$) grammar for an arbitrary, in general more complex language. (Feel free to ignore this example.)


texts: Bounds on "well dispersed" sparse matrices

texts:
Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is the minimum of the extent of $PMQ$ taken over all permutation matrices $P$ and $Q$. Let $f(n,k)$ be the maximum of $q(M)$ over all matrices $M$ with $k$ ones. What bounds can we give on $f(n,k)$?

Specifically, I am interested in finding whether there are any matrices $M$ with $k=O(n)$, such that $q(M)\ge (1+\epsilon)n$ for some $\epsilon>0$, i.e. $f(n,k)\ge (1+\epsilon)n$.

  Is it possible to achieve $f(n,k)\ge (1+\epsilon)n$ for $k=O(n)$?

Less formally, we have a grid that we can fill with a small number of dots, and the adversary is allowed to permute rows and columns in order to prevent the bottom corner from being filled. For example, I can have a matrix like

\begin{matrix}
\bullet&\cdot&\cdot&\cdot&\bullet\\
\cdot&\bullet&\cdot&\cdot&\bullet\\
\cdot&\cdot&\bullet&\cdot&\bullet\\
\cdot&\cdot&\cdot&\bullet&\bullet\\
\bullet&\bullet&\bullet&\bullet&\cdot\\
\end{matrix}

and the adversary can permute this to
\begin{matrix}
\cdot&\bullet&\bullet&\bullet&\bullet\\
\bullet&\cdot&\cdot&\cdot&\bullet\\
\bullet&\cdot&\cdot&\bullet&\cdot\\
\bullet&\cdot&\bullet&\cdot&\cdot\\
\bullet&\bullet&\cdot&\cdot&\cdot\\
\end{matrix}
so this matrix gets a quality of $6$. We want to distribute the dots so the quality is as large as possible.

Here are some observations:

$f(n,k)\le 2n$ trivially
$f(n,k)=2n$ only for $k=n^2$. This is because if $M$ has less than $n^2$ ones, then there is a spot containing a zero, which can be moved to the corner by a permutation.
$f(n,n)=n+1$. The identity matrix has $n$ ones, and all permutations of the identity matrix are permutation matrices. The best the adversary can do on a permutation matrix is put all the ones on the antidiagonal, which has $i+j=n+1$ for each of its ones.
$f(n,n+m^2-m)\ge n+m$: Similar to the above, where we use a $m\times m$ block of ones followed by ones on the diagonal. Permutations cannot break up the block, so the best option for the adversary is to put it on the antidiagonal, where it will extend out beyond the antidiagonal by $m$, like so:
\begin{matrix}
\cdot&\cdot&\cdot&\cdot&\bullet\\
\cdot&\cdot&\cdot&\bullet&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\end{matrix}


texts:
I'm looking for a textbook or reference material to learn about the theory of abstract data types, the ways in which they are specified (axiomatic specification vs abstract model), imperative vs functional definitions, etc.
I'm looking for a theoretical book that gives a good introduction to how they are discussed and defined in contemporary CS research.
Papers or course notes are welcome as well. Thank you.