texts:
I am learning the Quicksort algorithm and I am struggling with understanding the time complexity.

Here is the JavaScript ES6 code for the partition function that is used in the algorithm:

let partition = function(arr, low, high) {
  let pivotValue = arr[low];
  let i = low;
  let j = high;

  while (i < j) {
    while (i <= high && arr[i] <= pivotValue) {
      i++;
    }

    while (arr[j] > pivotValue) {
      j--;
    }

    if (i < j) {
      // swap arr[i], arr[j]
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  arr[low] = arr[j];
  arr[j] = pivotValue;

  return j;
};

I read that there is n work done for a single invocation of the partition function because there is n - 1 work being done in the while loop and 1 unit of work being done when copying the pivot back.

I don't understand why there is n - 1 work done in the while loop. As per my understanding, every time you make a comparison between the array value and pivotValue (arr[i] <= pivotValue or arr[j] > pivotValue), that is a unit of work being done.

So aren't there actually n units of work being done in the while loop, for a total of n + 1 in the partition function?


texts: Confused between 2 phase locking and 2 phase commit

texts: I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. But don't they both achieve the two things? don't these goals imply each other in the end?


texts:
Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no two people in $S$ know each other? Show that the problem is NP-Complete.

Clearly this resembles the Maximum Independent Set problem, however, I am having trouble seeing how to do the reduction. My idea is to generate a graph $G'$ such that vertices represents people and an edge between two vertices means those two people know each other.

The problem is, this graph can be disconnected so any ideas as to how this can be reduced?

EDIT:

Take for instance this graph $G'$

One possible Maximum Independent Set is clearly $\{2,3,7,5\}$ but does it matter if the graph is disconnected?


texts: I follow a course in Computer Architecture and I'm making exercises on number conversions. Now one of the questions asks me to convert 251.5625 to octal and hexdecimal base. No further info is given. Would this mean that I have to convert it and just ignore the point? Or what's the convention on something like this?


texts: find all paths from source to destinations and then calculate the path with minimum cost

texts:
I am trying to solve one problem. Please refer complete problem statement before proceeding.

You are given a road network, with N cities and M bi-directional
roads. Each road has some positive amount of tax associated to
it,meaning if there is a road connecting cities A and B with tax C,
you will need to pay C rupees to the government every time when you
use this road.
but you have a wildcard which can be used at most K times and when you
use wildcard while using a road, you do not need to pay tax associated
with the road.
You are planning to visit one city this weekend, due to limited budged
you want to estimate minimum passible cost from you home-city to every
other city, so that you can choose the destination according to the
budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=[i-j-k-l] do following
   for(int i=0;i<k;i++){
           int weight=findEdgeWithMaxWeight(p);
     cost of path p=cost of path-weight;
    }

I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.
Consider following diagram to visualize my approach.

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?
Edit: Hope Problem is bit clearer now.


texts: How to efficiently get frequency of subranges and update its values altogether?

texts:
I'm trying to solve the following problem:

There are N notes in an array (2<=N<=105) labeled 0..N-1, all of them initially set to 1. Then there follows Q operations to perform in the array (1<=Q<=105).

The task for each operation is:

Find the most frequent value between the inclusive range [A,B].
Add that value to all elements in the same range. The new values must be in range [0..8], then we take it modulo 9.

At the end, output all array values.

This is the first problem of "Maratona de Programação da SBC – ACM ICPC – 2017" here in Brazil, and I'm trying to solve it in the URI Online Judge site. Time Limit: 1 second.

First I tried SQRT Decomposition because it looked good, but it's not. This week I came up with a few nice ideas to solve it using Segment Tree. I was so sure my code was perfect... but it wans't. Time limit exceeded again.

I don't have Advanced Data Structures classes, I learn those things by myself. So I'm probably lacking some fancy tree structure that would solve this problem really faster. Please, give me some resource to learn such a structure.

Here is an Ideone link to my code. Let me describe the few nice ideas using Segment tree that I mentioned above:

Storing the difference (delta) instead of values. With that I was able to update the ranges without going to the leaf nodes. And to find value of some node, ex: leaf node [0,0] for N=8, I can traverse from root to that node and sum up delta values [0,7].delta + [0,3].delta + [0,1].delta + [0,0].delta.
Store in each node the count of every value [0..8] in its descendants and itself. Because each node represents a subrange, then the frequencies can be precalculated.
Instead of recalculating the subrange array of frequencies, I can rotate it. Ex: If the most frequent note is 3, the previous quantity of values 2 is now the quantity of values 5, and so on... so rotating makes sense instead of calculating the quantities of descendant nodes again.
This is the most brilliant, I think. Instead of rotating, use the value (calculated using delta since root path) to find which index of the frequency subrange array should be treated as the first index 0.

I spent more than twenty hours over this week since the first version of the segment tree approach. It was not easy to think all the ideas I listed above. I know I'm not the best at it. But I think you can feel how frustrated I am, after getting Time Limit Exceeded in all of my attempts.

I also think I evolved since the Square Root Decomposition approach. The problem is that I am out of ideas to improve it further. If I didn't see that 156 people have already solved it. I would think it is impossible.

Please, share a bit of your knowledge with me. Thanks in advance.


texts: How to get a heatmap of pixel influences from a Convolutional Neural Network

texts:
If I have a CNN model (let's say I'm using Tensorflow and Keras) that I've trained for a particular task. For example, let's say I've trained it to detect the difference between an apple and banana. For a given input image, is there a way to generate a heatmap overlaid on the original image that indicates which parts of that image influenced the network's decision?
I'm guessing that you'd have to use the chain rule to get the partial derivative of the loss function with respect to each pixel, and the normalize those values and heatmap them. Is there a library or existing method that does this?
How would I do this if I had a CNN mapping to predictions for more than two classes?


texts: Can we split a vector into positive and negative parts in LP?

texts:
Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v_1&\dots&v_{n}\end{bmatrix}$ can we write as $v=v_+-v_-$ where $v_+$ agrees with $v$ on non-negative components and is $0$ otherwise and $v_-$ agrees with $v$ on non-positive component and is $0$ otherwise.

Eg: $v=[-1,-3,4,5,0,0,1,2,-3,-4]$ then $v_+=[0,0,4,5,0,0,1,2,0,0]$ and $v_-=[-1,-3,0,0,0,0,0,0,-3,-4]$ holds.

I tried using $\max(0,v_i)\leq v_+(i)$ and $v_-(i)\leq\min(0,v_i)$ operations. I am unable to write this correctly without convex optimization.

$v$ is not a constant for me and is a variable. So is there a way to do this with only feasibility Linear Programming with only perhaps $O(1)$ integer variables?


texts: Is there a concept for an algorithm computing a function by first finding another algorithm?

texts:
If I understand it correctly, an algorithm that computes the value of a real function $f$ has computational complexity $O(g(n))$ if the following holds:
When we compute $f$ to precision $\delta$ requires on the order of $g(n)$ steps.

However, what if we have an algorithm that first "finds a more efficient algorithm to compute $f$", and then computes $f$?

  In other words, what if we have an algorithm $A$ that does the
  following:

  Find an efficient algorithm $B$ for computing $f$.
  use $B$ to compute $f$.

In that case, we can no longer speak of the computational time it would take to compute $f(5)$ for example,  because it fully depends on whether Algorithm $A$ has already found algorithm $B$. In other words, the computing time required to compute $f(5)$ if $5$ is the first comoputed number is far greater than the computational time required to compute $f(5)$ after $f(3)$ is already computed.

My question is, is there a concept/theory about this kind of algorithm that first finds another algorithm before computing a function? Specifically I am wondering about analysis of the computational complexity of such algorithms.


texts: Decoding problem and conditional probabilities

texts:
I'm reading the book by MacKay "Information theory, inference and learning algorithms" and I'm confused by how he introduces the decoding problem for LDPC codes (page 557).

given a channel output $\mathbf{r}$, we wish to find the codeword $\mathbf{t}$ that whose likelihood $P(\mathbf{r}|\mathbf{t})$ is biggest.

I can get on board with that, even if it seems a bit backwards since $\mathbf{r}$ is the evidence we have, so I would be more comfortable if we were trying to find $\mathbf{t}$ that maximizes $P(\mathbf{t}|\mathbf{r})$, and as a matter of fact, he goes on to say

there are two approaches to the decoding problem both of which lead to the generic problem 'find $\mathbf{x}$ that maximizes $$ P^*(\mathbf{x})=P(\mathbf{x})\mathbb{1}[\mathbf{Hx}=\mathbf{z}]$$

he exposes the two points of view in the following page, the first one especially confuses me

the codeword decoding point of view
First, we note the prior distribution over codewords $$ P(\mathbf{t})=\mathbb{1}[\mathbf{Ht}=\mathbf{0}]$$[...]. The posterior distribution over codewords is given by multiplying the prior by the likelihood [...] $$P(\mathbf{t}|\mathbf{r})\propto P(\mathbf{t})P(\mathbf{r}|\mathbf{t}) $$

from the generic decoding problem he gave, it looks like we're actually trying to maximize $P(\mathbf{x})=P(\mathbf{t}|\mathbf{r})$, instead of $P(\mathbf{r}|\mathbf{t})$.
Is it obvious that the two maxima are the same and with the same maximizer? It is not obvious to me since the maximizer $\mathbf{t_0}$ that maximizes $P(\mathbf{r}|\mathbf{t})$ might actually minimize $P(\mathbf{t})$, so the maximizer of $P(\mathbf{t})P(\mathbf{r}|\mathbf{t})$ might be different! I understand that in this case $P(\mathbf{t})$ is uniform, so this shouldn't be a problem, but it seems weird to me that this is simply not stated and I feel like I'm missing something.
Why should we start with the problem of maximizing $P(\mathbf{r}|\mathbf{t})$ and not $P(\mathbf{t}|\mathbf{r})$? Why does he seem to switch after a few sentences? Am I correct in thinking the algorithm presented actually maximizes $P(\mathbf{t}|\mathbf{r})$?
Thank you


texts:
I have several series of integers (vectors) that could be plotted at equal distances apart:

1: [0,1,2,1,5,3,5,7,4,2,3,4,3,4,5,6,8,1,3,1,3,8,4,3,5,1,3,8,3,4,1,8,8,6...]
2: [5,3,7,4,2,3,4,1,2,11,5,3,15,7,4,13,7,2,13,8,9,11,1,19,11,8,11,16,11...]
...
n: [40,31,32,41,45,43,45,57,54,42,53,44,53,44,53,35,31,33,8,3,4,1,8,8,6...]

I need to find an algorithm that finds the closest relative pattern within each of these series.

For instance, imagine I had a pattern such as 0,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0 (steady rise from 0 to 9 then a steady fall back to 0). I need to rank order the top patterns anywhere within these series to this pattern.

I might find in series number 37 this exact pattern, except the numbers, are in 100's: 0,100,200,300,400...900...100,0 Well that would be a very close match because it goes in the same direction and by the same proportions. The other thing is, that pattern might be buried deep within the 37th series, say it starts at index 55,000 or something.

I understand that this is quite vague but I don't know where to start. What is the best algorithm for finding these patterns fast? what is the best data structure to preprocess my data into?

I thought, perhaps I should get a percentage of change between every element in every series, then save that and query against that when I find the right algorithm. Then I thought, well if I'm gonna preprocess them, why don't I boil each series down to a function of some kind, perhaps that would be even faster to search...

Surely others have run into this kind of problem. What might they have called it?


texts: How are Neural Networks made so general?

texts:
After reading this blog about Deep Neural Networks learning about selfies I'm struck by how generic the network in question is.

In short: I'm thinking of trying to write something vaguely similar for solving cryptic crosswords, but I can't fathom how to make the general algorithms it uses generic enough that it can develop them ?

A contextual example from the blog is how the network 'understands' filters? Would I need to teach the network about tokenizing the input around keywords, or is that something the network has to 'figure out'? How do I 'seed' the operations the network can perform?


texts: How to relate circuit size to the running time of Turing machine

texts:
From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/,

  Define, $M_{[x,c]}$ as the deterministic Turing machine that operates
  as follows on an input $y$. The machine treats $x$ as a deterministic
  program, and simulates $x$ on input $y$. At the same time the machine
  runs a counter that stops its execution after steps $|y|^c$. If the
  machine accepts before the counter stops, then it accepts; otherwise,
  it rejects.

  Let $f(i,c)$ be the smallest natural number so that $M_{[i,c]}$makes a
  mistake on the input $y$. Then, if $P \neq NP$ is true, the function
  $f(i,c)$ is always defined.

  Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that $$f(i,c) > 2^{2^{|i|+c}}$$ Then, for infinitely many $n$, SAT has circuit size $n^{O(\log n)}$.

  Proof: Let $i>1$ and $c$ be so that $$f(i,c) > 2^{2^{|i|+c}}$$ Define
  $n = 2^{|i|+c-1}$. Note, that $c$ is at most $\log n$. Then,
  $M_{[i,c]}$ on all $y$ of length $n$ is correct, since $y \leq 2^n = 2^{2^{|i|+c-1}} < f(i,c)$.
  The size of the circuit that simulates this Turing machine on inputs
  of length $n$ is polynomial in $|i|$, $n$, and the running time of the
  machine. The machine, by definition, runs in time $|y|^c \leq n^c \leq n^{\log n}$

I am not getting this part. Can anyone explain this (to specify, “The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine” in the quote)? (So the question is how can we relate the running time of Turing machine to the size of the circuit.)


texts:
The number of possible min-heaps containing each value from {1,2,3,4,5,6,7} exactly once is:

My approach went like this: fixing 1 in the root for the remaining 6 elements we can choose 3 of them and then make a full node(node with two children). For a given set of 3 nodes we can arrange them in 2! ways i.e the children can be altered and the parent node is fixed. The parent node is the smallest of the three nodes which are fixed and this can be repeated even for the right child of the root as well and the right child and the left child can be again permuted in 2! ways. This will ultimately give me $6C3*2!*2!$ which is 80.

Can anyone suggest to me a generic method which works for any set of given numbers?


texts: Which calculating running time are correct?

texts:
Let $C$ be an array with length $n$ (assume the elements are cities with some properties). We have some properties sorted by importance. For example, 1.area, 2.population size, .... We use the following algorithm to find the best city according to sorted properties:

We choose the first property and examine each city. Then we delete half of the cities. (assume we can do this by $O(n)$ time.) Now we apply the second properties and again delete half of the remain cities. We continue this way until one city remains.

Can we say the running time is equal to $O(n)$ according to the recursive function
$T(n)= T(n/2)+ O(n)$,
and the master theorem or the running time is equal to $n \log(n)$ because we use binary search and in each iteration, we apply an operator in linear time?

which is correct and why another one is incorrect?


texts:
What is the reason to study planar graphs and algorithms on such graphs (as well as algorithms allowing to check a graph's planarity)? Where in industry this knowlege is needed?
I know that planarity arises in microchip design ("wires" intersection). I also found the following excerpt from a lecture notes:

  The study of two-dimensional images often results in problems related to
  planar graphs, as does the solution of many problems on the two-dimensional surface of our earth.
  Many natural three-dimensional graphs arise in scientific and engineering problems. These often
  come from well-shaped meshes, which share many properties with planar graphs.

Where I can read about it in more detail? Or may be you can explain in a few words what exactly these applications are?


texts: What is a suitable data structure in this scenario?

texts:
I need an efficient data structure for maintaining a set of values.
Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches per unit time.

I have 4 possible use cases:

$k \gg n_1,n_2$ with limited memory
$n_1 \gg k,n_2$ with limited memory
$k, n_1, n_2$ are comparable with limited memory
$k, n_1, n_2$ are comparable with unlimited memory

I have decided to use a doubly linked list for the second case and a direct address table for the fourth case.

My question is about the first and the third cases. Both Hash Table and Tree (AVL or Red-Black) look promising. Should I choose the Hash Table with an amortised constant time or the Tree with a $\log n$ worst case time?


texts:
How can I formally define * for a dfa with multiple initial states?
I know that the δ formal definition for NFA is δ: Q × ∑ → 2^Q
and for DFA it's δ : Q × Σ → Q
but what should I do if there is multiple initial states?How can I take into consideration all the options for the initial state?It seem like it should combine the NFA definition and DFA definition.. δ: 2^Q × ∑ → Q maybe?but it doesn't seem right neither.

I would appreciate any help I can get on this matter


texts:
Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong.

Lets take some non-trivial property of the set of computable functions, for example let $L = \{ f : \mathbb{N} \to \mathbb{N} \;|\; \text{f is a computable and total function} \}$. Obviously, $L$ is countably infinite and there's also a countably infinite number of computable functions not in $L$.

Now lets consider a turing complete programming language over of a finite set of instructions $\Sigma$ and the set of syntactically correct programs $P \subseteq \Sigma^*$, with $|P| = |\mathbb{N}|$. If I can choose the semantics of my language as I please, I may also number the programs as I please and so it should be possible to design a programming language where some subset of the programs computes exactly some arbitrary subset of the computable functions, as long as the cardinality matches.
For example, let $P_{pal} = \{ w \in \Sigma^* \;|\; w\text{ is a palindrome} \}$, and each program $p \in P_{pal}$ compute a total function. Since $|P_{pal}| = |L|$, such a language should exist.

However, $isPalindrome(w)$ is obviously turing-computable and since $isPalindrome(w) \iff isTotal(w)$, we would thus have a program which decides the non-trivial property $L$, which is not possible according to Rice's theorem.

Where is the error in my deduction? Does this mean there is no programming language where each palindromic program (or rather of any computable structure) computes exactly the total functions (or rather any set of computable functions)? This really perplexes me.


texts: Why do we need so many sorting algorithms?

texts: We have some best sorting methods like quick sort, merge sort etc., then why we need other sorting methods which perform poor?


texts: Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

texts:
My best attempt at a specific case of the problem where $n =$ 256:

For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2*lg(n+1)$ then $h\leq 16$ for $n  =$ 256.

But this doesn't exactly help me deduce whether the last row is all black nodes (thereby implication the parent of these black nodes are red)

Can someone hep me carry this further?


texts: Is there a way to calculate the number of all the languages over an alphabet?

texts:
Let $\Sigma = \{ a,b,c \}$ be an alphabet.

How should I calculate the number of Languages over $\Sigma$?


texts: How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?

texts:
We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the order statistic queries would be made in order (e.g., for $O(N)$ queries: what is elements number $1,3,5,\ldots,N$) .

How can we do it in $O(N)$ time ? We can't change the data structure in any way.

My thoughts:
1)The naive way is just to do delete min $N$ times but it would take $O(N \log N)$ so its not good enough.

2) if we could somehow use increase-key (if its min heap or decrease-key if its max heap) we would be able do find min in constant time increase its key so its larger than anything else in the heap we could avoid delete-min and its amortized bound of $O(log(n))$ entirely, but we are not allowed to modify the data-structure .

EDIT: sorry i didn't make it clear the heap don't have trees that waiting to be melded , otherwise its not possible since the heap could have N degree 0 trees and we cant sort N items in $O(N)$ time.


texts:
I know this question is very trivial to ask, but I have got some doubt
while solving this problem.Code is given below

public class BinarySearch {
public static int binSearch(int a[], int x) { // a is sorted
int low = 0, high = a.length - 1;
while (low <= high) {
 int mid = (low + high) / 2;
 if (x < a[mid])
 high = mid - 1;
 else if (x > a[mid])
 low = mid + 1;
 else
 return mid;

}

return Integer.MIN_VALUE;

}

If we want to calculate the worst case comparisons of binary search,then

it will be $2 \log n+1$, because $\log n+1$ for checking (low<=high) and $\log n$ for (x < a[mid]) or if (x > a[mid]).

Alright , i have no issue here , i can happily say that worst case comparison for Binary search is $2\log n +1$

I faced issue when i tried to solve the recurrence equation, given as-:

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

  $\text{Base Case}\,\,T(1)=1$

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

Generalizing the equation i got-:

$T(n)=T(\frac{n}{2^{k}})+1+1..+1(k \text{times})$

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

  $\frac{n}{2^k}=1$

  $k=\log n$

So $T(n)=\log n+1$
What actually this value signifies?
Is it Minimum number of comparison?
Confused
Please help me out


texts: Complexity of recursive Fibonacci algorithm

texts:
Using the following recursive Fibonacci algorithm:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

If I input the number 5 to find fib(5), I know this will output 5 but how do I examine the complexity of this algorithm? How do I calculate the steps involved?


texts: Best operating system for a computing degree?

texts: Not sure which OS is best to invest in for my computer science degree. Have had varying opinions - from your experience in education or working in the sector, what is the operating system that will treat me the best for the next three years of my degree?


texts: I have to convert this fsa to regular expression but these are too different than i learned... Can you guys help with converting these? Plz!


texts:
I have a question concerning NP reduction.
My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding out if the TRI-Graph is 3 coloring is NP-Complete.
I'm not asking for the answer. But I've been racking my brain on how to approach the reduction.
I'm curious to know if you guys have suggestions on which problem I should use to reduce it to my trigraph.
I've tried SAT3, CLIQUE, but those tri-edges make it very hard, maybe I'm going about it the wrong way.
Anyhow, any help would be appreciated. Thanks in advance.


texts: Choosing a non-cryptographic hash function for language with no unsigned integers

texts:
I'm implementing a hash table in pure UnrealScript, which only has support for signed 32-bit integers. This means no 64-bit integers and no unsigned integers. I was in the middle of implementing an FNV hash function, but ran into a potential problem.

  The offset_basis for FNV-1 is dependent on n, the size of the hash:
  32 bit offset_basis = 2166136261

Well, 2166136261 converts to -2128831035 when the bits are turned into an signed integer representation. My question is whether or not this will negatively affect the hash distribution and result in more collisions.

For quick reference, here is the psuedo-code for the FNV hash:

hash = offset_basis
for each octet_of_data to be hashed
    hash = hash * FNV_prime
    hash = hash xor octet_of_data
return hash

Thank you for your time.


texts: How to find i-th root of n whose remainder is the smallest?

texts:
Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively small number (e.g. the maximum number that can be represented by a unsigned int)?

I'm currently using gmp bignum library in C, and my algorithm is as follows:

It first finds the smallest possible base and the greatest possible base given the circunstances (binaries searches are performed) and then we know the range of i.

Then, for each possible i, we take the i-th root of n and the corresponding remainder. The smallest remainder is updated if the current remainder is smaller than it.

The algorithm does work, but it's far too slow (even using such a powerful library as gmp). For comparison, for a number with roughly 6 mega bits when expressed in binary the algorithm takes ~90 days to complete.

Intuitively, I think there is a better way to solve the problem (i.e. faster way, an algorithm with a smaller time complexity). What can be done to speed up this process?

Obs: Problem: Given n, find i such that the remainder, n - (floor(ithRootOf(n))^i, is the smallest possible. 2 <= floor(ithRootOf(n)) <= 2147483647


texts: How many times do we access memory with a TLB?

texts: As I understand it, when we are on a virtual memory based system, we have to access memory 2 times (one for the Page Table and one for the physical address in RAM). But, how many times would we have to access if we had a TLB?


texts: Is the language $\{a^n b^m : 1000|nm \}$ regular?

texts:
We have a language  $$ L = \{a^n b^m \mid 1000|nm \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say  $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$ and 1000|nm
if I say i = 0 , $L =a^{n-t}b^m$ and 1000|(n-h)*m and I can't prove (n-h)*m isn't dividable by 1000.
if I say i = 2  $L =a^{n+t}b^m$ and 1000|(n+h)*m I can't prove this too because I'm not sure about h value.
I think it didn't work. any idea?
I would appreciate it if you helped me with this.


texts: Complete explanation of state elimination methods

texts:
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the difference to convert the NFA to RE and DFA to RE.
Online there are a lot of resources, but it is difficult to find a complete answer to understand the general idea of this method.
And, again, sorry if my question is too general, but I think that this place is a good place to meet people that understand this argument better than me, and are also able to explain it in a logical way.


texts:
Since I don't have CS background I will most probably ask this question the wrong way. I need to choose a node from a tree, where I include all beneath this node leafs in a validation.

I have a data set from a big web directory that categorized websites. I already wrangled the data around so the root of every category is the language of the website. The Categories for each website look like this:

English/Computer/Hardware/CPUs/Intel
English/Computer/Hardware
English/Computer/Hardware/Motherboards
English/Computer/Hardware/Networking/
                ...
German/Computer/Hardware
German/Computer/Software
German/Computer
                ...

The trees I constructed can have both leafs and branches kinda like a directory structure with files and folders. I represented every individual languages as such a tree, where each node knows how many leaves it self has and all the branches beneath it. They look like that:

                                   English
                                     300
                                      |
                          A --------------------- B
                         120                     180
                          |                       |
                          E                C ----------- D
                         80               10            160

Now theses Category trees can go deep up, to up to 20 nodes and many (end)nodes only have very few leafs 1-10 in a tree with over a million leafs overall. Additionally the non-english trees have significantly less leafs, nodes, and depth.

As I wrote in the beginning, I want to pick a sub node and all the leafs beneath it to test some models, that look for similarity in websites. The amount of leafs should be representative for the data set but also as specific, category wise, as possible. My first intuition was to pick nodes that hold about 1% of the sum of all leafs in the tree. But I have no idea if this is a) specific enough and b) representative enough. It is just a number that sounds good that I can not backup with anything.

So my question, is there an algorithm that can give me such a number? So that I don't have to just pull it out of a hat?


texts: is AVL tree is better than heap for sorting purpose?

texts: for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?


texts:
I have some problems to understand computability and hope you can help me.
In the lecture we had following problem:
Consider the three partial functions $f,g,h\colon N \to N$, where $f$ is computable and $g$ is not computable. The following two statements are correct:

If $h(x) = g(f(x))$, then $h$ could be computable.

If $g(x) = h(f(x))$, then $h$ is not computable.

Well, 2 is clear I think, because we know that $g$ is not computable and $f$ is computable, so $h$ has to be not computable, otherwise $g$ would be computable.
But 1 is a big problem for me. If $f$ is computable and $g$ is not computable, how can $h$ be computable?


texts: Complexity Analysis for complex nested loops

texts:
What is the general approach for time complexity analysis when you have a loop structure which is complex?
For example if the length of the inner loop is some function o the iteration of the outer loop?
EX: Consider
for i in range(log_2(n)):
    for j in range(i^3)
         do something

A simple approach is to upper bound the inner loop by the term with the greatest number of iterations but this bound is very loose.


texts:
Let $L$ be the language over the alphabet $\{0, 1, 2, 3, (,), +, -, *, /\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$.

2 - - 3 is an incorrect expression, 2 + 3 is correct, 2 + (-3) is correct.
Is it possible to write a regular expression for this language?  If not, why?

I think that it is not possible to write a regular expression for this language, because of the operator / we cannot write 2 / 0 for example and are more than a finite number combinations to make this possible. Is it correct?


texts:
I fail to understand a algorithm, basically the matrix multiplication portion.

I can explain the unknown terms. At line no: 4 j will be 1,2,3,....,15. When ever new object is observed a value corresponding to this object assigned in j. There are total 15 objects. So when object number 1 observed it is assigned to j. j will be 1. If object no. 1 assigned again and again it will never assigned in j. J will be updated when object no. 2 is observed and so on.

Problem is in line no: 13 the matrix multiplication $H_t^i*\mu_t$. $\mu_t$ is 48*1 vector, where as  $H_t^i$ is a matrix with dynamic dimension. The number of column of $H_t^i$ will be change whenever the value of j will be change. But the for $\mu_t$ column will be remain static and it is 1. So when I implement it in matlab it give me a dimension mismatch error.

I think misunderstand this algorithm. Help me.


texts: Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

texts:
Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $ O(\log_t n) $ (where $t \in \mathbb{N}$ is the order of the tree).
There was one true/false question on exam which asks if the Big-O complexity of the operation mentioned in the example above is $ O(\log_2 n) $.
I am beginner in this topic but I understand that both $ O(\log_2 n) $ and $ O(\log_t n) $ belong to the same Big-O complexity category of $ O(\log n) $. The only thing which confuses me is whether it matters if the base of a logarithm is given as a constant or as a variable.
Additionally: Would the answer change if we swap the bases from the example and the question?
Edit (if relevant): The mentioned complexity is related to the number of disk accesses and it is not the time complexity.


texts: Understanding basic operation of TM and FA

texts:
As turing machine always halts on dead configuration,so consider the  case where it halts in final state,if on second last state by reading an input alphabet it comes to final state. Now in final state it will try to find the transition for the next symbol(i.e blank) and as there will be no transition on final state so machine will halt/dead in final and we can say string is accepted.

If i consider the case of Finite automate,now FA reaches the final state and the next is blank then we say machine will stop and string is accepted.But this is not dead configuration.

But in both cases the input is coming from tape and in case of FA ,it will halt when blank comes on tape and there is no dead configuration.But same behaviour in TM is having dead configuration behaviour.

Can someone please explain the difference in these two case from point of dead configuration.?

P.S:- By dead configuration,i mean that transition on the state is not defined for given alphabet


texts: Algorithm to test whether a binary tree is a search tree and count complete branches

texts:
I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable. This is an assignment for my data structures class.

So far I have

void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

But I can't really figure this one out. I know that this algorithm won't solve the problem because the count will be zero if the second if statement isn't true.

Could anyone help me out on this one?


texts: Satisfiability Toward A Sequential Circuit

texts:
Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean equation.

For example, constructing a loop by connecting the input and output of a negation gate will yield the equation $x=\lnot x$, which is not satisfiable. Given such circuit, the "satisfiability" in the sense naturally occur. My question is:

  Is determining whether this circuit can be satisfied known to be hard or easy? Furthermore, is finding or enumerating these configuration known to be hard or easy?


texts:
Does it make sense to speak of algorithms that take an infinite amount of time to terminate?

In particular, suppose we have a loop with a bound function that is initially positive and is decreased by the loop body each time. Furthermore, suppose that termination of the loop implies that bound function is non-positive. (Ie almost all assumptions of The Invariance Theorem are satisfied.)

Here's the rub, initially the value of the bound function is the cardinality of the natural numbers.

What can be said in such situations?

Any help or direction is most welcome; thank you!


texts: Negative lookahead in LR parsing algorithm

texts:
Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;

It's an ordinary rule, except that it has a restriction: a phrase produced with this rule cannot begin with Terminal1, ..., TerminalN. (Surely, this rule can be replaced with a set of usual rules, but it will result in a bigger grammar). This can be useful for resolving conflicts.

The question is, is there a modification of LR table construction algorithm that accepts such restrictions? It seems to me that such a modification is possible (like precedence relations).

Surely, it can be checked in runtime, but I mean compile-time check (a check which is performed while building parsing table, like %prec, %left, %right and %nonassoc directives in yacc-compartible generators.)


texts: (Why) is there no complexity class for linear space (O(n))?

texts:
tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it?

the Quantified Boolean Formula (QBF) problem is a P-space complete problem. I use the definition for QBF from here, which got its definition from here. It seems trivial to me that there's an exponential solution that uses linear space by using depth-first search. So this P-space complete problem uses linear space, but this does not mean that P-space=linear space. We have:

Linear space $\subseteq$ P-space $\subseteq$ Exp-time

In the (though unlikely) case that P=P-space, I was thinking about the contradiction/paradox situation that:

Linear space takes exponential time
P-space takes polynomial time
Exp-time takes exponential time

which, because of the likely contradiction, makes me want to conclude that

P = P-space $\implies$ P = P-space = Linear space

I wanted to think about the contradiction/paradox further and I wanted to lookup information about the linear space complexity class. None seems to be available. What am I overlooking. Is this complexity class not interesting? It is not even mentioned here.


texts: Find path from s to t that goes through another node w

texts: If you have directed and unweighted graph G how could you find a path from node s to node t that also goes through another node w? This could be a non-simple path.


texts: Complexity calculation using a recurrence relation

texts:
I just can't solve this problem, I'm new to reccurences. I have this recurrence

$T(n)=n*T(n-1)$
$T(1)=1$

The second term will be:

$T(n-1)=(n-1)*T(n-2)$

And so on.

It's complexity is O(n!) but i don't know how to solve it.

I hope you can help me with an idea!


texts: Can Java be accurately described as statically and dynamically typed?

texts: Java seems to be categorized as a statically-typed language [1], but I'm wondering if it would be accurate to describe it as generally statically-typed but having some dynamic typing because of the run-time type checks performed when downcasts are performed.


texts: Creating sum of all numbers within a sequence

texts:
Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
Max sum for sequence [2, 1, 5, 3, 4] is 31.

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

public static int solve(ArrayList<Integer> seq, int sumOfRemoved) {
  if (seq.size() == 3) {
    return seq.get(0) + seq.get(1) + seq.get(2) + sumOfRemoved;
  }
  LinkedList<Integer> maxValues = new LinkedList<>();
  for (int i = 1; i < seq.size() - 1; i++) {
    ArrayList<Integer> clone = (ArrayList<Integer>) seq.clone();
    clone.remove(i);
    int sum = seq.get(i - 1) + seq.get(i) + seq.get(i + 1);
    maxValues.add(solve(clone, sum));
  }
  int max = 0;
  for (int val : maxValues) {
    max = Math.max(max, val + sumOfRemoved);
  }
  return max;
}

My question is, is there more efficient algorithm solving this problem?


texts:
Why does the empty clause is logically equivalent to a contraddiction:
$\square \cup \square \Longleftrightarrow \perp$

and why the empty cube is logically equivalent to a tautology:
$\square \cap \square \Longleftrightarrow \top$ ?


texts: Why HOG angular bins have values between 0 and 180 degrees?

texts:
I have learned that HOG angular bins have values from 0 to 180 since the algorithm uses unsigned gradients. I am failing to understand why.

As far as I know gradient orientation is calculated as

angle = atan(S_y / S_x)

where S_x and S_y are image gradients in x and y directions respectively.

Provided that S_y and S_x are non-negative, the ratio will also never be negative. Hence, the angle should be in range from 0 to 90 degrees (see atan graph below). What am I missing?


texts: How to give a context-sensitive grammar for a^nba^nba^nb?

texts: I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.


texts: Computation tree logic and Kripke structures

texts:
Specifications in Kripke structures are verified by Computation tree logic (CTL). However, refering to this Wikipedia article the CTL-operators are relative to a current state. So, when we want to verify if EF q is satisfied in a Kripke structure

Do we only need to check if EF q holds starting from the starting state oder do we need to check if EF q holds starting from every state?


texts: Similarity measure of two arbitrary functions

texts:
Given two arbitrary functions, how can I measure how similar they are? For example:

def foo(a: str, b: str):
    return a + b

def bar(a: str, b: str):
    x = a + b
    return x

def fuz(a: str, b: str):
    x = a + b.upper()
    return x

foo and bar are operationally the same, for a given input they produce the same output, and so would have a similarity = 1.

bar and fuz are very similar and so would have a score between 0 and 1, but closer to 1.

For two arbitrary functions (any datatype input and output) how can I calculate a similarity metric?


texts: Getting O-bounds by applying regression methods to execution time measurements

texts:
Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(n·logn·n^2) or Ω(n·logn), in a theoretical way, doing reccurence ecuations and all that stuff. But when you plot the data from a CSV, you can't say just by looking at it 'oh yea this is O(n^2).

The data from the CSV is like:

n, execution_time_for_that_n...

How can I use a regression method to derive O-classes from such data?


texts: Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set?

texts:
Why isn't the set $\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ a r.e. set?

Note: $W_x = L(M_x)$


texts: Why does A* fail to find the fastest path when it reaches the goal?

texts:
I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example:

Take a 2x2 grid, in which you can only move in one of 4 (orthogonal) directions (no diagonal movement). Denote the node at (0, 0) by A, the node at (1, 0) by B, the node at (0, 1) by C, and the node at (1, 1) by D (so that it looks like

C D
A B

The weight going from A to B is 3, the weight going from A to C is 2, the weight from B to D is 1, and the weight from C to D is 3. Let the start node be A and the goal be D. Let our heuristic simply be Euclidean distance (or Manhattan distance, both produce the same result in this instance).

So, if my understanding of A* is correct, we start with an open set containing only A, so we pop A. It's neighbours are B and C, which have g values g(B) = 3, g(C) = 2, and h values h(B) = 1, h(C) = 1. So the f-values are f(B) = 3 + 1 = 4, f(C) = 2 + 1 = 3. Add these to the open set.

Now the open set is {B, C}. Since C has the lowest f-value, we pop it. C's only neighbour is D, which is the goal. So we stop, having found "the best path" from A to D.

This is clearly wrong. The algorithm should output the path A->B->D, which has total weight 4, but instead it stopped prematurely.

Now, if we were to have a larger graph, then after exploring the path A->C->D we would go back to B (which is still in the open set), notice that the path A->B->D to D gives D a lower f-value than A->C->D, so we update D's f-value, giving the correct fastest path. Alternatively, we could simply continue running A* until the open set is empty, rather than ending prematurely as soon as we've found the goal (however, this doesn't agree with Wikipedia's pseudocode implementation of A*).

Are my ideas correct, or am I missing something about how A* is typically implemented?


texts: Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?

texts:
The book I am reading is suggesting the following:

Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(n)} w$ is more complex in terms of space complexity than some trick which they use in order to create an expression of the form $$\sum_{j=1}^{P(n)} \langle v, U_1x_j\rangle \langle v, U_2x_j\rangle, \ldots, \langle v, U_{P(n)}x_j\rangle$$ for some vectors $x_j$.

Basically they say that $\langle v, U_1U_2\ldots U_{P(n)}w\rangle$ is not linear in space, as opposed to the same expression written this way by adding many $x$ vectors which render the expression equal but written differently as above.

How come the latter is better than the former? In both of them you have a vector which has to be stored in memory. They claim that in the latter you just add to the running total. But inside the inner product you still have to store a vector just the size of the first method. What's the difference?


texts: Why is the zero-th power of the empty set {ε}?

texts:
It has been asked before why $\emptyset^\star=\{\epsilon\}$.
The answer boils down to $\emptyset^\star$ being defined as
$$ L^\star = \bigcup_{i=0}^\infty L^i, $$
where a word in $L^i$ is the concatenation of $i$ words from $L$. So, for the empty language this leaves empty sets for all $i>0$, "but $L^0 = \{ \epsilon \}$
 since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$." (quoted from the answer.)

And that's what I'm curious about: is there a good reason to say that the concatenation of zero words is $\epsilon$ even for the empty set? Can you compare it to $0^0=1$ in arithmetics (where it's just more or less arbitrary) or is there a strong logical reason for this to be true?


texts: Finding optimal sequence of questions to minimize total student time

texts:
Suppose there is a tutorial session at a university.
We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$
students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be
the set of questions that a student has a doubt it. Assume that
$\forall 1 \leq j \leq n: Q_j \neq \phi$ and
$\bigcup_{1\leq j\leq n}Q_j = Q$.

All students enter the tutorial session in the beginning (at $t = 0$). Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time
taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the
time spent by $s_j$ in the tutorial session. We want to find out an
optimal permutation $\sigma$ in which questions are discussed
$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $T_\sigma = \Sigma_{1\leq j \leq n}t_j$ is minimized.

I have not been able to design a polynomial time algorithm, or prove $\mathsf{NP}$-hardness.

We can define a decision version of the problem
$$ \mathsf{TUT} = \{\langle k, n, \mathcal{F}_Q, C \rangle \mid \exists \sigma : T_{\sigma} \leq C\} $$

where $\mathcal{F}_Q$ is the set of $Q_j$'s.

We can then find out the minimum
$T_\sigma$ using binary search on $C$ and find out the optimal $\sigma$ using partial assignments to $\sigma$ in polynomial time using an oracle for $\mathsf{TUT}$. Also, $\mathsf{TUT} \in \mathsf{NP}$ because the optimal $\sigma$ can be used as a certificate which we can verify easily in polynomial time.

My question: Is $\mathsf{TUT}$ $\mathsf{NP}$-complete or can we design a
polynomial time algorithm for it?

Sidenote: By the way, I thought of this question after an actual tutorial
session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!


texts: Sparse Matrix inversion without actual inversion

texts:
I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix?

Thank you in advance


texts:
We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least half of clauses satisfied.

I don't understand why the algorithm needs to be so complicated. Why does the following not give a 1/2-approximation for MAXSAT in guaranteed linear time?

Let $m$ be the number of clauses in the formula.
Set all variables to true. Count the number of satisfied clauses. If it's at least $m/2$ then return this assignment.
Set all variables to false. Return this assignment.

Every clause contains at least one literal which will be satisfied either by setting a variable to true or a variable to false. Thus the two assignments satisfy a total of at least $m$ clauses so at least one of them satisfies $\ge m/2$ clauses.


texts: Poly-Time TSP Algorithm if there is constant factor approximation algorithm?

texts: I know that a polynomial-time constant factor approximation algorithm for the general Traveling Salesman Problem does not exist unless P=NP. However, I want to prove that the TSP decision problem (is there a Hamiltonian cycle of graph with weight sum <= k?) is in P if we assume that there is an approximation algorithm that guarantees optimal solution * a (a>1). Is there a way to prove this problem, without using polynomial reduction?


texts: Properties of Reverse Polish Notation expressions that are algebraically invariant

texts:
The RPN expressions

a b + c *

and

f d e + *

are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions

a b * c +

a b * c *

though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general

c (a + b) ≠ c + a * b
c (a + b) ≠ a * b * c

Without substituting values for any of the variables, is there a property that we could compute which is the same for a b + c * and f d e + * but not for a b + c * and a b * c + or a b * c *?

Assume the variables are real numbers, not e.g. matrices, so + and * are commutative, but - and ÷ are not.

This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?

This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.

I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.


texts: Which type compilers report if they cannot infer a precise type?

texts:
In the presence of subtyping, a type checker can usually infer only some inequality constraints on the type rather than the exact type. Of course, internally it will store the full constraints. But what is the common practice in case it needs to display the inferred type to the programmer?

I thought it might be reasonable to just display the lowest type that satisfies all the constraints (I guess it exists and unique if the types form a lattice). That would mean the programmer would know all the contexts where the name can be used. But then, if there's no constraint from below, the type checker would be displaying Bottom, and I don't think it's commonly done.

What am I missing?


texts: Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

texts:
So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you also need to know whether the reverse is true or not. Which is to say that the set of strings accepted by the DFA is described by the regex. I have no idea how to know if this is the case or not.

Could you guys tell me how to be sure if the DFA really recognizes the language described by the regex (000* + 111*)*


texts: example for weakly fair v.s. strongly fair scheduling in concurrency

texts:
I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different?

for reference, here are the definitions I have of each:

weakly fair: A condition becomes true and remains true at least until after the conditional atomic action has been executed.

strongly fair: If the condition is infinitely often true, a process will eventually see it as true and be able to proceed.

So I think I understand weakly fair, a conditional atomic action will execute when its condition is true, and the condition will remain true until the atomic action has ended.

But I don't see how strongly fair is different from this. for a conditional atomic action, once its condition is true it executes, and because it is atomic, the condition should remain true until it ends, right? this is the same as weakly fair isn't it?


texts: how does rotation works in AVL trees and what is a good way to understand it?

texts: If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 switch with T2? I saw multiple examples online but they had too many nodes and i couldn't really understand the concept of rotating and that's why i chose this simple example so that i (hopefully) can apply it in all other situations.


texts: Given a list of points in 3-D choose $m$ points such that sum of maximum values of $x$, $y$ and $z$ coordinates among all chosen points is minimum

texts:
We are given a list
$L = {(x_1, y_1, z_1), \dots, (x_n, y_n, z_n)}$
and an integer $m \leq n$.
The goal is to find a subset $S \subseteq \{1,\ldots,n\}$ of size $m$ which minimizes the following cost function:
$$\mathit{cost} = \max_{p \in S}(x_p) + \max_{p \in S}(y_p) + \max_{p \in S}(z_p).$$

Is there any subquadratic algorithm to solve the above problem?

This question was recently asked in hiring challenge for an internship in some company. The challenge is over. I have a working solution which runs in $O(n^2 \log{n})$.
Sketch of my algorithm

Iterate over all points $(x_i, y_i, j_i)$ in non-decreasing order of $x_i$. Along with that maintain a sorted list $S_1$ of pairs $(y_j, z_j)$ such that there is a point $(x_k, y_k, z_k)$ in original list such that $x_k\le x_i$ and $(y_k, z_k)=(y_j, z_j)$. Perform all the following steps in each iteration.
If $|S_1|<m$ then we know that there can not be any list of $m$ points where maximum value across $x$ coordinate is $x_i$. (In case of multiple point having same $x$-coordinate value we will eventually find a match in next iterations. So no need to worry about it.)
Now iterate over pairs $(y_j, z_j)$ ($j$ index is not related to one used in second step) in $S_1$ in non-decreasing order of $y_j$. Along with that we maintain another list of $S_2$ of values $z_k$ such that there is some pair $(y_k, z_k) \in S_1$ such that $y_k \le y_j$.
Now, If $|S_2|\ge m$ then update our $\mathit{ans}$ with $\min(\mathit{ans}, x_i + y_j + m^{th} \text{ largest value in } S_2)$


texts: How to use a logistic regression classifier to estimate the confidence of a rule?

texts:
The following is an excerpt from the Estimating LAT Confidence section of this paper:

  ... Since some LAT detection rules are more reliable than others, we
  would like to have a confidence value in each LAT that can be used to
  weight each LAT appropriately during answer scoring. To accomplish
  this, we trained a logistic regression classifier using a manually
  annotated gold standard. The classifier uses the focus and LAT rules
  that have fired as features, along with other features from the parse,
  NER, and the prior probability of a particular word being a LAT...

It's not clear to me what is the target variable of the logistic regression classifier. It sounds to me that it is binary variable indicating whether the fired rule was correct (1) or incorrect (0). Therefore, the prediction of the logistic regression classifier is the probability that the word is an LAT given that a certain rule has been hired (and some other features). Does this application of the logistic regression classifier make sense?

The details of the paper are as follows:

A. Lally et al., "Question analysis: How Watson reads a clue," in IBM Journal of Research and Development, vol. 56, no. 3.4, pp. 2:1-2:14, May-June 2012.
doi: 10.1147/JRD.2012.2184637


texts: If there's algorithm which returns true if Hamiltonian cycle exists in polynomial time then an algorithm to find the cycle in such time also exists?

texts:
How can it be proved that if there's an algorithm which in polynomial time determines whether a graph has a Hamiltonian cycle then there's an algorithm which can find such Hamiltonian cycle in polynomial time as well?

Note: there's no need to devise the actual algorithm I just need to prove that one causes the other to hold.

I thought that perhaps the algorithm A which just determines whether the graph contains a Hamiltonian cycle has to perform the same amount of work as the algorithm B which has to find the actual cycle because each node has to be visited.

But I'm not sure how to actually prove this.


texts: What is the mathematical principle of buddy algorithm?

texts:
The buddy algorithm is:

  The buddy for any block of size $2^k$ is another block of the same size, and with the same page frame number except that the kth bit is reversed.

Example:

If the block size if $2^3$ and the start page frame number(aka pfn) of this block is 0xC, the page frame number of the buddy of this block is pfn=0x4.

This algorithm is very ingenious but I have two questions.

Why the buddy of 0xC is 0x4 instead of 0x14?
Why reversing the kth bit does the trick?

References:
http://research.cs.vt.edu/AVresearch/MMtutorial/buddy.php


texts: Numbers choosing algorithm form constants according to input

texts:
First of all sorry for my poor English.

Problem:
There are 15 strings 1 to 50 and they’ve defined randomly.
There is a input 1 to 500.
This 15 strings are static but input is changing during 75k iteration.
At each iteration computer will pick some of 15 strings which are nearest value to input when they summarise.
Goal is end of the 75 k iteration sum of difference between summarise of picked number and the input is 2%. Or nearest point.

Barriers: computer cannot pick a number if that number picked in last 60 iterations.

Outputs:
Nearest point of goal and an analyse what would be the best 15 numbers accordingly that inputs.


texts: What are the substitues for Kolmogorov Complexity to analyse Hashing

texts:
The paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses" <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain a lower bound in the space of a data structure that rank with erros.

My question is: What are the other Algorithmic options of complexity that replace the Kolmogorov Complexity? Is Kolmogorov-Sinai Entropy a option?


texts: Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$?

texts: This question was asked in peter linz exercise. I have tried languages such as $\phi,\epsilon,\Sigma^*$.


texts: Regularity of language of words containing a square

texts: $$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this language regular or not regular?


texts: Does virtual address space resides in virtual memory?

texts:
I have several confusion like :

Does virtual address space resides in virtual memory ?
Does each process has its own virtual address space like each process has its own virtual memory and own page table ?
Mapping to physical address takes place from virtual memory or virtual address space if they are different thing ?


texts: Finding set of disjoint sets with additional value optimization

texts:
I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties:

Sum of all $v$'s is maximum
$S$ from all pairs construct a disjoint set

Example. For given set $Q$:

$Q = \{[\{1, 2\}, 5], [\{2, 3\}, 8], [\{3, 4\}, 2], [\{5\}, 1]\}$

Result $R$ should be:

$R = \{[\{2, 3\}, 8], [\{5\}, 1]\}$

I came up with an obvious algorithm which constructs every possible set of pairs whose $S$ constructs disjoint set:

T = {}
foreach (q in Q)
  foreach (t in T)
    if (union of all S from t and S from q constructs a disjoint set)
      add copy of t to T
      add q to t
  add {q} to T

Then I would find t with highest sum of all it's v's.

This is worst case $O(2^n)$.
Can I do better than this? I will appreciate any additional information regarding this problem.


texts: Minimum Subsequence Sum Algorithm Verification

texts:
I have an algorithm which is meant to solve the following computational problem:

Input: Sequence of positive integers
Output: A Sub-sequence of some desired length derived from original Sequence such that the sum of the sub-sequence's elements are the minimum sum possible

The Algorithm I have to solve this problem is implemented as a method in Java:

public int[] runA(int k) {

        //k is desired length of sub-sequence

        /*Sequence S is the original sequence provided as input, it is available as a class variable
        for the class 'MinimumSubsequence' which this method 'runA' is apart of*/

        //A is Sequence S copy with pseudo-boolean values attached to each element in S
        int[][] A = new int[this.S.length][2];
        //B is size K array storing the k smallest elements found in S along with their indexes
        int[][] B = new int[k][2];

        //initialization
        for (int i = 0; i < this.S.length; i++) {
            A[i][0] = this.S[i];
            A[i][1] = False;
        }
        for (int i = 0; i < k; i++) {
            B[i][0] = this.S[i];
            B[i][1] = i;
        }

        //Execution
        //search for k smallest elements in sequence S
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < this.S.length; j++) {
                if (A[j][0] <= B[i][0] && A[j][1] == False) {
                    B[i][0] = A[j][0];
                    B[i][1] = j;
                }
                A[(B[i][1])][1] = True;
            }
        }

        //build subsequence
        int[][] C = new int[this.S.length][2];
        for (int i = 0; i < C.length; i++) {
            C[i][1] = False;
        }
        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (B[j][1] == i && (C[i][1] == False)) {
                    C[i][0] = B[j][0];
                    C[i][1] = True;
                }
            }
        }
        int[] D = new int[k];
        int j = 0;
        for (int i = 0; i < C.length; i++) {
            if (C[i][1] == True) {
                D[j] = C[i][0];
                j++;
            }
        }

        return D;
    }

The algorithm basically works by scanning the original sequence provided, each time scanning for the next smallest number. Once it has found the k smallest numbers in the sequence it builds and returns a sub-sequence made from those smallest elements in the original sequence

I believe that this algorithm does correctly solve the computational problem and that the running time of this algorithm is in O(N) (N being size of input sequence). I would just like some verification about the correctness and efficiency of this algorithm. I am also wondering if there exists are more efficient algorithm to solve this computational problem as I'm just not very satisfied with this one but can think of no other approach.


texts:
I am not so familiar with trees.

How is a tree stored in memory? what is the data structure type used for storing it?

As a string?linked list? stack (!)?

Or is there some kind of data storage model for trees?


texts: Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes

texts:
I have two datasets $A$ and $B$:

$A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$
$B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$

Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.

Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and  $b_i \geq v$ reaches the biggest possible value.

For clarification: Say $a_3 \geq u$ but $b_3 < v$. Then $(a_3 + b_3)$ is not included in the sum. That is meant by $ a_i \geq u$ and  $b_i \geq v$.

Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.


texts: Relational calculus: what is a range-restricted variable?

texts: I know that if the set of free variables for a relational calculus query is equal to the set of range-restricted variables then the query is (roughly) safe. I also can identify free variables. However, I do not understand what range-restricted variables are at all, and I can't find any comprehensible explanations anywhere. Can anyone give me a hand? This is for domain relational calculus.


texts: What does it mean for a problem to be both NP hard and coNP hard

texts:
I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example).

I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard...not really helping there

Can someone please clarify for me on an intuitive level what does it mean for a problem to be coNP hard? Further, what does it mean for a problem to be both NP hard and coNP hard? What is a problem that illustrate this concept?

Thank you!


texts: It is possible to implement a *greater than* function using only addition, substractions and multiplications?

texts:
All values are from a finite field $Z_t$.
I want to write a function greater than like this

$GT(x,y) = \begin{cases}
  1, & \text{if } x > y, \\
  0, & \text{otherwise}.
\end{cases}$

using only additions, multiplications, subtractions and preferably not divisions.

The equality function

$EQU(x,y) = \begin{cases}
  1, & \text{if } x == y, \\
  0, & \text{otherwise}.
\end{cases}$

can be computed like this

$EQU(x,y) = 1 - (x-y)^p$, where p is the Euler totient function $p=phi(t)=t-1$ because $t$ is prime.

Can a greater than function be written in a similar way ?

The greater than function would be used for a homomorphic encryption application to find the maximum integer value from a vector of encrypted integers.


texts:
You are given a List of numbers (length unknown).

Let's say the length is 10.

GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned.

GetRandom(List) is called 100 times. If implemented correctly, each number will appear 10 times in the result.

Fine?

You now have to do the same for a Stream of numbers.

GetRandom(Stream, 5) is called. This adds 5 to the Stream. Stream is of length N=1, then 5 is returned (probability = 1/N = 1)

GetRandom(Stream, 3) is called. 3 is added to stream. N=2. Either 3 or 5 is returned (prob = 1/2).

How will this be tested for correctness?
If GetRandom(Stream) (without adding any more numbers) is called 10 times when length of list is 2, each number (3 & 5) should be returned ~5 times.

GetRandom(Stream, 7) is called.  7 is added to Stream. N = 3. One of the 3 numbers (5, 3, 7) is returned (probability = 1/3).

But how will this be tested for correctness?
If GetRandom(Stream) is called 10 times when N = 3, each number is returned ~3 times.

So far, so good ?

Alright, here is my algorithm:

N = 0
Pointer = 0

GetRandom(Stream, Number = NULL):
    Pointer += 1

    if Number is NOT NULL:
        N += 1
    else:
        if Pointer == N:
            Pointer = 1    # Reset

    return Stream[Pointer]    # Assume 1-based indexes

This simply cycles through all numbers in order / round-robin fashion.

If GetRandom(Stream) is called on a Stream with 100 numbers, 1000 times, each number will appear exactly 10 times.

If GetRandom(Stream, 77) is called on a Stream with 100 numbers (77 is the 101st number), while Pointer got reset to initial location 1. Then when GetRandom(Stream) is called 101 times, then on the 101st call, 77 will be output, which satisfies the required probability of 1/101. If it's called 202 times, then on the 202th call, 77 will be output, which satisfies 2/202.

Why bother with Reservoir Sampling k/k+1, Why bother with a random number generator?


texts: Which would be the most purely functional equivalent to generators?

texts:
Some programming languages, apart from functions, have generators (eg. Python's yield). Although generators are introduced in this Python's tutorial on functional programming, I don't think that they can be considered functional programming, because they do have state, and in a vary implicit manner.

Generators are reminiscent of laziness in pure functional languages like Haskell. Apart from laziness, are there other purely functional alternatives for having a construct similar to generators? Do you have any examples?


texts:
Right now I am doing some problems on application of decision tree/random forest. I am trying to fit a problem which has numbers as well as strings (such as country name) as features. Now the library, scikit-learn takes only numbers as parameters, but I want to inject the strings as well as they carry significant amount of knowledge.

How do I handle such scenario, I can convert string to numbers by some mechanism such as hashing in python. But I would like to know the best practice on how strings are handled in decision tree problems.


texts: how many hash table sequences will produce a given table

texts:
given the following hash table with linear probing when the hash function is:
 $$k mod 10$$

how many different sequences will produce the given table? (starting from an empty table)


texts: Given a relation and asked to enumerate all FD's and mark the trivial FD's

texts:
Given a relation R(A,B,C) and a FD set (A->B, B->C), find the FD Closure. Enumerate all the FD's and organize them accordingly to the LHS of the FD's. Mark all the trivial FD's.

I am a little confused with the second part of the question and don't understand what exactly they mean by "organize them accordingly to the LHS of the FD's"
My understanding is, Apart from the given FD's, we have A->C(on account of transitivity) and the trivial FD's will be A->A , B->B, C->C, A->AB, A->AC, B->BC. Is this the answer to the given question or am I missing something here?


texts: A hash function with predicted collisions

texts:
As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides for some known set of possible inputs and avoids collisions for other input values. To state the problem simpler:

Let $A$ be some set of strings.
Define a function $f$ such that $f(x_i) \rightarrow y_i$ with $y_i \neq y_j$ for all $i,j \notin A$ with $i \neq j$, and otherwise $f(x_i) \rightarrow y$ where $y \notin \{y_i \mid i \notin A\}$ is constant.

Is it possible? In addition, is it possible for performance of such a hash function not to depend on the size of $A$?


texts: I an brushing up on Dijkstra (specifically Wikipedia's pseudocode) and can't resolve this counter example. I want the shortest path between A and E. I would move from A to C to D, where D would have a cost of 105. Once I mark D as visited I no longer have an opportunity to find the correct path A to B to D to E. What am I missing?


texts: Why do source and sink have to be distinct in Ford-Fulkerson?

texts: Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard, doing this allows infinite flow. However if you take a graph where the source (which equals the sink) has no arcs leading into it shouldn't the max flow be $0$?


texts: Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

texts: I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as when we find non-trivial answers they have a gcd above 1 etc.). However, when a number solely has prime factors of form $4k+1$ this seems to be a more difficult reduction that needs multiple representations and these types of approaches seem to be bound to condition very often. This equivalence seems interesting because it connects computational problems in summation with problems in multiplication. Does anyone know of the/a reduction?


texts: Polysize bounded depth circuit for modified MAJORITY problem

texts:
I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 - n/\log n$. This is a modified form of the MAJORITY problem.

I want to use the probabilistic method but I cant seem to get it to work. I found a way to get a circuit that was not of bounded depth, iterate a bunch of random layers of gates that compute the MAJORITY function for three randomly selected inputs. This will, for $\mathcal{O}(\log n)$ depth, give the right result with overwhelming probability, so one such circuit is always correct.

I think I should have layers of alternating AND and OR gates, but since the $n/\log n$ factor is so small, even when we should get a $1$ for instance, the probability that a random input is a $1$ is only $1/2 + 1/\log n$, not really so high. I cannot seem to amplify this enough to take care of both cases.

Any help?


texts: Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups

texts: Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time chosen the vertex with highest number of edges, or something similar


texts: What class this graph connectivity problem belong to

texts:
We are given a Boolean circuit $C(x_1, \dots, x_n,y_1, \dots, y_n)$ with $2n$ inputs and we have to determine if the graph $G_C = (V_C, E_C)$ (specified below) is connected:
$$V_C = \{0,1\}^n, \\ E_C = \{((a_1, \dots, a_n), (b_1, \dots, b_n)) : C(a_1, \dots, a_n,b_1, \dots,b_n) = 1\}.$$
To which class this problem belongs? I know that graph connectivity can be done so fast (as fast as to be in P) and using a small amount of space. Does this is different in this particular graph? Is this problem in P, EXP, PSPACE?


texts: Are there any problems that are easy to compute but hard to verify?

texts:
Assuming P $\neq$ NP, NP-complete problems are "hard to solve, but have answers that are easy to check."  Does it make any sense to consider the opposite, that is, problems for which it's easy to compute a correct answer, but hard to verify an arbitrary purported solution?

I think such a problem would imply either:

Exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.
Some "correct" answers are easy to compute, but others are difficult to find.


texts: Why does TSP require no repetition of cities?

texts: It seems odd to me that the TSP denies the possibility of repeated cities.  The goal of this traveling salesman is to go as fast as possible and visit all of the cities, right?  So what if it is faster to travel through a city you have already been to?


texts: Does Hindley-Milner refer to the unification algorithm for type reconstruction, a type system, or a form of polymorphism?

texts:
What does Hindely-Milner refer to?

In Types and Programming Languages by Pierce, I only find that Section 22.4 Unification mentions "Hindley" and "Milner", when introducing the unification algorithm.

Does Hindley-Milner refer to the unification algorithm for type reconstruction/inference?
https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system refers to Hindley-Milner as a type system.

Where does Types and Programming Languages by Pierce define Hindley-Milner as a typing system?

Is a Hindley-Milner type system the same one which I heard:

  Hindley-Milner is a special and restricted form of parametric polymorphism, in that it only allows ∀ to appear at the beginning of a type. That is, you cannot have types like ∀α.(∀β.β→β)→α.

?
What is the relation between Hindley-Milner as a type reconstruction/inference algorithm and as a type system?

Does the unification algorithm by Hindley and Milner apply only to the Hindley-Milner type system?

Does type reconstruction/inference (what I saw in Ch22 Type Reconstruction in Pierce's book) only apply to polymorphic systems, not to monomorphic systems?

Section 22.2 defines type reconstruction/inference as:

  "Is some substitution instance of t well typed?” That is, can we ﬁnd a type substitition σ such that σΓ |- σt : T for some T?

  Looking for valid instantiations of type variables leads to the idea of type reconstruction (sometimes called type inference),

The footnote of Ch22 on p317 says

  The system studied in this chapter is the simply typed lambda-calculus (Figure 9-1) with booleans (8-1), numbers (8-2), and an inﬁnite collection of base types (11-1). The corresponding OCaml implementations are recon and fullrecon.

Does that imply that type reconstruction/inference only apply to polymorphic systems or also to monomorphic systems?

Thanks.

Also appreciate if you could consider What is "Hindley-Milner (i.e., uniﬁcation-based) polymorphism"?


texts: Runtime of a recursive algorithm to find a path in a DAG

texts:
About the following algorithm:

reach(Vertex s, Vertex t):
    if s = t return TRUE
    else
        for v in Adj(s) do
            if reach(v,t) return TRUE
        return FALSE

Why can we say that its runtime on a directed acyclic graph is $O(n!)$?

I can see why there are $n!$ different paths in the graph, is it because in each of those $n!$ paths, the loop will run at most $n$ times?


texts: Language of Turing machines that never visit some given state

texts:
Can someone help me to determine and prove if the following language is decidable or not?

I tried to think on some reductions but I can't figure it out...

$$A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$$

my try:

I built mapping reduce $E_{TM}\le_{m} B$:

$<M>\rightarrow <M>$

so I need to prove:
$$<M>\in E_{TM}\iff <M>\in B$$

First direction:

$<M>\in E_{TM}\rightarrow L(M)=\emptyset \rightarrow M \text{  never visits  }  q_{accept} \rightarrow  <M>\in B $

The problem is in the second direction. How can I promiss that if the language is empty $M$ visits all the states?

Thanks!


texts:
I am trying to implement a Gauss-Newton algorithm for non-linear optimisation. Unfortunately despite searching through the library and the internet I can't figure out quite how to use it in my case. As such I am hoping that I have come to the right place to ask for some assistance? Thank you to anyone willing to help me.

My problem consists of minimising a function $f(\vec x)$ where $\mathbb R^n \ni \vec x = (x_1, \dots ,x_n)$ and $f:\mathbb R^n\rightarrow \mathbb R$. Physically $f$ is a chi squared value $f=y-e(\vec x)$ where $y$ is the target value and $e(\vec x)$ is the test function evaluated at guess $\vec x$.

I begin by computing $f(\vec x+\delta \vec x)$ and  $f(\vec x)$. Here $\vec x+\delta \vec x=x_1+\delta x_1,\dots , x_n+\delta x_n$.  I then evaluate numerical derivatives using the following quotient formula,
\begin{equation}
\frac{\partial f(\vec x)}{\partial x_i} = \frac{f(x_1,\dots , x_i+\delta x_i,\dots ,x_n)-f(\vec x)}{\delta x_i}\qquad \forall i =1,\dots ,n
\end{equation}
I must then combine this into the Jacobian $\vec J$,
\begin{equation}
\vec J = \bigg(\frac{\partial f(\vec x)}{\partial x_1}\ \frac{\partial f(\vec x)}{\partial x_2} \cdots \frac{\partial f(\vec x)}{\partial x_n}\bigg)
\end{equation}
I can take the transpose of $\vec J$ denoted $\vec J^T$.

So far I can code the above (in C++). However The next part becomes confusing for me personally. In particular I do not know how to write the following matrix equation.
\begin{equation}
(\vec J \vec J^T)\delta \vec x = \vec Jf
\end{equation}
In fact I am not certain that this is the correct procedure?

Therefore, with numerical derivatives in place how can I obtain $\delta \vec x$ for the next iteration of the descent? Again many thanks for your time.


texts: Simulated annealing upper bound seems way too high

texts:
In a nutshell
I found this paper that provides an upper bound for the amount of iterations we expect before visiting the global optimum at least once. (It then uses that number to find a lower bound on the probability of finding the optimum within a given number of steps). The trouble is, when I plugged in some numbers for the formula given in the paper, the number of iterations was so impossibly high, it would be useless. I must not have understood the paper as well as I thought. Can anyone explain why that is, or what's really going on with this formula?
My understanding so far
Stated in Lemma 3.1, the expected number of steps before the global optimal state is less than $(d \exp(\Delta / T))^D$. We're modeling the transitions between candidate solutions as a Markov process, so there's an underlying graph. The variable $d$ represents the max degree of that graph and $D$ represents the diameter, the largest distance (minimal path) between two states. In this context, $\Delta$ is the largest difference between any two state's costs out of every pair, and $T$ is the minimum temperature.
I used the traveling salesman problem to use a concrete example. The way I figured, if the method of finding new states is swapping two cities in the path, then the degree of the graph of the Markov chain would be $d={n\choose2}$, where $n$ is the number of cities. In trying to get the diameter, I used $n-1$, since I figured the worst you could do trying to get from one path to another was to swap and put each city in its place. The last city would be in the right place automatically.
For $\Delta$ and $T$, it really doesn't matter what I pick. If I plug $n=10$ into the equation $({n\choose 2}\exp(1))^{n-1}$, I get something on the order of $10^{18}$. A larger, slightly more realistic delta, like 100, breaks the calculator, it's so large.
Either my numbers for my example using TSP are way off, or I didn't understand the paper, or maybe the upper bound is too large to be useful. Possibly a fourth thing I haven't thought of. So what's going on? Thanks in advance.
PS
If you know of any better reasons why SA works, that would be appreciated as well, since that's the ultimate goal of this inquiry. The idea of saying "it will have visited the best state within $k$ steps with probability $p$" appealed to me, but it hasn't been working out too well. I was trying to get a better understanding of why simulated annealing works. The intuitive explanation of striking a balance between a random walk and hill climbing works on some level, but I wanted a more mathematical understanding.


texts: Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$

texts:
I am trying to implement a context-free grammar for $L=\{a^n b^m \mid n \neq 2m\}$.

I have a difficulty trying to implement it because I don't know how to ensure that $n \neq 2m$.

I can easily implement $n=2m$ but the other way around doesn't seem intuitive. How can I approach this problem?


texts: Generate random point inside a polyhedron

texts:
I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)?

I find approaches for 2D case like the one described here but none in the case of polyhedrons(3D). Whether extending this approach for 2D is the only way, in which case that random point will still be forced to be on the surface of a triangle of a tetrahedron in the 3D triangulation of the given polyhedron?


texts: Is Equational Reasoning an application of Referential Transparency?

texts:
In various discussions of the merits of functional programming, the phrase referential transparency or equational reasoning is often listed.

My question is - are these roughly the same thing? (One being the concept, and the second being the process of applying the concept?


texts: Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$

texts:
The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$.

We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*w\}$. Two grammars are equivalent if the quadruple of $G_1 = (\Sigma_1,N_1,P_1,\sigma_1)$ and $G_2 = (\Sigma_2,N_2,P_2,\sigma_2)$ generate the same formal languages.

I think this statement is true, because they have to accept the same formal languages regardless if its called multiple times.

I'm asking this question so someone can confirm it, knows an exception, or has a proof.


texts: Product construction for given two finite automata

texts:
I need to construct a finite automata which accept a language $L =  L_1 \cap L_2$, where $L_1$ and $L_2$ are given below.

$L_1 = \{  w \mid w $ is divisible by 2 }

$L_1 = \{ w  \mid w $ is divisible by 3 }

I know how to design a finite automata for a single number but how do I combine the automatons which check divisibility by 2 and 3? I am able to combine the initial states of the two automatons by using ϵ transitions from a new state but how can I combine the final states of the two automatons? Input is in the set of decimal numbers Σ = {0,1,2,3,4,5,6,7,8,9}


texts: Difference longest path problem and underlying decision problem

texts:
I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-complete.
I have some trouble understanding the difference between the two though. How are they not the same? I read in another post on CS that decision problems are conceptually easier to understand. But does this mean there are solutions to this problem with NP-hard complexity?
As I understood from my professor a graph problem is in NP if there are exponentially many paths to test in terms of the graph size. As you might notice, this definition does not talk about possible solutions/algorithms.
Also, all the references I found only talk about solutions to the problem, but don't give any formal definition. Quoting wikipedia as a source for my work looks kind of messy. So if anybody knows a paper that nicely describes the problem formally, any tips are welcome.


texts: Computer Networks, bandwidth calculation

texts:
I don't know if this is the right place to ask this kind of questions, but I'm a little desperate and I can't find the answer to this Computer Networks exam question.

"A point to point 1000 km connection uses a Idle RQ frame protocol with a frame of 1 KByte. Calculate the bandwidth to use at its maximum the line. Is it possible to increment the bandwidth by incrementing the frame size? Why?"

I've tried to reverse the formula for the efficiency calculation by putting U = 1 but it seems to be impossible because the last step turns out to be bw = 0

I also tried to relate the frame size and the bandwidth but that's something used for the CSMA/CD which is not involved in this excercise

Thank you in advance for your help


texts:
I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper.

At the moment I have the following:

K- no restrictions on the frame, NPComplete

T- reflexive, NPComplete

K4- transitive, PSpaceComplete

S4 and S4.3 also PSpaceComplete

S5- symmetric, transitive and reflexive, NPComplete.

I am not able to find any results regarding complexity of the following axioms for modal logic:

D- serial

KB- symmetric

B- reflexive, symmetric

The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.


texts: Next Word Prediction using n-gram & Tries

texts: I am studying the following paper for understanding next-word prediction using n-gram & trie: - http://nlp.cs.berkeley.edu/pubs/Pauls-Klein_2011_LM_paper.pdf Before this, I did some brief study on what are n-grams. And, I know trie data structure. The issue is - the algorithm in paper is not so intuitive to understand. Anyone can provide some better/intuitive explanation of this algorithm, or some similar Language Model Implementation. I am new to this site, so if this question structure is inappropriate to this site, please guide. Thanks in advance.


texts: How do I get the solution for a recursion with n! using Master Theorem?

texts:
The problem in my book is T(n) = 16T(n/4) + n!

I don't know how to get at the correct solution my book has, which says Θ(n!)

here are pictures of the master theorem and the problem in my book.


texts: In predicate logic, is the "environment" only needed when free variables are present?

texts: Suppose there exist no free variables in a given predicate logic formula. Is then a model alone sufficient to fully interpret the formula and make inferences? Don't we need an environment or variable lookup table (as often mentioned)?


texts:
$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$

I am trying to reduce 3SAT to this problem but can't find a way. I tried taking a small example $\phi=(x_1 \vee x_2) \wedge (\overline{x_1} \vee x_2 ) $. In this example the formula can only be satisfied only when both $x_1,x_2$ are True. How do I reduce such a case of 3SAT to ExactOneSAT ?
This is an exercise from Sanjeev Arora and Barak Boaz : A modern approach to complexity, but not a homework exercise.


texts:
Here is a picture from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 207(English Version)/Page 206(Japanese Version):

I want to verify whether my interpretation is correct or not. My interpretation is in the picture that has red arrows.

From the picture, I made a table to understand easily the internal condition of Nasa Convolutional code.

So from my interpretation, I got

Out1:Input+S2+S3+S5+S6 .. formula(1)
Out2:Input+S1+S2+S3+S6.. formula(2)

From the excerpt Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

We know that when internal state is 100000, the output will be 11.However, when I use formula(1) and formula(2), I didn't get 11 but instead I got 10.

Out1:Input+S2+S3+S5+S6=1+0+0+0+0=1
Out2:Input+S1+S2+S3+S6=1+1+0+0+0=0

My question is, is my interpretation is correct? If it's correct, why don't I get the output 11? If it's wrong, where did I get it wrong? Please teach and correct me.


texts: Pushdown Automata - can you have multiple transition functions options between 2 states?

texts:
I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 0 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1
 - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1
 - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven't seen any that have multiple options to transition between states and was wondering if it was allowed.


texts: In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions?

texts:
As I understand it in dataflow programming, programs are structured as directed graphs, an example of which is below

Is it true to say that the arrows (or edges) represent the variables within a program and the vertexes (blue circles) represent programmatic functions? Or is this too much of a simplification?
I am interested in understanding how dataflow languages actually apply graph theory.


texts:
Considering plain RSA encryption, assume we have B who wants to send 10 messages to either A1 or A2. The recipients' public key, namely the exponent e1, e2 and prime product n1, n2 for A1/A2 respectively, is publicly known.

When B sends out, he will either encrypt his messages via $c_i = (m_i)^{e_1} mod (n_1)$ or $c_i = (m_i)^{e_2} mod (n_2)$

Let's assume eavesdropper E gets hold of the 10 encrypted messages $c_i$. Given that she knows e1, e2, n1, n2 - while she can't figure out the messages m themselves, can she figure out whether B sent the messages to A1 or A2, and if so, how?


texts: Optimal algorithm for finding the girth of a sparse graph?

texts:
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.


texts: Can we define feature relevance in terms of regression coefficients? Lots of works report definition of feature relevance in terms of probability and mutual information but I did not find any literature defining the relevance of features in terms of regression coefficients although many works have experimentally proved this.