texts: Showing a problem is NP complete? Reducing CLIQUE to KITE.

texts:
I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc.

The problem is, there doesn't seem to be anyone available in my department to help me until after the test. I really struggle to understand it and get confused all too often when looking at it. So I was wondering if my wonderful chums of the internet could work through a problem with me! (Problem is below if you wanna skip my waffle) I apologise if there is an awful lot of it, I hope this will be useful for me or future lurkers though. Feel free to only answer part of it.

I get that $X \leq_p Y$ means that given an oracle for Y, we can solve X using a polynomial number of standard computational operations plus a polynomial number of calls to that oracle for Y.
I also get that to show a problem Y is NP complete we show:

  There exists a polynomial time certifier for problem Y.

  We give a reduction $X \leq_p Y$ from a known NP problem X. Ie: Showing that X is no harder than Y.

But in practise, I really struggle to do both of these things. It all seems a bit hand wavy at times and the slides used by my course don't really help me, they seem to be used all over the place, here's a copy: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf

So, I thought we'd look at a problem that was included on an earlier test for my own module.

Given that CLIQUE is NP-complete, show that KITE is NP-complete

The CLIQUE decision problem is given a graph G and integer k; decide whether there is an induced complete subgraph of size k. The KITE decision problem is to decide whether there is a kite subgraph of size 2k, which consists of a clique of size k with a k-size tail.

Creating the certifier

So, how exactly should I write a certifier for KITE? I don't really understand what my certificates should be to be honest. I assume I want an input graph $G=(V,E)$ and then maybe a graph $H=(V',E')$ with an integer $k$ such that $H$ is a kite of $2k$. And then check if G contains H as an induced subgraph? But that seems way too easy considering it was worth 20% of the example paper.

algo kiteCertifier(Graph G, Graph H, int k) {
  for each v in V'
    if v not in V
      return no

   for each (u,v) in E'
      if (u,v) not in E
          return no

   return yes
}

I suppose what really confuses me is that I don't get how to pick a certificate for problems, perhaps I don't really get what a certificate is or what a certifier should actually be doing.

Showing $CLIQUE \leq_p KITE$

This is where I often get confused I think. I've seen different reduction examples showing an implication in one direction, then the other, and many just show iff.

Again, it can't just be as simple as saying every kite has a clique in it can it? That's almost axiomic! I wondered if perhaps I should show a graph contains a clique iff it contains a kite.

Given a clique C of size $2k$ or $2k+1$ (i.e.: odd or even clique) we show there always exists a kite of size $2k$ within it.
Consider any k nodes $\{v_1,v_2,...,v_k\}$ in the clique. These nodes also form a clique because every node v in the clique is connected to every other node w by an edge. Now consider the nodes $\{v_{k+1},v_{k+2},...,v_{2k}\}$. Each node $v_j$ in this set is connected by an edge to $v_{j+1}$ since C is a clique. We also have that $v_k$ is connected to $v_{k+1}$ and so we now have a kite of size 2k.

Now suppose we have a kite of size 2k, by definition, it contains a clique of size k.

But again, I really don't feel confident enough on this, am I even doing anything vaguely correct? :p Any help would be greatly appreciated.

Thanks very much!


texts: What are the difference between and consequences of using type parameters and type indexes?

texts:
In type theories, like Coq's, we can define a type with parameters, like this:

Inductive ListP (Element : Type) : Type
  := NilP  : ListP Element
   | ConsP : Element -> ListP Element -> ListP Element.

Alternatively, we can define a type with an index, like this:

Inductive ListI : Type -> Type
  := NilI  : forall t, ListI t
   | ConsI : forall t, t -> ListI t -> ListI t.

My questions are:

Are these fundamentally different or fundamentally the same?
What are the consequences of using one over the other?
When is it preferable to use one over the other?


texts:
Let us consider Martin-Löf type theory with a cumulative hierarchy of universes
$$
\mathcal{U}_0\colon\mathcal{U}_1\colon\ldots
$$
If $A, B\colon \mathcal{U}_i$, we can form an identity type $A=_{\mathcal{U}_i} B:\mathcal{U}_i$. Using the axiom of cumulative hierarchy, we can derive $A, B:\mathcal{U}_{i+1}$, so we have also an identity type $A=_{\mathcal{U}_{i+1}}B$. Assuming the Univalence axiom (for all the universes), they are both equivalent to a type of equivalences $(A\simeq B)$, which has nothing to do with universe issues. What can we say about the relationship between types $A=_{\mathcal{U}_i} B$ and $A=_{\mathcal{U}_{i+1}} B$ without the Univalence axiom?


texts: Min-weight bipartite matching in Christofides' algorithm

texts:
Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make all of them even, so that a Eulerian tour can be found (since all vertices are even now).

My question arises from a simple example: suppose there are four odd-degree vertices in the MST, labeled $v_1, ..., v_4$. Now suppose that $v_3$ and $v_4$ are already connected in the original MST, and further suppose that the minimum weight matching requires them to be connected. This means that the matching is redundant, and the two vertices still have odd degree at the end.

Does this simply mean that the bipartite matching has to be re-run to find the "next-to-minimum" matching, or are there other heuristics?


texts:
In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). Though I cannot prove that this would always work or won't but I intuitively felt that it should, but eventually some examples could be created that fail this greedy approach.

Can someone prove/disprove whether the greedy approach is correct? Not just a counterexample, but a general explanation would be quite useful.


texts: Number of substrings with exactly k distinct characters

texts:
Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return 0.
Input: s = "pqpqs", k = 2
Output: 7
Explanation: ["pq", "pqp", "pqpq", "qp", "qpq", "pq", "qs"]

I have this solution for it:
   def subarraysWithKDistinct(self, A, K):
        return self.atMostK(A, K) - self.atMostK(A, K - 1)

    def atMostK(self, A, K):
        count = collections.Counter()
        res = i = 0
        for j in range(len(A)):
            if count[A[j]] == 0: K -= 1
            count[A[j]] += 1
            while K < 0:
                count[A[i]] -= 1
                if count[A[i]] == 0: K += 1
                i += 1
            res += j - i + 1
        return res

What I don't understand is how does atMost(k) - atMost(k-1) gives the total number of substrings that have exactly k distinct characters? I tried different examples and it works. I understand how the code works but not how the final answer is computed after two-passes.
Can someone give me generic mathematical proof or intuition behind it?


texts: Compiler optimization which does an SMT-like optimization in software?

texts:
Say I had two functions called one after the other:

A1, A2 : vector of doubles
B1, B2 : vector of ints
f = dot product on ints
g = dot product on doubles

f(A1, A2)
g(B1, B2)

Does there exist a compiler optimization which could merge the dot product implementations for f and g such that you would get the following code(in psuedo-assembly):

mov F3 , #0
loop:
fetch from A1 into F1
fetch from A2 into F2
doublemulacum F1 F2 F3
fetch from B1 into R1
fetch from B2 into R2
integermulacum R1 R2 F3
branch if end of A1 and B1 not reached
# then branch to a cleanup implementation which completes the dot product for the longer vectors.

The advantage of this over generating two dot product calls, would be the ability to execute integer and double multiplications concurrently as well as being able to fetch concurrently, and get similar peformance to running the integer dot product on one SMT thread, and the double dot product on another SMT thread.

More generally is it possible to do something like this for two arbitrary (pure) functions, or would the cleanup logic for when one function finishes before the other be to complex?


texts: If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

texts:
Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?

If $B$ is NP-hard then $A$ is NP-hard.

Can some explain this intuitively?


texts: What is the best way to identify highly performing groups?

texts:
I am currently working on a project that involves sorting people into groups based on their ability to work well with others.
While it is a bit of a simplification, I have a problem that is essentially as follows:
Let us say we have 100 people. These people have to complete a task, and will subsequently receive a score depending on how well they performed. In order to complete the task, the participants are allowed to form groups of up to 5. When they collectively complete the task, they will also receive a single score. How can I identify (1) individuals that have a high capacity for teamwork; and (2) specific groups that are extremely good at performing said task (by receiving high scores)?
I’ve given it some thought but not many good answers come to mind. For example, I could make all the possible combinations of groups of 2, 3, 4, and 5 and try to identify such high performance groups. However, the number of combinations is astronomical and so I would like to determine a more elegant solution.
Thank you for your help. Please ask me any questions, I will be happy to answer if I have missed anything.


texts:
I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to destination and saturate atleast one edge in all of the shortest paths respectively [1] and we delete that path. In examples I am reading online, it is explained with an example of graph with all edges of unit length
[2].  Our professor explained the solution to this using dynamic trees. I am unable to apply the concept of dynamic trees (splay) for the solution of this problem. What will be stored in the nodes of the tree and on what basis will we perform the spaly operation?

[1] There can only be one shortest path, or many shortest paths of same length. What is the concept of all shortest paths?

[2] If a graph has all edges of unit lengths, then all the edges will be deleted (because all will appear in some path from source to sink). Then, source and destination will be disconnected in the end. What would be the use of doing this?

What is the goal for solving this problem? Can someone point in right direction in layman's terms? Also I have read some articles regarding this but unable to understand them and also none of them uses splay trees to solve this problem.


texts: How to use Master Theorem with strange format of $b$ parameter?

texts:
I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:

$$T(n)=\begin{cases}
6 &\text{ if } n=0,\\
T(n-1) + 6n + 6 &\text{otherwise.}
\end{cases}$$

How can I apply the Master Theorem to this problem? I have only seen the M.T. in one of these two formats:

$$T(n) = aT(n/b) + f (n)$$
$$T(n) = aT(n/b) + \Theta(n^c)$$

So I'm wondering how to transform the $T(n-1)$ to something usable. Is it even possible to apply the theorem to this kind of problem?


texts:
Let $a:=(a_1,a_2,\ldots,a_n) \in  \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with

$$f:
\begin{cases}
\hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\
\hfill ((a_1,a_2,\ldots,a_n), k) \hfill & \mapsto  (b_1,b_2,\ldots,b_n)\\
\end{cases}$$

$f$ satisfies the following constraints:

$(\forall b_{i=1,2,\ldots,n}\in \mathbb{Z})(\exists! a_{j=1,2,\ldots,n}\in \mathbb{Z}): b_i= a_j \pm k$
$b_{\max} - b_{\min} \le  a_{\max} - a_{\min}$

The task is to find a function $f$(or an algorithm) that satisfies the listed constraints. Could anyone give some hints how can I deal with this problem?

Examples:

Example 1:
$$f((1,7),4)=(5,3)$$
First constraint:
$$5 = 1 + 4$$
$$3 = 7 - 4$$

Second constraint:
$$5 - 3 \le 7 - 1$$

Example 2:
$$f((1,2,3,4,5,6,7),5)=(6,7,\ldots,12)$$
First constraint:
$$6 = 1 + 5$$
$$7 = 2 + 5$$
$$\vdots$$
$$12 = 7 + 5$$
Second constraint:
$$12 - 6 \le 7 - 1$$

I tried to solve this problem algorithmically. The following is an implementation using JAVA

public class MinDiff
{
    public static void main(String[] args)
    {
        int A[] = {1,7};
        int k = 4;
        System.out.println("Input a:=" + Arrays.toString(A) + ", k:=" + k);
        int d = find(A, k);
        System.out.println("Output a´:=" + Arrays.toString(A));
        System.out.println("Maximum difference is " + d);
    }

    private static int find(int a[], int k)
    {
        Arrays.sort(a);

        int n = a.length;
        System.out.println("Maximum difference is " + (a[n - 1] - a[0]));

        if (k >= a[n - 1] - a[0])
        {
            for (int i = 0; i < n; i++)
                a[i] += k;
            return a[n - 1] - a[0];
        }

        a[0] = a[0] + k;
        a[n - 1] = a[n - 1] - k;

        int max = Math.max(a[0], a[n - 1]);
        int min = Math.min(a[0], a[n - 1]);

        for (int index = 1; index < n - 1; index++)
        {
            if (a[index] < min)
                a[index] += k;
            else if (a[index] > max)
                a[index] -= k;
            else if ((a[index] - min) > (max - a[index]))
                a[index] -= k;
            else
                a[index] += k;

            max = Math.max(a[index], max);
            min = Math.min(a[index], min);
        }

        return  max - min;
    }

The above implementation fail to give a solution for the following input:
$$a:=(1,2,\ldots,7) \text{ and } k:=5$$

Generally I´m interedted in the following questions: Let $a:=(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n \text{ and } k \in \mathbb{N}^*$

What is the minimal distance that can we achieve? Could we answer this  question a priori?
Could we also a priori answer the following question: Does $k$ lead $a$ to an increase or decrease(the $2^{th}$ constraint)

Thanks in advance


texts: Can someone explain to me how a word is fetched from memory at the hardware level?

texts:
Most of the learning material my knowledge of computers is based on revolves around early , byte addressable CISC-like machines , such as the SAP described in Paul Malvino's great "Digital computer Electronics" book. The concepts described fairly simple to handle to understand once you get the hang of it : the address of the instruction is taken from the pc to the MAR, the instruction is fetched from memory into the Instruction Register , and then the data is fetched . The rest of the machine cycle goes on .

Problem is , i've come to realize that more modern designs are far different in how they operate , and i feel that the concepts learned in that book are holding me back because they lock me into looking at everything from a byte-addressable view.
When looking at SRAM  such as https://www.alliancememory.com/wp-content/uploads/pdf/AS6C62256.pdf, it seems easy at first . The address of the byte is put onto the address pins as described by the datasheet .The chip select pin is asserted . The data is put on the input pins if necessary . The WE/OE pins are asserted depending on the operation . this made sense for me .

But recently , i've been learning about RISC , which seems to operate on fairly on fairly different principles with regard to the Fetch stage. I'd like to think i have basic pipe-lining concepts wrapped up.

I'm intrigued by how multiple bytes can be pulled off memory , because it clashes with my preconceived notions about how memory works .
I used to think that only ONE byte and one byte only can be pulled off memory per instruction ( because only one address is specified by the PC ) , meaning that in order to increase instruction width , it would be necessary to have larger( word sized ) bytes .
something like the memory chips linked above could be synched under a single address, with 32 bits being fetched off a single address .
However , i've seen that this is not only inefficient , it's also not what is actually implemented.
I've been told that yes , RISC machines do multiple bytes off memory in one cycle .
A common explanation is the base address of the word is given , and somehow the 3 bytes after it are fetched as well . This is supposedly done using some magical hardware that is able to do this , but i've never been told how it is actually built and it's operating principles .
As far as i've seen , memory has address lines , I/O , a chip select pin and a write/output enable pin . How does this [1] output 4 bytes at once ?
I've sometimes been told that the cpu actually reads cache lines . But as far as i know , caches are just high speed SRAM that mirror part of main memory . I still can't understand it given my current understanding of memory .
Where am i wrong ? can somebody help me out on this?


texts: effective, efficient algorithms on antichains

texts:
In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable.

Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such that if x is in S, any y ≥ x is also in S: if L is finite (the situation is more complicated in the infinite case), then any such S can be represented as the upward closure of the antichain of its minimal elements.

Given S1 and S2 respectively defined as the upward closures of antichains A1 and A2, the literature describes how to compute an antichain describing the union (respectively, the intersection) of S1 and S2:

For union, take the union of S1 and S2 and keep only the minimal elements.
For intersection, assuming L is a lattice, take the least upper bounds of pairs of elements (a1,a2) from A1×A2, and retain the minimal elements.

There is a trivial quadratic algorithm for retaining only minimal elements (perform all pairwise comparisons and remove elements shown not to be minimal). Naively, union is thus quadratic and intersection degree 4.

I have not been able to find in the literature any more detailed description of suitable algorithms or data structures; for instance can the antichain be represented as a BDD-like structure, etc.

I'd be curious to know about literature on non-naive implementations of antichains, particularly if L is the lattice of subsets of a finite set.


texts: How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes?

texts:
When the halting problem is discussed, often the counterproof consists of some unsolved mathematical problem or a self-reference.

Is the halting problem decidable for pure programs on an ideal computer?

Is this of any relevance for most programms not even remotely dealing with complex math ? I often hear that performing static analysis on any program is useless, because "Halting-problem". I find this argument weak, to make a statement from a few theoretical counter examples to say that static analysis on any programm is useless.

And what about a modified version of the halting problem?

What about outputting those 3 possibilities:

Halts.
Does not halt.
Unknown.

Doesn't this simplify the halting problem enough to make a statement about any program in finite time ?


texts: Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

texts:
Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ and $t$? For simplicity, we can assume $G$ is simple, undirected and unweighted.

Even in many restricted graphs, the number of shortest paths between $s$ and $t$ can be exponential in the size of $G$. Therefore, we would naturally like avoid actually computing all the shortest $s$-$t$ paths. I don't know about the general case, but it seems to me that we can achieve this for some special graph classes.

This feels like something someone must have considered before. Is there any existing research into this, or is this in fact simple to do even for general graphs?


texts: Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$

texts:
I'm trying to understand decidable languages. In particular, I would like to show that
$$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$
I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?


texts:
Different machine has different efficiency on different tasks, like:

| T/M | M1  | M2  | M3  |
| T1  | a11 | a21 | a31 |
| T2  | a12 | a22 | a32 |
| T3  | a13 | a23 | a33 |

So, Machine $M_1$ needs $a_{11}$ time on finishing Task $T_1$.

Each machine can process one task everytime. Each single task cannot be splited up. How to find the min finishing time for all tasks in sum? (finishing time of each task include its waiting time and processing time).

I only has a awful enumerate algorithm for this, enumerate all possible solution and find out the min one. That costs $O(n^n)$.

Is there any optimized algorithm for this question?


texts: Confusion in understanding a DFA question

texts:
I am new to DFA and I am trying to understand the following question.
The alphabet is Σ = {0, 1}
Construct DFA for L = {0^n: n is either a multiple of 3 or a multiple of 5 }
Question
The above language does not say anything about the 1s.
When we write strings in this Language, we get
L = {є, 000, 00000, 000000, 000000000, ...}
There are no ones in this language.
According to the language description, 0010 would not be a valid string. Right?
So, in the DFA that we construct do we need to show 1s? Can I just leave them out?


texts: What Methods to use to Weight Employees by Value Using Predetermined Categories

texts:
In order to determine how much value employees provide to a company, I want to build a system that goes beyond basic math in terms of sorting said employees.  I'm working with values like current salary, number of people working under them, and a value from 1-3 of how indispensable they are to the company.  What methods should I use to construct a weighting system, so the allotments of value aren't just completely subjective?

*note - I'm not asking for a perfect method, just something that helps improve my accuracy on determining value.


texts:
Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole complexity, but sometimes it's hard for me to differentiate between O(1) and O(n) plus there's the whole theta notation and all that, basic explanation of P=NP and simple algorithms, tractability. I want a text that covers all that, and that doesn't require a heavy mathematical background, or something that can be read through.

LE: I'm still in highschool, not in University, and by heavy mathematical background I mean something perhaps not very high above Calculus and Linear Algebra (it's not that I can't understand it, it's the fact that for example learning Taylor series without having done Calculus I is a bit of a stretch; that's what I meant by not mathematically heavy. Something in which the math, with a normal amount of effort can be understood). And, do pardon if I'm wrong, but theoretically speaking, a class at which they teach algorithm design methods and actual algorithms should be called an "Algorithms" class, don't you think?
In terms of my current understanding, infinite series, limits and integrals I know (most of the complexity books I've glanced at seemed to use those concepts), but you've lost me at the Fast Fourier Transform.


texts: Number of parameters to be optimized in Artificial Bee Colony

texts:
I was reading this paper - Software defect prediction using cost-sensitive neural network by Ömer Faruk Arara and Kürsat Ayan

It uses Artificial Bee Colony algorithm to train the neural network. In ABC algorithm, the input is an N x D matrix, where D is the "number of parameters to be optimized" in the problem.

If the ultimate objective of the ABC algorithm is to minimize the Normalized Expected Cost of Misclassification (NECM) as the paper suggests, is D equal to the number of variables in the NECM function or is equal to the number of metrics passed to the ANN?


texts: Discrete fourier transform of a polynomial whose degree is not a power of 2

texts:
I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT.

But the problem that I am facing is this. FFT only works when $n$ is a power of 2. If I extend my polynomial by appending zeroes at the end, that would not solve my problem because then I would be evaluating my polynomial at cube roots of $m$ (where $m$ is a power of $2$ greater than $n$) which I don't want.

Any ideas on this?


texts: How can I solve this deadlock related problem mathematically?

texts:
I came across following problem:

  A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows:

if (i % 2 == 0) {
      if (i < n) request Ri
      if (i+2 < n) request Ri+2
}
else {
      if (i < n) request Rn-i
      if (i+2 < n) request Rn-i-2
}

  In which one of the following situations is a deadlock possible?
  (A) n=40, k=26
  (B) n=21, k=12
  (C) n=20, k=10
  (D) n=41, k=19

The given solution takes following form:

  Even numbered process $P_i$ request even numbered resources $R_i$ and $R_{i+2}$. Thus they share no more than 1 resource.
  Odd numbered process $P_i$ request

  Odd numbered resources $R_{n-i}$ and $R_{n-i-2}$ if $n$ is even
  Even numbered resources $R_{n-i}$ and $R_{n-i-2}$ if n is odd.

  In this example, for deadlock to occur, two processes must request same set of processes. For this, we need n to be odd so that some odd numbered process will request same set of even numbered resources as some even numbered process.
  Thus option A and C are not possible as they have even n.
  For option D, n = 41, k = 19. Resources requested will be:

  Thus no two processes request same set of resources.
  For option B, n = 21, k = 12. Resources requested will be:

  P7 and P10 request same set of resources R12 and R14.
  P9 and P8 request same set of resources R10 and R12.
  P11 and P6 request same set of resources R8 and R10.
  These pairs can cause deadlock if one of them come first and request one of the resources and then other comes and requests other resource and lastly both request the respective remaining resource.

I was guessing whether I can solve this mathematically to speed up. I thought following

  When i is even, Pi requests $R_i$ and $R_{i+2}$
  When i is odd, Pi requests $R_{n-i}$ and $R_{n-i-2}$
  Then I though I need to equate as follows:

  $i = n-i-2 \rightarrow 2i=n-2$
  $i+2 = n-i \rightarrow 2i=n-2$

  Then try out for option A as:

  $40-2 = 38 \rightarrow i=19$

  But later I realize, this was simply stupidity and remained directionless.

I still dont know whether I can solve this problem quickly mathematically without forming those tables. Is it possible?

(Sorry for more mathematical problem than the one involving Operating Systems or Computer Science concepts.)


texts: Can you use CPS to simulate state in a stateless programming language?

texts:
In a language supporting CPS, but no built in global state, we can represent a state based computation using a function. We call this function a state function. Assume the function takes three arguments, get, put, and cont. The intended interpretation of these functions is that get takes a continuation, and applies that continuation to some global state. put takes a new state and a continuation, changes the state to the new state, and applies () to the continuation. cont takes an argument, and ends the computation using that argument as the result.

We can define a function evalAbs such that for any state function f, evalAbs(tree, state) evaluates to (res, state'), where tree is an abstract syntax tree for f, res is what f evaluates to when it is computed with the global state initialized to state, and state' is the final state of that computation.

To define evalAbs, we can use recursion. The procedure for evalAbs(tree, state) is

Reduce tree to head normal form.
If this reduction results in "\get.put.cont.get(cont')", return evalAbs("\get.put.cont.cont'(state)", state).
If instead this reduction results in "\get.put.cont.put(state', cont')", return evalAbs("\get.put.cont.cont'(())", state').
If instead this reduction results in "\get.put.cont.cont(res)", return (res, state).
Otherwise, fail.

My question is if can we write an eval (itself written in CPS) that takes f itself instead of tree (i.e. f as a black box).


texts: Prove that every two longest paths have at least one vertex in common

texts:
If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.

I think that that common vertex should be in the middle of both the paths. Because if this is not the case then we can have a path of length $>k$. Am I right?


texts: Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well)

texts:
This problem probably falls under some category of algorithms but I don't know which.

  A given restaurant has $b_1..b_n$ branches around the world. A food critic has to travel all of the branches.

  When the critic finishes visit to the branch $1 \le j\le n$ he gets paid $m_j$ money by his employer for the job.
  For branch $j \le n-1$ he takes a flight to the next branch $b_{j+1}$ while the flight costs $c_j$ money. From the last branch $b_n$ a flight goes out to the first branch $b_1$ for the cost of $c_n$.

  It is also given that the total amount of money the critic received equals the total cost of flights so:
  $$
\sum_{j=1}^n m_j=\sum_{j=1}^n c_j
$$
  At any given point the critic can only pay for the next flight out of the money he currently has.

  Lastly, the critic can choose any branch which he will visit first and the first trip will be free.

  Prove that the branch $j$ exists such that the critic will be able to start from $b_j$ and visit all branches and suggest an algorithm which will find such a $j$ in $\Theta(n)$ time.

The hint which was given to us is to use queue data structure.

I thought of the following algorithm:

1) Add all branches to a queue.

2) Check if we can travel to the next branch that is if $m_j \ge c_{j+1}$.

If no, that means we don't have enough money so push the branch to the tail of the queue.
If yes, check if $m_j+m_{j+1} \ge c_{j+1}+c_{j+2}$ that is if the critic does travel to the next branch will he have enough money to continue from that branch?

--If yes then advance one branch in the queue.

--If no push the next branch to the tail of the tail of the queue

After one traversal of the queue we should have branches in such an order that the critic can complete the journey and branch $j$ will be at the head of the queue.

I'm on the right track? I'm not sure this proves formally enough that a $j$ indeed exists so the critic can complete the journey.


texts: Why doesn't relu cause back propegation to get stuck

texts: Say you have a neural net that is being trained using back propagation and you are using relu activation. Say the input to a node is a weighted sum of the previous layer with a bias term and say for a particular data point, this weighted sum plus bias is negative. Then relu returns 0. Notice the change in the loss as a function of the change in one of these weights or the bias is 0. Therefore the network won't improve the bias as the network does back propagation. Why is this not a problem?


texts: Context free languages invariant by "shuffling" right hand side

texts:
Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.:
$A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; CBD \; | CDB \; | \; DBC \; | \; DCB$
It may happen that the resulting language $L'$ generated by the expanded $G'$ is equal to $L$
For example:
Source               Shuffled
S -> XA | YB         S -> XA | AX | YB | BY
A -> YS | SY         A -> YS | SY
B -> XS | SX         B -> XS | SX
X -> 1               X -> 1
Y -> 0               Y -> 0

Is there a name for such class of grammars ($L(G) = L(G_{\text{shuffled}}))$?

Furthermore, does this theorem hold?

Theorem [it doesn't hold, see Yuval's answer and comments]: If exists a grammar $G$ such that, $L(G) = L(G_{\text{shuffled}})$, then for all $G'$ such that $L(G) = L(G')$ we have $L(G') = L(G'_{\text{shuffled}})$
In other words the "shuffle invariance" of grammars also corresponds to a class of languages.


texts: What does the following algorithm approximate? (Assume m>1,ϵ>0)

texts:
x = m;
y = 1;
While (x-y > ϵ)
{
    x = (x+y)/2;
    y = m/x;
}
print(x);

The answer is m½, its the Babylonian algorithm for square roots.
I understand the algorithm but haven't been able to reverse engineer what this code does (which is the point of this question since its not part of the curriculum and almost no one would have prior knowledge of it). So again, my question is how can I deduce this code calculates square roots, just from the code itself?


texts: Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?

texts:
What happens if we increment binary semaphore $x$ when it is equal to $1$.
E.g A process executes $V(x)$ when $x==1$;
What are the possible cases then-

Process would be blocked till $x$ becomes $0$. The moment $x$ becomes $0$,it is incremented.
Process would be blocked and no present or future changes will be there for $x$. i.e Process assumes as if there was never a $V(x)$.
Other. (If there is please mention).

Same query for $P(x)$ operation as well when $x=0$.

Actually, Galvin doesn't mention in pseudo code what to do during such condition.
Better if Someone could provide standard code for $P(x)$ and $V(x)$... Also, $P$ is wait operation whereas $V$ is signal operation.


texts: Status questionis for whether a machine can or can't "think"

texts: In his paper Computer Machinery and Intelligence, Turing addresses some arguments against the ability of a computer to pass the Turing test, such as the Theological Argument, the Mathematical Objection and the Argument from Consciousness. I wonder what is the current status of this debate; are there strong counterarguments for Turing's objections? Moreover, what is the most relevant bibliography on this topic?


texts: Aren’t most constraining variable and least constraining value the exact opposite?

texts:
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables as possible


texts: Are there any formal grammars describing the set of all directed graphs?

texts:
Let GRAPHS be the set of all directed graphs.

Is  there a set of strings STRYNGS such that there exists a bijection between
GRAPHS and STRYNGS?

The canonical definition of directed graph comes to mind:
An ordered pair of two sets, (V, E) such that V is a set of vertices
and E is a set of ordered pairs of elements in V.

Perhaps the following string is in the set of strings:

(  {0, 1, 2} ,    {(0, 1), (1, 0), (1, 2), (2, 0)}   )

Maybe we can use Zermelo's definition of natural number:

1 = { }
2 = {{ }}
3 = {{{ }}}
and so on...

The following two graphs are isomorphic:

(  {0, 1, 2} ,    {(0, 1), (1, 0), (1, 2), (2, 0)}   )
(  {9, 5, 3} ,    {(9, 5), (5, 9), (5, 3), (3, 9)}   )

STRYNGS need not contain all graphs per se, but merely at least one representative from each equivalence class defined by the graph isomorphism  relation.

If there there exists such set of strings STRYNGS, and there exists a bijection between the strings and the set of digraphs GRAPHS, does there also exist a grammar describing STRYNGS?

The grammar can be Context-sensitive, context-free or otherwise; any kind of grammar will do.


texts: That's my question, since it has two symbols but go to a single state, is DFA or NFA?


texts: Are there any proofs of exponential lower bound time complexity

texts:
I'm trying to understand what are the techniques to prove an exponential time lower bound.

For some problems, we can prove that the size of the output is exponential is the size of the input, thus it takes an exponential number of steps just to write the output. For example for some generalized board games, if the input is the size of the board and the output is the sequence of winning steps.

But what about decision problems, where $|output|=1$ ? Are there any decision problems in $EXPTIME$ with known exponential lower-bounds ?

I don't see how we can prove such a lower bound. Like if we take again the generalized board game and ask the question if there is a winning strategy, we can prove that evaluating all strategies will take (in the worst case) exponential time, but how can we prove that evaluating all strategies is the only way to answer the question ?

Or if I take another example, if my input is a number $x$ and the output is $1$ iff there exist a permutation $p$ such as shuffling the bits of $x$ makes it prime, i.e. $p(x)$ is prime. Exhaustively exploring all permutations and running a primality test will probably be exponential in $|x|$, but what if there is a smart way to answer just by looking at $x$ (in sub-exponential time) ?

I hope that looking at an example of such a proof will help me grasp the principles involved.


texts:
My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement.
I read that the IDS algorithm is optimal, but in my case is not optimal paths.

Is the IDS algorithm optimal for graphs (e.g. map as a grid), or does optimality only apply to searching trees?


texts: Range update + range query with binary indexed trees

texts:
I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates.

I found the following sources:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree
http://apps.topcoder.com/forums/?module=Thread&threadID=756271&start=0&mc=4#1579597

But even after reading through all of them I could not understand what the purpose of the second binary indexed tree is or what it does.

Could someone please explain to me how the binary indexed tree is modified to handle these?


texts: Find keys between $x$ and $y$ in binary search tree

texts: Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the height of the tree?


texts: What is the meaning of phenotype could be represented by a number of different genotype

texts:
I found this sentence in multiple sources but I didnt understand
in one thesis

With a neutral representation each phenotype could be represented by a
number of different genotype

and in another thesis

it may be possible for neural networks with functionally equivalent
topologies to be represented by a number of different genotypes

And in another source

the genotypical representation:
010 001 100 0000 1100 0000 0000 0000 0011 0100 0000 0000
However, the graph (phenotype) can also be represented by a number of
different genotypes. E.g:

010 001 100 0110 1100 0000 0011 0000 0011 0100 0000 0000

010 001 100 0000 1100 0000 0000 0000 0011 0100 1110 0100

Up to my understanding the first phenotype is the representation of the graph, so why the second or third phenotypes are different representations. how did we come up with the bold genotypes


texts: How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar

texts:
I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that

the <code> token must appear exactly twice,
while the <hour> token must appear at least once.

In the end I came up with this definition:

section     ::= hour_l CODE SC hour_l CODE SC hour_l ;
hour_l      ::= /* epsilon */
            | hour_l HOUR SC ;

where SC is a separator (semicolon) between tokens and hour_l is the non terminal symbol for hour's list.
This solution has a problem: HOUR can be absent, because epsilon can be reduced from hour_l.
Is there a clever solution other than specifying all possibilities or using the semantic capabilities of CUP (ie. putting a counter of how many times HOUR is present in section)? I'd prefer not to use semantics in order to achieve this; in fact, it seems to me this is syntax related.

Thanks


texts: What is a standard way to construct a turing machine for any function to compute

texts:
I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example:

f(x) = 2x + 3 n>= 0
MIN(x,y) leaves the smallest between x and y on the tape. e.g. x=2 y = 3 i.e. #aabaaa

I am not looking for a solution to the above but some kind of pattern i can use to solve these kind of particular problems quicker, in terms of transitions and what to have in mind before starting to solve.


texts:
I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant).

However I do not understand exactly how it is used for example for file systems or databases.

How do you choose the keys in these 2 scenarios? And what is the data?
Are data and keys the same?
I can't think of a good key that is able to order the data in a way that it is easily accessible. If I want to find an entry containing some string.
how useful would be a key that gives information about the size of each entry? or the alphabetical order? I don't exactly understand the concept.

I have to add that I don't understand much of file systems or databases which is probably why I'm confused.


texts: Name for sorting algorithm "while not sorted, swap the FIRST unordered pair"

texts:
A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass.

For a toy problem, we have a variant that just performs the first available swap in each iteration and repeats until sorted. It does not continue from the position of the last swap.

Is there a standard name for this sort? It seems so trivial that it must have a name, but we were surprised not to find it on any obvious lists. It's just like, a raw comparison sort.

Bubble

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
3, 2, 1, 4 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Variant

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
2, 3, 4, 1 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Don't worry, this is not meant to be a good sorting algorithm, just for a fun thing.


texts:
Problem: Given a DFA $D$, find all possible lengths of strings accepted by the $D$.

It makes sense that these lengths can be represented as $a_i+kb_i$. What might be the algorithm to find all such pairs $(a_i, b_i)$?


texts: Is the set of CFGs that contain all odd and even length words Turing-decidable?

texts:
$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)}

$ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd length in $\Sigma^*$} = {(M): $\Sigma$($\Sigma\Sigma$)* ⊆ L(M)}

Is $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ Turing Decidable?

I thought that this was yes because ALLEVEN would produce strings that are only even in length. ALLODD would produce strings that are only odd in length. The intersection would then be producing strings that are both even and odd in length, which is nothing. This means that we can reduce the problem to $E_{CFG}$ which is a decidable.

However, my professor says that $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ is exactly $ALL_{CFG}$ which is not decidable. I am not sure how he reached the conclusion that it is equal to $ALL_{CFG}$.


texts: MIPS Architecture : PC-relative addressing

texts:
In case of branch Instructions such as beq, bne, we use PC-relative addressing. But I am not clear why it is said in most of the books that MIPS address(while calculating branch target) is actually relative to the address of following(or sequentially next) instruction (PC+4) as opposed to the current instruction (PC)?

Anybody please explain me. Thanks.


texts: Are Perceptrons the neural network equivalence of Linear and Logistic Regression?

texts:
am I right in the assumption that both linear and logistic regression algorithms can be represented as the simplest form of neural networks,a perceptron, which consists of a two layers, an Input and an output, that combines all the input each with it's own respective weight to produces a prediction or classification polynomial?

if this is the case, is anything achievable by Linear or Logistic Regression is also achievable by a perceptron?


texts:
I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009).
In particular, this book states the following:

Karp-Lipton theorem
If NP $\subseteq$ $P_{\backslash poly}$, then PH $= \Sigma^p_2$.
Proof:
By Theorem 5.4, to show PH $= \Sigma^p_2$, it suffices to show that $\Pi^p_2\subseteq \Sigma^p_2$ and in particular it suffices to show that $\Sigma^p_2$ contains the $\Pi^p_2$-complete language $\Pi_2$SAT.

Theorem 5.4 states that

for every $i \geq 1$, if $\Sigma_i^p = \Pi_i^p$ then PH = $\Sigma_i^p$. That is, the hierarchy collapses to the ith level.

I am failing to understand how $\Pi^p_2\subseteq \Sigma^p_2$ implies $\Sigma_2^p = \Pi_2^p$.
As a more general question: does this hold for every $i$, i.e. does $\Pi^p_i\subseteq \Sigma^p_i$ imply $\Sigma_i^p = \Pi_i^p$ for all $i \geq 1$?


texts:
what is an easy but efficient way to evaluate Boolean Expression.  I have been searching a lot in google but not really finding a good book or site which has working algorithm.

Input string (A=100) and  B > 4)
Expected output to be either True or false.

regards
Deb


texts: What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

texts:
Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can be formulated as follows.

Problem Given a polynomial $P$, decide whether there is a graph $G$ with the corresponding adjacency matrix $A_G$ such that its characteristic polynomial $\chi_G(\lambda)$ equals the given $P$.

For an arbitrary $P$, it is not always the case that there is a corresponding $A_G$. The naive exhaustive algorithm for the problem uses a basic theorem in algebraic graph theory:

Theorem Let $G=(V,E)$ be a graph with adjacency matrix $A_G$ and $\chi_G(\lambda) = \lambda^n+c_1\lambda^{n-1}+c_2\lambda^{n-2}+\cdots+c_{n-1}\lambda+c_n$, then
(1) $c_1=0$,
(2) $-c_2 = |E|$, and
(3) $-c_3 = \text{twice the # of triangles in G}$.

Now, given $P$, the algorithm goes through every candidate $A_G$ of a corresponding $G$ with $|E|=-c_2$ and number of triangles ($K_3$) equal to $-c_3$. For each $A_G$, compute $\text{det}(A_G - \lambda I)$ and see if it equals the given $P$. If none match, return false. Otherwise, return the $A_G$.
This works, but is clearly not fast. The exhaustive algorithm would work even without the above theorem. Its use makes the search space smaller. What's a fast and more clever algorithm?


texts: How approximate sine using Taylor series

texts:
I need to approximate the sine function without internal libraries. I used Taylor series in 0 to solve this, but my program works for some values, but for others awful results.
The program gets x value, unit (degrees or radians) and how many words we want use for the approximation.
For values like

1 rad, 5 words results are ok:
sin(1 pi) = 0.833333 Difference: 0.00813765;

sin(0.5 pi) = 0.479167 Difference: 0.000258872

But for values like 125.6 rad it returns 2.60145e+008 and C++ sin() function gives -0.0636631, so the result is completely unreal.

Also it doesn't work for values in degrees although I convert degrees on radians. E.g. sin(4.71239 pi) = 6.63667 and real result should be -1.
I completely don't have any idea why it doesn't work properly, could anyone tell me what could cause these problems?

#include <iostream>
#include <math.h>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

using namespace std;

double degConverter(double);
void approximate(double, int, int);
int derivative(int);
double compareWithNorm(double, double);
double inline reductionFormula(double);

double inline degConverter(double x)
{
    return x / 180.0; //x * M_PI / 180.0    <-- the expression in comment gives wrong results in all situations?
}

void approximate(double x, int unit, int words)
{
    double result = 0;
    double xVal = 0;
    int factorial = 1;

    if (unit == 1)
    {
        xVal = x;
    }
    else if (unit == 0)
    {
        xVal = degConverter(x);
        x = xVal;
    }

    if (words > 1)
    {
        for (int i = 1; i < words; i++)
        {
            switch (i % 4)
            {
                case 1:
                    result += xVal / (double)factorial;
                break;

                case 3:
                    result -= xVal / (double)factorial;
                break;

            }
            xVal *= x;
            silnia *= i + 1;
        }
    }

    //Comparing with sin() function from math.h lib
    cout << "Difference between sin C++ and Taylor: " << compareWithNorm(x, result) << endl;
}

double compareWithNorm(double x, double result)
{
    double diff = 0;
    double pattern = sin(x);
    diff = pattern - result;
    if (diff < 0)
        diff *= -1;

    return diff;

}

double inline reductionFormula(double x)
{

    if (x > 2)
    {
        x = fmod(x, 2.0);
    }
    return x;
}

int main()
{
    double x;
    int unit = 1;
    int words = 1;

    cout << "Type x [degrees / rad]: ";
    cin >> x;
    cout << "\nType unit [deg = 0 / rad = 1]: ";
    cin >> unit;
    cout << "\nHow many words?: ";
    cin >> words;
    cout << endl;

    approximate(x, unit, words);

    return 0;
}


texts: Why is the assumption in the max heapify procedure crucial to its implementation?

texts: While watching MIT's 6.006 Lecture # 4 which is on heaps and heapsort, the professor was explaining why the time complexity of the max_heapify procedure is $O(\lg n)$. It's quite intuitive that it's bounded by $\log n$. But there's a lurking reason also, that affects the implementation, and that reason was the key assumption which has imposed to the procedure, namely the trees rooted at left(i) and right(i) are max heaps. Why is that? Why the assumption plays a role in its implementation? Is it even necessary?


texts: Prove that an infinite set is semidecidible

texts:
I have been asked to prove that:

Being C an infinite set. Prove that C is semidecidable if and only if exists a total computable function that is injective and whose image is C.

I've read the wikipedia articles of computable function and recursively enumerable set and I saw these properties are true. But I have no idea how to start the proof.

Could you please help me?

Thanks in advance.


texts: How are "Problem Complexity" and "Solution Complexity" different?

texts: I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the difference between these two. Do you all have an example(s) that can help me to understand?


texts: Convention of a += operator in pseudocode

texts:
I have to write some algorithm in pseudocode for a paper. For this I have the "$\leftarrow$" to assign a value.
$x \leftarrow y^2$
now I want to write a method which adds to the variable. In normal Python code I would write x += 1 for this. Is there a style convention how to layout this in pseudo-code in a paper? I dont really like the redundance of $x \leftarrow x+1$.


texts:
I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.

For example, if a graph G actually has a maximum clique with 13 vertices, and we use a 1.5-approximation algorithm to approximate the maximum clique - what is the minimum size clique that can be returned by this algorithm?

My first thought was to simply divide 13 / 1.5 since this would represent the worst that the algorithm could do. However, since that is ~ 8.6, would the minimum the algorithm returns be 9 or 8?


texts: Primitive Recursion and course-of-values recursion - examples?

texts:
I ran into examples that I not trivially understand on course-of-values recursion,

  In defining a function by primitive recursion, the value of the next
  argument $f(n+1)$ depends only on the value of the current argument
  $f(n)$. Definition of functions by course-of-values recursion,
  $f(n+1)$ depends on value(s) of some or all of the preceding
  arguments $f(n),…,f(0)$. very basic examples of definition by
  course-of-values recursion are Fibonacci numbers...

My examples, from the computation course, wrote following $f_1$ and $f_2$ is Primitive recursive. I reproduce them here:

Let $g$ be a primitive recursive function,

$f_1(0)=c_1, f_1(1)=c_2, f_1(x+2)=g(x,f_1(x),f_1(x+1))$, and
$f_2(x)=c, f_2(x+1)=g(x,[f_2(0),...,f_2(x)])$ are primitive recursive.

I couldn't say how $f_1$ and $f_2$ are Primitive Recursive? any idea
to finding these are P.R.?

Edit 1: after the Yuval Hint the $f_1$ is easy, but for $f_2$ there is a problem, I try more than three days, but not capable to create an easy encode for $f_2$. any hint or idea?


texts: Incorporating newline-as-statement-terminator heuristics into context-free languages

texts:
Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances.

My question is: how can I represent Scala-like optional semicolons in a context free grammar?  The specific issue is that some kinds of nesting delimiters "enable newlines" while others "disable newlines," so you need to pay attention to what kind of delimiters you are most immediately inside of.

I'm specifically asking about Scala's heuristic, because Julia and Quorum don't have specs.  Ruby has a spec, but handles the problem by scattering "[no line-terminator here]" throughout the formal grammar and I've been unable to find a general rule.  Go has a well described heuristic but it's lexical only, which makes it obvious how to specify and implement, but its usability is somewhat disappointing.  (Go inserts a semicolon even if you haven't closed the most recent ( token.)

Scala goes well beyond the Go lexical rule with a nesting rule (cf reference, Section 1.2).  In addition to lexically ensuring that both the token before and after the newline are consistent with the insertion of a statement terminator, newlines-as-statement-terminators are disabled between matching ( and ) parenthesis and [ and ] brackets, but then re-enabled between matching { and } braces.

I can figure out how to implement a simple pre-processor as a push-down automaton.  The automaton starts with enabled on the stack.  As you process the token stream, when you see a ( or [ push disabled onto the stack, when you see { push enabled onto the stack, and when you see ), ] or } pop the top of the stack.  Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if enabled is on the top of the stack.
So Scala's newline-to-statement-terminator rule is "context free" in some sense, but I haven't been able to figure out how to incorporate this push-down automaton in with the rest of the language grammar.


texts:
I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is:

For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L is regular, so is N(L).

How do I go about proving it?


texts: Expected distance between two random nodes in weighted tree

texts:
Given an undirected connected graph with N nodes and N-1 edges.

Out of N  nodes, 1...k nodes are selected, out of which 2 nodes are selected randomly (uniformly).

How do I calculate the expected distance between those 2 points?

By the way, I tried using sum of distance between all pairs of k nodes and divided it by k to get the distance. Denominator is correct. But this gives wrong answer. How do I correct the approach?


texts: Is this the correct way to use the pumping lemma?

texts:
I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not regular. I don't know quite how to apply the lemma and want to understand if I'm doing it right. If I had something like:

w = {anbk, n =/= k}

am I correct in that I can say that:

h = {anbn + r, r > 0} is a subset of w, and thus if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

The way I would show this is as follows:

h = xyz
|xy| <= n
x = an-r
y = ar
z = bn + r
xyz = an-rarbn + r
xy2z = an-ra2rbn + r = an + rbn + r

Thus h cannot be regular since an + rbn + r is not of the form {anbn + r, r > 0}, and since h is not regular w must not be regular, since h is an element of w.

Have I applied it correctly? I understand how to apply it for an easy language like {anbn}, because I can apply the lemma directly to this language, but the only way I could think of for my language was to create a subset that belongs to my language, and apply the lemma to that.

If I haven't applied it correctly, is there a way to show that my language is not regular (or regular), using another lemma, or perhaps with closure properties?

This is a really awesome topic, even if I don't understand the pumping lemma fully, I'm excited to explore it further!


texts: Could the execution of a Haskell program be considered as a proof using equational reasoning

texts:
Could the execution of a Haskell program be considered as a proof in equational reasoning. This follows on from my earlier question on Haskell and inductive proof. Currently I am stuck between morally yes, but technically perhaps no. Below are two Haskell programs together with what I consider to be paper based equational proofs of very simple theorems. I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a), so the proofs use ground terms or values.

-- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
theoremZ = z == 4
-- Paper based equational proof of Prog 1
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
theoremSize =  size (Add (Add Empty 1) 2) == 2
-- Paper based equational proof of Prog 2
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)


texts: Why does Karger's algorithm work "with high probability"

texts:
I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).

It states that a single round of contractions yields a min-cut with probability $\Omega(n^{-2})$ and concludes that $O(n^2 \log n)$ independent contractions are sufficient to find a min-cut with high probability.

It makes sense to me that $O(n^2)$ independent contractions yields a min-cut with a probability of approximately 1. Anything above this increases the probability, but why has $\log n$ being chosen?


texts:
I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me about how many apples does one talking about. Thus, numbers are quite abstract. If somebody asks you "how is it going" you can't answer "10". 10 what? But you could say 10 out of 10. But this is another abstraction. So, what I want to say is that a number is an abstraction. It can only be used to quantify other things. Thus, very often people say that "Number" is a type or set or category, etc. But then if a concrete number is an abstraction what is Number?

I hope you've got my idea and question and sorry if I used some terms incorrectly. I'm trying to study CS on my own and do make lots of mistakes.


texts: Use of Activation Units in Facial Expression Understanding

texts:
The topic of extracting the Facial Action Coding System (FACS) Action Units (AUs) [1] from images and it's translation into emotion prediction [2] is pretty well studied, but I'm not clear on how it stacks up against alternative approaches such as Convolutional Neural Networks (CNN). How much does the accuracy of AUs effect the accuracy of emotion detection?

"Joint Facial Action Unit Detection and Feature Fusion: A Multi-conditional Learning Approach", Eleftheriadis S, Rudovic O, Pantic M. (2016)
"Emotion Detection From Facial Expression And Its Use In The Evaluation Of Stress" Suvashis Das (2013)


texts: Decidability of language L = { n : ∃x∈N, n = 3x+2 }

texts:
I've recently came across this language and I don't know if my hint for proving its class is correct or not.

$$L = \{ n : \exists x \in N, \,n=3x+2 \} $$$n$ is in binary format.

I think $L$ is decidable and as proof I was considering using a canonical enumerator of $\{0,1\}^*$.

For each word $x$ printed by the enumerator, my algorithm would compute $3x+2$ and halt if the result was equal or greater to the provided input.
If equal, then accept, if greater, then reject.

I would like someone to confirm if I'm correct, pointing me in the right direction if I'm not.


texts:
Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?

For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.


texts: Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular

texts:
I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular.
I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got totally confused, what to do now?

Earlier I showed that $L_5=\{a^n b^n : n≥0\}$ is not regular.
In this Language it was very simple to choose $w$, namely $w= a^pb^p$, where $p$ is the pumping length. But this new Language is complicated, so I thought you guys could help me out.


texts: Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?

texts: why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire problem .So what is the difference in terminology of sub-problems in divide and conquer and dynamic programming except for the fact that in the latter case we have overlapping sub-problems since both tend to imply that we have some sub-problems which combine to give an optimal solution to entire problem so in case of divide and conquer can we say that each sub-problem also gives us optimal solution ?


texts: Formula for number of parameters in an undirected graphical (probability) model

texts:
I have googled endlessly, and I cannot find it. Can anyone point me to a reference that gives a way to calculate the number of parameters in an undirected Graphical Model?

Adapting from the similar formula for Bayes nets, this is my guess: if we have variables $1 \ldots k$ where variable $i$ has $d_i$ possible values, and $n(i)$ is the set of vertices adjacent to $i$ in the independence graph, then the number of parameters would be

$\Sigma_{i=1}^{k}(d_i - 1) \Pi_{j \in n(i)}d_j$.

Can anyone verify this, and if it's wrong, point me to a correct solution?

I'm trying to calculate the AIC and BIC scores for graphical models, but to do that, I need the number of parameters each has.

EDIT: To clarify, for graphical model I'm talking about the sub-class of log-linear discrete probability distributions. They're also called Markov Networks. See the Wikipedia article.

The idea is, you have $n$ discrete variables $v_1, \ldots, v_k$, where
$p(v_1 = x_1, \ldots, v_k = x_k) = u_{1}(x_1) \cdot \ldots \cdot u_{1,2,\ldots,k}(x_1, x_2, \ldots, x_k)$ i.e. there is a term for each combination of variables, and the probability is just the product of those terms.

Some of those terms will be $0$, depending on which variables are independent. The model is heirchical if it's , meaning that if a set of variables has non-zero $u$-term, then all of its subsets have non-zero u-terms. The model is graphical if it's heirarchical, and it's specified entirely by the independence graph (where $v_i$ and $v_j$ have an edge iff they are not conditionally independent given the other nodes.)

The number of the parameters is the number of non-zero $u$-terms. It's easy for the binary case, where each $u$ can just be a number, but when there are more than 2 possible values for each variable, it's more complicated, since you need a parameter for each value combination.


texts: Creating a self-affine fractal on L-systems

texts:
Hi I would like to create a self-affine fractal on L-Systems.
The axiom I have created is FF-GGG-GG-GGG++GGG+GG-GGG+GG+GGG+FF++ffGG+GGG+FF+GGG which creates the image below

At each stage I would like to replace each rectangle with the initial pattern. I am not sure how to do this.


texts: How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

texts:
I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive.

I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for all $n \geq n_0$.

The upper limit is easy to prove by taking $c_{2} = \sum\limits_{i=0}^k |a_i|$

I don't know how to prove the lower limit. Any hints?


texts: Can P vs NP be independent of accepted axioms?

texts:
On wikipedia's page on P vs NP it says that think that of 151 researchers surveyed, their thoughts were as follows:

  "126 (83%) believed the answer to be no, 12 (9%) believed the answer
  is yes, 5 (3%) believed the question may be independent of the
  currently accepted axioms and therefore is impossible to prove or
  disprove, 8 (5%) said either don't know or don't care or don't want
  the answer to be yes nor the problem to be resolved."

But can't P vs NP be restated as "Is there a polynomial time algorithm for 3SAT?", since $P=NP$ if there is and $P\neq NP$ if there is not.

It seems like this restatement cannot be independent of the axioms, if it were there would be some spaces where there IS a P time algorithm, and some where there isn't, with both being consistent with the regular axioms -- however couldn't one just use any P-time algorithm in that former group, since it must be consistent with our axioms?

Is there some subtlety that I am missing?

Any recommendations for books/textbooks/further readings that cover P vs NP and related problems in detail?


texts: Exists there an algorithm to determine if a graph is toroidal?

texts:
I was hoping to determine if a particular graph was toroidal.  My first instinct was to use Forbidden Minors, just as I would use the Kuratowski subgraphs to determine if a graph was planar.  After doing some digging I discovered The Robertson Seymour theorem which seems to entail that such forbidden subgraphs do exist, however according to the linked Wikipedia article, citing this paper, the particular subgraphs are currently unknown.

This is kind of a brick wall for me.  I don't recall any other way of computing planarity that might have been abstracted up to toroidality.  What algorithms are known for computing whether a given graph is toroidal?


texts: Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time

texts:
So I have the following language:
C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}
How to prove that this language is in P (decidable in deterministic polynomial time)?
I tried to come up with a polynomial-time algorithm and tried to show a reduction to a different language in P, but couldn't figure it out.


texts: Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class

texts:
I am trying to understand the space and time Hierarchy theorems according to

  Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach

but the more general case.

What I don't understand is why the language decided by our custom machine is in the larger complexity class. For example, with the case of time complexity, the cost of simulating the input machine is $t_1 \log t_1$, so why is the language decided by it in $DTIME(t_2)$ but not in $DTIME(t_1 \log t_1)$?

thanks


texts: Proving that the average case complexity of binary search is O(log n)

texts:
I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations.
But how would I go about proving that the average case complexity of binary search is O(log n)?


texts: What's a good method to decide wheter distributed or parallel computing?

texts:
I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). Currently, using CUDA, I just 'fill' one core on my GPU, having a low memory usage so i'm thinking about filling every multiprocesor by executing the same code. I'm talking, of course, of populating synchronous islands and using them as ecosystems with ocasional information sharing.

I've thought aswell on modifiying my algorithm for being run on a homemade raspberry cluster (not built yet) and treat every raspberry as an island aswell.

My problem is that, without implementing both systems, I don't know how to calculate or estimate what the best approach will be or knowing if the number of cores will result on a better execution time.

I know there are values i'll have to take in consideration, such as FLOPS of both systems, number of CUDA cores or raspberries, memory bandwidth ,etc. But i'd like to make a equation as exact as possible and I don't even know how to start to deal with the problem.

I know that is a very general problem, any suggestion will be listened to. I'm can provide any further information by editing the question

Thank you

Edit 1: In order to clarify the two first comments below this post i'll edit at here:

@Raphael♦
There will be communication about once every 10 seconds, with a transference of a bidimensional array of int[255][10] I'm not sure, maybe (probably) i'll be able to fit the memory of a raspberry. The most important memory size used contains on every thread a matrix of int[255][500]. The communication between the threads have not to be synchronous at all, they could be synchronized with a random couple they found free on that moment.

@TRex22
It's good to know that rasps aren't a good testing evnironement for researching purposes. My algorithm takes an input with an array of two or three points (x,y) or (x,y,z) and calculates the mathematical function f(x)=y or f(x,y) = z. The big matrix i have mentioned before, are DNA which codifies results for productions in a grammar (grammatical evolution). In my current algorithm the bandwith is not REALLY important, because every generation i'll only transfer the best solution (with a size of int[255]). Thanks anyway for your suggestion on OpenMP an MPI, i'll take a look.


texts: What is the practical difference between an neuromorphic processors and GPU's?

texts:
IBM is working on a neuromorphic computer, Synapse, intended for computation based on artificial neural networks.

My question is, what makes these types of computers more efficient at processing neural network algorithms, compared to GPU's?


texts: NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ))

texts:
I'm currently studying for an upcoming exam in theoretical computer science, but one of the exercises is confusing me: in the exercise sheet it says that the NFA $$M=(\{z_0,z_1,z_2\},\{a,b\},\delta,\{z_0,z_1,z_2\},\{z_2\})$$ corresponding to the regular expression $\alpha=(a^*b|\epsilon)(b^*(a|\epsilon))$ is defined by
$$\begin{array}{c|ccc}
\delta&z_0&z_1&z_2\\\hline
a&\{z_2\}&\{z_1\}&\emptyset\\
b&\{z_0\}&\{z_0,z_2\}&\emptyset
\end{array}$$
where $\delta$ is the transition function.

I don't understand how this can be right - if I'm not mistaken, the word $bb$ is an element of $L(\alpha)$ but it's not an element of $T(M)$.

So... basically, my question is: is the exercise sheet flawed or am I misunderstanding the concept of regular expressions?


texts: Is it okay to understand Job Queue Like this?

texts:
I have a hard time understanding the concept of job queue.
Is it right if I understand job queue like the following???
For example, when user click the icon of an exe file, the newly created process is passed to a job queue, and a long term scheduler decides when to allocate memory to this newly created process, depending on CPU limit or RAM limit, and if it is okay to allocate memory to newly created process, a job scheduler takes that memory and put it to the ready queue after memory allocation.


texts: Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm

texts:
I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t know how we insert these terms in the running time equation of the algorithm, and that’s what I want to understand. Also how we evaluate the value of ϵ.

Let suppose we have a algorithm:

M = K * Y
Let’s the running time of algorithm is pseudo-polynomial i.e p(n) * K where k and p(n)  are polynomial in n.
Somebody please guide me.

Zulfi.


texts: Understanding Computer organisation and architecture

texts:
What are some of the books for "computer organisation and architechture" which are best for self study. Such a text that one can grasps the big picture, and understandhow various things are fitting with each other.

Topics include: machine instructions and addressing modes, ALU and data path , cpu control design, memory interface, I/o interface (interrupt and DMA mode), instruction pipelining, cache and main memory.

Thanks


texts: Efficient algorithm to map two differently-sized sets of numbers as closely as possible?

texts:
The problem

I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped if they are farther apart then 0.18. As many numbers should get mapped as possible.

Also, the sets are not necessarily the same size. So, consequently, some numbers of the larger set won't get any mapping.

Example:

Is there a reasonably efficient algorithm that finds a mapping like this? Or, is there a term for this specific problem so that I can research algorithms on my own?

My research

Through googling I encountered this question, which led me to the term "Euclidean Bipartite Matching Problem" which seems to be the term for a problem very similar to mine. However, my problem is slightly different than the Euclidean Bipartite Matching Problem.

So basically, I'm looking for an efficient algorithm for the 1-dimensional Euclidean Bipartite Matching Problem except that the two sets of numbers can be of differing size, and the distance between two numbers must not exceed 0.18.

My attempt

I've already coded my own implementation, however... it doesn't work properly and is pretty complicated too so that I'm not even sure why it doesn't work.

As for the basic idea behind my implementation: let's call the first set the red numbers and the second set the blue numbers (apparently that's the terminology used in the Euclidean Bipartite Matching Problem). Now;

go through all red numbers, and for each:

find the closest blue number within a ±0.18 range
if the blue number is already assigned to a different red number:

if the existing assigned red number is nearer than our red number, skip this blue number

assign our red number to the blue number
if we overwrote a previously-assigned red number in the process, make the red number find itself a new blue number (i.e. make the red number go through steps 1-4 again)

(I'm doubtful that this implementation is even correct) but yeah, this is what I tried so far.

Are there well-known algorithms to do this task, so that I don't have to create a wonky, non-functioning, slow implementation myself? Or in general, is there a term for this specific problem? Then I could google for that term and find what I need.

I'll be happy about any answer or pointers :)


texts: Find Smooth Functions from Discrete Datas

texts:
I'm trying to write a algorithm to solve the following problem, which I did not find any related papers:
Given a set of discrete data points generated by n unknown smooth functions $f_1(x), f_2(x), \cdots, f_n(x)$ at $x_{1}, x_{2}, \cdots ,x_{m}$， how to group these data points into $n$ arrays $a^{(n)}_{i}$ so that the data points in each array come from a single smooth function, i.e.,  $a^{(n)}_{i}=f_{n}(x_i) \forall i$.
For example, if I have a straight line and a quadratic function plotted together in a single figure, I can easily distinguish between these two functions. However, it is very difficult for computer to distinguish these patterns.
This problem seems related to clustering analysis. However, I still didn't find any similar research result about it.


texts: For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE"

texts:
Claim: $3SAT \le_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new formula $f(\varphi)$.

It seemed pretty easy to show that $\varphi\in 3SAT\Rightarrow f(\varphi)\in 4NAE$:

If $\varphi \in 3SAT$, then every clause in $\varphi$ contains at least one $T$ literal. In $f(\varphi)$, let the added literal $z=F$. Then every clause in $f(\varphi)$ contains at least one $T$ and one $F$ literal, so $f(\varphi)\in 4NAE$.

Here's where I'm confused: At first, I thought that if $\varphi \notin 3SAT \Rightarrow f(\varphi) \notin 4NAE$.

We know $\varphi \notin 3SAT$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $\varphi$ containing all true literals, then if $f(\varphi)$ adds $z=T$ to each clause, wouldn't $f(\varphi)$ belong to $4NAE$?

On the other hand, I thought of this argument to show that $  f(\varphi)\in 4NAE \Rightarrow \varphi\in 3SAT$:

Suppose $f(\varphi)\in 4NAE$, where $x_i$ represents original literals in $\varphi$ and $z$ is added literal from reduction. Let $Y$ represent a satisfying assigment of $f(\varphi)$.

If $z=F$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either
$x_1$ or $x_2$ or $x_3$  had to be true. Thus, the original clause $(x_1 \vee x_2 \vee x_3)$ in $\varphi$ would evaluate as true, and so $\varphi$ contains satisfiable assignment.
if $z=T$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either
$x_1$ or $x_2$ or $x_3$  had to be false. Now define the assignment $Y '$ to be identical to $Y$ except with every literal negated, and remove all $z$'s. Then $(\bar x_1 \vee \bar x_2 \vee \bar x_3)$ contains at least one true literal. So $Y'$ is a satisfiable assignment of $\varphi $, and  $\varphi \in 3SAT$.

Basic logic says if p then q should be equivalent to "if not q then not p". So obviously I'm making some mistakes or assumptions here. I just don't see where.


texts: Data hazard or forward in MIPS SW after LW in this case?

texts:
so we know data hazards may occur on data that is not ready yet and we can solve them by forwarding data in between the pipes.

Look at this piece of code:

lw $6, -16($6)
sw $6, -16($5)

So the sw wants the data that comes from the MEM read and it wants it just for the MEM write. So we can use a bypass to forward the output of the MEM to the input of the MEM (in the data write input) and this is solving the hazard without a bubble (nop).

Is it implemented into the MIPS core and if not, what will it do?


texts:
In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented in the Turing machine. So my questions are:

If the Turing machine is as efficient as the RAM machine, then why are we not assuming Turing machine for algorithm analysis?
What is the difference between RAM and TM?


texts: Using Dijkstra to find shortest path in relation to two weight functions?

texts:
I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to find the lightest path from $s$ to $t$ in relation to $w_1$, out of all the lightest paths from $s$ to $t$ in relation to $w_2$.

I get that this question begs for me to modify Dijkstra somehow, but I just can't seem to find the intuition to do so. Any guidance would be appreciated!


texts: Maximizing the weighted average value of a set of items by doubling the weight of a subset of items

texts:
Given a set of $n$ items, each represented by $t_i=(w_i,v_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as:
$$
\frac{\sum_{i=1}^{n}v_iw_i}{\sum_{i=1}^nw_i}
$$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized.

For example, suppose you have the following set of items, where $t_i = (w_i,v_i)$:

$$
t_1 = (12, 1100000)\\
t_2 = (12, 1000000)\\
t_3 = (12, 850000)\\
t_4 = (10, 800000) \\
t_5 = (8, 1200000)
$$
The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight?

Thanks in advance.


texts: Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?

texts:
I'm working with a flow network like the following:

The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, also with capacity 1. X and Y both have edges with capacity 4 to the sink t.

Typically this would have many solutions: all of the ways you could split up A, B, C, and D between X and Y. In the modified version, I have to pick either X or Y. If the flow on (X, t) > 0, the flow on (Y, t) must be 0, and vice versa. So there are only two solutions, sending all 4 units of flow through X or through Y.

I'm wondering if there is a way to reduce this constraint to the standard max-flow so I can just run Ford-Fulkerson on a modified graph. That, or whether this is fundamentally harder and is an isomorphism of a different problem.

In simpler versions like the one I've laid out above you could just reduce the decision to a problem where you have only s, t, and the nodes X and Y and must send 1 unit of flow through the network, but I'm struggling with the general case where we have two edges X and Y, only one of which is allowed to have nonzero flow through it in the solution.


texts: Simplifying this expression with big O when several variables are involved

texts:
I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows :

\begin{eqnarray}
   \mathcal{O}(3m+2 m\cdot n\cdot p+p\cdot(n+m)) &=& \mathcal{O}(m\cdot(3+2n\cdot p)+p\cdot(n+m))\\
                 &=& \mathcal{O}(2m\cdot n\cdot p+n\cdot p + m\cdot p)\\                 &=& \mathcal{O}(n\cdot p \cdot(2m+1) + m\cdot p)\\
                 &=& \mathcal{O}(2n\cdot m \cdot p + m\cdot p)\\
                 &=& \mathcal{O}(m \cdot p\cdot(2n+1))\\
                 &=& \mathcal{O}(2n\cdot m \cdot p)\\
                 &=& \mathcal{O}(m\cdot n \cdot p)\\
 \end{eqnarray}

I successively replace $3+2n\cdot p$  by  $2n\cdot p$, $2m+1$ by $2m$ and $2n+1$ by $2n$ since they are asymptotically equivalent.
Is it correct?

More generally can I always replace any subexpression with an asymptotically equivalent one within the big-O expression?


texts:
When studying Markov models, I see this equation but I don't understand where does it come from:
$$ P(x,y,z) = P(x) P(y|x) P(z|y) = \frac{P(x) P(x,y) P(z,y)}{P(x) P(y)} $$
Can anyone explain to me?


texts:
How are Signed integers different from unsigned integers once compiled?

I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit integers when in binary eg 10000001 if this is a signed integer it would be equal to -127 but if it is unsigned it would be equal to 129. So my question is how can you tell the difference when presented with just 8 binary bits.

And also how are signed integers different from a compilers perspective, and how can a CPU tell the difference while performing arithmetic on them


texts:
I am trying to calculate the First and Follow of the following grammar

S->ABC
A->Aa
A->aB
B->Bb
B-> epsilon
C-> Cc
C-> Epsilon

I have calculated the firsts and it is all good

Follow(A) = {a,b,c,$}

What is confusing me is the follow of B, I get Follow(B) = Follow(A)
But on the other hand, I have a solution for the grammar that states that the follow(B) = {b,c,$}

So which one is the right one?


texts:
I was trying to come up with a formula for the number of swaps used in selection sort. So we know that selection sort gives the minimum number of swaps to sort an array.

The formula I came up with is given an unsorted array and it's descending or ascending order. We find the number of elements dissimilar to the sorted array. When we subtract 1 from this number we can get the number of swaps.

For example,
Let the array be

[3, 4,2 ,9,1]

Using selection sort for descending order:

[9,4,2,3,1] ---[9,4,3,2,1] which gives a total of 2 swaps

My logic:

Descending array is [9,4,3,2,1]. So three elements are in incorrect position which are 9, 3 and 2. So, 3-1 = 2 swaps.

Let us consider ascending order:

Section sort:

[1,4,2,9,3]--[1,2,4,9,3]--[1,2,3,9,4]--[1,2,3,4,9] which gives a total of 4 swaps.

My logic:

Ascending array is [1,2,3,4,9]. So all five elements are in incorrect position from the sorted array which gives a total swap count of 5-1 = 4.

But my logic seems to be incorrect when tested on hacker rank. Could you give me an example where this logic fails. Thanks :)


texts: Reducing lambda expression to normal form

texts:
Can someone explain the steps to reduce
  $$ (\lambda n. \lambda m. \lambda f. \lambda x.\ n\ (m\ f)\ x)\ (\lambda f. \lambda x.\ f\ (f\ x))\ (\lambda f. \lambda x.\ f\ x) $$
to $\lambda y. \lambda z.\ y\ (y\ z)$?


texts:
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?

Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, F \}$, if $w = uv$ and the state of $A$ on input $w$, after scanning $u$ is $q_i$ (when the head is at the beginning of subword $v$); and $A' = \{ Q, \Sigma, \delta, q_i, F \}$ then $w \in L(A)$ if and only if $v \in L(A')$


texts:
My friend asked this problem recently & am not sure which sorting to use for this kind of problem:-

There are 20 stones of different heights. Each stone is so heavy, we need to sort the stones such that smallest stones are to left and highest to right. As stones are heavy make algorithm which moves stone least distance possible

Which sorting method suits this kind of problem?


texts: Algorithm for exploring a parameter space

texts:
I have a research problem which has a general outline as follows:

I have a 2D parameter space, $(\alpha, \beta)$ which serve as initial conditions on some set of partial differential equations. Given values for $\alpha, \beta$ I can integrate this set of PDEs numerically to obtain a result in a 2D phase space $(x,y)$.

Now, suppose I want to work backwards and find the values of $(\alpha, \beta)$, which generate a particular $(x,y)$. I can see a general, crude algorithm as,

Choose a random $(\alpha, \beta)$
Integrate PDE to obtain $(x,y)$
Inspect how close to the desired result we are
Adjust $(\alpha, \beta)$.
Repeat

I feel like there must be a smart/fast way to do this. Can anyone point me in the direction of some algorithms/resources which may be able to accomplish this goal? Thanks


texts: Checking if two statements can be reached in one control flow

texts:
Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. I now want to figure out if it is possible to execute both statements (in order) within the same program execution.

Control Flow Graph: I have a graph with all the statements of the program and edges connecting the statements determining the control flow of the program intra function (i.e., within a function).

Call Graph: I also have edges connecting any function call with the start of the function control flow of the called function.

The literature I found concerning control flow covers only intra function flow analysis and the only correct approach I can come up with is a depth first (or breadth first) search starting from the first statement. This, however, hardly feels correct as it is quite cumbersome and I would expect a better solution.


texts: Complexity of finding the largest $m$ numbers in an array of size $n$

texts:
What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ time. Any comments regarding the proof itself, or the style (i.e. my ideas may be clear but the presentation not).

The original question:

  Given $n$ numbers, find the largest $m \leq n$ among them in time $o(n \log n)$. You may not assume anything else about $m$.

My answer:

Sort the first $m$ elements of the array. This takes $O(1)$ time, as this is totally dependent on $m$, not $n$.
Store them in a linked list (maintaining the sorted order). This also takes $O(1)$ time, for the same reason as above.
For every other element in the array, test if it is greater than the least element of the linked list. This takes $O(n)$ time as $n$ comparisons must be done.
If the number is in fact greater, then delete the first element of the linked list (the lowest one) and insert the new number in the location that would keep the list in sorted order. This takes $O(1)$ time because it is bounded by a constant ($m$) above as the list does not grow.
Therefore, the total complexity for the algorithm is $O(n)$.

I am aware that using a red-black tree as opposed to linked list is more efficient in constant terms (as the constant upper bound is $O(m\cdot \log_2(m))$ as opposed to $m$ and the problem of keeping a pointer to the lowest element of the tree (to facilitate the comparisons) is eminently doable, it just didn't occur to me at the time.

What is my proof missing? Is there a more standard way of presenting it (even if it is incorrect)?


texts: Efficient algorithm to filter off points from a point cloud

texts:
I have a master point cloud, which essentially just a list of points with {x,y} coordinates.

The point cloud is HUGE ( like, it can contain more than 1 million points). The problem now is that I have another (sub)set of point clouds, and I need to check whether the points inside the second point clouds are the same with any of the points in the first point clouds, and then remove them from the list.

The characteristics of the second point cloud:

The second point cloud points are usually clustered in a corner of the first point cloud ( but not always).
None of the points from the second point cloud will lie outside of the first point cloud ( the first point cloud always contain every single point of the second point cloud)

The naive algorithm will be something like this:

   public static List<Point> FilterPoints(Lis<Point> master, List<Point> subset)
   {
    var FilteredPoints = new List<Point>();
    for(int i=0; i< subset.Count; i++)
    {
        var isContained = false;
        for(int j=0; j< master.Count; j++)
        {
          if(subset[i].X==master[j].X && subject[i].Y==master[j].Y)
          {
              isContained = true;
              break;
          }
        }
        if(!isContained)
        {
           FilteredPoints.Add( master[i]);
        }
      }
     return FilteredPoints;
}

But is there anyway to improve over the above naive algorithm in terms of speed, given the known characteristics of the both point clouds?

PS: I've also asked about how to make use of C# language characteristics( if any) in order to improve the speed for the above algorithm at SO.