texts: What is the Effect of Hidden Layer Size?

texts:
I aim to gain more intuition with regards to the role of a hidden layer in a neural network architecture. And further to understand whether my classification problem is a linear one or not.

Here is what I have: I have a input of size 128 which is the output of the FFT of a multi-tone signal. Bellow you can find one input sample (vector size of 128 features):

In my dataset, for each input sample the peaks are randomly located across 128 frequencies 90-127Hz].

The output is simply the number of the peaks in the input samples (FFT). f0r example the output/label for the provided sample in the figure is 8. I have total of 10 labels/classes, ranges from 1 to 10.

My data-set consists of 1000 samples/rows.

I choose the fully connected feedforward network with one hidden layer to be training using my datasest. thats is my network has 128 (+ 1 bios) units in the input layer, 1 hidden layer and the output layer with 10 unit in it.

To understand the effect of the the hidden layer in training and testing, I set up a simulation where I train my network 100 times per number of units in the hidden layer. The number of units in the hidden layer ranges from 0 (no hidden layer) to 40 units.

I used neural network toolbox in MATLAB to program this. Moreover, I utilized patternet command and used the default setting for configuration of network: the training function is traincg, the loss function to minimize error is cross-entropy loss, and I use softmax fuction for the output layer.

I configure the network, as well as initialize the weights before training.

And finally, for the training the network, I partition my data-set to 70/15/15 ratio corresponding to train/validation/test data blocks.

To gain a better insight, I plotted the misclassification error of network vs. the number of units in the hidden layer on the testing data block, which you can find below:

now here are my questions:

a) Given the fact that I have the best performance when the network does not have a hidden layer,
--is my classification problem a linear or a non-linear?
--Are my classes linearly separable or not? (consider the high dimension of my input, 128)

b) Referring to the Fig. 2,
--Why does the network using one hidden layer with 10 units (or around 10) produce the "second" most optimum performance among?
--is it because I have 10 classes?
--Moreover, if I have only two classes, would the network with one hidden layer size two get the better classification accuracy, or we can't answer this?

c) what is the role of the hidden layer?

Given the proven power of such technique in many complex real world problems, utilizing the neural network for this problem is over-kill. As the main goals is to have deep intuition on the neural network power in classification, I choose this toy problem.

I would appreciate if someone could answer above questions to help me have better insight regarding choosing the suitable network architecture. I can provide more details in case more clarification is needed.


texts: Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

texts:
Here is a quote from the Source 1:

  For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

But here is a quote from the Source 2:

  If you have an oracle for the halting problem, then you can compute the Busy Beaver function. Given an input $n$, just search through all Turing machines with $n$ states and check whether they halt or not. For the TMs that halt, run them through to completion, and count the number of steps or symbols printed. Keep track of the maximum score. After you have run through all possible Turing machines, you will have the Busy Beaver number.

I can imagine how this would work for the first-order oracle machine simulating a no-oracle machine, but I cannot understand how an oracle machine of the arbitrary order would simulate the lower-order oracle machine, assuming that the simulated machine can also simulate another machine with the arbitrary level of "nested" oracles!

For example, consider the computation process of a 4th-order oracle Turing machine equipped with a halting oracle for the 3rd-order oracle Turing machine. At some moment the program starts simulating some program for, say, 2nd-order machine. But how does the oracle interprets the content on the oracle tape when the simulated program goes into ASK state? If the oracle interprets this content as the question for the 4-th order machine, then the simulation is absolutely meaningless because the answer would not correspond to the answer provided by the simulated (2nd-order) oracle.

But if the mathematically correct simulation cannot be performed, then how would an $x$-th-order Turing machine with a halting oracle for the $(x-1)$-th-order machine compute the Busy Beaver number of any $(x-y)$-th Turing machine (where $1 \geq y \geq x$ and $y$ is a natural number)?

If such simulations can be performed without logical paradoxes, then is it possible to provide a pseudocode (similarly to this answer) that shows how some 5-th order oracle Turing machine obtains a value of $BB_4(x)$, and then the value of $BB_2(x)$?


texts:
I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:

1. Build a max-heap out of the unsorted array, say A. (O(n))
2. Exchange root of the heap (max element in the heap) with the last
   element of the heap.
3. Decrement the heap size by 1.
4. Run MAX-HEAPIFY on A(1).
5. Keep repeating steps 2-4 until all elements have been sorted.

The step 3 takes time O(lg m), where m is the current size of the shrinking heap being max-heapified (m ranges from (A.length - 1) to 2). So the total time taken max-heapifying would be Σlg(n - j) where the summation runs from j = 1 to j = n-2. So the total time taken would be lg((n-1)!). We know that lg((n-1)!) < nlgn. So how can nlgn be the lower bound? (It should be lg((n-1)!) as per the above). Its ok if we are talking about the upper bound since nlgn is greater always, and we can say that heap sort in worst case takes O(n lg n).

I understand that the algorithm can have worst-case running time that is both O(nlgn) and Ω(nlgn); the former specifying an upper bound, and the latter the lower bound. What I understand is that the if runtime is Ω(nlgn), it means that the algorithm will take time of the order of nlgn lower bound. My question is different. The time taken in case of heap sort should Σlg(n - j), summing all the run times of max-heapify instances, which comes out to be lg((n-1)!. So heapsort in the worst case should have a run time of Ω(lg((n-1)!) instead of Ω(nlgn) ; also lg((n-1)!) < nlgn (since nlgn = lg (n raised to n)) Please correct me if wrong.


texts: Finding an index such that $A[i] = i$ in a strictly increasing integer array

texts:
I'm looking for a hint for solving the following problem :

  Given an array $A[1, \dots, k]$ of integers where $A[1] < A[2] < \dots < A[k]$
  write pseudocode for an algorithm that determines whether $A[j]=j$ for some $j\in \{1,\dots,k\}$. Worst-case running time should be $\Theta(\log k)$.

I shall find an easy to calculate criteria which finds the index involving the special structure of $A$.

Let's say $A = [-3 , 2 , 4, 5, 7, 8, 9, 10]$. My first approach would be to subdivide $A$ into two parts around the median (here $A[4]$). Since $A[4] = 5 > 4$ and the sequence keeps increasing, I don't have to look at $A[4,\dots,8]$.

My criterion would then be: For a sequence of numbers $A[a, \dots, b]$, if $A[a] > a$, then the solution can't be in that sequence since $A[a]< \dots < A[b]$.

Am I going in the right direction?


texts: If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?


texts:
How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound;
$$2^x -x^2 < 2^x + x^2 < 2^{x+1} = 2.2^n $$
Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?


texts: How are the web based compilers designed?

texts:
Is it possible to design a compiler that can safely compile and run untrusted code?

As a practical example, I want to know how the online compilers are designed/programmed?(Like the one on codepad.org) Are they similar to our traditional day-to-day compiler. How they are hosted on servers?


texts: How to find total number of minimum spanning trees in a graph with n edges?

texts:
I had this question on my final exam so sadly I don't have the question but as far as I remember, the question was saying:

  How many minimum spanning trees does a graph with 20 edges have.

I know that we can find minimum spanning trees with algorithms like Prim's algorithm etc. But how can we know the total number of minimum spanning trees in a graph with no figure given in the question (text only)?


texts: page table size in a 1 and 2 levels page table

texts:
Consider that  virtual page numbers are 36 bits, and page table entries, as well as pointers to other page tables are 4 bytes each.
First , if we need to calculate how much memory would a single level page table require , my answer is that we have 2^36 pages and since every page entry is 4 byte , therefore the answer will be (2^36)*4 bytes. Is that right ?
Secondly , can someone help me to calculate how much memory would a two level page table require and assume the bits are divided evenly between the two levels?


texts: Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

texts:
Is there a way to solve this recurrence using master theorem:

$$T(n) = 4T(n/2) + Θ(n^2/\log n)$$


texts:
Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points.

How about the other way around? Given a subdivision of (2D) space, how to determine unknown generators? Are there any common ways to do this?

Things I could think of were, assuming an underlying Delaunay triangulation, equal distances to Voronoi Vertices/"Delaunay Circumcenters", resulting in a system of quadratic equations.

Or searching for circles in the graph given by the Voronoi Vertices, and determining the center of the resulting polygons.

There is also a relationship to k-means clustering, as clusters defined by k-means, being the generators, yield a Voronoi Diagram in turn. This would leave me having to determine k and populate the regions with elements that are precisely not equidistant to two means.

I feel likely to be missing something very obvious and I would be happy for any direction in which to get started.


texts: Why Miller–Rabin instead of Fermat primality test?

texts:
From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity is the same.

The following is from the Fermat primality test:

  While Carmichael numbers are substantially rarer than prime
  numbers,1 there are enough of them that Fermat's primality test is
  often not used in the above form. Instead, other more powerful
  extensions of the Fermat test, such as Baillie-PSW, Miller-Rabin, and
  Solovay-Strassen are more commonly used.

What is the benefit of Miller-Rabin and why it is said to be more powerful than the Fermat primality test?


texts: Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

texts:
I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$.

However, I'm failing to see how that language would contain strings such as $bbbaaa$ or $aaabbb$. Am I missing something or is that regular expression incorrect? The expression I come up with was $ \left( \left( \left( a \cup b \right) ^*a \right) ^* \left( c \cup a \right) ^* \right) ^*b^* $


texts: Prove for Rice’s Theorem(Is the reduction used ? )

texts:
I was reading formal proof of Rice theorem in wikipedia: https://en.wikipedia.org/wiki/Rice%27s_theorem#Formal_proof
I want to know is what we used here is the reduction algorithm : we reduce the Halt problem language to the semantic problem language?
Thank you so much


texts: NP-Hard problems which are not NP-Complete

texts:
Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others.
Is it always true that a ${\sf NP}$-complete problem is always a decision problem such as vertex cover of size $k$, independent set of size $k$ and many others.


texts: Calculate number of cache lines per set or cache size

texts:
How can I calculate the number of cache lines per set or the cache size with the given information?

m (number of physical address bits): 32
C (cache size): unknown
B (Block size in bytes): 32
E (number of lines per set): unknown
S (number of cache sets): 32
t (tag bits): 22
s (set index bits): 5
b (block offset bits): 5
associativity unknown

Since we can calculate C with C=B*E*S or E with E=C/(B*S). I just need to know how to calculate C or E.


texts:
I've been reading about hidden Markov models and stumbled upon A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition by Lawrence R. Rabiner (Proc. IEEE, 77(2):257–286, 1989; PDF). The following appears as equation 49 in the section about continuous observations in hidden Markov models:

$$b_j(O) = \sum_{m=1}^M c_{jm}\mathfrak{N}[O, \mu_{jm}, U_{jm}], \quad 1\leq j\leq N\,.$$

What I want to know is how to use this equation given an estimation of the transition, emission, initial probabilities and a given continuous observed sequence to train the hidden Markov model using the Baum–Welch algorithm.

Also I haven't read the rest of the paper, since I already have a good amount of knowledge about discrete hidden Markov models. I'm just trying to learn how to use continuous time series data to train an HMM.


texts: complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$

texts:
A simple question:

What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k < n$?

Would this be in NP-complete or just NP?


texts:
After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for rearranging the tree after deleting an element.

Why is that ?


texts: Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so as to check myself. I need the practice.


texts:
Let's say there is a vector of length $n$:

Require Import Vector.
Variable T:Type.
Variable n:nat.
Variable v:t T n.

"list" gives a function "nth" that demands a default result that is returned when the list is longer than the index requested. This is convenient, and the definition is readable.

Now vector uses a definition of nth (using Fin) that assures on type level that the requested Index is smaller than the length of the vector. Confusingly, it also uses a constructor "t", just like Vector. How can I define a function that behaves the same as nth for lists? The definition of nth for vector plainly appears as unreadable to me. Should I use "to_list"?

Was this built this way to keep the type small (in the memory sense)?


texts: Partitioning in time complexity of the sum

texts:
We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete.

My question is - let's denote M as the sum of all numbers in S. Is O(M) considered to be polynomial in this case?

I will clarify: I want to prove that a certain problem is NP-hard, and in order to do so I use a reduction from partitioning that uses O(M) nodes in a graph. Is this considered to be a polynomial build?


texts: How can I make my algorithm more efficient or Is there a better way to solve the problem

texts:
Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you will take a positive number as an input and find out all the multiples of the number in the given array and print it.

Input:
2 4 9 15 21 20
q1 = 2
q2 = 3
q3 = 5

Output:
3
3
2

To solve this problem I thought of an algorithm which works as explained below:

Create an array name freq_data[] whose length will be equal to the maximum element of the array, and it stores the count of each and every number occurred in the input array.
For Example:

  array[] = {2, 4, 9, 15, 21, 20}
  max_element = 21
  freq_data[] = {0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1}

Create an array name multiples[] whose length will also be equal to maximum element encountered in the array. This array will store all the multiples of the numbers between $[1,\text{maximum value}]$. Using multiples[] array, I can answer the query in $O(1)$ time by printing the value at multiples[q - 1].
Initialise the multiples[0] = (size of arr[] - 1) because every number in the array is divisible by 1.
If the query entered is $(\gt \text{maximum value})$ in the array, then the answer will be zero because there will be no element in the array which will be divisible by arr[i] because for the number to be multiple of another, the number should be either equal to or greater than the divisor i.e $(\geq arr[i])$.
Time Complexity: $O(max \times log(max))$
Space Complexity: $O(max)$

Now I was wondering what if I changed the question like instead of taking the queries from the user, I am now interested in finding for each arr[i] how many multiples are present in the left-sub array with respect to arr[i].

Formally: You are given a sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$. Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

For Example:

1. Input:
arr[] = {2 6 3}
Output:
no_of_multiples[] = {0,0,1} // For 2 , 6 there are no multiples present but for 3 there is one multiple present i.e. 6

2. Input:
arr[] = {16,25,63,12,65,45,23,65,78,99,36,12,36,41,36,2,3}
Output:
no_of_multiples[] ={0,0,0,0,0,0,1,0,0,0,2,1,0,2,6,9}

To solve the above problem, the algorithm which I designed is basically based on the previous problem solution but rather than updating the freq_data[] at once I will first check how many multiples of the arr[i] is present in the freq_data[] and after finding all the multiples, I will increment the value at ++freq_data[data[i] - 1] and then I will print the freq_data[i] array after processing the whole arraarr[i].

Time Complexity: $O(n \times log(max))$
Space Complexity: $O(max)$

Solution In C Programming

My question is: Is there any better algorithm to solve the second part i.e Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

Edit-1: With reference to @gnasher729 points, there are constraints on the inputs because if the size of the input gets larger the algorithm will not give the right answer:

$1\leq n \leq 10^5$  Constraint on the length of the sequence
$1 \leq arr[i] \leq 10^6$ Constraint on the values of the sequence


texts: Nested Loop Time Complexity vs Successive Loops

texts:
An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic time):

for (i = 1; i <= x; i++)
    {
    for (j = 1; j <= i; j++)
        {
           // Some quadratic time calculation of x that gives y & z
        }
    }

A different algorithm using successive loops is created for a given $x$ that outputs the same $y$ & $z$:

for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives y
    }
for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives z
    }

Is the time complexity of the second algorithm $T_s(x)=O(x^2)$?


texts: How can a 64-bit processor address 2^64 different memory locations at a time?

texts:
I understand that a 64-bit processor can hold a 64-bit long address and that a 64-bit address can represent $2^{64}$ different values. But I don't understand why that processor can address $2^{64}$ different locations in memory at one time and thus process billions of billions of GB at a time (theoretically).

I haven't found a satisfying answer on google. On google they just explain that a 64-bit address can represent $2^{64}$ different values and thus it equates to the processor being able to process $2^{64}$ values (or memory locations) at a single time, though I am interested in as much detail as possible regarding how exactly that looks like.

64-bit address means for me that this address can have one of $2^{64}$ possible values and not that it can process $2^{64}$ at a time.


texts: minimum cardinality maximal matching of graph

texts:
How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.


texts:
According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel with operator. Actually i dont understand the rules which tells how to build such table.
For example take last production term   -> '(' expr ')' do we use rule terminal nonterminal because of ( expr or  do we use rule nonterminal terminal because of expr ) or do we use rule terminal nonterminal terminal shoudl we divide production or treat as whole? Then is there any other rule applicable in example from link then terminal nonterminal terminal ?


texts: How to decide whether a real life problem can be dealt with by computers?

texts: I get that complexity theory will be helpful to decide whether the resources at hand can deal with a mathematical function, but when presented with a non-purely mathematical problem - like building a robot that can cook, drive or make beds - how can we know whether it's feasible?


texts:
I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations.

As far as I can see, the sites that I found (CodeChef, Project Euler) seem to be more programming oriented, even if I like the format and their challenge. That is, even when speed is somehow important, you cannot not know the exact complexities values for the algorithm (the lovely greek letters), maybe some demonstration of the efficiency of the solution.

An online course or a book is acceptable if it is more problems oriented. In my opinion, these are the kind of questions that a development top company should ask anyway.


texts:
Is there a good data structure for storing overlapping sets? Consider having multiple sets which can overlap in various ways and would like to store them in the memory and access efficient way.

Example:
A = {a, b, c, d}
B = {a, b, c}
C = {b, c, d}
D = {a, b, d, e, f}

Storage:
W = {e}
X = {b, c}
Y = {d}
Z = {a}

B = Z union X
A = B union Y
C = X union Y
D = A union W


texts: Number of weight-balanced nodes in binary tree

texts:
I have to show that a binary tree with $n$ nodes has at least $(n-1)/2$ weight-balanced nodes and at most $n-1$ weight-balanced nodes. Here a node is weight-balanced if its siblings satisfy $\operatorname{weight}(u) \leq 2\operatorname{weight}(v)$.
So we get at least $(n-1)/2$ (where $n$ is positive and odd) if the one sibling satisfies $\operatorname{weight}(u)≤2\operatorname{weight}(v)$ and the other one doesn't (i.e. half of them when we disregard the root node).
And we get at most $n-1$ if both siblings satisfy $\operatorname{weight}(u)≤2\operatorname{weight}(v)$, so all nodes are weight-balanced except for the root node.
But how can I formally show that?


texts:
I'm trying to understand how LZW decodes a string.
For example suppose that we have a dictionary where:

a=0
b=1

and we have to encode the string "aabbabaabb", so the output of the encoding process (if I have not made mistakes) produces the string "0011324" and the dictionary became(using a tree representation):

(source: f.cl.ly)
The decoder will just know "0011324" and the starting dictionary where there are just a=0 and b=1.

How does it work the decoding process with just these 2 informations?


texts: What problem is to the set packing problem, as the hitting set problem to the set cover problem?

texts:
Wikipedia says that

  Set covering is equivalent to the hitting set problem

What problem is to the set packing problem, as the hitting set problem is to the set cover problem?

Is it that given the ground set $U$, and a collection of its subsets, $S \subseteq \mathcal P(U)$, find a $H \subseteq U$, so that $|H \cap S_i | \leq 1, \forall S_i \in S$, and maximize $|H|$.

What is the name of a set $H$ that satisfies $|H \cap S_i | \leq 1, \forall S_i \in S$  in this problem? I.e. the counter part of a hitting set in the hitting set problem?

Thanks.


texts: Why is it considered hard to maintain strong consistency in a distributed system?

texts:
Why can't you just use strongly consistent reads for all your DB reads, with retries on 500 responses? According to CAP theorem increasing consistency should probably lower availability, but can't the decreased availability (increased 500 responses) be handled fairly easily using retries? (assuming you are fine with a small percentage of queries taking a bit longer due to retries)
Using DynamoDB as an example, but this can be generalized to any noSQL cloud offering - It also seems like DDB with on demand scaling will simply increase your read capacity units (RCU) used if you turn on strong consistency, incurring a higher cost ($) but keeping the same latency on db queries, so it seems like the negative is only higher cost. It seems like you can just keep vertical scaling the DB's processing power to meet your needs. Is it actually plausible that with a noSQL cloud database with a high traffic level, you cannot just throw enough money at it, and it could hit some scaling limit to make strongly consistent reads slower?
And then with regard to the entire question generalized to distributed systems, what does it actually mean for a distributed system to be 'strongly consistent.' I've heard this used to describe systems before but I don't actually know it means beyond 'all DB interactions being strongly consistent.'

My second question might be more basic level but necessary to understand the cost of providing consistency, but why do consistent read issues actually occur, ie. why does stale data occur (in single queries like read/write, not transactions with multiple reads/writes per transaction)?
From what I understand, with decreasing probability any time after a write occurs, it's possible for one reader to read correct data, then a second reader to read stale data AFTER the first reader reads correct data (correct me if this isn't actually true, but my understanding was it is). Why does this happen? Doesn't a read just involve a read from some location on the disk?


texts: Regular expression for language with even number of 0's and 1's

texts:
Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s?

If we only require an even number of $0$'s, the language $(1^*)\mid(1^*01^*01^*)^*$ works. But once there is a requirement on both $0$'s and $1$'s, I'm not sure how to do it.


texts: How to determine the fewest number of comparisons for Heapsort?

texts:
I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case.

In its average case, Heapsort only requires $2n\log(n) - O(n)$ comparisons, although I don't know how to prove the best case scenario.

Can someone possibly hint me where to start with my calculation, I have no idea how to prove fewest number of comparisons, always been either worst case or most comparisons up until now.


texts: A context-free grammar for all strings that end in b and have an even number of bs

texts:
I'm trying to find CFG's that generate a regular language over the alphabet {a b}

I believe I got this one right: All strings that end in b and have an even number of b's in total:

$\qquad S \to SS \\
\qquad S \to YbYb \mid \varepsilon \\
\qquad Y \to aY \mid \varepsilon$

However, Im not sure how to accomplish this with an odd number of b's.

So for example, how could I find a CFG that generates all strings that end in b and have an odd number of b's in total: So far I have this,

$\qquad S \to SS \\
 \qquad S \to YYb \mid \varepsilon \\
 \qquad Y \to abY \mid baY \mid \varepsilon$

But this can generate abababb so it's incorrect and Im stumped at this point.


texts:
Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard.

As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By conflating one of the colors in the 3-coloring you have a 4-coloring, ergo 4-coloring is hard.

That's the how. But why is this a proof that 4-coloring is hard? Is it that you can use the solution to the 4-coloring problem to solve the 3-coloring problem? If so, how? If not, why is it a valid proof?

Bonus q: Must the polynomial reductions be able to go in both ways?

Edit: if you would be able to explain why this is so by an example you would do the internet a favor. I couldn't find this explained in a concrete way anywhere.


texts:
By writing out a number in binary I can arrive at the value of taking the first x number of bits out of it.

For example 00001101 (13) taking the first 6 bit would be 3
                          taking the first 5 bit would be 1
                          taking the first 4 bit would be 0 etc

This results, I can easily compute by spelling out the bits that makes up the number I am operating on, take the first couple of bits I am interested in and convert to binary.

I was wondering if there is any common short hand step which allows the same operation to be done, but in decimals (more like how we can do addition on decimals by carrying digits over) where I can use it to calculate what the result of taking the first x bits from a value y would be without having to mentally convert to a binary representation.


texts: Are there lossless data compression techniques that do not exploit repetitive patterns?

texts:
Lossless Data compression (source coding) algorithms heavily rely on repetitive  pattern (redundancy).

Is there a Lossless Data compression method/algorithm that is independent of repetitive  pattern (redundancy)?

Note:

Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.

Techniques  take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values. This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.

A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums. This is called discrete wavelet transform.


texts: Extension of Tarski's result on the decidability of reals

texts:
Due to Tarski's result, it is well-known that the first-order theory of reals $(\mathbb{R},+,\cdot,<,=,0,1)$ is decidable. I am working on a paper where I need an extension of this result. More precisely, I would like to consider formulas that involve rational functions, rational coefficients, minima and maxima. Trigonometric functions or exponential functions, instead, are excluded.

While this seems to me to be a straightforward consequence of Tarski's result (essentially, rewrite any formula with the above functions into one with polynomials only; e.g., rewrite $\sqrt[2]{x}$ into $\exists z (z^2 = x)$; for two polynomials $p$ and $q$, rewrite the formula $p / q \leq 1$ into $p \leq q$ and so on).

To my surprise, I could not find any paper that formally establishes this.

Before providing the proof on my own, I wanted to ask around whether someone is aware of a paper that establishes this result.


texts: why does relabel take O(VE) time total for unit capacity flow networks?

texts:
It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from  $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ relabelling operations per vertex, each taking $O(V)$ time, for a total of $O(V^3)$ for all relabelling operations.
I'm interested in what happens to these bounds when we restrict edge capacities to be 1. It is clear that there are no more non-saturating pushes, so only saturating pushes, of which there are always $O(VE)$, remain.
However, I found a 1995 phd thesis by a student of Goldberg that claims (on p 13) that when edge capacities are 1 (and thus all pushes are saturating), the relabelling portion takes $O(VE)$ time instead of the usual $O(V^3)$.
How does this $O(VE)$ result follow?


texts: Simplifying $b(abb + abbbb + aba^*bbb)^*$

texts:
I'm having issues simplifying regular expressions. I can't find a method to approach this problem.
How would I approach simplifying this regular expression:
$$b(abb + abbbb + aba^*bbb)^*$$


texts: I'm looking for a construct that is to semantic-analysis what NFA/DFA are to scanning and DPDA is to parsing

texts:
What maps to Semantic Analysis the way automata like Finite State Machines and Pushdown automatons map to Lexing and Parsing?

A couple of years ago I came across a paper that presented such a construct; I don't remember much about the paper to be useful, but here's what I think I remember:

I think the paper was from the late 80s or early 90s,
The construct had/employed a double-ended queue,
Elements were replaced in the queue until the replacement rules could no longer be applied [and replacements were longer sequences than what they replaced],
The paper mentioned that while it mapped to the Semantic Analysis, it was somewhat unwieldy to use.

Any help locating this paper would be most welcome, as would info on other constructs mapping to Semantic Analysis.

Thank you.


texts: Appropriate algorithm or heuristic for task scheduling

texts:
I'm sure this problem has been addressed before, but I'm unable to find an exact description of it.

I have $m$ machines, and $n$ tasks that need processing. Each task takes a variable amount of processing time, $t_i$, but this processing time is constant regardless of which machine processes it.

Each task is also assigned a variable $t_{total,i}$, which is the time at which the task is finished within the process, assuming we start at time 0.

The goal is to minimise $f=\sum_{i=0}^n t_{total,i}$, the sum of each time that each task took to be processed, including waiting time.

This naturally gives a priority to assigning the shortest tasks to be processed first, as well as to distribute the tasks fairly equally between the machines.

Is this described as a formal problem anywhere, or is a simple-case variant of a known problem?

From my research I believe it is a simplified variant of the job-shop scheduling problem, or similar to the multiple knapsack algorithm.


texts:
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.


texts:
I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks to that idle computer.

This is often used in pharmaceutical companies working on protein structure configurations, or as the CS community more commonly knows, the bit mining community.

Any who, i know this is often called grid computing, however there was another name for it. Scapegoating? or something like that. Not quite sure. The term has really been bugging me. Can you guys help me out?


texts: Sorting using comparison is superlinear or sublinear?

texts:
My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?

In more details: we know that sorting using comparison have the achievable lower bound of $O(n\ln n)$ where $n$ is the number of items to be sorted. Now the question of superlinear and sublinear is dependent on what is considered the size of the input, and I am not sure if $n$ is the size here. We have 2 cases:

(a) The input is a full acyclic graph describing the comparison relation. In this case the input size is actually $O(n^{2})$ and the problem is sublinear.

(b) The input is just the item to be sorted, plus the description of a Turing machine that will perform the comparison. Then the input size is $O(n)$ and the problem is superlinear.

Can anyone clarify what is the consensus on this? Some people tell me that sorting with comparison is an example of a problem with a nontrivial lower bound (ie. the lower bound stronger than just by looking at how much information do the algorithm need to know). However, it seemed to me that in fact this is one example where figure out how much information you need is the crux of the problem, and not any combinatorial nature of Turing machine. Thanks.


texts: Turing machine that checks whether a given string is an output of a given machine and input

texts:
Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?
My guess is that the answer is no because this might imply that the set of strings with Kolmogorov complexity greater than or equal to their length is decidable.


texts: Terminology - Ensemble or Bag of classifiers?

texts:
I am working on a classification problem. My algorithm involves splitting the data into several subsets based on a specific feature (e.g. number of XX) then training a classifier on each of these subsets. At test time, the incoming data will be passed to one of the trained classifiers depending this number of XX.

Would such a system be called an ensemble of classifiers or a bag of classifiers ?


texts: What is the point of the "check" array in a triple-array trie?

texts:
I am currently reading the definition of a triple-array trie as described here.

More precisely, I am trying to understand the nature of the three arrays:

  base. Each element in base corresponds to a node of the trie. For a trie node s, base[s] is the starting index within the next and
  check pool (to be explained later) for the row of the node s in the
  transition table.
  next. This array, in coordination with check, provides a pool for the allocation of the sparse vectors for the rows in the trie
  transition table. The vector data, that is, the vector of transitions
  from every node, would be stored in this array.
  check. This array works in parallel to next. It marks the owner of every cell in next. This allows the cells next to one another
  to be allocated to different trie nodes. That means the sparse vectors
  of transitions from more than one node are allowed to be overlapped.

I understand how those three arrays are linked together, but I fail to see the point of the "check" array. It seems to me like you could walk the trie without using the "check" array at all.

What am I missing?


texts: Estimating the run time of a program according to a given CPU performance

texts:
When we have a recurrence relation of a program, as an example:

 T(N) = N log N + 9N + 55

and the CPU capability let's say (10^6) or any other number. What is the formula or the method to estimate the run time (in second) if we run a program represented by a function of N, and a given N "inputs"?


texts: Is the Backus-Naur Form a type 2 grammar? If So why?

texts: I understand that the Backus-Naur Form is utilized to assess and specify type 2 grammar, but is it in itself a form of type 2 grammar?


texts: Randomized linear search -- Why does reducing the sample size make the running time constant?

texts:
I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$):

(1) Pick a random index $i$ from $L = [1, \ldots n]$. If $A[i] = x$, terminate. Otherwise, pick a new random index $i$, still in the list $L = [1, \ldots , n]$. Repeat until we've either found a $j$ such that $A[j] = x$ or until every index in $A$ has been exhausted.

(2) Similar to Algorithm $(1)$, except,for element $i$ at every iteration, we perform $L.\text{remove}(i)$ ($L$ has the index $i$ removed from it). This way, we're guaranteed to terminate within $n$ steps (as opposed to potentially running the algorithm forever, as in (1)).

Now, in (1):

  If we let $X = $ the number of iterations before Algorithm (1) terminates, we have $$X \sim \text{Geo}(1/n)$$ from which we get $E[X] = 1/(1/n) = n.$

In (2):

  Let Y = number of iterations before Algorithm (2) terminates.
  Let $Y_i$ = event that the algorithm terminates after $i$ iterations.

  Then $$P(Y_1) = \frac1n \\ P(Y_2) = \frac{n-1}{n}\left(\frac1{n-1}\right) = \frac1n \\ P(Y_3) = \underbrace{\left(\frac{n-1}n\right)\left(\frac{n-2}{n-1}\right)}_{P(\text{two failures})} \ \underbrace{\left(\frac{1}{n-2}\right)}_{P({\text{one success}})} = \frac1n \\ \vdots \\ P(Y_n) = \frac1n$$

  hence $$E[Y] = \sum_{i=1}^n iP(i \ \text{iterations are required to terminate}) = \sum_{i=1}^n \frac1n = n \cdot \frac1n = 1$$ but this doesn't make any sense. How can the expected number of iterations be constant.

Shouldn't $E[Y]$ vary linearly with $n$? What's going on here?
Also, when calculating the expected running time (of each of these algorithms), how do I take into account the possibility that the given list does not contain the element $x$? Obviously, it increases the expected running time, but by how much?


texts:
I stumbled upon this which looks like a promising way of implementing an orientation test.

I'm not interested in the described adaptive approach, I'm fine with using the naive determinant approach by checking if it evaluates to greater/less/equal 0. As I understand it, the only difference is that the more sophisticated adaptive approach will always work (won't suffer from round-off errors do to floating point arithmetic) whereas the naive determinant approach occasionally fails due to round-off errors. Is this correct?

I'm wondering if there are any easy to implement alternatives to the determinant approach? That is, if someone asked you to implement the orientation test without using the determinant approach, what would you do?


texts:
I am having trouble understanding the affine gap penalty in the following example -

Waterman-Smith-Beyer Algorithm:

\begin{align*}
D_{0,0} &= 0\\
D_{0,j} &= g(j)\\
D_{i,0} &= g(i)\\
\forall i,j > 0,~ S_{i,j} &= \min \begin{Bmatrix}
\min_{1 \leq k \leq j}{(D_{i,j-k} + g(k))}\\
D_{i-1,j-1} + w(a_i,b_j)\\
\min_{1 \leq k \leq j}{(D_{i-k,j} + g(k))}\\
\end{Bmatrix}
\end{align*}
where $g(k)$ is the gap penalty function and $w$ is the similarity score.

The affine gap penalty here is $g(k) = 1 + k$ and the mismatch score is $1$ and the match score is $0$.

I am not sure where the 3 and 4 come from or the 4 and 5 in cells 1,3 and 2,4. I'm not understanding how the affine gap penalty works here. I understand how the linear gap penalty worked in the Needlemen_Wunsch but not this. Is k the gaps before hand?


texts:
I have these two problems about regular expressions, can you help me?

1) Prove (ab)∗a = a(ba)∗.

I already proved this using induction and the definition of the kleene star * but I want to prove it now using NFAs, I drawed the NFAs for each but they don't seem to be equal from the picture and I'm stuck there.

2) Prove 0∗(11)∗((00)∗0∗(11)∗)∗0 = (0+11+00)∗0

For this I was think of creating a NFA for each side then converting them to a DFA and prove them equal using the product automata but since each side is very big that sounds like too much word to do by hand and I was wondering if there is a faster way.

Thanks in advance


texts:
so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time.

I was wondering how can I find the number of pairs $(i,j)$ in time less than $O(mn)$.  I was trying to use Two-Pointer but it seems that it doesn't work when there duplicate elements because there can be no way of moving one pointer without missing some pairs like $[1, 1, 2, 3, 3]$ and $x = 4$ or maintaining the linear time, unless I'm missing something here.

  Is there is some magical way of finding the number of pairs $(i,j)$ such that $a[i] + a[j] = x$ in less than $O(mn)$ time?


texts: Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays

texts:
Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between processes? I.e. if process A writes to shared memory, process B might not see the change for a while (but process A will see the change immediately).

It seems to me that this might be theoretically impossible if I don't have an upper bound on the delay, but if I do have such an upper bound, is there an algorithm that's a little more clever than just sticking busy-waits for the worst-case delay between the reads and writes of any other non-delay-tolerant algorithm?

(I'm trying to solve this problem: Cross-window synchronization (critical sections) in the browser)


texts: Find a quarrel-free seating order with a greedy algorithm

texts:
I'm revising for an Algorithms exam and looking at a sample question it says :

A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy movie. Some teenagers quarrel with each other all the time. The Problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.
Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm.

In lectures for greedy problems we've only covered Knapsack Problems so Next Fit/Best Fit for Bin Packing. I can't seem to understand how these methods have any relevance to coming up with a solution for the question.
Obviously I don't expect anyone to answer this, since I've not even made an attempt. But in honesty I don't know where to start. If you guys could give me some sort of hints or just general advice because I'm pretty stranded at the minute.


texts: Is there a name for the DAG obtained from a directed graph by collapsing together the strongly connected components?


texts: How to find max margin for non-separable SVM?

texts:
I am new to Machine Learning. Suppose a training set of positive (square) and negative (circle) points is given like:

Obviously there would be no nice linear separator of positive and negative points. So assume there exist a transformation for (x1,x2) points as:
y1 = (x1-5)^2, y2 = (x2-5)^2 in (y1,y2) space. We will then map all positive points to (25,25) and all negative points to (1,1).

Now, the question is how can I find the maximum-margin separator in new space? That is, what curve in the original space transforms to the straight-line boundary in the transformed space? Using that I need to determine that should a new point be considered positive or negative.


texts: Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?

texts: I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I thought there could only possibly be one block, since linear probing will go through all addresses sequentially?


texts:
I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting.  Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows and columns are swapped around pivots.  This is done to minimize the numerical errors by avoiding operations with small floating-point values.

A common approach would be to use for loops for swapping rows, but it would cost $O(n)$ operations to move a row and $O(n)$ to move a column. Using stack and list could be faster.

So the question is, how can stacks and lists be used in an implementation of Gauss-Jordan to efficiently swap columns in a matrix $A$?

I can change rows using pointers, but I can't realize how to use those structures to move columns and do Gauss-Jordan.

EDIT: Sorry i was to tired when create this question, as i'm not from a english speaker native country, i made some mistakes. The questions is about swapping columns using lists and stack. I'm really sorry, i wasted almost week thinking about it.


texts: Machine epsilon vs least positive number

texts:
What is the difference between machine epsilon and least positive number in floating point representation?

If I try to show the floating point number on a number line .Is the gap between exact 0 and the first positive (number which floating point can represent) ,and the gap between two successive numbers, different?

which one is generally  smaller?
and on which factor these two values depends(mantisa or exponent)?


texts:
I am a statistician by training, so am not too familiar with the computer science literature. One of the engineers at the firm I work at told me about problems with A/B testing in Canary releases.

I am well versed with the literature on A/B testing, but in the case of canary release, I am not quite sure what is being tested. The load a service gets over time is going to vary, so using naive tests where you assume independence of some form is not going to make the cut. My particular questions are

1) What is being tested? What are the assumptions about the data

2) What are "the metrics" which people keep mentioning in the blog articles on the subject and

3) In practice, when does an engg. say that systems look in a dangerous state? Does this mean that you see larger fluctuations OR any time you see a very big fluctuation which exceeds the normal expectations?

4) After how much time do you typically decide that you are satisfied with the results, and should deploy to the other nodes?

I am looking for a formal problem setup if possible. Could someone please suggest starting points for me to look at


texts: An example of a code that is neither p-code or s-code but is uniquely decodable?

texts: As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index of the letter in a given alphabet (starting from 0). Clearly it's not p-code and not a s-code and it's uniquely decodable. But I need to find another example of such code. And no, I wont accept {0, 010, 0110, ...}. By the way, code words must consist of 0 and 1, i.e. be binary.


texts: Understanding Property Testing with a toy example

texts:
I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example.

I did not understand the first step of the test in the following slide. Why is the first step $S= 2/\epsilon$?

Could someone please explain me in more detail (i.e. with a concrete example)? I would appreciate with that.


texts: What does Lambda Calculus teach us about data?

texts:
In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing?

Some context: as a software developer, I got used to the concept of data so much that I never considered its true nature. I'd very much appreciate any references that could help me deeper understand the role of data in computation.


texts:
I have a DAG and I want to list all pairs of vertices that are not comparable (there is no path from the first to the second or the second to the first).

In this image (taken from this StackOverflow question):

The output would this:

{B,C}
{B,D}

The output can be $O(n^2)$ so that's a lower bound. My current best algorithm is:

For each vertex X,

Run a search in the graph and note all reachable vertices, then do the same with the direction of arrows reversed.
Output {X,Y} for each vertex Y that you did not reach this way.

But that appears to be $O(nm + n^2)$.

I'm interested in either a faster algorithm or a proof that a faster algorithm doesn't exist.

I tried maintaining a list of predecessors in each node and going through the graph layer-by-layer with a BFS, but the existence of either edges within layers (if I layer by shortest path) or of shortcut edges (such as possibly from A to D in the example above) kept that from working.


texts:
I read that the further you get from 0, the less precision, due the way they are stored.

So why aren't numbers stored like this:
$32$ bits for representing a value between $-2^{31}$ and $2^{31}-1$ before the decimal point and another $32$ bits for representing the precision. $\frac{1}{2^{32}} = 0,00000000023$, which would be a fairly precise interval.

With this type of storage there would be no precision loss at high values.


texts: Functor laws and natural transformations in Haskell

texts:
As I've been struggling to get a deeper understanding of monads in Haskell, I started reading about functors and their counterparts in category theory. Keep in mind that I have no background on the latter.

According to Milewski(1), any polymorphic function of the type F a -> G a, where F and G are functors, automatically satisfies the naturality condition, although I have yet to figure out why. Anyways, this should hold in particular when F is the identity functor, which if understand correctly would correspond to the aforesaid function having the type a -> G a. Now, for simplicity let:

data G a = C a

If G is a functor, then since C :: a -> G a, C is a natural transformation. Viceversa, suppose C is a natural transformation. Thus, for all functions f:

(fmap f) . C == C . f

which I imagine is what leads to the wrapping-unwrapping analogy. In fact, if we render C x as {x} as in "wrapped x", then the previous can be re-written as:

(fmap f) {x} == {f x}

which quite literally means that applying the transformed f to the wrapped value is the same as unwrapping, applying f to the unwrapped value and re-wrap it. By the previous equality:

law 1) (fmap id) {x}      == {id x}
                          == {x}

law 2) (fmap (f . g)) {x} == {(f . g) x}
                          == {f (g x)}
                          == (fmap f) {g x}
                          == (fmap f) ((fmap g) {x})
                          == ((fmap f) . (fmap g)) {x}

It follows that G is a functor.

So is it correct to say that requiring the functor laws on a type constructor is equivalent to requiring that its data constructors satisfy the naturality conditions, or something along these lines? And if not, then what is the purpose of the functor laws from a "practical" point of view?

Edit: I just wanted to clarify that I don't really need an answer to the previous question. What really troubles me is that most tutorials on Haskell's functors make it seem like their wrapper-like nature (on which the intuition behind applicatives and monads is often based) stems from their laws when in reality it seems to be a consequence of the naturality conditions due to Wadler's free theorems(2), unless I'm completely mistaken. What role do the functor laws play in their interpretation as abstractions of some functional programming pattern?

(1) Milewski, B.; Category Theory for Programmers; 164
(2) reasonablypolymorphic.com/blog/theorems-for-free/


texts:
There is as input a set of $m$ sequences of length $n$.

I thought it was pretty straightforward at first that the time complexity of the algorithm provided below is $O(m^2n^4)$ but then it occurred to me that the time taken depends on the length of a LCS such that the longer a LCS relative to the input length the shorter the computation.
The question I have is can you confirm that while the (measured) time taken does depend on the length of a LCS (inversely), that fact does not have an effect on the result of the O-analysis?

// Let there be m sequences of lenght n.

// Length of lcs of two sequences. Theta(n^2)
lcs_length(x, y)
// Edit distance of two sequences. Theta(n^2)
d(x, y) = |x| + |y| - 2*lcs_length(x, y)
// Edit distance (total) of y to all of X. Theta(mn^2)
d(X. y) = sum of d(x, y) for x in X

// Longest common subsequence of a set of sequences S. O(m^2n^4)
lcs(S)
    X <- copy of S
    while true
        if exists x in X: |x| = 0
            return ""
        if exists x in X: for all s in S: x is a subsequence of s
            return x
        for x in X
            d_min <- +infinity
            i_min <- +infinity
            for i in 1..|x|
                // Make a copy of x with the ith symbol removed:
                x_i <- x[0..i-1] + x[i+1...]
                // Compute the sum of edit distances to all of the original sequences:
                d_i <- d(S, x_i)
                if d_i < d_min
                    d_min <- d
                    i_min <- i
        X <- X difference { x }
        X <- X union { x[0..i_min-1] + x[i_min + 1...] }


texts: Are all NP-complete languages log-space reducible to each other?

texts:
NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other?

It seems as if this is true because in log-space, we can have polynomially many computations.


texts:
What are advantages of closed hashing over open hashing?
I know the difference between those two but can't figure out why would closed hashing be better in any way.
Thanks.


texts: Runtime of searching for a number in an array?

texts:
Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).

But how about in the case where we know the number definately exists in the array? Does the runtime change then?

Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?


texts: Complexity time needed for any algorithm

texts: How to understand at least a small introduction to the complexity time for algorithm , how i can know that algorithm need O(log^2 N ) and so on is there any basic reference for this topic , needed in my project


texts: complexity of a variant of the subset sum problem

texts:
We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.

What is the complexity of this problem.


texts: What does "prompt collection" mean in the context of memory management?

texts:
I often see people assert that reference counting techniques such as shared_ptr in C++ provide prompt collection (e.g. here and here) but I am not sure what exactly is meant by this. Some people tell me that they mean "collects at the earliest possible point" but I think that is not true of scope-based reference counting because it defers collection to the end of scope even if a variable is dead. Therefore, I'm wondering if other people have a different interpretation that may be correct.

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting. For example, the following function runs in bounded memory:

let rec loop tmp i =
  if i<=0 then tmp else
    loop (Array.copy (loop (Array.copy tmp) (i-1))) (i-100)

Even though the argument tmp is in scope for the entire body of the function it is collected before even the first recursive call to loop.

EDIT Here is a simpler F# example with a single recursive call and some post-processing to ensure that the call is not in tail position so it cannot be eliminated:

let rec loop tmp i =
  if i<=0 then tmp else
    let tmp = loop (Array.copy tmp) (i-1)
    tmp.[0] <- tmp.[0] + 1
    tmp

Between the copying of the array and the call to loop the argument tmp dies and, indeed, I find that it is garbage collected so this program requires only O(1) space.

Here is the equivalent reference counted C++:

shared_ptr<vector<double> > loop(shared_ptr<vector<double> > tmp, int i) {
    if (i<=0) {
        return tmp;
    } else {
        shared_ptr<vector<double> > tmp1(new vector<double>(*tmp));
        shared_ptr<vector<double> > tmp2 = loop(tmp1, i-1);
        ++(*tmp2)[0];
        return tmp2;
    }
}

Although tmp dies between the creation of tmp1 and the call to loop, scope-based reference counting keeps it allocated until the end of scope. So n recursive calls require O(n) space.


texts: Algorithm for approximation with sum or difference of 2 unit fractions

texts:
Let $U =\{\frac{1}{n}: n\in \mathbb{N}\} \cup \{-\frac{1}{n}: n\in \mathbb{N}\}$ be the set of positive or negative unit fractions.

Given positive integers $m<n \in\mathbb{N}$, how do you find $u_1, u_2 \in U$ such that $|\frac{m}{n} - (u_1+u_2)|$ becomes minimal?

A weaker problem would be the following: Given positive integers $m<n \in\mathbb{N}$ and a positive integer $k\in\mathbb{N}$ devise an algorithm that outputs "Yes" if there exist $u_1, u_2\in U$ such that $|\frac{m}{n} - (u_1+u_2)| < \frac{1}{k}$, and "No" otherwise.


texts: What's the purpose of the "o(1-o)" in the back propagation algorithm

texts: I'm not sure what the purpose of the o(1-o) in the back propagation algorithm achieves? I'm guessing it's related to using the sigmoid function on the output but I'd like to have a proper understanding of the math behind it. Thanks!


texts:
May be it's a stupid question (sorry if it's the case).

What is the complexity the decision problem:

Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$

does there exists $x\in\mathbb{N}^n,x>0$ such that $Ax\geq 0$?

Where $x\geq 0$ means for all $x_i\geq 0$ and $x>0$ means there exists $x_j>0$.

I know that integer linear programming is NP-complete but it's expressed has $Ax\leq b$ and I failed to reduce $Ax\leq b$ to $Ax\geq0$ ...


texts: Let M be a Turing machine not necessarily halting on every input. Construct Turing machine M′ which halts on w if ww ∈ L(M) and does not halt otherwise.


texts: Use a directed graph to express a high-dimensional orthogonal polyhedra

texts:
I have a set of $d$-dimensional hyper-rectangles with integer axes. These hyper-rectangles may overlap. The union of these hyper-rectangles forms a $d$-dimensional orthogonal polyhedra $P$.
I sort the $d$ dimensions in order. So there are dimensions $1,2,3,\cdots,d$. I want to express $P$ by a directed graph $G$ (instead of a set of hyper-rectangles) as follows.

$G$ starts from a single node $P$ (each node of $G$ corresponds an orthogonal polyhedra).

Let $x_1$ be the integer axis of dimension 1. Each value of $x_1$ corresponds a $d-1$-dimensional hyper-plane $H_1(x_1)$ orthogonal to dimension 1. The intersection between $H_1(x_1)$ and $P$ is either empty or a $d-1$-dimensional orthogonal polyhedra $P_2(x_1)$. Different values of $x_1$ may have the same $P_2(x_1)$. Denote all distinct nonempty values of $P_2(x_1)$ by $P_{2,1},P_{2,2},P_{2,3},\cdots$, which are added as nodes to $G$. Draw directed edges $R(P,P_{2,i})$ from $P$ to $P_{2,i}$. $R(P,P_{2,i})$ contains all integer values of $x_1$ such that $P_2(x_1)=P_{2,i}$.

Generally, for $1\le k<d$, let $x_k$ be the axis of dimension $k$. Each value of $(x_1,x_2,x_3,\cdots,x_k)$ corresponds a $d-k$-dimensional hyper-plane $H_k(x_1,x_2,x_3,\cdots,x_k)$. The intersection between $H_k(x_1,x_2,x_3,\cdots,x_k)$ and $P$ is either empty or a $d-k$-dimensional orthogonal polyhedra $P_{k+1}(x_1,x_2,x_3,\cdots,x_k)$. Different values of $(x_1,x_2,x_3,\cdots,x_k)$ may have the same $P_{k+1}(x_1,x_2,x_3,\cdots,x_k)$. Denote all distinct nonempty values of $P_{k+1}(x_1,x_2,x_3,\cdots,x_k)$ by $P_{k+1,1},P_{k+1,2},P_{k+1,3},\cdots$, which are added as nodes to $G$. Let $P_{k,i}=P_k(y_1,y_2,y_3,\cdots,y_{k-1})$ be a node added in the last step. Denote all distinct values of $P_{k+1}(y_1,y_2,y_3,...,y_{k-1},x_k)$ by $P_{k+1,i_1},P_{k+1,i_2},P_{k+1,i_3},\cdots$. Draw directed edges $R(P_{k,i},P_{k+1,i_j})$ from $P_{k,i}$ to $P_{k+1,i_j}$. $R(P_{k,i},P_{k+1,i_j})$ contains all integer values of $x_k$ such that $P_{k+1}(y_1,y_2,y_3,...,y_{k-1},x_k)=P_{k+1,i_j}$.

For $k=d$, $P_{d,1},P_{d,2},P_{d,3},\cdots$ are orthogonal polyhedra of dimension 1 with integer axis, thereby can be expressed by a set of integers.

Is there any efficient algorithm to transform the orthogonal polyhedra $P$ from the rectangle-union expression to the directed-graph expression described above? I guess there should be a specific name of the directed-graph $G$. Maybe the generate graph of P?


texts: Why is every artificial neural network layered? Why isn't each node just a separate process?


texts: Minimization of idle time with two kinds of actors

texts:
Let's say I have 2 different types of machines responsible for 2 different duties.

I have the PRODUCTION_MACHINES that EACH are able to produce a single unit of goods within 2 hours.

Then I have TRANSPORTER_MACHINES which are EACH able to collect and package away a single unit of goods from the production line at 95 seconds per TRANSPORTER_MACHINE.

QUESTION:

Assuming there are 5 PRODUCTION_MACHINES working, and they are operated at different starting times, how many TRANSPORTER_MACHINES do you need in order to MINIMIZE the IDLE_TIME incurred in the production process ?

(Whereby "IDLE_TIME" is defined as the time expended by EITHER the PRODUCTION_MACHINE or a TRANSPORTER_MACHINE waiting to have its good collected or produced.

HINT: Too many TRANSPORTER_MACHINES will add to the idle time as there are prone to be extra TRANSPORTER_MACHINES idly waiting for struggling PRODUCTION_UNITS to produce quickly enough to keep up with DEMAND.

... and vice-versa, too few TRANSPORTER_UNITS will also increase the idle time, this time for the PRODUCTION_MACHINES as some of them will have to wait for the struggling TRANSPORTER_MACHINES to keep up with their SUPPLY.)

Thank you very much !


texts: Connected components at most n/2 problem

texts:
Let $G$=$(V,E)$ with $V=$ {$1,2,...n$}  and $E$ = {$e_1$,$e_2$,...$e_m$}. On the set of edges we have a cost function $c : E → R$, with a property like if i $\neq$ j then c($e_i$) $\neq$ c($e_j$).
We also know that the graph is represtend with adjancency lists, $A(v)$,v$\in$V, and for $u$ $\in$ $A(v)$, i can find the cost of the edge in O(1).

What my exercise requires : I am given a function, which takes the graph $G$ and the function cost $c$. And it finds the set $T$ (which at begin is $empty$). How we obtain $T$? For every $v$ $\in$ $V$, i find the neighbor with the $minimum$ $cost$, the neighbor will be $u$. And in T i $add$ the edge $uv$ ($T ← T ∪ {vu}$).

I need to prove that the graph $G'$=$(V,T)$ doesn't have circuits and the number of connected components is at most $n/2$.

Thinking about the problem, i found a relation if the graph has a odd or a even number of vertex. The fact that we find for every $v$ $\in$ G, the neighbor with the minimum cost, means every vertex will have $at least$ one neighbor. Right? So we will have in $G'$ pairs like this, meaning we will have a lot of connected components with pairs which is at most $n/2$ cause of these pairs. Am I thinking right? But I have no idea how I could prove it a bit mathematically, not only in words.


texts: What is exponent of denormalized real in IEEE 754 floating point format?

texts:
I was reading this link.

Here I noticed that, in table titles "Float Values (b = bias)", in exponent column, entry for denormalized reals is $00..00$, but in value column, the entry is $-b+1$. Why is there $+1$? If we consider bias of $127$ for single precision format, shouldnt it be $0-127$ only? If its $-126$, then shouldnt the entry in the exponent column be $00..01$?

(The article seems to have taken from Stallings book specified in the references. Stallings book also says the same as above.)


texts: Optimal Item Locations given Traversal Paths

texts:
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a number of items smaller or equal to the number of locations, as well as a finite number of traversal paths for the items.
A traversal path is a fixed order in which the items are supposed to be passed through by passing through the locations the items are placed in. The traversal time/traversal distance is calculated by adding the traversal distances between the different locations that are passed through. Also, all traversal paths start and end at the same location.
I now try to find an (approximately) optimal way to allocate the items in the locations (e.g. leading to a minimal average traversal time/distance), without trying every possible allocation.
How can this problem be approached? What are useful algorithms for solving it and what computational complexity do they have?


texts: Lambda calculus and runtime inspection of the term

texts:
This is possibly related to reflection and quoting but I don't want to assume anything beforehand. Here is my requirement.

My typed lambda calculus (Curry style) is a simpler variant of Calculus of Constructions (CoC). Is it possible to write an analyzer (e.g., type checker) that inspects the runtime representation of the term within the calculus? For example, what I want is roughly along the lines of the following:

$\Gamma \vdash Analyzer : \forall \tau. AST~\tau \rightarrow Bool$

where $AST~\tau$ is the type constructor representing the abstract syntax tree of a term with type $\tau$. The expected body of Analyzer is something like below.

Analyzer e =  case e of
                | Var -> True
                | Abs t e' -> Analyzer e'
                ...

There are two roadblocks for me.

How to represent AST of $e$ within the same language?
How can the Analyzer access the intensional structure of the term $e$?

I am reading few papers on reflection and quotation. The details are a bit dense and I am looking for a simpler explanation. I believe I don't require the full complexity of type self-representation here.

If there is an alternate way of accomplishing this, I'll be more than happy to accept it as an answer. For example, it might be possible to stringify the input term $e$. However, the Analyzer still has to iterate through the intensional structure of $e$. Is that possible within the calculus?


texts: Multiplication mod 2 without extra registers

texts:
For an arbitrary bitstring $(x_1, x_2,\ldots, x_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output will be such a bitstring $(y_1, y_2,\ldots, y_n)$ that:
$$
\begin{pmatrix}
y_1 \\ y_2 \\ y_3 \\ \ldots \\ y_n
\end{pmatrix}
= M
\begin{pmatrix}
x_1 \\ x_2 \\ x_3 \\ \ldots \\ x_n
\end{pmatrix} \bmod 2 \ ,
$$
The extra registers are not allowed. The circuit $C$ should only contain $NOT$ and $CNOT$ gates (where $CNOT(x, y) = (x, x+y \bmod 2) $). The matrix $M$ is such that it permits for a reversible calculation.

The lower bound is trivially given by $O(n^2)$ operations. (That's how you would usually multiply matrices, if you had access to the original values of registers all the time. The question, however, is inspired by quantum computation, where one cannot store the initial values, and extra qubits are expensive.)

A known fact from quantum information is that such circuit can be constructed with at most $O(\exp(n))$ gates. The goal is to design it using a sub-exponential number of gates.


texts: An algorithm to compute 'bridginess' of a node in an undirected graph

texts:
I have an undirected graph which may or may not contain a 'bridge'. I'm defining a bridge as a relatively narrow connection between two larger clusters. Take for example the following graph:

A----B
 \  /
  \/
  C
  |
  D
  |
  E
  /\
 /  \
F----G

In this example D would be considered the 'bridgiest' node, because it connects the two clusters ABC and EFG.

I can think of one way to do this: namely to find the shortest path from every node to every other node and keep an internal counter for every node each time it is traversed, but this is obviously pretty unrealistic for anything but very trivial graphs.

I wasn't sure how to research this, so if you have information on related problems that could also be helpful!


texts:
I have been reading about the AI approaches, and I came across the AI emergent approach that has the following definition:

That is, the appearance of an entity with a sense of its own identity and agency within a sufficiently complex system.

And I have got trouble understanding the meaning I have read the the paper What is a complex system? and the definition in this site, But I have still got trouble understanding the whole expression what does sufficiently mean exactly in this expression?


texts: To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA?

texts: Why can't a TM simulate a PDA? Then we can easily construct a PDA P which is made from grammar G. And contruct a TM that simulates P to prove that this problem is decidable.


texts: If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm?

texts:
I don't understand what it means for A to be polynomial time reducible to B. I'm guessing is that we can revised the algorithm some how such that it becomes B, where B is a polynomial time algorithm.

Can someone point out if I have this completely wrong?


texts: Trying to prove semidecidability of an undecidable language

texts: I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, which consists of exactly five strings. Because $S$ is a property of the accepted language (there exists a TM that recognizes $L$), hypothesis of Rice Theorem applies, and because the set is not empty nor it is the set of all computable functions (equally, $S$ is non-trivial), it is undecidable. Yet, is it semidecidable? I was kinda attempting to prove that the complement of $S$ is semidecidable (thus guessing that $S$ is not semidecidable), but couldn't come up with anything useful.


texts: Removing $\epsilon$ transitions in a NPDA

texts:
NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.

However, NFA's with $\epsilon$ transitions could be converted to those without any $\epsilon$ transitions and hence they can be made to halt.

I was wondering if this is possible even for the case of NPDA's.

Is there a canonical epsilon-free form for PDAs


texts: What is a good resource to learn about oriented matroids in the context of digraphs and optimization?

texts: I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good introduction to oriented matroids, especially in the context of directed graphs? It's a bonus if the resource is suitable for an (under)graduate level course and is preferably even free.


texts:
First post here and i hope this is the correct forum to ask this. I'm currently on my 5th semester of Computer Engineering.
I´m having some hard time deciding on what to specialize or what to do when i go out from university.

Some areas or subjects i'm interested are Mathematics, programming, also gpgpu computing and how gpu/cpu micro architectures are developed/works and how to relate the hardware or architecture to the software.

That's some subjects i'm really interested to have a career when i go out, but i don't have a clear idea how is called to work on some of those areas or what i should look for, i'm really confused on what to do later when i graduate.

I hope some of you could clarify me this and give me an idea on what to look for.

Thanks for reading and sorry again if this is not the correct forum to post this.


texts: I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the subject. Does this problem have a name? What is known about the computational complexity of this problem?


texts: Multiple Constraint Knapsack Problem Dynamic Programming

texts:
Is there any way for solving the Knapsack problem when we are limited by several constraints?

Let's assume that we have a set of items in which we have value v that we want to maximize and we also have two constraints weight and volume that must be lower or equal than the values W and V respectively.

My question is, can this problem be solved using dynamic programming?


texts: Example for an undecidable language L such that L is reducible to its complement and vice versa

texts:
I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$,
but I am not able to find a concrete language and reduction.
Is there anything like this?


texts: How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

texts:
In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature of context-sensitive grammar (page 3):

<thing> b ::= b <thing>

where <thing> is a non-terminal and b is a terminal.

I cannot see how this fits the form

$$αAβ → αγβ $$
(where $α$ and $β$ are strings, $A$ is a non-terminal and $γ$ is a non-empty string) for context-sensitive grammar unless the right hand side ends with $b$ as well:

<thing> b ::= b <thing> b

in which case we get $α=ε$, $β=b$ and $γ = b\; \text{<thing>}$.

Perhaps I haven't viewed it in the right angle? (Or is this a typo?)


texts: How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$

texts:
Consider the following recurrence relationship.
\begin{eqnarray}
T(n) &=&
\begin{cases}
    T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
    2T\left(\displaystyle\frac{n-1}{2}\right),　&n \ \mbox{is odd number}&
\end{cases} \nonumber \\
T(1) &=& 1
\end{eqnarray}
How to prove there exists an infinite set $X$, that when $n∈X$, $T(n)=Ω(n)$?


texts: Understanding N process Peterson's algorithm

texts:
The intuitive informal description of two process Peterson's algorithm for process 0 can be given  as follows:

flag[0]=true;                   //I am ready to enter my critical region
turn=1;                         //but you may take your turn to enter your critical section

while(flag[1]==true && turn==1) //if you are ready to enter your critical section
                                //and if its your turn,
{ }                             //I will wait

//Critical Section

flag[0]=false;                  //I am no more ready to enter my critical section

Peterson's algorithm for n processes is given as follows:

Each process runs the following pseudo code:

lock(pid);
<critical section>;
unlock(pid);

where lock() and unlock() functions are defined as below..

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;
    turn[count] = i;
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
}

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;

Now I want to understand the n process Peterson's algorithm in same intuitive way, but I am unable to bring such informal explanation for it. To be precise I want to know the following:

In 2 process Peterson's algorithm, flag[i]=true means "process i is ready to enter its critical section". What does it mean in n process algorithm when flag[i]=true
In 2 process Peterson's algorithm, turn=1 means "its process 1's turn to enter its critical section". What does it mean in n process algorithm when turn[i]=x
How can we intuitively /  informally describe the line:

 "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"


texts: Cheeger constant of a graph versus conductance of a Markov chain

texts:
Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as
$$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$
Given some doubly-stochastic Markov chain $P$ on $G$, its conductance $\Phi(P)$ is defined as
$$ \Phi(P) = \min_{S\subset V,0<|S|\leq|V|}\frac{\sum_{i\in S,j\in\overline{S}}p_{ij}\pi_i}{\sum_{i\in S}\pi_i} = \min_{S\subset V,0<|S|\leq|V|}\frac{\sum_{i\in S,j\in\overline{S}}p_{ij}}{|S|}, $$
with $\pi$ the stationary distribution ($=1/|V|$ for $P$ doubly-stochastic) of $P$ and $p_{ij}$ its transition probabilities.

One easily sees that for any doubly-stochastic $P$: $\Phi(P)\leq h(G)$.
Is it known for which cases $\max_P\Phi(P)=h(G)$, with $P$ doubly-stochastic?


texts: How can you compute the expected edit distance in $O(2^{3n/2})$ time?

texts:
In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A naive solution would requite $O(2^{2n})$ edit distance calculations.

The answer gives optimized code but no mathematical or algorithmic explanation.  I cannot see how to achieve the claimed complexity. How is this possible?


texts: Count of different ways to express N as the sum of given numbers

texts:
I'm working on a case and I need some help :)
I need to find number of ways and solutions itself to express N as the sum of given numbers.
So, Sum (N) = 600 and the numbers from which I need to get the sum are: 50, 75, 100, 150, 200, 250.
I want to find all different ways (number of ways and solutions) to express 600 as the sum of these given numbers, order does not matter.
Thank you all in advance,
David


texts: Is variance taken into account when algorithm analysis is performed?

texts:
Silly question. I was wondering if the measure of "variance" is taken into account when the analysis of an algorithm is performed (asymptotic). In general best-case,worst-case,average-case are taken into account, even for more complicated analysis. However is the variance actually used sometimes?

I can imagine that in theory you can perform the analysis, but at my knowledge no-one seems actually to use such measure, and I wonder why.


texts: Proving that the language of regular expressions is not regular

texts:
Prove that the language consisting of all valid regular expressions is not regular.

I am approaching this using the Myhill-Nerode Theorem as follows:

I am trying to find a pairwise distinguishable set. I feel that the proof will have to do largely with bracket expansions leading to an invalid string.

So I thought I would could choose a set like $\left(\left(0^{star}\right)^{star}\right)^n$, which is a valid regular expression, and expand it continuously to show that the resulting strings are invalid regular expressions. But I am struggling to figure out how exactly to do this.

If anyone can tell me what a good string to choose would be and how I should go about the proof, I would greatly appreciate it!


texts: Smoothing frequencies without count data

texts:
I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies under condition 2. However, there are events that occur in condition 1 but not condition 2, resulting in divide-by-zero problems when I attempt to normalize.

For raw count data, I understand that there are a number of smoothing techniques (e.g. Witten-Bell) that can help sort this out, but I only have the frequencies, not the individual counts. In other words, I have frequencies like {0, 0.1, 0.2, 0.7} which could correspond to counts of {0, 1, 2, 7}, {0, 10, 20, 70}, etc. Are there any algorithms that are able to smooth this type of frequency data?


texts: How can solutions of a Diophantine equation be expressed as a language?

texts:
I was given the question

  Where does the following language fit in the Chomsky hierarchy?

  Nonnegative solutions $(x,y)$ to the Diophantine equation $3x-y=1$.

I understand languages like $L = \{ 0^n1^n \mid n \ge 1\}$, but this language confuses me. What do the words in the language look like? How could I represent it using a grammar or regular expression?


texts: Image Comparison tuned to Human Perception

texts:
Say I have two systems that take the same drawing commands and starts drawing on their respective platforms (i.e. HTML Canvas). After this is done, I want to save and compare these two images to ensure that they are perceptually the same, even though the shapes and colors may be very slightly off (non-perceptible differences).

I tried using perceptual hashes, but unfortunately it does not seem sensitive enough for this task. So for example, if you set 1000 pixels all black (for an image that is 1920x1080) on one and compare it to the other, it will be very obvious perceptually but the pHash algorithm will still return a 100% match.

I tried using nearest neighbor averaging for all pixels. Basically, for each pixel, I averaged its value with that of a number of its neighbors and set this value back to the pixel. This seems to work well with shapes that have hard edges and straight lines, because it only takes a very small localized change for it to be perceptibly different. For long curves, this is not so good since there can be moderate changes throughout the entire curve with it still being considered perceptually the same.

Does there exist an algorithm that can handle perceptually small changes in many possible shapes/curves? Should I use multiple algorithms to handle this task?


texts: How NFA decides how to break up a string?

texts:
If we have a language K, that word w=uv, accepts.
$K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \  \text{is not divisible by 3}}\}$. Can we land strings like aaaa in final state? How does NFA decides to break up the string in this case, would it be u = aa, v = aa (w accepted) or u = aaa, v = a (w is not accepted). Or doesn't matter and we can land everything as long as right decomposition exists.


texts: Fewest induced subgraphs of order <= k which cover every edge

texts:
I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-complete).

I have a graph $G$ with $|V|$ vertices. Every vertex has at least one edge connected to it. I want to find the induced subgraphs of $G$ of order $\leq k$, where every edge in $G$ is found in at least one subgraph and the number of subgraphs is minimized. I can assume as a pre-condition that a solution exists (there exist no cliques with order $>k$).

For example, here is a graph $G$ with 5 vertices. If $k=4$, there's no solution with 1 subgraph since there are more than 4 vertices in $G$. A solution for $k=4$ with 2 subgraphs is shown beside it:

The order of each subgraph can be less than $k$, so $\{\{1, 2, 3\},\{1, 2, 4, 5\}\}$ is another valid solution.

This is not a solution because the black edge between $2$ and $3$ is not covered by either subgraph:

All I'm looking for is a name for the problem, if it exists, so that I can research it and hopefully find an approximation algorithm. Having subgraph order $\leq k$ is a hard requirement but the "minimum number of subgraphs" part can be approximated as long as it's close to minium.


texts: Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

texts:
For Hoare's partitioning algorithm quicksort is implemented as such

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot);
        quickSort(array, pivot+1, last);

but Lomuto is

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot-1);
        quickSort(array, pivot+1, last);

Notice the first one doesn't have pivot-1. Is it correct to call these two the same implementations of the quicksort algorithm? I'm having trouble rapping my head around the difference, I thought quicksort worked on the premise that after one call to it the pivot is in it's final place (so do +1 and -1 for the rest of the array) but Hoare's method doesn't seem to work like this.


texts: What is the difference between "objective function", "error function", "criterion function" and "cost function" in the context of neural networks?

texts:
The title says it all: I have seen three functions so far, that seem to be the same / similar:

error function
criterion function
cost function
objective function

I am currently working on classification problems.

$$E(W) = \frac{1}{2} \sum_{x \in E}(t_x-o(x))^2$$

where $W$ are the weights, $E$ is the evaluation set, $t_x$ is the desired output (the class) of $x$ and $o(x)$ is the given output. This function
seems to be commonly called "error function".

But while reading about this topic, I've also seen the terms "criterion function" and "objective functin". Do they all mean  the same for neural nets?

edit:

Geoffrey Hinton called cross-entropy for softmax-neurons and $E(W) = \frac{1}{2} \sum_{x \in E}(t_x-o(x))^2$ a cost function.


texts: Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part

texts:
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $w_v : V \to \mathbb{N}$.  Let $\lambda$ be a known constant.
We need to find an exact cover $C \subseteq \mathbb{P}(V)$ of $V$ (with $\iota : V \to C$ being the associated injection) such that each $p \in C$ is a contiguous subset (interval) in $\mathbb{N}$ and
$$\lambda \left( \sum_{\iota(i) \neq \iota(j)} w_e(i, j) \right) + (1 - \lambda) \left( \max_{p \in C} \sum_{v \in p} w_v(v) \right)$$
is minimized.
In other words, we are trying to minimize a convex combination of the sum of the edge weights of the cut edges and the maximum total node weight for each part.
Is there an efficient algorithm for this problem? An approximation algorithm?


texts: FFT for expanded form of equation multiplication

texts:
I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?

For example, if you are multiplying $A(x) = 1 + 2x + 6x^2$ and $B(x) = 4 + 5x + 3x^2$ such that you get $C(x) = A(x) \cdot B(x) = 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4$ without going directly to the simplified answer?

Furthermore, is it possible to use FFT to do this expanded form multiplication in $O(n\,log\,n)$ time? If so, can you show me how to apply FFT to this scenario?


texts: 1 + ε approximation for non linear program

texts:
Let us assume that we have the following (non linear) program :

R = min { ( (c1^T)*x + d1 ) / ( (c2^T)x + d2 ) : Ax<=b , (c2^T)*x+d2>0}

We also assume that the feasible solution area is bounded and that the objective value of the optimal solution belongs to [L,U].

We assume that we know a δ >0 , so that for every feasible solution x , ( c2^T)*x >= δ .

How can I prove that for every ε > 0 there is an ( 1 + ε) approximation of the solution of R? ( We can use a linear programming algorithm as subroutine). In addition , which is the time complexity of that algorithm?


texts: What do you get when you add $O(n)$ to itself $n$ times?

texts: I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $O(n) + O (n) = O(n)$, saying that is not true if you add $O(n)$ to itself $n$ times. Is the answer $O(n^2)$?


texts: How is the space complexity O(LogN) for rangeSumBST problem

texts:
Recursive
class Solution {

    int ans;
    public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R)
                ans += node.val;
            if (L < node.val)
                dfs(node.left, L, R);
            if (node.val < R)
                dfs(node.right, L, R);
        }
    }
}

Iterative
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }
}

Source: https://leetcode.com/problems/range-sum-of-bst/solution/
Suppose L is Integer.MIN_VALUE and R is Integer.MAX_VALUE, then wouldn't it traverse through all the nodes. Since we need to check the worst case, shouldn't it be O(N) instead of O(logN)


texts:
I have this problem where I want to fill every black shape with a line. Every dot of the shape needs to be visited by the line. Preferably creating the shortest line. Any idea how I can achieve this or to what algorithm to look at?

I do not have any experience with algorithms so please keep it simple.


texts: Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes

texts: The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one source to all vertices. However, if I only want to know the path between two vertices, is there a faster algorithm that only finds the distance between two nodes?


texts:
Let $\mathsf E$ be deterministic exponential time with linear exponent.  Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict?  If so, what's the proof?

The time hierarchy immediately separates, for instance, $\mathsf E$ and $\mathsf{TIME}(2^{n\log n})$.  Diagonalizing directly on $\mathsf P$ yields essentially the same bound (because diagonalizing polynomials gives $n^n=2^{n\log n}$).  But none of this yields a linear exponential upper bound...


texts: Is the "Bidirectional Dijkstra" algorithm optimal?

texts:
In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g.,
this, and this. Also there is some software that uses this algorithm (for example this DBMS).
But some posts express doubts about the optimality of this algorithm, such this, and this. Which one is correct?  Is the bidirectional Dijkstra's algorithm optimal or not?


texts:
I am trying to understand the following algorithm for Self reducibility of Clique.

Here we have a "MBClique" black box algorithm, which return yes/no for parameters  where G is a graph and K is a natural number. It answers the question: "Does G has a clique of K size?" - Our aim is then to use this Decision algorithm to search what the actual Clique graph is.

Given this Graph below, we can see it has a clique of size 3.

The search algorithm is as follows (it was extracted from the CSE 200: Computability and Complexity @ UCSD lecture notes, page 4):

Ok, so now given an algorithm MBClique that returns yes/no we are trying to search the actual k-clique. Suppose the graph of the image above is sent as parameter and k=3.

In the first if it passes through.
In the immediate after For loop all edges that don't affect the size of the clique are removed.
Now my question: what is the Repeat...Until part of the algorithm for? In my understanding after the For loop I already have the respective Graph that I want as an answer.

Thanks.


texts: Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

texts:
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton.

Now Assume that $R$ is a regular language and $D$ is a deterministic context-free language.
How can we prove that $R\cup D$ is a DCFL?

Note : I saw a similiar theorem for the intersection.  But i'm new to PDA's and i almost have no idea how to prove this one.

Thanks in advance.


texts: I want to find secrecy rate of a main channel in case of Gaussian broadcast channel. e.g. I have a single transmitter and a receiver where eavesdropper wants to eavesdrop the communication over secondary channel. What will be the information rate, so eavesdropper can be kept ignorant of sent message