texts: When computing asymptotic time complexity, can a variable dominate over other?

texts:
I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $n$ strings, each string of length $k$ letters. Using merge-sort, sorting a list of $n$ elements requires $O(n\log n)$. Comparing two strings of length $k$ has a cost of $O(k)$. Therefore, the cost would be $O(kn\log n)$.

However, I know some restrictions about $k$ and $n$ due to the nature of the problem. In particular, I know that for any list, $0 \lt k \leq 20$, and $0 \lt n \leq 80000$. In other words, the number of words in a list might vary in a much larger range than the length of the words.

In that case, would it be correct to say that $n$ dominates over $k$ and therefore the cost could be expressed as $O(n\log n)$? Or does the fact that we are discussing asymptotic costs make those restriction meaningless (as we are describing how the algorithm is impacted by the growth of each variable, regardless of how much they can actually grow)? In general, if two variables are independent, is it possible to dismiss one of them from the asymptotic cost under certain circumstances?


texts: Adding and removing output layer units of a neural network

texts:
I'm fairly new to deep learning, so if terminology makes no sense, please let me know so I can clarify what I mean.

We're working with a neural network for applying classes to inputs. That is, each output unit represents a target class, and its activation denotes the amount of relevance for a given input. The output layer is fully connected to the previous one.

This NN is used for prioritizing and ordering search results, so learning happens online (based on user choices), and the function/mapping we're approximating may shift over time.

Since the domain of our search results is open-ended, the set of target classes may dynamically change over time. Therefore, a fixed set of output units representing output classes doesn't work for us.

Is there any best practice (or at least some research) on adding/removing output layer nodes on already-trained neural networks?
To our surprise, we couldn't find any research papers or other literature discussing this topic.

For what it's worth, our current best idea is to deal with changes in the target set the following way:

For classes vanishing from the target set, remove their corresponding output layer units.
For new classes appearing in the target set, create new output layer units and fully connect them with weight zero (or alternatively, average of existing other edges, or randomized).

With such a solution, we'd expect the NN to remain stable on existing classes, and potentially giving a "disadvantage" to new ones, but this seems acceptable. Are there any other bad side effects that might emerge?


texts: Check array in linear time with a constant space complexity

texts:
Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.
E.g.
[1, 1, 1, 1] - all the elements are the same, so it is true
[12, 20, 1, 23] - all the elements are different, so it is also true
[12, 20, 1, 1] - we have just two 1, so it is false
The easy thing I was able to come up with is to use a hashmap to map an integer to a number of occurrences of that integer in the array. And then to iterate over the hashmap and check if there is at least one entry whose value is greater than 1 and is not equal to the length of the array, then I return false. Otherwise, I return true after the iteration.
The problem with my solution is that it has a linear space complexity and I feel that it should be possible to somehow solve the problem using a constant space complexity and linear time complexity.
So, could someone help me come up with an O(1) space complexity and O(n) linear complexity with respect to the array size solution, please?
I am working on this problem just for fun.


texts: Does a given e-NFA accepts all the Strings?

texts:
Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by it.

Of course the usual way is to construct a DFA, or complement the e-NFA but since we are talking about the whole language, I was wondering if there is a much more efficent method in the worst case.


texts: How to find out what are accept, loop and reject in this Turing Machine?

texts:
I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about...

so accept state would be --> Accept(T2) - all words with a a
                      loop state would be --> Loop (T2) - /\

reject state would be --> Reject(T2) - Strings with b

am I on a right track ? how could I do find accept, loop and reject on this TM? thanks!


texts: How to monitor and alter the value of decision variables using if then else

texts:
Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where :

X[a,b] =  1 if a is in b 0 otherwise

Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise.

I need to ensure that if two elements say k and l are both in f respectively i.e X[k,f] == 1 and X[l,f]==1 then no matching i.e for each (e,d) Y[k,l,e,d] = 0.

Knowing that my mathematical program is of type ILP, how do I write a constraint expressing the earlier statement ? Like I need to monitor both the value of the decision variables and the indices at the same time, is that possible to come up with a constraint ?

Highly appreciate your help.


texts: Is there a branch of CS about studying function calls branching?

texts:
I know little about computer science. I wrote a function that has some ifs and may call itself recursively.
Is there a branch of computer science that studies these possible branches?
I'd like to analyze the possible branches and maybe generate a graph of all of them to study all possible outcomes of my function.
my_func(&mut self, request: Request, retry_count: i32) -> Result<(), FuncError> {
   let response = self.send(request);
   let response = match response {
       Ok(_) => return Ok(()),
       Err(Error::Unauthorized(unauthorized)) => Err(FuncError::Unauthorized(unauthorized)),
       Err(Error::ConnectionClosed) => Err(FuncError::ConnectionClosed{}),
       Err(_) => Err(FuncError::UnknownError{})
   }
   match response {
      Ok(()) => Ok(()),
      Err(Error::Unauthorized(unauthorized)) => {
           self.authorize();
           return self.my_func(request, retry_count -1),
      }
      Err(Error::ConnectionClosed) => {
           self.connect();
           return self.my_func(request, retry_count -1),
      }
      Err(_) => Err(FuncError::UnknownError)
   }
}

I'd like to generate a graph of all possible outcome for this Rust method, considering a small retry_count of 3 for example. Or maybe read more about some theory on how to analyze this function and know more about it, etc.
I don't think there's something ready for Rust, but maybe for C++. Maybe one that I can do manually, without parsing some language.


texts: Password authentication over an insecure connection

texts:
I was thinking a way to send password to server secure way without using secure connection,I found one solution.I want to find flaw in this.(Note: I am begginer,dont judge me, I know little about cryptography and little about networks)

So server contains hashed version of my password.
When i want to send password I send server request to generate me random key(big enough it is less likely to be same ).
Then I hash password and add that hash to key and hash it again.I send that final hash to server.
Server use key and hash the hashed password from database the same way and compare my hash with it.If it is the same,password is correct.

Ex. (Simplified)
I want to send password "test123" to server.
I request random key and server sends me key "999".
I hash "test123" and get lets say "abc" ,and hash "abc999" and get "efg" and
send that to server.
Server recieves my "efg" , then gets "abc" hashed password from database, adds key "999" and gets "efg" ,so "efg"=="efg"  ,password correct.

The someone listening the connection can't use the same hash because it will get different key.


texts: Edmond's Blossom algorithm (Maximum Matching) explanation

texts:
I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here.

Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph algorithm to construct a maximum matching in a graph (matching is a set of edges without any common vertex; maximum matching is a matching with the highest cardinality of this set).

I do understand the idea behind finding augmenting paths and reversing the matching on them to get a matching with one higher cardinality,

  what I don't understand is why odd cycles are a problem in finding an augmenting path (the algorithm says to "shrink" any odd cycle found while searching for an augmenting path).

My best guess is that an odd cycle doesn't allow you to visit some path connected to the cycle because you come back along the same path that led you to the cycle? but I am not sure.

  How does an odd cycle create a problem, but even cycle doesn't?

A simple visual description, if someone can provide, might also be helpful.

Thanks in advance


texts:
I have a number of vector timestamps and have to identify all concurrent events:

I understand why (C, F) and (H,C) are concurrent events; They fulfill following condition:

But shouldn't then also the events (A, H), (B,H) (F, I), (D, I), (G, I) and (C, I) be concurrent?


texts:
Following is the excerpt from wiki

If numerical data are represented in terms of digits (or bits), then
the naive algorithm also entails storing approximately $2n$ times the
number of bits of $x$ (the evaluated polynomial has approximate
magnitude $x^n$, and one must also store $x^n$ itself). By contrast,
Horner's method requires only $n$ additions and $n$ multiplications, and
its storage requirements are only $n$ times the number of bits of $x$.

I don't understand, how?


texts: Generate algorithmically all grid points inside a hypercube

texts:
$\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty}$The problem comes directly from computational mathematics, and can be stated as follows:

Given a regular matrix $M\in\R^{d\times d}$, find effectively all vectors $v\in\Z^d$ such that $\n{Mv}\leq1$, where $\n{Mv}$ is the maximal component of the vector in modulus.

I give an algorithm below, but it's very inefficient, since it has much more steps than the number of grid points. It is still bearable for $d=5$ in my case, but it fails completely for $d=6$, I don't have that much time; moreover, I'd like to make some work on higher dimensions as well.

My current algorithm is based on the following (disclaimer: contains more math):
First, compute $\n{M^{-1}}$. Then, we observe that $\n{v}\leq\n{M^{-1}}\n{Mv}\leq\n{M^{-1}}$. This means that we can compute $L=\operatorname{floor} \n{M^{-1}}$ and then try all vectors $v\in\lbrace-L,-L+1,\dots,L-1,L\}^d$; there is exactly $(2L+1)^d$ of them. (And here lies the problem: if $d=6$ and $L=18$, I get $2.5{\rm\small E}9$ iterations, which is orders of magnitude larger than the number of points I think there are.)


texts: How to implement scheme's letrec in a lazy dialect?

texts:
In SICP, lazy evaluation is defined as delaying the evaluation of procedure arguments until the actual values are needed. (https://mitpress.mit.edu/sicp/full-text/sicp/book/node85.html)

letrec can be implemented by creating a closure (an expression + an environment) and mutating its environment to add a binding to itself. It looks like this in the host language (PLAI, a typed racket similar to ML):

(define (interp expression env)
    (type-case expression
        [letrec (name value body)
                (let (value' (interp value env))
                    (if (is-closure? value')
                        (let (new-binding (bind name value'))
                            (let (new-env (extend-env new-binding env))
                                (begin (set-closure-env! value' new-env)
                                       (interp body new-env))))
                        (interp body (extend-env new-binding env))))]))

In english, (letrec (name value) body) is then interpreted as follows. First evaluate value and if it is a closure then mutate its own environment to point to itself. If it is not a closure then just pass it as is. Evaluate body in a new environment containing this value bound to "name".

Now on to a lazy implementation.

In SICP, lazy evaluation is defined as delaying the evaluation of procedure arguments until the actual values are needed. (https://mitpress.mit.edu/sicp/full-text/sicp/book/node85.html)

So a function application of "fun" to "arg" is interpreted as evaluating "fun" to give a closure and then suspending its interpretation to "arg" until the value is needed (forced) by a strict operation (basically arithmethic primitives and side-effects).

When I try to implement letrec lazily, I fall into a trap.

In (letrec (name value) body) I must evaluate "value" to a closure and mutate its environment to include a binding of name to itself. Then value is fed to body as a function application: ((lambda (name) body) value). But this means that we will evaluate a function's argument strictly: we have to evaluate "value" in order to "close the knot" and make it point to itself.

Additionally, I can't use Y combinators easily because the host language is typed.

How can I get out of this?


texts: $k$-coloring in BPP, implies $k$-coloring in ZPP

texts:
Consider the next problem:

$k$-COL: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?

I need to prove that if $k$-COL is  in BPP, then it is also in ZPP. In other words, show that if there is a probabilistic polytime algorithm that decides whether a graph has a valid $k$-coloring or not with bounded error, then there is also a probabilistic polytime algorithm that does that with zero error.

My attempt

I've managed to prove it assuming that we are allowed to call an oracle that solves the above problem in polynomial time (see below).
But is there a way to show this without assuming $k$-COL $\in$ P?

Let $\mathcal{A}$ be a polynomial time machine with access to an oracle for $k$-COL.

Let $G$ be a graph and let $M$ be the BPP NTM that makes $k$-COL be in BPP. Let's define the following NTM $M'$:

If $G \in$ $k$-COL, execute $M$ on $G$.

If $M(G) = 1$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=1$.
If $M(G) = 0$, output $?$.

If $G \notin$ $k$-COL, execute $M$ on $G$.

If $M(G) = 1$, output $?$.
If $M(G) = 0$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=0$.

Definitions (for reference)

We define the class of languages Bounded-error Probabilistic Polynomial-time (BPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:

$Pr[M(x) \in \{0,1\}] = 1$,
if $x \in L$, then $Pr[M(x) = 1] \geq 3/4$,
if $x \notin L$, then $Pr[M(x) = 1] \leq 1/4$.

We define the class of languages Zero-error Probabilistic Polynomial-time (ZPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:

$Pr[M(x) \in \{0,1,\text{?}\}] = 1$ and $Pr[M(x) = \text{?}] \leq 1/2$,
if $x \in L$, then $Pr[M(x) = 0] = 0$,
if $x \notin L$, then $Pr[M(x) = 1] = 0$.


texts: I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What modifications are required in order to decrease the time complexity of the convex hull algorithm?


texts: Efficient lookup when key is made of multiple elements and elements can be empty

texts:
I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored key is the lookup value or it is a generalised version - index key has empties where lookup value has values. I think the formalisation would be "the lookup value logically subsumes the index-key". I also want the lookup function to return the most specific index-key, that is the key with the fewest empties.

For example, if the data is stored in a (<key>, <value>) tuple with the key being a tuple of the elements and ? representing the empty set/null value:

((1, ?, 6, 3), "hey")
((1, 5, 6, 3), "hi")
((2, ?, ?, ?), "hello")

So lookup((2, 4, 5, 6)) -> "hello". And lookup((1, 5, 6, 3)) -> "hi" because (1, 5, 6, 3) is more specific than (1, ?, 6, 3).

A simple solution is to store them as shown above and simply look through them. This would take $O(nm)$ where $n$ is the number of entries and $m$ is the number of elements in the key. Checking in most-to-least specific would mean a match could be returned immediately.

This there an approach that could improve this?

Thank you


texts: Does the Bellman-Ford algorithm find all the negative cycles?

texts:
The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some?

The algorithm really focuses on the shortest paths, so I'm unclear if it will find any negative cycle or if it might miss it.

Thanks!

EDIT:
I'm only interested in knowing if there is a negative cycle (not where it is). How does one prove that Bellman-Ford would find the existence of a cycle?


texts: Trying to break the proof of undecidability of the halting problem

texts:
Posted this question on cstheory.SE where they said to go here:

  I read the demonstration of the Halting problem, it is done by
  reductio ad absurdum where the push to get to the absurd is to use the
  halting function "H(A,b)" (where A=another function, b=the A
  parameter) as its own parameter. This proofs that can't exist a
  function which takes every function including its own as parameter and
  says if it is an infinite loop or not, but doesn't proof that a
  function Z(A,b) where {A,b!=Z} (1*) can't exist.

While I deleted that question I had this answer by dkuper:

  It is easy to circumvent this problem, by giving to the functions the
  code of a different machine which computes the same function.

  Say you succeeded in building your machine computing Z(a,b) which
  works as you said. Then you still get the reductio ad absurdum, by
  feeding to this machine the code of another machine which is
  equivalent. This is always possible because for every machine M, there
  are infinitely machines M′ which behaves the same as M (i.e. halt on
  exactly the same instances). So checking that the input is not
  precisely the machine M is not enough to avoid the paradox. And
  checking that the input does not behave the same as M is impossible.

So, now, this doesn't work if we assume that the function passed as parameter has a flag (applied by the constructor) that indicates if it is the halt function.


texts: I'm trying to find out which operation is fast, evaluating a comparison vs doing an arithmetic option on a single word (e.g subtract, add). Can anyone point me in the right direction with some blogs, books and other material?


texts: Checking if sequence is almost strictly in ascending order

texts:
This was part of my interview questions.

Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
For instance,
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false
There is no one element in this array that can be removed in order to get a >strictly increasing sequence.
For sequence = [1, 3, 2] the output should be
almostIncreasingSequence(sequence) = true
We can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, we can remove 2 to get the strictly increasing sequence [1, 3].
The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

The conceptual algorithm that the interviewer wanted was below with Java:
boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

but I didn't get the part comparing sequence[i] with sequence[i+1] andsequence[i+2] to increment the counter which are seq1 and seq2. How does this cover all the cases?


texts:
I have encountered the following problem that I found very interesting to solve:

  Given an array of positive integers $\{a_1, a_2, ..., a_n\}$ you are required
  to partition the array into $3$ blocks/partitions such that the maximum
  of sums of integers in each partition is the minimum it can be.
  Restriction: you cannot alter the turn in which the numbers appear
  (example: if you have $\{2, 5, 80, 1, 200, 80, 8000, 90\}$ one partition
  CANNOT be the $\{2, 80, 1, 90\}$). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array $\{2, 80, 50, 42, 1, 1, 1, 2\}$. The best partitioning according to the problem is
$$\{\, \{2, 80\},\, \{50\},\, \{42, 1, 1, 1, 2\} \,\}$$, so the output of the program in this case would be $82$.

I have already thought of a $\mathcal{O}(n^2)$ algorithm, but isn't there any better ( e.g. $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ ) algorithm?

My $\mathcal{O}(n^2)$ algorithm is (it is pseudocode):

  input $n \in \mathbb{Z}$
  Let $m \leftarrow -1$
  Let $r_1 \leftarrow  r_2 \leftarrow r_3 \leftarrow  0$
  Let $A \leftarrow (a_0,...,a_{n-1})$
  Let $S \leftarrow \sum_{i=0}^{n-1}{a_i}$
  for each $i = 1$ until $n-2$ do
  $\quad r_1 \leftarrow (r_1 + a_{i-1})$
  $\quad r_2 \leftarrow 0$
  $\quad$ for each $j = (i+1)$ until $n-1$ do
  $\quad\quad r_2 \leftarrow (r_2 + a_{j-1})$
  $\quad\quad r_3 \leftarrow S - (r_2  + r_1)$
  $\quad\quad \max_{\mathsf{temp}} \leftarrow \max(\max(r_1,r_2),r_3)$
  $\quad\quad$if $(\max_{\mathsf{temp}} < m \, \vee m = -1)$ then
  $\quad\quad\quad  m \leftarrow \max_{\mathsf{temp}}$
  $\quad\quad$endif
  return $m$


texts: Prove that at least as many edges as vertices implies a cycle

texts:
I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin.

  Prove that in a connected graph G with $p$ vertices, $q$ edges, and at least one cycle, $q \ge p$

How do I begin with this question? Any help would be greatly appreciated. Thank you so much.


texts: NP-completeness: Reduce to or reduce from?

texts:
Very simple question, but a mistake I make often enough that I'd love to have a standard reference.

I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $P$, then showing that this solves another NP-Hard problem $Q$ in polynomial time.

Have I reduced $P$ to $Q$ or have I reduced $Q$ to $P$?

Since $Q$ is the problem of known hardness I've chosen, have I reduced from $Q$ or reduced to $Q$?


texts: smallest satisfiability-equivalent formulas (generalized Tseitin transform)?

texts:
What is known about the following optimization problem for formulas in propositional logic:

input: formula $F$
output: formula $G$ in CNF with $\mathrm{Var}(G) \supseteq \mathrm{Var}(F)$ such that  for all assignments $m$, $m$ is a model of $F$ exactly if $m$ is the restriction (to $\mathrm{Var}(F)$) of some model of $G$
measure: size of $G$

The Tseitin transformation realizes the input/output specification in polynomial time but it does not care for size. One would say "why bother" because for Tseitin, the size of $G$ is linear in the size of $F$, and what more could you hope for?

My motivation is to improve bit blasting encodings of (finite domain) SMT problems, and there, even small improvements may be useful.

E.g., $F$ could be the formula that describes multiplication of 8-bit numbers: it has $3\times8$ variables, encoding numbers $a,b,c$; and it is true iff  $ab = c$. One can take any of the multiplication circuits, and Tseitin-transform them, but this may not be the best approach.

I know that reducing CNF size does not always reduce SAT solver runtime, so there could be other interesting criteria (for "propagatability"),
but I'd like to start with some obvious measure.


texts:
Question-
Prove:  Every decidable set is Turing reducible to the empty set.

Can anyone help me with this please?

All reductions tutorials I've seen use practical examples of reduction such as sipser's introduction to computation theory:

"A reduction is a way of converting one problem to another problem in such a
way that a solution to the second problem can be used to solve the first problem.
...
For example, suppose that you want to find your way around a new city. You
know that doing so would be easy if you had a map. Thus, you can reduce the
problem of finding your way around the city to the problem of obtaining a map
of the city"

I don't see how to use this kind of information as a general proof, or how the empty set is even usable to solve anything else in a practical example even.


texts: Faster Algorithm for the isomorphism of graphs of certain types

texts: Let $G = (V_1,E_1)$ and $H=(V_2,E_2)$ are two graphs. It is given that $l_1$ many edges (known to us) of $G$ will map to $l_1$ edges of $H$ in any isomorphism of $G$ and $H$. If I remove $l_1$ edges of $G$ (keeping the end vertices) then new graph is $G'$ and graph obtained after removing $l_1$ edges (keeping the end vertices) from $H$ is $H'$. It is given that isomorphism of $G'$ and $H'$ can be performed in polynomial time (say p). The algorithm to solve the isomorphism of $G$ and $H$ will take $O(l_1! p)$. Is it possible to solve the isomorphism of $G$ and $H$ in faster than $O(l_1! p)$


texts: A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given almost tree graph $G$ with distinct edge weight costs that computes a minimum spanning tree of $G$ in time $O(n)$?


texts: How can I measure the usability of a catalogue?

texts:
This question might seems vague but heres the context:

When we are focusing on HCI we would most likely be interested on knowing first how the user usually deals with a certain object. We then try to see how our system could take away one of the tasks he would do himself and try to do it itself.

The object of my interest here is a simple paper catalogue. How would you measure its usability (paper one).
Then, how would you map it to a system interface? How would you measure the usability now on the system?
How would you compare the two usabilities measures?

This question narrows down this approach which is suggested on Stones book - User Interface and Evaluation.

What the catalogue is about is not the point, that why I left it without a description: To avoid suggestions trying to measure what the catalogue is about. My focus here is on the particular mapping of this kind of object on the real world as a simple paper and when it is mapped to a system interface. Assume the catalogue to consist of rows and tables, where each matching row and table gives you a suggestion and you must first reason about each row and each column to see if it suits you (Perhaps you would suggest another template for the catalogue?).


texts: For how large graphs can we still check for isomorphism?

texts:
Let $G_1,$ $G_2$  be two arbitrary graphs with $n$ vertices and we want to check if they are isomorphic.

Question 1.  For what maximal value of $n$ we can actually perform such verification?

Question 2.
Is there any result like as  a list of all non-isomorphic graphs up to $n$, and what is the value of $n$ — 10, 20?


texts:
From , the proofs by the probabilistic method are often said to be non-constructive.

However,  a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms
 By Rajeev Motwani, Prabhakar Raghavan:

  We could view the proof  by the probabilistic method as a randomized
  algorithm. This would then require a further analysis bounding the
  probability that the algorithm fails to find a good partition on a
  given execution. The main difference between a thought experiment in
  the probabilistic method and a randomized algorithm is the end that
  each yields. When we use the probabilistic method, we are only
  concerned with showing that a combinatorial object exists; thus, we
  are content with showing that a favorable event occurs with non-zero
  probability. With a randomized algorithm, on the other hand,
  efficiency is an important consideration - we cannot tolerate a
  miniscule success probability.

So I wonder if randomized algorithms are viewed as not constructive, although they do output a solution at the end of each run, which may or may not be an ideal solution.

How is an algorithm or proof being "constructive" defined?

Thanks!


texts: How does the system know how to read the correct block from a disk?

texts: I am watching this video (https://www.youtube.com/watch?v=aZjYr87r1b8) and up to the ~6 minute mark, he explains the disk structure and how when you want to read a block, the spinner spins to the correct sector and the arm to the correct track. How do the spinner know where the correct sector is? How does the arm know where the correct track is? And how do they know they are reading from the beginning of the block and not in the middle of it?


texts: Representing "but not" in formal grammar

texts:
I just came across the following grammar definition:

  CommentChar ::

        SourceCharacter but not LineTerminator

But for discussion, I'll present this similar construct:

  Digit ::

         '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

  Zero ::

         '0'

  NonZeroDigit ::

         Digit but not Zero

Is this "but not" construct common in formal grammar specifications?  If there a name for it?

I realize that NonZeroDigit could be defined by "manually" expanding the nonterminals and finding the  difference -- here that process is as straightforward as it gets.  But for more complicated "but not" constructs, I imagine that would be painful and error-prone.

Or, in grammars that support it, is this just considered just a sequence of (a) a negative lookahead (for Zero) combined with (b) the nonterminal for Digit.


texts:
I'm wondering if if is possible to have a function $f$ such that there exists $x,y$ such that we have $f_t(x) > f_t(y)$ where $f_t$ denotes the true value of $f$ and $f_a(x)<f_a(y)$ where $f_a$ denotes the value of f as stored in a computer? (I am referring to floating point numbers and numerical analysis)

I am looking at programs that solve equations and so am concerned about if my programs will work in extreme cases. Things like if I have a function that is extremely close to $0$ in an absolute sense over the interval and I want to find the root. (In this case I think I can make an argument that if $f_t(x) \geq 0$, then we must have that $f_a(x) \geq 0$.) But if I'm looking for a maximum of a function that is almost constant, say $g$,  then I don't think I know that $g_t(x) > g_t(y)$ implies that $g_a(x) > g_a(y)$. Is this correct?

Any other resources on this matter would be greatly appreciated.


texts: semaphore implementation with test and set

texts:
I'm trying to understand the algorithm for implementing semaphores on SMP system using test and set instruction described here:
https://people.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf

(and a bunch of similar implementations on the web).

Locking semaphore looks like this:

void P(Semaphore s)
{
  Disable interrupts;
  while (ldl(s->lock) != 0 k !stc(s->lock, 1));
  if (s->count > 0) {
    s->count -= 1;
    s->lock = 0;
    Enable interrupts;
    return;
  }
  Add(s->q, current thread);
  s->lock = 0;
  sleep(); /* re-dispatch */
  Enable interrupts;
}

I have a number of questions about this.  One is -- what is enabling and disabling of interrupts for?  It seems that the whole reason we are using test and set is that interrupt disasbling is not feasible on SMP systems.
Then, what does the sleep() followed by enable interrupts mean?  Does it mean that we do whole sleep with interrupts disabled?  That can't be right as it defeats the purpose of sleeping.
And if we first enable interrupts and then sleep, doesn't it mean that we have a possibility of missing a wakeup after lock is set to 0 but before we sleep?


texts:
I am a little bit confused about how to calculate the memory capacity.

word=data lines size
byte=8 bit
n=adresse lines size

  Most of the people use this formula to calculate the capacity of the
  memory: C=(2^n*word)/8 octet

Is this formula correct when speaking about byte-addressable? Because if we have byte-addressable memory, I think the capacity will be 2^n octet.

If this is correct why people use the formula in all cases? If not can you please explain why to me?

Thanks you.


texts: Proving that $S_1+S_2 \leq f^{-\omega(1)}$

texts:
I am trying to show  for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $  . For a particular $S_1,S_2,f$. Does it suffice to prove there exists M1, for corresponding $S_1$, with $S_1(x,y,z) \leq (f(x,y,z))^{-c} $ and $M_2$ for $S_2({x,y,z)} \leq (f(x,y,z) )^{-c} $?

This is in the same spirit as showing $O(S_1+S_2) \leq T$ can be done by showing individual upper bounds.

All functions are  strictly positive increasing functions.  In particular, $f$ is not a constant.

I am trying to show that there for large enough $x,y,z$, $S_1 + S_2$ is smaller than the inverse of any polynomial in $f$.

I am looking to solve it for a particular case of $f=x^2 y^2+xz\ log (xz)$ but general answers are also appreciated.


texts: Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?


texts: On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb_slides.pdf, while defining L2 and U2, why are we taking min for both?


texts: Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$

texts: I've tried but I can't figure out any solution. Is there any hint for me to solve the question?


texts: Optimal scalability of a distributed algorithm

texts:
What's the optimal scalability of some algorithm when I implement it in a distributed manner?

Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes. I.e, if algorithm A takes T units of time with 1 computing node on input I, it can't run faster than T/n units of time  with n computing nodes on the same input I.

Is my intuition correct or are there some weird counter-examples to it?


texts: deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

texts:
Thanks a lot for your help.

I want to understand what really causes what I suppose to be a deadlock:

I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t really matter for my problem)

I have a container (list) of Couples, where a Couple simply is: 2 Words and 1 couple-Key.

I have a function that is suppose to do some calculation on the list of Couples,  it might modify the letters and the key during the calculation , but when the calculation is finish we can stock the result and reset it to the initial values.

Considering a code that uses a parallel for loop to get the results of all my couples. This uses a lock on the first word and then a lock on the second word before calling the getResult() function, why could a deadlock happen ?

My first idea was that if we have :

Couple 1 : A B

Couple 2 : B C

Couple 3 : C D

Couple 4 : D A

Couple 5 : A E.

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

My intuition is that, someway deadlock might occur if a cycle pattern appears in my list of Couples. On the other hand, I am unable to build an example that explains a deadlock appearance without considering one of these event:

simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment (quite unprobable to me).
a thread takes the priority to a former one (example:well I can't find any, finally I thinks it s equivalent to simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment. It's just that, considering a big cycle, the probability that it happends is as high as the proportion of time required for a calculation over the number of threads.

Am i right with my analysis ?

If the cause of the eventual deadlock is not due to the "simultaneously " event, I'd be glad to know what causes it, or happy if more precision to deadlock probability appearances depending on number of threads or length of cycles etc... are discussed .

Actually, I kind of have 10^5 Couples 10^4 Words.

Thanks,

Guillaume


texts: Showing that Subset Sum Reduces to 3-Partition

texts:
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.

This is a classic NP reduction question, except with the twist of it being a partition of 3 subsets instead of 2.
To prove that it is NP-complete I need to show that some NP-complete problem reduces to this problem. So I want to show that the subset sum problem reduces to this 3-Partition problem.
This is a solution to the 2-Partition problem that I understand. If someone could show me what needs to be modified for the 3-Partition version that would be great. I don't think it's as easy as considering $T$ $\cup$ $\{s-3t\}$ rather than $T$ $\cup$ $\{s-2t\}$, but perhaps it is.
EDIT: Would I have to do something like Subset Sum $\le_p$ Partition $\le_p$ 3-Partition? Or is there a way to go directly from Subset Sum $\le_p$ 3-Partition?


texts:
folks. My question is about explaining the each step of regular expressions. The task is to find the regular expression that contains 101 as a substring. I already know that the regular expression for this is

$$ (0 + 1)^*101(0 + 1)^*. $$

The question is that how we should show each step for explaining the regular expressions.


texts: Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?

texts:
I was reading the Paxos notes from yale from the following link:

http://pine.cs.yale.edu/pinewiki/Paxos

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was trying to better understand the revoting mechanism to avoid deadlocks in Paxos. The revoting mechanism is explained as follows in the article:

  The revoting mechanism now works like this: before taking a vote, a
  proposer tests the waters by sending a prepare(n) message to all
  accepters where n is the proposal number. An accepter responds to this
  with a promise never to accept any proposal with a number less than n
  (so that old proposals don't suddenly get ratified) together with
  the highest-numbered proposal that the accepter has accepted (so
  that the proposer can substitute this value for its own, in case the
  previous value was in fact ratified).

The bold section is the one that I was trying to understand better. The author tries to justify it with:

  "...so that the proposer can substitute this value for its own, in case the
  previous value was in fact ratified..."

But I didn't really understand why the proposer would want to ratify the previous value. By doing this, what crucial safety property is he guaranteeing? Why is he responding with that and not something else? Responding with the highest could be problem, right, since the current proposal would get lost?


texts:
I have recently implemented Dijkstra's Algorithm to the shortest path between all pairs of nodes in the graph. I have implemented this code in Java. As instructed I am using a linked list to represent the adjacency matrix. As instructed, I am running my algorithm for a complete graph. The running time for a 1000 node complete graph is about 361 minutes. For 2000 nodes, my program has been running for close to a day, and it is still running.

I would like to run this for a complete graph of 6000 nodes but the running time is going to be too long. I am wondering, if this is too be expected.

Bob


texts: how to solve simultaneous equation with O(n)

texts:
Does someone know how to solve the below?

Assume that the array $A$ is already sorted.
And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that

$A[i] + 4A[j] = A[i] + 5A[k] = 0$.

I came up with an algorithm that uses two double for-loop for each i, j and i,k. But the complexity will be $O(n^2)$..


texts: How do I go about constructing a game tree that does not duplicate any states?

texts:
Many games have states that can be reached via multiple paths in their gametree.

For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks like this:

   /---V---V---\
   |   |<K>|   |
   D---+---+---C
   |   |   |   |
   D---+---+---C
   |   | K |   |
   \---A---A---/

When both your own and your opponent's King move left and right (or vice versa) the game has returned to the same state (there is no castling).

The state space of this game is rather small (even if we ignore symmetry) and amounts to only 9*8 + 9 + 9 = 90 states.  But a game may last an infinite number of turns given that the kings can keep moving back and forth.

How do I go about constructing a game tree that does not duplicate any states, for this game, and more generally?


texts: How storage affect if we use tertiary language?

texts:
as we uses binary language in all the computer systems around us which consist of 0s and 1s (Off and On) bits. Let assume that someone is developing a computer system based on tertiary system -1, 0, 1 three states. The question is that how will it affect the storage of computer systems?

DUPLICATION: this question is different. Here the aspect is only of "storage"


texts: prove that a language is context free given a regular language

texts:
R is a regular language over $\Sigma=\{0,1\}$
$Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$
I need to prove that Sub(R) is context free.

I know that the quotient of a context free language with a regular language is context free
but I can't seem to continue for there..


texts: What does the notation $ [ i \neq k ] $ mean?

texts:
I can't figure out what the notation $[x \neq k ]$ means. Here's a bit of context:
The formula is:
$Pr[A_i^k = 1] = \frac{[i\neq k]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 \text {  if } i = k \\ \frac{1}{i-k+1} \text{ if } i \gt k
 \end{cases}$
and is part of a chapter where the average expected time of operations of a randomised treap are proved.
$A_i^k$ is an indicator variable defined as $[ x_i \text{ is a proper ancestor of }x_k ]$ where $x_n$ is the node with the $n$-th smallest search key.
That probability comes up because $\text{depth}(x_k) = \sum_{i=1}^{n} A_i^k$ and $\mathbf{E}[\text{depth}(x_k)] = \sum_{i=1}^nPr[A_i^k = 1]$.
I have no access to the pages that explain the notation since I'm studying from a pdf of a few pages taken from a book.


texts: An O(n log sqrt(n)) sorting algorithm? Skiena TADM 2nd Question 4-28

texts:
Skiena writes:

  In one of my research papers [Ski88], I discovered a comparison-based sorting
  algorithm that runs in $O(n\log\sqrt{n})$. Given the existence of an $\Omega(n \log n)$ lower bound for sorting, how can this be possible?

I believe the research paper he is referring to is Encroaching lists as a measure of presortedness, and the $O(n\log\sqrt{n})$ algorithm is Melsort.  I don't have the full text of the article, but the abstract states that melsort has [time] complexity $O(n\log m)$, where $m$ is the number of "encroaching lists" present in the input and $n$ is (presumably) the size of the input.

I suspect that the solution to Skiena's apparent paradox hinges on expected running time vs worst case running time.  He notes in the abstract of the '88 paper that melsort is "linear for well ordered sets and reduces to mergesort and $O(n\log{n})$ in the worst case."  If the expected number of encroaching lists, $m$, is $\sqrt{n}$ (as apparently conjectured by Skiena, according to wolfram's article on encroaching lists), it would follow that melsort's expected runtime is $O(n\log\sqrt{n})$.

But wikipedia states that "A comparison sort must have an average-case lower bound of $\Omega(n \log n)$ comparison operations," citing Cormen et al.  Checking the referenced pages of Introduction to Algorithms, I see only a proof that the worst-case runtime has that bound. Is the Wikipedia article incorrect?


texts: lower bound of checking if in array are two different elements

texts:
Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $ n-1 $.
Consider the diagram hasse. This diagram must be consistent (one piece), so you need at least $ n-1 $ edges (comparisons),.

However, I would like to consider a decision tree. Unfortunately, I can not consider this, look how I think about it.


texts: Using pumping lemma to show a language is not context free(Complicated)

texts:
How can i show that the following long language is not context free using the pumping lemma?

$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

And how can I conclude from that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language?

I have been struggling with it for many hours, would really appreciate an explanation I can follow and learn from. The examples given in class are simpler and not on that level, and I don't know which z to take and how to break it in order to deduct in a proof that L is not context free.

Could you please give a slow explanation so I could learn fast?

My attempt for the first part:

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=abc^{p_1}bc^{p_2}...bc^{2p_i+2}def^{p_1}ef^{p_2}...ef^{2p_i}ghq^{p_1}...ghq^{2p_i-1}$. vxy cannot contain c,f,q's, We'll divide it into the following cases based on vxy. Don't know how to divide it or how to continue, would really appreciate your assistance with it. Very important to me

My attempt for the second part(I don't understand it well enough to solve the first part, I will ask for your help with it):

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=0^p1^p2^p$. vxy cannot contain a,b,c's, We'll divide it into the following cases based on vxy:

Doesn't contain 0: pumping S with 0 to obtain $uv^0xy^0z=uxz$. in this case, there are fewer 1 or 2, so not in L.
There's 0 but not 2: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 0's than 2's, so it is not in L.
There are no 2's: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 1's or 0's than 2's, so it is not in L.

Since each option was checked and each one contradicted, It can be safe to assume that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language since it does not adhere to the pumping lemma.

Thank you very much


texts:
I read the lecture 4 of CS162 (UC Berkeley: https://inst.eecs.berkeley.edu/~cs162/sp17/static/lectures/4.pdf), but I got little bit confused about the meaning of the keyword "buffered" they used when mentioning the following informations:

  Kernel buffered reads

  Kernel buffered writes

  Data buffered automatically by C-library functions

What does each of 'buffering' and 'buffered' mean?


texts: An example of a context-sensitive grammar for a given language

texts: Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?


texts: is modulo of hash function is evenly distributed?

texts:
if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?

so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ?

Thanks


texts:
I know there's some easy proof for this, but why is $A \leq_T \bar{A}$ ? ... Suppose that $\bar{A}$ is c.e. and could loop, does this mean that the oracle $TM$ $M^{\bar{A}}$ could also loop?

But shouldn't $\leq_T$ mean that $M^{\bar{A}}$ be decidable?


texts: Why finding out an independent set of size k is in NP-C and not in P?

texts:
I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P.

P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is any positive integer.

P2: Given graph G(V, E), find out whether there exists an independent set of size 5 in the graph.

I cant get my head around this! I believe both should be in polynomial order.

Reason: $\binom{n}{5}=O(n^5)$ and so should $\binom{n}{k}=O(n^k)$.

Can anyone please explain whether I am right? or if not, what am I doing wrong?

Thanks in advance!


texts: If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa

texts:
If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$?
Here is my shot.
Case 1: $\overline{A} \leq_T B$
This is only possible if $A \leq_m B$ exists and $B=\overline{B}$. As you can transform any many-one reduction to its complement, we can show that if $A \leq_m B$, then $\overline{A} \leq_m \overline{B}=B$. Thus $\overline{A} \leq_m B$.
Case 2: $A \leq_T \overline{B}$
This is the same as above but we need to change the role of $A$ and $B$.


texts: Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta

texts:
So far I've understood that because of the definition of $\Theta$, we have
$c_1n^2 \le f(n) \le c_2n^2$.
I'm not sure how to proceed from there.


texts: Is there a similar categorization to Elementary Cellular Automata?

texts:
Elementary cellular automata show different systems and fractals like rule 30, rule 90, and rule 110. I want to know if there is another classification or type which shows similar structures just like in elementary cellular automata (ECA).

For example what other systems can show structures similar to Sierpinski triangle (which is the same as rule 90 in ECA)?

Is there a method to build rule 30 or 60 using other system than ECA?


texts: $\mathrm{\oplus P^{BPP}\subseteq BPP^{\oplus P}}$

texts:
Toda showed long ago that $\mathrm{PH\subseteq BP.\oplus P\subseteq BPP^{\oplus P}}$. That somehow describes the power of Parity Non-deterministic Computation.

If we swap the base and the exponent of the relativized class $\mathrm{BPP^{\oplus P}}$ to obtain yet another relativized one, namely $\mathrm{\oplus P^{BPP}}$. Then what have we obtained? A bigger or a smaller class?


texts: Efficient Median Algorithm With Very Constrained Operators

texts:
What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are not allowed. The algorithm I have come up with so far seems very inefficient and goes like so:

For an array of length n, create a working array of length 2n by
doing pairwise Max() comparisons for every pair of elements in the input
array. This 2n array is guaranteed not to contain the lowest value from the original (or one fewer of the lowest value if there were ties for the lowest value)
Recursively call (1) n/2 times
Take min() of final array

There's got to be a faster algorithm!


texts: How to optimize the return given the stock price of all time?

texts:
There is a list of N stocks.

In M days, the stock price is given. Assume that each stock has only 1 price per day. Assume that these prices are constant.

We start with an amount of money K.

For each day we can buy and sell an arbitrary number of stocks. In the last day, we have to sell all the stocks we have to get back cash.

The question is:
1) How to build a strategy that buys and sells stocks that maximize the cash in the end?

2) Given the constraint that the amount of money we hold at any time cannot be negative, what is the best strategy?

For instance, if we have only 1 stock and the price is:

1 7 3

The best strategy would be spending all the money to buy in day 1, sell everything on day 2 and do nothing on day 3.

Update: my very naive approach (for the case when there is one stock only) is a heuristic one - buying on the first day and then selling when the price is higher than buying price, then buying again when the price is lower than the previous selling price.


texts: Technique behind the way google earth overlaps polygons on top of pictures

texts:
What´s the technique behind the way google earth overlaps polygons on top of pictures(like the ones users assign to streets and houses) ?

It seems to be aware of perspective, and I don´t remember seeing it covered on books on computer vision.

Thanks,

Rafael


texts: Context free grammar problem for number of a's is twice the number of b's

texts:
Can you to find for me a context free grammar for the following language?
$$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$
Here $\#_a(w)$ counts the number of $a$'s in $w$.


texts: How to understand the CRC Algorithm from the CAN specification?

texts:
I am trying to understand how the cyclic redundancy check (CRC) algorithm from the Controller Area Network (CAN) specification works. Here is the pseudocode.

CRC_RG = 0;                         // initialize shift register
REPEAT
CRCNXT = NXTBIT EXOR CRC_RG(14);
CRC_RG(14:1) = CRC_RG(13:0);        // shift left by
CRC_RG(0) = 0;                      // 1 position
IF CRCNXT THEN
   CRC_RG(14:0) = CRC_RG(14:0) EXOR (4599hex);
ENDIF
UNTIL (CRC SEQUENCE starts or there is an ERROR condition)

I do understand the standard algorithms but not the CAN algorithm. I have calculated it by hand and programmed it and it works fine. I just don't understand why/how it works.


texts: Is there a "flaw" in the backpropagation algorithm?

texts:
While trying to find a better backpropagation algorithm, I came across a paradox in my algorithm and then I found out this also happens in the usual backpropagation algorithm.

Our neural network looks like this:

In this simple example, we have no biases. The activiation function is the usual
$f(x)=\frac{1}{1+e^{-x}}$

Our training set is just one datapoint: input = 0.9 and target_output = 0.9. The learning factor is set to 0.1.

The paradox happens when w2 is randomly initialized to a negative value. First, let's take a look at the "normal" situation (where the paradox does not happen). Let's say w1 and w2 are both positive, but the output is less than 0.9. w1 and w2 are both initialized at 0.1. Then to reduce the error, both w1 and w2 are increased, so the the output will get closer to 0.9. This is visible in the next graph (x is the training iteration, each training iteration contains one backpropagation).

Now let's take a look at the situation that w1 is intialized at 0.1 and w2 is initialized with a negative value (-0.5). Initially, an increase in w1 would cause a more negative value for the output layer, which increases the error. However, that's only the case because w2 is negative. Although w1 will decrease in the beginning, it will start increasing as soon as w2 becomes positive. The blue line (w1) is clearly decreasing in the beginning in the below graph from my experiment:

This "wrong" learning in the beginning of the blue line w1, is a consequence of using the derivative of the error function to induce small learning steps. Would it be better to somehow anticipate a positive w2 that will be needed anyway and so increase w1 from the beginning instead? Can we make a better backpropagation algorithm?


texts: If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

texts:
I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time?

Problem statement: Given a set of formulas in CNF in Łukasiewicz logic, I want to find an assignment for the variables in some truth set T_k, for some k, such that the assignment maximizes the number of satisfied formulas. I wanted to model this problem into CSP or SAT, hence my question. The SAT problem for CNF Łukasiewicz logic formulas is solvable in linear time. So, maybe we can take advantage of that.


texts: Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

texts:
Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation
$$W \cdot W^{T} = M,$$
where $M$ can have negative entries.


texts: Big-O notation for nested loops that might skip iterations

texts:
When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately?

Hypothetical example:

var n = input.length; //eg, [1,4,6,2,0,8]

for (var i = 0; i < n; i++) {
  visited[i] = true;

  for (var j = 0; j < n; j++) {
    if (visited[j] === true) {
      continue;
    }
  }
}

Another example:

function dfs(node) {
  if (visited[node]) {
    return 0;
  }

  visited[node] = true;

  var edges = edges[node];

  for (var i = 0; i < edges.length; i++) {
    dfs(edges[i]);
  }
}

//dfs(graph_that_has_cycles);


texts: If a problem is in P solved via dynamic programming, is it also in NP?

texts:
So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.

My answer is, "Since it is also polynomial time solvable, the problem is also in $NP$".

Is that a correct statement? If not, is a problem in P solved via dynamic programic also NP?


texts:
How can I represent an array when I am writing to show an algorithm in writing paper. Like Pi is represented by Greek letter. We use that Greek symbol to denote the value of Pi, Kind of like a pointer.

So, is there any general symbol for representing array?


texts: Efficient algorithms for dealing with linear algebra over the rationals

texts:
I'm an academic mathematician.  While trying to verify a counterexample to something in my research, the following computational problem has arisen:

Fix a vector space $V = \mathbb{Q}^n$.  Here $n$ is something on the order of $20,000$.  I have a procedure that spits out a sequence of vectors $\vec{v}_1,\vec{v}_2,\ldots$ in $V$.  The vectors $\vec{v}_i$ all have integer entries; these entries are bounded in size (by something on the order of 20 or 30).  For each $k \geq 2$, I need to decide if $\vec{v}_k$ is in the $\mathbb{Q}$-span of the set $\{\vec{v}_1,\ldots,\vec{v}_{k-1}\}$.

What algorithm should I use for this?  The naive thing to do would be to just use Gauss-Jordan elimination (or, if I want to mostly stick with integers, compute the Hermite normal form).  However, experiments I have done show that the size of the numbers that arise when you do this explode in complexity even for much smaller problems.  This accords with stuff I have found while searching the literature, though I don't know the computer science literature very well and have trouble determining the state of the art in stuff like this.


texts: Correct approach to Mapping Reduction from $E_{TM}$

texts:
as the title states, I am trying to figure out if my approach to solving mapping reduction from $E_{TM}$ to some other language is correct. As you surely know, $E_{TM} = \left \{ < M> \mid M \ is \ a \ TM \ such \ that \ L(M)= \emptyset \right \} $. What i am trying to check is whatever a string x is in L(M). My idea is to analyse $<M>$ in oder to check if there are any transition to $q_{accept}$, if so then L(M) cannot be empty. Now let's take another language, for instance let $REVERSE_{TM} = \left \{< M> \mid M \ is \ a \ TM \ such \ that \ L(M) = L(M)^{R} \right \} $ or even $REGULAR_{TM} = \left \{< M> \mid M \ is \ a \ TM \ such \ that \ L(M) \ is \ regular \right \} $.
Let's prove that $E_{TM} \leq_{m} REVERSE_{TM} $. Since i need to convert an istance "yes" w of $E_{TM}$ trought a function f, to f(w) which is an instance "yes" of $REVERSE_{TM}$. $f(<M>) = <M^{'}>$, where $<M^{'}>$ is a TM whose behaviour on input x is

if $x \neq x^{R}$ then accept.
if $x = x^{R}$ then,

analyse $<M>$ and if there are no transitions to $q_{accept}$ then accept
else do not accept x

Which language does M' recognize? It should recognize $ \Sigma^{*} $ if $L(M) = \emptyset $ meanwhile it should match $ \left \{ x \in \Sigma^{*} \mid x \neq x^{R} \right \} $.
We know that $(\Sigma^{*})^{R} = \Sigma^{*}$, so $<M'> \in REVERSE_{TM} <=> L(M) = \emptyset$. I think this mapping reduction should be correct but is it correct to let M' analyse M in order to figure out if L(M) is really empty (if it's empty there should be no transition to $q_{accept}$) ? Or is there another way to solve these reduction from $E_{TM}$ ?


texts: Dynamic programming and probability - list of problems

texts: Does anyone have a list of problems where you have to combine dynamic programming  with probability?


texts: Shortest path for vehicle routing problem with alternative locations

texts:
I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations.

Right now, I'm trying to find the shortest path in term of cost for a given order of clients. For the moment, I made an algorithm that labels each location with the routes that can go to this location.

Here is a scheme for an example I have (I only completed the first four columns):

each column represents a client and its locations
black arrows represent rounds that do depot -> Emplacement X -> depot
green arrows represent rounds that do depot -> Emplacement X -> Emplacement Y -> depot
red arrows represent rounds that do depot -> Emplacement X -> Emplacement Y -> Emplacement Z ->  depot
there are probably examples with bigger rounds
crossed out arrows are for emplacements that can't be reached (because of the time window)

With my example, the shortest path to only deliver the first two clients costs 265 and does:

depot -> Emplacement 3 -> Emplacement 16 -> depot (the round costs 265)

And the shortest path to only deliver the first three clients costs 508 and does:

depot -> Emplacement 3 -> depot (the round costs 186)
depot -> Emplacement 13 -> Emplacement 11 -> depot (the round costs 322)

What would be the best approach for creating an algorithm that finds the shortest path to deliver every client using the labels generated by my algorithm?

Edit: I tried doing recursion to try each possible route and keep the best. This solution kind of works when there are few clients and few locations but when there are a lot of clients/locations, the computation time explodes


texts: Given a set of integers $S$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time

texts:
Given a set of integers $S=\{s_1,s_2,...,s_n\}$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time.

I am not quite sure how to solve this but I think I have the workings of a start in progress.

If we say the last number we choose is $s_i$, then this reduces the problem to finding a subset of $S\backslash\{s_i\}$ that adds up to $T-s_i$.

I am having trouble coming up with a recurrence relationship for this because I am not sure how I would ensure the solution works. In other words, if there is a number $s_i$ that cannot be used in the subset that adds up to $T$, I am not sure how to express this.

I am thinking that the stopping conditions for the recurrence would be when all elements of $S$ are greater than $T$, in which case there is no solution, or when we find an element equal to $T$.

Could anyone point me in the right direction here and perhaps give more details about how to write a proper recurrence relationship for this problem?


texts: Efficiently finding $k$ smallest elements of Cartesian product

texts:
Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + \dots + x_n$, where $x_i\in A_i$.

I can't simply create all combinations in memory and sort them because of large amount of data.

For example, I have 1000 drinks, 1000 main courses and 1000 desserts. I want to find the 100 cheapest meals but I can't store all 1,000,000,000 elements in memory.

Additional details

I have Drinks, Main Courses and Desserts already sorted.
I've found some solutions like Efficient sorted cartesian product of 2 sorted array of integers but only for 2 lists. For greater amount of sets it still memory-consuming.
Lazy generating next "sorted" value will be useful.
If no efficient exact algorithm, it could be heuristic or approximation algorithm.
It's similar to X + Y sorting problem , efficient faster than O(n^2 * log n) solution is unknown

Question:

Are there an efficient ways to get only $k$ cheapest(*) elements of Cartesian product?
(*) Price of the result element is sum of all numbers in that element.


texts: Online algorithms and changing past decisions

texts:
We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.35).

I wonder if there are instances of online problems such that the competitive ratio does not decrease even if the algorithm is allowed to change its decisions ?


texts: Early Deadline First (EDF) scheduling in real-time systems feasibility test proof

texts:
I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu: http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf
It is based on Early Deadline First(EDF) scheduling.
It says the proof is similar to the proof for Theorem 6.1 on page 124-126. However, I am still stuck.
Here is what I have so far:
Density of task $T_j:\ \delta_j=\frac{e_j}{\min{\left(D_j,p_j\right)}}$
Density of the system: $∆=\sum_{j=1}^{n}\delta_j=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}$
$e_j$ is the execution time for task $T_j$
$D_j$ is the deadline for task $T_j$
$p_j$ is the period for task $T_j$
$\emptyset_j$ is the phase for task $T_j$
$r_{j,b}$ is the release time for task $T_j$ at period $b$
$J_{j,b}$ is the job for task $T_j$ at period $b$
$\emptyset_j=r_{j,1}$
$r_{j,b}+p_j=r_{j,b+1}$
THEOREM 6.2. A system $T$ of independent, preemptable tasks can be feasibly scheduled on one processor if its density is equal to or less than $1$.
If $D_j<p_j$ for some $j$, then $∆=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}\le1$ is only a sufficient condition so we can only say that the system may not be schedulable when the condition is not satisfied.
I try to prove the contrapositive just as Theorem 6.1 on page 124-126. So what I try to prove is that if according to an EDF schedule, the system fails to meet some deadlines, then its density is larger than $1$.
Suppose that the system begins to execute at time $0$. And at time $t$, the job $J_{i,c}$ of task $T_i$ misses its deadline. Assume the case that the current period of every task begins at or after $r_{i,c}$, the release time of the job that misses its deadline. We use $t$ to divide two types of task besides task $T_i$ as in below figure: 1) tasks with deadline happens before $t$ in the current period just like $T_f$, 2) tasks with deadline happens after $t$ in the current period just like $T_k$.

$J_{i,c}$ misses its deadline at $t$ tells us that any current job whose deadline is after $t$ is not given any processor time to execute before $t$ and that the total processor time required to complete $J_{i,c}$ and all the jobs with deadlines at or before $t$ exceeds the total available time $t$. So we have
$t<\left\lceil\frac{\left(t-\emptyset_i\right)}{p_i}\right\rceil e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{\left\lceil\frac{\left(t-\emptyset_f\right)}{p_f}\right\rceil e}_f$
then
$t<\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq i,f\neq k}\ e_f}$
And it is
$=\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq k}\ e_f}$
$\le \left(\frac{t}{p_i}\right)e_i+\sum_{k\neq i,k\neq f}{\left(\frac{t}{p_k}\right)e}_k+\sum_{f\neq i,f\neq k}{{\left(\frac{t}{p_f}\right)e}_f+\sum_{f\neq k}\ e_f}$
$=t\sum_{h=1}^{n}\frac{e_h}{p_h}+\sum_{f\neq k}\ e_f$
$\le t\sum_{h=1}^{n}\frac{e_h}{\min{\left(D_h,p_h\right)}}+\sum_{f\neq k}\ e_f$
$=t∆+\sum_{f\neq k}\ e_f$
So I prove up to $t<t∆+\sum_{f\neq k}\ e_f$
but I cannot prove $∆>1$


texts: Time complexity version of the Church-Turing Thesis

texts:
There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine."

I'm wondering if there's an analogous statement for time complexity, i.e. an argument that if some language is decided in $\Theta\left(f(n)\right)$ on a universal turing machine, then we should say its time complexity is $\Theta\left(f(n)\right)$.

This isn't equivalent to the CT thesis - e.g. quantum computers decide precisely those languages which are decidable in a non-quantum TM, but they may run that decision procedure more quickly.


texts: ARM STM instruction: page fault problem with MMIO

texts:
The ARM STM instruction is described here in the ARM manual.
This instruction writes all or a subset of registers at memory locations starting from a base memory address.
The manual does not impose any restriction on the start address. So, can the start address be such that some/all of the writes end up in MMIO address?
If so, there can be a problematic scenario where a page fault happens in the execution of the STM instruction:
Suppose the base memory address is b and 10 registers are to be written. The range b to b+5 belongs one page and the range b+6 - b+9 belongs to the next page. Suppose the virtual first page (where b belongs) is mapped to a physical page that corresponds to MMIO. Suppose the next virtual page is mapped to DRAM. Suppose that whe the STM execution tries to do the 7th write, to the address b+6, a page fault happens because the DRAM page is swapped out. The page fault handler loads that DRAM page and restarts the STM instruction. The first 6 writes (b to b+5) will be done again. Because these writes go to MMIO which can be mapped to devices, this operation may not be idempotent, e.g. it can launch some missiles twice!. The first 6 writes should not be repeated.
How do page handlers handle this problem, if they handle it at all?

The STM instruction is just an example. The same problem happens with any instruction that does multiple writes that span different virtual pages.


texts:
What is the difference between switches, flags and options when you want to specify something on the command line? Are they all synonyms?

Are there any reasons why some terminals require:

-op1 --option2

and others:

/option1 /option2

and when processing data, some require:

--data file.txt

and others:

/data=file.txt

or even:

/c:data=file.txt

?


texts: How do I show that a DFA accepts only one word?

texts:
I want to show that

$\qquad\displaystyle O = \{M : M \text{ is a DFA}, |L(M)| = 1\}$.

Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this problem.

Should I do something like this?

M = On input (M',w) where M' is a DFA and w is a string:

 - If M' accept only one member, accept.
 - If more than one or less than one accepted, reject.

But this will loop the program forever for the first step as it keeps testing every member after one member is selected. First step just doesn't seem right.

I think these questions might be relating to this: 1, 2


texts: Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)

texts:
I am having trouble finding the solution to this interview-like question:

$T(n)$ is given as:
$$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n > c, \end{cases}$$
where $c$ is some constant.
Find a function $f(n)$ so that $T(n) = \Theta(\log\log\log\log n)$.


texts:
Let $f$ be a Boolean function.

Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$.

Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with degree $d_p$.

Does $\exists p:d_p\leq d\leq d_p^c$ hold with some constant $c>0$?

$d_2\leq d\leq d_2^c$ does not hold with some constant $c>0$.

Counter example at $\Bbb F_2$.

$IP_n=\sum_{i=1}^nx_iy_i\bmod 2$ does have $d_2=2$, while $d=\Omega(n)$.


texts: Maximize length of side of triangle from points on a circle

texts:
Given a circle with $n$ points, among all triangles we can make using these points, we want to find a triangle with maximum length of its shortest side in $o(n^2)$.
We try to make a relation between this problem and convex hull but we can't. Any help be appreciated.


texts: How are programming languages and foundations of mathematics related?

texts:
Basically I am aware of three foundations for math

Set theory
Type theory
Category theory

So in what ways are programming languages and foundations of mathematics related?

EDIT

The original question was "Programming languages based on foundations of math"

with the added paragarph of

And implementations of theory
1. Type theory in Coq
2. Set theory in SETL
3. Category theory in Haskell

Based on a suggestion this was changed to "How are programming languages and foundations of mathematics related"

Since this is one of those questions were I did not know enough about what I was asking but wanted to learn something, I am modifing the question to make it more valuable for learning and others, yet leaving the details in so as not to make the current answer by Andrej Bauer seem off topic.

Thanks for all the comments and the answer so far, I am learning from them.


texts: Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

texts:
Consider the following local search approximation algorithm for the unweighted max cut problem:
start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you can move 1 or 2 vertices from one side of the partition to the other, or switch between 2 vertices on opposite sides of the partition, in a way that improves the cut, do so.

I know that this algorithm is a 2-approximation algorithm. I want to prove that this approximation is tight. That is, the algorithm is not an $\alpha$-approximation algorithm for any $\alpha < 2$ .

I found an example for the tightness of the "regular" local search approximation algorithm of max-cut, where at each iteration, you can move only 1 vertex from one side of the partition to the other, and can't switch between two vertices on opposite sides. The example is of the complete bipartite graph $ K_{2n,2n} $. If the initial cut includes $n$ vertices from each side of the graph in each side of the partition, the cut will include half of the edges, while the optimal cut will include all of them. The "regular" algorithm will not be able to improve the cut from this initial position.

However, this example doesn't work for the algorithm described on top, because we can improve the cut by switching between two vertices from opposite sides of the partition.

Can someone please describe an example or a give clue for an example that can prove that the approximation is tight?
Thanks.


texts: What should I do with a bunch of 16-17 year olds to get them interested in computer science?

texts: I'm going to be involved with a sort of 'open day' at my university in a few weeks. As part of this time, I (along with a coworker) am being given a whole bunch of high-school level students for two hours, as well as a computer lab big enough to contain them all, and I have to do some kind of activity or set of activities with them to encourage them to do computer science (at my university, ideally, but in general also). I am at an absolute loss as to what to do here, and welcome any and all suggestions.


texts:
I've been doing the HPC course from Udacity (https://classroom.udacity.com/courses/ud007/l)

One of the problems is as follows (apologies for the image, as I was unable to format this using $\LaTeX$):

Here, we assume a RISC processor. The text says:

  For consistency with the rest of the text, we use MIPS64, the 64-bit version
  of the MIPS instruction set. The extended 64-bit instructions are generally designated
  by having a D on the start or end of the mnemonic. For example DADD is the
  64-bit version of an add instruction, while LD is the 64-bit version of a load
  instruction.

Here F,D,E,M and W refer to the five stages in a pipeline i.e Instruction Fetch, Instruction Decode, Execution/Effective Address Cycle, Memory Access and Write-Back Cycle.

Is the give solution correct?

My attempt was:

Here, in the second instruction i.e DADDI , there are only two stalls. But since there is no operand forwarding, I believe the contents of the register be available after they've been written into the register file and so, there should be three stalls.

From what I could understand in this solution, the value from the register file is available after the M stage, before it is written. Is that possible?


texts: Why all problems are not in P complexity?

texts:
İf Somebody wants to play perfect chess.I consider for finding solution to this problem,possible minimum data compression method which describes with 10 bit maximum possible data is in the range of 2^10.Then with some formula which can take input as next move in the chess,There should be some formula that can change all equations which are in the chess solving algorithm.Therefore ,if we assume in the chess.There should be 10^120 possible games.With approximately 400 bit with if conditions we can calculate all possible game's best strategy and with same thinking way all math problems can be solved with P complexity.Why there are differences with complexity classes?Short answer:İn karnaugh map some variation cannot be described shortly.
I understood my mistake vote to delete.


texts: Proof of the undecidability of the Halting Problem

texts:
I'm having trouble understanding the proof of the undecidability of the Halting Problem.

If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ for both $a$ and $b$?

Why can't we feed $H()$ with $P$ and some arbitrary input, say, $x$?


texts:
I just recently learned about the existence of this hierarchical temporal memory (HTM). I already read the document Hierarchical Temporal Memory: Concepts, Theory and Terminology (by Jeff Hawkins and Dileep George), which seems rather easy to understand, but one red flag is that the document is neither peer-reviewed nor attempting to explain why it should work in details.

I tried to look around for some independent sources. I found a few papers that compare its performance against others, but none explain why it performs well (or not). I noticed some comments claiming that it was looked down by mainstream expert, but I was unable to find any actual criticisms.

What are the criticisms regarding the performance of HTM? Since HTM is meant to be generic, any domain-specific criticism should be related to a more fundamental problem.

Furthermore, there are a huge amount of training data to use, enough even for multiple months training session. Basically, any criticisms regarding size or length of training is not relevant.


texts: Syntax directed translation part of which compiler phase?

texts:
I am reading dragon book for compilers. I am not able to understand in which phase does syntax directed translation actually happen.

A CFG can have set of semantic rules attached to it which is evaluated. For example, we can have semantic rules attached to a CFG which adds the type of identifier in the symbol table. Does it happen in syntax analysis or semantic analysis phase?


texts: Smallest possible integer not obtained from sumset

texts:
Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A)

What is the best way of finding the smallest number ($S$) that can't be obtained from the sum of any subset of C?

i.e.
if $A=\emptyset$, the smallest number $S= 1+\sum_1^Nx$,
but if $A\ne \emptyset,\ S\leq 1+ \sum_1^Nx-\sum_{i=0}^na_i$,
However if $N=10,A=\{2\}$, then $S=2$, and that is something that I'm not sure how to get efficiently.

I can obviously bruteforce the solution, but I can't find a better way, and I don't know how these kinds of problems are called so that I could Google them.


texts: What is the reason that is FFT multiplication slower than other methods for small N?

texts:
I've seen plenty of statements in papers and on websites that Fast Fourier Transform-based multiplication algorithms are slower than other multiplication algorithms for relatively small input size N, and I've seen plenty of data in papers and on websites demonstrating that this is the case, but nothing I've come across has bothered to explain what causes FFT to be slower for small N.

I would guess that the overhead is due to getting the input into a form that FFT can swallow, but I'd like to know what the actual cause of the overhead is and whether it can be reduced.  Note that I'm not talking about switching from some FFT implementation to another method when N is below a certain size as many implementations do, but the source of overhead in the FFT itself and what can be done to reduce it.


texts: 2 Dimensional Subset Sum: looking for information

texts:
I do not know if this problems exists with a different name, if it is, I could not find it.

The problem is this:

  Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ such that the points of $A$ sum up to $(0,0)$?

If we restrict in $\mathbb{Z}$ this is the classic Subset-Sum problem. Furthermore this can be generalized in n-dimensions if all points are in  $\mathbb{Z}^n$.

Since Subset-Sum is NP-complete so would be this problem thus, I am intrested in approximating it. (Here there is another issue, even for the classic Subset-Sum: since the target is $0$ how the approximation ratio be represented? Maybe using the largest integer or the mean of $S$?)

Subset-Sum has an FPTAS but I don't think that that is the case for the 2D Subset-Sum. One idea is to solve only in the $x$ dimension and from all the addmisable  solutions pick the one that minimizes the sum in the $y$ dimension. But this cannot guarantee a ratio for the $y$ sum.

Does anyone has any information for me? Even bad news (inapproximability) are good news. The only close problem that I manage to locate is the Weighted Distribution problem (set of binary vector and ask if there is a subset that sums to the zero vector) coming from coding theory, proven to be $W[2]$-complete in this paper, thus not in EPTAS.

EDIT 1: Now I look at it again, I do not think that Weighted Distribution is similiar. It is more alike the classic Subset-Sum since every bit vector can just represent a number. Now I am looking at multidimensional Knapsack.

EDIT 2:An idea to tranform it to 1D-SS is to take the xx' (and after the yy' projections). The xx' projection will give you a good x value but for the y axis we cannot guarantee anything. Another approach, generalizing the classic SS aproximation idea (see here and here) is to create rings in $\mathbb{Z}^2$ but this also does not work good. Maybe if we take multiple projection and choose the best?


texts: Why doesn't A* give the optimal path for navigating from A to R in this state space?

texts:
Well, I have heard that the A* algorithm is optimal and complete. However, when trying to navigate from A to R using A*, it outputs the path, A --> E --> R, although there is a shorter path, A --> M --> R. My question is, is that possible for A* to be not optimal sometimes? if not, what am I doing wrong here? Any helpful advice is highly appreciated.

The question: In the following diagram, A is the start node and R is the goal node. Arcs are labeled with the value of the cost function; the number gives the cost of traversing the arc. Heuristic function value for each node is given within brackets. Using A*, find the route from A to R.

This is what I tried. But what I'm getting is not the optimal path.


texts: Physical significance of Don't cares in Digital Logic design

texts:
In many Digital functions we come across don't care conditions where we use don't cares to minimize functions.
What is the significance of these don't cares in real world scenario where we actually implement the functions using logic gates?


texts: Please help me fix / finish this Fitch proof, I am stuck

texts:
Using the Fitch application and only Intro and Elim rules (& REIT if necessary), prove that
$$\forall x \forall y (P(x) \implies Q(y)) \iff (\exists x P(x) \implies \forall y Q(y))$$
is a logical truth (i.e. prove it from no premises)
I am attaching a screenshot of my work so far, please give me feedback and/or assistance so that I can fix or finish this proof. I am currently stuck and don't know if what I did is right or not because I don't know what to do next. Any feedback is appreciated.
Thanks.


texts: How to show that all 2-terminal SP-graphs are O(log n)-outer-planar

texts:
I am trying to show that every 2-terminal SP-graph is $O(\log(n))$-outer-planar for a challenge question on my assignment. In particular, I am trying to prove this by induction on the number of combinations (either a series or a parallel combination). This is what I have so far.

The base case on $0$ combinations is that we just have some edge $(s, t)$. Clearly this is outer-planar and so $O(\log(n))$-outer-planar as well (in this case, $\log(2) = 1$, so this does hold).

Now we do the inductive step. Given some 2-terminal outer-planar graph $G = (V, E)$, we will show that it is $O(\log(n))$-outer-planar, where $|V| = n$. Since $G$ is a 2-terminal outer-planar graph, it was either the result of combining two graphs $G_1$ on $n_1$ vertices and $G_2$ on $n_2$ vertices by series or by parallel. So we have two cases two consider.

The first case is when $G_1$ and $G_2$ were combined by series. By induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. Since $G$ was combined by series, it has $n = n_1 + n_2 - 1$ vertices, where $n_1, n_2 \ge 2$. Let $n_0 = \max(n_1, n_2)$. Then $G$ is $O(\log(n_0))$-outer-planar since we have not added any layers to $G_1$ or $G_2$ by combining them. It follows that $G$ is $O(\log(n))$-outer-planar since $n_0 \le n$.

In the second case, $G_1$ and $G_2$ are combined in parallel, meaning that $G$ has $n = n_1 + n_2 - 2$ vertices. Again by induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. However, this time we cannot conclude that the number of layers around $G$ is the same.

This is where I am stuck. I understand that we are at-most doubling the amount of vertices in $G$ by combining them in parallel, but I don't know how to use that to argue that the number of layers in $G$ is $O(\log(n))$. Any help would be appreciated since I've been stuck on this for several days now.

EDIT: Now that the deadline has passed for my assignment, I would love to have a solution so that I can prepare for my midterm exam (solutions to bonus/challenge problems are never posted).

Terminology

Series-parallel graphs (SP-graphs) are constructed in the following way. A two-terminal graph is a graph with two distinguished nodes $s,t$. A single edge connecting $s$ and $t$ is an SP-graph. If $(G_1,s_1,t_1)$ and $(G_2,s_2,t_2)$ are two SP-graphs, then their serial composition is an SP-graph, and their parallel composition is an SP-graph. The serial composition is obtained by identifying $t_1$ with $s_2$; the new terminals are $s_1$ and $t_2$. The parallel composition is obtained by identifying $s_1$ and $s_2$, and $t_1$ and $t_2$; the new terminals are $s_1=s_2$ and $t_1=t_2$. SP-graphs are the minimal class of graphs generated by these operations. See Wikipedia for more on this class.

$k$-outerplanar graphs: A planar embedding (i.e. an embedding without crossings) is $1$-outerplanar if all of the vertices belong to the unbounded face. For $k \gt 1$, a planar embedding is said to be $k$-outerplanar if removing the vertices on the outer face results in a $(k − 1)$-outerplanar embedding. A graph is $k$-outerplanar if it has a $k$-outerplanar embedding.


texts: Find Hamiltonian cycle in polynomial time

texts: I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only possible in exponential time.


texts: Leftist Heap doesn't support DecreaseKey operation?

texts: I'm studying data structure. When I read the chapter of heap, something really confused me. DecreaseKey's time complexity of the binary heap is O(lgn). However, I found somewhere on internet claimed that Leftist Heap doesn't support DecreaseKey operation. But I wonder why? Can't we simply treat leftist heap as binary heap to perform DecreaseKey?


texts:
Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).

For any vector $w \in \mathbb{R}^n$ and any number $c \in \mathbb{R}$ we define the LTF (x) gate as the function, $\{0,1\}^n \rightarrow \{0,1\}$ such that $LTF(x) =0$ if $c + \vec{w}.\vec{x} \leq 0$ or else $LTF(x) = 1$.


texts: Proving that vertex labeling is NP-complete

texts:
Given a graph $G=(V,E)$, all the vertices $v \epsilon V$ are labeled with values from $\{1,2,...\ldots n\}$ where $|V| = n$ such that for all edges $(x,y) \epsilon E$ such that $|label(x) - label(y)| \ge 2$. We have to determine whether such a labeling is possible for a graph.

Now I have to prove that doing so is a NP-complete problem. While showing that it belongs to NP is straightforward, I am unable to think of which NP-complete problem to be considered for reduction in polynomial time to this problem as part of the proof?


texts: Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

texts:
I have many questions which related to this topic.
I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths  of all vertex by asking about each vertex whether it's weighted higher than edge plus previous vertex.
The point is, I don't understand since we are in DAG why isn't DFS alone enough to find shortest paths. Both weighted and unweighted.
I also don't understand why we need a stack in topological sort. If you were to perform a DFS on some DAG. It will automatically produce a topological sort, if you do a pre-order DFS traverse.


texts:
Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$

I'm trying to write a grammar for this language?
I tried this:

$S \to S_1 \mid S_2 \\
S_1 \to aXb \\
X \to aXb \mid aaXb \mid aab \\
S_2 \to aYb \\
Y \to aYb \mid Yb \mid b \\
$

What do you think?


texts: Crafting a dataset to train a NN that recognizes image styles

texts:
In this paper the authors show how to use two NN that respectively recognize an art style and an image content to apply style filters to photographs.

However, I am confused about how would one train a NN to consistently identify the style of a given author, given that the dataset cannot be too big (an author may paint around ~100 famous canvas in his life?) and normally you need a really big dataset to train for such a thing.

I am just being pessimistic about NN capacity to learn from small datasets or is there a technique for expanding a dataset which could be used in this context?

Reference: A Neural Algorithm of Artistic Style, by Leon A. Gatys, Alexander S. Ecker, Matthias Bethge


texts:
I'm working on a project that needs an advertisement targeting algorithm.  I don't know much about the space, so I'm here to ask how to get started.

The interesting thing about this problem is that I have no access to ad performance metrics.  So the targeting algorithm will have to be rule based, not an ML algorithm that optimizes for clicks.  For instance, advertisers will say 'Show this ad to iOS users from Australia'.

Let's assume I have several features (user's IP address, browser, etc) and a large number of advertisements, each with a few matching rules which evaluate to true/false for a given input of features.  How can I efficiently match the advertisements to the input?  I'd like to know the list of ads that match, and maybe a score based on the number of matching rules and some weight coefficient for each type of rule.

Naively, I could store all of these ads/rules in memory and evaluate all of them for each input.  This seems like it would be slow, and once there are bajillions of ads, it seems like it would be impossible to hold the ads in memory on one machine.

Ideas?


texts: Shifted Big Os. How to say O((n+c)!) = O(n!)?

texts:
Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is
$nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$
Strictly, there is no constant factor that would make $n!$ greater than $(n+1)$, but it seems pointless to indicate that there is a constant shift.
Is it ok to write $O((n+c)!) ≈ O(n!)$ or even $O((n+c)!) = O(n!)$, when $c$ is constant?


texts: Using pumping lemma to prove irregularity of regular language - what is my error?

texts:
I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong?

L={ab}, assume the language is regular so by the pumping lemma there exists some n, and σ = αβγ and σ' = αβ^kγ ∈ L for all non negative k.

σ = aaabbb

α = aa

β = ab

γ = bb

then σ'= αβ^2γ for k=2, σ' =aaababbb

σ'∉ L, a contradiction, thus L is not regular.

L as described I know to be a regular language so I would expect to find ∈ L. This is due to my choice of β spanning across two characters but there is nothing I can find in the pumping lemma which forbids this.


texts: Linear time labeling algorithm for a tree?

texts:
I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in the obvious way until all vertices have a label. The reason I do this is I want to store the vertices in a queue, and go through them "leaves first". Is there an easy way to do this $O(n+m)$ time?

I can solve the problem by doing a BFS on every step. But in the worst case, on every step I go through every vertex, remove exactly two leaves and enqueue them. I believe this takes quadratic time.

Another idea was to first find all the leaves, and then do a BFS from every leaf. This doesn't give me the desired solution. For example, consider a kind of "crown graph" as in the figure below. The desired solution is shown, but launching a BFS from each leaf would result in only two labels used.

Ideally, the linear time algorithm would also be easy to explain and implement.


texts: Coming up with a loop invariant for the partition section Quicksort?

texts:
void partition(int a[], int L, int R) {
int i = L;
int pivot = a[R];
 for (int j = L; j < R; j++) {
     if (a[j] <= pivot) {
     swap(a[i], a[j]);
      i++;
     }
  }
swap(a[i], a[R]);
}

My code is above. My loop invariant is "At the beginning of the iteration, j is in the range of a[L] to a[R-1]". Is this correct? Or if it is not am I on the right track. Thank you.


texts:
Peter (P), Mary (M), Otto (O) and Dicky (D) would like to rent an apartment house. The house has three floors: G/F, 1/F, 2/F. Every floor has only one apartment. P, M, O and D must be assigned to exactly one floor. Note that more than one person can live in the same apartment. Consider the following constraints.

P and M cannot live in the same apartment.
D must live on a higher floor than O.
D must live alone.
If P and O live together, they must be on 1/F.
If P and O live separately, one of them must live on the 2/F.

How do I use AC-3 to solve this question?
I found two possible solutions: P,M,O,D = 2,0,0,1 or 1,0,1,2