texts:
I'm basically trying to solve 4.2

(Taken from Semantics with Applications)

As I see it, the functional F will be defined like so:

(F g)s = s if s x == 0
(F g)s = gs[x -> x -1] if s x!=0

So, the first function is

g1 s = undefined for all s

I don't think this is a fixed point, because when s x = 0 , the function would output undefined when it really should be s

Am I on the right track?

By that logic,  g2 and g3 would be fixed points since they terminate at a state where x = 0.


texts: Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

texts:
I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.

For N number of meals per day, find permutation of recipes that comes the closest to satisfying these conditions:

Sum of meal calories ~= my defined daily calorie limit
Average recipe macros* (weighted by recipe calories) ~= my desired macros (i.e. (30/40/30))

(*: Macros are the ratio of carbs/protein/fats in a meal, and are usually found in a tuple form: (CC/PP/FF))

Each recipe can be assumed to be in the form:

'name': {
   'calories': a,
   'protein': b,
   'carbs': c,
   'fats': d
}

In other words:

Inputs: n_meals, max_cals, (cc,pp,ff) # <- macros
Output: [recipe_1, recipe_2, ..., recipe_n]

I have no formal training in algorithms, so I'm not really sure where to start. The naive approach would be to take every permutation of recipes in the list and use the permutation which satisfies the criterion the closest.

This is definitely a multi-dimensional optimization problem but that's the depth of my knowledge. Perhaps something like a breadth-first search algorithm would be most appropriate?

Thanks all.


texts: Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L

texts:
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:

For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = a_3 a_6 a_9 \dots$
Then, for a language $L$, define $third(L) = \{third(w) : w ∈ L\}$.
Show that if $L$ is regular, then $third(L)$ is also regular.
(Hint: Construct an ϵ-NFA from the DFA for $L$.)

TEACHER'S SOLUTION:
If $L$ is regular, it is accepted by some DFA, say $A = (Q,Σ,δ,s_0,F)$.
We will construct an ϵ-NFA $B$ such that $L(B) = third(L(A))$.
Here, you need four copies of $A$.
Formally, $B = (Q × \{1,2,3,4\}, Σ, ρ, F × \{2,3,4\})$,
where $ρ =$
${\{(⟨p, 1⟩, ϵ, ⟨q, 2⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$
${\{(⟨p, 2⟩, ϵ, ⟨q, 3⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$
${\{(⟨p, 3⟩, a, ⟨q, 4⟩) : (p, a, q) ∈ δ\}}$ ${∪}$
${\{(⟨p, 4⟩, ϵ, ⟨p, 1⟩) : p ∈ Q\}}$.
(Do not confuse ρ and p.)
WHAT I DO UNDERSTAND:
• I understand how Cartesian products work.
WHAT I MAY OR MAY NOT UNDERSTAND:
• Are the ${(p, a, q) ∈ δ}$ parts another way of saying ${δ(p,a) = q}$?
• I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed. And, I suspect that that's the purpose of the stuff with the angle brackets.
• I suspect that the purpose of taking the Cartesian product of Q and ${\{1,2,3,4\}}$ and the purpose of taking the Cartesian product of F with ${\{2,3,4\}}$ is to have a state for each copy of A, where ${⟨p, 1⟩}$ represents the state p of the first copy of A (but is technically a state of B, not A).
• Should ${⟨s_0, 1⟩}$ be the start state of B, such that B's n-tuple is a 5-tuple, rather than a 4-tuple, and that that 5-tuple is ${B = (Q × \{1,2,3,4\}, Σ, ρ, ⟨s_0, 1⟩, F × \{2,3,4\})}$?
WHAT I DON'T UNDERSTAND:
• I don't understand what the transitions regarding the four copies (defined by B's transition relation, ρ) achieve exactly.
• Also, why does one need four copies of A? Can't one just add those additional transitions to a single copy of A?
Any input would be GREATLY appreciated!
Edit for adding new information (#1):
Thanks to all of you for responses. :)
I have a comparatively small question:
The transition relation, ρ, is also function in this case, because each state of the NFA B only has one transition to another state, per input, right?


texts: Could you explain this variant of the Preflow Push Algorithm to me?

texts:
I am having trouble to understand the FIFO-rule for the Preflow Push Algorithm. In class I learnt the  the following version of the FIFO-rule:

The active nodes are stored in a queue. Newly active nodes get enqueued, no longer active nodes get dequeued. (So far I get it.) For every active node $v$ we also keep a queue of the edges in the residual graph that are incident to $v$. The current PUSH-Operation is always done on the first allowed edge in this queue.

I do not quite get how I should understand the latter part. Suppose a node $v$ gets active and (we assume the nodes of the graph are named $1,\ldots,n$ and we traverse all nodes in lexicographic order) and $v$ is incident to $1,\ldots,n$ in that FIFO order. Then we have to take the edge incident to $1$ and the queue then has the form $[n,1,\ldots,n-1]$. Does the queue retain this form if $v$ gets active again or is it set back to $[1,\ldots,n]$?
Could you please expalain this to me?


texts: Let's assume that I have an LTL formula and I want to convert it to a Buchi automaton. For which fragment of LTL, GBA is more succinct and for which fragment BA has the same size as GBA.


texts: Is there a difference between $\lambda xy.xy$ and $\lambda x.\lambda y.xy$?

texts:
I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.

$\lambda xy.xy$
$\lambda x.\lambda y.xy$

Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same thing?

Especially this definition of pair creation made me wonder:

  pair = $\lambda xy.\lambda p.pxy$


texts: Proving the Language is not regular for $(a^n)^n$

texts:
I am trying to solve a pumping Lemma Problem where $L= \{(a^n)^n ; n\ge 0\}$
I am having a lot of trouble with the pumping lemma and understanding using it with different languages. Here is what I have so far and would appreciate any input on it.

Assume for contradiction that $L$ is a regular language. Since $L$ is infinite we can apply the pumping Lemma. Let $p$ be the critical length for $L$.

Let $w = (a^p)^p$ and length of $|w|>=p$. From the pumping lemma we can write $w = (a^p)^p = xyz$. With
$|xy| \le p$ and $|y| \ge 1$. Thus $y = a^k, 1\le k\le p$. So for $xy^iz \in L$ we can take $xy^0z = xz = (a^{p-k})^p$ which should be contained in $L$ but since it is not we have a contradiction thus the language is not regular.

Any help or recommendations is appreciated, thank you.


texts:
Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, delete and closest_pair in $O(\log n)$ time.

I know that a sorted array supports search, insert and delete in $O(\log n)$ time. So, all we need to do is maintain information about the closest pair during the insert and delete operations.

The only problem is that the closest_pair would perform in better than $O(\log n)$ time since information about the closest pair would already be available. So, I'm stuck at this point.


texts: Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete

texts:
Let $\mathrm{SpaceTMSat} = \{\langle M, w, 1^n\rangle\mid\text {DTM $M$ accepts $w$ in space }n\}$.

How do I prove that this language is PSPACE-complete?
NP contains NP-complete problems and so does PSPACE. Am I supposed to prove it the same way as I would prove an NP-complete problem?


texts: How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?

texts: I heard Google creates indexes of pages. Even then, the number of indexes goes with time. Why wouldn't this slow down the search?


texts: Boys And Girls Problem. How to prove that the algorithm is correct?

texts:
Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl.
If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 children stand next to a boy:

(G -> B G -> B G -> B -> B -> B -> B -><- B)

and 3 children stand next to a girl:

(-> G B -> G B -> G B B B B B ->)

Now, given that, there are n children standing in a circle, x of them stand next to a boy, and y of them stand next to a girl.
Where n >= 2 and 0 <= x, y <= n;
If there is a solution, we print the order of boys and girls in the format similar to: BGBGGG, where B stands for "boy" and G stands for "girl", otherwise, we print "Impossible".
Here is the pseudo-code:

sortBoysAndGirls(n, x, y) {
    if (n == 2 and x == 1 and y == 1) {
        print "BG"
        return
    }

    if (x == y or ((x - 1) + (y - 1)) != n) {
        print "Impossible"
        return
    }

    result = ""
    for (i = 0; i < n; ++i) {
        if (x > 1) {
            result = result + "B"
            --x
        }
        if (y > 1) {
            result = result + "G"
            --y
        }
    }

    print result
    return
}

Implementing and testing the algorithm (using tester/checker) above showed, that it works in concrete situations, but now i need to prove that it works generally.
Any ideas?


texts:
Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each.

Now, elements ($E_i$) arrive serially with properties such as:

E1 : Should be placed in either B or C.
E2 : Should be placed in either A or B or C.
E3 : Should be placed in either A or B.

When an element arrives, we have to place the element in one of the 4 sets, immediately i.e. we cannot wait for all elements to arrive, and then decide.

When a new element arrives:

If there exists space in one or more sets, satisfying the constraints, we place the element in the set with minimum cardinality. Ties are broken randomly.
If there is no space satisfying the constraints, the existing elements may be redistributed to accommodate the new element.
If even after redistribution, there is no space satisfying the constraints, discard the new element.

Objective
Accommodate the newly arriving elements, while having less number of redistribution.

An illustrative example depicting the problem is attached.

What strategy should i choose to achieve the objective? I need an algorithm for the redistributions that is scalable to large number of sets and more than 2 entry for each set.

In the picture, randomly I have chosen 2 possibilities, one of which yields less number of redistribution than the other. So are there any approaches other than exhaustively checking all possible combinations?


texts: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and columns are set to 0

texts:
For this question, I implemented this:

public void setZeros (int[][] matrix) {
    firstScan(matrix);
    secondScan(matrix);
}

public void firstScan(int[][] matrix) {
    int i,  j;
    for (i =0; i < matrix.length; i++) {
        for (j = 0; j < matrix[0].length; j++)
        {if (matrix[i][j] == 0) {markRowsAndColums(matrix ,i,j);
        }}}}

public void secondScan(int[][] matrix) {
    int i,  j;
    for (i =0; i < matrix.length; i++) {
        for (j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == -1)  {
            matrix[i][j]= 0;
        }}}}

public void markRowsAndColums (int[][] matrix, int i,int j) {
    for ( int x = 0; x< matrix[0].length; x++ ) {
        if(matrix[i][x] !=0) {matrix[i][x] = -1;}}
    for ( int x = 0; x< matrix.length; x++ ) {
        if(matrix[x][j] !=0) {matrix[x][j] = -1;}
    }}

My first scan aims to change all rows and columns that have zeros into -1s (but not the zeros).

My second scan aims to convert all the -1s into zeros.

Do you think it is a good solution? Does it work? And I don't know what the runtime of the algorithm is. It would be great if you could give me a hint cuz I really have no idea.


texts: How to find time complexity for functions in lazy functional languages?

texts:
So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict imperative languages, and there seems to be very little about finding time complexity in lazy functional languages.

The former resources are somewhat unsuitable for finding the time complexity of lazy functions. E.g.:

minimum = head . sort

For a good definition of sort, minimum will run in $\cal{O}(n)$ time even though head runs in $\cal{O}(1)$ time and sort can run in $\cal{O}(n * log(n))$ or $\cal{O}(n^2)$ time.

However if I wrote this function in a strict imperative language as

fun minimum(list):
    sort(list);
    return head(list);

and then tried to combine the complexities of the sort and head functions the way it is done with algorithms in strict imperative languages, then I would get that the minimum function will run in $\cal{O}(n * log(n)) + \cal{O}(1) = \cal{O}(n * log(n))$ or $\cal{O}(n^2) + \cal{O}(1) = \cal{O}(n^2)$ time.

Which is of course correct for the strict function, however it doesn't have to be very accurate for the lazy version of the same function as shown above. So using the same technique in lazy programming languages wouldn't be all that useful.

I think the difference comes in from the laziness, because it causes data to be computed only as much as they are required by the function using them. This is opposite to how it works in strict languages, where the function using the data has no control over how much the data gets evaluated by the function creating them.

This means that knowing the time complexity of fully evaluating a function, which is what one usually looks for when figuring out the time complexity of a function, isn't necessarily useful for knowing the time complexity of a function using data from this function unless said function evaluates the data fully.

So what is useful to know about one function to figure out the time complexity of another function using the resulting data from it inside a lazy functional language?

Is there a formal system that helps out with finding out the time complexity in this situation?

I know I could probably try evaluating the whole function by hand if I have source to all the functions that it uses, but I don't necessarily have that.

On similar note, if I don't have the source of a function and I only have a documentation to it, then what would the writer of said documentation need to include in the documentation for me to be able to accurately find the time complexity of a function that uses their function?

As said before, the time complexity of evaluating the function fully isn't enough. But what if they included time complexity of evaluating the first i elements of the list the function is generating? Would that be enough? If yes, then how could this be generalized to other data structures as well?


texts:
From page 29 of The algebra of programming :

  For any category C the opposite category $C^{op}$ is defined to have
  the same objects and arrows as C, but the source and target operators
  are interchanged and composition is defined by swapping arguments:

  $$ f \cdot g \text{  in  } C^{op} = g \cdot f \text{ in } C. $$

This doesn't makes sense. Suppose C is the categories of all functions, and we have $f: A \leftarrow B$ and $g: B \leftarrow C$, then $g \cdot f$ doesn't even exist. Or, suppose $f: A \leftarrow B$ and $g: B \leftarrow A$, then $f \cdot g : A \leftarrow A$, and $g \cdot f : B \leftarrow B$, this is not interchanging source and target, this is changing both!


texts: Principles of Programming Languages: Understanding Judgements

texts:
I am taking a principles of programming languages class right now and am trying to understand the following judgement form.

n' = -toNumber(v)
------------------
-v --> n'

(Sorry, I can't post pictures yet. And Stack doesn't take LaTeX.) I think it means "n' = -v implies that -v maps to n' " or something along those lines.  I guess I really just don't know what the --> means.  In math it can either mean "maps to" or "implies" and "maps to" just made more sense.


texts: Is it a good idea to determine coordinates of object on images with regression algorithms?

texts:
I am doing doing one of getting started competitions on kaggle, the one which requires you to find coordinates of different objects on images.

I know that the usual method for this is to use sliding window and predict whether some piece of image is that object. But I wonder, what if I just use values of all pixels as features and try to teach a regression algorithm how to predict the coordinates of the object on that image? What kind of regression algorithm would be best?


texts: What are the inputs to an LSTM for Slot Filling Task

texts:
I am confused on the inputs of a Long-Short Term Memory (LSTM) for the slot filling task in Spoken Language Understanding.

Before I worked on this, I implemented a language model with a Recurrent Neural Network (RNN) and then with a LSTM. The input to the RNN and LSTM language models was a one hot vector, which represented each word.

Now, when moving on to the slot filling task for a LSTM, I am having trouble what the input would be. I know that a one-hot vector representation is not enough for this task because the outputs along each time step are slot labels. I have a dictionary (in Python) that maps words to indices (which I can turn into a one hot vector), and I also have a dictionary with a labels (that are used for slot filling), which I got from the ATIS data. Here is an example:

I know I need the above two dictionaries to accomplish the slot filling task, but I cannot figure out how to use them as inputs for the LSTM? Furthermore, I have been using the basic LSTM structure, and for the language model LSTM I build, the output at each time step went through a Softmax function. Is this what will be required for slot filling too?

I am in high school and do not have anyone to contact, so any help is really appreciated. Thank you so much.


texts:
Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$
  grid. Before the game begins, the domino bones  $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$
  are placed on the grid (constituting a perfect tiling). In the next step, the domino bones are hidden, leaving only the numbers revealed. The purpose of the game is to recover the original arrangement of the domino bones.
You can play the game here: http://www.puzzle-dominosa.com/:

Rules:

  The rules are simple. You have to find the location of all the dominoes on the grid. A domino is a pair of numbers. You can only have one of each pair.

I have some polynomial algorithms that solve a relatively small part of the puzzle. I could also show that typical Dominosa grids have at least $2^{\frac{n}{2}+o\left(n\right)}$ solutions.

Is Dominosa NP-Hard?


texts: Prove that any algorithm that has sublinear time have a constant time complexity?

texts:
This exercise is taken from Goldreich's textbook of "Computational Complexity - A Conceptual Perspective", first ed., p.140.

Exercise 4.3: Referring to any reasonable model of computation and assuming that the input length is not given explicitly, prove that any algorithm that has sub-linear time complexity actually has constant time complexity?

Here is the note given by Oded:

Guideline: Consider the question of whether or not there exists an infinite set of strings S such that invoked on any input $x \in S$ the algorithm reads all of x. Note that if S is infinite then the algorithm cannot have sub-linear time complexity, and prove that if S is finite then the algorithm has constant time complexity.

For definition of sublinear time, see here.
This is how I show it: Since we strictly read less than the size of the input |x|, then it is necessarily that we read some of the input, let's say 1, 2, ..., k where k < |x|. Since k is not part of the input, therefore time complexity of this algorithm is O(1). Is my conclusion right? If not, then why?
As you notice, I didn't use the hint since I didn't know how to show if S is finite, then the algorithm has a constant time.


texts: in a graph G= (V,E), finding a clique of size |V|- d where d is some constant

texts:
Is the question above still NP? I've been stuck on this question for couple of days now... I know k-Clique problem is NP-complete generally, but the problem is k = |V|-d where d is some integer constant...My current guess is that for large |V|,
d << |V| => Finding all subsets of size k = (V choose V-d) so this question is in P.


texts: How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time?

texts:
I'm implementing a Fibonacci Heap, where the lists are stored as a circular doubly-linked lists. What I'm trying to do is given a pointer to a random node in one linked list, and a random node in another, I want to merge them together in O(1) time. I tried drawing this out, but I couldn't seem to figure out how to do this. Here is my first idea, in pseudocode:

union(Node one, Node two) {
    if other = nil
        return

    p1 = one
    p2 = one.right
    p3 = two
    p4 = two.right

    p1.right = p4
    p4.left = p1
    p2.right = p3
    p3.left = p2
}

Each Node has a left and right attribute, which stores the node to the left and right, respectively. However, this didn't work. Can anyone figure out how to merge together two linked lists?


texts: Merge Sort sentinel: What if your array contains Integer.MAX_VALUE?

texts:
I'm just getting my head round Merge Sort, and I was wondering whether the use of the sentinel value was considered good practice in the real world, or mostly an algorithmic conceit?
I get that it simplifies the comparison operations in pseudocode, where "infinity" is a valid value. With real-world arrays, though, the largest possible value for the sentinel is always a value that the array to be sorted could conceivably contain.


texts: NP-hardness of language of graphs with $\alpha(G)=n/3$

texts:
How to prove the NP-hardness of the language $\{G \mid \alpha(G) =\frac{1}{3} |V(G)|\}$?
Here $G$ is a graph, $V(G)$ is its vertex set, and $\alpha(G)$ is the independence number of $G$, which is the maximum size of an independent set.


texts: Need help classifying this problem and suggestions on how to tackle it

texts:
I've got an idea for a tool I want to make but I am not sure how to go on about trying to solve it... I was hoping if you could help me classify it and also give me some suggestions on how I could try solving it.

Background

This summer I played through the Persona 4 JRPG game, similar to Pokemon. In the game, you can collect and level up "personas". The game also features a system that allows players to combine personas through "fusion" to create other personas.

There are tools out there that calculate the various combinations of "parents" possible to create a certain persona. However, these tools only give the immediate parents, I want to create a tool that given a set of personas the player has available, shows all the fusions that need to be made to crate a persona, as cheaply as possible (there is a price involved).

Details

There are about 100 or so personas in the game and each persona belongs to a certain arcana (type).

When a player has found a certain persona, he or she can "summon" (create) it later for a certain price. These summoning costs are what makes out the price for the total creation chain.

The fusion is done by combining two or three personas. The resulting persona's arcane is a look-up depending on the parents', and the resulting persona is then the persona with lowest rank in the given arcana with a rank greater than the average of the parents.

After fusion is done, the resulting persona is added to the list of available personas which the player can create.

Details of the fusion are explained in this link: http://persona4.wikidot.com/fusiontutor

Task

Given a list of available personas, I want to return the whole "fusion-chain" while minimizing the total cost.

What makes this problem so difficult is the fact that the available personas changes depending on the order they are created. In general, it seems that it is cheaper to summon a persona than to summon its parents and fuse them. Because of this, it seems I would have to investigate every permutation possible...

Question

I would like to classify this problem, is it np-complete? np-hard? or even worse? It looks like a simple dynamic programming problem, but what do you do when the result is dependent on the order in which you solve each sub-problem?

Also, I wonder if anyone has some ideas on how this could be solved, preferably with as low total cost as possible.

Note: I don't know about suitable tags so I would welcome suggestions for that as well :)


texts: Segmenting a human body point cloud into limbs

texts:
I have a human body point cloud taken through a Kinect (v1). Now, I want to segment the point cloud into different parts, namely hands, lower arms, upper arms, torso, upper legs, lower legs, feet and head.

Here's the method I'm currently using:

I get the approximate skeleton from the point cloud using OpenNI
I take those points from the point cloud that are at a distance d from the line that is the bone (obtained from OpenNI). This distance d is currently set differently for different parts, based on observations only.

The problem with the above method is that it's not very robust. The parameter d can be different for people with different body types and also this is prone to errors since at the joints, the points within the circle of radius d will lie in both the parts.

Is there a better way of segmenting the point cloud?

Edit: This is what I get from OpenNI

The blue portion is the lower arms segmented using the above algorithm.


texts:
I was confronted with this problem in an online programming challenge and it has been bugging me since:

In the problem, you are given a list of 16-bit numbers, say
$a_0, a_1, ..., a_n$. An "XOR subsequence" is defined as the exclusive-or combination of every element in a consecutive subsequence of the list. The problem is that you must find the most commonly occurring XOR subsequence out of every possible consecutive subsequence in the list. In the event of a tie, the lowest numeric XOR value out of the most frequently occurring ones wins.

The first solution I came up with was an $O(n^2)$ solution where I compute the XOR for consecutive subsequences $a_0,...,a_i$ from $i=0$ to $i=n$, which can be done in $O(n)$, and doing the same thing starting at $a_1$, etc, and incrementing a counter in a map for every result. I know this repeats a lot of work, so I tackled the problem from a different angle and tried to define it mathematically. I defined $X_{i,j}$ to be the XOR of $a_i,...,a_j$ so that I could write the following:

$X_{i,j} =
\begin{cases}
a_i & \text{if } i = j \\
a_j \oplus X_{0, j-1} & \text{if } i = 0 \text{ and } j > 0 \\
X_{0,i-1} \oplus X_{0,j} & \text{if } 0 < i < j
\end{cases}
$

I implemented that with memoization, which I believe eliminates all redundant calculations, but using memoization turns out to be slow and use $O(n^2)$ space when attempting to calculate all $X_{i,j}$ for $0 \leq i \leq n $ and $i \leq j \leq n$, which is unacceptable.

Is there any way I can make this any faster than $O(n^2)$? Or if not, is there any efficient way to reduce the number of computations? Or am I missing some simplification to the problem that doesn't require me to compute every $X_{i,j}$? I'm sort of new to dynamic programming, so it's been hard to wrap my brain around this problem. My original solution was too slow by a factor of about 5 seconds (vs the time limit of 4 seconds for the challenge), so I believe even a constant factor reduction in time would make the solution acceptable.


texts: Given a family of hash functions in table form, how can I know whether it's universal?

texts:
I've been given the following two families of hash functions:

H

and

G

Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions $F$ is called universal if for every $x \neq y$, $\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$ ($f$ is a function in $F$).
However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?


texts: Is there a fast, "partial planarization" algorithm for non-planar graphs?

texts:
On "partial planarization" I understand an algorithm, which tries to reach an optimal, or nearly-optimal solution for non-planar graphs. For example, which minimizes the number of the crossing edges (but I can imagine some other viewpoint, too).

I think, a such algorithm could be maybe even fast (around $O(V^3)$ or maybe faster).

Is there a such algorithm?


texts: Difference between the languages accepted by two DFAs with different initial state/accepting states?

texts:
Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.

Given two DFAs $A = (Q, \Sigma, \delta, q_1, F_1)$ and $B = (Q, \Sigma, \delta, q_2, F_2)$ where the set of states, the input alphabet and the transition function of $A$ and $B$ are the same, the initial states and the final(accepting) states could be different. Let $L_1$ and $L_2$ be the languages accepted by $A$ and $B$, respectively.

There are four cases:

$q_1 = q_2$ and $F_1 = F_2$.
$q_1 \neq q_2$ and $F_1 = F_2$.
$q_1 = q_2$ and $F_1 \neq F_2$.
$q_1 \neq q_2$ and $F_1 \neq F_2$.

My question is

    What are the differences between $L_1$ and $L_2$
     in cases 2, 3 and 4?

I have a more specific question along this line,

The transition monoid of an automaton is the set of all functions on the set of states
induced by input strings. See the page for more details. The transition monoid can be regarded as a monoid acting on the set of states. See this Wiki page for more details.

In many literatures, an automaton is called strongly connected when the monoid action is transitive, i.e. there is always at least one transition (input string) from one state to another state.

    If $A$ and $B$ are strongly connected automata, what are the differences between $L_1$ and $L_2$ in cases 2, 3 and 4 above?

Any literatures discussing these issues in details?

I have searched many books and articles and found nothing helpful so far. I believe I don't have the appropriate key words yet. Thus I am seeking help. Any pointers/references will be appreciated very much.


texts: How to find middle element of doubly linked list using head and tail?

texts:
Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node and check if the reference of both is same or not. This works fine if there are odd number of elements in the list. I am not able to find when should I stop in case the number of elements in the list is even.

while(head.next != end.previous) {
    head = head.next;
    end = end.previous;
}


texts: The index of a language is the number of Myhill-Nerode classes that it has. It is also equal to the number of states in the minimal DFA for the language. What is an example of a language that has a different index from its reversal?


texts: Proving a value is the result of the execution of an algorithm

texts:
Assuming an algorithm $A$ known to both Alice and Bob.

Alice runs the algorithm and gets a result $R$.
How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random value (without having Bob run the algorithm himself)?

The goal is for Bob to perform less calculations checking Alice proof than running the algorithm itself. A probabilistic scheme for the proof is fine.

Please note that Alice does not have to prove correctness of $R$, just that she ran $A$ to obtain $R$.

The algorithm and its inputs can be modified to build the proof if necessary

Note: from the discussions below. I am happy with heuristics or techniques to obtain the proof. This is not a rhetorical question on algorithms.

Note2: @DavidRicherby suggests providing an execution trace, which seems perfectly reasonable. This leads to two sub-questions

How does Alice practically build a trace which proves to Bob with high probability that the trace is the one linked to the result ? (Bob should run less calculations checking the trace, than running the calculation himself)
Could such a mechanism be generic i.e. work with any algorithm ? For instance by confining execution inside a Virtual Machine which could record all operations.


texts: How to verify a property about a certain order of events in TCTL / UPPAAL?

texts:
I'd like to check if a certain order of events happens if another property holds true using UPPAAL and TCTL.

If A==true then eventually (B==true and eventually (C==true and eventually (D==true)))

But since "In contrast to TCTL, Uppaal does not allow nesting of path formulae." I'm not sure how to do this.

What I'v got so far is only something like:

E$\diamond$ (A && B)

E$\diamond$ (A && C)

E$\diamond$ (A && D)


texts: Determining if a TM decidable or not, with limited information

texts:
Were being asked to determine the whether this Turing Machine is decidable or not

"Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine whether $M$ will ever overwrite a symbol $a$ by a symbol $b$ in its computation on input $x$"

I'm not looking for answers, just hints on how to even approach this problem. Like, would we declare a language which is a subset of that language, and then apply reducibility?


texts: What is the asymptotic runtime of this nested loop?

texts:
I am trying to analyse the runtime of this algorithm:

for(i=1; i < n; i++){
   for(j=1; j <= i; j++){
         statement1;
   }
}

Expanding the above loop into.

First :

for(j=1; j <= 1; j++){
   statement1;          //complexity O(1)
}

Second:

for(j=1; j <=2 ; j++){
   statement1;          //complexity O(2)
}

...

n-th:

for(j=1; j <= n; j++){
   statement1;          //complexity O(n)
}

So the runtime of the loop should be

$\qquad \displaystyle O(1) + \dots + O(n) = O\Bigl(\frac{n(n+1)}{2}\Bigr) = O(n^2)$.

Can I reason like this, or what is the proper way to analyse nested for-loops?


texts: Looking for algorithms context-aware to solve a Bicycle Routing Problem

texts: I am conducting a study has the general objective to build a route recommendation system for bicycle users, able to suggest viable alternatives to dislocation in urban environments, with reference to contextual information such as: street blockades , points of origin and destination and user preferences (avoid streets with uphill, downhill, high-speed roads, etc.), that is, from these contextual information how to suggest the best options for routes that meet these requirements. Someone suggests some algorithm or a combination of Algorithms that permit the inference of these User preferecias and then calculate what the possible route options?


texts: Do FOL theorem provers accept axiom schemata?

texts:
Axiom schemata (such as ZFC) are, in a sense, infinite sets of axioms. Do the ATPs designed to work with FOL (such as Vampire) accept axiom schemata?
I looked in the Vampire "manual" briefly, but couldn't answer this question. Is this possible? How would one do it in TPTP syntax? Are problems involving axiom schemata part of the CASC FOF division?


texts: Longest common subsequence with at most one swap

texts: Is there a good algorithm for calculating the longest common subsequence where we consider two sequences identical if they can be transformed to one another with at most 1 swapping of subsequences (i.e. taking two non-overlapping subsequences of the same length and substituting them for each other)? For example ABCDEFGHIJ would be considered identical to EFGHABCDIJ but not to ABCDEHFGIJ. Or is there such an algorithm for subsequences of length one?


texts: How can I prove this language is not CFL?

texts: I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m - is prime \}$ is not CFL, by taking a random length for $vx$ ($uvwxy$) and prove that the length of the whole word is not prime (I manage to prove that this length is product of two factors). But with this problem I can't do this because of that $n$. At the end it results a non prime number (this product), but I have to decrease the length of $b$'s so I know nothing about that final number. Is there another method to prove that this language is not CFL or am I wrong somewhere?


texts: Bounded Quadratic Congruence Problem Variant (for some specific Residue)

texts:
Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x<L$ such that $x^2≡ a(mod\ b)$?

The above problem is NPComplete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Is there some specific value of $a$ (say $a_0$) such that, if we limit the original problem (the residue) to only $a_0$, the problem ceases to be NPComplete (and much easily solvable than the generic case) ?

My guess is for any/each specific $a_0$ the problem still remains NPComplete but I am not certain. Anyone please ?


texts: How to use Latin hypercube sampling with fixed points?

texts:
I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points.

I thought about taking the min distance between the points, and if I have an already evaluated point that is near on LHS point, I remove the LHS to minimize the number of evaluations.
Sadly this is not how LHS works, and the results are not very good.


texts: How many range are completely inside a given range

texts:
I have a list of ranges ai , bi. And I have many queries in the form of a range c, d, which asks how many ranges ( ai, bi ) are completely inside c, d.

c <= ai & bi  <= d

There are so many of these queries. So I want to know if there is an algorithm that answer each query in a time complexity that is better than O(n).

My first attempt was to use two sorted list. One with respect to the end point of ranges and the other with respect to the start point of ranges. This way I can find how many ranges start after c, and how many ranges end before d. But I couldn't find a way to calculate their union. So this attempt was unsuccessful.

My second idea was to use Interval Tree. Interval Tree can help you find whether any ranges overlap with a certain range. I couldn't come up with a modification so that it gives me what I want instead of just overlaps. My best attempt had time complexity of O(n) for each query. For example if the ranges were are all equal my query would take O(n) but this wasn't the only example and there were a lot of other cases that the result of each query would take O(n).

So now I am wondering whether there is a data structure or an algorithm that helps me do these queries in sub-linear time?


texts: Solving complicated recurrence relation (rectangle packing)

texts:
I have written an algorithm for rectangle packing where I have the following recurrence relation for the running time:
$$
T(x,y,z)=\begin{cases}
    O(1)&\text{, if x = 0}\\
    \sum^{z-1}_{i=0}\bigl(x\cdot T(x-1,y+1,z+1-i)\bigr)+x\cdot y\cdot z&\text{, if x > 0}\\
\end{cases}
$$

You however always start with $T(n, 0, 1)$ for an input of size $n$.

I am now trying to get an asymptotic running time in terms of $n$. I tried just filling in the recurrence until you see a pattern but I could not find a pattern.


texts: Type-system combining type-states and typed effects?

texts: Has anyone succeeded in implementing or designing a type-system that combines both type-state (linear types) and effect types (e.g. Koka)?


texts: Intuitive description for training of LSTM (with forget gate/peephole)?

texts:
I am a CS undergraduate (but I don't know much about AI though, did not take any courses on it, and definitely nothing about NN until recently) who is about to do a school project in AI, so I pick a topics regarding grammar induction (of context-free language and perhaps some subset of context-sensitive language) using reinforcement learning on a neural network. I started to study previous successful approach first to see if they can be tweaked, and now I am trying to understand the approach using supervised learning with Long Short Term Memory.
I am reading "Learning to Forget: Continual Prediction with LSTM". I am also reading the paper on peephole too, but it seems even more complicated and I'm just trying something simpler first. I think I get correctly how the memory cell and the network topology work. What I do not get right now is the training algorithm. So I have some questions to ask:

How exactly does different input get distinguished? Apparently the network is not reset after each input, and there is no special symbol to delimit different input. Does the network just receive a continuous stream of strings without any clues on where the input end and the next one begin?
What is the time lag between the input and the corresponding target output? Certainly some amount of time lag are required, and thus the network can never be trained to get a target output from an input that it have not have enough time to process. If it was not Reber grammar that was used, but something more complicated that could potentially required a lot more information to be stored and retrieved, the amount of time need to access the information might varied depending on the input, something that probably cannot be predicted while we decide on the time lag to do training.
Is there a more intuitive explanation of the training algorithm? I find it difficult to figure out what is going on behind all the complicated formulas, and I would need to understand it because I need to tweak it into a reinforced learning algorithm later.
Also, the paper did not mention anything regarding noisy training data. I have read somewhere else that the network can handle very well noisy testing data. Do you know if LSTM can handle situation where the training data have some chances of being corrupted/ridden with superfluous information?


texts: How are logical addresses of instruction operands mapped to physical addresses?

texts:
Is address translation for all operands in single instruction done only once and then are all operands fetched continuously?

For example, consider any dummy instruction INSTR with two operatnds OP1 and OP2:

INSTR OP1, OP2

How does an operating system map logical addresses of these operands to their physical addresses? Is this address translation done only once for each instruction and then are all operands stored in consecutive memory locations? Or is address translation done separately for each operand and hence page tables are referenced for each operand separately?


texts: What are networking technologies to distribute the file faster with storing on more replicas?

texts:
Question: Suppose you launch a job on 10,000 machines in your own data centre. The job is slow to start because all the machines are trying to load the same large executable ﬁle. Name two networking technologies you could use to distribute the ﬁle faster, in addition to storing it on more replicas. Explain why each is appropriate.

I think one option would be peer-to-peer technology (bitTorrent). Second option can be IP Multitasking, but it does not replicas files and store in other nodes. What could be other option for this question?


texts: Differential Privacy with only positive noise

texts:
The Laplace mechanism is a standard way of making the output of a function $f$ differentially private.
More concretely, let $\Delta_f$ be the sensitivity of $f$, i.e. the maximum value by which the output of $f$ can change, if the input database is changed by one row.
On input database $x$, the $\epsilon$-private Laplace mechanism outputs $x + R$, where $R$ is sampled from the $Lap(1/\epsilon)$ distribution, which is scaled by $1/\epsilon$.
Since the distribution is symmetrically distributed around $0$, it can regularly happen that the added noise $R$ is negative and thus the reported value $x + R < x$.
Question:
Are there mechanisms that only adds positive noise, i.e. that never produces an output that is smaller than the real output? Importantly, I'm interested in mechanisms that do not know a lower bound on the output range of $x$ (this exclude simple truncation approaches like the ones used for histograms, which can be truncated at $0$).


texts: How to write operational semantics rule for havoc x?

texts:
If I want to extend a new language by adding a new command havoc x, which
updates the variable x with a non-deterministic value, how to write operational semantics rule for havoc x?
I'm confused about generate a non-deterministic value.
If I write like this:
$$\frac{n = [e]_ {intexp}\sigma}{(\mathrm{havoc}\ x,\sigma)\rightarrow(x:=x+n,\sigma)}$$
is it make sense?


texts: Formal Class of Languages Describable by .NET Regular Expressions

texts:
This is sort of a computer science question and sort of a programming question.  What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well known class)?  For instance formal regular expressions describe the class of regular languages but .NET regular expressions (as with most modern regular expression engines) are more powerful than formal regular expressions and therefore describe a larger class of languages.

This is basically the same question as this Which languages do Perl-compatible regular expressions recognize? but for .NET regular expressions instead of perl regular expressions.   However as far as I can tell, this question was never answered completely either.


texts:
I have a large number of equivalences which look like:
$(a \leq 0.54 \wedge b \geq 0.12) \vee (c \gt 0.98)$ $\Leftrightarrow$ $(x \leq 0.25) \vee (x \gt 0.91 \wedge y \geq 0.01)$
This is just an example. In general, formulae on either left or right side of the equivalence  could be anything that takes the form of a disjunctive normal form (DNF) clause, the numbers could be any real numbers with a fixed precision, and the inequality signs could be $\leq$, $\lt$, $\geq$, or $\gt$.
What is important is that the possible variables on the left side of all the formulae (here $\{a, b, c\}$) form a set that is distinct from the possible variables on the right side of all the formulae (here $\{x, y, z\}$). There could be any fixed number of variables on either side: doesn't need to be 3 variables, and doesn't need to be an equal number on either side.
I also have some implications of the form:
$(a \leq 0.32 \wedge b \geq 0.62)$ $\Rightarrow$ $(c \gt 0.00)$
Here both left and right sides are just conjunctions of inequalities, but what is important is that the set of variables on both left and right sides, i.e. $\{a, b, c\}$ here, is the same as the set of variables on only the left side of the previous kind of the formula (i.e. the equivalences).
My question is: what kind of automated reasoner would I need to find the logical consequences of a set of such formulae? I am just looking for a concrete identification of the general class of problems this belongs to, and any out-of-the-box reasoners which may be available. Perhaps this is an SMT problem?


texts: Are Elementary Cellular Automata structures considered to be fractals?

texts:
I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.

But, what about the other rules from Elementary CA? Are they also considered to be fractals?

Is there a definition relating Elementary Cellular Automata and fractals?


texts: Restricting capabilities of admin role in database schema

texts:
Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an assignment in a course and teacher or tutor can provide the grade for it.

Now while implementing is it good idea to not allow admin of a database to not to change the grade of students for an assignment? I got this suggestion that as admin is superuser (user with all capabilities) he should be able to change the grade. So what should I do?  and why?


texts: How fast we can run 128-bit LCG generator?

texts:
Let's consider some 128-bit LCG generator mod $2^{128}$, with some random 128-bit multiplier and increment. How fast we can run it using the same tricks like in AES:
https://crypto.stackexchange.com/questions/44927/how-long-does-a-good-aes-encryption-take
They use there some hardware instruction/hardware acceleration and it is absurdly fast. Can we do the same thing with LCG? If we run pure LCG in C it could be several dozen of GB/s. But can we do it faster in some easy way?


texts: Lazy Stochastic Gradient Descent: Multiplicative vs Additive

texts:
I am reading Bob Carpenter's note at http://lingpipe.files.wordpress.com/2008/04/lazysgdregression.pdf and William Cohen's note at http://www.cs.cmu.edu/~wcohen/10-605/notes/sgd-notes.pdf.

They described the same technique to lazily decay the regularization component of the weight vector (algorithm 2 in Carpenter's). However, I noticed a small difference in their approaches and wondered if this details mattered.

In Carpenter's, the regularization component is updated following $w_i \leftarrow w_i + \eta\frac{u_i - q}{n}\nabla \text{Err}_R$. The vector $\mathbf{u}$ stores the value of $q$ when $u_i$ was last updated. Initially, $\mathbf{u} \leftarrow \mathbf{0}$ and $q=0$. The counter $q$ is incremented after the weight vector has been updated for a particular training sample.

In Cohen's, the regularization component is updated following $w_i \leftarrow w_i \times (1-2\lambda\mu)^{(k-u_i)}$ (by the way, they have different notations for the same thing, both $\lambda$ and $\eta$ refer to the learning rate). The counter $k$ is the same as $q$ in Carpenter's note and incremented before any update to the weight vector. And $\mu$ is the regularization factor.

I have two questions:

Why is Carpenter's adding the regularization component and Cohen's multiplying?
When the first training sample comes in, Carpenter's version essentially ignores the regularization because $u_i - q = 0$. However, Cohen's version does decay the current weight value by a factor of $1-2\lambda\mu$. Does this make any difference?


texts:
I have a single output variable $y$ and a number of inputs $x_1$, $x_2$, etc. These are time series. Each $x_i$ explains the changes in $y$ in specific circumstances, and the goal is to have a linear model that looks like $y=b_1x_1+b_2x_2+...$ The point is that each $x_i$ must be sampled on different clock $c_i$. Imagine that $y$ is continuous, but each $x_i$ is somewhat discrete, most of the time is 0, an occasionally it has an  impulse, i.e. 'ticks'. Then, it decays quickly back to steady state of 0. We want to sample $x_i$ only then, when it "jumps", and decide the influence of these impulses of separate $x_i$s individually.

My approach is to take one sampling method $s_1$, sample $y$ and $x1$ on it, specific to $x_1$. Do the regression $y$ on $x_1$. Then, take the error $y-b_1x_1$, sample the error on another sampler $s2$, and regress this on $x_2$.

I can decide to sample $x$s and $y$ whenever I want, I can examine their value at any point in time, and decide whether to sample based on that. Most of time the $x$s will be 0, so I will choose to sample $x_i$ when it's actually trying to tell me something about $y$.

What's a good approach to solve this problem? Is there a regression form specific to this sort of situations?

Due to practical constraints, I want my model to include all $x$s at the same time, rather than switch between different models on the fly.


texts: Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

texts:
Let me define first Halting problem $(\mathsf{HP\text{}})$.
Given :  $(M , x)$,  $M$ is a turing machine and $x$ is a input binary string to turing machine $M$.
Decide  : Does $M$ halt on string $x$?
I tried to reduce $\mathsf{SAT\text{}}$ instance to $\mathsf{HP\text{}}$ in polynomial time. Let $\phi$ be a instance of $\mathsf{SAT\text{}}$ and define a map $\mathsf{T\text{}} \colon \mathbb \phi \to\mathbb M$. If $\phi$ is satisfiable (means true) then turing machine $M$ will halt on string $x$ and if  $\phi$ is not satisfiable (means false) then turing machine $M$ will not halt on string $x$.
I don't know whether the map $\mathsf{T\text{}}$ right or wrong. So my question is how to define a map and to compute this map in polynomial time?


texts: Algorithm notation between two functions

texts:
I have two functions,
$$ f = n^{1.6} $$
$$ g = n^{1.5} $$

I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is  $ f = \omega(g) $.
Can anyone explain why it is $ f = \omega(g) $ ?
Thanks in advance!


texts: What does the R superscript notation mean in regular/formal languages?

texts:
What does the capital R superscript notation mean in regular languages?  I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means.  For example in this syntax:

$L = \{ww^R\mid w \in \Sigma^{\ast} \}$


texts: Enumerate the terms resulting from decomposing a number by repeated divisions by 2

texts:
Consider a natural number $n>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = 4 + 5 = 2 + 2 + 2 + 3 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2$.

There will be $2^{\lfloor \log_2 n\rfloor}$ terms because the decomposition forms a complete binary tree of height $\lfloor \log_2 n\rfloor$.

I am looking for an iterative form of this recursive process. The enumeration $a_0 = 0, a_{i+1} = \left\lfloor \frac {(i+1) \cdot n} {2^{\lfloor \log_2 n\rfloor}} \right\rfloor - a_i$ comes close because it does satisfy the following conditions: (a) each term is 1 or 2; (b) the sum of the first $2^{\lfloor \log_2 n\rfloor}$ terms is $n$. But the elements are not identical to the recursive decomposition form.

Any help would be welcome. Thanks!


texts: Proof that dead code cannot be detected by compilers

texts:
I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter, but it has me stumped so I might use it as an example instead.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

In the program above, it's obvious that the print statement will never execute because of the return. Compilers sometimes give warnings or errors about dead code. For example, the above code will not compile in Java. The javac compiler, however, will not detect all instances of dead code in every program. How would I prove that no compiler can do so?


texts: In NLP, tokens not seen in training sample, but you know or don't know what they are

texts:
In NLP, do you distinguish tokens that you don't observe in a training sample and still expect that they may occur in a test sample, between

those you know what they are, and
those you don't know what they are, and how many of them

If yes, how do you treat them differently to estimate the probabilities in N-grams?


texts: Find maximal clique consisting of at least half of the vertices

texts:
Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority of the vertices will belong to this clique. This clique may or may not be maximal; however, given these assumptions it will definitely be a subgraph of the maximum clique of $G$.
My goal is to find the most efficient algorithm to find the maximum clique of the graph. If the maximum clique is not unique, finding one of them is fine.
In general, $G$ won't be planar or perfect graph and to the best of my knowledge there is no exponential or linear-time algorithm to solve this problem.
I thought that, one way is to do an exhaustive search of all $n\choose c$ induced subgraphs until I find a clique $C$. Then, one can keep adding vertices to $C$ such that they connect to all vertices currently in $C$ until this clique cannot be enlarged anymore. Then, $C$ will be one maximum clique.
Assuming that $n$ is not too large, maybe $n < 50$, do you think that this is a reasonable method given that $n\choose c$ is large? Is there a more efficient algorithm?
One small optimization is to exclude all vertices with degree $< c-1$ from consideration.


texts: Given a sufficiently powerful computer and model, can dice rolls be predicted?

texts:
I guess that this is a chaos, randomness and modelling question.  Can it be conceived that a sufficiently powerful (perhaps quantum) computer might be able to accurately predict the scores on a physical die tossed from a cup?

I understand that dice land the way they do because of highly complex and chaotic interactions between the die and whatever it hits.  There is a concept of total physical modelling (that I don't know the technical term for) that aims to model a real item on an atomic level. This would require great computational power and storage.

Is such modelling possible, or are there fundamental (perhaps quantum) nuances that will always prevent this? They say the weather is chaotic and unpredictable, yet the Met Office now says that today's three day forecasts are as accurate as yesteryear's daily forecasts. Advances seem to be possible...


texts:
I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function () = ^2 +  log2() + log2(). Show your working.

My answer is O(n^2) because it's the term with the highest degree. However, I'm not really sure how to show it. Am I right by saying that it has to be proven like this -> f(n) is an element of O(n^2). So far, I've only done questions like n^2 + 2n + 1 and I have to find c and k values. I'm not quite sure how to do this one. Can anyone help me out, please?

Thanks


texts: Partition points in a plane with a straigth line

texts:
Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned.

Is there an algorithm which, when given a ratio a/b, divides the plane with a straight line, so that the values of the points are distributed as close as possible to the given ratio?

Points may be on the dividing line, then the are counted to the 'left/upper' partition.


texts: Proof of value discovery in complete graphs

texts:
I have an assignment

There are n > 2 finite processors, two registers for each processor.
Register s_i is not readable by the processor p_i but any other processor can read it.
Register r_i is readable and writable by the processor p_i and any other processor can read it.

I have to solve the problem to let p_i discover the secret s_i value by reading r_i value. I don't have to (probably) come up with something super-scientific a somewhat simple proof will do just fine. I've been reading through various publications (leader election, complete graphs, uniform, etc) but wasn't able to find a point to start from.


texts: Understanding kQBF: changing order of quantification?

texts:
2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z)$ is valid. But what I can't understand is following:

Can't we change order of quantification? E.g. isn't following true $\exists X~\forall Y:\varphi(X,Y) = \forall Y~\exists X:\varphi(X,Y)$?
If we can, what prevents us from doing this in the second case and reducing 3QBF to 2QBF? E.g. $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z) = \exists \{X, Z\}~\forall Y:\varphi(X,Y,Z)$.

The main idea is to reduce the number of alternations to one.

What I thought:

Let we have a formula $\forall x_1~\exists y_1...\forall x_k~\exists y_k:\varphi(x_1,y_1...x_k,y_k)$. Then we can construct a truth-table (theoretically) where columns will be sorted this way:

x_1 x_2 ... x_k y_1 ... y_k ф
  0   0 ...   0   0 ...   0 _
  0   0 ...   0   0 ...   1 _
  .   . ...   .   . ...   . .
  .   . ...   .   . ...   . .
  1   1 ...   1   1 ...   1 _

Then we can divide table (no row/column moving) in $2^k$ parts each containing $2^k$ rows. If each of that part has satisfiying assignment, formula is valid. But that means that there is no difference at all in which order we should assign variables, since truth-table of formula is independent on the quantifiers.

In other words following must be true: $\forall x_1~\exists y_1...\forall x_k~\exists y_k:\varphi(x_1,y_1...x_k,y_k) = \forall x_1~\forall x_2...\forall x_k~\exists y_1...\exists y_k:\varphi(x_1,y_1...x_k,y_k)$

It seems that we can change order of quantification in first order logic. Compare following sentences:

There exists a village such that all villagers have shovels. Here we have two alternations ($\exists X~\forall Y~\exists Z$).
Every villager has a shovel in some village. This is logically equivalent, but has only one alternation ($\forall Y~\exists Z~\exists X$).

There are 4 another ways to move quantifiers and all of them will produce equal statements. Yet I do not have any reasons to think we can't change order of quantification in logic.

Ability to change order of quantification $\Leftrightarrow \mathsf{NP = PSPACE}$. This problem is open for decades and logic rules I used are not something really new. So, this is strange... like I am missing something.


texts: Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)

texts:
I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used to enumerate all $n \choose 2$ ways to choose $2$ values from a total of $\left|V\right|$ possible values.
For example:

Here, $V = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$ and $E = \left\{ (0,1),(0,2),\cdots,(5,6) \right\}$ and creating the initial graph is of the order $O(n^2)$. $E$ readily contains all possible pairs of numbers chosen from the list.
I was wondering if the same strategy could be used to enumerate any $n \choose k$ where $0 \leq k \leq n$, or if there are more efficient algorithms for this purpose.


texts:
For a given input $N$, how many times does the enclosed statement executes?

  for $i$ in $1\ldots N$ loop
  $\quad$for $j$ in $1\ldots i$ loop
  $\quad$$\quad$for $k$ in $i\ldots j$ loop
  $\quad$$\quad$$\quad$$sum = sum + i$ ;
  $\quad$$\quad$end loop;
  $\quad$end loop;
  end loop;

Can anyone figure out an easy way or a formula to do this in general. Please explain.


texts: The Law of Excluded Miracle in the language of guarded commands

texts:
The definition of weakest precondition is familiar (let me use Isabelle's syntax here):

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

the weakest precondition ensuring Q when executing a command in an initial state s is given by the formula in the RHS.

Now, Dijkstra, for instance in, "Nondeterminacy and Formal Derivation of Programs" talks about the law of the excluded middle:

definition "F ≡ λ t. False"

lemma "wp c F = F" unfolding wp_def F_def by simp

according to this article the meaning of this proposition would be:

  started in a given state, a program execution must either terminate or
  loop forever

However, I don't see how this proposition states this fact. Unrolling the definitions I get:

∃t. (c,s) ⇒ t ∧ (λ t. False) t = ∃t. (c,s) ⇒ t ∧ False = False

seen as a function in s, obviously this LHS matches the RHS. However, I don't see how this tells that the program terminates or loops.
Could you explain what is happening here?


texts:
Suppose that we have a max heap and that it contains duplicate values .Is it always true that nodes with same value are adjacent(neighbors)?I think it is true because if there was any other node being intercepted between them then this would break the max heap property as it would be out of order(with respect to value) with at least one of the two nodes.
Is this correct?


texts: Formal name of the product of product type

texts:
What is the formal name in type theory of the operation that creates a "matrix of types" from product types (such as std::tuple in C++)?

For example if we consider std::tuple<int, float, char> t1  and std::tuple<std::string, double> t2 (in C++, but the same question remains for any product type in any language), what would the name of the operation that would construct the following matrix of product types:

int, std::string
int, double
float, std::string
float, double
char, std::string
char, double


texts: A recursive language minus a recursively enumerable language results in a recursive language?

texts:
I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question.

Aren't all recursive languages also recursively enumerable? Does this mean the answer to the question is that a recursive language minus a recursively enumerable language results in a recursively enumerable language, but more specifically, a recursive language?


texts: Finding weight/value of each person on a team

texts:
If I have a team, with between $n_1$ and $n_2$ people per team, with results of team's head to head matchups, how would I be able to estimate each person's value?

Example data (I drew this up quickly, the actual one is many lines longer):

| Home   | Away   | Home Score | Away Score | Home Members  | Away Members     |
| ------ | ------ | ---------- | ---------- | ------------- | ---------------- |
| Team 1 | Team 2 | 4          | 2          | John, Joe     | Mary, James      |
| Team 1 | Team 3 | 3          | 2          | Joe, Patricia | Mark, Paul, Ross |
| Team 2 | Team 5 | 1          | 2          | Mary, Robert  | Steve, Lisa      |
| Team 4 | Team 3 | 4          | 3          | Ashley        | Mark, Matt       |
| Team 4 | Team 5 | 2          | 3          | Donna, Emily  | Anne, Lisa       |

For the example data, I want to be able to say something like John is the best with a individual score of $s_1$ and Mary is right behind him with a individual score of $s_2$ and James is the worst with a score of $s_n$.

We define $s_1 \geq s_2 \geq \ldots \geq s_n$ (although it is almost guaranteed that $s_1 > s_n$). We should be able to say that a team of John and Mary will beat any other team of 2. We should also be able to say that if we replace any Person1 with Person2 on TeamX, TeamX will do better if $s_{\textrm{Person1}} < s_{\textrm{Person2}}$, worse if $s_{\textrm{Person1}} > s_{\textrm{Person2}}$, and equally as well if $s_{\textrm{Person1}} = s_{\textrm{Person2}}$.

This means that we cannot have one person "carried" by their team. For example, we cannot give Joe an unreasonably high $s_{\textrm{Joe}}$ just because he was on a team with John who scores very well. This is the problem with most simplistic algorithms (such as ELO). Going into a little more detail as to why this is a problem, let us take ELO as an example. Let us say that John and Patricia are both strong players. Even if Joe is a bad player, he would have a high score by ELO. However, the ideal system should somehow differentiate good players from players on good teams. This is the crux of the problem.

This seems fairly trivial, but I can't seem to wrap my head around how to do it. Any method I create seems to have circular reasoning, as if I update one person's value than it means that everyone on their teams falls (the team is only so good, so each person's score on the same team is necessarily zero sum), which then comes back to update the original person's value, which causes updates to everyone else, and so on.


texts: Is there any algorithmic way to decide the equivalence classes in the nerode relation?

texts:
Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$

The Nerode relation $R_L$ says

$xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$

By looking at the language : I can conclude that the equivalence classes should be something like

$[\epsilon]=\{x|x$ doesnt end with $0\}$

$[0]=\{x|x$ ends with $0$ but not with $00\}$

$[00]=\{x|x$ ends with $00\}$

My question is : Is there any smart way to find the equivalence classes of any Language ? Can we do this algorithmically?


texts: Is halting problem computable for particular inputs/assumptions

texts:
From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a paradox when giving P as an input to the same P, having: P(P), trying to decide if P halts or not using P itself.

So my question is: is halting problem computable by program P for all other programs used as input but P itself? In other words: is halting problem not computable only in this special case or the proof is more general and I'm missing something?


texts:
You have to sort a given array (assuming nothing more than the elements are totally ordered) which is write once read many (WORM) in constant space i.e using a constant number of variables.

So, my naive approach was to fix the position of one element at a time. But in what order? If I do it first to last then the information of the element of the index where I placed the first element is lost. So, if I start with the first element, then try to fix the element where the first element was placed, I will eventually run into problem because I'll have to remember the relative order of the current element and the elements sorted till now.

It seems doable but I can't really figure it out. For now, I don't care about running time.


texts: Minimize Burst time left in CPU Scheduling in a fixed interval of time

texts:
I have $P$ different processes given along with their respective Burst time and arrival time. The time quantum is $1$ sec i.e. each process can only run for $1$ sec. There's a total time $F$ given for which computer will be available to perform these processes. Also for each process $P_i$ there exists a respective cost/sec for not performing it. There's no penalty for the waiting time. Penalty is on the basis of how much percaentage of burst time was left. Preemption is allowed.

For Eg- If $P=3$,$F=10$. $P_1$ has burst time of $9$ sec and penalty of $10/sec$ for $P_1$
Suppose the Gantt Chart comes out to be $|P_1P_2P_3P_1P_2P_2P_1P_1P_2P_1|$

Since $P_1$ was allowed to run for only $5$ sec till the end of all processes so total penalty will be $(9-5)*10= 40$ .

I have to schedule the process in so as to minimize the sum of penalty for all processes.

If priority was given instead of penalty for no-operation, I would simply select the process first on basis of arrival time and then on the basis of priority and then preempt the process like Preemptive Priority scheduling.

I tried it by using greedy approach. First I sort the jobs on basis of Arrival time and then if clash occurs then on the basis on cost so as to minimize the sum of total cost incurred. I choose the job with min Arrival time and maximum Cost.

Is there any more optimal and efficient way to minimize the total cost ?


texts: How to create model for a powerful language whose programs are guaranteed to terminate?

texts:
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang issue where a rule of the form .*ab.*cd doubles the state count of the DFA.

The solution for the "big bang" problem is to create a program-augmented-DFA like this:

.*ab
{
  var=1;
}
.*cd
{
  if (var)
  {
    raise();
  }
}

Now, a problem with programming languages in general is that programs written in nontrivial languages may end up in infinite loop or in infinite recursion. Thus, I'm planning to implement a bytecode where backwards jumps are strictly forbidden but forwards jumps are allowed. The bytecode would contain the following opcodes:

EXIT, RAISE
PUSH_BYTE, PUSH_WORD, PUSH_DWORD, PUSH_QWORD
EQ, NE, LT, GT, LE, GE for equality and inequality
LOGICAL_AND, LOGICAL_NOT, LOGICAL_OR, BITWISE_AND, BITWISE_OR, BITWISE_XOR, BITWISE_NOT
SHL, SHR
ADD, SUB, MUL, DIV, MOD, UNARY_MINUS
JMP_FWD, IF_FALSE_JUMP_FWD for nonconditional and conditional jumps (only forwards)
NOP for padding
SET_VAR for setting a variable in the variable structure
PUSH_VAR for pushing a variable in the variable structure into stack
POP and POP_MANY for popping variables from the stack
perhaps some other opcodes like for ++, --, += operators etc.

The additional data structures accessed by programs are the variable structure (permanent) and stack (nonpermanent). Nonnegative variables (0, 1, 2, 3, ...) are in the variable structure and negative variables (-1, -2, -3, -4, ...) refer to the stack. So, in the example .*ab / .*cd program, var would be in the variable structure as it's permanent.

I have already verified that arbitrary logical expressions and complex if-else structures can be implemented in this bytecode.

Is there some kind of formal model for bytecodes whose microprograms always are guaranteed to terminate?

Note function calls are missing. Would the language become more powerful if I allowed function calls forwards, but never function calls backwards (thus making recursion impossible)? If the program can manipulate the stack, I assume a secondary stack for just instruction pointer return locations would be needed. Would such a secondary stack that cannot be manipulated allow supporting function calls in a language whose programs are guaranteed to terminate?

At least without function calls I know that there is an upper bound for the stack size: if one instruction can push at most one item into the stack, if there are N instructions, an upper bound for the stack size is N. Would the upper bound change if function calls were supported?

Also, without function calls, a program of N instructions takes at most N cycles. Would this change if function calls were supported? For example, would it be possible to have a program with N instructions that takes $2^N$ cycles to execute?

As practical example of a similar language, my online search found this that may be applicable: https://en.wikipedia.org/wiki/Sieve_(mail_filtering_language)


texts:
We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also constructible enumerable.

To show this do we have to construct a Turing machine for the union and one for the cartesian product?


texts: Interleaving first and second half of an array of even length in place

texts:
If A is an array with the following elements:
$$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$

How to shuffle A to form:
$$ a_1,b_1,a_2,b_2,...,a_n,b_n $$

with minimal swaps and using no additional space?

I read this answer and wrote the following code:

def shuffle(a,left,right):
if right - left>=4:
    half = (right - left)/2
    for i in xrange(half/2):
        tmp = a[left + half + i]
        a[left + half+i] = a[left + half/2 + i]
        a[left + half/2 + i] = tmp
    shuffle(a,left,left + (right - left)/2)
    shuffle(a,left + (right - left)/2, right)

a = ['a1','a2','a3','a4',
     'b1','b2','b3','b4']
shuffle(a,0,len(a))

This gives an algorithm with O(nLog(n)) swaps. But I realized that this works only when n = 2k for some integer k. Is there a minor tweak that one could make to get the same complexity for arbitrary n?


texts: How to match two sets of points based on the closeset distance?

texts:
I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in K$ and for all $j\in N$. The entry of the matrix $d_{ij}$ can be viewed as the Euclidean distance between triangle $i$ and circle $j$.

I would like to assign the triangles to the circles with the constraint that each assigned point is assigned to its closest neighbor. Also, the assignment must be one-to-one. For example, let

$$
\mathbf{D}=\begin{pmatrix}
1 & 1 & 5\\
2 & 3 & 1\\
5 & 8 & 6
\end{pmatrix}.
$$
Now:

triangle 1 would like to be assigned to circle 1 or 2 and then 3 (we have a tie);
triangle 2 would like to be assigned to circle 3 then 1 and then 2;
triangle 3 would like to be assigned to circle 1 then 3 and then 2;

How can I solve this problem?

I thought of creating a list of preferences based on $\mathbf{D}$ like in the example:

List of preference for triangle 1: 1, 2, 3
List of preference for triangle 2: 3, 1, 2
List of preference for triangle 3: 1, 3, 2

But how can I continue on solving this?


texts: Relations between statements involving universal quantifier, conditional and biconditional

texts:
If we consider two predicates:

$b(x)$: x is a boy

$c(x)$: x is clever

Then, there are four statements involving $∀, b(x), c(x), →$ and  $↔$ . These are below along with my interpretation of their meaning. Correct me if I am wrong in any of these interpretations.

(a) $∀x(b(x)→c(x))$ - All boys are clever

(b) $∀x(b(x))→∀x(c(x))$ - If all are boys, then all are clever

(c) $∀x(b(x)↔c(x))$ - All boys are clever & all those who are clever are boys

(d) $∀x(b(x))↔∀x(c(x))$ - If all are boys, then all are clever & if all are clever then all are boys

I am trying to determine all conditional $(→,↛)$ / bi-conditional $(↔)$ relations between each two of above four. Between any two of these, if there is $↔$, then there is only one relation. However, if there is conditional relation in one direction, then conditional relation in other direction will be invalid. That is there can be $(→,↛)$. So at max there will be $4C_2\times 2=12$ such relations.

Now to understand these relations, I prepared below table. I considered that there are only two person in the universe $x_1,x_2$. $\{(b,c),(¬b,¬c)\}$ means $x_1$ is boy and is clever and $x_2$ is not a boy and is not clever.
The truth values (in table) in boldface (all other than vi, viii and xiv) are one which I feel are correct, though I am not sure. The non bold-faced truth values (vi, viii and xiv) are ones which I am unsure. So, I am more likely make mistake with them.

Based on the truth values in above table, I prepared following relations:

Q. Are relations 1 to 12 correct?

Q. Also is there some fault in the example predicates $b(x)$ and $c(x)$ themselves?

Actually, I must doing similar for existential quantifier. But afterwards. But am I correct with all this thinking or am just over thinking? Or am severly screwed with my logics?


texts: Lower Bounds for Size of Independent Set in a Graph?

texts:
I recently learnt that for any instance of a k-SAT problem with $m$ clauses and $n$ literals , we have an assignment of literals such that at least $m(1 - 2^{-k})$ clauses are satisfied.

I was wondering if we can we show a (non trivial) lower bound of the kind that any graph $G = (V,E)$ has an independent set of size $S$ where $S$ is some function in the number of vertices and edges or the like?

Since in the optimisation version we try to find a maximum independent subset, the tighter the lower bound, the better. Hence I was wondering if there is such a lower bound exists, how tight can we make it?


texts:
Say I have the following memory scheme:

  Data bus: 8 bit

  Main Memory Store: 256 Byte

  Cache Store : 32 Byte

  Block Size : 4 Byte

How would I go about listing the assigned bits for tag,offset and block number for location 12?

I think the right answer is 12 is binary is 00001100 since we have 8-bit representation. Then the first 4-bits would be line number and block number and the last 4 would be the offset? Is this correct? If not can anyone explain why?

I got this question wrong on homework and my TA is not responding to my questions.

My line of thinking is that each memory location saved in a cache is made of 3 components, the tag (which is what the cache uses to recognize it), the index (the location in cache that it is stored), the offset(tells the ram which offset hold the value).

Now in tag + index = baselocation and baselocation + offset = the address we want in main mem.

First off to calculate the offset it should 2^b where b = linesize. In direct mapping line size = block size which is 4. So the lower 4 bits are my offset.

Next the index which is the power of 2 that is needed to uniquely address memory. Since the cache total is 32. We need 2^x = 32 which is 5.

Lastly the tag is total# of bits - (offset + index) = -1 because 8 -9 which I know is inherently wrong.

This leads me to my previous answer above for location 12. Since it is 8-bits the lower 4 must be my offset leaving the upper 4 for my tag and index.

Guess that's why I got it wrong. But what is the right answer? And how do you solve these types of problems?


texts: Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?

texts: It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of langauges, than any Turing machine), does there exist a Turing machine $T$ which can always compute $M$ such that $T(M, x) = M(x)$?


texts: Why does this NFA having an empty symbol

texts:
I'm trying to understand the difference of DFA from NFA
I have this example in my coursebook

Are the empty symbols at the start necessary?
or can we do away with them to have something like this


texts: Find a collection of sets where each number from a given list is contained in a different set

texts:
I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S.  The cardinality of each of these sets can be anywhere from 1 to N.  The number of sets is variable, but is necessarily at least N.

e.g.

$S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$

Sets:

$\{3, 6\}$
$\{1, 2, 5\}$
$\{5\}$
$\{2, 6\}$
$\{2, 5\}$
$\{7, 8\}$
$\{1, 3, 5\}$
$\{7, 9\}$
$\{4, 8, 9\}$
$\{4, 5\}$

I'm looking for an algorithm that will let me determine if there is a group of N sets, where each element of S is contained in a different set (the other elements in the set are irrelevant).  Note that every element of S will always be represented at least once in the collection of sets (otherwise it is obvious that no solution is possible).

For this example, a possible solution is:

$\{\mathbf{1}, 2, 5\}$
$\{\mathbf{2}, 5\}$
$\{1, \mathbf{3}, 5\}$
$\{\mathbf{4}, 5\}$
$\{\mathbf{5}\}$
$\{2, \mathbf{6}\}$
$\{\mathbf{7}, 9\}$
$\{7, \mathbf{8}\}$
$\{4, 8, \mathbf{9}\}$

(bold numbers indicate the element of S for which each set was selected)

But if we were to exclude the set $\{4, 5\}$ from the pool of available sets, there would be no possible solution, despite every number being represented at least once in the available sets, and the number of sets still being at least N.

My N will not be more than 100, and the number of sets could be up to 100,000.  The frequency of numbers in the sets will likely be very unevenly distributed, so, for example, there might be 95% of the sets that contain a 1, but only <1% of sets that contain a 3.

Obviously the best performance is desirable, but I would appreciate any algorithm that is better than a brute-force search of every possible combination of sets.


texts: Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

texts:
I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $

If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where
$ V $ = Set of Variables or Non-Terminal Symbols
$ \Sigma $ = Set of Terminal Symbols
$ \delta $ = Set of Production Rules
$ S $ = Start Symbol

By def.
$$
G^R = \langle V \ ,\  \Sigma \ ,\  \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \}\ ,\  S \rangle
$$

$$
G^* = \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\  \delta \ \cup \ \{S' \rightarrow S'S \ |\ \lambda\} \ , \  S' \rangle
$$

Then I tried the following

$$
(G^R)^*= \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\  \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \} \ \cup \ \{S' \rightarrow S'S \ |\ \lambda\} \ , \  S' \rangle
$$
and
$$
(G^*)^R = \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\  \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \} \ \cup \ \{S' \rightarrow S S' \ |\ \lambda\} \ , \  S' \rangle
$$

I do not know how to continue, I haven't found any counterexample


texts: NP-hard proof with reduction from two known NP-hard problems

texts:
As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can reduce a know NP-hard problem Q to problem P in pseudo polynomial time.
Is it possible to show that a certain problem P is NP-hard by reducing two known NP-hard problems Q and Q' to a problem in P?


texts: Relations between deciding languages and computing functions in advice machines

texts:
I'm trying to understand implications of translating between functions and languages for P/Poly complexity.  I'm not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts.  (I have a project in which I want to discuss Hava Siegelmann's analog recurrent neural nets, which recognize languages in P/Poly, but I'd like to understand and be able to explain to others implications this has for computing functions.)
Suppose I want to use an advice Turing machine $T_1$ to calculate a function from binary strings to binary strings $f: \{0,1\}^* \rightarrow \{0,1\}^*$.  $T_1$ will be a machine that can compute $f$ in polynomial time given advice that is polynomial-size on the length of arguments $s$ to $f$, i.e. $f$ is in P/Poly.  (Can I say this?  I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)
Next suppose I want to treat $f$ as defining a language $L(f)$, by encoding its arguments and corresponding values into strings, where $L(f) =  \{\langle s,f(s)\rangle\}$ and $\langle\cdot,\cdot\rangle$ encodes $s$ and $f(s)$ into a single string.
For an advice machine $T_2$ that decides this language, the inputs are of length $n = |\langle s,f(s)\rangle|$, so the relevant advice for such an input will be the advice for $n$.

Question 1: If $T_1$ can return the result $f(s)$ in polynomial time, must there be a machine $T_2$ that decides $\{\langle s,f(s)\rangle\}$ in polynomial time?  I think the answer is yes.  $T_2$ can extract $s$ from $\{\langle s,f(s)\rangle\}$, and then use $T_1$ to calculate $f(s)$, and then encode $s$ with $f(s)$ and compare it with the original encoded string.  Is that correct?

Question 2 (my real question): If we are given a machine $T_2$ that can decide $\{\langle s,f(s)\rangle\}$ in polynomial time, must there be a way to embed $T_2$ in a machine $T_3$ so that $T_3$ can return $f(s)$ in polynomial time?
I suppose that if $T_2$ must include $T_1$, then the answer is of course yes.  $T_3$ just uses the capabilities of $T_1$ embedded in $T_2$ to calculate $f(s)$.  But what if $T_2$ decides $L(f)$ some other way?  Is that possible?
If we are given $s$, we know its length, but not the length of $f(s)$.  So in order to use $T_2$ to find $f(s)$, it seems there must be a sequential search through all strings $s_f = \{\langle s,r\rangle\}$ for arbitrary $r$. (I'm assuming that $f(s)$ is unbounded, but that $f$ has a value for every $s$.  So the search can take an arbitrary length of time, but $f(s)$ will ultimately be found.)
One thought I have is that the search for a string $s_f$ that encodes $s$ with $f(s)$ has time complexity that depends on the length of the result $f(s)$ (plus $|s|$, but that would be swamped when $f(s)$ is long).
So now the time complexity does not have to do with the length of the input, but only the length of $f(s)$.  Maybe $L(f)$ is in P/Poly if $f$ is in P?  (Still confused here.)
Thinking about these questions in terms of Boolean circuits has not helped.


texts: Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?

texts:
Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10?  for example

int [] a = {1, 2, 15, 25, 28};
// would produce [2, 28], [15, 25]

I don't think so because when all sums are divisible by 10 then the total number of pairs is $n(n-1)/2$ which is $O(n^2)$.

int [] a = {5, 15, 25, 35, 45};
// n(n-1)/2 = 5(4)/2 = 10
// pairs [5, 15], [5, 25], [5, 35], [5, 45], [15, 25], [15, 35], [15, 45], [25, 35], [25, 45], [35, 45]


texts: Entropy and Information Gain for multi attributes

texts:
Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset:

$\begin{array}{cccccc|c}
x1 & x2 & x3 & x4 & x5 & x6 & y \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0 & 1 & 0\\
0 & 1 & 1 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 1 & 0 & 0\\
1 & 0 & 1 & 1 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 0 & 1\\
1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{array}$

How can I calculate the information gain for $x1,x2$ or $x1,x2,x3$ or $x1,x2,x3,x4$


texts: Why does the formula 2n + 1 find the child node in a binary heap?

texts:
I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with

$leftchild = 2n + 1$

$rightchild = 2n + 2$

I can see that this formula works and have played around with it for a little bit looking at examples, but I still don't understand why it works. Can anyone help me understand the intuition behind why this is correct?


texts: What's the reason for sqrt(n) bounds in online learning?

texts:
I have a question regarding no-regret algorithms (of online learning). As far as I can see, such algorithms allow the absolute regret up to round $n$, which is $R_n$, to grow by $\sqrt{n}$. So, in the limit, the per round regret ($R_n/n$) approximates $0$. Which makes it a no-regret algorithm. The problem is that I cannot see how to interpret $\sqrt{n}$. To clarify what I mean with "interpret" just an example: I know that in a binary game the mistake of algorithms is quite often bounded by $\log_2 n$. As an explanation one can think of a binary tree:

n=0    {0,1}
        / \
n=1 {0,1} {0,1}
      / \    / \
n=2 ... ... ... ...

Since:

log2(1) = 0
log2(2) = 1
log2(4) = 2
etc.

One can link $n$ (the number of rounds) and $\log_2(n)$ (the number of possible ways to $n$). Is there a similar link between $n$ and $\sqrt{n}$ for real values? What does the $\sqrt{n}$ stand for?


texts:
I have created an adjacency matrix which looks something like  this

    A   B   C   D   E   F   G   H   I
A   0   0   0   0   0   0   0   0   0
B   1   0   0   0   0   0   0   0   0
C   1   0   0   0   0   0   0   0   0
D   0   0   0   0   0   0   0   0   0
E   1   1   0   1   0   0   0   0   0
F   1   1   1   1   1   0   0   0   0
G   0   0   1   1   0   0   0   0   0
H   0   1   0   0   0   0   1   0   0
I   1   1   0   0   0   1   0   0   0

I am trying to manipulate this matrix such that an indirect link between two alphabet will replace the direct link. e.g. In the graph, C is connected to A and F is connected to both A and C (among others) and I is connected to both A and F. How do I go about removing the direct connections such as A and F, A and I since there are indirect connection between (C to A and F to C, C to A and F to C and I to F).

I tried using loop but it seems like more the indirect connection, the number of loop required increases as well. What type of algorithm should I use for this type of problem? Would adjacency list be a better alternative?


texts: Machine learning for recommendation systems (feed forward and recurrent neural networks)

texts:
I recently started to learn about machine learning. I have created a feed forward neural network (ffnn) and a recurrent neural network (rnn) to predict user ratings of movies. I am using a subset of 2000 users and their ratings of the "Netflix Prize" dataset.

The ffnn as well as the rrn have an accuracy of ~40% - 45% on the test set evaluation. This seems to be very low and I expected to get at least somewhere near 60% - 70% accuracy. I tried different network configurations (dimensions, layers, optimizers, etc.) but nothing changed the accuracy significantly (only 1% - 3% max).

Both models are constructed in a sense of supervised learning. The ffnn uses embeddings of users+movies for the input and ratings for the output. For the rrn I am using one hot encoded movie vectors as input and one hot encoded ratings vectors as the output.

For the implementation I am using Keras in Python.

The ffnn is constructed like this:

dimension = 120
model_users = Sequential()
model_users.add(Embedding(len(np.unique(users)), dimension))
model_users.add(Reshape((dimension,)))

model_movies = Sequential()
model_movies.add(Embedding(len(np.unique(movies)), dimension, input_length=1))
model_movies.add(Reshape((dimension,)))

model = Sequential()
model.add(Merge([model_users, model_movies], mode = 'concat'))
model.add(Dropout(0.1))
model.add(Dense(100, activation = 'relu'))
model.add(Dropout(0.1))
model.add(Dense(500, activation = 'sigmoid'))
model.add(Dropout(0.1))
model.add(Dense(dimension, activation = 'linear'))
model.add(Dropout(0.1))
model.add(Dense(5, activation = 'softmax'))
model.compile(loss = 'categorical_crossentropy', optimizer = 'adam', metrics=['accuracy'])
print(model.summary())

The rnn model is constructed like this:

dimensions = len(movies_unique)

model = Sequential()
model.add(Masking(mask_value = 0, input_shape = (dimensions, dimensions)))
model.add(LSTM(32, return_sequences = True))
model.add(TimeDistributed(Dense(len(ratings_unique), activation = 'relu')))
model.add(Activation('softmax'))
model.compile(loss = 'mse', optimizer = 'adam', metrics = ['accuracy'])
print(model.summary())

How can I further improve the accuracy to get beyond ~45%? I might be missing something fundamental here, so any help is appreciated! :)

Best, Nico


texts:
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following Facts is False, and True.
$I$) Graph $G$ is a Tree.
                False.

$II$) weight of each ${u,v}$ edge, is at least equal to heaviest edge in shortest path from $u$ to $v$.
                True.

Anyone can describe me why the second fact is hold? Intuitive idea or
example or proof?


texts: Is there a canonical definition of “pure” function?

texts:
StackOverflow pointed me here, so the question might be a bit in a layman's terms.

Wikipedia defines pure functions as

  In computer programming, a function may be described as a pure
  function if both these statements about the function hold:

  The function always evaluates the same result value given the same
  argument value(s). The function result value cannot depend on any
  hidden information or state that may change as program execution
  proceeds or between different executions of the program, nor can it
  depend on any external input from I/O devices.
  Evaluation of the result does not cause any semantically observable side effect or
  output, such as mutation of mutable objects or output to I/O devices.

However it does not seem to cite any sources -- so it is hard to say whether this is an accepted definition, or who defined it this way.

When I look at what the languages do when they include a syntax/annotation for "pure" functions, there are quite a few different approaches:

In D the only limitation is non-mutation of global state. "Pure" functions can mutate its arguments.
In GCC there are two types of "pure": pure (no side-effects, but can read global state) and const (stricly pure as per wikipedia definition).
In C#, it is defined as "does not make any visible state changes" (whatever that is).
Haskell follows the Wikipedia definition.

So my question is: is there a canonical definition of pure function?
And if there is, what is its source?


texts:
I'm currently learning about conjunctive normal form in a course on logic for Computer Science. I was reading the Wikipedia entry on the subject and encountered this:

  Typical problems in this case involve formulas in "3CNF": conjunctive normal form with no more than three variables per conjunct. Examples of such formulas encountered in practice can be very large, for example with 100,000 variables and 1,000,000 conjuncts.

There is no source for this, and I'm curious as to the "practice" that's being referred to here. What kind of problems lead to these large sets of conjuncts; and can anyone point me to some examples?

Many thanks.